기초과학연구원 이산수학그룹
Determining the density required to ensure that a host graph G contains some target graph as a subgraph or minor is a natural and well-studied question in extremal combinatorics. The celebrated 50-year-old Erdős-Sós conjecture states that for every k, if G has average degree exceeding k-2 then it contains every tree T with k vertices …
Given a hypergraph $H=(V,E)$, we say that $H$ is (weakly) $m$-colorable if there is a coloring $c:V\to $ such that every hyperedge of $H$ is not monochromatic. The (weak) chromatic number of $H$, denoted by $\chi(H)$, is the smallest $m$ such that $H$ is $m$-colorable. A vertex subset $T \subseteq V$ is called a transversal …
Dirac's theorem determines the sharp minimum degree threshold for graphs to contain perfect matchings and Hamiltonian cycles. There have been various attempts to generalize this theorem to hypergraphs with larger uniformity by considering hypergraph matchings and Hamiltonian cycles. We consider another natural generalization of the perfect matchings, Steiner triple systems. As a Steiner triple system …
For $d\ge 2$ and an odd prime power $q$, let $\mathbb{F}_q^d$ be the $d$-dimensional vector space over the finite field $\mathbb{F}_q$. The distance between two points $(x_1,\ldots,x_d)$ and $(y_1,\ldots,y_d)$ is defined to be $\sum_{i=1}^d (x_i-y_i)^2$. An influential result of Iosevich and Rudnev is: if $E \subset \mathbb{F}_q^d$ is sufficiently large and $t \in \mathbb{F}_q$, then …
Given a set of lines in $\mathbb R^d$, a joint is a point contained in d linearly independent lines. Guth and Katz showed that N lines can determine at most $O(N^{3/2})$ joints in $\mathbb R^3$ via the polynomial method. Yu and I proved a tight bound on this problem, which also solves a conjecture proposed …
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 …