Graphs without Large Complete Minors are Quasi-Random

Abstract

We answer a question of Sós by showing that, if a graph G of order n and density p has no complete minor larger than would be found in a random graph G ( n , p ), then G is quasi-random, provided either p > 0.45631 … or κ( G ) [ges ] n (log log log n )/(log log n ), where 0.45631 … is an explicit constant. The results proved can also be used to fill the gaps in an argument of Thomason, describing the extremal graphs having no K t minor for given t .