[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki\/expander-mixing-lemma-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki\/expander-mixing-lemma-wikipedia\/","headline":"Expander mixing lemma – Wikipedia","name":"Expander mixing lemma – Wikipedia","description":"before-content-x4 The expander mixing lemma intuitively states that the edges of certain d{displaystyle d} after-content-x4 -regular graphs are evenly distributed","datePublished":"2022-01-21","dateModified":"2022-01-21","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/e85ff03cbe0c7341af6b982e47e9f90d235c66ab","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/e85ff03cbe0c7341af6b982e47e9f90d235c66ab","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki\/expander-mixing-lemma-wikipedia\/","wordCount":16717,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4The expander mixing lemma intuitively states that the edges of certain d{displaystyle d}       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets S{displaystyle S} and T{displaystyle T} is always close to the expected number of edges between them in a random        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4d{displaystyle d}-regular graph, namely dn|S||T|{displaystyle {frac {d}{n}}|S||T|}.Table of Contents       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4d-Regular Expander Graphs[edit]Statement[edit]Tighter Bound[edit]Biregular Graphs[edit]Proof of First Statement[edit]Proof Sketch of Tighter Bound[edit]Applications[edit]Converse[edit]Generalization to hypergraphs[edit]References[edit]d-Regular Expander Graphs[edit]Define an (n,d,\u03bb){displaystyle (n,d,lambda )}-graph to be a d{displaystyle d}-regular graph G{displaystyle G} on n{displaystyle n} vertices such that all of the eigenvalues of its adjacency matrix AG{displaystyle A_{G}} except one have absolute value at most \u03bb.{displaystyle lambda .} The d{displaystyle d}-regularity of the graph guarantees that its largest absolute value of an eigenvalue is d.{displaystyle d.} In fact, the all-1’s vector 1{displaystyle mathbf {1} } is an eigenvector of AG{displaystyle A_{G}} with eigenvalue d{displaystyle d}, and the eigenvalues of the adjacency matrix will never exceed the maximum degree of G{displaystyle G} in absolute value.If we fix d{displaystyle d} and \u03bb{displaystyle lambda } then (n,d,\u03bb){displaystyle (n,d,lambda )}-graphs form a family of expander graphs with a constant spectral gap.Statement[edit]Let G=(V,E){displaystyle G=(V,E)} be an (n,d,\u03bb){displaystyle (n,d,lambda )}-graph.  For any two subsets S,T\u2286V{displaystyle S,Tsubseteq V}, let e(S,T)=|{(x,y)\u2208S\u00d7T:xy\u2208E(G)}|{displaystyle e(S,T)=|{(x,y)in Stimes T:xyin E(G)}|} be the number of edges between S and T (counting edges contained in the intersection of S and T twice). Then|e(S,T)\u2212d|S||T|n|\u2264\u03bb|S||T|.{displaystyle left|e(S,T)-{frac {d|S||T|}{n}}right|leq lambda {sqrt {|S||T|}},.}Tighter Bound[edit]We can in fact show that|e(S,T)\u2212d|S||T|n|\u2264\u03bb|S||T|(1\u2212|S|\/n)(1\u2212|T|\/n){displaystyle left|e(S,T)-{frac {d|S||T|}{n}}right|leq lambda {sqrt {|S||T|(1-|S|\/n)(1-|T|\/n)}},}using similar techniques.[1]Biregular Graphs[edit]For biregular graphs, we have the following variation, where we take \u03bb{displaystyle lambda } to be the second largest eigenvalue.[2]Let G=(L,R,E){displaystyle G=(L,R,E)} be a bipartite graph such that every vertex in L{displaystyle L} is adjacent to dL{displaystyle d_{L}} vertices of R{displaystyle R} and every vertex in R{displaystyle R} is adjacent to dR{displaystyle d_{R}} vertices of L{displaystyle L}. Let S\u2286L,T\u2286R{displaystyle Ssubseteq L,Tsubseteq R} with |S|=\u03b1|L|{displaystyle |S|=alpha |L|} and |T|=\u03b2|R|{displaystyle |T|=beta |R|}. Let e(G)=|E(G)|{displaystyle e(G)=|E(G)|}. Then|e(S,T)e(G)\u2212\u03b1\u03b2|\u2264\u03bbdLdR\u03b1\u03b2(1\u2212\u03b1)(1\u2212\u03b2)\u2264\u03bbdLdR\u03b1\u03b2.{displaystyle left|{frac {e(S,T)}{e(G)}}-alpha beta right|leq {frac {lambda }{sqrt {d_{L}d_{R}}}}{sqrt {alpha beta (1-alpha )(1-beta )}}leq {frac {lambda }{sqrt {d_{L}d_{R}}}}{sqrt {alpha beta }},.}Note that dLdR{displaystyle {sqrt {d_{L}d_{R}}}} is the largest eigenvalue of G{displaystyle G}.Proof of First Statement[edit]Let AG{displaystyle A_{G}} be the adjacency matrix of G{displaystyle G} and let \u03bb1\u2265\u22ef\u2265\u03bbn{displaystyle lambda _{1}geq cdots geq lambda _{n}} be the eigenvalues of AG{displaystyle A_{G}} (these eigenvalues are real because AG{displaystyle A_{G}} is symmetric). We know that \u03bb1=d{displaystyle lambda _{1}=d} with corresponding eigenvector v1=1n1{displaystyle v_{1}={frac {1}{sqrt {n}}}mathbf {1} }, the normalization of the all-1’s vector. Define \u03bb=max{\u03bb22,\u2026,\u03bbn2}{displaystyle lambda ={sqrt {max{lambda _{2}^{2},dots ,lambda _{n}^{2}}}}} and note that max{\u03bb22,\u2026,\u03bbn2}\u2264\u03bb2\u2264\u03bb12=d2{displaystyle max{lambda _{2}^{2},dots ,lambda _{n}^{2}}leq lambda ^{2}leq lambda _{1}^{2}=d^{2}}. Because AG{displaystyle A_{G}} is symmetric, we can pick eigenvectors v2,\u2026,vn{displaystyle v_{2},ldots ,v_{n}} of AG{displaystyle A_{G}} corresponding to eigenvalues \u03bb2,\u2026,\u03bbn{displaystyle lambda _{2},ldots ,lambda _{n}} so that {v1,\u2026,vn}{displaystyle {v_{1},ldots ,v_{n}}} forms an orthonormal basis of Rn{displaystyle mathbf {R} ^{n}}.Let J{displaystyle J} be the n\u00d7n{displaystyle ntimes n} matrix of all 1’s. Note that v1{displaystyle v_{1}} is an eigenvector of J{displaystyle J} with eigenvalue n{displaystyle n} and each other vi{displaystyle v_{i}}, being perpendicular to v1=1{displaystyle v_{1}=mathbf {1} }, is an eigenvector of J{displaystyle J} with eigenvalue 0. For a vertex subset U\u2286V{displaystyle Usubseteq V}, let 1U{displaystyle 1_{U}} be the column vector with vth{displaystyle v^{text{th}}} coordinate equal to 1 if v\u2208U{displaystyle vin U} and 0 otherwise. Then,|e(S,T)\u2212dn|S||T||=|1ST(AG\u2212dnJ)1T|{displaystyle left|e(S,T)-{frac {d}{n}}|S||T|right|=left|1_{S}^{operatorname {T} }left(A_{G}-{frac {d}{n}}Jright)1_{T}right|}.Let M=AG\u2212dnJ{displaystyle M=A_{G}-{frac {d}{n}}J}. Because AG{displaystyle A_{G}} and J{displaystyle J} share eigenvectors, the eigenvalues of M{displaystyle M} are 0,\u03bb2,\u2026,\u03bbn{displaystyle 0,lambda _{2},ldots ,lambda _{n}}. By the Cauchy-Schwarz inequality, we have that |1STM1T|=|1S\u22c5M1T|\u2264\u20161S\u2016\u2016M1T\u2016{displaystyle |1_{S}^{operatorname {T} }M1_{T}|=|1_{S}cdot M1_{T}|leq |1_{S}||M1_{T}|}. Furthermore, because M{displaystyle M} is self-adjoint, we can write\u2016M1T\u20162=\u27e8M1T,M1T\u27e9=\u27e81T,M21T\u27e9=\u27e81T,\u2211i=1nM2\u27e81T,vi\u27e9vi\u27e9=\u2211i=2n\u03bbi2\u27e81T,vi\u27e92\u2264\u03bb2\u20161T\u20162{displaystyle |M1_{T}|^{2}=langle M1_{T},M1_{T}rangle =langle 1_{T},M^{2}1_{T}rangle =leftlangle 1_{T},sum _{i=1}^{n}M^{2}langle 1_{T},v_{i}rangle v_{i}rightrangle =sum _{i=2}^{n}lambda _{i}^{2}langle 1_{T},v_{i}rangle ^{2}leq lambda ^{2}|1_{T}|^{2}}.This implies that \u2016M1T\u2016\u2264\u03bb\u20161T\u2016{displaystyle |M1_{T}|leq lambda |1_{T}|} and |e(S,T)\u2212dn|S||T||\u2264\u03bb\u20161S\u2016\u20161T\u2016=\u03bb|S||T|{displaystyle left|e(S,T)-{frac {d}{n}}|S||T|right|leq lambda |1_{S}||1_{T}|=lambda {sqrt {|S||T|}}}.Proof Sketch of Tighter Bound[edit]To show the tighter bound above, we instead consider the vectors 1S\u2212|S|n1{displaystyle 1_{S}-{frac {|S|}{n}}mathbf {1} } and 1T\u2212|T|n1{displaystyle 1_{T}-{frac {|T|}{n}}mathbf {1} }, which are both perpendicular to v1{displaystyle v_{1}}. We can expand1STAG1T=(|S|n1)TAG(|T|n1)+(1S\u2212|S|n1)TAG(1T\u2212|T|n1){displaystyle 1_{S}^{operatorname {T} }A_{G}1_{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)}because the other two terms of the expansion are zero. The first term is equal to |S||T|n21TAG1=dn|S||T|{displaystyle {frac {|S||T|}{n^{2}}}mathbf {1} ^{operatorname {T} }A_{G}mathbf {1} ={frac {d}{n}}|S||T|}, so we find that|e(S,T)\u2212dn|S||T||\u2264|(1S\u2212|S|n1)TAG(1T\u2212|T|n1)|{displaystyle left|e(S,T)-{frac {d}{n}}|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|}We can bound the right hand side by \u03bb\u20161S\u2212|S||n|1\u2016\u20161T\u2212|T||n|1\u2016=\u03bb|S||T|(1\u2212|S|n)(1\u2212|T|n){displaystyle 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)}}} using the same methods as in the earlier proof.Applications[edit]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 (n,d,\u03bb){displaystyle (n,d,lambda )}-graph is at most \u03bbn\/d.{displaystyle lambda n\/d.} This is proved by letting T=S{displaystyle T=S} in the statement above and using the fact that e(S,S)=0.{displaystyle e(S,S)=0.}An additional consequence is that, if G{displaystyle G} is an (n,d,\u03bb){displaystyle (n,d,lambda )}-graph, then its chromatic number \u03c7(G){displaystyle chi (G)} is at least d\/\u03bb.{displaystyle d\/lambda .} 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 \u03bbn\/d,{displaystyle lambda n\/d,} so at least d\/\u03bb{displaystyle d\/lambda } 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 \u03c0{displaystyle pi } with a polarity \u22a5,{displaystyle perp ,} the polarity graph is a graph where the vertices are the points a of \u03c0{displaystyle pi }, and vertices x{displaystyle x} and y{displaystyle y} are connected if and only if x\u2208y\u22a5.{displaystyle xin y^{perp }.} In particular, if \u03c0{displaystyle pi } has order q,{displaystyle q,} then the expander mixing lemma can show that an independent set in the polarity graph can have size at most q3\/2\u2212q+2q1\/2\u22121,{displaystyle q^{3\/2}-q+2q^{1\/2}-1,} a bound proved by Hobart and Williford.Converse[edit]Bilu and Linial showed[3] that a converse holds as well: if a d{displaystyle d}-regular graph G=(V,E){displaystyle G=(V,E)} satisfies that for any two subsets S,T\u2286V{displaystyle S,Tsubseteq V} with S\u2229T=\u2205{displaystyle Scap T=emptyset } we have|e(S,T)\u2212d|S||T|n|\u2264\u03bb|S||T|,{displaystyle left|e(S,T)-{frac {d|S||T|}{n}}right|leq lambda {sqrt {|S||T|}},}then its second-largest (in absolute value) eigenvalue is bounded by O(\u03bb(1+log\u2061(d\/\u03bb))){displaystyle O(lambda (1+log(d\/lambda )))}.Generalization to hypergraphs[edit]Friedman and Widgerson proved the following generalization of the mixing lemma to hypergraphs.Let H{displaystyle H} be a k{displaystyle k}-uniform hypergraph, i.e. a hypergraph in which every “edge” is a tuple of k{displaystyle k} vertices. For any choice of subsets V1,...,Vk{displaystyle V_{1},…,V_{k}} of vertices,||e(V1,...,Vk)|\u2212k!|E(H)|nk|V1|...|Vk||\u2264\u03bb2(H)|V1|...|Vk|.{displaystyle left||e(V_{1},…,V_{k})|-{frac {k!|E(H)|}{n^{k}}}|V_{1}|…|V_{k}|right|leq lambda _{2}(H){sqrt {|V_{1}|…|V_{k}|}}.}References[edit]Alon, N.; Chung, F. R. K. (1988), “Explicit construction of linear sized tolerant networks”, Discrete Mathematics, 72 (1\u20133): 15\u201319, doi:10.1016\/0012-365X(88)90189-6.     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki\/expander-mixing-lemma-wikipedia\/#breadcrumbitem","name":"Expander mixing lemma – Wikipedia"}}]}]