Force a large regular induced subgraph: does $F(n)/\log n\to\infty$? (Erdős #82)
Statement
For a graph on $n$ vertices, call an induced subgraph regular if every one of its vertices has the same degree inside the subgraph (empty and complete induced subgraphs count as trivial regular subgraphs). Let $F(n)$ be the largest integer 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$$ as $n\to\infty$. Equivalently, letting $G(m)$ be the least integer such that every graph on $G(m)$ vertices contains a regular induced subgraph on at least $m$ vertices, show that $G(m)\le 2^{o(m)}$.
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean/Coq preferred — a formalisation stub already exists — else a full written proof) that $F(n)/\log n\to\infty$, equivalently $G(m)\le 2^{o(m)}$; OR a disproof, i.e. a construction plus proof that $F(n)\ll\log n$ along some subsequence. ADVANCES: prove a lower bound $F(n)\ge g(n)\log n$ with $g(n)\to\infty$ on an explicit graph family, strictly beyond the Ramsey guarantee $F(n)\gg\log n$ stated in the background, with proof; OR establish a new exact value or improved bound for $G(m)$ beyond the records in the background ($G(5)=17$, $G(6)\ge21$, $G(7)\ge30$, $G(k)\ge\frac{9}{163}k^2$), delivered as an explicit extremal graph together with a machine-verifiable exhaustiveness certificate; OR tighten the general upper bound below $F(n)\ll n^{1/2}$ with proof. Deliver the proof file, or the extremal graph plus verified search code, or the improved-bound proof.
Background
Conjectured by Erdős, Fajtlowicz, and Staton [Er93, p.340; Er95; Er97d]. Small exact values are $F(5)=3$ and $F(7)=4$. Ramsey's theorem gives $F(n)\gg\log n$ for free (a guaranteed large clique or independent set is trivially regular); Bollobás observed the upper bound $F(n)\ll n^{1/2+o(1)}$, improved by Alon, Krivelevich, and Sudakov [AKS07] to $n^{1/2}(\log n)^{O(1)}$ and by Dyson and McKay [DyMc26] to $F(n)\ll n^{1/2}$. Erdős's sharper form [Er93] asks, with $t(n)$ the largest guaranteed trivial (empty or complete) induced subgraph (so $t(n)\gg\log n$ by Ramsey), whether $F(n)-t(n)\to\infty$. In the inverse formulation, Fajtlowicz, McColgan, Reid, and Staton [FMRS95] found $G(1)=1$, $G(2)=2$, $G(3)=5$, $G(4)=7$, $G(5)\geq12$; Alexeev and McKay computed $G(5)=17$, $G(6)\geq21$, $G(7)\geq29$; and Dyson and McKay [DyMc26] proved $G(7)\geq30$ and $G(k)\geq\frac{9}{163}k^2$ for all large $k$. Listed as open on erdosproblems.com/82 (fetched 2026-07-13, status 'open', tagged 'graph theory'); a Lean 4 formalisation exists in google-deepmind/formal-conjectures; related to erdosproblems.com/1031. No Erdős prize is attached. The attacker's tool: exhaustive/randomised graph enumeration and SAT to extend the exact values and lower-bound records for $G(m)$ (nauty-style search), plus probabilistic/entropy arguments to push the lower bound on $F(n)$ above $\log n$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #82 (T. F. Bloom) | website |
| REF-02 | Lean 4 formalisation of Erdős #82 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.