|
|
| (720 intermediate revisions by more than 100 users not shown) |
| Line 1: |
Line 1: |
| In [[combinatorics]], an '''expander graph''' is a [[sparse graph]] that has strong [[connectivity (graph theory)|connectivity]] properties, quantified using [[vertex (graph theory)|vertex]], [[edge (graph theory)|edge]] or spectral expansion as described below. Expander constructions have spawned research in pure and applied mathematics, with several applications to [[Computational complexity theory|complexity theory]], design of robust [[computer network]]s, and the theory of [[error-correcting code]]s.<ref>{{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
| | This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users. |
|
| |
|
| ==Definitions==
| | If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]] |
| | * Only registered users will be able to execute this rendering mode. |
| | * Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere. |
|
| |
|
| Intuitively, an expander is a finite, undirected [[multigraph]] in which every subset of the vertices "which 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.
| | Registered users will be able to choose between the following three rendering modes: |
|
| |
|
| A disconnected graph is not an expander, since the boundary of a connected component is empty. Every connected 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.
| | '''MathML''' |
| | :<math forcemathmode="mathml">E=mc^2</math> |
|
| |
|
| ===Edge expansion===
| | <!--'''PNG''' (currently default in production) |
| The ''edge expansion'' (also ''isoperimetric number'' or [[Cheeger constant (graph theory)|Cheeger constant]]) <math>h(G)</math> of a graph <math>G</math> is defined as
| | :<math forcemathmode="png">E=mc^2</math> |
| : <math>h(G) = \min_{0 < |S| \le \frac{n}{2} } \frac{|\partial(S)|}{|S|}\,,</math> | |
| where the minimum is over all nonempty sets <math>S</math> of at most <math>n/2</math> vertices and <math>\partial(S)</math> is the ''edge boundary'' of <math>S</math>, i.e., the set of edges with exactly one endpoint in <math>S</math>.<ref>Definition 2.1 in {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
| |
|
| |
|
| ===Vertex expansion===
| | '''source''' |
| The ''vertex isoperimetric number'' <math>h_{\text{out}}(G)</math> (also ''vertex expansion'' or ''magnification'') of a graph <math>G</math> is defined as
| | :<math forcemathmode="source">E=mc^2</math> --> |
| : <math>h_{\text{out}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|}\,,</math> | |
| where <math>\partial_{\text{out}}(S)</math> is the ''outer boundary'' of <math>S</math>, i.e., the set of vertices in <math>V(G)\setminus S</math> with at least one neighbor in <math>S</math>.<ref name="BobkovHoudre">{{harvtxt|Bobkov|Houdré|Tetali|2000}}</ref>
| |
| In a variant of this definition (called ''unique neighbor expansion'') <math>\partial_{\text{out}}(S)</math> is replaced by the set of vertices in <math>V</math> with ''exactly'' one neighbor in <math>S</math>.<ref name="AlonCapalbo">{{harvtxt|Alon|Capalbo|2002}}</ref>
| |
|
| |
|
| The ''vertex isoperimetric number'' <math>h_{\text{in}}(G)</math> of a graph <math>G</math> is defined as
| | <span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples]. |
| : <math>h_{\text{in}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{in}}(S)|}{|S|}\,,</math> | |
| where <math>\partial_{\text{in}}(S)</math> is the ''inner boundary'' of <math>S</math>, i.e., the set of vertices in <math>S</math> with at least one neighbor in <math>V(G)\setminus S</math>.<ref name="BobkovHoudre" />
| |
|
| |
|
| ===Spectral expansion=== | | ==Demos== |
| When <math>G</math> is [[regular graph|regular]], a [[linear algebra]]ic definition of expansion is possible based on the [[Eigenvalue#Eigenvalues of matrices|eigenvalues]] of the [[adjacency matrix]] <math>A=A(G)</math> of <math>G</math>, where <math>A_{ij}</math> is the number of edges between vertices <math>i</math> and <math>j</math>.<ref>cf. Section 2.3 in {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
| |
| Because <math>A</math> is [[symmetric matrix|symmetric]], the [[spectral theorem]] implies that <math>A</math> has <math>n</math> real-valued eigenvalues <math>\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_{n}</math>.
| |
| It is known that all these eigenvalues are in <math>[-d,d]</math>.
| |
|
| |
|
| Because <math>G</math> is regular, the uniform distribution <math>u\in\R^n</math> with <math>u_i=1/n</math> for all <math>i=1,\dots,n</math> is the [[stationary distribution]] of <math>G</math>.
| | Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]: |
| That is, we have <math>Au=du</math>, and <math>u</math> is an eigenvector of <math>A</math> with eigenvalue <math>\lambda_1=d</math>, where <math>d</math> is the [[degree (graph theory)|degree]] of the vertices of <math>G</math>.
| |
| The ''[[spectral gap]]'' of <math>G</math> is defined to be <math>d-\lambda_2</math>, and it measures the spectral expansion of the graph <math>G</math>.<ref>This definition of the spectral gap is from Section 2.3 in {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
| |
|
| |
|
| It is known that <math>\lambda_n=-d</math> if and only if <math>G</math> is bipartite.
| |
| In many context, for example in the [[expander mixing lemma]], it is necessary to bound from below not only the gap between <math>\lambda_1</math> and <math>\lambda_2</math>, but also the gap between <math>\lambda_1</math> and
| |
| the second-largest eigenvalue in absolute value:
| |
| <math>\lambda=\max\{|\lambda_2|, |\lambda_{n}|\}</math>.
| |
| Since this is the largest eigenvalue corresponding to an eigenvector orthogonal to <math>u</math>, it can be equivalently defined using the [[Rayleigh quotient]]:
| |
| :<math>\lambda=\max_{0\neq v\perp u} \frac{\|Av\|_2}{\|v\|_2}\,,</math>
| |
| where <math>\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{1/2}</math> is the [[2-norm]] of the vector <math>v\in\R^n</math>.
| |
|
| |
|
| The normalized versions of these definitions are also widely used and more convenient in stating some results.
| | * accessibility: |
| Here one considers the matrix <math>\frac{1}{d} A</math>, which is the [[Markov transition matrix]] of the graph <math>G</math>.
| | ** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]] |
| Its eigenvalues are between <math>-1</math> and <math>1</math>.
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)] |
| For not necessarily regular graphs, the spectrum of a graph can be defined similarly using the eigenvalues of the [[Laplacian matrix]].
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)] |
| For directed graphs, one considers the [[singular values]] of the adjacency matrix <math>A</math>, which are equal to the roots of the eigenvalues of the symmetric matrix <math>A^T A</math>.
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)] |
| | ** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]]. |
| | ** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]]. |
| | ** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode. |
|
| |
|
| ==Relationships between different expansion properties== | | ==Test pages == |
| The expansion parameters defined above are related to each other.
| |
| In particular, for any <math>d</math>-regular graph <math>G</math>,
| |
| :<math>h_{\text{out}}(G) \le h(G) \le d \cdot h_{\text{out}}(G)\,.</math>
| |
|
| |
|
| Consequently, for constant degree graphs, vertex and edge expansion are qualitatively the same.
| | To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages: |
| | *[[Displaystyle]] |
| | *[[MathAxisAlignment]] |
| | *[[Styling]] |
| | *[[Linebreaking]] |
| | *[[Unique Ids]] |
| | *[[Help:Formula]] |
|
| |
|
| ===Cheeger inequalities===
| | *[[Inputtypes|Inputtypes (private Wikis only)]] |
| When <math>G</math> is <math>d</math>-regular, there is a relationship between <math>h(G)</math> and the spectral gap <math>d - \lambda_2</math> of <math>G</math>. An inequality due to Tanner and independently [[Noga Alon|Alon]] and [[Vitali Milman|Milman]]{{Sfn|Alon|Spencer|2011}} states that
| | *[[Url2Image|Url2Image (private Wikis only)]] |
| | | ==Bug reporting== |
| : <math>\frac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}\,.</math><ref>Theorem 2.4 in {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
| | If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de . |
| | |
| This inequality is closely related to the [[Cheeger bound]] for [[Markov chains]] and can be seen as a discrete version of [[Cheeger_constant#Cheeger.27s_inequality|Cheeger's inequality]] in [[Riemannian geometry]].
| |
| | |
| Similar connections between vertex isoperimetric numbers and the spectral gap have also been studied:<ref>See Theorem 1 and p.156, l.1 in {{harvtxt|Bobkov|Houdré|Tetali|2000}}. Note that ''λ''<sub>2</sub> there corresponds to 2(''d'' − ''λ''<sub>2</sub>) of the current article (see p.153, l.5)</ref>
| |
| : <math>h_{\text{out}}(G)\le \left(\sqrt{4 (d-\lambda_2)} + 1\right)^2 -1</math>
| |
| : <math>h_{\text{in}}(G) \le \sqrt{8(d-\lambda_2)}.</math>
| |
| Asymptotically speaking, the quantities
| |
| <math>\frac{h^2}{d}</math>, <math>h_{\text{out}}</math>, and <math>h_{\text{in}}^2</math> are all bounded above by the spectral gap <math>O(d-\lambda_2)</math>.
| |
| | |
| ==Examples of expanders==
| |
| ===Petersen graph===
| |
| [[image:Petersen graph blue.svg|thumb|The [[Petersen graph]]]]
| |
| Consider the 3-regular graph ''G'' on 10 vertices (''n'' = 10, ''d'' = 3) shown.
| |
| | |
| If we number the vertices by going around twice, starting with the outside pentagon and then the inside pentagon, ''G'' has the following adjacency matrix:
| |
| | |
| <math>
| |
| \begin{pmatrix}
| |
| 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\
| |
| 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
| |
| 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\
| |
| 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0\\
| |
| 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1\\
| |
| 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0\\
| |
| 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\
| |
| 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\
| |
| 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0\\
| |
| 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0\\
| |
| \end{pmatrix}
| |
| </math>
| |
| | |
| One can calculate that the two largest eigenvalues of this matrix are 3 and 1. From this, one may deduce that
| |
| | |
| <math>\frac{d - \lambda_2}{2} = \frac{3 - 1}{2} = 1</math>
| |
| | |
| <math>\sqrt{2 d (d - \lambda_2)} = \sqrt{2 \cdot 3 (3 - 1)} = 2 \sqrt{3}</math>
| |
| and consequently that <math>1 \leq h(G) \leq 2 \sqrt{3} \approx 3.46 </math>.
| |
| | |
| In fact, <math>h(G) = 1</math>. To persuade oneself of this, it suffices to consider the five vertices in the central star: there are five edges that touch exactly one of these vertices, giving an edge expansion for this set of 5/5 = 1.
| |
| | |
| ===Ramanujan graphs===
| |
| By a theorem of Alon and Boppana, all large enough <math>d</math>-regular graphs satisfy <math>\lambda \ge 2\sqrt{d-1} - o(1)</math>.<ref>Theorem 2.7 of {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
| |
| [[Ramanujan graph]]s are <math>d</math>-regular graphs that meet this bound, that is, they satisfy <math>\lambda \le 2\sqrt{d-1}</math>.<ref>Definition 5.11 of {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
| |
| Hence Ramanujan graphs have an asymptotically smallest possible second-largest eigenvalue <math>\lambda</math> (in absolute value).
| |
| | |
| [[Alexander Lubotzky|Lubotzky]], Phillips, and Sarnak (1988), Margulis (1988), and Morgenstern (1994) show how Ramanujan graphs can be constructed explicitly.<ref>Theorem 5.12 of {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
| |
| By a theorem of Friedman (2003), [[Random regular graph|random d-regular graphs]] on <math>n</math> vertices are almost Ramanujan, that is, they satisfy <math>\lambda \le 2\sqrt{d-1}+\epsilon</math> with probability <math>1-o(1)</math> as <math>n</math> tends to infinity.<ref>Theorem 7.10 of {{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>
| |
| | |
| ==Other examples==
| |
| [[Abstract algebra|Algebraic]] constructions based on [[Cayley graph]]s are known for various variants of expander graphs.
| |
| Most recently, combinatorial constructions of expanders have also been discovered.
| |
| | |
| ==Applications and useful properties== | |
| The original motivation for expanders is to build economical robust networks (phone or computer): an expander with bounded valence is precisely an asymptotic robust graph with number of edges growing linearly with size (number of vertices), for all subsets.
| |
| | |
| Expander graphs have found extensive applications in [[computer science]], in designing [[algorithm]]s, [[Expander code|error correcting codes]], [[Extractor (mathematics)|extractors]], [[pseudorandom generator]]s, [[sorting network]]s ({{harvtxt|Ajtai|Komlós|Szemerédi|1983}}) and robust [[computer network]]s. They have also been used in proofs of many important results in [[computational complexity theory]], such as [[SL (complexity)|SL]]=[[L (complexity)|L]] ({{harvtxt|Reingold|2008}}) and the [[PCP theorem]] ({{harvtxt|Dinur|2007}}). In [[cryptography]], expander graphs are used to construct [[hash function]]s.
| |
| | |
| The following are some properties of expander graphs that have proven useful in many areas.
| |
| | |
| ===Expander mixing lemma===
| |
| {{Main|Expander mixing lemma}}
| |
| The expander mixing lemma states that, for any two subsets of the vertices <math>S, T \subseteq V</math>, the number of edges between <math>S</math> and <math>T</math> is approximately what you would expect in a random <math>d</math>-regular graph. The approximation is better, the smaller <math>\lambda=\max\{|\lambda_2|,|\lambda_n|\}</math> is.
| |
| In a random <math>d</math>-regular graph, as well as in an [[Erdős–Rényi model|Erdős–Rényi random graph]] with edge probability <math>d/n</math>, we expect <math>\frac{d}{n} \cdot |S| \cdot |T|</math> edges between <math>S</math> and <math>T</math>.
| |
| | |
| More formally, let <math>E(S, T)</math> denote the number of edges between <math>S</math> and <math>T</math>.
| |
| If the two sets are not disjoint, edges in their intersection are counted twice, that is,
| |
| <math>E(S,T)=2|E(G[S\cap T])| + E(S\setminus T,T) + E(S,T\setminus S)</math>.
| |
| | |
| Then the expander mixing lemma says that the following inequality holds:
| |
| :<math>\left|E(S, T) - \frac{d \cdot |S| \cdot |T|}{n}\right| \leq d\lambda \sqrt{|S| \cdot |T|}\,.</math>
| |
| where <math>\lambda</math> is the absolute value of the '''normalized''' second largest eigenvalue.
| |
| | |
| ===Expander walk sampling=== | |
| {{Main|Expander walk sampling}}
| |
| The [[Chernoff bound]] states that, when sampling many independent samples from a random variables in the range <math>[-1, 1]</math>, with high probability the average of our samples is close to the expectation of the random variable. The expander walk sampling lemma, due to {{harvtxt|Ajtai|Komlós|Szemerédi|1987}} and {{harvtxt|Gillman|1998}}, states that this also holds true when sampling from a walk on an expander graph. This is particularly useful in the theory of [[derandomization]], since sampling according to an expander walk uses many fewer random bits than sampling independently.
| |
| | |
| ==See also==
| |
| *[[Algebraic connectivity]]
| |
| *[[Zig-zag product]]
| |
| | |
| ==Notes==
| |
| {{Reflist|colwidth=25em}}
| |
| | |
| ==References==
| |
| {{Refbegin|colwidth=25em}}
| |
| '''Textbooks and surveys'''
| |
| * {{cite book|title=The Probabilistic Method|first1=N.|last1=Alon|author1-link=Noga Alon|first2=Joel H.|last2=Spencer|author2-link=Joel Spencer|publisher=John Wiley & Sons|year=2011|edition=3rd|chapter=9.2. Eigenvalues and Expanders|ref=harv}}
| |
| * {{Citation | last=Chung |first=Fan R. K. | title=Spectral Graph Theory | series=CBMS Regional Conference Series in Mathematics | volume=92 | publisher=[[American Mathematical Society]] | year=1997 | isbn=0-8218-0315-8}}
| |
| * {{Citation | first1=Guiliana |last1=Davidoff | first2=Peter | last2=Sarnak | first3=Alain | last3=Valette | title=Elementary number theory, group theory and Ramanjuan graphs | publisher=[[Cambridge University Press]] | series=LMS student texts | volume=55 | year=2003 | isbn=0-521-53143-8}}
| |
| * {{Citation | first1=Shlomo | last1=Hoory | first2=Nathan | last2=Linial | author2-link = Nati Linial | first3=Avi | last3=Widgerson | author3-link = Avi Wigderson | title=Expander graphs and their applications | journal= Bulletin (New series) of the American Mathematical Society | volume=43 | issue=4 | pages=439–561 | url=http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf | year=2006 | doi = 10.1090/S0273-0979-06-01126-8}}
| |
| * {{Citation | first1=Mike |last1=Krebs | first2=Anthony | last2=Shaheen | title=Expander families and Cayley graphs: A beginner's guide | publisher=Oxford University Press | year=2011 | isbn=0-19-976711-4}}
| |
| '''Research articles'''
| |
| * {{Citation|last1=Ajtai|first1=M.|author1-link=Miklós Ajtai|last2=Komlós|first2=J.|author2-link=János Komlós (mathematician)|last3=Szemerédi|first3=E.|author3-link=Endre Szemerédi|chapter=An O(n log n) sorting network|title=Proceedings of the 15th Annual ACM Symposium on Theory of Computing|pages=1–9|year=1983|doi=10.1145/800061.808726|isbn=0-89791-099-0}}
| |
| * {{Citation
| |
| | first1=M. | last1=Ajtai
| |
| | first2=J. | last2=Komlós
| |
| | first3=E. | last3=Szemerédi
| |
| | chapter=Deterministic simulation in LOGSPACE
| |
| | title=Proceedings of the 19th Annual ACM Symposium on Theory of Computing
| |
| | pages=132–140
| |
| | year=1987
| |
| | work=ACM
| |
| | doi=10.1145/28395.28410
| |
| | isbn=0-89791-221-7
| |
| }}
| |
| * {{cite doi|10.1109/SFCS.2002.1181884}}
| |
| * {{Citation
| |
| |last1=Bobkov|first1=S.
| |
| |last2=Houdré|first2=C.
| |
| |last3=Tetali|first3=P.
| |
| |title=λ<sub>∞</sub>, vertex isoperimetry and concentration|journal=Combinatorica|volume=20|issue=2|year=2000|doi=10.1007/s004930070018|pages = {153–172}}}.
| |
| * {{Citation|last=Dinur|first=Irit|title=The PCP theorem by gap amplification|journal=Journal of the ACM|volume=54|issue=3|year=2007|doi=10.1145/1236457.1236459|pages=12}}.
| |
| * {{Citation
| |
| | first=D. | last=Gillman
| |
| | title=A Chernoff Bound for Random Walks on Expander Graphs
| |
| | journal=SIAM Journal on Computing
| |
| | volume=27
| |
| | issue=4,
| |
| | pages=1203–1220
| |
| | year=1998
| |
| | publisher=Society for Industrial and Applied Mathematics
| |
| | doi=10.1137/S0097539794268765
| |
| }}
| |
| * {{Citation|first=Omer|last=Reingold|authorlink=Omer Reingold|title=Undirected connectivity in log-space|journal=[[Journal of the ACM]]|year=2008|
| |
| volume=55|issue=4|pages=Article 17, 24 pages|doi=10.1145/1391289.1391291
| |
| }}
| |
| {{Refend}}
| |
| | |
| == External links ==
| |
| * [http://www.ams.org/notices/200407/what-is.pdf Brief introduction in Notices of the American Mathematical Society]
| |
| * [http://michaelnielsen.org/blog/archive/notes/expander_graphs.pdf Introductory paper by Michael Nielsen]
| |
| * [http://www.math.ias.edu/~boaz/ExpanderCourse/ Lecture notes from a course on expanders (by Nati Linial and Avi Wigderson)]
| |
| * [http://ttic.uchicago.edu/~prahladh/teaching/spring05/index.html Lecture notes from a course on expanders (by Prahladh Harsha)]
| |
| *[http://www.yann-ollivier.org/specgraph/specgraph.html Definition and application of spectral gap]
| |
| | |
| {{DEFAULTSORT:Expander Graph}}
| |
| [[Category:Graph families]]
| |
| | |
| [[cs:Expander (graf)]]
| |
| [[fr:Graphe expanseur]]
| |
| [[he:גרף מרחיב]]
| |
| [[pl:Ekspander]]
| |
