Gauss-Bonnet Theorem for Graphs? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T22:07:06Z http://mathoverflow.net/feeds/question/26256 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/26256/gauss-bonnet-theorem-for-graphs Gauss-Bonnet Theorem for Graphs? Joseph O'Rourke 2010-05-28T12:49:53Z 2011-11-28T01:41:28Z <p>One can define the Euler characteristic &chi; for a graph as the number of vertices minus the number of edges. Thus an <em>n</em>-cycle has &chi; = 0 and <em>K</em><sub>4</sub> has &chi; = &ndash;2.<br> Is there an analog for the Gauss-Bonnet theorem for graphs, something akin to:<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[total turn angle] + [enclosed curvature] = &tau; + &omega; = 2 &pi; &chi; ?<br> 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?</p> <p><b>Addendum</b>. (<em>27Nov11</em>). 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." <a href="http://arxiv.org/abs/1111.5395" rel="nofollow">arXiv:1111.5395v1</a>. Here is Knill's first figure: <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/KnillFig1.jpg" alt="Knill Fig 1"></p> http://mathoverflow.net/questions/26256/gauss-bonnet-theorem-for-graphs/26264#26264 Answer by Benoît Kloeckner for Gauss-Bonnet Theorem for Graphs? Benoît Kloeckner 2010-05-28T13:39:39Z 2010-05-28T13:39:39Z <p>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)$.</p> <p>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.</p> <p>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).</p> http://mathoverflow.net/questions/26256/gauss-bonnet-theorem-for-graphs/26281#26281 Answer by Tony Huynh for Gauss-Bonnet Theorem for Graphs? Tony Huynh 2010-05-28T16:27:13Z 2010-05-28T16:27:13Z <p>There is indeed a version of Gauss-Bonnet for graphs $G$ embedded on a 2-manifold. Here, the <em>combinatorial curvature</em> at a vertex $x$ of $G$ is</p> <p>$1-\frac{deg(x)}{2} + \sum_{f \sim v} \frac{1}{size(f)}$,</p> <p>where $f \sim v$ means that the face $f$ is incident to the vertex $x$. </p> <p>This <a href="http://www.math.ust.hk/~mabfchen/Paper/Gauss-Bonnet.pdf" rel="nofollow">paper</a> by Chen and Chen, then gives a Gauss-Bonnet formula for embedded infinite graphs with a finite number of accumulation points.</p> http://mathoverflow.net/questions/26256/gauss-bonnet-theorem-for-graphs/59551#59551 Answer by Oliver for Gauss-Bonnet Theorem for Graphs? Oliver 2011-03-25T12:17:16Z 2011-03-25T12:17:16Z <p>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 <a href="http://arxiv.org/abs/1009.2292" rel="nofollow">http://arxiv.org/abs/1009.2292</a>). 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: <a href="http://www.math.harvard.edu/~knill/graphgeometry/papers/1.pdf" rel="nofollow">http://www.math.harvard.edu/~knill/graphgeometry/papers/1.pdf</a>) 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.</p>