Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 7

Problem 82

Statement. Let $F(n)$ be maximal such that every graph on $n$ vertices contains a regular induced subgraph on at least $F(n)$ vertices. Prove that $F(n)/\log n\to \infty$ .

Status. Open.

Source. erdosproblems.com/82, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #82, https://www.erdosproblems.com/82.

References.

[AKS07] Alon, N. and Krivelevich, M. and Sudakov, B., Large nearly regular induced subgraphs. arXiv:0710.2106 (2007).
[DyMc26] P. Dyson and B. McKay, Ramsey numbers for regular induced subgraphs. arXiv:2604.08215 (2026).
[Er93] Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350. Chapter II, displays (12) and (13), the Fajtlowicz--Staton--Erdős questions, printed p. 340: "Let $f(n)$ be the largest integer for which every $G(n)$ contains an induced regular subgraph of $f(n)$ vertices. Is it true that (12) $f(n)/(\log n)\to\infty$ ", with "perhaps $f(n)>n^\epsilon$ holds for sufficiently small $\epsilon$ " and "Bollobás observed that $f(n)<cn^{1/2}$ "; the survey's $f$ is the page's $F$ . Library home: erdos_1993_my_favorite_solved_unsolved_problems_graph_theory.
[FMRS95] Fajtlowicz, Siemion and McColgan, Tamara and Reid, Talmage and Staton, William, Ramsey numbers for induced regular subgraphs. Ars Combin. (1995), 149-154.

Formalization. Statement in formal-conjectures.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (15)

Extremal and Structural Graph Theory extremal_graph_theory/alon_2007_large_nearly_regular_induced_subgraphs Proposition 1.1 (p. 2): f(n,K) >= n^{1-b/K} for K >= 2.1 Proposition 1.5 (p. 2): f(n,K) <= 7Kn/log n for constant K >= 2 Theorem 1.2 (p. 2): dense graphs have linear (1+eps)-nearly regular induced subgraphs Theorem 1.3 (p. 2): f(n, 1+eps) >= n^{eps^2/(250 ln(1/eps))}Theorem 1.4 (p. 2): f(n,1) <= O(n^{1/2} log^{3/4} n)extremal_graph_theory/dyson_2026_ramsey_numbers_regular_induced_subgraphs Theorem 1.1 (p. 2): N_{>=k} >= ((2e)^{-1} - o(1)) k^2 Theorem 1.2 (p. 2): N_5 = 21, N_{>=5} = 17 and lower bounds for k = 6, 7 Theorem 2.1 (p. 2): N_{>=k} >= (9/163) k^2 for sufficiently large k Theorem 4.2 (p. 11): unions of blown-up cycles with no induced regular subgraph of prime order p Theorem 4.3 (p. 12): N_{qp} >= p^2 + 2q^2p - 4qp + 2 + (p-1)min{q-1, p-q} for primes q < p Theorem 4.4 (p. 12): N_{4p} >= p^2 + 11p - 1 for prime p >= 7 extremal_graph_theory/erdos_1993_my_favorite_solved_unsolved_problems_graph_theory

Graph