Erdős problem 1105 · problems.science

The anti-Ramsey number $\mathrm{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).

Sources

Browse retained paths and inspect the exact material available for this Problem.

2 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

1105.lean

Retained formal statement2 of 2

Let $P_k$ be the path on $k$ vertices and $\ell=\lfloor\frac{k-1}{2}\rfloor$ . If $n\geq k\geq 5$ then is $\mathrm{AR}(n,P_k)$ equal to $\max\left(\binom{k-2}{2}+1, \binom{\ell-1}{2}+(\ell-1)(n-\ell+1)+\epsilon\right)$ where $\epsilon=1$ if $k$ is odd and $\epsilon=2$ otherwise?

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

FormalConjectures/ErdosProblems/1105.leanErdos1105.erdos_1105.parts.ii8 linesExact file

1True ↔2  ∀ (k n : ℕ),3    5 ≤ k →4      k ≤ n →5        have ℓ := (k - 1) / 2;6        have ε := if Odd k then 1 else 2;7        (SimpleGraph.pathGraph k).antiRamseyNum n =8          max ((k - 2).choose 2 + 1) ((ℓ - 1).choose 2 + (ℓ - 1) * (n - ℓ + 1) + ε)

SolvedStatement only, no proof

Sources

Search problems.science