기초과학연구원 이산수학그룹
A graph is $H$-Ramsey if every two-coloring of its edges contains a monochromatic copy of $H$. Define the $F$-Ramsey number of $H$, denoted by $r_F(H)$, to be the minimum number of copies of $F$ in a graph which is $H$-Ramsey. This generalizes the Ramsey number and size Ramsey number of a graph. Addressing a question …
We present the KKM theorem and a recent proof method utilizing it that has proven to be very useful for problems in discrete geometry. For example, the method was used to show that for a planar family of convex sets with the property that every three sets are pierced by a line, there are three …
The Dedekind's Problem asks the number of monotone Boolean functions, a(n), on n variables. Equivalently, a(n) is the number of antichains in the n-dimensional Boolean lattice $^n$. While the exact formula for the Dedekind number a(n) is still unknown, its asymptotic formula has been well-studied. Since any subsets of a middle layer of the Boolean …
Melchior’s Inequality (1941) implies that, in a rank-3 real-representable matroid, the average number of points in a line is less than three. This was extended to the complex-representable matroids by Hirzebruch in 1983 with the slightly weaker bound of four. In this talk, we discuss and sketch the proof of the recent result that, in …
For any finite point set $P \subset \mathbb{R}^d$, we denote by $\text{diam}(P)$ the ratio of the largest to the smallest distances between pairs of points in $P$. Let $c_{d, \alpha}(n)$ be the largest integer $c$ such that any $n$-point set $P \subset \mathbb{R}^d$ in general position, satisfying $\text{diam}(P) < \alpha\sqrt{n}$ (informally speaking, `non-elongated'), contains a …
The uniform Turán density $\pi_u(F)$ of a hypergraph $F$, introduced by Erdős and Sós, is the smallest value of $d$ such that any hypergraph $H$ where all linear-sized subsets of vertices of $H$ have density greater than $d$ contains $F$ as a subgraph. Over the past few years the value of $\pi_u(F)$ was determined for …
We prove the existence of a computable function $f\colon\mathbb{N}\to\mathbb{N}$ such that for every integer $k$ and every digraph $D$ either contains a collection $\mathcal{C}$ of $k$ directed cycles of even length such that no vertex of $D$ belongs to more than four cycles in $\mathcal{C}$, or there exists a set $S\subseteq V(D)$ of size at …
There has been a raising interest on the study of perfect matchings in uniform hypergraphs in the past two decades, including extremal problems and their algorithmic versions. I will introduce the problems and some recent developments.
Amazon drivers hit the road every day, each taking a Prime van in a traveling salesman problem tour through 150 or more customer stops. But even a whisper of the TSP strikes fear in the heart of the computing world. A Washington Post article reported it would take "1,000 years to compute the most efficient …
We prove a conjecture of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak, that for every graph $H$, there is a polynomial $p$ such that for every positive integer $s$, every graph of average degree at least $p(s)$ contains either $K_{s,s}$ as a subgraph or contains an induced subdivision of $H$. This improves upon a result …