Regular subgraphs at every density

In 1975, Erdős and Sauer asked to estimate, for any constant r, the maximum number of edges an n-vertex graph can have without containing an r-regular subgraph. In a recent breakthrough, Janzer and Sudakov proved that any n-vertex graph with no r-regular subgraph has at most Cr n log log n edges, matching an earlier lower bound by Pyber, Rödl and Szemerédi and thereby resolving the Erdős–Sauer problem up to a constant depending on r. We prove that every n-vertex graph without an r-regular subgraph has at most Cr2 n log log n edges. This bound is tight up to the value of C for n ≥ n0 (r) and hence resolves the Erdős–Sauer problem up to an absolute constant. Moreover, we obtain similarly tight results for the whole range of possible values of r (i.e., not just when r is a constant), apart from a small error term at a transition point near r ≈ log n, where, perhaps surpris- ingly, the answer changes. More specifically, we show that every n-vertex graph with average degree at least min(Cr log(n/r), Cr2 log log n) contains an r-regular subgraph. The bound Cr log(n/r) is tight for r ≥ log n, while the bound Cr2 log log n is tight for r (log n)1−Ω(1) . These results resolve a problem of Rödl and Wysocka from 1997 for almost all values of r. To find regular subgraphs efficiently, we replace and improve substantial parts of the Janzer–Sudakov framework for the Erdős–Sauer problem. Our strategies involve the algebraic techniques of Alon, Friedland and Kalai, the recent breakthroughs on the sunflower conjecture, techniques to find almost-regular subgraphs developed from Pyber’s work, and, crucially, a novel random process that efficiently finds a very nearly regular subgraph in any almost-regular graph. A key step in our proof uses this novel random process to show that every K-almost-regular graph with average degree d contains an r-regular subgraph for some r = ΩK (d), which is of independent interest.