Gauss-Bonnet Theorem for Graphs? - MathOverflow

Gauss-Bonnet Theorem for Graphs?

2010-05-28T12:49:53Z

One can define the Euler characteristic χ for a graph as the number of vertices minus the number of edges. Thus an n-cycle has χ = 0 and K₄ has χ = –2.
Is there an analog for the Gauss-Bonnet theorem for graphs, something akin to:
[total turn angle] + [enclosed curvature] = τ + ω = 2 π χ ?
Certainly if one embeds the graph on a manifold, then an interpretation is possible via Gauss-Bonnet on the manifold. But is there a more purely combinatorial interpretation?

Addendum. (27Nov11). A new paper on this topic just appeared on the arXiv: Oliver Knill (who answered below back in March), "A graph theoretical Gauss-Bonnet-Chern Theorem." arXiv:1111.5395v1. Here is Knill's first figure:

Answer by Benoît Kloeckner for Gauss-Bonnet Theorem for Graphs?

2010-05-28T13:39:39Z

One can do the following : given a graph with $n$ vertices and $m$ edges, define the scalar curvature of a vertex $x$ of valency $v(x)$ by $S(x)=2-v(x)$. Isolated and pendant vertices have positive scalar curvature, $S$ vanishes precisely on degree two vertices (wich are those one want to call flat), and is negative for higher degrees, reminiscent of the trees being $\mathrm{CAT}(-\infty)$.

Now $\sum_x S(x)=2n-\sum_x v(x)=2\chi$ is a Gauss-bonnet formula. It is very simple, but one does not expects much more from such local considerations.

I guess that to get a more subtle formula, one can try to add some geometric structure to the graph (for example, a length on each edge and an angle for each pair of adjacent edges, and maybe a circular ordering of the edges incident to each vertex).

Answer by Tony Huynh for Gauss-Bonnet Theorem for Graphs?

2010-05-28T16:27:13Z

There is indeed a version of Gauss-Bonnet for graphs $G$ embedded on a 2-manifold. Here, the combinatorial curvature at a vertex $x$ of $G$ is

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

where $f \sim v$ means that the face $f$ is incident to the vertex $x$.

This paper by Chen and Chen, then gives a Gauss-Bonnet formula for embedded infinite graphs with a finite number of accumulation points.

Answer by Oliver for Gauss-Bonnet Theorem for Graphs?

2011-03-25T12:17:16Z

There are different type of curvatures for graphs. In two dimensions its not the degree of the point which matters but the length of the circles at the point like in differential geometry. This is different from the degree if graphs with boundary are considered. The simplest curvature for two dimensional graphs (I defined the dimension for graphs in http://arxiv.org/abs/1009.2292). For the curvature K(x) = 6-|S(x)|, any two dimensional graph G has total curvature 6 chi(G). More interesting and subtle is a second order curvature 2|S1(x)|-|S2(x)| which is differential geometrically motivated because curvature is a second order difference notion. Gauss-Bonnet is now not true in general and it seems that some smoothness condition needs to be satisfied. It is true for all two dimensional graphs non-negative curvature and for graphs which are "smooth" enough in some sense which I still struggle to define. I myself got more interested in Gauss-Bonnet-Chern for n-dimensional graphs and have a result there. There is a natural Chern-Euler form on n-dimensional graphs those total sum is the Euler characteristic for an n-dimensional graph. This form is defined also in odd dimensions but seems to be zero (it is in 3 dimensions but I still struggle to verify this in higher dimensions). Note that all this is purely graph theoretical. No additional structure on the graph is necessary. No embedding in an ambient Euclidean space necessary for example. The inductive dimension as defined in the above mentioned paper (revised here: http://www.math.harvard.edu/~knill/graphgeometry/papers/1.pdf) is a natural way to define polyhedra and polytopes as graphs which become n-dimensional graphs after some truncation or stellation procedure. The inductive dimension for graphs looks similar to inductive dimension usually considered in topology but is utterly different. With the usual inductive dimension, any graph would be one dimensional.