Skip to content

Erdős problem 1105

The anti-Ramsey number AR(n,G)\mathrm{AR}(n,G) is the maximum possible number of colours in which the edges of KnK_n can be coloured without creating a rainbow copy of GG (i.e. one in which all edges have different colours).

Sources

The source's own material, retained exactly.

2 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

1105.lean

Retained formal statement2 of 2

Let PkP_k be the path on kk vertices and ℓ=⌊k−12⌋\ell=\lfloor\frac{k-1}{2}\rfloor. If n≥k≥5n\geq k\geq 5 then is AR(n,Pk)\mathrm{AR}(n,P_k) equal to max⁡((k−22)+1,(ℓ−12)+(ℓ−1)(n−ℓ+1)+ϵ)\max\left(\binom{k-2}{2}+1, \binom{\ell-1}{2}+(\ell-1)(n-\ell+1)+\epsilon\right)where ϵ=1\epsilon=1 if kk is odd and ϵ=2\epsilon=2 otherwise?

A proof of the formula for AR(n,Pk)\mathrm{AR}(n,P_k) for all n≥k≥5n\geq k\geq 5 has been announced by Yuan [Yu21].

FormalConjectures/ErdosProblems/1105.leanErdos1105.erdos_1105.parts.ii8 linesExact file
True ↔  ∀ (k n : ℕ),    5 ≤ k →      k ≤ n →        have ℓ := (k - 1) / 2;        have ε := if Odd k then 1 else 2;        (SimpleGraph.pathGraph k).antiRamseyNum n =          max ((k - 2).choose 2 + 1) ((ℓ - 1).choose 2 + (ℓ - 1) * (n - ℓ + 1) + ε)
SolvedStatement only, no proof