Disproof of the tree product conjecture via the Heisenberg group
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.03041
curl -X POST /api/v1/records/arxiv/2607.03041/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.03041/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'