The extremal function for $K_p$ minors

Other Talks
Tuesday, November 6, 2018 - 12:30pm
30 minutes
Skiles 006
Georgia Tech

This talk is organized by the Association for Women in Math (AWM). Everyone is welcome to attend.

In 1968, Mader showed that for every integer $p = 1, 2, …, 7$, agraph on $n \geq p$ vertices and at least $(p-2)n - \binom{p-1}{2} + 1$ edgeshas a $K_p$ minor. However, this result is false for $p = 8$ with the counter-example K2,2,2,2,2. In this talk, we will discuss this function presented byMader for $K_p$ where $p$ is bigger. We will also discuss related resultsproved using probabilistic methods and the relation of this problem toHadwiger’s conjecture.