Erdoes #575 - working report - Erdős Problem a Day

Erdős problem #575 — wave9r

Date checked: 2026-07-28 UTC.

Claim labels used below are the requested ones:

(a) elementary-rigorous: proved here from definitions, without an external theorem.
(b) rigorous-modulo-named-theorem: depends on the theorem explicitly named.
(c) plausible/structural-unverified: not asserted as a theorem.
(d) computational-only: established only in the stated finite search range.

Direct observations about a web page or PDF are marked “source check”; any mathematical conclusion drawn from them still receives one of (a)–(d).

0. Mandatory live-page gate

I fetched https://www.erdosproblems.com/575 on 2026-07-28 through the Bright Data browser route, then separately fetched its discussion page and LaTeX-source view. The browser returned the rendered page, rather than a Cloudflare challenge.

Live statement

The setup immediately preceding the question defines, for a finite family \(\mathcal F\) of finite graphs,

\operatorname{ex}(n;\mathcal F) :=\max\{e(H): |V(H)|=n,\ H\text{ contains no member of }\mathcal F\},

and notes \(\operatorname{ex}(n;\mathcal F)\leq \operatorname{ex}(n;G)\) for every \(G\in\mathcal F\). This is an equivalent formal transcription of the live-page setup.

The exact live-page question is:

Is it true that, for every \(\mathcal{F}\), if there is a bipartite graph in \(\mathcal{F}\) then there exists some bipartite \(G\in\mathcal{F}\) such that \[ > \mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})? > \]

Here \(\ll_{\mathcal F}\) asks for a constant depending only on the fixed family, not on \(n\).

Status, comments, and worker markers

(a; source check) The live status is OPEN; the page says it was last

edited 18 January 2026.

(a; source check) It lists 0 claimed proofs, **Currently working:

None, and Interested in collaborating: None**. Thus the mandatory stop condition was not triggered.

(a; source check) The page attributes the problem to Erdős and

Simonovits, cites [ErSi82], says “See also [180],” and links it as problem #51 in the older graph-problem collection.

(c; as a comment alone) There is one comment, by Kevin Barreto on

14 January 2026. It points to a note by Yuval Wigderson, says that the statement as written has a trivial counterexample, and says that a proposed repair excludes forests. The site explicitly warns that comments are not verified.

(a; independently checked below) The mathematical content of that

comment is correct. It is proved from scratch below and is also confirmed by two primary sources.

The linked live page for problem #180 now explicitly records Zach Hunter's “folklore counterexample”: a forbidden star together with a forbidden matching, both having at least two edges. It says the family extremal number is bounded while each individual extremal number is linear. Thus the construction below is known, not claimed here as novel.

1. Result

(a) The live statement is false. Take

\boxed{\mathcal F=\{K_{1,2},\,2K_2\}},

where \(2K_2\) is a matching of two edges. Both members of \(\mathcal F\) are bipartite. For every positive integer \(n\),

\operatorname{ex}(n;\mathcal F)= \begin{cases} 0,&n=1,\\ 1,&n\geq2, \end{cases} \tag{1}

\operatorname{ex}(n;K_{1,2})=\left\lfloor\frac n2\right\rfloor, \tag{2}

and

\operatorname{ex}(n;2K_2)= \begin{cases} 0,&n=1,\\ 1,&n=2,\\ 3,&n=3,\\ n-1,&n\geq4. \end{cases} \tag{3}

Consequently, for \(n\geq4\),

\frac{\operatorname{ex}(n;K_{1,2})} {\operatorname{ex}(n;\mathcal F)} =\left\lfloor\frac n2\right\rfloor\longrightarrow\infty, \qquad \frac{\operatorname{ex}(n;2K_2)} {\operatorname{ex}(n;\mathcal F)} =n-1\longrightarrow\infty. \tag{4}

There are only two possible choices of bipartite \(G\in\mathcal F\), and both ratios are unbounded. No constant implicit in \(\ll_{\mathcal F}\) can therefore exist.

2. From-scratch proof

2.1 Both forbidden graphs are bipartite

(a) \(K_{1,2}\) has bipartition “centre versus two leaves.” The graph \(2K_2\) has a bipartition obtained by putting one endpoint of each edge on each side. Hence the hypothesis that \(\mathcal F\) contain a bipartite graph is satisfied—in fact, every member is bipartite.

2.2 The family extremal number

(a) Let \(H\) be a graph with two distinct edges. Those edges either share a vertex or they do not.

If they share a vertex, their union contains \(K_{1,2}\).
If they do not, they form \(2K_2\).

Thus every \(\mathcal F\)-free graph has at most one edge. Conversely, a one-edge graph contains neither forbidden graph. This proves (1), including the trivial \(n=1\) boundary case.

2.3 Forbidding \(K_{1,2}\)

(a) A graph is \(K_{1,2}\)-free exactly when every vertex has degree at most one. Such a graph is a matching together with isolated vertices, so it has at most \(\lfloor n/2\rfloor\) edges. A matching covering all but at most one vertex attains that bound. This proves (2).

2.4 Forbidding \(2K_2\)

(a) A \(2K_2\)-free graph has a pairwise-intersecting edge set. If it has at most one edge there is nothing to prove. Otherwise choose two of its edges, written \(ab\) and \(ac\).

Every further edge must meet both \(ab\) and \(ac\). It must therefore either contain \(a\), or be the edge \(bc\).

If \(bc\) is absent, all edges contain \(a\), so there are at most \(n-1\)

edges.

If \(bc\) is present, no edge can use a vertex outside

\(\{a,b,c\}\): an edge from \(a\), \(b\), or \(c\) to an outside vertex is disjoint from, respectively, \(bc\), \(ac\), or \(ab\). Hence the whole graph has at most the three edges of the triangle \(abc\).

It follows that

e(H)\leq\max\{n-1,3\}.

The star \(K_{1,n-1}\) gives \(n-1\) edges, while for \(n=3\) the triangle gives three edges. Direct inspection handles \(n=1,2\), proving (3). Notice that the triangle is used only as an extremal host; the forbidden graph \(2K_2\) itself remains bipartite.

2.5 Uniform failure, not just a finite example

(a) If a constant \(C_{\mathcal F}\) satisfied the requested estimate for \(G=K_{1,2}\), then (1)–(2) would give \(\lfloor n/2\rfloor\leq C_{\mathcal F}\) for all sufficiently large \(n\), which is impossible. For \(G=2K_2\), (1) and (3) would similarly give \(n-1\leq C_{\mathcal F}\). This is the required uniformity step.

3. Independent computation

The standalone verifier is erdos575_wave9r_verify.py. It uses only the Python standard library. It does not call an extremal-graph package or put the claimed values into the search routine.

The verifier:

two-colours \(K_{1,2}\) and \(2K_2\) by breadth-first search;
generates every labeled simple graph on \(n=1,\ldots,7\);
detects \(K_{1,2}\) from degrees and \(2K_2\) by testing every edge pair;
maximizes the number of edges separately under the three avoidance

conditions;

only after enumeration compares the answers with (1)–(3);
directly checks the matching, star/triangle, and one-edge witnesses for

every \(1\leq n\leq100\).

Run:

python3 runs/erdos575_wave9r_verify.py

Successful output:

n  labelled_graphs  ex(K1,2)  ex(2K2)  ex(family)
1               1         0        0           0
2               2         1        1           1
3               8         1        3           1
4              64         2        3           1
5            1024         2        4           1
6           32768         3        5           1
7         2097152         3        6           1
n=10: ratios = 5, 9
n=100: ratios = 50, 99
n=1000: ratios = 500, 999
PASS: exhaustively checked 2,131,019 labelled graphs (n=1..7)

(d) This table is an exhaustive result only for \(n\leq7\). The all-\(n\) conclusion is supplied by the elementary proof above, not by extrapolation from the table.

The successful timed run used 20.60 seconds of wall time, 99% of one CPU, and 16,000 KiB maximum resident memory. python3 -m py_compile also passed. The script's SHA-256 is

817c1cc82e5cf5e43ee4659ff68bbda0afbad02cffcb6d8db1b57753b51d3018

(d) The first run found all table entries but deliberately failed its final total-count assertion: my hand-entered total was wrong. Summing the enumerated graph counts gives \(2{,}131{,}019\); I corrected only that bookkeeping constant and reran the entire enumeration to the successful output above.

4. Primary-source and current-state audit

4.1 Erdős–Simonovits (1982)

(a; source check) P. Erdős and M. Simonovits, “Compactness results in extremal graph theory,” Combinatorica 2 (1982), 275–288, DOI 10.1007/BF02579234, exists with the stated authors, venue, year, and pages. I inspected the author-hosted scan at CompactnessCCA.pdf; its downloaded SHA-256 was 8e27f4d921641836dee1b44f4abf685bcaa875593dc1a83dfe41c5b5e9137ccc.

There is a documentary wrinkle. On printed page 276, equation (5) literally has

\operatorname{ex}(n,L)=O(\operatorname{ex}(n,L^*)),

the already-trivial direction. The surrounding compactness discussion, the live #575 page, and the later sources below use the intended nontrivial reverse comparison \(\operatorname{ex}(n,L^*)=O(\operatorname{ex}(n,L))\). The live page was specified as authoritative for this task, so the counterexample above is tested against its displayed nontrivial direction.

The older UCSD “problem #51” page also renders a \(t(n,\mathcal F)\) version in the trivial orientation. This reinforces the need to use the live #575 wording rather than silently repairing or replacing it.

4.2 Wigderson's note

(a; source check and independently reproved) Yuval Wigderson's two-page note, The Erdős–Simonovits compactness conjecture needs more assumptions, exists and states the same family \(\{K_{1,2},2K_2\}\). It credits Jordan Lefkowitz for pointing out the example, proves that the family extremal number is one while both individual numbers are linear, and reports that Simonovits suggested restricting the conjecture to families containing no forest. The downloaded PDF had SHA-256 81b84deb2d44c97bc2bf77dafcce11255b0cdeb11cdea1d517e4f74302eaec46. I found no arXiv identifier for this standalone note; I do not infer from that search miss that none exists.

4.3 A 2026 primary source

(a; source check) David Conlon, Eion Mulrenin, and Cosmin Pohoata, Two counterexamples to a conjecture about even cycles, arXiv:2603.24515 (submitted 25 March 2026), exists and is a seven-page math.CO preprint. Its introduction formulates the compactness conjecture with the no-forest hypothesis; its first footnote gives \(\{K_{1,2},2K_2\}\) as a simple counterexample without that hypothesis and cites Wigderson for details. The downloaded arXiv PDF had SHA-256 273ba6e7b2f448ca0563ca6475094dad788eb4b3cfce9a175afab6d579002cb4.

(c; literature-status qualification) This March 2026 paper still calls the no-forest version a conjecture. My searches found no primary source settling that repaired version, but this is a bounded literature search, not a proof of global nonexistence. The repaired version is a different problem from the exact live statement and is not needed for the counterexample.

5. Verified state

(a) Nothing remains to be proved for the yes/no question exactly as displayed on the live #575 page: the two-member family above is a uniform counterexample, with exact extremal numbers for every \(n\). The website's OPEN label appears not to have incorporated the counterexample already mentioned in its own comment and on its linked #180 page. This report does not claim to settle the distinct, forest-free modification.

FOUND: The live #575 statement is uniformly false for \(\mathcal F=\{K_{1,2},2K_2\}\): \(\operatorname{ex}(n;\mathcal F)=1\) for \(n\ge2\), while both member extremal numbers grow linearly.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger