Even-path inverse Turán conjecture

Let tt be a positive integer, let P2tP_{2t} denote the path of length 2t2t, and let ex1(k,H)\operatorname{ex}^{-1}(k,H) denote the inverse Turán number of HH, namely the maximum number of edges in a graph whose every HH-free subgraph has fewer than kk edges. A complete tt-partite graph is balanced when its tt vertex classes have equal sizes. Even-path inverse Turán conjecture. The inverse Turán number of a path of length 2t2t is attained asymptotically by a balanced, complete tt-partite graph. Therefore, for every tt,

ex1(k,P2t)=k22(t1)2(11t)+o(k2).\operatorname{ex}^{-1}(k,P_{2t})=\frac{k^2}{2(t-1)^2}\left(1-\frac{1}{t}\right)+o(k^2).

This conjecture identifies balanced complete multipartite graphs as asymptotically extremal for even paths; the source presents it as an open question.

Sources & referencesView supporting material

Primary source

Ervin Győri, Nika Salia, Casey Tompkins and Oscar Zamora, “Inverse Turán numbers”, arXiv:2007.07042 (2021).

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.