Georgia Institute of Technology College of Sciences

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.