Expander graph

In mathematics , expander graphs are families of graphs that are simultaneously thin and highly connected and have very good stability properties, i.e. they cannot be broken down into several connected components by removing relatively few edges. This clearly means that every “small” subset of nodes has a relatively “large” neighborhood.

Definitions

A graph is an expander if its Cheeger constant meets the inequality ${\displaystyle X=(E,K)}$ ${\displaystyle \varepsilon }$

${\displaystyle h(X)\geq \epsilon }$

Fulfills.

One speaks of a family of expander graphs if

• there is one such that all graphs of the family are -expander, ${\displaystyle \varepsilon >0}$ ${\displaystyle \varepsilon }$

and if it continues

• the number of nodes in the graphs approaches infinity (for each there are only finitely many graphs in the family with fewer than nodes) ${\displaystyle N\in \mathbb {N} }$ ${\displaystyle N}$

and

• there is a uniform upper bound for the nodal degree of the graph. ${\displaystyle v}$

Because of the Cheeger-Buser inequality , the first condition is equivalent to the requirement that there exists such that for all graphs of the family the second smallest eigenvalue of the Laplace matrix is the inequality ${\displaystyle \epsilon ^{\prime }>0}$ ${\displaystyle \lambda _{1}}$

${\displaystyle \lambda _{1}(X)\geq \varepsilon ^{\prime }}$

Fulfills.

The name "expander graph" is explained by the following property of expanders with an upper bound for the node degree: for a node , the number of nodes is at least equal to the distance . ${\displaystyle \varepsilon }$ ${\displaystyle v}$ ${\displaystyle x}$ ${\displaystyle \leq n}$ ${\displaystyle \min \left({\frac {\mid E\mid }{2}},\left(1+{\frac {\varepsilon }{v}}\right)^{n}\right)}$

Examples

• The Cayley graphs of are expanders because for them holds . According to the as yet unproven Selberg conjecture, it should always be. ${\displaystyle SL(2,\mathbb {Z} /n\mathbb {Z} )}$ ${\displaystyle \lambda _{1}>{\frac {3}{16}}}$ ${\displaystyle \lambda _{1}\geq {\frac {1}{4}}}$

• Ramanujan graphs have optimal expander properties.

• The Petersen graph is a Ramanujan graph.

• Lubotzky-Philips-Sarnak construct families of Ramanujan graphs as quotients of p-adic symmetric spaces under certain group effects. ${\displaystyle PGL(2,\mathbb {Q} _{p})/PGL(2,\mathbb {Z} _{p})}$

• There are several arguments that certain classes of random graphs with positive probability or even probability are expander graphs or even Ramanujan graphs. Historically, the first such class was described by Kolmogorov-Barzdins in 1967. ${\displaystyle 1}$

literature

• Alexander Lubotzky : Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski. Progress in Mathematics, 125. Birkhäuser Verlag, Basel, 1994. ISBN 3-7643-5075-X
• Shlomo Hoory, Nathan Linial , Avi Wigderson : Expander Graphs and their Applications , Bulletin of the AMS, Volume 43, 2006, pp. 439-561, online

Web links

• E. Kowalski: Expander Graphs
• N. Linial, A. Wigderson: Expander Graphs and their applications

Individual evidence

1. ^ Lubotzky , Phillips , Sarnak : Ramanujan graphs. Combinatorica 8 (1988) no. 3, 261-277.
2. ↑ Kolmogorow , Bārzdiņš : On the realization of networks in three-dimensional space. (1967), in: Selected Works of Kolmogorov , Volume 3, Kluwer Academic Publishers, Dordrecht, 1993.