News about this project

[January 6, 2013] The The McKean-Singer Formula in Graph Theory [PDF] [ArXiv]. This paper deals with the Dirac operator D on general finite simple graphs G. It is a matrix associated with G and contains geometric information. The square L=D² is a block matrix, where each block is the Laplacian on p-forms. The McKean-Singer formula telling that str(exp(-t L) is the Euler characteristic for all t reflects a symmetry. It has combinatorial consequences for counting paths in the simplex space. It also helped to construct graphs which are Dirac isospectral. The matrix is also valuable for doing computations in geometry. Already Poincare has used it in 1900. Today, one can with a dozen lines of computer algebra system code produce the cohomology groups for any graph. The Dirac operator also allows to to see the graph theoretical Gauss-Bonnet-Chern theorem as an example of a discrete index theorem.
[November 4, 2012] The Lusternik-Schnirelmann theorem for graphs [ArXiv]. With Frank Josellis, we prove cup(G) ≤ tcat(G) ≤ crit(G) for a general finite simple graph G where cup(G) is the cup length, tcat(G) is the minimal number of in G contractible subgraphs covering G and crit(G) is the minimal number of critical points an injective function can have on G. This implies cup(G) ≤ cat(G) ≤ cri(G) for a general finite simple graph G, where cat(G) is the minimum over all tcat(H) with H homotopic to G and cri(G) is the minimal crit(H) for an graph H homotopic to G. The Lusternik-Schnirelmann theorem links an algebraic invariant (cup) with a topological invariant (cup) and an analytic invariant (cri). [Update Nov 13, 2012: The original cat was renamed topological category tcat(G) since it is - similarly than the geometric category gcat(G) - not yet a homotopy invariant. (While the Fox graph is an example with gcat(G)=3, tcat(G)=cat(G)=2, the dunce hat G is homotopic to a point and satisfies cat(G)=1 but tcat(G)=2 because it is not contractible).
[June 4, 2012:] A fixed point theorem for graphs [ArXiv, June 4, 2012] proves a general Lefschetz formula for graph endomorphisms, leading to fixed point results like a discrete Brouwer theorem which generalizes the edge theorem of Nowakowski-Rival. Unlike in the continuum, we have to look at simplices as the basic "points". With the right notion of "degree" of a simplex with respect to T, the proof is pretty close to Hopfs proof in the classical case, which essentially boils down to "circular graphs have Euler characteristic 0" and "fixed points have Euler characteristic 1" and "every attractor of an endomorphism is either a circular graph or fixed point". The paper also gives a formula for the zeta function of T which involves the signature and dimension of prime simplex orbits.
[May 1, 2012:] A continuation shows that curvature K(x) is zero for odd dimensional geometric graphs. This is proven by showing that the symmetric index j(f,x) = [i(f,x) + i(-f,x)]/2 is constant zero for odd dimensional geometric graphs, a result which holds for odd dimensional Riemannian manifolds. In the discrete, we need to define level surfaces B(f,x) = { f=c } in unit spheres S(x). We show that each B(f,x) is a polytop which can be completed to become geometric. For general simple graphs, the symmetric index j(f,x) satisfies j(f,x) = [2-chi(S(x))-chi(B(x))]/2 (a formula which also holds in the manifold case). For odd dimensional graphs in particular, j(f,x) = -chi(B(f,x))/2 which is zero by Poincaré-Hopf and induction. Curvature K(x) as the expectation E[j(f,x)] over a probability space of scalar functions f is therefore zero too.
[Feb 20, 2012:] This paper brings in some probability theory. It will be used to show that curvature for odd dimensional geometric graphs is constant zero: if we integrate over all Morse functions on a graph and average the indices, we get curvature. Since each individual index function adds up to Euler characteristic, simply taking expectation over all fields gives Gauss-Bonnet. While this does not simplify the proof of Gauss-Bonnet in the discrete, it most likely will simplify Gauss-Bonnet-Chern for Riemannian manifolds.
[Jan 31, 2012:] Wolfram Demo of Dimension and Euler characteristic and Wolfram Demo of GaussBonnetPoincareHopf.
[Jan 29, 2012:] An expository paper [PDF] which might be extended more in the future. It deals with Gauss-Bonnet, Poincare-Hopf and Green Stokes in a graph theoretical setting.
[Jan 4, 2012:] A discrete analogue of Poincare-Hopf for a general simple graphs G. Computer experimentation were essential to try different approaches, starting with small dimensions and guided by the continuum to find the index which works for random graphs. Discretisation would have been difficult because the index is classically defined as the degree of a sphere map (needing algebraic topology to be understood properly) and the analogue of spheres in graph theory can be pretty arbitrary graphs. Even with a computer, it needed months of experimentation. Morse theory is relief also in the continuum.
[Dec 19, 2011:] A paper on the dimension and Euler characteristic of random graphs provides explicit formulas for the expectation of inductive dimension dim(G) or Euler characteristic X(G), which are considered random variables over Erdoes-Renyi probability spaces. Most results were found first experimentally using brute force computations before proving them. The paper belongs to the mathematics of complex networks. Dimension and Euler characteristic mixes in some geometry.
[Nov 21 2011:] A paper on higher dimensional Gauss-Bonnet which fits the occasion of Chern's birthday of October 26, 1911, The result was obtained in the summer of 2009 but illustrating it with examples took time. One can define curvature K(x) which depends only on the unit sphere of a vertex x in a graph G=(V,E) such that the sum of K(x) over V is Euler characteristic X(G). To see this implemented in Mathematica visit the code page.
[Jul 6, 2010] This project started in spring 2009. The subject is simple topology or discrete differential geometry. A paper. The goal is to understand graphs on a geometric level and investigate discrete analogues of structures which are known in differential geometry. This website is up since July 2010.