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
Crnloglogn 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
Cr2nloglogn 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≈logn, where, perhaps surprisingly, the answer changes. More specifically, we show that every
n-vertex graph with average degree at least
min(Crlog(n/r),Cr2loglogn) contains an
r-regular subgraph. The bound
Crlog(n/r) is tight for
r≥logn, while the bound
Cr2loglogn is tight for
r<(\log n)^{1-\Omega(1)}. These results resolve a problem of Rödl and Wysocka from 1997 for almost all values of
r.
Among other tools, we develop 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.