Gráfico de expansión

---

En combinatoria , un gráfico de expansión es un gráfico disperso que tiene fuertes propiedades de conectividad , cuantificadas mediante la expansión de vértices , bordes o espectrales. Las construcciones de expansores han generado investigaciones en matemáticas puras y aplicadas, con varias aplicaciones a la teoría de la complejidad , el diseño de redes informáticas robustas y la teoría de los códigos de corrección de errores . ^[1]

Intuitivamente, un gráfico de expansión es un multigrafo no dirigido finito en el que cada subconjunto de vértices que no es "demasiado grande" tiene un límite "grande" . Las diferentes formalizaciones de estas nociones dan lugar a diferentes nociones de expansores: expansores de borde, expansores de vértices y expansores espectrales , como se define a continuación.

Un gráfico desconectado no es un expansor, ya que el límite de un componente conectado está vacío. Cada gráfico conexo es un expansor; sin embargo, diferentes gráficos conectados tienen diferentes parámetros de expansión. El gráfico completo tiene la mejor propiedad de expansión, pero tiene el mayor grado posible. Informalmente, un gráfico es un buen expansor si tiene parámetros de expansión altos y de bajo grado .

La expansión del borde (también número isoperimétrico o constante de Cheeger ) h ( G ) de un gráfico G en n vértices se define como

donde , que también se puede escribir como con el complemento de y las aristas entre los subconjuntos de vértices .${\displaystyle \parcial S:=\{\{u,v\}\in E(G)\ :\u\in S,v\in V(G)\setminus S\}}$${\displaystyle \parcial S=E(S,{\overline {S}})}$${\displaystyle {\overline {S}}:=V(G)\setminus S}$${\ estilo de visualización S}$${\displaystyle E(A,B)=\{\{u,v\}\en E(G)\ :\ u\en A,v\en B\}}$${\displaystyle A,B\subseteq V(G)}$

En la ecuación, el mínimo es sobre todos los conjuntos no vacíos S de como máximo n /2 vértices y ∂ S es el borde límite de S , es decir, el conjunto de bordes con exactamente un extremo en S . ^[2]

---