The tree product conjecture for graphs of polynomial growth
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.