The rainbow Turán path conjecture

About 4 years old · traced to

Let PℓP_{\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 PℓP_{\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.