Regularity-free proof of Nikiforov–Rousseau goodness theorem
Question on Eliminating the Regularity Lemma from Nikiforov–Rousseau's General Theorem · arXiv:2109.09205
Status open high confidence
Fox, He, and Wigderson show that their techniques avoid the regularity lemma for Theorem 1.3 (books are p-good) and a partial case of Nikiforov–Rousseau's general goodness result (Theorem 2.1 of Nikiforov–Rousseau), but explicitly ask whether the elimination can be extended to the full generality of that theorem. No subsequent paper has been found that resolves this question for the full Nikiforov–Rousseau general theorem; related work on fan-complete Ramsey numbers (arXiv:2208.05829) proves regularity-free goodness results for other specific graph families, but does not address the general theorem.
Reviewer notes. No follow-up found that resolves the full generality of Nikiforov–Rousseau Theorem 2.1 without the regularity lemma. The paper arXiv:2208.05829 (Fan-complete Ramsey numbers, updated Jan 2025) proves regularity-free Ramsey goodness for fan-complete graphs K₁+nH using a stability-supersaturation approach, representing related but not fully general progress; it was not verified to directly address the open question. The conjecture is recent (arXiv 2021, journal 2023) and a thorough web search returned no resolution, supporting high confidence that it remains open.
Context
The authors show that their techniques can avoid the regularity lemma for Theorem 1.3, a special case of Nikiforov–Rousseau's most general goodness result. They ask whether this elimination can be extended to the full generality of that theorem, noting it would be very interesting to see how far these ideas can be pushed.
Notes. Posed in prose in the introduction as 'for example, is it possible to completely eliminate the use of the regularity lemma from the proof of [28, Theorem 2.1]?'.
Source paper
Ramsey goodness of books revisited
Jacob Fox, Xiaoyu He, Yuval Wigderson · 2023-07-14
https://arxiv.org/abs/2109.09205
PDF source