BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211130T163000
DTEND;TZID=Asia/Seoul:20211130T173000
DTSTAMP:20260422T224842
CREATED:20211130T073000Z
LAST-MODIFIED:20240707T080630Z
UID:4852-1638289800-1638293400@dimag.ibs.re.kr
SUMMARY:Seonghyuk Im (임성혁)\, Large clique subdivisions in graphs without small dense subgraphs
DESCRIPTION: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}$. \nIn 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. \nAs 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. \nThis is joint work with Jaehoon Kim\, Youngjin Kim\, and Hong Liu.
URL:https://dimag.ibs.re.kr/event/2021-11-30/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR