Loading Events

« All Events

  • This event has passed.

Alexandr V. Kostochka, On Ramsey-type problems for paths and cycles in dense graphs

Tuesday, October 8, 2019 @ 4:30 PM - 5:30 PM KST

Room 1501, Bldg. E6-1, KAIST


Alexandr V. Kostochka
University of Illinois at Urbana-Champaign

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.


Tuesday, October 8, 2019
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room 1501, Bldg. E6-1, KAIST


Sang-il Oum (엄상일)