The tree product conjecture for graphs of polynomial growth

From papers

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 G1GkG_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×NNg \colon \mathbb{R} \times \mathbb{N} \to \mathbb{N} and h ⁣:R×NNh \colon \mathbb{R} \times \mathbb{N} \to \mathbb{N} such that for every cR1c\in \mathbb{R}_{\geqslant 1} and dNd \in \mathbb{N}, every finite graph HH with growth fH(r)crdf_H(r)\leqslant cr^d is isomorphic to a subgraph of

T1TdKg(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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.