On constructing expanders for any number of vertices

Webpage for a memo by Oded Goldreich


Abstract

While typical constructions of explicit expanders work for certain sizes (i.e., number of vertices), one can obtain construction of about the same complexity by manipulating the original expanders. One way of doing so is detailed and analyzed below.

For any $m\in[0.5n,n]$ (equiv., $n\in[m,2m]$), given an $m$-vertex expander, $G_m$, we construct an $n$-vertex expander by connecting each of the first $n-m$ to of $G_m$ to an (otherwise isolated) new vertex, and adding edges arbitrarily to regain regularity. The analysis of this construction uses the combinatorial definition of expansion.

Material available on-line


Back to either Oded Goldreich's homepage or general list of papers.