Constante de Cheeger (teoría de grafos)

En matemáticas , la constante de Cheeger (también número de Cheeger o número isoperimétrico ) de un gráfico es una característica numérica de un gráfico que refleja si el gráfico tiene un "cuello de botella" o no. La constante de Cheeger como una forma de medir la presencia de un "cuello de botella" es de interés en muchas áreas, por ejemplo, para crear redes informáticas altamente conectadas , para barajar cartas y en topología de baja dimensión (en particular, en el estudio de hiperbólicos ). Variedades tridimensionales [1] ). Nombrado en honor al matemático Jeff Cheeger .

Definición

Sea un grafo no dirigido con un conjunto de vértices y arcos . Sea un conjunto de vértices el conjunto de todos los arcos que conectan los vértices del conjunto con los vértices que no pertenecen a [2] : $GRAMO$ ${\ estilo de visualización V (G)}$ ${\ estilo de visualización E (G)}$ $A\subseteq V(G)$ $\parcial A$ $A$ $A$

\parcial A:=\{(x,y)\in E(G)\mid x\in A,y\in V(G)\setminus A\}.

Recuerda que los arcos no están dirigidos, por lo que el arco es el mismo arco que . $(x, y)$ $(y, x)$

Entonces , la constante de Cheeger del gráfico (indicada como ) se define como $GRAMO$ $h(G)$

h(G):=\min \left\{\left.{\frac {|\parcial A|}{|A|}}\right|A\subseteq V(G),0<|A| \leqslant {\frac {|V(G)|}{2}}\right\}.

La constante de Cheeger es estrictamente positiva si y solo si la gráfica es conexa . Es intuitivamente claro que si la constante de Cheeger es pequeña pero positiva, hay un "cuello de botella" en el gráfico, en el sentido de que hay dos conjuntos "grandes" de vértices con un número "pequeño" de enlaces (arcos) entre ellos. La constante de Cheeger es "grande" si cualquier división de un conjunto de vértices en dos subconjuntos deja un número "grande" de conexiones entre estos subconjuntos. $GRAMO$

Ejemplo: red informática

Imagine que necesita desarrollar una configuración de red en la que la constante Cheeger sea grande (al menos significativamente diferente de cero), incluso si | V ( G )| (la cantidad de computadoras en la red) es grande.

Por ejemplo, hay N ≥ 3 computadoras unidas en un anillo , formando un grafo G N. Numeremos las computadoras con los números 1, 2, ..., N en el anillo en el sentido de las agujas del reloj. Desde un punto de vista matemático, hay un gráfico con muchos vértices

V(G_{N}):=\{1,2,\puntos,N\}

y muchos arcos

E(G_{N}):=\{(1,2),(2,3),\dots ,(N-1,N),(N,1)\}.

Tomemos estas computadoras en la cadena como el conjunto A : $\lpiso N/2\rpiso$

A:=\{1,2,\dots ,\lpiso N/2\rpiso \}.

Está claro que

\parcial A=\{(\lpiso N/2\rpiso,\lpiso N/2\rpiso +1),(N,1)\},

asi que

{\frac {|\parcial A|}{|A|}}={\frac {2}{\lpiso N/2\rpiso}}\a 0

N\to \infty .

Este ejemplo muestra un límite superior en la constante de Cheeger h ( G N ), y tiende a cero cuando N tiende a infinito. Por lo tanto, podemos considerar una red de computadoras conectadas en un anillo como consistente en "cuellos de botella" continuos para N grande , y esto es comprensible en un sentido práctico. Tan pronto como falle una computadora en el anillo, la tasa de cambio caerá bruscamente. Si fallan dos computadoras desconectadas, la red se dividirá en dos partes desconectadas.

Desigualdad de Cheeger

La constante de Cheeger es particularmente importante en el contexto de los gráficos de expansión , ya que sirve como una medida de cómo sus arcos cubren un gráfico. La llamada desigualdad de Cheeger está relacionada con la brecha espectral y contiene la constante de Cheeger.

Véase también

Notas

↑ Lackenby, 2010 , §7 El comportamiento de los invariantes geométricos y topológicos en cubiertas finitas, p. 13
↑ Lubotzky, 2011 , Capítulo 1. Gráficos de expansión. 1.1 Definiciones básicas. P.5.

Literatura

Donetti, L., Neri, F. y Muñoz, M. Topologías de redes óptimas: expansores, jaulas, grafos de Ramanujan, redes entrelazadas y todo eso // J. Stat. mecánico - 2006. - T. 2006 , nº. 08 . -doi : 10.1088 / 1742-5468/2006/08/P08007 .
Lackenby, M. Heegaard splittings, la conjetura virtual de Haken y la propiedad (τ) // Invent. Matemáticas. - 2006. - T. 164 , núm. 2 . - S. 317-359 . -doi : 10.1007 / s00222-005-0480-x .
Marcos Lackenby. Espacios de cobertura finitos de 3 variedades // Actas del Congreso Internacional de Matemáticos. Hyderabad, India. — 2010.
Alejandro Lubotzky. Expander Graphs in Pure and Applied Mathematics // Este documento se basa en notas preparadas para las conferencias del coloquio en la reunión anual conjunta de la American Mathematical Society (AMS) y la Mathematical Association of America (MAA). — 2011.