Loading Events

« All Events

  • This event has passed.
:

Seonghyuk Im (임성혁), Large clique subdivisions in graphs without small dense subgraphs

November 30 Tuesday @ 4:30 PM - 5:30 PM KST

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

Speaker

What is the largest number $f(d)$ where every graph with average degree at least $d$ contains a subdivision of $K_{f(d)}$? Mader asked this question in 1967 and $f(d) = \Theta(\sqrt{d})$ was proved by Bollobás and Thomason and independently by Komlós and Szemerédi. This is best possible by considering a disjoint union of $K_{d,d}$. However, this example contains a much smaller subgraph with the almost same average degree, for example, one copy of $K_{d,d}$.

In 2017, Liu and Montgomery proposed the study on the parameter $c_{\varepsilon}(G)$ which is the order of the smallest subgraph of $G$ with average degree at least $\varepsilon d(G)$. In fact, they conjectured that for small enough $\varepsilon>0$, every graph $G$ of average degree $d$ contains a clique subdivision of size $\Omega(\min\{d, \sqrt{\frac{c_{\varepsilon}(G)}{\log c_{\varepsilon}(G)}}\})$. We prove that this conjecture holds up to a multiplicative $\min\{(\log\log d)^6,(\log \log c_{\varepsilon}(G))^6\}$-term.

As a corollary, for every graph $F$, we determine the minimum size of the largest clique subdivision in $F$-free graphs with average degree $d$ up to multiplicative polylog$(d)$-term.

This is joint work with Jaehoon Kim, Youngjin Kim, and Hong Liu.

Details

Date:
November 30 Tuesday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:
,

Venue

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

Organizer

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.