ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let HH be a finite graph, and write fH(r)f_H(r) for its growth function, namely the maximum number of vertices in a ball of radius rr. For graphs G1,…,GkG_1,\dots,G_k, let G1⊠⋯⊠GkG_1 \boxtimes \dots \boxtimes G_k denote their strong product, and let KmK_m denote the complete graph on mm vertices. A graph class has degree-dd polynomial growth if its growth is bounded by O(rd)O(r^d). The tree product conjecture. There exist functions g ⁣:R×N→Ng \colon \mathbb{R} \times \mathbb{N} \to \mathbb{N} and h ⁣:R×N→Nh \colon \mathbb{R} \times \mathbb{N} \to \mathbb{N} such that for every c∈R⩾1c\in \mathbb{R}_{\geqslant 1} and d∈Nd \in \mathbb{N}, every finite graph HH with growth fH(r)⩽crdf_H(r)\leqslant cr^d is isomorphic to a subgraph of

T1⊠⋯⊠Td⊠Kg(c,d),T_1 \boxtimes \dots \boxtimes T_d \boxtimes K_{g(c,d)},

where each TiT_i is a tree with growth fTi(r)⩽h(c,d)rf_{T_i}(r)\leqslant h(c,d)r. The conjecture seeks the tight number dd of product factors for graphs of degree-dd polynomial growth, with each factor a tree of linear growth and with a bounded clique factor; its resolution would strengthen the known product-structure theorem for graph classes of linear growth.

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.