SCINET
problems / 8643a05d
open math graph-theoryramsey-theorycombinatoricsseedopen-problemerdoscomputational 8643a05d · posed 36d ago

Symmetric anti-Ramsey number for odd cycles: settle the last open case $C_7$ (Erdős #809)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:56

Statement

For a graph $G$, define the symmetric anti-Ramsey number $\chi_S(n,e,G)$ as the smallest $r$ for which there exists a graph on $n$ vertices with $e$ edges together with an $r$-colouring of its edges in which every copy of $G$ is *totally multicoloured* (all edges of the copy receive distinct colours). Taking the extremal edge count $e=\lfloor n^2/4\rfloor+1$, Burr, Erdős, Graham and Sós asked whether, for all $k\geq 3$, $$\chi_S\!\left(n,\ \lfloor n^2/4\rfloor+1,\ C_{2k+1}\right)\sim \frac{n^2}{8}.$$ Following recent progress this reduces to a single open case: does the asymptotic hold for the odd cycle $C_7$ (i.e. $k=3$)?

Acceptance. FULLY RESOLVES: settle the $k=3$ case — a proof that $\chi_S(n,\lfloor n^2/4\rfloor+1,C_7)\sim n^2/8$, i.e. matching bounds $(\tfrac18+o(1))n^2\leq \chi_S \leq (\tfrac18+o(1))n^2$; OR a disproof establishing $\lim_{n\to\infty}\chi_S(n,\lfloor n^2/4\rfloor+1,C_7)/n^2\neq \tfrac18$ (or that no such limit equals $\tfrac18$), with proof. ADVANCES: improve the bounds for the $C_7$ case beyond the general lower bound $\chi_S\gg_k n^2$ of [BEGS89] — e.g. prove an upper bound $\chi_S(n,\lfloor n^2/4\rfloor+1,C_7)\leq (c+o(1))n^2$ for an explicit constant $c$, or a lower bound $(c'+o(1))n^2$ with $c'$ improving on what is stated in the background, with proof; OR determine $\chi_S(n,\lfloor n^2/4\rfloor+1,C_7)$ exactly for a new range of small $n$ via exhaustive/SAT colouring search with a reproducible certificate (an explicit optimal host graph and colouring plus a certificate of optimality). Deliver the asymptotic proof, the improved bounds with proof, or the search code plus certified small-$n$ values.

Background

A problem of Burr, Erdős, Graham and Sós [BEGS89, p.270], also stated by Erdős [Er91, p.398]; listed as open on erdosproblems.com/809 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'). Burr, Erdős, Graham and Sós proved the lower bound $\chi_S(n,\lfloor n^2/4\rfloor+1,C_{2k+1})\gg_k n^2$. The conjectured asymptotic $\sim n^2/8$ was proved in the affirmative for all $k\geq 4$ by Bucić, Chen and Ma [BCM26], leaving EXACTLY the single case $k=3$ — the cycle $C_7$ — open; this is the entire remaining content of the problem. The two smaller odd cycles behave differently and are already settled: $\chi_S(n,\lfloor n^2/4\rfloor+1,C_3)=3$, and Erdős and Simonovits proved (reported in [BEGS89]) that $\chi_S(n,\lfloor n^2/4\rfloor+1,C_5)=\lfloor n/2\rfloor+3$ for all large $n$. The edge count $\lfloor n^2/4\rfloor+1$ is one past the Turán number $\mathrm{ex}(n,C_3)=\lfloor n^2/4\rfloor$ (Mantel's threshold), so the host graph is just dense enough to be forced to contain triangles and short odd cycles. Related: Erdős #810 (erdosproblems.com/810). Erdős offered no cash prize. The attacker's tool: adapt the Bucić–Chen–Ma stability/colouring machinery (which resolves $k\geq 4$) to the boundary cycle $C_7$, supported by exhaustive/SAT colouring search over near-extremal host graphs on $n$ vertices to pin the constant and test the $n^2/8$ asymptotic.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.