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 gráfico es una medida numérica de si un gráfico 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, en la construcción de redes de ordenadores bien conectadas , en el barajado de cartas . La noción teórica de grafos se originó a partir de la constante isoperimétrica de Cheeger de una variedad riemanniana compacta .

La constante de Cheeger lleva el nombre del matemático Jeff Cheeger .

Definición

Sea G un gráfico 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 límite de arista de A ):

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

Tenga en cuenta que los bordes están desordenados, 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 sólo si G es un gráfico 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" enlaces (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

Diseño de 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) es grande.

Por ejemplo, considere una red en anillo de N ≥ 3 computadoras, considerada como un gráfico 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 vienen 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}}}$

Tome 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 "cuello de botella" para N grande , y esto es muy indeseable en términos prácticos. Sólo necesitaríamos que fallara uno de los ordenadores del anillo, 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 gráficos de expansión , ya que es una forma de medir la expansión de los bordes de un gráfico. Las llamadas desigualdades de Cheeger relacionan la brecha de valores propios de un gráfico con su constante de Cheeger. Más explícitamente

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

en el cual es el grado máximo para los nodos en y es el espacio espectral de la matriz laplaciana del gráfico. ^[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 }$

Ver también

• Teoría de grafos espectrales
• Conectividad algebraica
• Atado a Cheeger
• Conductancia (gráfico)
• Conectividad (teoría de grafos)
• Gráfico de expansión

Referencias

1. Mohar, Bojan (diciembre de 1989). "Números isoperimétricos de gráficos". Revista de teoría combinatoria, serie B. 47 (3): 274–291. doi :10.1016/0095-8956(89)90029-4. hdl : 10338.dmlcz/128408 .
2. Montenegro, Ravi; Tetali, Prasad (2006). "Aspectos matemáticos de los tiempos de mezcla en cadenas de Markov". Encontró. Teoría de las tendencias. Computadora. Ciencia . 1 (3): 237–354. CiteSeerX 10.1.1.638.5846 . doi :10.1561/0400000003. ISBN  9781933019772.

• Donetti, L.; Neri, F. y Muñoz, M. (2006). "Topologías de red óptimas: expansores, jaulas, gráficos de Ramanujan, redes entrelazadas y todo eso". J. estadística. Mec . 2006 (8): P08007. arXiv : cond-mat/0605565 . Código Bib : 2006JSMTE..08..007D. doi :10.1088/1742-5468/2006/08/P08007. S2CID  16192273.
• Lackenby, M. (2006). "Escisiones de Heegaard, la conjetura y propiedad virtualmente de Haken (τ)". Inventar. Matemáticas . 164 (2): 317–359. arXiv : matemáticas/0205327 . Código Bib : 2006 InMat.164..317L. doi :10.1007/s00222-005-0480-x. S2CID  12847770.