The intrinsic dimensionality of graphs

ABSTRACT

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 Z^d 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 Linial[15].

REFERENCES

• 1: N. Alon and J. H. Spencer. The probabilistic method. Wiley-Interscience {John Wiley & Sons}, New York, second edition, 2000.
• 2: P. Assouad. Plongements lipschitziens dans Rspn. Bull. Soc. Math. France, 111(4):429--448, 1983.
• 3: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 4: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 5: Andreas Brandstädt , Victor Chepoi , Feodor Dragan, Distance approximating trees for chordal and dually chordal graphs, Journal of Algorithms, v.30 n.1, p.166-184, Jan. 1999 [doi>10.1006/jagm.1998.0962]
• 6: Victor Chepoi , Feodor Dragan, A note on distance approximating trees in graphs, European Journal of Combinatorics, v.21 n.6, p.761-766, Aug. 2000 [doi>10.1006/eujc.1999.0381]
• 7: F. R. K. Chung. Labelings of graphs. In Selected topics in graph theory, 3, pages 151--168. Academic Press, San Diego, CA, 1988.
• 8: P. Erdos, F. Harary, and W. T. Tutte. On the dimension of a graph. Mathematika, 12:118--122, 1965.
• 9: Uriel Feige, Approximating the bandwidth via volume respecting embeddings, Journal of Computer and System Sciences, v.60 n.3, p.510-539, June 2000 [doi>10.1006/jcss.1999.1682]
• 10: J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.
• 11: Kirsten Hildrum , John D. Kubiatowicz , Satish Rao , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564877]
• 12: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 13: David R. Karger , Matthias Ruhl, Finding nearest neighbors in growth-restricted metrics, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510013]
• 14: Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
• 15: N. Linial. Variation on a theme of Levin. In J. Matouvsek, Ed., Open Problems, Workshop on Discrete Metric Spaces and their Algorithmic Applications. Haifa, March 2002.
• 16: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 17: N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441--454, 1993.
• 18: L. Lovasz and K. Vesztergombi. Geometric representations of graphs. In Paul Erdos, Proc. Conf., Budapest, 1999.
• 19: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 20: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 21: Satish Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, Proceedings of the fifteenth annual symposium on Computational geometry, p.300-306, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304983]
• 22: S. Semmes. Bilipschitz embeddings of metric spaces into Euclidean spaces. Publ. Mat., 43(2):571--653, 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
embeddings, finite metric spaces, graph decomposition, growth restricted graphs, lovasz local lemma, low--dimensional