기초과학연구원 이산수학그룹
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 …
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 …
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 …
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 …
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 …
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 …
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 …
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)$ …
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 …
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 …