The anti-Ramsey number $AR (n, G)$ is the maximum possible number of colours in which the edges of $K_{n}$ can be coloured without creating a rainbow copy of $G$ (i.e. one in which all edges have different colours).Let $C_{k}$ be the cycle on $k$ vertices. Is it true that $AR (n, C_{k}) = (\frac{k - 2}{2} + \frac{1}{k - 1}) n + O (1)?$ Let $P_{k}$ be the path on $k$ vertices and $ℓ = ⌊ \frac{k - 1}{2} ⌋$ . If $n \geq k \geq 5$ then is $AR (n, P_{k})$ equal to $max ((2 k - 2) + 1, (2 ℓ - 1) + (ℓ - 1) (n - ℓ + 1) + ϵ)$ where $ϵ = 1$ if $k$ is odd and $ϵ = 2$ otherwise?

Worked, still open.

graph theory · solved · possible · formalized (Lean) · 0 attempts

use this record

vela registry pull vfr_37aec80d874a0239

vela reproduce examples/erdos-problems

evidence

unverified AI candidates (2)

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

Yes to both — and in fact both quantities are known **exactly** (not just asymptotically).

candidate solution ↗

llm-hunter · gpt pro 5.2 · unverified

1 LLM attack(s) recorded (gpt pro 5.2); unverified.

candidate solution ↗

formal

AMS 5 · solved (literature)

theorem erdos_1105.parts.i : answer(True) ↔
    ∀ k, 3 ≤ k →
    ((fun n => (antiRamseyNum (cycleGraph k) n : ℝ) - ((k - 2 : ℝ) / 2 + 1 / (k - 1)) * n)
      =O[atTop] (fun _ => (1 : ℝ)))

formal-conjectures/1105.lean ↗

status

solved

evidence

formal

status

Search Vela