Subdivided expanders and counterexamples to the Tree Product Conjecture

2026/08/05 by Andrea Munaro
Mathematics · #math.CO #msc:05C48 #msc:05C76 #msc:05C40

paper · pdf

11 pages

arxiv created 2026/08/05 · arxiv updated 2026/08/06

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 ≥ 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 Ω(n^1-1/dlog n), where n denotes the number of vertices.

Citations

• Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
• Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
• Large-scale geometry of Borel graphs of polynomial growth
• Graphs of Linear Growth have Bounded Treewidth
• Product structure of graph classes with strongly sublinear separators
• Polynomial growth and asymptotic dimension
• Separation profiles, isoperimetry, growth and compression
• A continuum of expanders
• Sublinear separators, fragility and subexponential expansion
• Layered Separators in Minor-Closed Graph Classes with Applications
• Parameterized Algorithms