Subdivided expanders and counterexamples to the Tree Product Conjecture
Distel, Gollin, Harvey, Hendrey, Hickingbotham, Mohar and Wood (2023) conjectured that graphs of degree-$d$ polynomial growth can be embedded into the strong product of $d$ trees, each with linear growth, and a constant-size complete graph. Very recently, the case $d = 4$ of the conjecture was disproved by Illingworth, Norin and Steiner (2026). In this paper, we provide counterexamples to the conjecture for every integer $d \geq 2$, thus leaving $d=1$ as the only open case. Our counterexamples are appropriately subdivided cubic expanders. Our main contribution is to construct, for every real…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.04659
curl -X POST /api/v1/records/arxiv/2608.04659/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.04659/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'