Loading Events

« All Events

  • This event has passed.

Hong Liu, A proof of Mader’s conjecture on large clique subdivisions in $C_4$-free graphs

Thursday, December 12, 2019 @ 4:30 PM - 5:30 PM KST

Room 1401, Bldg. E6-1, KAIST


Hong Liu (刘鸿)
Mathematics Institute, University of Warwick, UK
Given any integers $s,t\geq 2$, we show there exists some $c=c(s,t)>0$ such that any $K_{s,t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $cd^{\frac{1}{2}\frac{s}{s-1}}$ vertices. In particular, when $s=2$ this resolves in a strong sense the conjecture of Mader in 1999 that every $C_4$-free graph has a subdivision of a clique with order linear in the average degree of the original graph. In general, the widely conjectured asymptotic behaviour of the extremal density of $K_{s,t}$-free graphs suggests our result is tight up to the constant $c(s,t)$. This is joint work with Richard Montgomery.


Thursday, December 12, 2019
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room 1401, Bldg. E6-1, KAIST


Jaehoon Kim (김재훈)
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.