Erdős Problem #82
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
A graph is regular if every vertex has the same number of neighbours. Every clique and every independent set is regular, but there are many other examples. Erdős, Fajtlowicz and Staton ask how large a regular induced subgraph one can always find in an arbitrary \(n\) vertex graph.
Let \(F(n)\) be the largest guaranteed order. Erdős #82 asks whether
The word induced is important: the selected vertices must retain exactly the edges they had in the original graph, without selectively deleting edges to manufacture regularity.
A small example
A cycle \(C_5\) is 2-regular, so all five vertices form a regular induced subgraph. A star \(K_{1,4}\) has an induced independent set of four leaves, which is 0-regular, but the full star is not regular. A clique and an independent set always provide trivial regular induced subgraphs.
Ordinary Ramsey theory guarantees a clique or independent set of logarithmic order. Proving that the worst graph always has a substantially larger regular induced subgraph is the open issue; exhibiting a single highly regular graph does not suffice.
What is known
The conjecture remains OPEN. Alon, Krivelevich and Sudakov, Large nearly regular induced subgraphs, proved the historical bounds
Dyson and McKay's 2026 primary preprint sharpens the worst-case upper bound to a constant multiple of \(\sqrt n\) and investigates exact small Ramsey thresholds.
A further 8 August 2026 preprint by Ariel Edgardo Levy, Sharp asymptotics for regular induced subgraphs of type-based random graphs, states in its Theorem 1.2 that
Its Theorem 1.3 gives a matching bound inside a specified type-based random-graph family. That is not a lower bound for every graph and does not settle the proposed superlogarithmic growth. The new preprint postdates the maintained catalogue's April 2026 revision; its full proof is not independently certified here.
GCL's current state
The original source issue is #1351. GCL inspected the 2008 primary abstract, 2026 Dyson–McKay abstract and Levy's 2026 primary Theorems 1.2–1.3. The protected Lean statement at Formal Conjectures snapshot 85f86371 defines regular induced subgraphs and the limit; its proof hole is not a proof. No exact semantic equivalence or kernel replay is claimed.
An authenticated RESULT/1 source report is posted on the original issue. It is unadjudicated source evidence, not independent proof certification or editorial admission.
What remains
A bounded verification task is to enumerate graphs on at most six vertices and calculate the maximal size of a regular induced subgraph, then take the minimum across graphs of each order. Acceptance: retain all edges induced by each vertex subset, allow degree zero, and produce a certificate for both minimizer and all-graph bound. This finite exercise tests the definition only. Separately compare the pinned Lean definition against the current source semantics without altering the protected provider.
Sources and claim boundaries
- Alon, Krivelevich and Sudakov, arXiv:0710.2106.
- Dyson and McKay, arXiv:2604.08215 (2026); Levy, arXiv:2608.08169 (August 2026), primary theorem statements checked, full proofs not independently reproduced.
- Maintained Erdős #82; original GCL issue #1351.
No new universal lower bound, full formal certification, or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1351 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.