Győri–Paulos–Salia–Tompkins–Zamora planar forbidden-subgraph counting conjecture

Let F\mathcal F be a finite set of graphs, let HH be a graph, and let G\mathcal G be the class of all planar graphs with no subgraph isomorphic to any member of F\mathcal F. Assume that HGH\in\mathcal G. Győri–Paulos–Salia–Tompkins–Zamora's conjecture. There is an integer kk such that

ex(H,G,n)=Θ(nk).\operatorname{ex}(H,\mathcal G,n)=\Theta(n^k).

This conjecture concerns the polynomial order of homomorphism and subgraph counts in planar graph classes with finitely many forbidden subgraphs. The paper notes that its bounded-expansion theorem gives a negative answer to a related question, but does not state a resolution of this conjecture.

Sources & referencesView supporting material

Primary source

Chun-Hung Liu, “Homomorphism counts in robustly sparse graphs”, arXiv:2107.00874 (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.