Editing Expander graph (section)

===Expander mixing lemma===
{{Main|Expander mixing lemma}}
The expander mixing lemma states that for an {{math|(''n'', ''d'', ''λ'')}}-graph, for any two subsets of the vertices {{math|''S'', ''T'' ⊆ ''V''}}, the number of edges between {{mvar|S}} and {{mvar|T}} is approximately what you would expect in a random {{mvar|d}}-regular graph. The approximation is better the smaller {{math|''λ''}} is. In a random {{mvar|d}}-regular graph, as well as in an [[Erdős–Rényi model|Erdős–Rényi random graph]] with edge probability {{math|{{frac|''d''|''n''}}}}, we expect {{math|{{frac|''d''|''n''}} • {{abs|''S''}} • {{abs|''T''}}}} edges between {{mvar|S}} and {{mvar|T}}.

More formally, let {{math|''E''(''S'', ''T'')}} denote the number of edges between {{mvar|S}} and {{mvar|T}}. 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 \lambda  \sqrt{|S| \cdot |T|}.</math>
Many properties of {{math|(''n'', ''d'', ''λ'')}}-graphs are corollaries of the expander mixing lemmas, including the following.<ref name="Hoory 2006"/>

* An [[Independent set (graph theory)|independent set]] of a graph is a subset of vertices with no two vertices adjacent. In an {{math|(''n'', ''d'', ''λ'')}}-graph, an independent set has size at most {{math|{{frac|''λn''|''d''}}}}.
* The [[Graph coloring|chromatic number]] of a graph {{mvar|G}}, {{math|''χ''(''G'')}}, is the minimum number of colors needed such that adjacent vertices have different colors. Hoffman showed that {{math|{{frac|''d''|''λ''}} ≤ ''χ''(''G'')}},<ref>{{Cite journal|last1=Hoffman|first1=A. J.|last2=Howes|first2=Leonard|date=1970|title=On Eigenvalues and Colorings of Graphs, Ii|url=https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1749-6632.1970.tb56474.x|journal=Annals of the New York Academy of Sciences|language=en|volume=175|issue=1|pages=238–242|doi=10.1111/j.1749-6632.1970.tb56474.x|bibcode=1970NYASA.175..238H|s2cid=85243045|issn=1749-6632}}</ref> while Alon, Krivelevich, and Sudakov showed that if {{math|''d'' < {{frac|2''n''|3}}}}, then<ref>{{Cite journal|last1=Alon|first1=Noga|author-link1=Noga Alon|last2=Krivelevich|first2=Michael|author-link2=Michael Krivelevich|last3=Sudakov|first3=Benny|author-link3=Benny Sudakov|date=1999-09-01|title=Coloring Graphs with Sparse Neighborhoods|journal=[[Journal of Combinatorial Theory]] | series=Series B |language=en|volume=77|issue=1|pages=73–82|doi=10.1006/jctb.1999.1910|doi-access=free|issn=0095-8956}}</ref>

<math>\chi(G) \leq O \left( \frac{d}{\log(1+d/\lambda)} \right).</math>

* The [[Diameter (graph theory)|diameter]] of a graph is the maximum distance between two vertices, where the distance between two vertices is defined to be the shortest path between them. Chung showed that the diameter of an {{math|(''n'', ''d'', ''λ'')}}-graph is at most<ref>{{Cite journal|last=Chung|first=F. R. K.|date=1989|title=Diameters and eigenvalues|url=https://www.ams.org/jams/1989-02-02/S0894-0347-1989-0965008-X/|journal=Journal of the American Mathematical Society|language=en|volume=2|issue=2|pages=187–196|doi=10.1090/S0894-0347-1989-0965008-X|issn=0894-0347|doi-access=free}}</ref>

<math>\left\lceil \log \frac{n}{ \log(d/\lambda)} \right\rceil.</math>