¿Teorema de Gauss-Bonnet para grafos?

Question

Se puede definir la característica de Euler de un grafo como el número de vértices menos el número de aristas. Por tanto, un $n$ -ciclo tiene $\chi = 0$ y $K_4$ tiene $\chi=-2$ . ¿Existe un análogo del teorema de Gauss-Bonnet para los grafos, algo parecido a:

     [ángulo de giro total] $+$ [curvatura cerrada] $= \tau + \omega = 2 \pi \chi$ ?

Ciertamente, si se incrusta el grafo en un colector, entonces es posible una interpretación a través de Gauss-Bonnet en el colector. Pero, ¿existe una interpretación más puramente combinatoria?

Anexo . ( 27 de noviembre de 2011 ). Un nuevo artículo sobre este tema acaba de aparecer en arXiv: Oliver Knill (que respondió más abajo en marzo), "A graph theoretical Gauss-Bonnet-Chern Theorem." arXiv:1111.5395v1 . Aquí está la primera cifra de Knill:
     

Answer 1

Se puede hacer lo siguiente: dado un gráfico con $n$ vértices y $m$ aristas, definir la curvatura escalar de un vértice $x$ de valencia $v(x)$ por $S(x)=2-v(x)$ . Los vértices aislados y colgantes tienen curvatura escalar positiva, $S$ desaparece precisamente en los vértices de grado dos (que son los que uno quiere llamar planos), y es negativo para grados superiores, lo que recuerda a los árboles que son $\mathrm{CAT}(-\infty)$ .

Ahora $\sum_x S(x)=2n-\sum_x v(x)=2\chi$ es una fórmula de Gauss-bonnet. Es muy simple, pero no se espera mucho más de tales consideraciones locales.

Supongo que para obtener una fórmula más sutil, se puede intentar añadir alguna estructura geométrica al grafo (por ejemplo, una longitud en cada arista y un ángulo para cada par de aristas adyacentes, y quizá un ordenamiento circular de las aristas incidentes en cada vértice).

Answer 2

Existe una versión de Gauss-Bonnet para grafos $G$ incrustado en un 2-manifold. Aquí, el curvatura combinatoria en un vértice $x$ de $G$ est

$1-\frac{deg(x)}{2} + \sum_{f \sim v} \frac{1}{size(f)}$ ,

donde $f \sim v$ significa que la cara $f$ es incidente al vértice $x$ .

Este papel de Chen y Chen, luego da una fórmula de Gauss-Bonnet para grafos infinitos embebidos con un número finito de puntos de acumulación.

Answer 3

Existen diferentes tipos de curvaturas para los gráficos. En dos dimensiones no es el grado del punto lo que importa, sino sino la longitud de los círculos en el punto, como en geometría diferencial. Esto es diferente del grado si se consideran grafos con límites. La curvatura más simple para grafos bidimensionales (Definí la dimensión para grafos en http://arxiv.org/abs/1009.2292 ). Para la curvatura K(x) = 6-|S(x)|, cualquier grafo bidimensional G tiene una curvatura total 6 chi(G). Más interesante y sutil es una curvatura de segundo orden 2|S1(x)|-|S2(x)| que tiene una motivación geométrica diferencial porque la curvatura es una noción de diferencia de segundo orden. noción de diferencia de segundo orden. Ahora Gauss-Bonnet no es cierto en general y parece que debe cumplirse alguna condición de suavidad. En es cierta para todos los grafos bidimensionales de curvatura no negativa y para los grafos que son lo suficientemente "suaves" en algún sentido que aún me cuesta definir. Yo mismo me interesé más por Gauss-Bonnet-Chern para grafos n-dimensionales y allí tengo un resultado. Hay una forma natural de Chern-Euler en grafos n-dimensionales cuya suma total es la característica de Euler para un grafo n-dimensional. Esta forma está definida también en dimensiones Impares pero parece ser cero (lo es en 3 dimensiones pero todavía me cuesta verificarlo en dimensiones superiores). Nótese que todo esto es puramente teoría de grafos. Ninguna estructura adicional en en el grafo. No hay incrustación en un espacio euclidiano ambiente por ejemplo. La dimensión inductiva, tal como se define en el documento antes mencionado (revisado aquí: http://www.math.harvard.edu/~knill/graphgeometry/papers/1.pdf ) es una forma natural de definir poliedros y politopos como grafos que se convierten en grafos n-dimensionales después de algún procedimiento de truncamiento o estelación. La dimensión inductiva de los grafos se parece a la dimensión inductiva que se suele considerar en topología, pero es completamente distinta. Con la dimensión inductiva habitual, cualquier grafo sería unidimensional.