The intrinsic dimensionality of graphs

We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich 16. Let Z∞d be the infinite graph whose vertex set is Zd and which has an edge (u,v) whenever ||u-v||∞ = 1. Let dim(G) be the smallest d such that G occurs as a (not necessarily induced) subgraph of Z∞d. The growth rate of G, denoted ρG, is the minimum ρ such that every ball of radius r > 1 in G contains at most rρ vertices. By simple volume arguments, dim(G) = Ω(ρG). Levin conjectured that this lower bound is tight, i.e., that dim(G) = O(ρG) for every graph G.Previously, it was not known whether dim(G) could be upper bounded by any function of ρG, even in the special case of trees. We show that a weaker form of Levin's conjecture holds by proving that, for every graph G, dim(G) = O(ρG log ρG). We disprove, however, the specific bound of the conjecture and show that our upper bound is tight by exhibiting graphs for which dim(G) =Ω(ρG log ρG). For families of graphs which exclude a fixed minor, we salvage the strong form, showing that dim(G) = O(ρG). This holds also for graphs without long induced simple cycles. Our results extend to a variant of the conjecture for finite-dimensional Euclidean spaces due to Linial15.