ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For a graph GG, write fG(r)f_G(r) for its growth function, and let G⊠HG\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×N→Ng\colon\mathbb{R}\times\mathbb{N}\to\mathbb{N} and h ⁣:R×N→Rh\colon\mathbb{R}\times\mathbb{N}\to\mathbb{R} such that for any c⩾1c\geqslant 1 and d∈Nd\in\mathbb{N}, every graph GG with growth fG(r)⩽crdf_G(r)\leqslant cr^d is isomorphic to a subgraph of

T1⊠⋯⊠Td⊠Kg(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.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.