3
$\begingroup$

I would like to know if there is any research dealing with the problem of constructing an increasing family of expander graphs.

The goal is to find a family of expander graphs $(G_i)_{i \in \mathbb{N}} = ((V_i,E_i ))_{i \in \mathbb{N}} $ satisfying $V_1 \subseteq V_2 \ldots \subseteq V_n$ and $E_1 \subseteq E_2 \ldots \subseteq E_n$ for all $n \in \mathbb{N}$

and more idealy a family where $V_i = \{1,2 \ldots, n \}$.

$\endgroup$

1 Answer 1

3
$\begingroup$

You can construct such a family, with $|V_{n+1}| = 2|V_n|$, using random lifts. The classical work in the area is Bilu and Linial, Lifts, discrepancy and nearly optimal spectral gap. There are several recent papers of Marcus, Spielman and Srivastava on the topic (Interlacing families I and IV), which improve the bounds in the bipartite case; see also Hall, Puder and Sawin, Ramanujan coverings of graphs.

A related notion is expanding expanders, see for example Gil Cohan and Itay Cohen, Spectral expanding expanders.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.