About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Abstract
We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich [Combinatorica, 1995]. For a graph G, let dim(G) be the smallest d such that G occurs as a (not necessarily induced) subgraph of ℤ ∞d , the infinite graph with vertex set ℤ d and an edge (u, v) whenever ∥u - v∥∞ = 1. 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 unknown whether dim(G) could be bounded above by any function of ρ G . We show that a weaker form of Levin's conjecture holds by proving that dim(G) = O(ρ G log ρ G ) for any graph 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 several special families of graphs (e.g., planar graphs), we salvage the strong form, showing that dim(G) = O(ρ G ). Our results extend to a variant of the conjecture for finite-dimensional Euclidean spaces posed by Linial and independently by Benjamini and Schramm. © 2007 Springer-Verlag.