Actual transcript from https://www.youtube.com/watch?v=MCL9R3CJCo0
http://www.math.harvard.edu/~knill/technology/2016/automated   Automatic 

0:00Welcome! These slides deal with an integer valuation on finite simple
0:04graphs. It is the Wu characteristic. Since I, Oliver, cannot talk as fast as computer
0:09voices do, the comments to the slides are read by Ava and Alex.
0:14The Wu characteristic is a quadratic valuation on graphs which sums up over
0:18pairs of complete intersecting sub graphs. While not a homotopy invariant, it is
0:22invariant under Barycentric subdivision and so defines a
0:25combinatorial invariant for compact manifolds. On finite simple graphs, it is
0:29a multiplicative quadratic valuation for discrete manifolds with boundary. It is
0:34the Euler characteristic of the interior minus the Euler characteristic of the
0:37boundary. There is a Gauss-Bonnet formula for the characteristic. The
0:40existence of quadratic Somerville invariants confirms
0:44a conjecture of Gruenbaum.
0:48The Euler characteristic is by far the most important valuation. It is a homotopy
0:51invariant. It behaves correctly with respect to sums and products and
0:55is invariant under Barycentric subdivisions. The Euler characteristic
0:58super counts simplices, complete sub-graphs of the graph. The even dimensional
1:02ones are counted positively and the odd dimensional are counted negatively.
1:09Even so Platonic solids were known in ancient
1:11Greece already, the Euler polyhedral formula has not yet been known at that
1:15time. The characteristic is named after Leonhard Euler who first proved the
1:19famous Formula v - e + f = 2 in the planar case. More than 100
1:23years before, Rene Descartes discovered some of the relations already,
1:26wrote it down in a secret diary, but did not prove it.
1:30the formula was extended to higher dimensions, starting with Ludwig
1:33Schlaefly and Henri Poincaré. Many important theorems deal with Euler
1:37characteristics. Examples are Gauss-Bonnet, Poincaré-Hopf, Euler-Poincare, Riemann-Hurwitz
1:42Riemann-Roch or McKean-Singer. The Wu characteristic sums all ordered
1:49pairs of intersecting simplices in the graph. Interactions between even
1:53dimensional simplices are counted positively, the interaction
1:56between even and odd dimensional cases are counted negatively. Let's call it the
1:59Wu characteristic, after Wen-Tsun Wu who introduced these valuations
2:02about sixty years ago. The numbers have not have been studied much since.
2:11Wu made his PhD under the guidance of Charles Ehresmann who had other famous
2:15students like Andre Haefliger.
2:19Here is a simple example of an
2:21evaluation of the Euler characteristic of a graph. The
2:24graph is the complete graph with two vertices: the 1-simplex. For the Euler
2:28characteristic, we just count simplices. Since there are two even dimensional
2:32vertices, which are the vertices and one 1-dimensional simplex, the edge, the Euler
2:36characteristic is 2-1 =1. For the Wu characteristic, first count the
2:40interactions between vertices, then the interaction between the edges,
2:44there is one, and finally the interactions between vertices and edges,
2:48there are 4. Note that we look at the order of the pairs. If we add everything
2:52up, we get minus 1.
2:56And here is another example. The graph is
3:00the triangle. Counting vertices, edges and triangles gives 1. Note that this is
3:04already Euler's formula v-e+f=1. For the Wu characteristic,
3:08there are now already more possibilities: we have the interactions between
3:12vertices, we have the self interactions between edges, we also have the
3:16interactions between different edges. New is also the self-interactions between
3:20triangles and the interactions between edges and triangles as well as
3:24the interactions between vertices in triangles. If we add everything up, we get
3:28that the Wu characteristic of the triangle is 1. We see already a pattern:
3:34For even dimensional simplices, the Wu characteristic is 1.
3:37For odd dimensional simplices, the Wu characteristic is -1. This will
3:42follow in general from a boundary formula and the fact that the Wu
3:45characteristic is invariant under Barycentric subdivision. Since the Wu characteristic of
3:52a simplex is minus 1 for odd dimensional graphs and 1 for even dimensional graphs,
3:56we can write the Wu characteristics using omega. The characteristic is a quadratic
4:00valuation. There are more general characteristics, the cubic one, for
4:04example, sums up over all triples of simplices, which simultaneously intersect.
4:08For the cubic characteristic, all simplices evaluate to 1 again, like for the
4:12Euler characteristic. Assume, a graph has
4:17maximal dimension d, meaning that there are d-dimensional simplices present in the
4:20graph but no (d+1)-dimensional simplices. If v of k counts the number of
4:24simplices in G, one can form the f-vector, which contains all these numbers.
4:28Now take the dot product between this (d+1)-dimensional vector X with this
4:34f-vector. This gives the value of the valuation.
4:40Quadratic valuations are described by
4:41f-matrix here denoted with capital V.
4:45This matrix is the analog of the f-vector. It counts the number of
4:48intersections of i-vertices with j-vertices. To get the quadratic
4:52valuation, take a symmetric matrix X, usually with integer entries, telling
4:56what value we give to an interaction of i-dimensional and j-dimensional
4:59intersecting simplices, then we form the sum.
5:04The discrete Hadwiger theorem of Klain and Rota assures that the space of linear evaluations
5:09of a graph is (d+1)-dimensional, where (d+1) is the clique number, the
5:13maximum number of vertices which a complete graph in G can have. There
5:16is a generalization of the discrete Hadwiger result. It gives the dimension of the
5:20set of quadratic evaluations. Note that the space of valuation is still a linear
5:24space. It is just that the action of the valuation on graphs is now quadratic.
5:31Hugo Hadwiger was a Swiss mathematician.
5:32Hadwigers theorem is a celebrated theorem in integral geometry.
5:36The theory in the continuum is well developed. Valuations have to be built
5:40carefully. Unlike for measures, valuations evaluate geometric objects
5:44with internal structure, simplicial structure. In the continuum, the basic
5:49ingredients are convex sets.
5:53The discrete version of Hadwiger's has been developed later. It can be found
5:57in the book of Dan Klain and Gian-Carlo Rota: "Introduction to geometric probability"
6:01from 1997. In the discrete also, a valuation does not measure the content of sets,
6:05but of objects with internal structure given by simplicial complexes. One can
6:09also formulate it using graphs. As graphs have a natural simplex structure,
6:14the Whitney complex.
6:18Here is the standard basis for
6:19the space of linear valuations. There is a similar standard basis for quadratic
6:23valuations. There is another natural bases in the linear case and it is a
6:27Barycentric subdivision.
6:32Here are four graphs on which the Wu characteristic is evaluated.
6:34It is a Adenine, Guanine, Cytosine and Thymine. They are the nitrogenous bases
6:39of the DNA. The numbers on the vertices of the graphs are curvatures.
6:43They add up to the Wu characteristic.
6:48Here is the Gauss-Bonnet formula for valuations.
6:49It in particular applies to the Wu characteristics: There always exists a
6:54function K on vertices such at the sum over all vertices is the value of the
6:58valuation. This works for linear evaluations and also for any multi-linear evaluation.
7:02Of course, the prototype is the Euler characteristic. The theorem originally
7:07comes from the continuum, where it had been proven in more and more generality,
7:10culminating in the Gauss-Bonnet-Chern theorem.
7:16We can locate the discrete version of the theorem appeared in a paper of Norman Levitt.
7:19But the statement had not been seen as a Gauss-Bonnet result and not in graph theory.
7:26In the continuum, the Gauss-Bonnet-Chern theorem
7:28involves the Euler curvature, which is a complicated expression in terms of
7:31the Riemann curvature tensor. It is Pfaffian and only defined for even dimensional
7:35manifolds. In the discrete, curvature is defined for all networks. The fact that
7:40it vanishes for odd dimensional geometric graphs is a special case of
7:43the Dehn-Somerville relations.
7:48Here are the main figures for the Gauss-Bonnet-Chern Theorem it in the continuum.
7:52Gauss and Bonnet dealt only with the two-dimensional case.
7:56After work of Allendoerfer and Weil Chern was the first to prove the result
7:58without embedding in an ambient space. While the curvature is defined for any
8:04multi-linear valuation, here is an explicit expression of the curvature in
8:07the case of the Wu characteristic. The curvature depends on a disk of radius
8:11and has become a second-order difference operator, like in the continuum. The sum
8:15is over all pairs of simplices x and y, where x contains the vertex and the
8:19simplex y intersects the simple x. Note that the simplex y does not
8:23necessarily have to contain the vertex v. You can try it out implemented in
8:26computer code contained in the preprint.
8:31Here is a simple example of a line graph. We compare the curvatures of of the Euler
8:33characteristic and the Wu characteristic.
8:36You see the Euler curvature is supported here on the
8:39boundary. For the Wu characteristic curvature has moved slightly inside. For a line
8:43graph, in distance 2 or larger from the boundary, the curvature of the line graph
8:47is zero. The graph is flat there.
8:52This is an example which is a
8:53discretization of the Lemnicate, a quartic variety. It is the figure eight graph. The
8:58curvature is only nonzero near the intersection point, which is the
9:01singularity. The total curvature of the figure 8 graph is 7, which is the Wu characteristic.
9:07You will see that the Wu characteristic is invariant under Barycentric subdivision.
9:10This will mean that we can assign also the Wu characteristic 7 to the lemniscate.
9:14The wheel graph is a two dimensional disc.
9:18It has Wu characteristic 1.
9:20This is true for all two-dimensional discs and more generally,
9:23for all even dimensional balls. The boundary of an even dimensional ball
9:27is an odd-dimensional sphere. The Wu characteristic of that sphere is zero,
9:34like Euler characteristic. The three-ball is a graph which has Euler
9:37characteristic -1. The curvature is here located at only one central point. The unit
9:41sphere - the vertices connected to that vertex - is an octahedron graph, which is
9:46an even dimensional graph. We see here already an illustration telling that the
9:49characteristic of a graph with boundary is the Euler characteristic
9:52of the graph minus the Euler characteristic of the boundary.
9:58Here is an example of a tree.
9:59It is a graph of maximal dimension one which has no closed loop. The Wu
10:03characteristic is here much larger than the Euler characteristic. You can observe
10:06that the curvature can become negative near an end point.
10:12We look at the Euler characteristic and
10:12Wu characteristics in comparison. The graph
10:16is a two-dimensional disk. To the left you see the Euler curvature. The Euler
10:20curvature in the interior is 1 minus the length of the unit sphere
10:23divided by 6. It is one-half minus the length of the unit sphere divided by six
10:28on the boundary. The Euler curvatures in the two-dimensional case have been
10:31known since the 19th century, especially through the work of Heinrich Heesch in
10:35graph coloring.
10:39And here is a circle bouquet, a wedge sum of circles.
10:40The Euler characteristic is -4. One can see this also
10:45from the fact that there are no triangles and five loops, leading to a Betti number 5
10:48The Euler characteristic 1 minus 5 which is minus 4. The Wu
10:53characteristic is pretty large already. This is due to the many interactions
10:56at the singularity. The sum is 76.
11:02Despite the fact that the cube
11:03graph is usually considered a two-dimensional polyhedron, we look at it
11:06as a one-dimensional geometric object, as it has no triangles. You can think of it
11:11as a sphere with six holes. The Euler characteristic is 2-6 which is equal to
11:15minus 4. The Wu
11:16characteristic is 20. The Wu curvature is constant 5/2.
11:23Here is another general theorem
11:24which holds for any
11:25finite simple graph and any valuation. We can attach to the vertices an index
11:29which adds up to the valuation. An integer value function on vertices is
11:33also called a divisor. The theorem also applies to the Wu characteristic.
11:41The continuum theorem is due to Henry Poincare and Heinz Hopf and requires
11:45the function to be regular enough like a Morse function so that
11:47critical points are isolated. In the discrete, the theorem holds for any
11:49finite simple graph and any linear or multi-linear valuation.
11:54It especially holds for the Wu characteristic.
11:58For a linear valuation,
12:00like for example the
12:00Euler characteristic, the index is given by this formula. Here B(X) is the
12:05subgraph of the unit ball of the vertex generated by the vertices on which f is
12:08smaller or equal than the value taken on the central vertex. The graph S(x) is the
12:12subgraph of the unit sphere of the vertex generated by the vertices on which f is
12:16smaller than the value taken on the central vertex.
12:22Here is an example, where the valuation is the volume, a particularly simple valuation.
12:26The volume is the number of facets, the number of highest dimensional simplices which occur
12:30in a graph. In this case, the index is always non-negative.
12:37A quadratic valuation can also be
12:39written as a bilinear form or intersection number. In the case of the
12:42Wu characteristic, this is written as given. We sum up
12:44over all ordered pairs of simplices, where the first simplex is in A and the
12:48second is in B, which intersect. When seen like that, the Wu characteristic
12:52is a self-intersection number of the graph with itself.
12:57Here are two examples of computations.
12:59If an odd-dimensional graph intersects nicely with an odd dimensional graph, then
13:02the intersection number is equal to one. To the right, we see a curve
13:06intersecting a disc. The intersection number is minus one.
13:12And here is an example of two-dimensional disc, intersecting
13:15transversely in a point. In three space, this looks like a cone. But in
13:18four-dimensional space, one could draw the embedding so that the intersection is
13:22perpendicular. The intersection number is 1. In a preliminary step, the Poincare Hopf index
13:27of the Wu characteristic and a function f is given by a sum of intersection numbers.
13:29This is now first written as a function on pairs of vertices.
13:33The index is zero if the two vertices have distance larger than two.
13:37The reason is that then, the balls of different
13:41vertices do not intersect so that the
13:44intersection numbers are zero.
13:48We can push the index function from pairs of vertices to the vertices.
13:50It becomes a scalar function on vertices. It still is an integer.
13:54The Poincare-Hopf theorem states that this sums up to the Wu characteristic.
14:00Here is a general formula which shows
14:02why the characteristic is so important. Like Euler characteristic, it is
14:06multiplicative. The product of two graphs consists of all pairs (x,y) of simplices
14:11where x is a simplex in the first draft and y is a simplex in the
14:14in the second graph. Now, two such vertices are connected if one is contained in the
14:19other. In the special case where one graph is the one point graph, this is the
14:23Barycentric subdivision. This product has all the properties we wish for.
14:27It satisfies the Kuenneth formula for cohomology.
14:32Here is an example of a product of a line graph - a discrete interval -
14:34and a circular graph - a discrete circle.
14:38The resulting graph is a discrete cylinder. The Euler characteristic of the line graph
14:42is one. The Euler characteristic of the second graph is 0. The cylinder has
14:46Euler characteristic zero. Similarly, the Wu characteristic of the first graph is
14:49minus 1, with Wu characteristic of the circle is zero and the cylinder again has
14:53Wu characteristic 0. The product formula especially implies that
14:59the Wu characteristic is invariant under Barycentric refinement.
15:01The Barycentric refinement of a graph G has as vertices the set of simplices in G.
15:07Two such new vertices are connected, if one is contained in the other.
15:11How can one see that the Euler characteristic is invariant?
15:15The parity of the simplex - a number which is -1 for odd simplices.
15:19and 1 for even dimensional simplices - is a scalar function
15:23on the vertices of the Barycentric refinement. It turns out, this is the Poincare-Hopf index
15:27of a function f! Poincare Hopf tells that it sums up to the Euler characteristic of
15:30the refined graph. Note that the Euler characteristic is a much larger sum as it
15:34would sum up over all simplices in the new graph.
15:38Raoul Bott called a quantity which is
15:39invariant under Barycentric refinements
15:40a topological invariant. Bott himself found a few interesting
15:44invariants like that in his early career. Topological invariants for graphs
15:48are interesting as they produce topological invariants for compact manifolds. Indeed,
15:52an initial triangulation of a manifold becomes after Barycentric
15:56refinement closer and closer to the manifold.
16:02For d-graphs, discrete manifolds,
16:03the Wu characteristic is related to the Euler characteristic and the
16:07Euler characteristic of the boundary. There is a general theorem of Yu from 2010,
16:11telling that such a relation has to hold for a topological invariant. The formula
16:15implies that for graphs without boundary, the Euler characteristic and the Wu
16:19characteristic agree. It also implies that for odd-dimensional graphs with boundary
16:22the Wu characteristic is minus the Euler characteristic of the boundary.
16:29For a 3-dimensional ball for example, the Wu characteristic is minus 1.
16:33The graph has a two dimensional sphere as boundary. The Wu characteristic is 1 minus 2 which
16:38is minus one. One could get a three ball also through
16:41Barycentric refinement of a 3-simplex.
16:45The f-vector of a graph encodes the cardinalites
16:46of the set of complete subgraphs of a graph.
16:50Similarly the f-matrix encodes the cardinalites of the set of pairs of complete subgraphs
16:53of a graph intersecting in a non-empty graph.
16:57Here is an example of a computation of the f-vector and f-matrix of a graph.
17:01We can use the f-vector to get the Euler characteristic and use the f-matrix
17:05to get the Wu characteristics.
17:10The classical Dehn-Sommerville relations tell that some linear valuations are zero for graphs
17:11which are geometric. We call them d-graphs. A d-graph is a finite simple graph for which
17:16every unit sphere is a (d-1)-sphere. A d-sphere is a d-graph which when punctured
17:21becomes contractible. The proof is very simple.
17:25The curvature of a Dehn-Somerville valuation is a Somerville valuation
17:28of the unit sphere. These relations have been developed by
17:34Max Dehn, Duncan Sommerville and Victor Klee. Gruenbaum asks in 1970, whether
17:39the f-matrix satisfies some Dehn-Sommerville equations. He says then that it may be conjecture that
17:44the answer is affirmative. We can confirm this conjecture now.
17:47Branko Grünbaum is well known through his many papers and books in combinatorial
17:54topology and discrete geometry.
18:01Here is how we get quadratic Dehn-Sommerville relations.
18:02Take a vector a, which enters the Euler
18:06characteristic and the Dehn-Sommerville vector b.
18:09Then produce the quadratic valuation
18:15as indicated. It is zero on d-graphs.
18:16In comparison, here is how we write the Wu characteristic. This is an example,
18:17but only if d is odd, as the Wu characteristic is then the Euler characteristic
18:21and the Euler characteristic are a Dehn-Sommerville invariant for
18:24odd dimensional graphs.
18:29An other important principle, which holds not only for linear valuations but also
18:31for quadratic and higher multi-linear valuations
18:34is that if we average the indices over a nice probability space of functions,
18:38then we get curvature.
18:44This result is related to some index averaging result proven by Thomas Banchoff
18:45in the 60ies. It is a general principle which connects Poincare-Hopf and Gauss-Bonnet.
18:49If we average the Poincare Hopf indices,
18:53we get Euler curvature.
18:58Here is an example which illustrates this in the case of a simple linear valuation,
19:01the volume. The graph is a two dimensional disk of volume 12.
19:05How do we get the index of a vertex v? Just count all the triangles which contain v
19:09for which the value of f at v is a maximum. For every function f
19:12we get like this an index. When averaging over all functions,
19:16we get the curvature at a vertex as the number
19:19of triangles attached to the vertex divided by 3.
19:23The proof of Gauss-Bonnet is very simple.
19:25The valuation is given by definition as a sum over simplices.
19:28Take these values and shove them equally to all the vertices of the simplex.
19:33In the case of a quadratic valuation we first have to get the interaction value on the
19:37simplex, then distribute it to the vertices
19:43To prove Poincare Hopf, just move the value of the simplex to the vertex
19:47on which f is maximal. Since we do not distribute
19:50the values, they remain integers.
19:53The multiplicative property can best be
19:55seen algebraically. We get values on the vertices of the product graph.
19:56This turns out to be a Poincare Hopf index
20:01of the Wu characteristic on the product graph!
20:07Here is a computation
20:08which illustrates how one can get the
20:09Wu characteristic in the Stanley-Reisner ring. The Euler characteristic is just
20:13evaluating the ring element at a point, where all vertices have the value minus 1.
20:16To get the Wu characteristic, we square the Euler characteristic, then subtract all
20:21the terms in the square of f as we need to remove all simplex pairs
20:24which do not intersect. To show the boundary formula
20:30one has to write the sum of interactions according
20:30to in which simplex the interaction
20:33takes place. Now, there are cases where both simplices x,y are different and not equal
20:38then cases, where one of them is z and, then one case where both are z.
20:42The upshot is that all the values together give either 1 or minus 1 depending on whether
20:45z is even or odd dimensional. In other words, we get the Euler characteristic.
20:53To prove the Dehn Sommerville relations
20:54one can proceed
20:55like in the linear case and show that the curvature is equal to the
20:58Dehn Sommerville valuation on the unit sphere. This allows to use induction.
21:06Here are some graphs. The first is the 16-cell, a three dimensional sphere
21:10and one of the 6 Platonic solids in 4 dimensions. It is the analogue of the Octahedron in four
21:14dimensions and a 3-sphere: you can check that any of its unit spheres is an octahedron.
21:18Its dual graph of the 16-cell is the Tesseract - the four dimensional cube.
21:22Note that this is a one dimensional graph, as it contains no
21:26triangles. But if we triangulate it, we get a 3-sphere again.
21:31Lets compute some quantities for these graphs!
21:35We see here the f-vector and the f-matrix computed for the 16-cell.
21:38The Euler characteristic is the dot product between the Euler vector with this vector.
21:42It is zero, like for any three dimensional geometric graph.
21:46This is already a classical Dehn-Sommerville relation.
21:49With the f-matrix we can compute the Wu characteristic by applying it to the Euler vector and again
21:52taking the dot product. It is again zero. This illustrates already a quadratic
21:57Dehn-Sommerville relation.
22:01The tesseract is the 4 dimensional cube.
22:02But it is a one-dimensional graph as it has no triangles.
22:03The f-vector has only 2 components.
22:04The Euler characteristic is minus 16,
22:09The Wu characteristic is 112.
22:11The Wu curvature is constant 7.
22:18And here is the computation
22:19for the triangulated tesseract
22:20which is now no more a Platonic solid.
22:23Its Euler characteristic and Wu characteristic are still zero.
22:30When applying the f-matrix to pairs of classical Dehn-Sommerville vectors, we get the
22:34Dehn-Sommerville matrix. What always happens for d-graphs
22:37is that the first row and first column of the matrix is zero.
22:41These are the non-linear Dehn-Sommerville relations, which Grünbaum conjectured to hold.
22:46Finally, here is an example
22:48of a pair of graphs and the product graph. The Euler characteristics of the factors are 1 and 0.
22:53The Wu characteristics of the factors are 5 and 8.
22:57The product has Euler characteristic 0 and Wu characteristic 40.
23:01This is the end. For more details, look at the paper on the ArXiv.