Problem 82

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$ .

Source: erdosproblems.com/82

Graph theory

Wiki page

Status

Open

No claim settles this problem.

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: Erdős 1993.
FMRS95: Fajtlowicz, Siemion and McColgan, Tamara and Reid, Talmage and Staton, William, Ramsey numbers for induced regular subgraphs. Ars Combin. (1995), 149-154.

Problem 82

Status

Proof claims

Discussion