## 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.