Expander graph
|
|
In combinatorics, an expander graph is in rough terms a sparse graph with high vertex or edge expansion, or in other words highly connected. Expander constructions have spawned research in pure and applied mathematics, with several applications to computer science, in particular cryptography and the theory of error-correcting codes.
The expansion of a graph is related to the graph spectrum, studied in spectral graph theory. In particular, the expansion is related to the second eigenvalue of the adjacency matrix. A random graph has good expansion, with high probability. Explicit constructions of expander graphs are needed in several applications.
Ramanujan graphs are class of d-regular expander graphs, with explicit constructions, that achieve the largest gap between the first and second eigenvalues of the adjacency matrix. They are formally defined as graphs whose second eigenvalue is less than
- <math>2\sqrt{d-1}.\,<math>
Let N(S) denote the set of neighbors of S (excluding S itself), where S is a set of vertices and neighbors can be defined as adjacent vertices.
The vertex expansion of a graph is the minimum of |N(S)| / |S|.
Let E(A,B) denote the number of edges with one extremity in A and the other in B, where A and B are vertex sets. Let /S denote the complement of S.
The edge expansion of a graph is the minimum E(S,/S) / |S|.