Characterisation of polynomial-growth graphs by products of trees
Statement
For a graph , write for its growth function, and let denote the strong product of graphs and . Let be the complete graph on vertices. A graph has polynomial growth with parameters and when , and each below is a tree with growth bounded linearly in .
Polynomial-growth product-structure conjecture. There exist functions and such that for any and , every graph with growth is isomorphic to a subgraph of
where each is a tree of growth .
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.