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.

Definition

  1. 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.
  2. 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.

Proof

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 C = S = I. To prove the first equality, consider a complete triangle of type ABC. This has just one edge of positive orientation and so contributes +1 to S. At the same time as a complete triangle it counts +1 as part of C. As a second example consider a triangle of type ABA. This has two edges AB, one each of positive and negative orientation, and so contributes a total of 0 to S. It also contributes zero to C, since it is not complete. By surveying all the possible types of triangle, one verifies that each triangle is counted in the same way in S as in C; therefore C = S.

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 S = I.

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.

Definition

A Sperner labeling of a triangle's triangulation is a labeling that satisfies the following conditions:

  1. The vertices of the original triangle are labeled with three different letters A, B, and C.
  2. 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.
  3. There is no restriction on labeling of the vertices of the triangulation inside the original triangle.

Sperner's Lemma

Every Sperner's labeling contains at least one complete triangle.

Remark

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.

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

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 c + 1. Since, each AA segment contains two A vertices while each AB contains only one, and every internal A vertex is shared by two segments of the subdivision, we have 2a + b = 2c + 1. Therefore b is odd.

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 P = f(P).

Remark

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 Q ∈ G we may define g(f(g-1(Q))) ∈ G. This gives us a continuous transformation of G into itself. If P is a fixed point of f and Q = g(P) then

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

Definition

The longest edge of a triangulation T is called its diameter d(T).

Proof

Thus let D be a triangle, and f: D → D a continuous transformation of D into itself. For every P ∈ D form v(P) = f(P) - P, a vector from P to f(P).

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 v(P) = 0 we have a problem with our labeling. But, if we ran into a point P where v(P) = 0 we may stop here since then f(P) - P = 0 and P is the fixed point of f. Thus assume that this has not happened. Then the triangulation Tn is assured to have a complete triangle Dn.

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.

References

  1. J.L. Casti, Five Golden Rules, John Wiley & Sons, 1996
  2. M. Henle, A Combinatorial Introduction to Topology, Dover Publications, NY, 1994.
  3. M. Kac and S.M. Ulam, Mathematics and Logic, Dover Publications, NY, 1968.
  4. S. Stein, How The Other Half Thinks, McGraw-Hill, 2001

Elements of Topology

|Contact| |Front page| |Contents| |Did you know?| |Geometry|

Copyright © 1996-2018 Alexander Bogomolny

71872991