# News about this project

- [August 23, 2015] A Sard theorem for Graph Theory: , with a miniblog for updates. How to we define level surfaces, discrete algebraic sets in graph theory? How large is the set of critical values? What is the second derivative test or how does one do Lagrange extremization in a network? Things go pretty much in the same way as in the continuum, but there are some twists. Local copy.
- [August 9, 2015] The graph spectrum of barycentric refinements:
See a miniblog with code and updates.
The graph spectra of Barycentric refinements G
_{m}of a finite simple graph show a remarkable universality: the graph spectra converge to a distribution which only depends on the maximal dimension of a complete subgraph. For graphs without triangles, the distribution is related to the smooth equilibrium measure of the Julia set of the quadratic map z^{2}-2. In higher dimension, the universal distributions are unidentified, but appears to be non-smooth with discrete or singular continuous components. Local copy. - [July 25, 2015] Some pictures of eigenfunctions: A gallery of pictures.
- [June 21, 2015] The Jordan-Brouwer theorem for graphs. The theme is well suited to test definitions and geometric notions. We prove a general Jordan-Brouer-Schoenflies separation theorem for knots of codimension one. The inductive definition of spheres (as we found out during this research put forward already by Alexander Evako) works very well. The proof would not have been possible without the tool of the graph product found earlier. (Local copy).
- [May 27, 2015] Kuenneth formula in graph theory. Having stumbled over new product for finite graphs, we introduce de Rham cohomology for general finite simple graphs graphs, show a discrete de Rham theorem, prove the Kuenneth formula and Eilenberg-Zilber theorem and prove that the dimension is super additive dim(G x H) >= dim(G) + dim(H) like Hausdorff dimension in the continuum. Products GxH have explicitly computable chromatic numbers, and if G,H are geometric, then G x H is geometric and even Eulerian. The product allows to define joins, new notions of homotopy, discrete manifolds or fibre bundles. (local copy). Updates.
- [Feb 1, 2015] Some diary notes on the miniblog.
Theoretical obstacles seem gone. The problem is to implement the procedure and see it work.
- [Jan 11,2015] "Graphs with Eulerian Unit spheres" is written in the context of coloring problems but addresses the fundamental question "what are lines and spheres" in graph theory. We define d-spheres inductively as homotopy spheres for which each unit sphere is a (d-1) sphere. In order to define lines in a graph, we need a unique geodesic flow. Because such a flow requires a fixed point free involution on each unit sphere, we restrict to the subclass of Eulerian graphs. Such graphs with Eulerian unit spheres are the topic of this paper. Eulerian spheres are very exciting since if we could extend a general 2-sphere to an Eulerian 3-sphere, it would prove the 4-color theorem. The paper also gives a short independent classification of all Platonic solids in d-dimensions, which only uses Gauss-Bonnet-Chern: these are d-spheres for which all unit spheres are (d-1)-dimensional Platonic solids. (local copy)
- [Dec 21,2014] Coloring graphs using topology. A geometric approach to graph coloring. We hope it could be a path towards ``seeing why the four color theorem is true". The idea is to embed the graph in a higher dimensional graph and made 4 colorable by cutting it up. It works in examples but not yet systematically. (local copy, containing updates), mini blog, some illustration.
- [Oct 12,2014] We looked at various variational problems and especially Characteristic Length and Clustering [ArXiv]. (local copy) and [update log] We see more indications that Euler characteristic is the most interesting functional and see correlations between dimension and length-cluster coefficient. A tiny mathematical lemma proven expresses clustering coefficient with a relative characteristic length allowing to look at clustering and length-cluster coefficient in general metric spaces.
- [Oct 5, 2014] Curvature from Graph Colorings and (Local copy). This is an extension of the Index expectation theorem but with a much smaller probability space: the set of colorings. It uses the remark that the discrete Poincaré-Hopf theorem holds also for locally injective functions aka colorings. Averaging over all colorings gives curvature. The topic mixes chromatic graph theory, integral geometry and is motivated by results known in differential geometry (like the Fary-Milnor theorem of 1950 which writes total curvature of a knot as an index expectation) and is elementary.
- Link to Binet article
- [July, 2014:] A summer HCRP project with Jenny Nitishinskaya on graph coloring problems
seen from a differential geometric and topological point of view.
A summary report [PDF].
It has been turbulent as we were in uncharted territory.
We conjecture that 4 colors suffice, as for any orientable surface like sphere or torus.
(note that we look for graphs where every unit sphere
is a cyclic graph, disqualifying the K
_{7}example, which is 6 dimensional for us). We also believe that chromatic number 5 is maximal for surfaces (attained only for nonorientable surfaces like the projective plane (an example found by Jenny)). [Dec. 2014/Jan. 2015 updates there are examples due to Fisk showing that the chromatic number 5 can occur for tori. It really seems to matter that the complement of a torus in a 3 sphere is not simply connected. There is evidence that the chromatic number of any surface is 3,4 or 5: any 2D surface S can be placed into a closed 4D unit ball B, so that the complement of S intersected with int(B) is simply connected. For orientable surfaces we can place S even into the 3-dimensional boundary of B. By coloring int(B)-S (the problem being to make the interior 5 colorable by subdivision or collaps), we could color S.] - [June 17, 2014:] Update on Binet paper Local copy. Substantially enhanced, including PseudoPaffians and Chebotarev-Shamis. [See the mini update blog]
- [Apr 3, 2014:] Orbital graphs with Sigma graphics library.
- [Mar 23, 2014:] "If Archimedes would have known functions ..." contains a Pecha-Kucha talk, a short summary of calculus on finite simple graph, a collection of calculus problems and some historical remarks. ArXiv and local copy [PDF] with updates.
- [February 8, 2014:] "Classical mathematical structures within topological graph theory", ArXiv, and Local copy [PDF] consists of some preparation notes for a talk at the a AMS session in January. See also the slides.
- [January 12, 2014:] A notion of graph homeomorphism., (local [PDF]) We find a notion of homeomorphism between finite simple graphs which preserves basic properties like connectivity, dimension, cohomology and homotopy type and which for triangle free graphs includes the standard notion of homeomorphism of graphs. The notion is inspired by pointless topology and Cech constructions. The fact that homeomorphisms with non-zero Lefschetz numbers have fixed open invariant sets, can be seen as a Kakutani fixed point theorem for finite simple graphs.
- [December 15, 2013:]
The zeta function of circular graphs [ARXIV]
(local [PDF].
The Riemann zeta function is the Dirac zeta function of the circle. We study the roots of the zeta function
of the circular graphs C
_{n}, which are entire functions. We prove that the roots converge to the axes Re(s)=1. This is equivalent that the roots of the Laplace zeta function of the circular graphs converge to the axes Re(s)=1/2. We also derive discrete Basel problem values like zeta(2)=(n^{2}-1)/12 or zeta(4) = (n^{2}-1)(n^{2}+11)/45 which lead in the limit to the classical Basel values zeta(2) = pi^{2}/6 or zeta(4)=pi^{4}/90 for the circle. [Updates: Dec 18: The Kubert connection with Milnor's results. Dec 24: the local maximum of the imaginary part in Figure 3 is at the height of the first root of the Riemann zeta function. - [December 1, 2013:] On quadratic orbital networks [ARXIV],
and local [PDF].
Some remarks in the case of quadratic orbital networks. Was written after finding a disconnected quadratic
network (Z
_{p},z^{2}+a,z^{2}+b,z^{2}+c) with prime p. The computer is since still looking for more. [Update January 22, 2014: Some slides] - [November 26, 2013:] Natural orbital networks [ARXIV], local file [PDF]. This is part of the project on dynamical graphs. It contains questions about the connectivity of orbital networks generated by polynomial maps.
- [November 17, 2013] Dynamically generated networks. Project page. Arxiv. This is a project started with Montasser Ghachem in September 2013. This paper shows some pictures and states some results related to elementary number theory. The project page shows some pictures, movies.
- [July 13, 2013] Counting rooted forests in a network.
We prove that the number of rooted spanning forests in a finite simple graph is det(1+L) where L is the combinatorial
Laplacian of the graph. Compare that with the tree theorem of Kirchhoff which tells that
the pseudo determinant Det(L) is the number of rooted spanning trees in a finite simple graph.
The result can also be interpreted as a voting count: assume that in a social network everybody can vote one of the
friends as "president". If the network forbids any cyclic nominations to prevent groups from tempering with the vote,
then the number of possible voting patterns is det(L+1).
See ArXiv.

July 18: We found that Cheboratev and Shamis have proven the forest theorem already. We are of course disappointed but also reassured. The paper is now upgraded to count colored trees. The linear algebra results are much stronger and give this too. The update will appear also on the ArXiv. update blog. - [July 13, 2013] The Euler characteristic of an even-dimensional graph. We argue that Euler characteristic is an interesting functional on four dimensional geometric graphs because Euler curvature as an average of two dimensional curvatures of random two dimensional geometric subgraphs. Since Euler curvature is conceptionally close to scalar curvature, which integrates to the Hilbert action, the Euler characteristic should be an interesting analogue. ArXiv.
- [June 24, 2013] A Isospectral deformation of the Dirac operator: More details about the
integrable system which deforms D=d+d
^{*}on a graph or manifold. This is the first writeup on this system. Its rough on the edges, chatty and repetitive and maybe even has a forbidding style, but details to most computations should be there. ArXiv. Source code to experiment with the system will be posted later. - [June 9, 2013] Some expanded notes [PDF] from a talk given on June 5 at an ILAS meeting. ArXiv and Slides [PDF]. The talk covered on some linear algebra related to the Dirac operator D of a graph and to demonstrate how natural this object is. The language of graphs is also a natural frame work in which one can see essential ideas of multi-variable calculus in arbitrary dimensions. Stokes theorem on graphs was covered in this talk in even less than 6 minutes 40 seconds.
- [May 31, 2013] A Cauchy-Binet theorem for Pseudo-Determinants [PDF],
ArXiv, Jun 1, 2013.
This paper generalizes the classical Cauchy-Binet theorem
for pseudo determinants and more: it gives an expression for the coefficients of the characteristic
polynomial of the matrix F
^{T}G in terms of products of minors of F and G, where F,G are arbitrary matrices of the same size. The proof is done using the exterior algebra. An update of June 10, 2013 includes Mathematica code. July 6: added that the main result implies an identity for usual determinants: for any two matrices F,G of the same shape det(1+F^{T}G) = sum_P det(F_P) det(G_P), where P runs over all possible minors, with 1 for the empty minor. See also the [ update log with Mathematica code to copy paste. ] August 6: article. - [May 31, 2013] An integrable evolution equation in geometry ,
[ArXiv, Jun 1, 2013].
A bit more back to the roots when working on integrable systems in grad school. It introduces a Noether symmetry by doing an isospectral deformation of the
Dirac operator D=d+d
^{*}on any compact Riemannian manifold or finite simple graph. It also deforms the exterior derivative d but the Laplacian L=D^{2}stays the same as does cohomology. Classical wave or heat evolution on the geometry are not affected neither. Besides the deformed D(t) = d(t) + d(t)^{*}+ b(t) the new exterior derivative defines a new Dirac operator C(t) = d(t) + d(t)^{*}which in the spirit of noncommutative geometry defines a new geometry on the manifold or graph. We prove that the geometry always expands, with a fast inflationary start - as in cosmology. The McKean-Singer supersymmetry relation still holds: the nonlinear unitary evolution U(t) - which naturally replaces the Dirac wave evolution - has the property that str(U(t))= chi(G) at all times. However, supersymmetry is not visible. At t=0, a fermion f and its partner Df are orthogonal at t=0. Already after a short time, the super partner D(t) f is so close to the fermionic subspace that it must be taken as a fermion. Supersymmetry is not broken, but invisible. This holds we take symmetries of quantum mechanics serious. An other feature of the system is that if we do not constrain the evolution to the real, a complex structure evolves. It is absent at t=0 and asymptotically for large t, but it is important in the early part of the evolution. We illustrate in the simplest case like the circle or the two point graph but have computer code which evolves any graph. - [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
^{2}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:] Index expectation (ArXiv 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 Poincaré Hopf (ArXiv ) 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.