Resolution of the Erdős–Sauer problem on regular subgraphs
Oliver Janzer, Benny Sudakov
Abstract
Abstract 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\geq 3$ . We prove that any n -vertex graph with average degree at least $C_k\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 $C_k\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.