Regular subgraphs at every density

In 1975, Erdős and Sauer asked to estimate, for any constant r r , the maximum number of edges an n n -vertex graph can have without containing an r r -regular subgraph. In a recent breakthrough, Janzer and Sudakov proved that any n n -vertex graph with no r r -regular subgraph has at most C r n log ⁡ log ⁡ n C_r 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 r . We prove that every n n -vertex graph without an r r -regular subgraph has at most C r 2 n log ⁡ log ⁡ n Cr^2 n \log \log n edges. This bound is tight up to the value of C C for n ≥ n 0 ( r ) n\geq n_0(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 r (i.e., not just when r r is a constant), apart from a small error term at a transition point near r ≈