Problem 182

Let $k\geq 3$ . What is the maximum number of edges that a graph on $n$ vertices can contain if it does not have a $k$ -regular subgraph? Is it $\ll n^{1+o(1)}$ ?

Source: erdosproblems.com/182

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved, the site's label. The answer to the yes-or-no part is yes, first by Pyber's $f_k(n)<ck^2n\log n$ (Combinatorica 1985; an accepted partial claim, refereed, on its claim page (Pyber, 1985)). Janzer and Sudakov's Theorem 1.2 (Forum Math. Pi 11 (2023), e19; refereed), which the site credits with the resolution, gives for every $k$ a constant $C(k)$ with $f_k(n)\le\tfrac12C(k)\,n\log\log n$ and, with the Pyber--Rödl--Szemerédi construction, determines the order. The order is known up to constants and not asymptotically: the construction of Pyber, Rödl and Szemerédi (1995; Theorem 1, printed p. 42) gives $f_k(n)\ge cn\log\log n$ for every $k\ge3$ , and Chakraborti, Janzer, Methuku and Montgomery (Trans. Amer. Math. Soc., online 18 August 2026; cited from arXiv v2) prove that the maximum is $\Theta(k^2\,n\log\log n)$ once $n$ is large in terms of $k$ , tight up to an absolute constant. No asymptotic formula is known. The prize question of [Er78] for $k=3$ , whether $f_3(n)<Cn$ , is settled in the negative by the lower bound. Two accepted full claims, both refereed, carry the standing: Janzer and Sudakov's, on its claim page (Janzer and Sudakov, 2022), also reviewed through the curator's credit, and Chakraborti, Janzer, Methuku and Montgomery's, on its claim page (Chakraborti Janzer Methuku Montgomery, 2024). Pyber's bound and the Pyber--Rödl--Szemerédi lower bound are accepted partial claims, refereed, on Pyber's page and the Pyber--Rödl--Szemerédi page. One unreviewed proof claim of 2026-08-24 on the site's proof-claim tab asserts the $n^{1+o(1)}$ bound for induced $k$ -regular subgraphs, the variant Szemerédi asked about, which implies the answer yes to the yes-or-no part; it is a claimed partial claim on its claim page (Korsky, 2026) and bears no weight on the standing.

JaSu23: Janzer, Oliver and Sudakov, Benny, Resolution of the Erdős-Sauer problem on regular subgraphs. Forum Math. Pi 11 (2023), Paper No. e19, 13 pp.; doi:10.1017/fmp.2023.19 (received 2 November 2022, accepted 29 June 2023, published online 24 July 2023); arXiv:2204.12455 (v2, 15 August 2022). Theorem 1.2, p. 2. Library home: Janzer and Sudakov 2023.
CJMM24b: D. Chakraborti, O. Janzer, A. Methuku, and R. Montgomery, Regular subgraphs at every density. arXiv:2411.11785 (v1 18 November 2024; v2 26 November 2025); Trans. Amer. Math. Soc., doi:10.1090/tran/9694, published online 18 August 2026 (Crossref record; the journal version is not held). Theorems 1.4--1.5 and Propositions 1.6--1.7, p. 2 of v2. Library home: Chakraborti et al. 2024.
PRS95: Pyber, L. and Rödl, V. and Szemerédi, E., Dense graphs without 3-regular subgraphs. J. Combin. Theory Ser. B 63 (1995), 41--54, doi:10.1006/jctb.1995.1004 (the site's reference list titles it "Dense subgraphs without 3-regular subgraphs"). Theorem 1 and the König remark, printed p. 42; the proof, pp. 42--46; the concluding remarks, p. 53. Library home: Pyber and Szemerédi 1995; paged at Pyber and Szemerédi 1995, Theorem 1. Its theorem is also quoted as Theorem 1.1 of [JaSu23] and Theorem 1.2 of [CJMM24b].
Er75: Erdős, P., Some recent progress on extremal problems in graph theory. Congr. Numer. XIV (1975), 3--14; Section 3 (pp. 8--9 of the Rényi archive scan 1975-42.pdf, printed pp. 10--11 by the article's pagination). Library home: Erdős 1975.
Er78: Erdős, Paul, Problems and results in combinatorial analysis and combinatorial number theory. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) (1978), 29--40; p. 31. Library home: Erdős 1978; the passage is paged at Erdős 1978, Problem (p. 31).
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25--42; Part III, item 3. Library home: Erdős 1981, whose text is the Rényi archive's retyped 1981-16.pdf, without the journal's pagination; the passage is on its p. 7.
Er88: Erdős, P., Problems and results in combinatorial analysis and graph theory. Discrete Math. 72 (1988), 81--92; Section 6, p. 85. Not cited by the site. Library home: Erdős 1988.
Py85: Pyber, L., Regular subgraphs of dense graphs. Combinatorica 5 (1985), 347--349, doi:10.1007/BF02579250. Not filed in the library; its bound $f_k(n)<c_2k^2n\log n$ is quoted in [Er88], on p. 2 of [JaSu23] and as Theorem 1.1 of [CJMM24b]. Claim page: Pyber 1985.

Problem 182

Status

Proof claims

Discussion