Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


The claim. Yuval Wigderson, The Erdős--Simonovits compactness conjecture needs more assumptions, a two-page note hosted on the author's page, undated (PDF metadata 25 July 2022, the date this page carries; it is not a verified posting date), carded at its library home. Its Observation (p. 1, paged at observation_p1) takes F={K1,2,2K2}\mathcal F=\{K_{1,2},2K_2\}, the two-edge star and the two-edge matching. Any graph with two edges contains one of them, so ex(n;F)=1\mathrm{ex}(n;\mathcal F)=1 for n≥2n\ge2, while ex(n;K1,2)=⌊n/2⌋\mathrm{ex}(n;K_{1,2})=\lfloor n/2\rfloor and ex(n;2K2)=n−1\mathrm{ex}(n;2K_2)=n-1 for n≥4n\ge4. Both members are bipartite, so the statement's hypothesis holds and both are candidates for GG; neither satisfies ex(n;G)≤C ex(n;F)\mathrm{ex}(n;G)\le C\,\mathrm{ex}(n;\mathcal F) for all nn with any constant CC. The answer to the question is therefore no, for a family of forests. The note credits the example to Jordan Lefkowitz, points to Chvátal and Hanson for a more general form, and reports Simonovits's view that such examples were long known; it then states (p. 2), as Simonovits's suggestion, the no-forest form of the conjecture, which it assigns no status and which OpenAI 2026 disproves.

Standing. Claimed, not accepted. The note is unpublished and unrefereed; the site's commentary does not mention it, and the only mention on the site is a forum comment of 14 January 2026 (not the curator) pointing to it; Chapter 10 of OpenAI's report (p. 237) prints the same three extremal numbers for n≥4n\ge4 and calls the family folklore, which is a restatement, not a review. The problem page recomputes the five-line argument, and that recomputation is this project's own and awards no acceptance. Problem 180, the same question without the bipartite clause, records the same example.

Depends on. Nothing in this wiki: the argument is the note's five lines, recomputed on the problem page.