Expander Mixing lemma Induced edges:E(S,T)={(u,v):u∈S,v∈T,uv∈E} 在这个定义中我们也允许相交的s,T,此时交集中的每条边会被计算两次. Expander Mixing lemma 设G为n个顶点的d-正则图，其谱半径为a,则对任意ssml,Tsm, Es,7刀-Sr ≤a√1SlTT Proof:注意到E(ST)=径AXr.令Xs=L:a,x=:b,其中，为邻接矩阵A的一组正交 正规特征基，对应特征值a}. E(S,T)= aiaibi. 由Cauchy--Schwarz, 6,)- s allall2lbll2 allxsll2llxT2 avISIIT n Expander Mixing lemma Induced edges: � �, � ≔ { �, � : � ∈ �, � ∈ �, �� ∈ �} 在这个定义中我们也允许相交的�, �, 此时交集中的每条边会被计算两次. Expander Mixing lemma 设G为n个顶点的d-正则图，其谱半径为�，则对任意� ⊆ � , � ⊆ [�], � �, � − � � � � ≤ � � � . Proof: 注意到� �, � = �7 ,��,. 令 �' = ∑( �(�( , �# = ∑( �(�(, 其中 {�(} 为邻接矩阵�的一组正交 正规特征基, 对应特征值{�(}. � �, � = � � � � + ( .8* �.�.�. . 由Cauchy-Schwarz, � �, � − � � � � ≤ � � * � * = � �7 * �, * = � � �