• This event has passed.

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

## Tuesday, November 30, 2021 @ 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:
Tuesday, November 30, 2021
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:
,

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

## Organizer

Sang-il Oum (엄상일)
View Organizer Website
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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