Disproof of the tree product conjecture via the Heisenberg group

Abstract

Product structure theory aims to understand complex graphs by embedding them into products of simpler graphs. In this direction, Campbell, Distel, Gollin, Harvey, Hendrey, Hickingbotham, Mohar and Wood (2022) put forth the conjecture that all graphs of degree-$d$ polynomial growth (i.e., where balls of radius $r$ have $\mathcal{O}(r^d)$ vertices) can be embedded into the strong product of $d$ trees, each with linear growth, and a constant-size clique. In this paper, we disprove this conjecture for $d = 4$. The counterexamples are finite subgraphs of a Cayley graph of the discrete $3$-dimensional Heisenberg group $\mathbb{H}(\mathbb{Z})$. These graphs were first proposed by Huang and McCarty as potential counterexamples to the conjecture. A key technical tool of our proof is the ''quantitative central collapse'' theorem due to Cheeger, Kleiner and Naor (2011), guaranteeing that every Lipschitz map from the continuous Heisenberg group $\mathbb{H}$ to the function space $L_1$ collapses along a central line.

Disclosure

“en Huang was studying geometric group theory. The examples were also explicitly proposed for investigation by McCarty at the 2024 Barbados Graph Theory workshop. Our main contribution here is to settle this problem. AI Disclosure. We used ChatGPT 5.5 Pro to assist us with working out the details of the compactness argument presented in Section 7. Its output was carefully checked and rewritten by the authors. The content of all other sections is due entirely to the authors. 2 T”

PDF page 4

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-24T00:28:51.963Z

Structural counts