Ghosh et al.'s conjecture on even-length paths in planar graphs

Less than 1 year old · traced to

For a finite simple graph GG, let N(G,H)N(G,H) be the number of unlabeled, not necessarily induced copies of HH in GG. Define

f(n,H)=max⁡{N(G,H):∣V(G)∣=n and G is planar}.f(n,H)=\max\{N(G,H): |V(G)|=n \text{ and } G \text{ is planar}\}.

Let PkP_k denote the path on kk vertices, so P2ℓ+1P_{2\ell+1} has even length 2ℓ2\ell. Ghosh et al.'s conjecture. For every fixed integer ℓ≥2\ell\ge 2,

f(n,P2ℓ+1)=4ℓ(nℓ)ℓ+1+O(nℓ).f(n,P_{2\ell+1})=4\ell\left(\frac{n}{\ell}\right)^{\ell+1}+O(n^\ell).

The lower bound is supplied by blowing up one bipartition class of a cycle C2ℓC_{2\ell}, while the conjectured matching upper bound remained to be proved in the source. The corresponding conjecture has since been resolved by Lv, Győri, He, Salia, Tompkins and Zhu.

References

Primary source

Zhen Liu and Chuanshu Wu, “The maximum number of paths of even length in a planar graph”, arXiv:2607.27284 (2026).

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.