The tree product conjecture for graphs of polynomial growth
The tree product conjecture for graphs of polynomial growth
Let be a finite graph, and write for its growth function, namely the maximum number of vertices in a ball of radius . For graphs , let denote their strong product, and let denote the complete graph on vertices. A graph class has degree- polynomial growth if its growth is bounded by . The tree product conjecture. There exist functions and such that for every and , every finite graph with growth is isomorphic to a subgraph of
where each is a tree with growth . The conjecture seeks the tight number of product factors for graphs of degree- polynomial growth, with each factor a tree of linear growth and with a bounded clique factor; its resolution would strengthen the known product-structure theorem for graph classes of linear growth.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Freddie Illingworth, Sergey Norin and Raphael Steiner, “Disproof of the tree product conjecture via the Heisenberg group”, arXiv:2607.03041 (2026).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.