Abstract
Deterministic constructions of expander graphs have been an important topic of research in computer science and mathematics, with many well-studied constructions of infinite families of expanders. In some applications, though, an infinite family is not enough: we need expanders which are “close” to each other. We study the following question: Construct an an infinite sequence of expanders G 0,G 1,…, such that for every two consecutive graphs G i and G i + 1, G i + 1 can be obtained from G i by adding a single vertex and inserting/removing a small number of edges, which we call the expansion cost of transitioning from G i to G i + 1. This question is very natural, e.g., in the context of datacenter networks, where the vertices represent racks of servers, and the expansion cost captures the amount of rewiring needed when adding another rack to the network. We present an explicit construction of d-regular expanders with expansion cost at most \(\frac{5d}{2}\), for any d ≥ 6. Our construction leverages the notion of a “2-lift” of a graph. This operation was first analyzed by Bilu and Linial [1], who repeatedly applied 2-lifts to construct an infinite family of expanders which double in size from one expander to the next. Our construction can be viewed as a way to “interpolate” between Bilu-Linial expanders with low expansion cost while preserving good edge expansion throughout.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bilu, Y., Linial, N.: Lifts, discrepancy and nearly optimal spectral gap. Combinatorica 26(5), 495–519 (2006)
Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.) 43(4), 439–561 (2006)
Bassalygo, L.A., Pinsker, M.S.: The complexity of an optimal non-blocking commutation scheme without reorganization. Problemy Peredači Informacii 9(1), 84–87 (1973)
Bollobás, B.: The isoperimetric number of random regular graphs. Eur. J. Comb. 9(3), 241–244 (1988)
Friedman, J.: A Proof of Alon’s Second Eigenvalue Conjecture and Related Problems. Memoirs of the American Mathematical Society. AMS (2008)
Margulis, G.A.: Explicit constructions of expanders. Problemy Peredači Informacii 9(4), 71–80 (1973)
Gabber, O., Galil, Z.: Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci. 22(3), 407–420 (1981)
Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261–277 (1988)
Reingold, O., Vadhan, S., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In: FOCS (2000)
Marcus, A., Spielman, D.A., Srivastava, N.: Interlacing families i: Bipartite ramanujan graphs of all degrees. In: FOCS, pp. 529–537 (2013)
Singla, A., Hong, C.Y., Popa, L., Godfrey, P.B.: Jellyfish: Networking data centers randomly. In: 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI) (April 2012)
Pandurangan, G., Robinson, P., Trehan, A.: DEX: self-healing expanders. In: 2014 IEEE 28th International Parallel and Distributed Processing Symposium, Phoenix, AZ, USA, May 19-23, pp. 702–711. IEEE (2014)
Naor, M., Wieder, U.: Novel architectures for p2p applications: The continuous-discrete approach. ACM Trans. Algorithms 3(3) (August 2007)
Dinitz, M., Schapira, M., Valadrsky, A.: Explicit expanding expanders. Preprint (2015). http://arxiv.org/abs/1507.01196
Alon, N., Chung, F.: Explicit construction of linear sized tolerant networks. Discrete Mathematics 72(13), 15–19 (1988)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dinitz, M., Schapira, M., Valadarsky, A. (2015). Explicit Expanding Expanders. In: Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015. Lecture Notes in Computer Science(), vol 9294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48350-3_34
Download citation
DOI: https://doi.org/10.1007/978-3-662-48350-3_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48349-7
Online ISBN: 978-3-662-48350-3
eBook Packages: Computer ScienceComputer Science (R0)