Loading Events

« All Events

  • This event has passed.
:

Luke Postle, Further progress towards Hadwiger’s conjecture

Thursday, September 17, 2020 @ 10:00 AM - 11:00 AM KST

Zoom ID: 934 3222 0374 (ibsdimag)

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable.  Recently, Norin, Song and I showed that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta > 1/4$, making the first improvement on the order of magnitude of the $O(t\sqrt{\log t})$ bound. Here we show that every graph with no $K_t$ minor is $O(t (\log t)^{\beta})$-colorable for every $\beta > 0$; more specifically, they are $O(t (\log \log t)^{6})$-colorable.

Details

Date:
Thursday, September 17, 2020
Time:
10:00 AM - 11:00 AM KST
Event Category:
Event Tags:

Venue

Zoom ID: 934 3222 0374 (ibsdimag)

Organizer

O-joung Kwon (권오정)
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.