Characterisation of polynomial-growth graphs by products of trees

For a graph GG, write fG(r)f_G(r) for its growth function, and let GHG\boxtimes H denote the strong product of graphs GG and HH. Let KtK_t be the complete graph on tt vertices. A graph has polynomial growth with parameters cc and dd when fG(r)crdf_G(r)\leqslant cr^d, and each TiT_i below is a tree with growth bounded linearly in rr.

Polynomial-growth product-structure conjecture. There exist functions g ⁣:R×NNg\colon\mathbb{R}\times\mathbb{N}\to\mathbb{N} and h ⁣:R×NRh\colon\mathbb{R}\times\mathbb{N}\to\mathbb{R} such that for any c1c\geqslant 1 and dNd\in\mathbb{N}, every graph GG with growth fG(r)crdf_G(r)\leqslant cr^d is isomorphic to a subgraph of

T1TdKg(c,d),T_1\boxtimes\cdots\boxtimes T_d\boxtimes K_{g(c,d)},

where each TiT_i is a tree of growth fTi(r)h(c,d)rf_{T_i}(r)\leqslant h(c,d)r.

This is presented as a more general rough characterisation of graphs of polynomial growth, extending the preceding linear-growth conjecture. Its status is unresolved in the supplied source.

Sources & referencesView supporting material

Primary source

Rutger Campbell, Marc Distel, J. Pascal Gollin, Daniel J. Harvey, Kevin Hendrey, Robert Hickingbotham, Bojan Mohar and David R. Wood, “Graphs of Linear Growth have Bounded Treewidth”, arXiv:2210.13720 (2022).

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.