Polynomial upper bound for genus-increment growth ratios

Let Ah\mathcal A^h be one of the graph classes considered in the paper, indexed by graphs on [n][n] embeddable in surfaces of Euler genus at most hh. Genus-increment growth-ratio conjecture. There are constants α\alpha and β\beta such that, for every 0hn0\leq h\leq n,

Anh+2Anhαnβ.\frac{|\mathcal A^{h+2}_n|}{|\mathcal A^h_n|}\leq \alpha n^\beta.

The conjecture is proposed as an upper bound when the allowed Euler genus is increased by two; the surrounding discussion suggests that one might take β=2\beta=2, and notes that this would imply a conjecture about the planar growth constant.

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.