In some circumstances index equals the content
This is known as the Index Lemma, a fundamental result in the theory of Dynamic Systems and Algebraic Topology. The Lemma deals with triangulations of plane polygons. A triangulation of a polygon D is a division of D into a finite number of triangles so that each edge on the boundary of D belongs to just one triangle of the subdivision, and each edge in the interior of D is shared by exactly two triangles of the subdivision.
Consider a simple (with no self-intersections) polygon with an arbitrary number of vertices. Triangulate it in any way and label the vertices of the triangulation with the three labels A, B, and C. A triangle in a triangulation is called complete iff its three vertices all received different labels. It's natural to call a complete ΔABC. There are also triangles AAB, CCC, etc. Two quantities are associated with every triangulation.
- The Content C is the number of complete triangles counted by orientation. This means that a triangle counts as +1 if its labels read ABC in a counterclockwise direction around the triangle, but counts -1 if the labels read ABC clockwise around the triangle. This is consonant with a general convention in mathematics that the counterclockwise direction is thought to be positive, while the clockwise direction negative.
- The Index I is defined to be the number of edges labeled AB around the boundary of the polygon counted by orientation, meaning that an edge counts +1 if it reads AB counterclockwise around the polygon, and -1 if it reads AB clockwise around the polygon.
(In the sample diagram both index I and content C equal -1.)
The Index Lemma
The index equals the content.
For the proof let S be the number of edges labeled AB on and inside the polygon counted in the following way: each triangle is considered apart from all the others and its edges AB counted +1 or -1 by orientation. The proof is completed by showing that
On the other hand, consider an individual edge labeled AB. If this edge is inside the polygon, then it is an edge in two triangles in one of which it counts plus one while in the other it counts minus one. These edges then contribute nothing to S. But edges on the boundary of the polygon are counted only once in S, and then just as they are for
the index I. Therefore
For now, let's use the Index Lemma to prove first Sperner's Lemma and then Brouwer's Fixed Point Theorem. In the following we shall only consider triangulations of triangles and not of arbitrary polygons. Thus consider a triangle D and triangulate it into smaller triangles. As before, label the vertices of the triangulation with the letters A, B, and C. We are interested in a particular kind of labeling.
A Sperner labeling of a triangle's triangulation is a labeling that satisfies the following conditions:
- The vertices of the original triangle are labeled with three different letters A, B, and C.
- Vertices of the triangulation that lie on the side AB are labeled either A or B. A similar condition holds for the vertices on sides BC and AC.
- There is no restriction on labeling of the vertices of the triangulation inside the original triangle.
Every Sperner's labeling contains at least one complete triangle.
To better appreciate the proof or, perhaps, even to come up with a different one, it may be useful to gain insite into the dynamics of labeling as one keeps adding nodes to the triangulation. In the applet below you add nodes by clicking inside (or on the side of) the original triangle. The new node is labeled according to which of the radio buttons is checked. The labeling can be changed later by repeatedly clicking on existing nodes.
|What if applet does not run?|
Proof of Sperner's Lemma
We shall actually show that the number of complete triangles is odd. From the Index Lemma suffice it to show that the Index I in Sperner's triangulation is odd. With this in mind we ought only to consider the side AB of the original triangle. Let's call a segment complete if its ends are labeled differently, i.e. A and B. Let b stand for the number
of complete segments on the side AB of the original triangle. Let a denote the number of AA segments, and let c denote the number of internal (to the side AB) A vertices. Thus, e.g. the total number of A vertices on the side AB of the original triangle is
Here is another proof I learned from James Tanton.
Start with a triangulation of a sphere. Label all the vertices with one of three letters A, B, C. Then there is an even number of ABC triangles. For a proof, assume there is at least one ABC triangle. Place doors on AB edges and, starting with an ABC triangle form a path through the doors. The number of triangles is finite, meaning that somewhere, i.e., in one of the triangles, the path will have to terminate. The last triangle which obviously has only one AB edge must be labeled ABC. This could not be the original ABC triangle because the only way to get back there is through the door you already passed. However, this is impossible to step into a triangle twice. If it were possible, there would exist the first triangle twice traversed. This triangle would have to have three AB edges.
Brouwer's Fixed Point Theorem
Let f be a continuous transformation of a triangle into itself. Then there exists a point P such that
Such P is known as a fixed point of f. Therefore, the theorem claims that any continuous transformation of a triangle into itself has a fixed point. Let D be a triangle, g a continuous 1-1 transformation of D onto G. Then, for
g(f(g-1(Q))) = g(f(g-1(g(P)))) = g(f(P)) = g(P) = Q,
which exactly means that Q is a fixed point of thus defined transformation. The implication being that, although I have formulated Brouwer's Theorem for triangles only, it applies to a much wider class of planar sets. Loosely speaking, these are bounded closed sets with no holes.
We shall need the following
The longest edge of a triangulation T is called its diameter d(T).
Thus let D be a triangle, and f: D → D a continuous transformation of D into itself. For every
For simplicity, position D such that its base is horizontal and the third vertex is located above the base.
Next we shall consider a sequence of triangulations Tn of D with d(Tn) decreasing to 0 as n growth. With each such triangulation we associate a Sperner's labeling. A vertex P of the triangulation receives a label A iff v(P) points in the northeast or east direction, it receives a label B if v(P) points in the northwest or plain west direction; for a strictly north direction select either A or B randomly. All other P's are labeled with C.(Why is this a Sperner's labeling?) Of course, if
Now I am going to cut corners a little. Bounded sets in the plane have what's known as the Weierstrass-Bolzano property according to which every infinite sequence of points has at least one point near it. We have three sequences of points. The first is formed by vertices of Dn's labeled A, the second consists of the vertices labeled B, and the remaining vertices of Dn's form the third sequence. Each of this sequences has at least one point near it. Since d(Tn) decreases to 0, there is at least one point P near each of the sequences. By continuity of f, v(P) is bound to be 0.
- J.L. Casti, Five Golden Rules, John Wiley & Sons, 1996
- M. Henle, A Combinatorial Introduction to Topology, Dover Publications, NY, 1994.
- M. Kac and S.M. Ulam, Mathematics and Logic, Dover Publications, NY, 1968.
- S. Stein, How The Other Half Thinks, McGraw-Hill, 2001