# Updates

Here are some updates (mini blog) on my paper on graph topology.- January 16, 2014: The AMS meeting in Baltimore has shown me again how exotic the picture of graphs with higher dimensional structure still is. Unfortunately, I did not have time to present the graph topology because it is a point of view which is very different from what is done in topological graph theory. But there are many analogues. Roman Nedela for example showed me work on a Lefschetz fixed point theorem in graph theory which looks at the graph as a one dimensional object so that only the first cohomology group is interesting, which of course corresponds to the genus. In the second half of this talk [PDF] there are some slides on graph topology.
- I also looked at the talk
Computational topology via discrete Morse theory by Pawel Dlotko, which
deals with higher dimensional structures on graphs. What I do to compute the cohomologies
of a graph, is to make homotopy reductions of the graph in order to reduce the complexity (which
leaves the cohomology invariant), then compute the Dirac matrix D. The kernel of L
_{k}on k-forms is then a basis for the cohomology group H^{k}which in principle could be lifted up to the original graph. It seems that Dlotko does the homotopy part also algebraically, but the whole setup is much more complicated. You find the Mathematica procedures for computing the Dirac matrix of an arbitrary graph in the source code of this papeer. The homotopy reduction steps need a couple of more lines of Mathematica: take a point, find the sphere. Remove the point with all connections if the sphere is contractible. Computing the cohomology groups can be done relatively fast for an arbitrary graph. But this was solved and essentially done already by Poincare, who of course had no computer and needed to write down the incidence matrices by hand. It seems that Pawel Dlotko's methods are able to handle much larger graphs then I can deal with. - January 17, 2014:
The paper solves the problem to find an equivalence
relation "homeomorphism" between finite simple graphs which has the following properties:
- It is simple and based on standard set theoretical topology. It is constructive and allows for many different topologies on a graph. We have an equivalence relation between topological graphs and a functional which measures how good the topology is from a dimension point of view. This also holds for general topological spaces: the real line for example has many topologies, from the indiscrete topology to the discrete topology. The most natural topology is the one for which a subbasis is given by intervals. Why is this a natural topology? First of all, the sub basis elements are contractible (a homotopy notion). Second, they are one dimensional (a dimensional notion).
- The construction is motivated by Cech constructions and so rooted in traditional constructions. The concept of "contractibility" of the open cover as well as the concept of "nerve" is directly taken from notions which are traditionally used in topology.
- It has the property that
**unconditionally**, homeomorphisms preserve homotopy type, cohomology, Euler characteristic and dimension. - Homeomorphisms satisfy the same Lefschetz fixed point theorem as in the continuum. Its only now that the "points" are actually union of contractible sets. It might look as if not much is gained like that but this reformulation of our fixed point theorem for graph automorphism now immediately allows to derive the classical Brouwer fixed point theorem by approximation. Because we are formally so close to the standard topological notions on manifolds, the transition from graphs to manifolds is immediate.
- Completely new the combination and fundamental role of "dimension" in the setup. We feel that this is an important ingredient, especially if graphs are used to model geometric situations or dynamical systems on graphs. The paper explains at several places why dimension is so crucial: dimension and homotopy is often closely related. Homotopy alone is much, much too weak because from the homotopy point of view, every contractible set is a point. We want to distinguish balls of various dimension, especially in geometric setups where also the boundaries (spheres) play an important role. Connectivity properties depend on a crucial way on dimension: the one dimensional ball has a disconnected boundary, the two dimensional ball has a boundary with nontrivial fundamental group (a totally fundamental topological notion as the name tells), the three and higher dimensional balls have boundaries which are simply connected.
- If we look at analogues of
partial differential equations on graphs. For example, if we look at Maxwell equations
dF=0,d
^{*}F=j on a graph, then F is a 2 form which lives on two dimensional components of a graph. We need at least 2 dimensions to study the evolution. Natural from the physical point of view are situations where the graph has four dimensional components (K_{5}subgraphs which have 6 triangles carrying the electromagnetic traditional field (E1,E2,E3,B1,B2,B3) ). One might wonder why to use space-time language from the continuum. As Poincare has realized even earlier than Einstein, the Lorentz group is the symmetry group of the wave equation and electromagnetism is conveniently described by simple equations dF=0, d^{*}F=j. With F=dA, we get with a Lorentz gauge d^{*}A=0 to the Poisson equation LA=j which is in the absence of matter the wave equation LA=0. In a pseudo Riemannian manifold of type (-1,1,1,1) this is the wave equation for each component of A. In the discrete, on a graph, it is unnatural to have time implemented in the geometry. This is fortunately, because it is ugly in the continuum: we were seduced to it about 110 years ago just because of symmetry and its just awful. Everybody learning relativity experiences that while it is impressive to speak about space-time manifolds, it is not intuitive, hard to learn, and hardly useful. When we simulate a physical system on the computer, we do not build a "space time manifold", but we evolve time by solving differential equations. The picture with space-time manifolds does not explain for example, why it is not possible to reverse time. Actually, time is a completely different beast: it is a geodesic motion in the symmetry group of the geometric object. It is a nonlinear integrable system. As shown in the Dirac deformation papers there is a natural arrow of time now and the linear wave equation (hence a Lorentzian structure) is obtained in the limit for large time. Space expands and always comes with a inflationary start. This is just linear algebra. - Dimension is everywhere central in mathematics: fractal geometry, probability theory, information theory and of course topology or algebra. There are various notions of dimensions which have been introduced in graph theory. The inductive dimension has the first time appeared in my elemente paper.

- January 18, 2014:
The difficulty to do topology on graphs is illustrated in a
thesis of
Antoine Vella, 2005. It poses the question to find a topology
which makes the graph path connected if and only if it is connected.
The thesis skillfully illustrates the problem. But it does not provide a solution.

That this is in not possible has been recognized by many. A recent paper "An Alexandroff topology on graphs" by Amiri, Jafarzadeh and Khatibzadeh for example deals with the problem to study topologies on graphs. These authors essentially focus on the topology generated by unit balls except that they decide to use the topology generated by the unit spheres and call this the "graphic topology" and realize that if a vertex is connected to all other vertices then {x} is both open and closed and the graph disconnected.

As we have stated in our article, this can not be avoided. On a finite simple graph, classical topologies alone have almost always different connectivity properties than the graph itself. We overcome this problem by slightly modifying the definition of connectivity which is equivalent to the classical general set-theoretical case if there is a sub-base of contractible sets. - January 19, 2014: The condition to have all intersections contractible is in algebraic topology called a "good cover". For a sphere, one needs at least 4 open sets to get a good cover, where we take open balls around the vertices of a tetrahedron. We would not accept that yet because the nerve graph is not homotopic to a discretisation of a sphere. We need 6 open sets to get a cover of the sphere in such a way that the graph is a two dimensional graph. We have required all intersections to be contractible only for "optimal covers". Having all intersections contractible has the advantage that the Brouwer fixed point theorem will lead to a contractible fixed point if the Lefschetz number is non-vanishing. When writing the paper, I first had required to