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
Department of Mathematics, 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 (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.