Growth-constant threshold for order-dependent surface classes

Let gg be a genus function, and let Ag\mathcal A^g denote one of the graph classes considered in the paper, such as Eg\mathcal E^g, OEg\mathcal O\mathcal E^g, NEg\mathcal N\mathcal E^g, or OEgNEg\mathcal O\mathcal E^g\cap\mathcal N\mathcal E^g. Let γP\gamma_{\mathcal P} be the growth constant of the planar graphs. Growth-constant threshold conjecture. The class Ag\mathcal A^g has growth constant γP\gamma_{\mathcal P} if and only if

g(n)=o ⁣(nlogn).g(n)=o\!\left(\frac{n}{\log n}\right).

The paper proves the forward necessary condition and the matching conclusion under the stronger hypothesis g(n)=o(n/log3n)g(n)=o(n/\log^3 n); the conjecture asks whether the threshold can be improved to o(n/logn)o(n/\log n).

Sources & referencesView supporting material

Primary source

Colin McDiarmid and Sophia Saller, “Classes of graphs embeddable in order-dependent surfaces”, arXiv:2106.06775 (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.