The rainbow Turán path conjecture

From papers

Let PP_{\ell} be the path with \ell edges, and let ex(n,P)\operatorname{ex}^*(n,P_{\ell}) denote the maximum number of edges in a properly edge-colored nn-vertex graph containing no rainbow copy of PP_{\ell}. Here O(1)O(1) denotes a quantity bounded independently of nn.

Rainbow Turán path conjecture. For all 3\ell \geq 3,

ex(n,P)=2n+O(1).\operatorname{ex}^*(n,P_{\ell}) = \frac{\ell}{2}n + O(1).

The lower bound is supplied by Johnston and Rombach's construction, while the cases =3,4\ell=3,4 were known and the paper proves the matching asymptotic upper bound for P5P_5. The assertion remains open in general for longer paths.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Anastasia Halfpap, “The rainbow Turán number of P_5”, arXiv:2210.03376 (2022).

Solutions 0

No solutions have been posted yet.