Eppstein's integer-power conjecture for planar subgraph counts

About 6 years old · traced to

Let HH be a graph, and let ex⁡P(n,H,∅)\operatorname{ex}_{\mathcal{P}}(n,H,\emptyset) denote the maximum number of copies of HH in an nn-vertex planar graph.

Eppstein's conjecture. For every graph HH, there exists a non-negative integer kk such that

ex⁡P(n,H,∅)=Θ(nk).\operatorname{ex}_{\mathcal{P}}(n,H,\emptyset)=\Theta(n^k).

This is a restricted planar version of a question posed by Eppstein about subgraph counts in minor-closed graph families. The paper presents it as an open conjecture, while verifying it for trees and establishing general upper bounds.

References

Primary source

Ervin Győri, Addisu Paulos, Nika Salia, Casey Tompkins and Oscar Zamora, “Generalized Planar Turán Numbers”, arXiv:2002.04579 (2020).

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.