User:Manojmp/Expanders

In combinatorics, an expander graph refers to a sparse graph which has high connectivity properties, quantified using vertex or edge expansion as described below. Expander constructions have spawned research in pure and applied mathematics, with several applications to computer science, and in particular to theoretical computer science, design of robust computer networks and the theory of error-correcting codes.

Definitions

A family of regular undirected multigraphs (with self-loops) of increasing number of vertices and constant degree $d$ is said to be a family of expander graphs if the expansion parameters (as defined below) of all the graphs in the family are bounded below by a strictly positive constant. There are various possible definitions for the expansion parameter, which are qualitatively similar, but quantitatively different. Below we let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$, and $|V|=n$.

Edge expansion

The edge expansion parameter of $G$ is defined as

$h(G)=\min _{\{S||S|\leq {\frac {n}{2}}\}}{\frac {|\partial (S)|}{|S|}}$

where the minimum is over all $S\subseteq V$ with at most $n/2$ vertices in it, and $\partial (S)$ stands for the set of edges in $E$ with exactly one endpoint in $S$.

Vertex expansion

The vertex expansion parameter of $G$ is defined as

$g(G)=\min _{\{S||S|\leq \alpha {n}\}}{\frac {|\Gamma (S)|}{|S|}}$

where $\alpha$ is a parameter of the definition, and $\Gamma (S)$ stands for the set of vertices in $V$ with at least one neighbor in $S$. In a variant of this definition (called unique neighbor expansion) $\Gamma (S)$ stands for the set of vertices in $V$ with exactly one neighbor in $S$.

Spectral expansion

A linear algebraic definition of expansion is possible based on the eigenvalues of the adjacency matrix of $G$ (with the $i$-th diagonal entry being the number of self-loops on the $i$-th vertex). For $G$ as described, there are $n$ eigenvalues $\lambda _{0}\geq \lambda _{1}\geq \ldots \geq \lambda _{n-1}$ with $\lambda _{0}=d$. The expansion parameter here is the spectral gap defined as $\lambda _{0}-\lambda _{1}$. An alternate definition of the spectral gap is as $\lambda _{0}-\lambda$, where $\lambda =\max\{|\lambda _{1}|,|\lambda _{n-1}|\}$.

These definitions can be extended to the case of directed graphs. A directed graph can also be interpreted as a balanced bipartite graph (with all edges going from one copy of $V$ to another copy). The definition of bipartite expanders can further be generalized to the case of unbalanced bipartite graphs.

Examples of Expanders

A random $d$-regular graph has good expansion, with high probability. Explicit constructions of expander graphs are needed in several applications. Ramanujan graphs are a family of $d$-regular expander graphs, with explicit constructions, that have essentially the largest possible spectral gap. Algebraic constructions based on cayley graphs are known for various variants of expander graphs. Combinatorial constructions using graph products are also known.

Applications

Expander graphs have found extensive applications in computer science, in designing algorithms, error correcting codes, randomness extractors, pseudorandomness generators, sorting networks and robust computer networks. They have also been used in proving many important results in computational complexity theory.