기초과학연구원 이산수학그룹
We say a graph $G$ is $(2,m)$-linked if, for every choice of $m+2$ distinct vertices $a_1,\ldots,a_m,b_1,b_2$ in $G$, there exist two vertex-disjoint connected subgraphs $A$ and $B$ of $G$ such that $\{a_1,\ldots,a_m\}\subseteq V(A)$ and $\{b_1,b_2\}\subseteq V(B)$. A related notion is $k$-linkedness: a graph is $k$-linked if, for any distinct vertices $s_1,\ldots,s_k,t_1,\ldots,t_k$, it contains $k$ pairwise …
In the 1970s, Erdős and Szemerédi conjectured that for any $n \ge k-1\ge 2$, any collection of subsets of $$ not containing a $k$-sunflower has size at most $c_k^n$ for some $c_k<2$. In the $k=3$ case, this follows from the work of Croot, Lev, and Pach and Ellenberg and Gijswijt on the cap-set problem, through …
TBA
TBA
TBA
In the 1980s, Ron Graham asked whether every red/blue coloring of the positive integers contains a monochromatic Pythagorean triple and offered a $100 prize for the answer. The bounty was claimed in 2016 by Heule, Kullmann, and Marek, who showed that every such coloring of has a monochromatic triple. Their proof used SAT solvers and …
The codegree Turán density γ(F) of a k-uniform hypergraph F is the smallest γ ≥ 0 with the following property: if every set of k−1 vertices in an n-vertex k-uniform hypergraph H lies in at least (γ+o(1))n edges, then H contains a copy of F for all sufficiently large n. Piga, Sanhueza-Matamala, and Schacht proved …