Lema de mezcla de expansor

---

El lema de mezcla del expansor indica intuitivamente que los bordes de ciertos gráficos regulares se distribuyen uniformemente a lo largo del gráfico. En particular, el número de aristas entre dos subconjuntos de vértices y es siempre cerca del número esperado de bordes entre ellos en un aleatorio - grafo regular , a saber .${\ Displaystyle d}$${\ Displaystyle S}$${\ Displaystyle T}$ ${\ Displaystyle d}$${\ Displaystyle {\ frac {d} {n}} | S || T |}$

Definir una -graph ser un gráfico -regular en vértices de tal manera que todos los valores propios de su matriz de adyacencia , excepto uno, tienen un valor absoluto en la mayoría El -regularity de las garantías gráfico que su mayor valor absoluto de un valor propio es De hecho, el todo El vector de -1 es un vector propio de con valor propio , y los valores propios de la matriz de adyacencia nunca excederán el grado máximo de en valor absoluto.${\ Displaystyle (n, d, \ lambda)}$${\ Displaystyle d}$${\ Displaystyle G}$${\ Displaystyle n}$${\ Displaystyle A_ {G}}$${\ Displaystyle \ lambda.}$${\ Displaystyle d}$${\ Displaystyle d.}$${\ Displaystyle \ mathbf {1}}$${\ Displaystyle A_ {G}}$${\ Displaystyle d}$${\ Displaystyle G}$

Si arreglamos y luego, los gráficos forman una familia de gráficos expansores con una brecha espectral constante .${\ Displaystyle d}$${\ Displaystyle \ lambda}$${\ Displaystyle (n, d, \ lambda)}$

Sea un gráfico. Para dos subconjuntos cualesquiera , sea ​​el número de bordes entre S y T (contando los bordes contenidos en la intersección de S y T dos veces). Entonces${\ Displaystyle G = (V, E)}$${\ Displaystyle (n, d, \ lambda)}$${\ Displaystyle S, T \ subseteq V}$${\ Displaystyle e (S, T) = | \ {(x, y) \ in S \ times T: xy \ in E (G) \} |}$

---