Subdivided expanders and counterexamples to the Tree Product Conjecture

Abstract

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\ge 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 number $d>1$, subdivisions of cubic expanders with degree-$d$ polynomial growth and whose balanced separators have size $\Omega (n^{1-1/d}\log n)$, where $n$ denotes the number of vertices.

11 pages