HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Increasing families of expander graphs

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
graphsexpanderincreasingfamilies

Problem

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 \}$.

Solution

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.

Context

StackExchange Computer Science Q#162758, answer score: 3

Revisions (0)

No revisions yet.