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

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:
Tuesday, October 8, 2019
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:
,

Venue

Room 1501, Bldg. E6-1, KAIST

Organizer

Sang-il Oum (엄상일)
Website:
https://dimag.ibs.re.kr/home/sangil/
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.