The tree product conjecture for graphs of polynomial growth

Less than 1 year old · traced to

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.

References

Primary source

Freddie Illingworth, Sergey Norin and Raphael Steiner, “Disproof of the tree product conjecture via the Heisenberg group”, arXiv:2607.03041 (2026).

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.