기초과학연구원 이산수학그룹
On October 8, 2019, Prof. Alexandr V. Kostochka from the University of Illinois at Urbana-Champaign gave a colloquium talk at the KAIST Mathematical Sciences – IBS Discrete Mathematics Group Joint Colloquium. The title of his talk was “On Ramsey-type problems for paths and cycles in dense graphs“. He will stay one week at IBS Discrete Mathematics Group.
A well-known Ramsey-type puzzle for children is to prove that among any 6 people either there are 3 who know each other or there are 3 who do not know each other. More generally, a graph $G$ arrows a graph $H$ if for any coloring of the edges of $G$ with two colors, there is a monochromatic copy of $H$. In these terms, the above puzzle claims that the complete $6$-vertex graph $K_6$ arrows the complete $3$-vertex graph $K_3$.
We consider sufficient conditions on the dense host graphs $G$ to arrow long paths and even cycles. In particular, for large $n$ we describe all multipartite graphs that arrow paths and cycles with $2n$ edges. This implies a conjecture by Gyárfás, Ruszinkó, Sárkőzy and Szemerédi from 2007 for such $n$. Also for large $n$ we find which minimum degree in a $(3n-1)$-vertex graph $G$ guarantees that $G$ arrows the $2n$-vertex path. This yields a more recent conjecture of Schelp.
This is joint work with Jozsef Balogh, Mikhail Lavrov and Xujun Liu.