- Series
- Job Candidate Talk
- Time
- Monday, February 14, 2022 - 11:00am for 1 hour (actually 50 minutes)
- Location
- ONLINE
- Speaker
- Luke Postle – University of Waterloo – luke.postle@gmail.com – https://www.math.uwaterloo.ca/~lpostle/
- Organizer
- Anton Bernshteyn

Link: https://bluejeans.com/398474745/0225

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t \ge 1$. Hadwiger's Conjecture is a vast generalization of the Four Color Theorem and one of the most important open problems in graph theory. Only the cases when $t$ is at most 6 are known. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t (\log t)^{0.5})$ and hence is $O(t (\log t)^{0.5})$-colorable. In a recent breakthrough, Norin, Song, and I proved that every graph with no $K_t$ minor is $O(t (\log t)^c)$-colorable for every $c > 0.25$, Subsequently I showed that every graph with no $K_t$ minor is $O(t (\log \log t)^6)$-colorable. Delcourt and I improved upon this further by showing that every graph with no $K_t$ minor is $O(t \log \log t)$-colorable. Our main technical result yields this as well as a number of other interesting corollaries. A natural weakening of Hadwiger's Conjecture is the so-called Linear Hadwiger's Conjecture that every graph with no $K_t$ minor is $O(t)$-colorable. We prove that Linear Hadwiger's Conjecture reduces to small graphs. In 2005, Kühn and Osthus proved that Hadwiger's Conjecture for the class of $K_{s,s}$-free graphs for any fixed positive integer $s \ge 2$. Along this line, we show that Linear Hadwiger's Conjecture holds for the class of $K_r$-free graphs for every fixed $r$.