Erdős–Faudree–Rousseau–Schelp small-subgraph problem
For every integer , there exists a constant such that, for every sufficiently large integer , every graph on vertices satisfying contains a subgraph on at most vertices whose minimum degree is at least .
References
- Small subgraphs of large minimum degree — arXiv — Zach Hunter, Barnabás Janzer, Oliver Janzer, Benny Sudakov
Source: arXiv
Progress summary
The original conjecture has a claimed proof, while a new unrefereed preprint gives stronger quantitative results for related cases.
The Erdős–Faudree–Rousseau–Schelp conjecture asks whether one extra edge beyond the extremal threshold forces a subgraph of minimum degree at least after deleting a fixed positive proportion of the vertices. A preprint by Sauermann claims a complete proof; the latest work extends the quantitative picture beyond that statement.
Known results
- Erdős, Faudree, Rousseau, and Schelp (1990): deletion of at least vertices.
- A 2017 paper improved this to deletion of vertices.
- Sauermann’s preprint, submitted in 2017 and revised in 2018, claims deletion of at least vertices for some .
October 2026 quantitative extension
Hunter, Barnabás Janzer, Oliver Janzer, and Benny Sudakov report that, for even , the relevant bound is , alongside a tight-exponent forbidden-family result for all positive . This is claimed progress, not a refereed verification.
Current status (as of October 2026): The original conjecture has a claimed but unverified proof, and the newer quantitative extensions remain unrefereed; the broader formulation is not independently settled.
Solutions 0
No solutions have been posted yet.