The Game of Hex and the Brouwer Fixed-Point Theorem

This post makes no claim of originality—it exists to present an interesting mathematical fact. I will present 2 mathematical theorems

1. The Hex theorem
2. Brouwer's fixed point theorem

and claim their equivalence. For a proof, see David Gale (1979) The Game of Hex and the Brouwer Fixed-Point Theorem, The American Mathematical Monthly, 86:10, 818-827, DOI: 10.1080/00029890.1979.11994922 (behind a paywall...).

First, i will state and "prove" the theorems in everyday language, then give an account of the paper above, still using everyday language.

Theorems in everyday language

Brouwer's fixed point theorem

(From Wikipedia.)

Take an ordinary map of a country, and suppose that that map is laid out on a table inside that country. Some point on the map will exactly correspond to a physical point in the country. This point is sometimes marked "You are here".

Hex theorem

I will put a description of the rules below, although it may be quicker to play a game against AI and guess the rules. Here goes the Theorem:

It is impossible for the game Hex to end in a draw.

The game Hex

(Taken 1:1 from Wikipedia.)

Hex is played on a rhombic grid of hexagons, typically of size 11×11, although other sizes are also possible. Each player has an allocated color, conventionally red and blue, or black and white. Each player is also assigned two opposite board edges. The hexagons on each of the four corners belong to both adjacent board edges.

The players take turns placing a stone of their color on a single cell on the board. The most common convention is for Red or Black to go first. Once placed, stones are not moved, replaced, or removed from the board. Each player's goal is to form a connected path of their own stones linking their two board edges. The player who completes such a connection wins the game.

The end of a game of Hex on a standard 11×11 board. Here, White wins the game.

Intuition on the Hex theorem

In order for white to not have a connected path in the end, black must continuously block white, thereby winning the game. Hence a draw is impossible.

Mathematical Statements

The only statement in need of clarification is Brouwer's fixed point theorem. We require some definitions first.

Definition. (Continuous Function) Intuitively, a continuous function is such that you can trace its graph without lifting your pencil. Some details.

Definition. (closed Disk) We define the closed disk to be the set of points around the origin with magnitude less or equal than one. $D = \{ x \in \Bbb{R}^2 : |x| \le 1 \}$

Theorem. (Brouwer) Every continuous function from a closed disk to itself has at least one fixed point.

So for any $f : D \to D$ continuous, there exists $x \in D$ such that $f(x)=x$.

To relate this to the intuitive version from before, the notion of continuous function from a closed disk to itself corresponds to the map lying within the country. Each physical point is continuously translated (mapped) (for example, in a linear interpolation) to the virtual point on the map. This Illustration also "proves" the Theorem.

A real proof is given, for example, in Agricola, Ilka, and Thomas Friedrich. 2010. Vektoranalysis: Differentialformen in Analysis, Geometrie und Physik. 2., überarbeitete und erweiterte Auflage. SpringerLink Bücher. Wiesbaden: Vieweg+Teubner., paragraph 2.8.

An interpretation

Picture the Hex board as a triangulated disk: each hexagonal cell is a tiny triangle-patch, and the two pairs of opposite edges that get "glued" correspond to a wraparound boundary identification. The blue/red labeling of stones turns into a labeling of the vertices of this triangulation.

"Proof" of equivalence

While both theorems make sense as stated, they may not hold in general: for example, consider the surface of a donut where there are (continuous) rotations around it that map it to itself. I'll try to explain how both statements are equialent, i.e. imply each other.

Hex ⟹ Brouwer

Take a continuous map $f: D \to D$. Lay an $n \times n$ Hex board on top of $D$, so each cell sits at some point $p$, and ask: did $f$ move $p$ mostly left, mostly right, mostly up, or mostly down? Color each cell red if $f$ pushed it more horizontally, blue if more vertically (with a tie-breaking convention at the boundary that respects which edge of the board it's near). Now the Hex theorem says this coloring can't be a draw: either there's a red chain connecting left-to-right or a blue chain connecting top-to-bottom.

The point is: it can be shown that a chain like that forces a contradiction in directions, somewhere along that connecting chain, the "pushed mostly right" cells have to butt up against "pushed mostly left" cells (because the chain reaches both opposite edges, and $f$ maps $D$ into $D$, so it can't push everything off the same side). This clash means there's a cell where $f$ barely moves the point at all, inparticular, in the limit, as you make the board finer and finer ($n \to \infty$), these almost-still points converge (by compactness of $D$) to a fixed point of $f$. So: no draws in Hex $\Rightarrow$ every continuous self-map of the disk has a fixed point.

Brouwer ⟹ Hex

Now suppose, for contradiction, that some filled-up Hex board is a draw: no red chain side-to-side, no blue chain top-to-bottom. From this stone configuration you can build a continuous "potential" function on the disk: roughly, at each point, measure how close you are to red's frontier versus blue's frontier, and use that to define a displacement: push the point in the direction that red would want to advance, scaled by how blocked blue currently is, and vice versa. Because neither side has completed a connection, this displacement function never has a zero: there's always some net direction to push, everywhere on the disk. Composing "current position" with "always nonzero push in a continuous way" gives you a continuous self-map of $D$ that moves every point which gives a map with no fixed point. This directly contradicts Brouwer's theorem. So Brouwer's theorem $\Rightarrow$ a draw is impossible.