Loading Events

« All Events

  • This event has passed.
:

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

October 8 Tuesday @ 4:30 PM - 5:30 PM

Room 1501, Bldg. E6-1, KAIST

Speaker

Alexandr V. Kostochka
University of Illinois at Urbana-Champaign
https://faculty.math.illinois.edu/~kostochk/

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.

Details

Date:
October 8 Tuesday
Time:
4:30 PM - 5:30 PM
Event Category:
Event Tags:
,

Venue

Room 1501, Bldg. E6-1, KAIST

Organizer

Sang-il Oum