Constante de Cheeger (teoría de grafos)

Medida de si un gráfico tiene o no un "cuello de botella"

En matemáticas , la constante de Cheeger (también número de Cheeger o número isoperimétrico ) de un grafo es una medida numérica de si un grafo tiene o no un "cuello de botella". La constante de Cheeger como medida de "cuello de botella" es de gran interés en muchas áreas: por ejemplo, la construcción de redes de computadoras bien conectadas , el barajado de cartas . La noción teórica de grafos se originó después de la constante isoperimétrica de Cheeger de una variedad compacta de Riemann .

La constante de Cheeger debe su nombre al matemático Jeff Cheeger .

Definición

Sea G un grafo finito no dirigido con un conjunto de vértices V ( G ) y un conjunto de aristas E ( G ) . Para una colección de vértices A ⊆ V ( G ) , sea ∂ A la colección de todas las aristas que van desde un vértice en A hasta un vértice fuera de A (a veces llamado el límite de aristas de A ):

${\displaystyle \partial A:=\{\{x,y\}\in E(G)\ :\ x\in A,y\in V(G)\setminus A\}.}$

Nótese que los bordes no están ordenados, es decir, . La constante de Cheeger de G , denotada h ( G ) , está definida por ^[1] ${\displaystyle \{x,y\}=\{y,x\}}$

${\displaystyle h(G):=\min \left\{{\frac {|\partial A|}{|A|}}\ :\ A\subseteq V(G),0<|A|\leq {\tfrac {1}{2}}|V(G)|\right\}.}$

La constante de Cheeger es estrictamente positiva si y solo si G es un grafo conexo . Intuitivamente, si la constante de Cheeger es pequeña pero positiva, entonces existe un "cuello de botella", en el sentido de que hay dos conjuntos "grandes" de vértices con "pocos" vínculos (aristas) entre ellos. La constante de Cheeger es "grande" si cualquier posible división del conjunto de vértices en dos subconjuntos tiene "muchos" vínculos entre esos dos subconjuntos.

Ejemplo: redes de computadoras

Disposición de la red en anillo

En aplicaciones a la informática teórica, se desea diseñar configuraciones de red para las cuales la constante de Cheeger sea alta (al menos, acotada desde cero) incluso cuando | V ( G )| (la cantidad de computadoras en la red) sea grande.

Por ejemplo, considere una red en anillo de N ≥ 3 computadoras, pensada como un grafo G _N . Numere las computadoras 1, 2, ..., N en el sentido de las agujas del reloj alrededor del anillo. Matemáticamente, el conjunto de vértices y el conjunto de aristas están dados por:

${\displaystyle {\begin{aligned}V(G_{N})&=\{1,2,\cdots ,N-1,N\}\\E(G_{N})&={\big \{}\{1,2\},\{2,3\},\cdots ,\{N-1,N\},\{N,1\}{\big \}}\end{aligned}}}$

Considere A como una colección de estas computadoras en una cadena conectada: ${\displaystyle \left\lfloor {\tfrac {N}{2}}\right\rfloor }$

${\displaystyle A=\left\{1,2,\cdots ,\left\lfloor {\tfrac {N}{2}}\right\rfloor \right\}.}$

Entonces,

${\displaystyle \partial A=\left\{\left\{\left\lfloor {\tfrac {N}{2}}\right\rfloor ,\left\lfloor {\tfrac {N}{2}}\right\rfloor +1\right\},\{N,1\}\right\},}$

y

${\displaystyle {\frac {|\partial A|}{|A|}}={\frac {2}{\left\lfloor {\tfrac {N}{2}}\right\rfloor }}\to 0{\mbox{ as }}N\to \infty .}$

Este ejemplo proporciona un límite superior para la constante de Cheeger h ( G _N ) , que también tiende a cero cuando N → ∞ . En consecuencia, consideraríamos que una red en anillo tiene un alto grado de "cuello de botella" para valores grandes de N , y esto es altamente indeseable en términos prácticos. Solo necesitaríamos que una de las computadoras en el anillo falle, y el rendimiento de la red se reduciría considerablemente. Si dos computadoras no adyacentes fallaran, la red se dividiría en dos componentes desconectados.

Desigualdades de Cheeger

La constante de Cheeger es especialmente importante en el contexto de los grafos expansores, ya que es una forma de medir la expansión de los bordes de un grafo. Las denominadas desigualdades de Cheeger relacionan la brecha de valores propios de un grafo con su constante de Cheeger. Más explícitamente

${\displaystyle 2h(G)\geq \lambda \geq {\frac {h^{2}(G)}{2\Delta (G)}}}$

donde es el grado máximo de los nodos en y es la brecha espectral de la matriz laplaciana del grafo. ^[2] La desigualdad de Cheeger es un resultado fundamental y una motivación para la teoría de grafos espectrales . ${\displaystyle \Delta (G)}$ ${\displaystyle G}$ ${\displaystyle \lambda }$

Véase también

• Teoría de grafos espectrales
• Conectividad algebraica
• Cheeger con destino
• Conductancia
• Conectividad
• Gráfico expansor

Notas

1. Mohar 1989, págs. 274–291.
2. Montenegro y Tetali 2006, págs. 237–354.

Referencias

• Mohar, Bojan (1989). "Números isoperimétricos de grafos". Journal of Combinatorial Theory, Serie B . 47 (3): 274–291. doi : 10.1016/0095-8956(89)90029-4 .
• Montenegro, Ravi; Tetali, Prasad (2006). "Aspectos matemáticos de los tiempos de mezcla en cadenas de Markov". Fundamentos y tendencias en informática teórica . 1 (3): 237–354. doi :10.1561/0400000003. ISSN  1551-305X.
• Donetti, Luca; Neri, Franco; Muñoz, Miguel A (2006-08-07). "Topologías de red óptimas: expansores, jaulas, grafos de Ramanujan, redes enredadas y todo eso". Journal of Statistical Mechanics: Theory and Experiment . 2006 (08): P08007–P08007. arXiv : cond-mat/0605565 . Bibcode :2006JSMTE..08..007D. doi :10.1088/1742-5468/2006/08/P08007. ISSN  1742-5468. S2CID  16192273.
• Lackenby, Marc (2006). "Desdoblamientos de Heegaard, la conjetura virtualmente de Haken y la propiedad (τ)". Inventiones mathematicae . 164 (2): 317–359. arXiv : math/0205327 . Bibcode :2006InMat.164..317L. doi :10.1007/s00222-005-0480-x. ISSN  0020-9910. S2CID  12847770.