Graph Products

Graph Products

The video of August 20 also gave a bit of an overview of graph products. I should have mentioned the Lexicographic product (introduced by Hausdorff in 1914) mentioned in my article on Graphs, Groups and Geometry. Here is an abbreviation of the story of that video: for finite simple graphs, the Shannon product (strong product) together with disjoint union builds up to a ring which has all the properties we can wish for: it is compatible with cohomology (The Kuenneth formula is directly realized by tensor products of harmonic forms = cohomology classes) so that Euler characteristic satisfies the rule of product. This is what we want from a product. Looking at a product which does not satisfy the rule of product is like looking at a curvature which does not satisfy Gauss-Bonnet or a calculus which does not satisfy the fundamental theorem of calculus. Now, I had been looking for a product for multi-graphs (multiple connections are possible) or quivers (multi-graphs with loops). This was not just for the purpose of generalization. Quivers actually can be seen as natural analogues of objects appearing physics (a space with electromagnetic field) or algebraic geometry (divisors).

When looking at the physics connection, we have looked at discrete analogues of magnetic Schroedinger operators where the multiple connections model a magnetic field and the loops model a scalar potential, an intriguing picture considering that now fields are part of the geometry. In the context of algebraic geometry, the loops can model divisors (at least effective divisors) Again, it is nice to see divisors seen as geometric objects. A modern take on the classical Riemann-Roch theorem l(D)-l(K-D) = X(D) is to see the right hand side X(D) = X(G) + deg(D) as an Euler characteristic of the divisor and l(D)-l(K-D) as a cohomological Euler characteristic. Riemann-Roch then appears as a glorified Euler-Poincare formula, but more subtle because the numbers l(D) are harder to compute. The number l(D) appearing in Riemann-Roch is also very intuitive if one thinks in terms of physics. It measures how much energy we can take away modulo principal divisors so that we still have an effective divisor. Related to that it is interesting also when we can really look at cohomology of a quiver. We have seen that this is no problem for an effective divisor because it comes with a delta set (which is just a shiny finite abstract simplicial complex in which sets can appear with multiplicity) and which is a notion that is more general than simplicial sets.

Free after the UNIX moto simplicity, generality, clarity which I follow as a source of wisdom since I use unix for organizing my electronic world (and brain!), it makes more sense to go with the more general notion if it also becomes simpler and clearer. There is a heroic effort by Greg Friedman explaining simplicial sets (presheaves on the simplicial category) and still after digging into that for years, I find delta sets (presheaves on the strict simplicial category) much more approachable. I prefer a geometric structure with less axioms and notions if there is a choice. Compare that with the notion of matroid which is more complex than finite abstract simplicial complexes (the later has only one axiom: the set of sets has to be invariant under the operation of taking non-empty subsets) But take a matroid and remove the empty set and you have a finite abstract simplicial complex. The notion of finite abstract simplicial complex is much simpler, has less structure, yes, but is as powerful as we wish. In some sense [modulo the empty set part which is just a silly definition thing as there are also versions of simplicial complexes, where the empty set (the void) is allowed. Note that the empty set itself is a simplicial complex. It is the (-1)- dimensional sphere even, a very important object. But the empty set does not contain the empty set. We can work without the void! ] matroids are simplicial complexes. Also simplicial sets are delta sets. In each of the cases, just strip away some complexity and structure. Of course, in some cases, it makes sense to look at objects with more structure like matroids or simplicial sets. I personally have a finite and shrinking amount of hours left to do mathematics and simply refuse to get bugged down in structures which are too complex. So, why not look at hyper graphs then, which generalize simplicial complex and get rid of the only axiom there is there? Hypergraphs are just sets of sets. More generally, one can look at hypergraphs in which sets can appear with multiplicity. One could call this a hyper delta set. Still, there is no cohomology in general and no theorems in general. If I look at a geometric structure, I want a minimum of theorems to work: Gauss-Bonnet, Poincare-Hopf, Euler-Poincare, McKean-Singer, Brouwer-Lefschetz, Riemann-Hurwitz, Riemann-Roch. (I gave that list once in a math table talk from 2016, where I talked about a multi-variate version of Euler characteristic, the Wu characteristic and where we also want to have the product property. Now, all these theorems generalize to objects that appear in arithemtic. In the case of cohomology of elements in the ring of Shannon one has to look at postive and negative cohomology. There will be positive and negative Betti numbers for example, but the compatibility of cohomology with arithmetic prevails when just asking the betti nmbers of -A to be the negative of the Betti numbers of A.

But there is an issue when looking at general divisors, where the values attached at the vertices or edges can become negative: there is no delta set anymore lurking around and so no cohomology. I might talk about this a bit net time but this is where algebraic geometry has come up with the notion of effective divisors. Here in the discrete, effective divisors are divisors which can be realized by quivers and which therefore come with a delta set and cohomologies which satisfy all the properties we want. Also in terms of cohomology, for me, cohomology needs to come with an exterior derivative d defining a chain complex and so also come with a Dirac operator D=d+d* (not to be confused of course with a divisor. D is just a matrix) and with a Hodge operator L=D*D and so some interesting spectral theory (and of course Hodge theory which is the most intuitive approach to cohomology. No Jedi hand-waving using exact sequences are necessary, only notions of linear algebra are required. Why are we interested in general divisors, where also negative loops or connections are allowed. One reason is physics, there is anti-matter. An other is arithmetic. We want objects which form a ring. Now, as we have also seen since a long time, there is a natural ring associated to any delta set, it is the face ring. A little bit more general as we look now at polynomials with integer coefficients. Like G = x+y+2xy which we see as a quiver, where two points are connected by two edges. (It is mentioned in the video as one of the simplest Feynman diagrams, where a particle pair gets created and annihilated). One could call this quiver the virtual particle quiver. Its Barycentric refinement is C4 which is a 1-dimensional sphere. So, we decided to consider this quiver to be a sphere too.

Apropos Barycentric refinement. It appears a bit silly to worry too much about various structures like quivers as the Barycentric refinement is always a finite simple graph. Once the faces of a geometric object are identified, just take these faces as the nodes of your graph, then look at the incidence graph. This captures the geometry and for finite simple graphs, we have a great arithmetic, the Shannon ring, which does all we want. More recently, a couple of weeks ago, I mentioned that I also consider the manifold problem solved. It has bothered me for years that the Shannon product of two manifolds is not a manifold any more . Once, we loosen up and look at soft manifolds (I think in the video below I called them weak manifolds. The article on soft manifolds is not finished yet and I debated various names, but soft manifold is probably a good name). But back to the movie and the product. The good news of that video is that we can multiply quivers using a generalized Shannon product and extend this to a ring! The bad news is that the functor which assigns to a quiver a delta set does not work with the product: the Kuenneth formula fails. What we have to do therefore is to consider the product of two quivers as an element of the face ring which provides a product of delta sets. In the finite simple graph case, the product delta set came from the delta set of the product. That fails for quivers. But that is not a big deal. There many ways to avoid the problem. One is to go with Barycentric refinements where we have the Shannon arithmetic compatible with cohomology or we go with the Face ring (Stanley Reisner). And these structures are from a homotopy point of view equivalent. Thank god. And they would (if we believed in infinity and looked at geometric realizations in some Euclidean space) correspond to what one classically does.

NameOriginTime
TensorWhithehead, Russell1910
LexigographicHausdorff1914
StrongShannon1956
LargeSabidussi1959
CartesianHarary1969
FaceStanley/Reisner1974
RootedGodsil1978
Products in Graph Theory