Page 285 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 285
EXTREMAL AND PROBABILISTIC COMBINATORICS (MS-20)
Erdos-Rademacher Problem
Oleg Pikhurko, pikhurko@gmail.com
University of Warwick, United Kingdom
We will give an overview of recent results on the Erdos-Rademacher Problem which asks for
the minimum number of r-cliques that a graph with n vertices and m edges can have.
On Hadwiger’s Conjecture
Luke Postle, lpostle@uwaterloo.ca
University of Waterloo, Canada
We discuss recent progress on Hadwiger’s conjecture. In 1943, Hadwiger conjectured that ev-
ery graph with no Kt minor is (t − 1)-colorable for every t ≥ 1. In the 1980s, Kostochka
and√Thomason independently√proved that every graph with no Kt minor has average degree
O(t log t) and hence is O(t log t)-colorable. Recently, Norin, Song and I showed that ev-
ery graph with no Kt minor is O(t(log t)β)-colora√ble for every β > 1/4, making the first
improvement on the order of magnitude of the O(t log t) bound. Here we show that every
graph with no Kt minor is O(t(log t)β)-colorable for every β > 0; more specifically, they are
O(t(log log t)6)-colorable.
283
Erdos-Rademacher Problem
Oleg Pikhurko, pikhurko@gmail.com
University of Warwick, United Kingdom
We will give an overview of recent results on the Erdos-Rademacher Problem which asks for
the minimum number of r-cliques that a graph with n vertices and m edges can have.
On Hadwiger’s Conjecture
Luke Postle, lpostle@uwaterloo.ca
University of Waterloo, Canada
We discuss recent progress on Hadwiger’s conjecture. In 1943, Hadwiger conjectured that ev-
ery graph with no Kt minor is (t − 1)-colorable for every t ≥ 1. In the 1980s, Kostochka
and√Thomason independently√proved that every graph with no Kt minor has average degree
O(t log t) and hence is O(t log t)-colorable. Recently, Norin, Song and I showed that ev-
ery graph with no Kt minor is O(t(log t)β)-colora√ble for every β > 1/4, making the first
improvement on the order of magnitude of the O(t log t) bound. Here we show that every
graph with no Kt minor is O(t(log t)β)-colorable for every β > 0; more specifically, they are
O(t(log log t)6)-colorable.
283
