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\).
2. [BEGS89] proves that no such \(\epsilon\) exists with \(P_4\) in place of
\(C_4\).
3. 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.
4. [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.
2. Mehtaab Sawhney (2025-12-07) gives a counterexample to Tao's deliberately
loose three-coordinate pattern; it is not a counterexample to #810.
3. 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.
4. Sawhney (2025-12-08) explains the close relation to the \((7,4)\) problem
through linear 3-graphs and a random tripartition.
5. Tao asks whether the implication to \((7,4)\) is formal.
6. Sawhney sketches that a dense \((7,4)\)-free 3-graph, after linearisation
and tripartition, yields a dense bipartite example for #810.
7. Matija Bucić (2026-04-01) notes that this implication already appears in
the original BEGS paper.
8. Thomas Bloom (2026-04-01) says this prompted the added details and
references on the problem page.
9. 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,
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,
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\)*,
- 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
\[ M(n)=\max\{|E(G)|:\ |V(G)|=n,\ \exists c:E(G)\to[n]\text{ such that every }C_4\text{ is rainbow}\}. \]Then #810 asks whether
\[ \liminf_{n\to\infty}\frac{M(n)}{n^2}>0. \]This equivalence is (a).
For an ordinary graph \(G\), define its conflict graph \(Q(G)\) by
\[ V(Q(G))=E(G), \]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).
\[ G\text{ has the required }n\text{-edge-colouring} \quad\Longleftrightarrow\quad \chi(Q(G))\le n. \]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:
\[ \boxed{(M(1),\ldots,M(10))=(0,1,3,5,7,11,14,17,23,30).} \]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.
| \(n\) | exact \(M(n)\) | \(C_4\)'s in lower certificate | graphs checked at \(M(n)+1\) | upper obstruction |
|---:|---:|---:|---:|:---|
| 4 | 5 | 1 | 1 labelled | 1 has \(K_5\subseteq Q\) |
| 5 | 7 | 2 | 45 labelled | all 45 have \(K_6\subseteq Q\) |
| 6 | 11 | 10 | 455 labelled | all 455 have \(K_7\subseteq Q\) |
| 7 | 14 | 16 | 54,264 labelled | 53,844 have \(K_8\subseteq Q\); the other 420 have \(\alpha(Q)\le2\) |
| 8 | 17 | 23 | 663 unlabelled | 662 have \(K_9\subseteq Q\); one explicit exceptional obstruction |
| 9 | 23 | 46 | 5,995 unlabelled | all have \(K_{10}\subseteq Q\) |
| 10 | 30 | 95 | 71,318 unlabelled | all have \(K_{11}\subseteq Q\) |
For \(n=4,\ldots,7\), every labelled graph is generated directly as a bit
mask; the candidate counts are respectively
\[ \binom66,\quad\binom{10}8,\quad\binom{15}{12},\quad\binom{21}{15}. \]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
\[ \begin{aligned} T_1&=\{02,14,16\},& T_2&=\{03,24,36\},\\ T_3&=\{05,25,46\},& T_4&=\{06,27,47\}. \end{aligned} \]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:
\[ \begin{array}{c|ccc} t&2&3&4\\ \hline |R|&12&9&6\\ \nu(\overline Q[R])&5&3&0\\ t+|R|-\nu(\overline Q[R])&9&9&10. \end{array} \]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;
2. 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 -vseparately 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,
\[ \frac{M(10)}{10^2}=0.30 \]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.