Expander graph

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

Definitions

Intuitively, an expander graph is a finite, undirected multigraph in which every subset of the vertices that is not "too large" has a "large" boundary. Different formalisations of these notions give rise to different notions of expanders: edge expanders, vertex expanders, and spectral expanders, as defined below.

A disconnected graph is not an expander, since the boundary of a connected component is empty. Every connected finite graph is an expander; however, different connected graphs have different expansion parameters. The complete graph has the best expansion property, but it has largest possible degree. Informally, a graph is a good expander if it has low degree and high expansion parameters.

Edge expansion

The edge expansion (also isoperimetric number or Cheeger constant) h(G) of a graph G on n vertices is defined as

h

(

G

)

=

min

0

<

|

S

|

≤

n

2

|

∂

S

|

|

S

|

,

{\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial S|}{|S|}},}

where

∂

S

:=

{

{

u

,

v

}

∈

E

(

G

)

:

u

∈

S

,

v

∉

S

}

,

{\displaystyle \partial S:=\{\{u,v\}\in E(G)\ :\ u\in S,v\notin S\},}

which can also be written as ∂S = E(S, S) with S := V(G) \ S the complement of S and

E

(

A

,

B

)

=

{

{

u

,

v

}

∈

E

(

G

)

:

u

∈

A

,

v

∈

B

}

{\displaystyle E(A,B)=\{\{u,v\}\in E(G)\ :\ u\in A,v\in B\}}

the edges between the subsets of vertices A,B ⊆ V(G).

In the equation, the minimum is over all nonempty sets S of at most n⁄2 vertices and ∂S is the edge boundary of S, i.e., the set of edges with exactly one endpoint in S.

Intuitively,

min

|

∂

S

|

=

min

|

E

(

S

,

S

¯

)

|

{\displaystyle \min {|\partial S|}=\min |E({S},{\overline {S}})|}

is the minimum number of edges that need to be cut in order to split the graph in two.