Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-08T18:28:16.848Z Has data issue: false hasContentIssue false
  • English
  • Français

An Elementary Construction of Constant-Degree Expanders

Published online by Cambridge University Press:  01 May 2008

NOGA ALON ,
ODED SCHWARTZ  and
ASAF SHAPIRA
NOGA ALON
Affiliation:
Schools of Mathematics and Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: nogaa@tau.ac.il)
ODED SCHWARTZ
Affiliation:
School of Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: odedsc@tau.ac.il, asafico@tau.ac.il)
ASAF SHAPIRA
Affiliation:
School of Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: odedsc@tau.ac.il, asafico@tau.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We describe a short and easy-to-analyse construction of constant-degree expanders. The construction relies on the replacement product, applied by Reingold, Vadhan and Wigderson (2002) to give an iterative construction of bounded-degree expanders. Here we give a simpler construction, which applies the replacement product (only twice!) to turn the Cayley expanders of Alon and Roichman (1994), whose degree is polylog n, into constant-degree expanders. This enables us to prove the required expansion using a simple new combinatorial analysis of the replacement product (instead of the spectral analysis used by Reingold, Vadhan and Wigderson).

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 3 , May 2008 , pp. 319 - 327
Copyright
Copyright © Cambridge University Press 2008

References

[1]Ajtai, M. (1994) Recursive construction for 3-regular expanders. Combinatorica 14 379–416.CrossRefGoogle Scholar
[2]Alon, N. (1986) Eigenvalues and expanders. Combinatorica 6 83–96.CrossRefGoogle Scholar
[3]Alon, N. and Milman, V. D. (1984) Eigenvalues, expanders and superconcentrators. In Proc. 25th Annual Symp. on Foundations of Computer Science (FOCS), Singer Island, Florida, IEEE, pp. 320–322. Also: λ1, isoperimetric inequalities for graphs and superconcentrators. J. Combin. Theory Ser. B 38 73–88 (1985).Google Scholar
[4]Alon, N. and Roichman, Y. (1994) Random Cayley graphs and expanders. Random Struct. Alg. 5 271–284.CrossRefGoogle Scholar
[5]Bilu, Y. and Linial, N. (2006) Lifts, discrepancy and nearly optimal spectral gaps. Combinatorica 26 495–519.CrossRefGoogle Scholar
[6]Dodziuk, J. (1984) Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Amer. Math. Soc. 284 787–794.CrossRefGoogle Scholar
[7]Gabber, O. and Galil, Z. (1981) Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci. 22 407–420.CrossRefGoogle Scholar
[8]Gromov, M. (1983) Filling Riemannian manifolds. J. Differential Geometry 18 1–147.CrossRefGoogle Scholar
[9]Hoory, S., Linial, N. and Wigderson, A. (2006) Expander graphs and their applications. Bull. Amer. Math. Soc. 43 439–561.CrossRefGoogle Scholar
[10]Lubotzky, A., Phillips, R. and Sarnak, P. (1988) Ramanujan graphs. Combinatorica 8 261–277.CrossRefGoogle Scholar
[11]Margulis, G. (1973) Explicit constructions of expanders. Problemy Peredacl Informacii 9 71–80.Google Scholar
[12]Margulis, G. A. (1988) Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators. Problems of Information Transmission 24 39–46.Google Scholar
[13]Pinsker, M. (1973) On the complexity of a concentrator. In 7th Annual Teletraffic Conference, pp. 1–4.Google Scholar
[14]Reingold, O., Vadhan, S. and Wigderson, A. (2002) Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. of Math. 155 157–187.CrossRefGoogle Scholar