Loading Events

« All Events

  • This event has passed.

Jaehoon Kim (김재훈), Ramsey numbers of cycles versus general graphs

Monday, March 21, 2022 @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)


Jaehoon Kim (김재훈)
Department of Mathematical Sciences, KAIST

The Ramsey number $R(F,H)$ is the minimum number $N$ such that any $N$-vertex graph either contains a copy of $F$ or its complement contains $H$. Burr in 1981 proved a pleasingly general result that for any graph $H$, provided $n$ is sufficiently large, a natural lower bound construction gives the correct Ramsey number involving cycles: $R(C_n,H)=(n-1)(\chi(H)-1)+\sigma(H)$, where $\sigma(H)$ is the minimum possible size of a colour class in a $\chi(H)$-colouring of $H$. Allen, Brightwell and Skokan conjectured that the same should be true already when $n\geq |H|\chi(H)$.

We improve this 40-year-old result of Burr by giving quantitative bounds of the form $n\geq C|H|\log^4\chi(H)$, which is optimal up to the logarithmic factor. In particular, this proves a strengthening of the Allen-Brightwell-Skokan conjecture for all graphs $H$ with large chromatic number.

This is joint work with John Haslegrave, Joseph Hyde and Hong Liu


Monday, March 21, 2022
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B232
IBS (기초과학연구원)


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.