Games in Topology (Another Proof of Brouwer’s Fixed Point Theorem)

Theorem (Brouwer’s Fixed Point Theorem, BFPT). Suppose that [tex]B\subset \mathbb{R}^n[/tex] is the closed n-dimensional unit ball and [tex]f\colon B\to B[/tex] is a continuous function. Then there exists a point [tex]x\in B[/tex] such that [tex]f(x)=x[/tex].

Theorem (Jordan’s Curve Theorem) Let [tex]f\colon S^1\to \mathbb{R}^2[/tex] be an embedding of the unit circle to the plane. Then [tex]\mathbb{R}^2=A\cup B\cup C[/tex] where A and B are open and disjoint and [tex]\partial A=\partial B=C=f[S^1][/tex].

Two weeks ago I presented a relatively simple proof of BFPT. Today I will introduce the game Hex and show that at least one player always wins (the game cannot end such that none of the players is in a winning position). Then I will show how this implies BFPT. Then I will show how BFPT implies a version of Jordan’s Curve Theorem and then show how this in turn implies that there is always exactly one winner in Hex.

So the table of contents is:

(1) At least one player wins in Hex implies
(2) a simple proof of BFPT implies
(3) a version of Jordan’s Curve Theorem implies
(4) that at most one player wins in Hex.

In my opinion this is mind-explodingly cool. Some reference:

The Game of Hex and the Brouwer Fixed-Point Theorem
David Gale, The American Mathematical Monthly, Vol. 86, No. 10 (Dec., 1979), pp. 818-827.
The Jordan Curve Theorem Via the Brouwer Fixed Point Theorem
Ryuji Maehara, The American Mathematical Monthly, Vol. 91, No. 10 (Dec., 1984), pp. 641-643 .

Source: HexWiki, licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.

Consider the game Hex: The game board is an approximation of a rhombus filled with hexagons:

(picture is in public domain)

The players put one after another black and white pieces inside the hexagons (one player puts only white pieces and the other only black ones). The black player wins if he manages to build a black path connecting the black sides of the board and the white player wins if she manages to build a white path connecting the white sides. Now the trick is that

Theorem (1) When all hexagons of a Hex board are coloured in black and white, there exists either a white path connecting the white sides or a black path connecting the black sides.

Remark. This clearly means that when the game ends, at least one of the player has won. See Corollary A in the end.

Proof of Theorem (1).
There are several proofs of this theorem on the web, espesially if you have access to Jstor. Let us see the original one given by David Gale. First let H be the following graph: The vertices are the edges of the hexagons of the board and the edges are the edges of the hexagons of the board. Suppose next that the Hex board is colored with black and white stones. Construct a graph G as follows. Vertices of G are vertices of H and edges of G are those edges of H which have differently colored hexagons (or a hexagon and a border) on their different sides. Let me borrow the picture from the Gale’s paper:

x is for black and o is for white

Thus one gets (clearly) a graph with vertices that have degrees 0, 1 and 2. Such graphs are disjoint unions of isolated points, paths and cycles (prove this by induction on the number of vertices). Since there are only four vertices with degree 1, (at the corners) there are exactly two paths with the end-points being at the corners. Following these paths one easily finds either a white path connecting the white regions or a black path connecting the black regions. [tex]\phantom{lolloll}\square[/tex]

Proof of Brouwer’s Fixed Point Theorem (2)
Following Gale, I will present the proof for n=2. Only a minor change in the setting is enough to generalize for all n (one has to generalize Hex to an n-dimensional board and prove Theorem (1) in that setting). Suppose f is a continuous function from the unit square, [tex][0,1]\times [0,1][/tex] to itself. By streching the edges of the borderlines of the hexagons, the game board is easily transformed to be a linear image of this square. Let [tex]\varepsilon>0[/tex]. We shall show that there is a point [tex]x\in [0,1]\times [0,1][/tex] such that [tex]|f(x)-x|\leqslant\sqrt{2}\varepsilon[/tex]. Once we have this, choose such an [tex]x_n[/tex] for each [tex]\varepsilon_n=1/n[/tex] and take a converging subsequence of [tex](x_n)_{n=1}^\infty[/tex] (by compactness). By continuity of f, the limit of this sequence must be a fixed point of f.

In order to find x, let [tex]0<\delta\leqslant\varepsilon[/tex] be such that

[tex]\forall x,y (|x-y|\leqslant\delta\Rightarrow |f(x)-f(y)|\leqslant\varepsilon)[/tex].

Such [tex]\delta[/tex] exists because f is continuous and its domain is compact, so it is uniformly continuous. Let n be a big enough number in order to have [tex]1/n\leqslant\delta[/tex]. Then pick four regions from the square:

[tex]H^+= \{(x_1,x_2)\mid f(x_1)-x_1\geqslant \varepsilon\}[/tex]
[tex]H^-= \{(x_1,x_2)\mid x_1-f(x_1)\geqslant \varepsilon\}[/tex]
[tex]V^+=\{(x_1,x_2)\mid f(x_2)-x_2\geqslant \varepsilon\}[/tex]
[tex]V^-= \{(x_1,x_2)\mid x_2-f(x_2)\geqslant \varepsilon\}[/tex]

Then identify the square with the game board (e.g. by a linear map as explained above) and color a hexagon black, if its middle point is in [tex]H^+\cup H^-[/tex] and white if it is in [tex]V^+\cup V^-[/tex]. By Theorem (1), if all hexagons are colored, then there must be either a black or a white path. W.l.o.g suppose there is a white path. By the definition of [tex]\delta[/tex] a distance between a point in [tex]V^+[/tex] and a point in [tex]V^-[/tex] must be bigger than [tex]\delta[/tex]. Because the hexagons have diameters less than [tex]\delta[/tex], no two hexagons, respectively from [tex]V^+[/tex] and [tex]V^-[/tex], are adjacent. Hence the path cannot intersect both [tex]V^+[/tex] and [tex]V^-[/tex]. That is, the path is contained in either one of them. But since the function f does not take elements out of the square this is a contradiction, because [tex]\delta[/tex] was also chosen to be [tex]\leqslant\varepsilon[/tex] and a top (resp. bottom) element cannot be contained in [tex]V^+[/tex] (resp. [tex]V^-[/tex]). We conclude that there must be a hexagon with the middle point not in any of the four sets [tex]H^+,H^-,V^+,V^-[/tex]. Let the middle point be x. Then [tex]|f(x)-x|\le\sqrt{2}\varepsilon.\quadd \square[/tex]

Theorem (3) Let [tex]h=(h_1,h_2)[/tex] and[tex] v=(v_1,v_2)[/tex] be two functions from the interval [tex][-1,1][/tex] to the square [tex][-1,1]\times [-1,1][/tex] such that

Then the curves h and v meet, i.e. there exist [tex]t,s\in[0,1][/tex] such that [tex]v(t)=h(s)[/tex]

Illustration: the image of the function h (horizontal) is blue and the image of v (vertical) is red:

Proof of (3). Suppose they do not meet. Define the function
[tex]N\colon [-1,1]\times [-1,1]\to \mathbb{R}[/tex]
by
[tex]N(s,t)=\max\{|h_1(t)-v_1(s)|, |h_2(t)-v_2(s)|\}[/tex]
Thus N is the max-norm of the difference. Since there is no fixed point, [tex]N(s,t)[/tex] is always non-zero. Hence we can define the continuous function
[tex]\displaystyle F\colon [-1,1]\times [-1,1]\to [-1,1]\times [-1,1][/tex]
by
[tex]F(s,t)=\left(\frac{h_1(t)-v_1(s)}{N(s,t)},\frac{h_2(t)-v_2(s)}{N(s,t)}\right).[/tex]
F contradicts BFPT, because it does not have a fixed point! Indeed, suppose that there exist [tex]s,t[/tex] such that [tex]F(s,t)=(s,t)[/tex]. Clearly one of the co-ordinates of F(s,t) must have absolute value 1. By [tex]F(s,t)=(s,t)[/tex] this is true for (s,t). Suppose for example that s=-1. Then by definition of [tex]v_1[/tex] we have [tex]v_1(s)=-1[/tex] which implies that the first co-ordinate of [tex]F(s,t),\,F_1(s,t)=\frac{h_1(t)-v_1(s)}{N(s,t)}[/tex] is positive though it was supposed to be -1. The same argument goes for all the other cases, [tex]s=1, t=-1\text{ and }t=1[/tex]. [tex]\square[/tex]

Remark: Using Theorem (3) one is able to deduce the actual Jordan’s Curve Theorem by doing some brute force, see the reference mentioned above.

Theorem (4) At most one player wins in Hex.
Proof of (4) This is a straight consequence of Theorem (3). Suppose on contrary that both players win. Then there are both: a black path connecting the black regions and a white path connecting the white regions. Now construct functions [tex]h,v\colon [-1,1]\to [-1,1]\times [-1,1][/tex] such that h follows the black path and v the white path so that they satisfy the assumptions of Theorem (3). Then the hexagon in which these paths meet (by Theorem (3) they necessarily meet) must be white and black which is impossible. [tex]\square[/tex]

Theorems (1) and (3) have also game theoretical consequeces:

Corollary A Exactly one player wins in Hex, i.e. Hex cannot end in a draw. [tex]\phantom{lolloll}\square[/tex]

Corollary B The player who starts has a winning strategy if the board is symmetric (nxn for some n).
Proof. Use the strategy steeling argument that was used here (Theorem 2) to show this fact for tic-tac-toe: From Corollary A it follows by a surviving argument that one of the players has a winning strategy: if Player 2 does not have a winning strategy on the k:th move, then Player 1 can play so that she doesn’t have it on the (k+1):st move either. If Player 2 had a winning strategy, Player 1 could use it against her. Thus Player 1 has a winning strategy. [tex]\phantom{lolloll}\square[/tex]