Erdős problem #810 — live-page audit, exact finite computation, and wall

Access/research date: 2026-07-27 (UTC).

Claim labels used below:

• (a) elementary-rigorous: a complete argument is given and does not

depend on the computation.

• (b) rigorous modulo named theorem: this is quoted from the identified

paper/theorem.

• (c) plausible/structural-unverified: useful interpretation, not a

theorem claimed here.

• (d) computational-only: certified by the supplied exhaustive program;

this is not promoted to a non-computational theorem.

0. Mandatory live-page check

I fetched the rendered live page and its discussion thread through the Bright Data browser path; ordinary extraction was truncated, so I separately queried the rendered document.body.innerText. This was done before doing any mathematics.

Verbatim current statement

Does there exist some 𝜖 >0 such that, for all sufficiently large 𝑛, there exists a graph 𝐺 on 𝑛 vertices with at least 𝜖𝑛² many edges such that the edges can be coloured with 𝑛 colours so that every 𝐶₄ receives 4 distinct colours?

Source: live problem #810, accessed 2026-07-27. The page says it was last edited 2026-04-01.

Stop-condition audit

The live page showed:

• status: OPEN;
• claimed proofs: 0;
• currently working on this problem: None;
• interested in collaborating: None;
• likes: None;
• “looks difficult”: None;
• “looks tractable”: None;
• “results could be formalisable”: None;
• “working on formalising”: None;
• formalised statement: No;
• comments: 9.

Thus neither mandatory stop condition was present, and I proceeded.

Results listed on the live page

The page records the following.

1. Burr, Erdős, Graham, and Sós believed the answer is no. With

\(\chi_S(n,e,H)\) denoting their maximal anti-Ramsey function, the question is whether \[ \chi_S(n,\epsilon n^2,C_4)\le n \] for some fixed \(\epsilon>0\) and every sufficiently large \(n\).

1. [BEGS89] proves that no such \(\epsilon\) exists with \(P_4\) in place of

\(C_4\).

1. Their stronger conjecture asks whether, for every connected bipartite

non-star \(H\), \[ \chi_S(n,\epsilon n^2,H)/n\longrightarrow\infty. \] Sárközy and Selkow proved this when \(H\) is not complete bipartite; the complete-bipartite case, including \(C_4=K_{2,2}\), remains open.

1. [BEGS89] gives, for an absolute \(c>0\),

\[ \chi_S(n,c\,g(n;7,4),C_4)\le n, \] where \(g(n;7,4)\) is the indicated \((7,4)\) extremal 3-uniform-hypergraph function. It remains unknown (and is believed) that \(g(n;7,4)=o(n^2)\). The page points to problem #1178 and also to #809.

These are (b) as statements attributed to the named papers.

What the nine live comments say

The discussion thread itself warns that comments are not verified. I therefore record these as comments, not as established results.

1. Terence Tao (2025-12-07) observes that a negative answer to #810 would

imply the finite-field Ajtai–Szemerédi square theorem: a dense square-free \(A\subseteq\mathbb F_2^d\times\mathbb F_2^d\) would give the bipartite graph \(a\sim b\), coloured \(a+b\), whose \(C_4\)'s are all rainbow. He also notes a resemblance to skew-corner-free sets.

1. Mehtaab Sawhney (2025-12-07) gives a counterexample to Tao's deliberately

loose three-coordinate pattern; it is not a counterexample to #810.

1. Vjekoslav Kovač (2025-12-07) states the literal rectangle reformulation:

on the four occupied cells of any genuine \(2\times2\) rectangle, all six possible equal-colour pairs must be forbidden.

1. Sawhney (2025-12-08) explains the close relation to the \((7,4)\) problem

through linear 3-graphs and a random tripartition.

1. Tao asks whether the implication to \((7,4)\) is formal.
2. Sawhney sketches that a dense \((7,4)\)-free 3-graph, after linearisation

and tripartition, yields a dense bipartite example for #810.

1. Matija Bucić (2026-04-01) notes that this implication already appears in

the original BEGS paper.

1. Thomas Bloom (2026-04-01) says this prompted the added details and

references on the problem page.

1. Tao (2025-12-11) reports AlphaEvolve examples with edge counts

\[ 5,7,11,14,17,23,30,34,\ldots,155\qquad(n=4,\ldots,25), \] explicitly warning that AlphaEvolve gives no guarantee of optimality and suggesting SAT computation. The linked examples.txt returned a WordPress authorization/403 page during this run, so I did not rely on it.

1. Primary-source literature check

I verified the following sources and the claims used here.

• S. A. Burr, P. Erdős, R. L. Graham, and V. T. Sós,

Maximal antiramsey graphs and the strong chromatic number, Journal of Graph Theory 13 (1989), 263–282, DOI 10.1002/jgt.3190130302; author/archive PDF. Page 273 contains \(\chi_S(n,cg(n;7,4),C_4)\le n\) and explicitly says that \(g(n;7,4)=o(n^2)\) was unknown.

• G. N. Sárközy and S. Selkow,

On an anti-Ramsey problem of Burr, Erdős, Graham, and T. Sós, Journal of Graph Theory 52 (2006), 147–156, DOI 10.1002/jgt.20148. Its Theorem 4 proves the dense superlinear-colour conclusion for connected bipartite graphs that are not complete bipartite, and the paper explicitly says the complete-bipartite case “for instance \(C_4\)” remains open.

• The live page also cites P. Erdős,

Problems and results in combinatorial analysis and combinatorial number theory, in Graph Theory, Combinatorics, and Applications, Vol. 1 (1991), 397–406, MR1170793, specifically p. 399.

I searched the exact title/DOI, “maximal anti-Ramsey \(C_4\),” “\(\chi_S(n,e,C_4)\),” and the rainbow/polychromatic-\(C_4\) formulations. The closest current primary-source hits were:

• Li–Ning–Xie, *Two problems of Burr, Erdős, Graham, and Sós on maximal

anti-Ramsey functions for \(P_4\)*, arXiv:2606.30505;

• Yang, *On the maximal anti-Ramsey problem of Burr, Erdős, Graham, and Sós

for \(P_4\)*, arXiv:2607.05896;

• Bucić–Chen–Ma, *On a maximal anti-Ramsey conjecture of Burr, Erdős, Graham,

and Sós*, arXiv:2603.18952, concerning odd cycles.

Their statements concern \(P_4\) or odd cycles, not the \(C_4\) question here. I found no primary source claiming a resolution or a sharper directly applicable \(C_4\) result. This is an honest search miss, not a proof that no such literature exists.

2. Exact finite reduction

Define

Then #810 asks whether

This equivalence is (a).

For an ordinary graph \(G\), define its conflict graph \(Q(G)\) by

joining two vertices of \(Q(G)\) exactly when the corresponding two edges of \(G\) occur together in at least one \(C_4\) of \(G\).

Lemma (a).

Proof. Each \(C_4\) contributes a \(K_4\) on its four edges to \(Q(G)\). Thus a proper colouring of \(Q(G)\) gives four pairwise distinct colours on every \(C_4\). Conversely, if every \(C_4\) is rainbow, any two edges made adjacent in \(Q(G)\) have different colours. \(\square\)

The property is closed under deleting edges. Therefore, to prove \(M(n)\le m\), it is enough to reject every \(n\)-vertex graph with exactly \(m+1\) edges: a larger valid graph could be trimmed to such a graph. This monotonicity is (a).

3. Exact computed table through \(n=10\)

The supplied exhaustive checker establishes:

The values for \(n\le3\) are trivial because there is no \(C_4\). The values for \(4\le n\le10\) are (d). In particular, the first seven AlphaEvolve counts on the live page, through \(n=10\), are optimal.

For \(n=4,\ldots,7\), every labelled graph is generated directly as a bit mask; the candidate counts are respectively

For \(n=8,9,10\), nauty 2.8.8 geng supplies one graph from each isomorphism class. The property and \(Q(G)\) are isomorphism-invariant. The nauty completeness dependency is why these remain labelled (d) rather than being presented as a hand proof.

The sole \(n=8\) exception to the clique obstruction

The exceptional 18-edge graph has graph6 code GUZurw. Its \(Q\) has \(\alpha(Q)=3\), and its only independent triples, written as triples of edges of the original graph, are

They are pairwise disjoint.

Any eight-colouring of the 18 vertices of \(Q\) needs at least two three-vertex colour classes: with \(t\) triples, eight classes cover at most \(3t+2(8-t)=16+t\) vertices. For every possible exact choice of \(t\) of the four triples, the maximum matching size in the nonconflict graph induced on the remaining vertices is:

Here \(|R|-\nu\) is exactly the minimum number of pair/single classes needed once no further triple class is used. Every case needs more than eight colours. The companion script enumerates the four triples and recomputes all these matching numbers from scratch; its independent DSATUR routine also returns UNSAT. This finite obstruction is (d), with the displayed counting implication itself (a) once the enumerated data are accepted.

4. Explicit lower certificates

Vertices and colours are zero-based. Each item \((u,v,c)\) means that edge \(\{u,v\}\) is present with colour \(c\). The complete machine-readable versions are embedded in the companion script.

n=4:
((0,1,0),(0,2,3),(0,3,2),(1,2,1),(1,3,0))

n=5:
((0,1,3),(0,2,3),(0,3,2),(0,4,2),(1,2,0),(1,3,1),(2,4,1))

n=6:
((0,1,5),(0,2,4),(0,3,3),(0,4,5),(0,5,4),(1,2,0),
 (1,3,1),(1,4,2),(2,3,2),(2,5,1),(4,5,3))

n=7:
((0,1,1),(0,2,3),(0,3,2),(0,4,1),(0,5,4),(0,6,6),
 (1,2,5),(1,3,4),(1,4,0),(2,3,0),(2,5,6),(3,6,5),
 (4,5,2),(4,6,3))

n=8:
((0,3,7),(0,4,6),(0,5,5),(0,7,4),(1,4,7),(1,5,3),
 (1,6,4),(1,7,1),(2,5,0),(2,6,6),(2,7,7),(3,6,5),
 (3,7,2),(4,6,3),(4,7,0),(5,7,1),(6,7,2))

n=9:
((0,3,2),(0,4,0),(0,6,8),(0,7,6),(0,8,5),(1,3,3),
 (1,5,6),(1,6,1),(1,7,4),(1,8,0),(2,4,4),(2,5,5),
 (2,6,3),(2,7,7),(2,8,2),(3,5,8),(3,6,7),(3,8,4),
 (4,5,3),(4,7,8),(4,8,1),(5,7,1),(6,8,6))

n=10:
((0,2,0),(0,4,1),(0,5,2),(0,6,7),(0,7,3),(0,8,6),
 (1,3,2),(1,4,0),(1,5,6),(1,6,5),(1,7,8),(1,9,1),
 (2,4,9),(2,6,2),(2,7,4),(2,8,5),(2,9,6),(3,5,4),
 (3,6,9),(3,7,0),(3,8,1),(3,9,3),(4,6,8),(4,8,4),
 (4,9,7),(5,7,7),(5,8,8),(5,9,9),(6,8,3),(7,9,5))

For each certificate the checker performs two separate tests:

1. enumerate the three undirected Hamilton cycles on every four-set and

directly demand four distinct colours whenever all four edges occur;

1. independently build \(Q(G)\) and demand that the displayed colouring is

proper.

Thus the lower bounds become (a) after direct inspection of these finite lists; the script supplies that inspection.

5. Reproduction and independent checks

Complete checker:

runs/erdos810_wave6m_reverify.py

It uses only the Python standard library and /bin/nauty-geng for \(n\ge8\). Run:

python runs/erdos810_wave6m_reverify.py

Observed output on this VM (nauty package 2.8.8+ds-5):

certificate n=4: 5 edges, 1 C4s, verified
certificate n=5: 7 edges, 2 C4s, verified
certificate n=6: 11 edges, 10 C4s, verified
certificate n=7: 14 edges, 16 C4s, verified
certificate n=8: 17 edges, 23 C4s, verified
certificate n=9: 23 edges, 46 C4s, verified
certificate n=10: 30 edges, 95 C4s, verified
upper n=4: all 1 labelled 6-edge graphs rejected; K_5=1, capacity=0
upper n=5: all 45 labelled 8-edge graphs rejected; K_6=45, capacity=0
upper n=6: all 455 labelled 12-edge graphs rejected; K_7=455, capacity=0
upper n=7: all 54264 labelled 15-edge graphs rejected; K_8=53844, capacity=420
n=8 exceptional GUZurw: alpha=3, four possible triples; matching obstruction verified
upper n=8: all 663 unlabelled 18-edge graphs rejected; K_9=662, exceptional=1
upper n=9: all 5995 unlabelled 24-edge graphs rejected; K_10=5995, exceptional=0
upper n=10: all 71318 unlabelled 31-edge graphs rejected; K_11=71318, exceptional=0
EXACT: {1: 0, 2: 1, 3: 3, 4: 5, 5: 7, 6: 11, 7: 14, 8: 17, 9: 23, 10: 30}

Wall time was 18.1 seconds. SHA-256 of the checker at report time:

abd7933ebbd53e8160a74a3be459e46e6f49d65cec279fed963ed85f502b1e75

Additional independent checks performed during the run:

• nauty-geng -u -v separately returned 663, 5,995, and 71,318 graphs in

the three upper-bound layers.

• The script's from-scratch graph6 parser agreed with NetworkX on all 663

\(n=8\) inputs and the first 1,000 inputs in each of the \(n=9,10\) layers.

• The \(n\le7\) lower witnesses can be regenerated rather than read from the

embedded list using --discover-small.

6. What this does and does not settle

The finite table is genuine progress, but it gives no asymptotic density. In particular,

does not imply any uniform positive lower bound as \(n\to\infty\). No claim that #810 is solved is made.

Exact structural wall

After a random bipartition of \(G\), encode a coloured edge \(ab\) as a tripartite triple \((a,b,c(ab))\). A non-rainbow rectangle consists of four such triples on two \(a\)'s and two \(b\)'s with a repeated third coordinate. Consequently:

• a positive answer needs, uniformly for every sufficiently large order, a

functional tripartite 3-graph with \(\Omega(n^2)\) triples avoiding all six repeated-colour rectangle patterns;

• a negative answer needs an \(o(n^2)\) extremal theorem for precisely this

functional family.

The latter would in particular imply the relevant \((7,4)\) conclusion highlighted by BEGS and the live comments. The missing lemma is therefore not ordinary supersaturation of \(C_4\): it must force a \(C_4\) containing two edges from the same colour class among only \(O(n)\) colour classes. Equivalently, it must find either:

• two same-coloured adjacent edges \(uv,uw\) whose other endpoints have a

common neighbour completing a \(C_4\); or

• two same-coloured disjoint edges for which one of the two cross-pairings is

present.

This exact coloured-completion statement is what current regularity machinery does not provide. In the Sárközy–Selkow proof, the non-complete-bipartite hypothesis supplies an induced \(P_4\), which is first embedded with a repeated colour and then extended. \(C_4=K_{2,2}\) has no such induced \(P_4\), so that step is unavailable. This diagnosis is (b) for what their proof uses and (c) as a roadmap for the missing \(C_4\) lemma.

Next computation and realistic cost

The live heuristic gives 34 edges for \(n=11\). An upper test would need the 15,108,047 unlabelled 11-vertex graphs with 35 edges (the count was obtained with geng -u; the graphs were not searched). Scaling the measured \(n=10\) conflict/clique audit gives roughly 1–3 single-core hours in this Python implementation, with memory small; a tuned C implementation should be substantially faster. That exceeds the requested few-CPU-minute budget and was not run. Even a longer finite table would still not supply the missing uniform asymptotic step.

7. Claim ledger

• Conflict-graph equivalence and deletion monotonicity: (a).
• Explicit lower certificates once directly checked: (a).
• BEGS89 and Sárközy–Selkow literature statements: (b).
• Exact \(M(n)\) table for \(4\le n\le10\): (d).
• Interpretation of the precise missing coloured-completion lemma: (c).
• Any asymptotic answer to #810: not obtained.

PARTIAL: Exhaustive certificates prove computationally that \(M(n)=0,1,3,5,7,11,14,17,23,30\) for \(1\le n\le10\), but the uniform dense construction/colored-completion lemma needed for Erdős #810 remains open.