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 Lk
on k-forms is then a basis for the cohomology group Hk 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 (K5 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