Three colours force a triangle

The fixed-point theorem says that a continuous map of a disc into itself leaves some point where it is, and its proof is topological: a loop that cannot be shrunk, a degree that cannot change. Underneath it there is a statement with no topology in it at all, about a triangle cut into smaller triangles and coloured with three colours.

The colouring above was made at random, subject only to the rule, and the number of three-coloured triangles came out odd. That is not a property of this colouring. It is a property of every colouring obeying the rule, on every subdivision of any triangle whatever, and it is provable by an argument about doors.

The rule, and where it bites #

Label the three corners of the big triangle with the three colours. Then the restriction is:

a vertex on the edge between two corners may take only one of those two corners’ colours, and a vertex in the interior may take any colour at all.

The three corners themselves have no choice — each lies on two edges at once, and the only colour permitted on both is its own. A vertex partway along an edge has two options. An interior vertex has three, and the picture takes all of them at random.

That is the entire hypothesis. Nothing is assumed about how the triangle was cut up, how many pieces there are, or whether they are the same size; nothing is assumed about the colouring beyond the restriction on the boundary. The conclusion — that some small triangle carries all three colours, and that the number of them is odd — follows from a hypothesis so weak that it is worth checking twice that it says anything at all.

Doors, and a corridor with one way in #

The proof is a walk, and it is the reason the corridor is drawn in the figures.

Call an edge a door when its two ends carry the first two colours. Then count the doors of a single small triangle:

• if its colours are all three, it has exactly one door;
• if its colours are the first two only, it has exactly two;
• if it misses one of the first two colours entirely, it has none.

So every triangle has zero, one or two doors, and it has exactly one precisely when it is three-coloured. That is the observation the whole argument turns on, and it is a matter of listing the cases.

Now walk. Enter the big triangle through a door on the boundary and follow the corridor: on arriving in a triangle with two doors, leave by the one not just used. The walk cannot revisit a triangle — arriving twice would need three doors, and no triangle has three — so it cannot cycle, and since there are finitely many triangles it must stop. It stops only when the current triangle has no other door, which is to say when the triangle carries all three colours.

Where does the parity come from? From the bottom edge. Along it the colours run from the first at one end to the second at the other, and every vertex on it carries one of those two; so the colour changes an odd number of times, and the number of doors on that edge is odd. Every corridor either ends in a three-coloured triangle or comes back out through another boundary door, and the ones that come back out pair the boundary doors up two at a time. An odd number of doors cannot be entirely paired, so at least one corridor ends inside — and a slightly longer version of the same bookkeeping gives the stronger statement that the number of three-coloured triangles is itself odd.

Notice what the argument never does. It never looks at the shape of anything, never uses a distance, and never takes a limit. It is a finite piece of arithmetic about a finite picture, and it can be checked by hand on any given colouring — which is exactly what the figure does before it draws.

The count, done exactly #

The walk shows that at least one three-coloured triangle exists. The stronger claim — that the number of them is odd — is a double count, and it is worth doing because the parity is the part that cannot be weakened.

Count the pairs (small triangle, door of that triangle) in two ways. Summing over triangles gives one for each three-coloured triangle and two for each triangle with the first two colours only, so the total has the same parity as the number of three-coloured triangles. Summing over doors gives two for each interior door — every interior edge belongs to two triangles — and one for each boundary door. So

$$\#\{\text{three-coloured}\} \equiv \#\{\text{boundary doors}\} \pmod 2,$$

and the boundary doors were counted above: an odd number, all of them on the bottom edge, because the other two edges cannot carry both of the first two colours at once.

The two arguments are the same technique used in opposite directions. In Königsberg a parity forbids something; here a parity forces something. What they share is the move of counting one set of objects by summing over two different things it is attached to, which is the whole of double counting as a method.

The same statement, one dimension down #

The lemma has a one-dimensional ancestor that everybody already believes, and seeing it makes the shape of the general statement obvious.

Take a segment, colour its left end with the first colour and its right end with the second, and colour the interior points arbitrarily with those two. Then the number of small segments whose two ends differ is odd, so there is at least one. That is a restatement of the fact that a sign change forces a crossing, which is the intermediate value theorem with the analysis taken out.

The triangle is that argument one dimension up, and the pattern continues: in a tetrahedron cut into small tetrahedra and four-coloured under the corresponding rule, the number of four-coloured pieces is odd. The proof is the same walk through rooms with doors, where a door is now a triangular face carrying the first three colours.

How a colouring forces a fixed point #

The reason the lemma is worth its own rung is that Brouwer’s theorem drops out of it, and the passage is short.

Take a continuous map $f$ of a triangle into itself. Every point has barycentric coordinates — three non-negative numbers summing to one, saying how the point is a weighted average of the corners — and the map changes them. Colour a vertex $v$ with the first colour if the map decreases its first coordinate, the second if it decreases its second, the third otherwise, taking the smallest such index. Two facts follow: the colouring obeys Sperner’s rule, because a point on an edge has a zero coordinate that cannot decrease; and a vertex coloured $i$ has $f$ pushing it away from corner $i$.

Now cut the triangle finer and finer. Each subdivision has a three-coloured small triangle, and its three vertices are pushed away from three different corners at once. As the triangles shrink, those three vertices are forced together, and a point where all three coordinates fail to increase is a point that does not move. Compactness supplies the convergent subsequence, and continuity supplies the conclusion.

The division of labour is worth naming. The lemma does the combinatorial work and is entirely finite; compactness does the limiting work and is the only place infinity enters. Everything that feels topological about the fixed-point theorem is concentrated in that single step.

What the argument costs #

The proof is constructive in a way the topological one is not: it says which triangle to look in, and the corridor is a procedure a person could follow with a pencil.

What it does not promise is that following it is quick. The corridor in the first figure passes through seven triangles out of thirty-six; on a subdivision fine enough to locate a fixed point to three decimal places there are millions of triangles, and nothing in the argument bounds how many of them a corridor visits. The walk is guaranteed to end, and the guarantee says nothing about when.

There is a second cost, and it is the one that catches people out. The lemma finds a three-coloured triangle; the fixed-point theorem needs a limit of them, and a limit needs a subsequence, and choosing a subsequence is exactly the non-constructive step. So the finished proof of Brouwer is constructive in its combinatorial half and not in its analytical half — and the fixed point it produces cannot in general be computed to arbitrary precision by any procedure that reads the map at finitely many points. The same split between a construction and a mere existence recurs wherever a limit is taken at the end of a finite argument.

Where it turns up outside topology #

The lemma travels, and the reason is that its hypothesis is so cheap: any three-way choice made continuously on a triangle is a Sperner colouring in disguise.

The best-known use is splitting a rent. Three housemates must assign three rooms and divide the rent between them; the space of divisions is a triangle, since three prices summing to the total is a point in barycentric coordinates. Colour each vertex of a fine subdivision with the room its owner would choose at those prices, arrange the ownership so the rule is obeyed, and a three-coloured small triangle is a price at which all three people want different rooms. That is an envy-free assignment, and the only assumptions are that each person always prefers a free room to one costing the whole rent and that preferences do not jump.

It is a striking argument because it needs no arithmetic about anybody’s valuation. The cut-and-choose protocols proceed by constructing a division and checking it; this one proceeds by colouring a triangle and pointing at a small piece of it, and the fairness is a corollary of a parity count.

What the picture cannot show #

The colouring is random and the figure draws one of them. The lemma is about all of them, and no drawing can exhibit an odd number of three-coloured triangles for every colouring at once — what the picture offers is one instance and the corridor that explains it, with the counting argument doing the work the drawing cannot.

The subdivision is also coarse on purpose. Thirty-six triangles is enough to show a corridor of seven; a subdivision fine enough for the fixed-point argument would be a grey wash, and the three-coloured pieces in it would be smaller than the dots marking their corners.

And the limit is absent entirely. Every drawn triangle has positive size, and the fixed point is what appears when the size goes to zero. The pictures are of the lemma, which is finite; the theorem is what the lemma becomes when it is applied infinitely often, and that step has no picture.

Where it came from #

Emanuel Sperner proved it in 1928, at twenty-three, and not as a route to Brouwer’s theorem: he wanted a new proof that the dimension of a Euclidean space is a topological invariant, and the lemma was the combinatorial engine of it. The application to fixed points came later, and the application to fair division much later — Francis Su’s rent-splitting argument is from 1999.

That order is the usual one and it is worth noticing. A combinatorial fact proved for one purpose turns out to be the finite skeleton of a theorem in another subject, and then the skeleton is more useful than the theorem, because it can be checked, followed and computed with. The same has happened to the pigeonhole principle, which began as an observation and now carries proofs in half a dozen fields.

The ladder from here #

Below: the fixed-point theorem this proves and the hairy ball theorem, which is the same kind of statement about a different object. Above: the contraction mapping, where an extra hypothesis buys uniqueness and an algorithm, and the cases where the fixed point escapes, which is what happens when the triangle is replaced by a set the lemma does not apply to. Sideways: the crossing rule for a closed curve, whose proof is the same parity, and fair division, where this lemma supplies the existence that the protocols supply by construction.

What makes the hypothesis so weak #

It is worth noticing how little the colouring rule constrains, because that is where the lemma’s strength comes from.

Of the vertices in the first figure, three have no choice, the ones along the edges have two each, and every interior vertex has all three. On a subdivision of side six that is a free choice at fifteen interior vertices and a binary choice at fifteen edge vertices — over a hundred million legal colourings, and the count of three-coloured triangles is odd for every one of them.

A hypothesis that leaves that much freedom and still forces a conclusion is doing something structural rather than arithmetic. What it constrains is only the boundary, and the boundary is where the parity comes from; the interior is free precisely because the walk does not care what it finds there.

A parity that will not be argued with #

The lasting point is how little the argument needs. Doors, a walk that cannot cycle, and a boundary count that comes out odd — no distances, no limits, no continuity, and nothing that could not be checked by hand on any particular case.

Parity arguments have this character generally. An alternating sum that survives every deformation, a permutation whose parity no legal move can flip and a crossing count that decides an inside from an outside are all the same move: find a quantity that is odd, and no amount of rearrangement can make it zero.