Resolution of the Erdős-Sauer problem on regular subgraphs.

In this paper, we completely resolve the well-known problem of Erdős and Sauer from 1975 which asks for the maximum number of edges an n-vertex graph can have without containing a k-regular subgraph, for some fixed integer k ≥ 3. We prove that any n-vertex graph with average degree at least Ck log log n contains a k-regular subgraph. This matches the lower bound of Pyber, Rödl and Szemerédi and substantially improves an old result of Pyber, who showed that average degree at least Ck log n is enough. Our method can also be used to settle asymptotically a problem raised by Erdős and Simonovits in 1970 on almost regular subgraphs of sparse graphs and to make progress on the well-known question of Thomassen from 1983 on finding subgraphs with large girth and large average degree. [ABSTRACT FROM AUTHOR]