Английская Википедия:Expander mixing lemma

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

The expander mixing lemma intuitively states that the edges of certain <math>d</math>-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets <math>S</math> and <math>T</math> is always close to the expected number of edges between them in a random <math>d</math>-regular graph, namely <math>\frac dn|S||T|</math>.

d-Regular Expander Graphs

Define an <math>(n, d, \lambda)</math>-graph to be a <math>d</math>-regular graph <math>G</math> on <math>n</math> vertices such that all of the eigenvalues of its adjacency matrix <math>A_G</math> except one have absolute value at most <math>\lambda.</math> The <math>d</math>-regularity of the graph guarantees that its largest absolute value of an eigenvalue is <math>d.</math> In fact, the all-1's vector <math>\mathbf1</math> is an eigenvector of <math>A_G</math> with eigenvalue <math>d</math>, and the eigenvalues of the adjacency matrix will never exceed the maximum degree of <math>G</math> in absolute value.

If we fix <math>d</math> and <math>\lambda</math> then <math>(n, d, \lambda)</math>-graphs form a family of expander graphs with a constant spectral gap.

Statement

Let <math>G = (V, E)</math> be an <math>(n, d, \lambda)</math>-graph. For any two subsets <math>S, T \subseteq V</math>, let <math>e(S, T) = |\{(x,y) \in S \times T : xy \in E(G)\}|</math> be the number of edges between S and T (counting edges contained in the intersection of S and T twice). Then

<math>\left|e(S, T) - \frac{d |S| |T|}{n}\right| \leq \lambda \sqrt{|S| |T| }\,.</math>

Tighter Bound

We can in fact show that

<math>\left|e(S, T) - \frac{d |S| |T|}{n}\right| \leq \lambda \sqrt{|S| |T| (1 - |S|/n)(1 - |T|/n)}\,</math>

using similar techniques.

Biregular Graphs

For biregular graphs, we have the following variation, where we take <math>\lambda </math> to be the second largest eigenvalue.

Let <math>G = (L, R, E)</math> be a bipartite graph such that every vertex in <math>L</math> is adjacent to <math>d_L</math> vertices of <math>R</math> and every vertex in <math>R</math> is adjacent to <math>d_R</math> vertices of <math>L</math>. Let <math>S \subseteq L, T \subseteq R</math> with <math>|S| = \alpha|L|</math> and <math>|T| = \beta |R|</math>. Let <math>e(G) = |E(G)|</math>. Then

<math>\left|\frac{e(S, T)}{e(G)} - \alpha \beta\right| \leq \frac{\lambda}{\sqrt{d_Ld_R}} \sqrt{\alpha \beta (1 - \alpha) (1 - \beta)} \leq \frac{\lambda}{\sqrt{d_Ld_R}} \sqrt{\alpha \beta}\,.</math>

Note that <math>\sqrt{d_L d_R}</math> is the largest eigenvalue of <math>G</math>.

Proofs

Proof of First Statement

Let <math>A_G</math> be the adjacency matrix of <math>G</math> and let <math>\lambda_1\geq\cdots\geq\lambda_n</math> be the eigenvalues of <math>A_G</math> (these eigenvalues are real because <math>A_G</math> is symmetric). We know that <math>\lambda_1=d</math> with corresponding eigenvector <math>v_1=\frac 1{\sqrt n}\mathbf{1}</math>, the normalization of the all-1's vector. Define <math>\lambda=\sqrt{\max\{\lambda_2^2,\dots,\lambda_n^2\}}</math> and note that <math>\max\{\lambda_2^2,\dots,\lambda_n^2\}\leq\lambda^2\leq\lambda_1^2=d^2</math>. Because <math>A_G</math> is symmetric, we can pick eigenvectors <math>v_2,\ldots,v_n</math> of <math>A_G</math> corresponding to eigenvalues <math>\lambda_2,\ldots,\lambda_n</math> so that <math>\{v_1,\ldots,v_n\}</math> forms an orthonormal basis of <math>\mathbf R^n</math>.

Let <math>J</math> be the <math>n\times n</math> matrix of all 1's. Note that <math>v_1</math> is an eigenvector of <math>J</math> with eigenvalue <math>n</math> and each other <math>v_i</math>, being perpendicular to <math>v_1=\mathbf{1}</math>, is an eigenvector of <math>J</math> with eigenvalue 0. For a vertex subset <math>U \subseteq V</math>, let <math>1_U</math> be the column vector with <math>v^\text{th}</math> coordinate equal to 1 if <math>v\in U</math> and 0 otherwise. Then,

<math>\left|e(S,T)-\frac dn|S||T|\right|=\left|1_S^\operatorname{T}\left(A_G-\frac dnJ\right)1_T\right|</math>.

Let <math>M=A_G-\frac dnJ</math>. Because <math>A_G</math> and <math>J</math> share eigenvectors, the eigenvalues of <math>M</math> are <math>0,\lambda_2,\ldots,\lambda_n</math>. By the Cauchy-Schwarz inequality, we have that <math>|1_S^\operatorname{T}M1_T|=|1_S\cdot M1_T|\leq\|1_S\|\|M1_T\|</math>. Furthermore, because <math>M</math> is self-adjoint, we can write

<math>\|M1_T\|^2=\langle M1_T,M1_T\rangle=\langle 1_T,M^21_T\rangle=\left\langle 1_T,\sum_{i=1}^nM^2\langle 1_T,v_i\rangle v_i\right\rangle=\sum_{i=2}^n\lambda_i^2\langle 1_T,v_i\rangle^2\leq\lambda^2\|1_T\|^2</math>.

This implies that <math>\|M1_T\|\leq\lambda\|1_T\|</math> and <math>\left|e(S,T)-\frac dn|S||T|\right|\leq\lambda\|1_S\|\|1_T\|=\lambda\sqrt{|S||T|}</math>.

Proof Sketch of Tighter Bound

To show the tighter bound above, we instead consider the vectors <math>1_S-\frac{|S|}n\mathbf 1</math> and <math>1_T-\frac{|T|}n\mathbf 1</math>, which are both perpendicular to <math>v_1</math>. We can expand

<math>1_S^\operatorname{T}A_G1_T=\left(\frac{|S|}n\mathbf 1\right)^\operatorname{T}A_G\left(\frac{|T|}n\mathbf 1\right)+\left(1_S-\frac{|S|}n\mathbf 1\right)^\operatorname{T}A_G\left(1_T-\frac{|T|}n\mathbf 1\right)</math>

because the other two terms of the expansion are zero. The first term is equal to <math>\frac{|S||T|}{n^2}\mathbf 1^\operatorname{T}A_G\mathbf 1=\frac dn|S||T|</math>, so we find that

<math>\left|e(S,T)-\frac dn|S||T|\right|

\leq\left|\left(1_S-\frac{|S|}n\mathbf 1\right)^\operatorname{T}A_G\left(1_T-\frac{|T|}n\mathbf 1\right)\right|</math>

We can bound the right hand side by <math>\lambda\left\|1_S-\frac{|S|}{|n|}\mathbf 1\right\|\left\|1_T-\frac{|T|}{|n|}\mathbf 1\right\| =\lambda\sqrt{|S||T|\left(1-\frac{|S|}n\right)\left(1-\frac{|T|}n\right)}</math> using the same methods as in the earlier proof.

Applications

The expander mixing lemma can be used to upper bound the size of an independent set within a graph. In particular, the size of an independent set in an <math>(n, d, \lambda)</math>-graph is at most <math>\lambda n/d.</math> This is proved by letting <math>T=S</math> in the statement above and using the fact that <math>e(S,S)=0.</math>

An additional consequence is that, if <math>G</math> is an <math>(n, d, \lambda)</math>-graph, then its chromatic number <math>\chi(G)</math> is at least <math>d/\lambda.</math> This is because, in a valid graph coloring, the set of vertices of a given color is an independent set. By the above fact, each independent set has size at most <math>\lambda n/d,</math> so at least <math>d/\lambda</math> such sets are needed to cover all of the vertices.

A second application of the expander mixing lemma is to provide an upper bound on the maximum possible size of an independent set within a polarity graph. Given a finite projective plane <math>\pi</math> with a polarity <math>\perp,</math> the polarity graph is a graph where the vertices are the points a of <math>\pi</math>, and vertices <math>x</math> and <math>y</math> are connected if and only if <math>x\in y^{\perp}.</math> In particular, if <math>\pi</math> has order <math>q,</math> then the expander mixing lemma can show that an independent set in the polarity graph can have size at most <math>q^{3/2} - q + 2q^{1/2} - 1,</math> a bound proved by Hobart and Williford.

Converse

Bilu and Linial showed that a converse holds as well: if a <math>d</math>-regular graph <math>G = (V, E)</math> satisfies that for any two subsets <math>S, T \subseteq V</math> with <math>S \cap T = \empty </math> we have

<math>\left|e(S, T) - \frac{d |S| |T|}{n}\right| \leq \lambda \sqrt{|S| |T|},</math>

then its second-largest (in absolute value) eigenvalue is bounded by <math>O(\lambda (1+\log(d/\lambda)))</math>.

Generalization to hypergraphs

Friedman and Widgerson proved the following generalization of the mixing lemma to hypergraphs.

Let <math>H</math> be a <math>k</math>-uniform hypergraph, i.e. a hypergraph in which every "edge" is a tuple of <math>k</math> vertices. For any choice of subsets <math>V_1, ..., V_k</math> of vertices,

<math>\left| |e(V_1,...,V_k)| - \frac{k!|E(H)|}{n^k}|V_1|...|V_k| \right| \le \lambda_2(H)\sqrt{|V_1|...|V_k|}.</math>

References

• Шаблон:Citation.
• F.C. Bussemaker, D.M. Cvetković, J.J. Seidel. Graphs related to exceptional root systems, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), volume 18 of Colloq. Math. Soc. János Bolyai (1978), 185-191.

• Шаблон:Cite thesis
• Шаблон:Citation.

• Шаблон:Citation.

• Шаблон:Citation.