Using Brouwer’s Fixed Point Theorem

Abstract

Brouwer’s fixed point theorem from 1911 is a basic result in topology—with a wealth of combinatorial and geometric consequences. In these lecture notes we present some of them, related to the game of HEX and to the piercing of multiple intervals. We also sketch stronger theorems, due to Oliver and others, and explain their applications to the fascinating (and still not fully solved) evasiveness problem.

1 Introduction

The fixed point theorem of Brouwer is one of the most widely known results of topology. It says that every continuous map f: B ^d → B ^d of the d-dimensional closed unit ball to itself has a fixed point, that is, a point x ₀ ∈ B ^d such that f(x ₀) = x ₀.

This result was established by Luitzen Egbertus Jan Brouwer (1881–1960) at the end of his important 1911 paper [20], in which he also introduced the fundamental concept (and proof technique) of the mapping degree. It has many striking and famous applications to problems in Geometry, Analysis, Game Theory and Combinatorics.

Brouwer’s fixed point theorem is in several ways similar to the Borsuk–Ulam theorem from 1933, which has gotten a lot of attention and appreciation for being unusually rich in applications. For example, the 1978 proofs of the 1956 Kneser conjecture by Lovász and by Bárány employed the Borsuk–Ulam Theorem in order to solve a problem about partitioning a set system, or equivalently, bounding the chromatic numbers for a certain class of graphs. This unexpected use of a result from equivariant topology is one of the starting points (probably the most famous one) for the field of “Topological Combinatorics” [11, 46]. We refer to the detailed, elementary exposition in Matoušek’s book “Using the Borsuk–Ulam Theorem” [52]. Current research continues this line of work, using more advanced methods from Equivariant Algebraic Combinatorics; see for example the text “Beyond the Borsuk–Ulam Theorem: The Topological Tverberg Story” [14] in this volume.

In various respects, Brouwer’s theorem is a simpler result than the Borsuk–Ulam theorem: For example, it is very easy to state (as it does not involve symmetry, or a group action), and it is quite easy to prove (see below). It can also easily be derived from the Borsuk–Ulam theorem (see [73]), while indeed it is not as straightforward to obtain “Borsuk–Ulam from Brouwer.”

Just like the Borsuk–Ulam theorem, Brouwer’s theorem has many equivalent versions, as well as powerful and useful extensions. For instance, the Lefschetz fixed point theorem that works for spaces much more general than a ball, the Schauder fixed point theorem that works also for compact balls in infinite-dimensional Banach spaces, the Kakutani fixed point theorem for set-valued maps, and so on. See Shapiro [67] for a friendly introduction to fixed point theorems with Analysis applications in mind.

The striking applications of the Brouwer theorem in Combinatorics and Geometry seem not to be as well known as the applications of the Borsuk–Ulam theorem. In order to help to remedy this, we present three distinct areas of such applications in the three main sections of these lecture notes:

• 1. Brouwer’s theorem can be invoked to prove that the game of HEX can never end without a winner. And indeed, the d-dimensional version of this claim turns out to be equivalent to Brouwer’s theorem! This observation of David Gale in his award-winning 1979 paper [27] may also be counted among the starting points of Topological Combinatorics. In our presentation we not only use this to prove the HEX theorem, but we also give a combinatorial proof of the HEX theorem and derive Brouwer’s theorem from this.

• 2. Some results about hypergraph matchings and transversals have a topological core, to be derived from the Brouwer theorem. Our presentation treats one striking instance, concerning the relation between packing and transversal numbers for systems of d-intervals.

• 3. The Evasiveness conjecture states that every non-trivial monotone graph property is evasive, that is, it does not allow for a query strategy that cannot be tricked into checking all potential edges of a graph in order to establish the property. This conjecture is still open in general, but the special case of a graph on a prime power number of vertices was proved using fixed point theorems of Smith and Oliver. These theorems may be seen as extensions of Brouwer’s. The Appendix to this paper collects and sketches the necessary tools.

Further remarkable applications of Brouwer’s fixed point theorem on geometric problems, not treated here, include the work by Bondarenko and Viazovska [17] on the construction of spherical designs, and the work on center points and regression depth by Amenta et al. [5].

Our presentation is based on lecture notes that were written about fifteen years ago, with a history that for some parts goes back nearly thirty years. These notes can be regarded as a companion or perhaps as a “prequel” to Matoušek’s book [52].

The three main parts do not depend on each other, so they can be read indepenently. We refer to [52] for notation and terminology not explained here.

2 A Game Model for Brouwer’s Fixed Point Theorem

2.1 The Game of HEX

Let’s start with a game: “HEX” is a board game for two players, invented by the ingenious Danish poet, designer and engineer Piet Hein in 1942 [29], and rediscovered in 1948 by the mathematician John Nash [57], who got a Nobel memorial prize in economics in 1994 (for his work on game theory, but not really for this game … ).

HEX, in Hein’s version, is played on a rhombical board, as depicted in the figure.

The rules of the game are simple: There are two players, whom we call White and Black. The players alternate, with White going first. Each move consists of coloring one “grey” hexagonal tile of the board white resp. black. White has to connect the white borders of the board (marked W and W′) by a path of his white tiles, while Black tries to connect B and B′ by a black path. They can’t both win: Any winning path for white separates the two black borders, and conversely. (This isn’t hard to prove—however, the statement is closely related to the Jordan curve theorem, which is trickier than it may seem when judged at first sight: see Exercise 13.)

However, here we concentrate on the opposite statement: There is no draw possible—when the whole board is covered by black and white tiles, then there always is a winner. (This is even true if one of the players has cheated badly and ends up with much more tiles than his/her opponent! It is also true if the board isn’t really “square,” that is, if it has sides of unequal lengths.) Our next figure depicts a final HEX position—sure enough one of the players has won, and the proof of the following “HEX theorem” will give us a systematic method to find out which one.

Theorem 2.1 (The HEX theorem)

If each tile of an (n × m)-HEX board is colored black or white, then either there is a path of white tiles that connects the white borders W and W′, or there is a path of black tiles that connects the black borders B and B′.

Our plan for this section is the following:

• We give a simple proof of the HEX theorem.

• We show that it implies the Brouwer fixed point theorem …

• … and conversely: The Brouwer fixed point theorem implies the HEX theorem.

• Then we prove that one of the players has a winning strategy.

• And then we see that on a square board, the first player can win, while on an uneven board, the player with the longer borders has a strategy to win.

All of this is really quite simple, but it nicely illustrates how a topological theorem enters the analysis of a discrete situation.

Proof of the HEX theorem

For the proof we trace a certain path between the black and the white tiles. It starts in the lower left-hand corner of the HEX board on the edge that separates W and B. Whenever the path reaches a corner of degree 3, there will be both colors present at the corner (due to the edge we reach it from), and so there will be a unique edge to proceed on that does have different colors on its two sides.

Our path can never get stuck or branch or turn back onto itself, otherwise we would have found a vertex that has one or three edges that separate colors, whereas this number clearly has to be even at each vertex. Thus the path can be continued until it leaves the board—that is, until it reaches W′ or B′. But that means that we find a path that connects W to W′, or B to B′, and on its sides keeps a white path of tiles resp. a black path. That is, one of White and Black has won! □

Now this was easy, and (hopefully) fun. We continue with a re-interpretation of the HEX board—in Nash’s version—that buys us two drinks for the price of one:

• (i) a d-dimensional version of the HEX theorem, and

• (ii) the connection to the Brouwer fixed point theorem.

Definition 2.2 (The $\boldsymbol{d}$-dimensional HEX board)

The d-dimensional HEX board is the graph H(n, d) on the vertex set V = {−1, 0, 1, …, n, n + 1}^d, in which two vertices $\boldsymbol{v},\boldsymbol{w} \in V$ are connected by an edge if and only if $\boldsymbol{v} -\boldsymbol{ w} \in \{ 0,1\}^{d} \cup \{ 0,-1\}^{d}$.

The colors for the d-dimensional HEX game are 1, 2, …, d, where we identify “1 = white” and “2 = black.” The interior of the HEX board is given by V ′ = {0, 1, 2, …, n}^d. All the other vertices, in V ∖V ′, form the boundary of the board. The vertices in the boundary of H(n, d) get preassigned colors

$$\displaystyle{\kappa (\boldsymbol{v}) =\kappa (v_{1},\ldots,v_{d})\:=\ \left \{\begin{array}{@{}l@{\quad }l@{}} \min \{i:\, v_{i} = -1\} \quad &\text{if this exists}, \\ \min \{i:\, v_{i} = n + 1\}\quad &\mathrm{otherwise}. \end{array} \right.}$$

Our drawing depicts the 2-dimensional HEX board H(5, 2), which represents a dual graph for the (6 × 6)-board that we used in our previous figures, with the preassigned colors on the boundary.

The d-dimensional HEX game is played between d players who take turns in coloring the interior vertices of H(n, d). The i-th player wins if he¹ achieves a path of vertices of color i that connects a vertex whose i-th coordinate is − 1 to a vertex whose i-th coordinate is n + 1.

Theorem 2.3 (The $\boldsymbol{d}$-dimensional HEX theorem)

For d-dimensional HEX at least one of the players reaches his goal: When all interior vertices of H(d, n) are colored, then at least one player has won.

Proof

The proof that we used for 2-dimensional HEX still works: It just has to be properly translated for the new setting. For this we first check that H(n, d) is the graph of a triangulation $\Delta (n,d)$ of [−1, n + 1]^d, which is given by the clique complex of H(n, d). That is, a set of lattice points S ⊆ {−1, 0, 1, …, n + 1}^d forms a simplex in $\Delta (n,d)$ if and only if the points in S are pairwise connected by edges. To check this, verify that each point x ∈ [−1, n+1]^d lies in the relative interior of a unique simplex, which is given by

$$\displaystyle\begin{array}{rcl}&& \Delta (\boldsymbol{x})\:=\ \mbox{ conv}\big\{\boldsymbol{v} \in \{-1,\ldots,n + 1\}^{d}:\, {}\\ & &\qquad \qquad \qquad \qquad\qquad \lfloor x_{i}\rfloor \leq v_{i} \leq \lceil x_{i}\rceil \mbox{ for all }i, {}\\ & &\qquad \qquad \qquad \qquad\qquad \lfloor x_{i} - x_{j}\rfloor \leq v_{i} - v_{j} \leq \lceil x_{i} - x_{j}\rceil \mbox{ for all }i\neq j\big\}. {}\\ \end{array}$$

Every full-dimensional simplex in $\Delta (n,d)$ has d + 1 vertices. A simplex S in $\Delta (n,d)$ is completely colored if it has all d colors on its vertices. Thus each completely colored d-simplex in $\Delta$ has exactly two completely colored facets, which are (d − 1)-faces of the complex $\Delta (n,d)$. Conversely, every completely colored (d − 1)-face is contained in exactly two completely colored d-simplices—if it is not on the boundary of [−1, n + 1]^d.

With this the (constructive) proof that we gave before for the 2-dimensional HEX theorem generalizes to the following: We start at the d-simplex

$$\displaystyle\begin{array}{rcl} \Delta _{0}& \,:=\,& \mbox{ conv}\{ -\mathbf{1},-\mathbf{1}\,+\,\boldsymbol{e}_{1},-\mathbf{1}\,+\,\boldsymbol{e}_{1} + \boldsymbol{e}_{2},\ \ldots \,-\mathbf{1} + \boldsymbol{e}_{1} +\ldots +\boldsymbol{e}_{d-1},-\mathbf{1} + \boldsymbol{e}_{1} +\ldots +\boldsymbol{e}_{d}\} {}\\ & =& \mbox{ conv}\{ -\mathbf{1},-\mathbf{1} + \boldsymbol{e}_{1},-\mathbf{1} + \boldsymbol{e}_{1} + \boldsymbol{e}_{2},\ \ldots \,-\boldsymbol{e}_{d},\,\mathbf{0}\}, {}\\ \end{array}$$

whose facet ((d − 1)-face) $\mbox{ conv}\{ -\mathbf{1},-\mathbf{1} + \boldsymbol{e}_{1},\ldots,-\boldsymbol{e}_{d-1} -\boldsymbol{e}_{d},-\boldsymbol{e}_{d}\}$ is completely colored. (Verify this!) This simplex is shaded in the following figure for H(5, 2), which depicts the same final position that we considered before.

Now we construct a sequence of completely colored d-dimensional simplices that starts at $\Delta _{0}$: We find the second completely colored (d − 1)-face of $\Delta _{0}$, find the second completely colored d-simplex it is contained in, etc. Thus we find a chain of completely colored d-simplices that ends on the boundary of [−1, n+1]^d—at a different simplex than the one we started from. In particular, the last d-simplex in the chain has a completely colored facet in the boundary, and by construction this facet has to lie in a hyperplane $H_{i}^{+} =\{ \boldsymbol{x}:\, x_{i} = n + 1\}$. At this point we check that every completely colored (d − 1)-simplex in the boundary of H(n, d) is contained in one of the hyperplanes H _i ⁺, with the sole exception of the boundary facet of our starting d-simplex. The chain of d-simplices then provides us with an i-colored path from the i-colored vertex

$$\displaystyle{-\mathbf{1} + \boldsymbol{e}_{1} +\ldots +\boldsymbol{e}_{i-1} \in H_{i}^{-} =\{ \boldsymbol{x}:\, x_{ i} = -1\}}$$

to the i-colored vertex in H _i ⁺: So the i-th player wins. □

Our drawing illustrates the chain of completely colored simplices (shaded) and the sequence of (white) vertices for the winning path that we get from it.

2.2 The Brouwer Fixed Point Theorem

Now we proceed from the discrete mathematics setting of the HEX game to the continuous world of topological fixed point theorems. Here are three versions of the Brouwer fixed point theorem.

Theorem 2.4 (Brouwer fixed point theorem)

The following are equivalent (and true):

(Br1) :

Every continuous map f:  B ^d ⟶  B ^d has a fixed point.

(Br2) :

Every continuous map f:  B ^d ⟶  S ^d−1 has a fixed point.

(Br3) :

Every null-homotopic map f:  S ^d−1 ⟶  S ^d−1 has a fixed point.

(The term null-homotopic that appears here refers to a map that can be deformed to a constant map.)

Proof of the equivalences

(Br1)⇒(Br2) is trivial, since S ^d−1 ⊆ B ^d.

For (Br2)⇒(Br3) let h:  S ^d−1 × [0, 1] ⟶  S ^d−1 be a null-homotopy for f, i.e., a continuous map that interpolates between our original map f and a constant map, with $h(\boldsymbol{x},0) = f(\boldsymbol{x})$ and $h(\boldsymbol{x},1) = \boldsymbol{x}_{0}$ for all $\boldsymbol{x} \in S^{d-1}$. From this we construct a continuous map F:  B ^d ⟶  S ^d−1 that extends f, by

$$\displaystyle{F(\boldsymbol{x})\:=\ \left \{\begin{array}{@{}l@{\quad }l@{}} h( \frac{\boldsymbol{x}} {\vert \boldsymbol{x}\vert },2 - 2\vert \boldsymbol{x}\vert )\quad &\text{ if }\frac{1} {2} \leq \vert \boldsymbol{x}\vert \leq 1, \\ \boldsymbol{x}_{0} \quad &\text{ for }\vert \boldsymbol{x}\vert \leq \frac{1} {2}. \end{array} \right.}$$

This map is continuous, and by (Br2) it has a fixed point, which must lie in the image, that is, in S ^d−1.

For the converse, (Br3)⇒(Br2), let f:  B ^d ⟶  S ^d−1 be continuous. Then the restriction $f\vert _{S^{d-1}}$ is null-homotopic, since $h(\boldsymbol{x};t)\:=\ f((1 - t)\boldsymbol{x})$ provides a null-homotopy. Thus, by (Br3) the map $f\vert _{S^{d-1}}$ has a fixed point, hence so does f.

Finally, we get (Br2)⇒(Br1): If f:  B ^d ⟶  B ^d has no fixed point, then we set $g(\boldsymbol{x})\:=\ \frac{f(\boldsymbol{x})-\boldsymbol{x}} {\vert \,f(\boldsymbol{x})-\boldsymbol{x}\vert }$. This defines a map g:  B ^d ⟶  S ^d−1 that has a fixed point $\boldsymbol{x}_{0} \in S^{d-1}$ by (Br2), with $\boldsymbol{x}_{0} = \frac{f(\boldsymbol{x}_{0})-\boldsymbol{x}_{0}} {\vert \,f(\boldsymbol{x}_{0})-\boldsymbol{x}_{0}\vert }$. But this implies $f(\boldsymbol{x}_{0}) = \boldsymbol{x}_{0}(1 + t)$ for $t\:=\ \vert \,f(\boldsymbol{x}_{0}) -\boldsymbol{x}_{0}\vert> 0$, and this is impossible for $\boldsymbol{x}_{0} \in S^{d-1}$. □

In the following we use the unit cube [0, 1]^d in place of the ball B ^d: It should be clear that the Brouwer fixed point theorem equally applies to self-maps of any domain D that is homeomorphic to the ball B ^d, resp. of the boundary ∂D of such a domain.

Proof of the Brouwer fixed point theorem (“HEX ⇒ (Br1)”).

If f:  [0, 1]^d ⟶  [0, 1]^d has no fixed point, then for some ɛ > 0 we have that $\vert \,f(\boldsymbol{x}) -\boldsymbol{x}\vert _{\infty }\geq \varepsilon$ for all $\boldsymbol{x} \in [0,1]^{d}$ (namely, one can take $\varepsilon \:=\ \min \{\vert \,f(\boldsymbol{x}) -\boldsymbol{x}\vert _{\infty }:\, \boldsymbol{x} \in [0,1]^{d}\}$, which exists since [0, 1]^d is compact).

Furthermore, any continuous function on the compact set [0, 1]^d is uniformly continuous (see e.g. Munkres [59, §27]), hence there exists some δ > 0 such that $\vert \boldsymbol{x} -\boldsymbol{x}'\vert _{\infty } <\delta$ implies $\vert \,f(\boldsymbol{x}) - f(\boldsymbol{x}')\vert _{\infty } <\varepsilon$. We take δ < ɛ (without loss of generality), and then choose n with $\frac{1} {n} <\delta$.

From f, we now define a d-coloring of H(n, d), by setting

$$\displaystyle{\kappa (\boldsymbol{v})\:=\ \min \{i:\, \vert \,f_{i}(\frac{\boldsymbol{v}} {n}) -\frac{v_{i}} {n} \vert \geq \varepsilon \}}$$

for the interior vertices $\boldsymbol{v} \in H(n,d)$, where f _i denotes the ith component of f. This is well-defined, since $\frac{\boldsymbol{v}} {n} \in [0,1]^{d}$, and thus the absolute value of at least one component of $f(\frac{\boldsymbol{v}} {n}) -\frac{\boldsymbol{v}} {n}$ has to be at least ɛ. Now, the d-dimensional HEX theorem guarantees a chain $\boldsymbol{v}^{0},\boldsymbol{v}^{1},\ldots,\boldsymbol{v}^{N}$ of vertices of color i, for some i, where v _i ⁰ = 0 and v _i ^N = n. Furthermore, we know that $\vert \,f_{i}(\frac{\boldsymbol{v}^{k}} {n} ) -\frac{v_{i}^{k}} {n} \vert \geq \varepsilon$ for 0 ≤ k ≤ N. Also, at the ends of the chain we know the signs:

• $f(\tfrac{\boldsymbol{v}^{0}} {n} ) \in [0,1]^{d}$ implies $f_{i}(\tfrac{\boldsymbol{v}^{0}} {n} ) \geq 0$ and hence $f_{i}(\tfrac{\boldsymbol{v}^{0}} {n} ) -\tfrac{v_{i}^{0}} {n} \geq \varepsilon$, and

• $f(\tfrac{\boldsymbol{v}^{N}} {n} ) \in [0,1]^{d}$ implies $f_{i}(\tfrac{\boldsymbol{v}^{N}} {n} ) \leq 1$ and hence $f_{i}(\tfrac{\boldsymbol{v}^{N}} {n} ) -\tfrac{v_{i}^{N}} {n} \leq -\varepsilon$.

It follows that for some k ∈ {1, 2, …, N} we must have a sign change:

• $f_{i}(\tfrac{\boldsymbol{v}^{k-1}} {n} ) -\tfrac{v_{i}^{k-1}} {n} \geq \varepsilon$ and $f_{i}(\tfrac{\boldsymbol{v}^{k}} {n} ) -\tfrac{v_{i}^{k}} {n} \leq -\varepsilon$.

All these facts taken together provide a contradiction, since

• $\vert \tfrac{\boldsymbol{v}^{k-1}} {n} -\tfrac{\boldsymbol{v}^{k}} {n} \vert _{\infty } = \tfrac{1} {n} <\delta,$

whereas

$$\displaystyle{\vert \,f(\tfrac{\boldsymbol{v}^{k-1}} {n} )-f(\tfrac{\boldsymbol{v}^{k}} {n} )\vert _{\infty }\geq \vert \,f_{i}(\tfrac{\boldsymbol{v}^{k-1}} {n} )-f_{i}(\tfrac{\boldsymbol{v}^{k}} {n} )\vert \geq 2\varepsilon -\vert \tfrac{v_{i}^{k-1}} {n} -\tfrac{v_{i}^{k}} {n} \vert \geq 2\varepsilon -\tfrac{1} {n}> 2\varepsilon -\delta>\varepsilon.}$$

□

Proof of the equivalences

that the Brouwer fixed point theorem implies the HEX theorem (“Br1 ⇒ HEX”). Assume we have a coloring of H(n, d). We use it to define a map [0, n]^d ⟶  [0, n]^d, as follows: On the points in {0, 1, …, n}^d we define

$$\displaystyle{f(\boldsymbol{v}) = \left \{\begin{array}{@{}l@{\quad }l@{}} \boldsymbol{v} + \boldsymbol{e}_{i}\quad &\text{if }\boldsymbol{v}\text{ has color }i\text{, and there is a path on vertices of color}i \\ \quad &\text{that connects }\boldsymbol{v}\text{ to a vertex }\boldsymbol{w}\text{ with }w_{i} = 0 \\ \boldsymbol{v} -\boldsymbol{e}_{i}\quad &\text{if }\boldsymbol{v}\text{ has color }i\text{, but there is no such path.} \end{array} \right.}$$

If for the given coloring there is no winning path for HEX, then these definitions do not map any point $\boldsymbol{v}$ outside [0, n]^d. Hence this by linear extension defines a simplicial map f:  [0, n]^d ⟶  [0, n]^d on the simplices of the triangulation $\Delta (n,d)$ that we have considered before.

The following two observations now give us a contradiction, showing that this f cannot have a fixed point:

• If $\Delta = \mbox{ conv}\{\boldsymbol{v}^{0},\boldsymbol{v}^{1},\boldsymbol{v}^{2},\ldots,\boldsymbol{v}^{d}\} \subseteq \mathbb{R}^{d}$ is a simplex and $f: \ \Delta \ \longrightarrow \ \mathbb{R}^{d}$ is a linear map defined by $f(\boldsymbol{v}^{i}) = \boldsymbol{v}^{i} + \boldsymbol{w}^{i}$, then f has a fixed point on $\Delta$ if and only if $\mathbf{0} \in \mbox{ conv}\{\boldsymbol{w}^{0},\ldots,\boldsymbol{w}^{d}\}$.

• If $\boldsymbol{v},\boldsymbol{v}'$ are adjacent vertices, then we cannot get $f(\boldsymbol{v}) = \boldsymbol{v} -\boldsymbol{e}_{i}$ and $f(\boldsymbol{v}') = \boldsymbol{v}' + \boldsymbol{e}_{i}$. Hence for each simplex of $\Delta (n,d)$, all the vectors $\boldsymbol{w}^{i}$ lie in one orthant of $\mathbb{R}^{d}$! □

2.3 The Joy of HEX: Who Wins?

So, who can win the 2-dimensional HEX game? A simple but ingenious argument due to John Nash, known as “stealing a strategy,” shows that on a square board the first player (“White”) always has a winning strategy. In the following we first define winning strategies, then show that one of the players has one, and finally conclude that the first player has one. Still: The proof will be non-constructive, and we don’t know how to win HEX. So, the game still remains interesting …

Definition 2.5

A strategy is a set of rules that tells one of the players which move to choose (i.e., which tile to color) for every legal position on the board. A winning strategy here guarantees to lead to a win, starting from an empty board, for all possible moves of the opponent.

A position of the HEX game is a board on which some tiles may have been colored white or black, together with the information who moves next (unless all tiles are colored). A position is legal if it can occur in a HEX game: That is, if either White moves next, and the numbers of white and black tiles agree, or if Black moves next, and White has one more tile.

A winning position for White is a position such that White has a winning strategy that tells him how to proceed (for arbitrary moves of Black) and guarantees a win. Similarly, a winning position for Black has a winning strategy that guarantees to lead Black to a win.

Lemma 2.6

Every (legal) position for HEX is either a winning position for White or a winning position for Black.

Proof

Here we proceed by induction on the number g of “grey” tiles (i.e., “free” positions on the board). If no grey tiles are present (g = 0), then one of the players has won—by the HEX theorem.

If g > 0 and White is to move, then any move that White could choose reduces g, and thus (by induction) produces a winning position for one of the players. If there is a move that leads to a winning position for White, then this is really nice and great for White: This makes the present position into a winning position for White, and any such move can be used for a winning position for White. Otherwise—too bad: If every possible move for White produces a winning position for Black, then we are at a winning position for Black already.

And the same argument applies for g > 0 if Black is to move. □

Of course, the argument given here is much more general: Essentially we have proved that for any finite deterministic 2-person game without a draw and with “complete information” there is a winning strategy for one of the players. (This is a theorem of Zermelo, which was rediscovered by von Neumann and Morgenstern). Furthermore, for games where a draw is possible either one player has a winning strategy, or both players can force a draw. We refer to Exercise 12, and to Blackwell and Girshick [13, p. 21].

For HEX, Lemma 2.6 shows that at the beginning (for the starting position, where all tiles are grey, and White is to move), there is a winning strategy either for White or for Black. But who is the winner?

Our first attempt might be to follow the proof of Lemma 2.6. Only for the 2 × 2 board this can be done:

In this drawing, you can decide for every position whether it is a winning position for White or for Black, starting with the bottom row (g = 0) that has three winning positions for each player, ending at the top node (g = 4), which turns out to be a winning position for White.

For larger boards, this approach is hopeless—after all, there are $\binom{n^{2}}{\lfloor n^{2}/2\rfloor }$ final positions to classify for “g = 0,” and from this one would have to work one’s way up to the top node of a huge tree (of height n ²). Nevertheless, people have worked out winning strategies for White on the n × n boards for n ≤ 5 (see Gardner [28]).

Theorem 2.7

For the HEX game played on a HEX board with equal side lengths, White (the first player) has a winning strategy.

Proof

Assume not. Then by Lemma 2.6 Black has a winning strategy. But then White can start with an arbitrary move, and then—using the symmetry of the board and of the rules—just ignore his first tile, and follow Black’s winning strategy “for the second player.” This strategy will tell White always which move to take. Here the “extra” white tiles cannot hurt White: If the move for White asks to occupy a tile that is already white, then an arbitrary move is fine for White. But this “stealing a strategy” argument produces a winning strategy for White, contradicting our assumption! □

Notes Gale’s beautiful paper [27] was the source and inspiration for our treatment of Brouwer’s fixed point theorem in terms of the HEX game. Nash’s analysis for the winning strategies for HEX is from Gardner’s classical account in [28], some of which reappears in Milnor’s [57]. See also the accounts in Jensen and Toft [37, Sect. 17.14], and in Berlekamp, Conway and Guy [9, p. 680], where other cases of “strategy stealing” are discussed. (A theoretical set-up for this is in Hales and Jewett [33, Sect. 3].)

The traditional combinatorial approach to the Brouwer fixed point theorem is via Sperner’s lemma [71]; see e.g. Exercise 4 below and the presentation in [1]. Lovász’s [48] matroid version of Sperner’s lemma in Exercise 5 was further generalized by Lindström [45]. Kryński [44], however, showed that these results can easily be derived from earlier results.

A more geometric version of the combinatorial lemmas is given by Mani [50].

Exercises

• 1. Stir your coffee cup. Show that the (moving, but flat) surface has at every moment at least one point that stands still (has velocity zero).

• 2. Prove that if you tear a sheet of paper from your notebook, crumble it into a small ball, and put that down on your notebook, then at least one point of the sheet comes to rest exactly on top of its original position.

  Could it happen that there are exactly two such points?

• 3. In the proof of the Brouwer fixed point theorem (Theorem 2.4, (Br2)⇒(Br3)), we could have tried to simply put $F(\boldsymbol{x})\:=\ h( \frac{\boldsymbol{x}} {\vert \boldsymbol{x}\vert },1 -\vert \boldsymbol{x}\vert )$. Is this continuous?

• 4.

  • (a) Prove “Sperner’s Lemma” [71]: Let $\Delta$ be a triangulation of the d-dimensional sphere and let us color the vertices of $\Delta$ using d + 1 colors. Then $\Delta$ has an even number of colorful facets (meaning d-faces containing vertices of all colors).

  • (b) Show that Sperner’s Lemma implies the Brouwer fixed point theorem.

• 5.

  • (a) Let $\Delta$ be a triangulation of a d-dimensional manifold with vertex set V. Assume that a matroid M of rank d + 1 without loops is defined on V. If $\Delta$ has a facet that is a basis of M then it has at least two such facets. (Lovász [48])

  • (b) Show that part (a) implies Sperner’s Lemma, and hence also Brouwer’s theorem.

• 6. Let B _E = 2^E ∖{∅, E} be the poset of all proper subsets of a finite set E, ordered by containment. Show that if an order-preserving map f:  B _E → B _E does not have a fixed point then it is surjective, and hence an automorphism.

• 7. Let P = B _E ∖{A}, for some proper subset A.

  • (a) Give a quick proof that P has the fixed point property, meaning that any order-preserving self-map has a fixed point.

  • (b) Give a slow proof, not using topology, that P has the fixed point property.

• 8. For HEX on a 3 × 3 board, how large is the tree of possible positions?

• 9. Can you write a computer program that plays HEX and wins (sometimes) [22]?

• 10. For d-dimensional HEX, is there always some “short” winning path? Show that for every d ≥ 2 there is a constant c _d such that for all n there is a final configuration such that only one player wins, but his shortest path uses more than c _d ⋅ n ^d tiles.

• 11. Construct an algorithm that, for given ɛ > 0 and f:  [0, 1]² ⟶  [0, 1]², calculates a point x ₀ ∈ [0, 1]² with | f(x ₀) − x ₀ | < ɛ. [27, p. 827]

• 12. If in a complete information two player game a draw is possible, argue why either one of the players has a winning strategy, or both can force at least a draw.

• 13. Prove that for 2-dimensional HEX, not both players can win! For this, prove and use the “polygonal Jordan curve theorem”: any simple closed polygon in the plane uniquely divides the plane into an “inside” region and an “outside” region.

  (The general Jordan curve theorem for simple “Jordan arcs” in the plane has extensive discussions in many books; see for example Munkres [59], Stillwell [72, Sect. 0.3], or Thomassen [75].)

• 14. On an (m × n)-board that is not square (that is, m ≠ n), the player who gets the longer sides, and hence the shorter distance to bridge by a winning path, has a winning strategy. Our figure illustrates the case of a (6 × 5)-board, where the claim is that Black has a winning strategy.

  • (i) Show that for this, it is sufficient to consider the case where m = n + 1 (i.e., the second player Black, who gets the longer side, has a sure win).

    

  • (ii) Show that in the situation of (i), Black has the following winning strategy. Label the tiles in the “symmetric” way that is indicated by the figure, such that there are two tiles of each label. The strategy for Black is to always take the second tile that has the same label as the one taken by White. Why will this strategy always win for Black? (Hint: You will need the Jordan curve theorem.)

    (This is in Gardner [28] and in Milnor [57], but neither source gives the proof. You’ll have to work yourself!)

3 Piercing Multiple Intervals

3.1 Packing Number and Transversal Number

Let $\mathcal{S}$ be a system of subsets of a ground set X; both $\mathcal{S}$ and X may generally be infinite. The packing number of $\mathcal{S}$, usually denoted by $\nu (\mathcal{S})$ and often also called the matching number , is the maximum cardinality of a system of pairwise disjoint sets in $\mathcal{S}$:

$$\displaystyle{\nu (\mathcal{S}) =\sup \{ \vert \mathcal{M}\vert:\, \mathcal{M}\subseteq \mathcal{S},\,M_{1} \cap M_{2} = \varnothing \mbox{ for all }M_{1},M_{2} \in \mathcal{M},M_{1}\neq M_{2}\}.}$$

The transversal number or piercing number of $\mathcal{S}$ is the smallest number of points of X that capture all the sets in $\mathcal{S}$:

$$\displaystyle{\tau (\mathcal{S}) =\min \{ \vert T\vert:\, T \subseteq X,\,S \cap T\neq \varnothing \mbox{ for all }S \in \mathcal{S}\}.}$$

A subsystem $\mathcal{M}\subseteq \mathcal{S}$ of pairwise disjoint sets is usually called a matching (this refers to the graph-theoretical matching, which is a system of pairwise disjoint edges), and a set T ⊆ X intersecting all sets of $\mathcal{S}$ is referred to as a transversal of $\mathcal{S}$. Clearly, any transversal is at least as large as any matching, and so always

$$\displaystyle{\nu (\mathcal{S}) \leq \tau (\mathcal{S}).}$$

In the reverse direction, very little can be said in general, since $\tau (\mathcal{S})$ can be arbitrarily large even if $\nu (\mathcal{S}) = 1$. As a simple geometric example, we can take the plane as the ground set of $\mathcal{S}$ and let the sets of $\mathcal{S}$ be lines in general position. Then ν = 1, since every two lines intersect, but $\tau \geq \frac{1} {2}\vert \mathcal{S}\vert$, because no point is contained in more than two of the lines.

One of the basic general questions in combinatorics asks for interesting special classes of set systems where the transversal number can be bounded in terms of the matching number.² Many such examples come from geometry. Here we restrict our attention to one particular type of systems, the d-intervals, where the best results have been obtained by topological methods.

Fractional packing and transversal numbers

Before introducing d-intervals, we mention another important parameter of a set system, which always lies between ν and τ and often provides useful estimates for ν or τ. This parameter can be introduced in two seemingly different ways. For simplicity, we restrict ourselves to finite set systems (on possibly infinite ground sets). A fractional packing for a finite set system $\mathcal{S}$ on a ground set X is a function $w: \ \mathcal{S}\ \longrightarrow \ [0,1]$ such that for each x ∈ X, we have $\sum _{S\in \mathcal{S}:\,x\in S}w(S) \leq 1$. The size of a fractional packing w is $\sum _{S\in \mathcal{S}}w(S)$, and the fractional packing number $\nu ^{{\ast}}(\mathcal{S})$ is the supremum of the sizes of all fractional packings for $\mathcal{S}$. So in a fractional packing, we can take, say, one-third of one set and two-thirds of another, but at each point, the fractions for the sets containing that point must add up to at most 1. We always have $\nu (\mathcal{S}) \leq \nu ^{{\ast}}(\mathcal{S})$, since a packing $\mathcal{M}$ defines a fractional packing w by setting w(S) = 1 for $S \in \mathcal{M}$ and w(S) = 0 otherwise.

Similar to the fractional packing, one can also introduce a fractional version of a transversal. A fractional transversal for a (finite) set system $\mathcal{S}$ on a ground set X is a function φ:  X ⟶  [0, 1] attaining only finitely many nonzero values such that for each $S \in \mathcal{S}$, we have ∑ _{x ∈ S} φ(x) ≥ 1. The size of a fractional transversal φ is ∑ _{x ∈ X} φ(x), and the fractional transversal number $\tau ^{{\ast}}(\mathcal{S})$ is the infimum of the sizes of fractional transversals.

By the duality theorem of linear programming (or by the theorem about separation of disjoint convex sets by a hyperplane), it follows that $\nu ^{{\ast}}(\mathcal{S}) =\tau ^{{\ast}}(\mathcal{S})$ and thus that

$$\displaystyle{\nu (\mathcal{S})\ \leq \ \nu ^{{\ast}}(\mathcal{S})\ =\ \tau ^{{\ast}}(\mathcal{S})\ \leq \ \tau (\mathcal{S})}$$

for any finite set system $\mathcal{S}$.

When trying to bound τ in terms of ν, in many instances it proved very useful to bound ν ^∗ as a function of ν first, and then τ in terms of τ ^∗. The proof presented below follows a somewhat similar approach.

3.2 The d-Intervals

Let I ₁, I ₂, …, I _d be disjoint parallel segments in the plane. (We may assume without loss of generality that they are horizontal unit length intervals at distinct heights/y-coordinates.) A set $J \subset \bigcup _{i=1}^{d}I_{i}$ is a d-interval if it intersects each I _i in a closed interval. We denote this intersection by J _i and call it the ith component of J. The following drawing shows a 3-interval:

Intersection and piercing for d-intervals are taken in the set-theoretical sense: Two d-intervals intersect if, for some i, their ith components intersect.

The 1-intervals, which are just intervals in the usual sense, behave nicely with respect to packing and piercing, as for any family $\mathcal{F}$ of intervals, we have $\nu (\mathcal{F}) =\tau (\mathcal{F})$. (This is well-known and easy to prove: Exercise 1!) This, however, does not extend to d-intervals. For example, the family $\mathcal{F}$ of three 2-intervals

has $\nu (\mathcal{F}) = 1$ while $\tau (\mathcal{F}) = 2$. By taking multiple copies of this family, one obtains families with τ = 2ν for all values of ν.

Gyárfás and Lehel [31] showed by elementary methods that for any d and any family $\mathcal{F}$ of d-intervals, $\tau (\mathcal{F})$ can be bounded by a function of $\nu (\mathcal{F})$ (also see [32]). Their function was rather large (about ν ^d! for d fixed). After an initial breakthrough by Tardos [74], who proved $\tau (\mathcal{F}) \leq 2\nu (\mathcal{F})$ for any family of 2-intervals, Kaiser [39] obtained the following result:

Theorem 3.1 (The Tardos–Kaiser theorem on $\boldsymbol{d}$-intervals)

Every family $\mathcal{F}$ of d-intervals, d ≥ 2, has a transversal of size at most $(d^{2} - d) \cdot \nu (\mathcal{F})$ .

Here we present a proof using the Brouwer fixed point theorem. Alon [2] found a short non-topological proof of the slightly weaker bound $\tau (\mathcal{F}) \leq 2d^{2}\nu (\mathcal{F})$.

Proof

Let $\mathcal{F}$ be a fixed system of d-intervals with $\nu (\mathcal{F}) = k$, and let t = t(d, k) be a suitable (yet undetermined) integer. The general plan of the proof is this: Assuming that there is no transversal of $\mathcal{F}$ of size dt, we show by a topological method that the fractional packing number $\nu ^{{\ast}}(\mathcal{F})$ is at least t + 1. Then a simple combinatorial argument proves that the packing number $\nu (\mathcal{F})$ is at least $\frac{t+1} {d}$, which leads to $t <d^{2} \cdot \nu (\mathcal{F})$. Sharper combinatorial reasoning in this step leads to the slightly better bound in the theorem.

Our candidates for a transversal of $\mathcal{F}$ are all sets T with each T _i = T ∩ I _i having exactly t points; so | T | = td. For technical reasons, we also permit that some of the t points in I _i coincide, so T can be a multiset.

The letter T could also abbreviate a trap. The trap is set to catch all the d-intervals in $\mathcal{F}$, but if it is not set well enough, some of the d-intervals can escape. Each of them escapes through a hole in the trap, namely through a d-hole. The points of T _i cut the segment I _i into t + 1 open intervals (some of them may be empty), and these are the holes in I _i ; they are numbered 1 through t + 1 from left to right. A d-hole consists of d holes, one in each I _i . The type of a d-hole H is the set {(1, j ₁), (2, j ₂), …, (d, j _d )}, where j _i ∈ [t+1] is the number of the hole in I _i contained in H. A d-interval $J \in \mathcal{F}$ escapes through a d-hole H if it is contained in the union of its holes. The drawing shows a 3-hole, of type {(1, 2), (2, 4), (3, 4)}, and a 3-interval escaping through it:

Let $\mathcal{H}_{0}$ be the hypergraph with vertex set [d] × [t+1] and with edges being all possible types of d-holes; for example, the hole in the picture yields the edge {(1, 2), (2, 4), (3, 4)}. So $\mathcal{H}_{0}$ is a complete d-partite d-uniform hypergraph. By saying that a $J \in \mathcal{F}$ escapes through an edge H of $\mathcal{H}_{0}$, we mean that J escapes through the d-hole (uniquely) corresponding to H.

Next, we define weights on the edges of $\mathcal{H}_{0}$; these weights depend on the set T (and also on $\mathcal{F}$, but this is considered fixed). The weight of an edge $H \in \mathcal{H}_{0}$ is

$$\displaystyle{q_{H} =\sup \{ \mbox{ dist}(J,T):\, J \in \mathcal{F},J\mbox{ escapes through }H\}.}$$

Here dist(J, T): = min_{1 ≤ i ≤ d} {dist(J _i , T _i )} and dist(J _i , T _i ) is the distance of the ith component of J to the closest point of T _i . Thus q _H can be interpreted as the largest margin by which some d-interval from $\mathcal{F}$ escapes through H. If no members of $\mathcal{F}$ escape through H, we define q _H as 0. Note that this is the only case where q _H = 0. Otherwise, if anything escapes, it does so by a positive margin, since we are dealing with closed intervals.

From the edge weights, we derive weights of vertices: The weight w _v of a vertex v = (i, j) is the sum of the weights of the edges of $\mathcal{H}_{0}$ containing v. These weights, too, are functions of T; to emphasize this, we write w _v = w _v (T).

Lemma 3.2

For any d ≥ 1, t ≥ 1, and any $\mathcal{F}$ , there is a choice of  T such that all the vertex weights w _v (T), v ∈ [d] × [t+1], coincide.

It is this lemma whose proof is topological. We postpone that proof and finish the combinatorial part first.

Let us suppose that a trap T was chosen as in the lemma, with w _v (T) = W for all v. If W = 0 then T is a transversal, since all edge weights are 0 and no $J \in \mathcal{F}$ escapes. So suppose that W > 0.

Let $\mathcal{H} = \mathcal{H}(T) \subseteq \mathcal{H}_{0}$, the escape hypergraph of T, consist of the edges of $\mathcal{H}_{0}$ with nonzero weights. Note that

$$\displaystyle{ \nu (\mathcal{H}) \leq \nu (\mathcal{F}). }$$

(1)

Indeed, given a matching $\mathcal{M}$ in $\mathcal{H}$, for each edge $H \in \mathcal{M}$ choose a $J \in \mathcal{F}$ escaping through H—this gives a matching in $\mathcal{F}$.

We note that the re-normalized edge weights $\tilde{q}_{H} = \frac{1} {W}\,q_{H}$ determine a fractional packing in $\mathcal{H}$ (since the weights at each vertex sum up to 1). For the size of this fractional packing, which is the total weight of all vertices, we find by double counting

$$\displaystyle{\sum _{H\in \mathcal{H}}\tilde{q}_{H} = \frac{1} {d}\sum _{H\in \mathcal{H}}\sum _{v\in H}\tilde{q}_{H} = \frac{1} {d}\sum _{v\in [d]\times [t+1]}\frac{w_{v}} {W} = \frac{1} {d}\sum _{v}1 = t + 1.}$$

As $\nu ^{{\ast}}(\mathcal{H})$ is the supremum of the weights of all fractional packings, and $\tilde{q}_{H}$ is a particular fractional packing, this yields $\nu ^{{\ast}}(\mathcal{H}) \geq \sum _{H\in \mathcal{H}}\tilde{q}_{H} = t + 1$.

The last step is to show that $\nu (\mathcal{H})$ cannot be small if $\nu ^{{\ast}}(\mathcal{H})$ is large. Here is a simple argument leading to a slightly suboptimal bound, namely $\nu (\mathcal{H}) \geq \frac{1} {d}\,\nu ^{{\ast}}(\mathcal{H})$.

Given a fractional matching $\tilde{q}$ of size t + 1 in $\mathcal{H}$, a matching can be obtained by the following greedy procedure: Pick an edge H ₁ and discard all edges intersecting it, pick H ₂ among the remaining edges, etc., until all edges are exhausted. The $\tilde{q}$-weight of H _i plus all the edges discarded with it is at most d = | H _i |, while all edges together have weight t + 1. Thus, the number of steps, and also the size of the matching {H ₁, H ₂, …}, is at least $\lceil \frac{t+1} {d} \rceil$.

If we set $t = d \cdot \nu (\mathcal{F})$, we get $\nu (\mathcal{H})>\nu (\mathcal{F})$, which contradicts (1). Therefore, for this choice of t, all the vertex weights must be 0, and T as in Lemma 3.2 is a transversal of $\mathcal{F}$ of size at most $d^{2}\nu (\mathcal{F})$.

The improved bound $\tau (\mathcal{F}) \leq (d^{2} - d) \cdot \nu (\mathcal{F})$ for d ≥ 3 follows similarly using a theorem of Füredi [26], which implies that the matching number of any d-uniform d-partite hypergraph $\mathcal{H}$ satisfies $\nu ^{{\ast}}(\mathcal{H}) \leq (d - 1)\nu (\mathcal{H})$. (For d = 2, a separate argument needs to be used, based on a theorem of Lovász stating that $\nu ^{{\ast}}(G) \leq \frac{3} {2}\nu (G)$ for all graphs G.) The Tardos–Kaiser Theorem 3.1 is proved. □

Proof of Lemma 3.2

Let σ ^t denote the standard t-dimensional simplex in $\mathbb{R}^{t+1}$, i.e. the set $\{\boldsymbol{x} \in \mathbb{R}^{t+1}:\, x_{j} \geq 0,\,x_{1} + \cdots + x_{t+1} = 1\}$. A point $\boldsymbol{x} \in \sigma ^{t}$ defines a t-point multiset {z ₁, z ₂, …, z _t } ⊂ [0, 1], z ₁ ≤ z ₂ ≤ ⋯ ≤ z _t , by setting z _k = ∑ _{j = 1} ^k x _j . Here is a picture for t = 2:

A candidate transversal T with t points in each I _i can thus be defined by an ordered d-tuple $(\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{d})$ of points, $\boldsymbol{x}_{i} \in \sigma ^{t}$, where $\boldsymbol{x}_{i}$ determines T _i . Such an ordered d-tuple can be regarded as a single point $\boldsymbol{x}$ in the Cartesian product P = σ ^t ×σ ^t ×⋯ ×σ ^t = (σ ^t)^d. To each $\boldsymbol{x} \in P$, we have thus assigned a candidate transversal $T(\boldsymbol{x})$.

For each vertex v = (i, j) of the hypergraph $\mathcal{H}_{0}$, we define the function $g_{ij}: \,P\ \rightarrow \ \mathbb{R}$ by $g_{ij}(\boldsymbol{x}) = w_{(i,j)}(T(\boldsymbol{x}))$, where w _v (T) is the vertex weight. This is a continuous function of $\boldsymbol{x}$, since the edge weights q _H and hence the vertex weights $w_{(i,j)}(T(\boldsymbol{x}))$ change continuously when $T(\boldsymbol{x})$ moves—even if by this move new edges from $\mathcal{F}$ escape, or fail to escape, through a hole: If this is due to a small change of $T(\boldsymbol{x})$, then they escape, or fail to escape, by a narrow margin.

We note that for each $\boldsymbol{x}$, the sum

$$\displaystyle{S_{i}(\boldsymbol{x}) =\sum _{ j=1}^{t+1}g_{ ij}(\boldsymbol{x})}$$

is independent of i; this is because $S_{i}(\boldsymbol{x})$ equals the sum of the weights of all edges. So we can write just $S(\boldsymbol{x})$ instead of $S_{i}(\boldsymbol{x})$.

If there is an $\boldsymbol{x} \in P$ with $S(\boldsymbol{x}) = 0$, then all the vertex weights $w_{(i,j)}(T(\boldsymbol{x}))$ are 0 and we are done. Otherwise, we define the normalized functions

$$\displaystyle{f_{ij}(\boldsymbol{x}) = \frac{1} {S(\boldsymbol{x})}\,g_{ij}(\boldsymbol{x}).}$$

For each i, $f_{i1}(\boldsymbol{x}),\ldots,f_{i(t+1)}(\boldsymbol{x})$ are nonnegative and sum up to 1, and so they are the coordinates of a point in the standard simplex σ ^t. All the maps f _ij together can be regarded as a map f:  P →  P. To prove the lemma, we need to show that the image of f contains the point of P with all the d(t + 1) coordinates equal to $\frac{1} {t+1}$.

The product P is a convex polytope, and its nonempty faces are exactly all Cartesian products F ₁ × F ₂ ×⋯ × F _d , where the F ₁, …, F _d are nonempty faces of the factors σ ^t, …, σ ^t of P = σ ^t ×σ ^t ×⋯ ×σ ^t (Exercise 2). We note that for any face F of P, we have f(F) ⊆ F: Indeed, any face G of σ ^t has the form $G =\{ \boldsymbol{x} \in \sigma ^{t}:\, x_{i} = 0\mbox{ for all }i \in I\}$, for some index set I, and the faces of P are products of faces G of this form. So it suffices to know that $f_{ij}(\boldsymbol{x}) = 0$ whenever $(\boldsymbol{x}_{i})_{j} = 0$. This holds, since $(\boldsymbol{x}_{i})_{j} = 0$ means that the jth hole in I _i is empty, so nothing can escape through that hole, and thus $f_{ij}(\boldsymbol{x}) = 0$. The proof of Lemma 3.2 is now reduced to the following statement.

Lemma 3.3

Let P be a convex polytope and let f:  P →  P be a continuous map satisfying f(F) ⊆ F for each face ³ F of P. Then f is surjective.

Proof

Since the condition is hereditary for faces, it suffices to show that each point $\boldsymbol{y}$ in the interior of P has a preimage. For contradiction, suppose that some $\boldsymbol{y} \in \mbox{ int}P$ is not in the image of f. For $\boldsymbol{x} \in P$, consider the ray that starts at $f(\boldsymbol{x})$ and passes through $\boldsymbol{y}$, and let $g(\boldsymbol{x})$ be the unique intersection of that ray with the boundary of P.

This g is a well-defined and continuous map P →  P, and by Brouwer’s fixed point theorem, there is an $\boldsymbol{x}_{0} \in P$ with $g(\boldsymbol{x}_{0}) = \boldsymbol{x}_{0}$. The point $\boldsymbol{x}_{0}$ lies on the boundary of P, in some proper face F. But $f(\boldsymbol{x}_{0})$ cannot lie in F, because the segment $\boldsymbol{x}_{0}f(\boldsymbol{x}_{0})$ passes through the point $\boldsymbol{y}$ outside F—a contradiction. □

3.3 Lower Bounds

It turns out that the bound in Theorem 3.1 is not far from being the best possible. In particular, for $\nu (\mathcal{F}) = 1$ and d large, the transversal number can be near-quadratic in d, which is rather surprising. For all k and d, systems $\mathcal{F}$ of d-intervals can be constructed with $\nu (\mathcal{F}) = k$ and

$$\displaystyle{\tau (\mathcal{F}) \geq c\, \frac{d^{2}} {(\log d)^{2}}\,k}$$

for a suitable constant c > 0 (Matoušek [51]). The construction involves an extension of a construction due to Sgall [66] of certain systems of set pairs. Here we outline a (non-topological!) proof of a somewhat simpler result concerning families of homogeneous d-intervals, which are unions of at most d closed intervals on the real line. These are more general than the d-intervals, but an upper bound only slightly weaker than Theorem 3.1 can be proved for them along the same lines (Exercise 4): τ ≤ (d ² − d + 1)ν.

Proposition 3.4

There is a constant c > 0 such that for every d ≥ 2 and k ≥ 1, there exists a system $\mathcal{F}$ of homogeneous d-intervals with $\nu (\mathcal{F}) = k$ and

$$\displaystyle{\tau (\mathcal{F}) \geq c\,\frac{d^{2}} {\log d} \,k.}$$

Proof

Given d and k, we want to construct a system $\mathcal{F}$ of homogeneous d-intervals. Clearly, it suffices to consider the case k = 1, since for larger k, we can take k disjoint copies of the $\mathcal{F}$ constructed for k = 1. Thus, we want an $\mathcal{F}$ in which every two d-intervals intersect and with $\tau (\mathcal{F})$ large.

In the construction, we will use homogeneous d-intervals of a quite special form: Each component is either a single point or a unit-length interval. First, it is instructive to see why we cannot get a good example if all the components are only points. In that case, the family $\mathcal{F}$ is simply a d-uniform hypergraph (whose vertices happen to be points of the real line). We require that any two edges intersect, and thus any edge is a transversal and we have $\tau (\mathcal{F}) \leq d$.

For the actual construction, let n and N be integer parameters (whose value will be set later). Let V = [n] be an index set, and I _v , for v ∈ V, be auxiliary pairwise disjoint unit intervals on the real line. In each I _v , we choose N distinct points x _v, i , i = 1, 2, …, N.

The constructed system $\mathcal{F}$ will consist of homogeneous d-intervals J ¹, J ², …, J ^N. For each i = 1, 2, …, N, we choose auxiliary sets ∅ ⊂ B _i ⊆ A _i ⊆ V and then construct J ⁱ as follows:

$$\displaystyle{J^{i} =\Big (\,\bigcup _{ v\in B_{i}}I_{v}\Big) \cup \{ x_{u,i}:\, u \in A_{i}\setminus B_{i}\}.}$$

The picture shows an example of J ¹ for n = 6, A ₁ = {1, 2, 4, 5} and B ₁ = {2, 4}:

The heart of the proof is the construction of suitable sets A _i and B _i on the ground set V. Since the J ⁱ should be homogeneous d-intervals, we obviously require

• (C1) For all i = 1, 2, …, N, $\varnothing \subset B_{i} \subseteq A_{i}$ and | A _i | ≤ d.

The condition that every two members of $\mathcal{F}$ intersect is implied by the following:

• (C2) For all i ₁, i ₂, 1 ≤ i ₁ < i ₂ ≤ N, we have $A_{i_{1}} \cap B_{i_{2}}\neq \emptyset$ or $A_{i_{2}} \cap B_{i_{1}}\neq \emptyset$ (or both).

Finally, we want $\mathcal{F}$ to have no small transversal. Since no two d-intervals of $\mathcal{F}$ have a point component in common, a transversal of size t intersects no more than t members of $\mathcal{F}$ in their point components, and all the other members of $\mathcal{F}$ must be intersected in their interval components. Therefore, the transversal condition translates to

• (C3) Put t = cd ²∕logd for a sufficiently small constant c > 0, and let $\mathcal{B} =\{ B_{1},B_{2},\ldots,B_{N}\}$. Then $\tau (\mathcal{B}) \geq 2t$, and consequently $\tau (\mathcal{B}') \geq t$ for any $\mathcal{B}'$ arising from $\mathcal{B}$ by removing at most t sets.

A construction of sets A ₁, …, A _N and B ₁, …, B _N as above was provided by Sgall [66]. His results give the following:

Proposition 3.5

Let b be a given integer, let n ≤ cb ²∕logb for a sufficiently small constant c > 0, and let B ₁, B ₂, …, B _N be b-element subsets of V = [n]. Then there exist sets A ₁, A ₂, …, A _N , with B _i ⊆ A _i , | A _i | ≤ 3b, and such that(C2) is satisfied.

With this proposition, the proof of Proposition 3.4 is easily finished. We set $b = \lfloor \frac{d} {3}\rfloor$, n = cb ²∕logb, and we let B ₁, B ₂, …, B _N be all the $N = \binom{n}{b}$ subsets of V of size b. We have τ({B ₁, …, B _n }) = n − b + 1 and condition (C3) holds. It remains to construct the sets A _i according to Proposition 3.5; then (C1) and (C2) are satisfied too. The proof of Proposition 3.4 is concluded by passing from the A _i and B _i to the system $\mathcal{F}$ of homogeneous d-intervals as was described above. □

Sketch of proof of Proposition 3.5

Let G = (V, E) be a graph on n vertices of maximum degree b with the following expander-type property: For any two disjoint b-element subsets A, B ⊆ V, there is at least one edge e ∈ E connecting a vertex of A to a vertex of B. (The existence of such a graph can be easily shown by the probabilistic method; the constant c arises in this argument. See [66] for references.)

For each i, let v _i be an (arbitrary) element of the set B _i , and let

$$\displaystyle{A_{i} = B_{i} \cup N(v_{i}) \cup \Big (V \setminus \bigcup _{u\in B_{i}}N(u)\Big),}$$

where N(v) denotes the set of neighbors in G of a vertex v ∈ V. It is easy to check that | A _i | ≤ 3b, and some thought reveals that the condition (C2) is satisfied. □

3.4 A Helly-Type Problem for d-Intervals

Kaiser and Rabinovich [41] investigated conditions on a family $\mathcal{F}$ of d-intervals guaranteeing that $\mathcal{F}$ can be pierced by a “multipoint,” that is, $\tau (\mathcal{F}) \leq d$ and there is a transversal using one point of each I _i . They proved the following.

Theorem 3.6 (The Kaiser–Rabinovich theorem on $\boldsymbol{d}$-intervals)

Let k = ⌈log₂(d + 2)⌉ and let $\mathcal{F}$ be a family of d-intervals such that any k or fewer members of  $\mathcal{F}$ have a common point. Then $\mathcal{F}$ can be pierced by a multipoint.

Let’s put this result into context: The proof of the Kaiser–Tardos Theorem 3.1 sets out to show that there exists a transversal consisting of exactly t points in each of the intervals I _i , for a suitable t. We eventually get that if every two d-intervals meet (that is, $\nu (\mathcal{F}) = 1$), then we can take t < d. The Kaiser–Rabinovich theorem says that if every ⌈log₂(d + 2)⌉ meet then t < 2 suffices. The upcoming proof of Theorem 3.6 can be extended to yield an interpolation between this result and the Kaiser–Tardos theorem: If every ⌈log _b (d + 2)⌉ edges meet, then we can take t < b. For b = d this yields the result of Kaiser–Tardos for $\nu (\mathcal{F}) = 1$.

Proof

We use notation from the proof of Theorem 3.1. We apply Lemma 3.2 with t = 1, obtaining a set T with one point in each T _i such that all the 2d vertices of the escape hypergraph $\mathcal{H} = \mathcal{H}(T)$ have the same weight W. If W = 0 we are done, so let us assume W > 0.

By the assumption on $\mathcal{F}$, every k edges of $\mathcal{H}$ share a common vertex. We will prove the following claim for every ℓ:

If every ℓ + 1 edges of $\mathcal{H}$ have at least m common vertices, then every ℓ edges of $\mathcal{H}$ have at least 2m + 1 common vertices.

For ℓ = k, the assumption holds with m = 1, and so by (k − 1)-fold application of this claim, we get that every edge of $\mathcal{H}$ “intersects itself” in at least 2^k − 1 vertices, i.e. d > 2^k − 2. The claim thus implies the theorem.

The claim is proved by contradiction. Suppose that $\mathcal{A}\subseteq \mathcal{H}$ is a set of ℓ edges such that $C =\bigcap \mathcal{A}$ has at most 2m vertices, and let $\bar{C}:=\{ (i,3 - j):\, (i,j) \in C\}$. No edge $H \in \mathcal{H}$ contains both (i, 1) and (i, 2), thus also C does not contain both (i, 1) and (i, 2), and thus $\bar{C}$ is a subset of the complement of C; it is matched to C by (i, 3 − j) ↔ (i, j), and thus $\vert C\vert = \vert \bar{C}\vert$.

By the assumption, $\mathcal{A}$ plus any other edge together intersect in at least m vertices. Thus, any $H \in \mathcal{H}\setminus \mathcal{A}$ contains at least m vertices of C, and consequently no more than m vertices of $\bar{C}$.

Let U be the total weight of the vertices in C, and $\bar{U}$ the total weight of the vertices in $\bar{C}$. The edges in $\mathcal{A}$ contribute solely to U, while any other edge H contributes at least as much to U as to $\bar{U}$, and so $U>\bar{ U}$. But this is impossible since all vertex weights are identical and $\vert C\vert = \vert \bar{C}\vert$. The claim, and Theorem 3.6 too, are proved. □

An interesting open problem is whether k = ⌈log₂(d + 2)⌉ in Theorem 3.6 could be replaced by k = k ₀ for some constant k ₀ independent of d. The best known lower bound is k ₀ ≥ 3.

Notes Tardos [74] proved the optimal bound τ ≤ 2ν for 2-intervals by a topological argument using the homology of suitable simplicial complexes. Kaiser’s argument [39] is similar to the presented one, but he proves Lemma 3.2 using a rather advanced Borsuk–Ulam-type theorem of Ramos [64] concerning continuous maps defined on products of spheres. The method with Brouwer’s theorem was used by Kaiser and Rabinovich [41] for a proof of Theorem 3.6.

Lemma 3.3 seems to be new in the version that we give here, but it relates to a vast literature of “KKM-type lemmas,” which starts with a paper by Knaster, Kuratowski, and Mazurkiewicz [43] from 1929. We refer to Bárány and Grinberg [7] and the references given there, such as mathoverflow.net/questions/67318 .

Alon’s short proof [2] of the bound τ ≤ 2d ² ν for families of d-intervals applies a powerful technique developed in Alon and Kleitman [4]. For the so-called Hadwiger–Debrunner ( p, q)-problem solved in the latter paper, the quantitative bounds are probably quite far from the truth. It would be interesting to find an alternative topological approach to that problem, which could perhaps lead to better bounds. See, for example, Hell [34].

The variant of the piercing problem for families of homogeneous d-intervals has been considered simultaneously with d-intervals; see [2, 32, 39, 74]. The upper bounds obtained for the homogeneous case are slightly worse: τ ≤ 3ν for homogeneous 2-intervals, which is tight, and τ ≤ (d ² − d + 1)ν for homogeneous d-intervals, d ≥ 3 [39]. The reason for the worse bounds is that the escape hypergraph needs no longer be d-partite, and so Füredi’s theorem [26] relating ν to ν ^∗ gives a little worse bound (for d = 2, one uses a theorem of Lovász instead, asserting that $\nu ^{{\ast}}\leq \frac{3} {2}\nu$ for any graph).

Sgall’s construction [66] answered a problem raised by Wigderson in 1985. The title of Sgall’s paper refers to a different, but essentially equivalent, formulation of the problem dealing with labeled tournaments.

Alon [3] proved by the method of [2] that if T is a tree and $\mathcal{F}$ is a family of subgraphs of T with at most d connected components, then $\tau (\mathcal{F}) \leq 2d^{2}\nu (\mathcal{F})$. More generally, he established a similar bound for the situation where T is a graph of bounded tree-width (on the other hand, if the tree-width of T is sufficiently large, then one can find a system of connected subgraps of T with ν = 1 and τ arbitrarily large, and so the tree-width condition is also necessary in this sense). A somewhat weaker bound for trees has been obtained independently by Kaiser [40].

Strong results for piercing of d-trees, improving on Alon’s results, were obtained by Berger [8], based on a topological approach via KKM-type lemmas. (For these see the references given above.)

Exercises

• 1. We have claimed that for any family $\mathcal{F}$ of intervals, it is well-known and easy to prove that $\nu (\mathcal{F}) =\tau (\mathcal{F})$. Prove this!

• 2. Let P and Q be convex polytopes. Show that there is a bijection between the nonempty faces of the Cartesian product P × Q and all the products F × G, where F is a nonempty face of P and G is a nonempty face of Q.

• 3. Show that the following “Brouwer-like” claim resembling Lemma 3.3 is not true: If f:  B ⁿ ⟶  B ⁿ is a continuous map of the n-ball such that the boundary of B ⁿ is mapped surjectively onto itself, then f is surjective.

• 4. Prove the bound $\tau (\mathcal{F}) \leq d^{2}\nu (\mathcal{F})$ for any family of homogeneous d-intervals (unions of d intervals on a single line). Hint: Follow the proof for d-intervals above, but encode a candidate transversal T by a point of a simplex (rather than a product of simplices).

4 Evasiveness

4.1 A General Model

The idea of evasiveness comes from the theory of complexity of algorithms. Evasiveness appears in different versions for graphs, digraphs and bipartite graphs. We start with a general model that contains them all.

Definition 4.1 (Argument complexity of a set system; evasiveness)

In the following, we are concerned with a fixed and known set system $\mathcal{F}\subseteq 2^{E}$, and with the complexity of deciding whether some unknown set A ⊆ E is in the set system. Here our “model of computation” is such that

• given, and known, is a set system $\mathcal{F}\subseteq 2^{E}$, where E is fixed, | E | = m.

• On the other hand, there is a

• fixed, but unknown subset A ⊆ E.

• We have to

• decide whether $A \in \mathcal{F}$, using only

• questions of the type “Is e ∈ A?”

(It is assumed that we always get correct answers YES or NO. We only count the number of questions that are needed in order to reach the correct conclusion: It is assumed that it is not difficult to decide whether e ∈ A. You can assume that some “oracle” that knows both A and $\mathcal{F}$ is answering.)

The argument complexity $c(\mathcal{F})$ of the set system $\mathcal{F}$ is the number of elements of the ground set E that we have to test in the worst case—with the optimal strategy.

Clearly $0 \leq c(\mathcal{F}) \leq m$. The set system $\mathcal{F}$ is trivial if $c(\mathcal{F}) = 0$: then no questions need to be asked; this can only be the case if $\mathcal{F} =\{\}$ or if $\mathcal{F} = 2^{E}$. Otherwise $\mathcal{F}$ is non-trivial.

The set system $\mathcal{F}$ is evasive if $c(\mathcal{F}) = m$, that is, if even with an optimal strategy one has to test all the elements of E in the worst case.

For example, if $\mathcal{F} =\{\emptyset \}$, then $c(\mathcal{F}) = m$: If we again and again get the answer NO, then we have to test all the elements to be sure that A = ∅. So $\mathcal{F} =\{\emptyset \}$ is an evasive set system: “being empty” is an evasive set property.

4.2 Complexity of Graph Properties

Definition 4.2 (Graph properties)

Here we consider graphs on a fixed vertex set V = [n]. Loops and multiple edges are excluded. Thus any graph G = (V, A) is determined by its edge set A, which is a subset of the set $E = \binom{n}{2}$ of “potential edges.”

We identify a property $\mathcal{P}$ of graphs with the family of graphs that have the property $\mathcal{P}$, and thus with the set family $\mathcal{F}(\mathcal{P}) \subseteq 2^{E}$ given by

$$\displaystyle{\mathcal{F}(\mathcal{P})\:=\ \{A \subseteq E:\,\ ([n],A)\mbox{ has property }\mathcal{P}\}.}$$

Furthermore, we will consider only graph properties that are isomorphism invariant; that is, properties of abstract graphs that are preserved under renumbering the vertices.

A graph property is evasive if the associated set system is evasive, and otherwise it is non-evasive.

With the symmetry condition of Definition 4.2, we would accept “being connected”, “being planar,” “having no isolated vertices,” and “having even vertex degrees” as graph properties. However, “vertex 1 is not isolated,” “123 is a triangle,” and “there are no edges between odd-numbered vertices” are not graph properties.

Example 4.3 (Graph properties)

For the following properties of graphs on n vertices we can easily determine the argument complexity.

Having no edge: :

Clearly we have to check every single e ∈ E in order to be sure that it is not contained in A, so this property is evasive: Its argument complexity is $c(\mathcal{F}) = m = \binom{n}{2}$.

Having at most k edges: :

Let us assume that we ask questions, and the answer we get is YES for the first k questions, and then we get NO-answers for all further questions, except for possibly the last one. Assuming that k < m, this implies that the property is evasive. Otherwise, for k ≥ m, the property is trivial.

Being connected: :

This property is evasive for n ≥ 2. Convince yourself that for any strategy, a sequence of “bad” answers can force you to ask all the questions.

Being planar: :

This property is trivial for n ≤ 4 but evasive for n ≥ 5. In fact, for n = 5 one has to ask all the questions (in arbitrary order), and the answer will be $A \in \mathcal{F}$ unless we get a YES answer for all the questions—including the last one. This is, however, not at all obvious for n > 5: It was claimed by Hopcroft and Tarjan [35], and proved by Best, Van Emde Boas and Lenstra [10, Example 2] [15, p. 408].

A large star: :

Let $\mathcal{P}$ be the property of being a disjoint union of a star $\Delta _{1,n-4}$ and an arbitrary graph on 3 vertices, and let $\mathcal{F}$ be the corresponding set system.

Then $c(\mathcal{F}) <\binom{n}{2}$ for n ≥ 7. For n ≥ 12 we can easily see this, as follows. Test all the $\lfloor \frac{n} {2} \rfloor \lceil \frac{n} {2} \rceil$ edges {i, j} with $i \leq \lfloor \frac{n} {2} \rfloor <j$. That way we will find exactly one vertex k with at least $\lfloor \frac{n} {2} \rfloor - 3 \geq 3$ neighbors (otherwise property $\mathcal{P}$ cannot be satisfied): That vertex k has to be the center of the star. We test all other edges adjacent to k: We must find that k has exactly n − 4 neighbors. Thus we have identified three vertices that are not neighbors of k: At least one of the edges between those three has not been tested. We test all other edges to check that ([n], A) has property $\mathcal{P}$. (This property was found by L. Carter [10, Example 16].)

Being a scorpion graph: :

A scorpion graph is an n-vertex graph that has one vertex of degree 1 adjacent to a vertex of degree 2 whose other neighbor has degree n − 2. We leave it as an (instructive!) exercise to check that “being a scorpion graph” is not evasive if n is large: In fact, Best, van Emde Boas and Lenstra [10, Example 18] [15, p. 410] have shown that $c(\mathcal{F}) \leq 6n$.

From these examples it may seem that most “interesting” graph properties are evasive. In fact, many more examples of evasive graph properties can be found in Bollobás [15, Sect. VIII.1], alongside with techniques to establish that graph properties are evasive, such as Milner and Welsh’s “simple strategy” [15, p. 406].

Why is this model of interest? Finite graphs (similarly for digraphs and bipartite graphs) can be represented in different types of data structures that are not at all equivalent for algorithmic applications. For example, if a finite graph is given by an adjacency list, which for every vertex lists the neighbors in some order, then one can decide fast (“in linear time”) whether the graph is planar, e.g. using an old algorithm of Hopcroft and Tarjan [35]; see also Mehlhorn [53, Sect. IV.10] and [54]. Note that such a planar graph has at most 3n − 6 edges (for n ≥ 3).

However, assume that a graph is given in terms of its adjacency matrix

$$\displaystyle{M(G)\ \ =\ \ \big (m_{ij}\big)_{1\leq i,j\leq n}\ \ \in \ \{ 0,1\}^{n\times n},}$$

where m _ij = 1 means that {i, j} is an edge of G, and m _ij = 0 says that {i, j} is not an edge. Here G is faithfully represented by the set of all $\binom{n}{2}$ superdiagonal entries (with i < j). Then one possibly has to inspect a large part of the matrix until one has enough information to decide whether the graph in question is planar. In fact, if $\mathcal{F}\subseteq 2^{E}$ is the set system corresponding to all planar graphs, then $c(\mathcal{F})$ is exactly the number of superdiagonal matrix entries that every algorithm for planarity testing has to inspect in the worst case.

The statement that “being planar” is evasive (for n ≥ 5) thus translates into the fact that every planarity testing algorithm that starts from an adjacency matrix needs to read at least $\binom{n}{2}$ bits of the input, and hence its running time is bounded from below by $\binom{n}{2} = \Omega (n^{2})$. This means that such an algorithm—such as the one considered by Fisher [24]—cannot run in linear time, and thus cannot be efficient.

Definition 4.4 (Digraph properties; bipartite graph properties)

• (1) For digraph properties we again use the fixed vertex set V = [n]. Loops and parallel edges are excluded, but anti-parallel edges are allowed. Thus any digraph G = (V, A) is determined by its arc set A, which is a subset of the set E′ of all m : =  n ² − n “potential arcs” (corresponding to the off-diagonal entries of an n × n adjacency matrix).

  A digraph property is a property of digraphs ([n], A) that is invariant under relabelling of the vertex set. Equivalently, a digraph property is a family of arc sets $\mathcal{F}\subseteq 2^{E'}$ that is symmetric under the action of $\mathfrak{S}_{n}$ that acts by renumbering the vertices (and renumbering all arcs correspondingly). A digraph property is evasive if the associated set system is evasive, otherwise it is non-evasive.

• (2) For bipartite graph properties we use a fixed vertex set V ⊎ W of size m + n, and use E″ : =  V × W as the set of potential edges. A bipartite graph property is a property of graphs (V ∪ W, A) with A ⊆ E″ that is preserved under renumbering the vertices in V, and also under permuting the vertices in W. Equivalently, a bipartite graph property on V × W is a set system $\mathcal{F}\subseteq 2^{V \times W}$ that is stable under the action of the automorphism group $\mathfrak{S}_{n} \times \mathfrak{S}_{m}$ that acts transitively on V × W.

Example 4.5 (Digraph properties)

For the following digraph properties on n vertices we can determine the argument complexity.

Having at most k arcs: :

Again, this is clearly evasive with $c(\mathcal{F}) = m$ if k < m = n ² − n, and trivial otherwise.

Having a sink: :

A sink in a digraph on n vertices is a vertex k for which all arcs going into k are present, but no arc leaves k, that is, a vertex of out-degree δ ⁺(v) = 0, and in-degree δ ⁻(v) = n − 1. Let $\mathcal{F}$ be the set system of all digraphs on n vertices that have a sink. It is easy to see that $c(\mathcal{F}) \leq 3n - 4$. In particular, for n ≥ 3 “having a sink” is a non-trivial but non-evasive digraph property.

In fact, if we test whether (i, j) ∈ A, then either we get the answer YES, then i is not a sink, or we get the answer NO, then j is not a sink. So, by testing arcs between pairs of vertices that “could be sinks,” after n − 1 questions we are down to one single “candidate sink” k. At this point at least one arc adjacent to k has been tested. So we need at most 2n − 3 further questions to test whether it is a sink.

In the early 1970s Arnold L. Rosenberg conjectured that all non-trivial digraph properties have quadratic argument complexity, that is, that there is a constant γ > 0 such that for all non-trivial properties of digraphs on n vertices one has $c(\mathcal{F}) \geq \gamma n^{2}$. However, Stål Aanderaa found the counter-example (for digraphs) of “having a sink” [10, Example 15] [63, p. 372]. We have also seen that “being a scorpion graph” is a counter-example for graphs.

Hence Rosenberg modified the conjecture: At least all monotone graph properties, that is, properties that are preserved under deletion of edges, should have quadratic argument complexity. This is the statement of the Aanderaa–Rosenberg conjecture [65]. Richard Karp considerably sharpened the statement, as follows.

Conjecture 4.6 (The evasiveness conjecture)

Every non-trivial monotone graph property or digraph property is evasive.

We will prove this below for graphs and digraphs in the special case when n is a prime power; from this one can derive the Aanderaa–Rosenberg conjecture, with $\gamma \approx \frac{1} {4}$. Similarly, we will prove that monotone properties of bipartite graphs on a fixed ground set V ∪ W are evasive (without any restriction on | V | = m and | W | = n). However, we first return to the more general setting of set systems.

4.3 Decision Trees

Any strategy to determine whether an (unknown) set A is contained in a (known) set system $\mathcal{F}$—as in Definition 4.1—can be represented in terms of a decision tree of the following form.

Definition 4.7

A decision tree is a rooted, planar, binary tree whose leaves are labelled “YES” or “NO,” and whose internal nodes are labelled by questions (here they are of the type “e ∈ A?”). Its edges are labelled by answers: We will represent them so that the edges labelled “YES” point to the right child, and the “NO” edges point to the left child.

A decision tree for $\mathcal{F}\subseteq 2^{E}$ is a decision tree such that starting at the root with an arbitrary A ⊆ E, and going to the right resp. left child depending on whether the question at an internal node we reach has answer YES or NO, we always reach a leaf that correctly answers the question “$A \in \mathcal{F}?$”.

The root of a decision tree is at level 0, and the children of a node at level i have level i + 1. The depth of a tree is the greatest k such that the tree has a vertex at level k (a leaf).

We assume (without loss of generality) that the trees we consider correspond to strategies where we never ask the same question twice.

A decision tree for $\mathcal{F}$ is optimal if it has the smallest depth among all decision trees for $\mathcal{F}$, that is, if it leads us to ask the smallest number of questions for the worst possible input.

Let us consider an explicit example.

The following figure represents an optimal algorithm for the “sink” problem on digraphs with n = 3 vertices. This has a ground set E = {12, 21, 13, 31, 23, 32} of size m = 6.

The algorithm first asks, in the root node at level 0, whether 12 ∈ A. In case the answer is YES (so we know that 1 is not a sink), it branches to the right, leading to a question node at level 1 that asks whether 23 ∈ A?, etc. In case the answer to the question 12 ∈ A? is NO (so we know that 2 is not a sink), it branches to the left, leading to a question node at level 1 that asks whether 13 ∈ A?, etc.

For every possible input A (there are 2⁶ = 32 different ones), after two questions we have identified a unique “candidate sink”; after not more than 5 question nodes one arrives at a leaf node that correctly answers the question whether the graph (V, A) has a sink node: YES or NO. (The number of the unique candidate is noted next to each node at level 2.)

For each node (leaf or inner) of level k, there are exactly 2^m−k different inputs that lead to this node. This proves the following lemma.

Lemma 4.8

The following are equivalent:

• $\mathcal{F}$ is non-evasive.

• The optimal decision trees $T_{\mathcal{F}}$ for $\mathcal{F}$ have depth smaller than m.

• Every leaf of an optimal decision tree $T_{\mathcal{F}}$ is reached by at least two distinct inputs.

Corollary 4.9

If $\mathcal{F}$ is non-evasive, then $\vert \mathcal{F}\vert$ is even.

This can be used to show, for example, that the directed graph property “has a directed cycle” is evasive [10, Example 4].

Another way to view a (binary) decision tree algorithm is as follows. In the beginning, we do not know anything about the set A, so we can view the collection of possible sets as the complete boolean algebra of all 2^m subsets of E.

In the first node (at “level 0”) we ask a question of the type “e ∈ A?”; this induces a subdivision of the boolean algebra into two halves, depending on whether we get answer YES or NO. If you think of the boolean algebra as a partially ordered set (indeed, a lattice), then each of the halves is an interval of length m − 1 of the boolean algebra (2^E, ⊆ ). If you prefer to think of it as a rendition of the m-dimensional hypercube, then the halves are subcubes of codimension 1, containing all the vertices of two opposite facets.

At level 1 we ask a new question, depending on the outcome of the first question. Thus we independently bisect the two halves of level 0, getting four pieces of the boolean algebra, all of the same size.

This process is iterated. It stops—as we do not need to ask a further question—on parts that we create that either contain only sets that are in $\mathcal{F}$ (this yields a YES-leaf) or that contain only sets not in $\mathcal{F}$ (corresponding to NO-leaves).

Thus the final result is a special type of partition of the boolean algebra into intervals. Some of them are YES intervals, containing only sets of $\mathcal{F}$, all the others are NO-intervals, containing no sets from $\mathcal{F}$. If the property in question is monotone, then the union of the YES intervals (i.e., the set system $\mathcal{F}$) forms an ideal in the boolean algebra, that is, a “down-closed” set such that with any set that it contains it must also contain all its subsets.

Let $p_{\mathcal{F}}(t)$ be the generating function for the set system $\mathcal{F}$, that is, the polynomial

$$\displaystyle{p_{\mathcal{F}}(t)\:=\ \sum _{A\in \mathcal{F}}t^{\vert A\vert }\ \ =\ \ f_{ -1} + tf_{0} + t^{2}f_{ 1} + t^{3}f_{ 2} +\ldots.}$$

where $f_{i} = \vert \{A \in \mathcal{F}:\, \vert A\vert = i + 1\}\vert$.

Proposition 4.10

$$\displaystyle{(1 + t)^{m-c(\mathcal{F})}\ \ \big\vert \ \ p_{ \mathcal{F}}(t).}$$

Proof

Consider one interval $\mathcal{I}$ in the partition of 2^E that is induced by any optimal algorithm for $\mathcal{F}$. If the leaf, at level k, corresponding to the interval is reached through a sequence of k _Y YES-answers and k _N NO-answers (with k _Y + k _N = k), then this means that there are sets A _Y ⊆ E with | A _Y | = k _Y and A _N ⊆ E with | A _N | = k _N , such that

$$\displaystyle{\mathcal{I}\ \ =\ \ \{ A \subseteq E:\, A_{Y } \subseteq A \subseteq E\setminus A_{N}\}.}$$

In other words, the interval $\mathcal{I}$ contains all sets that give YES-answers when asked about any of the k _Y  elements of A _Y , NO-answers when asked about any of the k _N  elements of A _N , while the m − k _Y − k _N elements of E∖(A _Y ∪ A _N ) may or may not be contained in A. Thus the interval $\mathcal{I}$ has size $2^{m-k_{Y }-k_{N}}$, and its counting polynomial is

$$\displaystyle{p_{\mathcal{I}}(t)\:=\ \sum _{A\in \mathcal{I}}t^{\vert A\vert }\ \ =\ \ t^{k_{Y } }(1 + t)^{m-k_{Y }-k_{N} }.}$$

Now the complete set system $\mathcal{F}$ is a disjoint union of the intervals $\mathcal{I}$, and we get

$$\displaystyle{p_{\mathcal{F}}(t)\ \ =\ \ \sum _{\mathcal{I}}p_{\mathcal{I}}(t).}$$

In particular, for an optimal decision tree we have $k_{Y } + k_{N} = k \leq c(\mathcal{F})$ and thus $m - c(\mathcal{F}) \leq m - k_{Y } - k_{N}$ at every leaf of level k, which means that all the summands $p_{\mathcal{I}}(t)$ have a common factor of $(1 + t)^{m-c(\mathcal{F})}$. □

Corollary 4.11

If $\mathcal{F}$ is non-evasive, then $\vert \mathcal{F}^{even}\vert = \vert \mathcal{F}^{odd}\vert$ , that is,

$$\displaystyle{-f_{-1} + f_{0} - f_{1} + f_{2} \mp \cdots = 0.}$$

Proof

Use Proposition 4.10, and put t = −1. □

We can now draw the conclusion, based only on simple counting, that most set families are evasive. This cannot of course be used to settle any specific cases, but it can at least make the various evasiveness conjectures seem more plausible.

Corollary 4.12

Asymptotically, almost all set families $\mathcal{F}$ are evasive.

Proof

The number of set families $\mathcal{F}\subseteq 2^{E}$ such that

$$\displaystyle{\#\{A \in \mathcal{F}\mid \#A\mbox{ odd}\} = \#\{A \in \mathcal{F}\mid \#A\mbox{ even}\} = k}$$

is $\binom{2^{m-1}}{k}^{2}$. Hence, using Stirling’s estimate of factorials,

$$\displaystyle{\mbox{ Prob (}\mathcal{F}\mbox{ non-evasive)}\, \leq \, \frac{\sum _{k=0}^{2^{m-1} }\binom{2^{m-1}}{k}^{2}} {2^{2^{m} }} \, =\, \frac{\binom{2^{m}}{2^{m-1}}} {2^{2^{m} }} \, \sim \, \frac{1} {\sqrt{\pi 2^{m-1}}} \rightarrow 0,}$$

as m → ∞. □

Conjecture 4.13 (The “Generalized Aanderaa–Rosenberg Conjecture”, Rivest and Vuillemin [62])

If $\mathcal{F}\subseteq 2^{E}$ , with symmetry group $G \subseteq \mathfrak{S}_{E}$ that is transitive on the ground set E, and if $\emptyset \in \mathcal{F}$ but $E\notin \mathcal{F}$ , then $\mathcal{F}$ is evasive.

Note that for this it is not assumed that $\mathcal{F}$ is monotone. However, the assumption that $\emptyset \in \mathcal{F}$ but $E\notin \mathcal{F}$ is satisfied neither by “being a scorpion” nor by “having a sink.”

Proposition 4.14 (Rivest and Vuillemin [62])

The Generalized Aanderaa–Rosenberg Conjecture  4.13 holds if the size of the ground set is a prime power, | E | = p ^t .

Proof

Let $\mathcal{O}$ be any k-orbit of G, that is, a collection of k-sets $\mathcal{O}\subseteq \mathcal{F}$ on which G acts transitively. While every set in $\mathcal{O}$ contains k elements e ∈ E, we know from transitivity that every element of E is contained in the same number, say d, of sets of the orbit $\mathcal{O}$. Thus, double-counting the edges of the bipartite graph on the vertex set $E \uplus \mathcal{O}$ defined by “e ∈ A” (displayed in the figure below) we find that $k\vert \mathcal{O}\vert = d\vert E\vert = dp^{t}$. Thus for 0 < k < p ^t we have that p divides $\vert \mathcal{O}\vert$, while $\{\varnothing \}$ is one single “trivial” orbit of size 1, and k = p ^t doesn’t appear. Hence we have

$$\displaystyle{-f_{-1} + f_{0} - f_{1} + f_{2} \mp \cdots \equiv -1\bmod p,}$$

which implies evasiveness by Corollary 4.11. □

Proposition 4.15 (Illies [36])

The Generalized Aanderaa–Rosenberg Conjecture  4.13 fails for n = 12.

Proof

Here is Illies’ counterexample: Take E = {1, 2, 3, …, 12}, and let the cyclic group $G = \mathbb{Z}_{12}$ permute the elements of E with the obvious cyclic action.

Take $\mathcal{F}_{I} \subseteq 2^{E}$ to be the following system of sets

• ∅, so we have f ₋₁ = 1

• {1} and all images under $\mathbb{Z}_{12}$, that is, all singleton sets: f ₀ = 12,

• {1, 4} and {1, 5} and all images under $\mathbb{Z}_{12}$, so f ₁ = 12 + 12 = 24,

• {1, 4, 7} and {1, 5, 9} and all their $\mathbb{Z}_{12}$-images, so f ₂ = 12 + 4 = 16,

• {1, 4, 7, 10} and their $\mathbb{Z}_{12}$-images, so f ₃ = 3.

An explicit decision tree of depth 11 for this $\mathcal{F}_{I}$ is given in our figure below. Here the pseudo-leaf “YES(7,10)” denotes a decision tree where we check all elements e ∈ E that have not been checked before, other than the elements 7 and 10. If none of them is contained in A, then the answer is YES (irrespective of whether 7 ∈ A or 10 ∈ A), otherwise the answer is NO. The fact that two elements need not be checked means that this branch of the decision tree denoted by this “pseudo-leaf” does not go beyond depth 10. Similarly, a pseudo-leaf of the type “YES(7)” represents a subtree of depth 11.

Thus the following figure completes the proof. Here dots denote subtrees that are analogous to the ones just above. □

Note, however, that Illies’ example is not monotone: For example, we have $\{1,4,7\} \in \mathcal{F}_{I}$, whereas $\{1,7\}\notin \mathcal{F}_{I}$.

4.4 Monotone Systems

We now concentrate on the case where $\mathcal{F}$ is closed under taking subsets, that is, $\mathcal{F}$ is an abstract simplicial complex, which we also denote by $\Delta \:=\ \mathcal{F}$. In this setting, the symmetry group acts on $\Delta$ as a group of simplicial homeomorphisms. If $\mathcal{F}$ is a graph or digraph property, then this means that the action of G is transitive on the vertex set E of $\Delta$, which corresponds to the edge set of the graph in question. Again we denote the cardinality of the ground set (the vertex set of $\Delta$) by | E | = m.

A complex $\Delta \subseteq 2^{E}$ is a cone if it has a vertex v such that A ∪{ v} is a face of $\Delta$ for any face $A \in \Delta$. For example, every simplex $\Delta = 2^{E}$ is a cone, but also every star graph K _m, 1, considered as a simplicial complex of dimension 1, is a cone.

A complex $\Delta \subseteq 2^{E}$ is collapsible if it can be reduced to a one-point complex (equivalently, to a simplex) by steps of the form

$$\displaystyle{\Delta \ \longrightarrow \ \Delta \setminus \{A \in \Delta:\, A_{0} \subseteq A \subseteq A_{1}\},}$$

where A ₀ ⊂ A ₁ are faces of $\Delta$ with $\varnothing \neq A_{0}\neq A_{1}$, and A ₁ is the unique maximal element of $\Delta$ that contains A ₀. For example, every tree, considered as a simplicial complex of dimension 1, is collapsible.

Our figure illustrates a sequence of collapses that reduce a 2-dimensional complex to a point. In each case the face A ₀ that is contained in a unique maximal face is drawn fattened.

Theorem 4.16

We have the following implications:

$\Delta$ is a cone $\ \Longrightarrow\ \Delta$ is non-evasive $\ \Longrightarrow\ \Delta$ is collapsible $\ \Longrightarrow\ \Delta$ is contractible.

Proof

The first implication is clear: For a cone we don’t have to test the apex e ₀ in order to see whether a set A is a face of $\Delta$, since $A \in \Delta$ if and only if $A \cup \{ e_{0}\} \in \Delta$. The third implication is easy topology: One can write down explicit deformation retractions. The middle implication we will derive from the following claim, which uses the notion of a link of a vertex e in a simplicial complex $\Delta$: This is the complex $\Delta /e$ formed by all faces $A \in \Delta$ such that e ∉ A but $A \cup \{ e\} \in \Delta$.

Claim

$\Delta$ is non-evasive if and only if either $\Delta$ is a simplex, or it is not a simplex but it has a vertex e such that both the deletion $\Delta \setminus e$ and the link $\Delta /e$ are non-evasive.

Let us first verify this claim: If no questions need to be asked (that is, if c(Δ) = 0), then $\Delta$ is a simplex. Otherwise we have some e that corresponds to the first question to be asked by an optimal algorithm. If one gets a YES answer, then the problem is reduced to the link $\Delta /e$, since the faces $B \in \Delta /e$ correspond to the faces A = B ∪{ e} of $\Delta$ for which e ∈ A. In the case of a NO-answer the problem similarly reduces to the deletion $\Delta \setminus e$.

Now let us return to the proof of Theorem 4.16, where we still have to verify that “$\Delta$ is non-evasive ⇒ $\Delta$ is collapsible.” We use induction on the number of faces of $\Delta$.

If $\Delta$ is not a simplex, then by the Claim it has a vertex e such that the link $\Delta /e$ and the deletion $\Delta \setminus e$ are collapsible. If the link is a simplex, then deletion of e is a collapsing step $\Delta \rightarrow \Delta \setminus e$, where $\Delta \setminus e$ is collapsible, so we are done by induction.

If the link is not a simplex, then it has faces $\varnothing \subset A_{0} \subset A_{1}$ such that A ₁ is the unique maximal face in the link that contains A ₀. This means that $\Delta$ has faces {e} ⊂ A ₀ ∪{ e} ⊂ A ₁ ∪{ e} such that A ₁ ∪{ e} is the unique maximal face in $\Delta$ that contains A ₀ ∪{ e}. In this way any collapsing step in the link $\Delta /e$ yields a collapsing step in $\Delta$, and again we are done by induction. □

4.5 A Topological Approach

The following simple lemma provides the step from the topological fixed point theorems for complexes to combinatorial information.

Lemma 4.17

If a (finite) group G acts vertex-transitively and with a fixed point on a finite complex $\Delta$ , then $\Delta$ is a simplex.

Proof

If V  : =  {v ₁, …, v _n } is the vertex set of $\Delta$, then any point $x \in \|\Delta \|$ has a unique representation of the form

$$\displaystyle{x\ \ =\ \ \sum _{ i=1}^{n}\lambda _{ i}\,v_{i},}$$

with λ _i ≥ 0 and ∑ _{i = 1} ⁿ λ _i = 1. If the group action, with

$$\displaystyle{gx\ \ =\ \ \sum _{ i=1}^{n}\lambda _{ i}\,gv_{i},}$$

is transitive, then this means that for every i, j there is some g ∈ G with gv _i = v _j . Furthermore, if x is a fixed point, then we have gx = x for all g ∈ G, and hence we get λ _i = λ _j for all i, j. From this we derive $\lambda _{i} = \frac{1} {n}$ for all i. Hence we get

$$\displaystyle{x\ \ =\ \ \frac{1} {n}\sum _{i=1}^{n}\,v_{ i}}$$

and this is a point in $\|\Delta \|$ only if $\Delta$ is the complete simplex with vertex set V.

Alternatively: The fixed point set of any group action is a subcomplex of the barycentric subdivision, by Lemma A.4. Thus a vertex x of the fixed point complex is the barycenter of a face A of $\Delta$. Since x is fixed by the whole group, so is its support, the set A. Thus vertex transitivity implies that A = E, and $\Delta = 2^{E}$. □

Theorem 4.18 (The Evasiveness Conjecture for prime powers: Kahn, Saks and Sturtevant [38])

All monontone non-trivial graph properties and digraph properties for graphs on a prime power number of vertices | V | = q = p ^t are evasive.

Proof

We identify the fixed vertex set V with GF(q). Corresponding to a non-evasive monotone non-trivial graph property we have a non-evasive complex $\Delta$ on a set $E = \binom{V }{2}$ of $\binom{q}{2}$ vertices. By Theorem 4.16 $\Delta$ is collapsible and hence $\mathbb{Z}_{p}$ -acyclic, that is, all its reduced homology groups with $\mathbb{Z}_{p}$-coefficients vanish.

The symmetry group of $\Delta$ includes the symmetric group $\mathfrak{S}_{q}$, but we take only the subgroup of all “affine maps”

$$\displaystyle\begin{array}{rcl} G& \:=\ & \{x\ \longmapsto \ ax + b:\, a,b \in \mbox{ GF}(q),\ a\neq 0\}, {}\\ \end{array}$$

and its subgroup

$$\displaystyle\begin{array}{rcl} P& \:=\ & \{x\ \longmapsto \ x + b:\, b \in \mbox{ GF}(q)\} {}\\ \end{array}$$

that permute the vertex set V, and (since we are considering graph properties) extend to an action on the vertex set $E = \binom{V }{2}$ of $\Delta$. Then we can easily verify the following facts:

• G is doubly transitive on V, and hence induces a vertex transitive group of symmetries of the complex $\Delta$ on the vertex set $E = \binom{V }{2}$ (interpret GF(q) as a 1-dimensional vector space, then any (ordered) pair of distinct points can be mapped to any other such pair by an affine map on the line);

• P is a p-group (of order p ^t = q);

• P is the kernel of the homomorphism that maps (x ↦  ax + b) to a ∈ GF(q)^∗, the multiplicative group of GF(q), and thus a normal subgroup of G;

• $G/P\cong \mbox{ GF}(q)^{{\ast}}$ is cyclic (this is known from your algebra class).

Taking these facts together, we have verified all the requirements of Oliver’s fixed point theorem, as provided in the Appendix as Theorem A.7. Hence G has a fixed point on $\Delta$, and by Lemma 4.17 $\Delta$ is a simplex, and hence the corresponding (di)graph property is trivial. □

From this one can also deduce—with a lemma due to Kleitman and Kwiatowski [42, Thm. 2]—that every non-trivial monotone graph property on n vertices has complexity at least n ²∕4 + o(n ²) = m∕2 + o(m). (For the proof see [38, Thm. 6].) This establishes the Aanderaa–Rosenberg Conjecture. On the other hand, the Evasiveness Conjecture is still an open problem for every n ≥ 10 that is not a prime power. Kahn, Saks and Sturtevant [38, Sect. 4] report that they verified it for n = 6.

The following treats the bipartite version of the Evasiveness Conjecture. Note that in the case where mn is a prime power it follows from Proposition 4.14.

Theorem 4.19 (The Evasiveness Conjecture for bipartite graphs, Yao [76])

All monotone non-trivial bipartite graph properties are evasive.

Proof

The ground set now is E = V × W, where any monotone bipartite graph property is represented by a simplicial complex $\Delta \subseteq 2^{E}$.

An interesting aspect of Yao’s proof is that it does not use a vertex transitive group. In fact, let the cyclic group $G\:=\ \mathbb{Z}_{n}$ act by cyclically permuting the vertices in W, while leaving the vertices in V fixed. The group G satisfies the assumptions of Oliver’s Theorem A.7, with P = {0}. It acts on the complex $\Delta$ which is acyclic by Theorem 4.16. Thus we get from Oliver’s Theorem that the fixed point set $\Delta ^{G}$ is acyclic. This fixed point set is not a subcomplex of $\Delta$ (it does not contain any vertices of $\Delta$), but it is a subcomplex of the order complex $\Delta (\Delta )$, which is the barycentric subdivision of $\Delta$ (Lemma A.4).

The bipartite graphs that are fixed under G are those for which every vertex in V is adjacent to none, or to all, of the vertices in W; thus they are complete bipartite graphs of the type K _k, n for suitable k. Our figure illustrates this for the case where m = 6, n = 5, and k = 3.

Monotonicity now implies that the fixed graphs under G are all the complete bipartite graphs of type K _k, n with 0 ≤ k ≤ r for some r with 0 ≤ r < m. (Here r = m is impossible, since then $\Delta$ would be a simplex, corresponding to a trivial bipartite graph property.)

Now we observe that $\Delta ^{G}$ is the order complex (the barycentric subdivision) of a different complex, namely of the complex whose vertices are the complete bipartite subgraphs K _1,n , and whose faces are all sets of at most r vertices.

Thus $\Delta ^{G}$ is the barycentric subdivision of the (r − 1)-dimensional skeleton of an (m − 1)-dimensional simplex. In particular, this space is not acyclic. Even its reduced Euler characteristic, which can be computed to be $(-1)^{r-1}\binom{m - 1}{r}$, does not vanish. □

We have the following sequence of implications:

$$\displaystyle{\mbox{ non-evasive$^{\mbox{ (1)}}$ }\,\Longrightarrow\,\mbox{ collapsible$^{\mbox{ (2)}}$ }\,\Longrightarrow\,\mbox{ contractible$^{\mbox{ (3)}}$ }\,\Longrightarrow\,\mathbb{Q}\mbox{ -acyclic$^{\mbox{ (4)}}$ }\,\Longrightarrow\,\chi = 1\mbox{ $^{\mbox{ (5)}}$,}}$$

which corresponds to a sequence of conjectures:

Conjecture($\boldsymbol{k}$)

Every vertex-homogeneous simplicial complex with property (k) is a simplex.

Here we call a simplicial complex vertex-homogeneous if its symmetry group acts transitively on the vertices.

The above implications show that

$$\displaystyle{\mbox{ Conj. (5)}\Longrightarrow\mbox{ Conj. (4)}\Longrightarrow\mbox{ Conj. (3)}\Longrightarrow\mbox{ Conj. (2)}\Longrightarrow\mbox{ Conj. (1)}\Longrightarrow\begin{array}{l} \mbox{ Evasiveness}\\ \mbox{Conjecture}\end{array} }$$

Here Conjecture (5) is true for a prime power number of vertices, by Theorem 4.14.

However, Conjectures (5) and (4) fail for n = 6: A counterexample is provided by the six-vertex triangulation of the real projective plane (see [52, Section 5.8]). Even Conjectures (3) and possibly (2) fail for n = 60: a counterexample by Oliver (unpublished), of dimension 11, is based on the group A ₅; see Lutz [49].

So, it seems that Conjecture (1)—the monotone version of the Generalized Aanderaa–Rosenberg Conjecture 4.13—may be the right generality to prove, even though its non-monotone version fails by Proposition 4.15.

4.6 Quillen’s Conjecture

In this final section we briefly comment on a well-known conjecture of Daniel Quillen from 1978 concerning finite groups. Upon first sight it seems very remote from the topic of evasiveness that we have just discussed, but under the surface one finds some surprising similarities.

In this section we assume familiarity with basic finite group theory, and with the topology of order complexes.

A finite group is a p-group if its order is a power of the prime number p. A subgroup of a finite group G is a p-Sylow subgroup if it is a maximal p-group. The number n _p of p-Sylow subgroups of G is called the p-Sylow number of G.

Let G be a finite group and p ^e a prime power such that | G | = p ^e m and p does not divide m. Here are some well known properties.

• 1. There exists a p-Sylow subgroup of G of order p ^e.

• 2. Any two p-Sylow subgroups of G are conjugate to each other.

• 3. $n_{p}(G) \equiv 1\mod p$.

These statements are the familiar Sylow theorems, the first substantial results in most treatises on group theory.

For a finite group G and a prime number p dividing its order, let L _p (G) denote the poset of non-trivial p-subgroups of G, ordered by inclusion. This is a ranked poset, the maximal elements of which are the p-Sylow subgroups. It becomes a lattice if one adds new bottom and top elements.

In 1978 Quillen published the following conjecture [61], which in a surprising way connects a topological condition with an algebraic one.

Conjecture 4.20 (Quillen’s conjecture)

L _p (G) is contractible if and only if G has a non-trivial normal p-subgroup.

Here L _p (G) refers to the order complex, whose simplices are the totally ordered chains x ₀ < x ₁ < … < x _d of L _p (G). The “if” direction, which is very easy, was proved by Quillen, and he proved the “only if” direction for the case of solvable groups. The conjecture has since then been verified in many cases, but the general case is still wide open.

In the previous section we considered an array of conjectures, among them this one:

Conjecture (3)

Every vertex-homogeneous contractible simplicial complex is a simplex.

This conjecture turns out to be relevant both for evasiveness and for p-subgroups:

Conjecture (3) ⇒ Evasiveness Conjecture,

Conjecture (3) ⇒ Quillen’s Conjecture.

However, Conjecture (3) is false. It was mentioned in the previous section that counterexamples on 60 vertices are known. So, why spend time on discussing it? We believe that it is nevertheless instructive to see in which way Conjecture (3) is relevant for Quillen’s Conjecture. It is conceivable that progress for one of the Evasiveness Conjecture and the Quillen Conjecture can lead to progress for the other.

Proposition 4.21

Conjecture (3) ⇒ Quillen’s Conjecture

Proof

Suppose that L _p (G) is contractible. We are to prove that G has a non-trivial normal p-subgroup.

Define the auxiliary Sylow complex Syl _p (G) this way: The vertices are the p-Sylow subgroups of G. A collection of such subgroups form a simplex (or, face) of Syl _p (G) if their intersection is nontrivial (not just the identity). This is clearly a simplicial complex.

An application of the nerve theorem (or the crosscut theorem), see Björner [12, p. 1850], shows that these two complexes are of same homotopy type:

$$\displaystyle{\mathrm{Syl}_{p}(G) \sim L_{p}(G)}$$

The group G acts by conjugation on the vertex set of Syl _p (G), and by the second Sylow theorem this action is transitive. So, Syl _p (G) is a vertex-homogeneous and contractible complex. Conjecture (3) then implies that Syl _p (G) is a big simplex. This means precisely that the intersection of all p-Sylow subgroups is non-trivial and is a fixed point under the action. Hence this is a non-trivial normal p-subgroup.

Following along the reasoning in this proof can help to verify the Quillen conjecture in some special cases, such as this.

Proposition 4.22

If n _p = q ^e , that is, if the number of p-Sylow subgroups is the power of some prime number q, then G satisfies the Quillen conjecture.

Here the Rivest–Vuillemin Theorem 4.14 is relevant. In fact, with this and Conjecture (5) a sharper version of the Quillen conjecture can be obtained in the case when n _p = q ^e, using trivial Euler characteristic instead of contractibility. We leave further thoughts and experiments in this direction to the reader.

Notes The classical textbook account on evasiveness, from the Graph Theory point of view, is in Bollobas [15, Chap. VIII].

A textbook account from a Topological Combinatorics point-of-view was recently given in de Longueville [47, Chap. 3]. The appendices A–E to this book also provide a concise and user-friendly account of the Algebraic Topology tools employed. See also Miller [55].

Gorenstein [30] is a standard text on finite groups. The book by Smith [70] contains a wealth of material on subgroup lattices and can serve as our general reference for these.

Exercises

• 1. What kind of values of $c(\mathcal{F})$ are possible for graph properties of graphs on n vertices? For monotone properties, it is assumed that one has $c(\mathcal{F}) \in \{ 0,m\}$, and this is proved if n is a prime power. In general, it is known that $c(\mathcal{F}) \geq 2n - 4$ unless $c(\mathcal{F}) = 0$, by Bollobás and Eldridge [16], see [15, Sect. VIII.5].

• 2. Show that the digraph property “has a sink” has complexity

  $$\displaystyle{c(\mathcal{F}_{sink}) \leq 3(n - 1) -\lfloor \log _{2}(n)\rfloor.}$$

  Can you also prove that for any non-trivial digraph property one has $c(\mathcal{F}) \geq c(\mathcal{F}_{sink})$?

  (This is stated in Best, van Emde Boas and Lenstra [10, p. 17]; there are analogous results by Bollobás and Eldridge [16] [15, Sect. VIII.5] in a different model for digraphs.)

• 3. Show that if a complex $\Delta$ corresponds to a non-evasive monotone graph property, then it has a complete 1-skeleton.

• 4. Give examples of simplicial complexes that are contractible, but not collapsible. (The “dunce hat” is a key word for a search in the literature … )

• 5. Assume that when testing some unknown set A with respect to a set system $\mathcal{F}$, you always get the answer YES if there is any set $A \in \mathcal{F}$ for which this YES and all the previous answers are correct, that is, unless this “YES” would allow you to conclude $A\notin \mathcal{F}$ at this point.

  • (i) Show that with this type of answers you always need m questions for any algorithm (and thus $\mathcal{F}$ is evasive) if and only if $\mathcal{F}$ satisfies the following property:

    (*) :

    for any $e \in A \in \mathcal{F}$ there is some f ∈ E∖A such that $A\setminus \{e\} \cup \{\, f\} \in \mathcal{F}$.

  • (ii) Show that for n ≥ 5, the family $\mathcal{F}$ of edge sets of planar graphs satisfies property (∗).

  • (iii) Give other examples of graph properties that satisfy (∗), and are thus evasive.

  (This is the “simple strategy” of Milner and Welsh [56]; see Bollobás [15, p. 406].)

• 6. Let $\Delta$ be a vertex-homogeneous simplicial complex with n vertices and Euler characteristic $\chi (\Delta ) = -1$. Suppose that $n = p_{1}^{e_{1}}\cdots p_{k}^{e_{k}}$ is the prime factorization of n and let $m =\max \{ p_{1}^{e_{1}},\ldots,p_{k}^{e_{k}}\}$. Prove that $\dim \Delta \geq m - 1.$

• 7. Let W _n ^q be the set of all words of length n in the alphabet {1, 2, …, q}, q ≥ 2. For subsets $\mathcal{F}\subseteq W_{n}^{q}$, let $c(\mathcal{F})$ be the least number of inspections of single letters (or rather, positions) that the best algorithm needs in the worst case s ∈ W _n ^q in order to decide whether $s \in \mathcal{F}$.

  Define the polynomial

  $$\displaystyle{p_{\mathcal{F}}(x_{1},\ldots,x_{q}) =\sum _{s\in \mathcal{F}}x_{1}^{\mu _{1} }\cdots x_{q}^{\mu _{q} },}$$

  where μ _i = #{j: s _j = i} for s = s ₁⋯s _q .

  Show that

  $$\displaystyle{(x_{1} +\ldots +x_{q})^{n-c(\mathcal{F})}\ \ \big\vert \ \ p_{ \mathcal{F}}(x_{1},\ldots,x_{q}).}$$

Appendix: Fixed Point Theorems and Homology

1.1 Lefschetz’ Theorem

Fixed point theorems are “global–local tools”: From global information about a space (such as its homology) they derive local effects, such as the existence of special points where “something happens.” Of course, in applications to combinatorial problems we need to combine them with suitable “continuous–discrete tools”: From continous effects, such as topological information about continuous maps of simplicial complexes, we have to find our way back to combinatorial information. In this Appendix we assume familiarity with more Algebra and Algebraic Topology than in other parts of these lecture notes, including some basic finite group theory, chain complexes, etc. As this is meant to be a reference and survey section, no detailed proofs will be given. A main result we head for is Oliver’s Theorem A.7, which is needed in Sect. 4. On the way to this, skim or skip, depending on your tastes and familiarity⁴ with these notions.

A powerful tool on our agenda (which yields a classical proof for Brouwer’s fixed point theorem and some of its extensions) is Hopf’s trace theorem. For this let V be any finite-dimensional vector space, or a free abelian group of finite rank. When we consider an endomorphism g:  V  ⟶  V then the trace trace(g) is the sum of the diagonal elements of the matrix that represents g. The trace is independent of the basis chosen for V. In the case when V is a free abelian group, then trace(g) is an integer.

Theorem A.1 (The Hopf trace theorem)

Let $\Delta$ be a finite simplicial complex, let $f: \ \|\Delta \|\ \longrightarrow \ \|\Delta \|$ be a self-map, and denote by f _#i resp. f _∗i the maps that f induces on i-dimensional chain groups resp. homology groups.

Using an arbitrary field of coefficients k , one has

$$\displaystyle{\sum _{i}(-1)^{i}\mathit{\mbox{ trace}}(f_{ \#i})\ \ =\ \ \sum _{i}(-1)^{i}\mathit{\mbox{ trace}}(f_{ {\ast}i}).}$$

The same identity holds if we use integer coefficients, and compute the traces for homology in the quotients $H_{i}(\Delta, \mathbb{Z})/T_{i}(\Delta, \mathbb{Z})$ of the homology groups modulo their torsion subgroups; these quotients are free abelian groups.

This theorem is remarkable as it allows to compute a topological invariant that depends solely on the homotopy class of f, by means of a simple combinatorial counting. The proof for this uses the definition of simplicial homology, and simple linear algebra; we refer to Munkres [58, Thm. 22.1] or Bredon [19, Sect. IV.23].

For an arbitrary coefficient field k, the Lefschetz number of the map $f: \ \|\Delta \|\ \longrightarrow \ \|\Delta \|$ is defined as

$$\displaystyle{L_{\mathbf{k}}(f)\:=\ \sum _{i}(-1)^{i}\mbox{ trace}(f_{ {\ast}i})\ \ \in \mathbf{k}.}$$

Similarly, taking integral homology modulo torsion, the integral Lefschetz number is defined as

$$\displaystyle{L(f)\:=\ \sum _{i}(-1)^{i}\mbox{ trace}(f_{ {\ast}i})\ \ \in \mathbb{Z}.}$$

The universal coefficient theorems imply that one always has $L_{\mathbb{Q}}(f) = L(f)$: Thus the integral Lefschetz number L(f) can be computed in rational homology, but it is an integer.

The Euler characteristic of a complex $\Delta$ coincides with the Lefschetz number of the identity map $\mbox{ id}_{\Delta }: \ \|\Delta \|\ \longrightarrow \ \|\Delta \|$,

$$\displaystyle{\chi (\Delta ) = L(\mbox{ id}_{\Delta }),\quad \text{where }\mbox{ trace}((\mbox{ id}_{\Delta })_{{\ast}i}) =\beta _{i}(\Delta ).}$$

Thus the Hopf trace theorem yields that the Euler characteristic of a finite simplicial complex $\Delta$ can be defined resp. computed without a reference to homology, simply as the alternating sum of the face numbers of the complex $\Delta$, where $f_{i} = f_{i}(\Delta )$ denotes the number of i-dimensional faces of $\Delta$:

$$\displaystyle{\chi (\Delta )\:=\ f_{0}(\Delta ) - f_{1}(\Delta ) + f_{2}(\Delta ) -\cdots \,.}$$

This is then a finite sum that ends with $(-1)^{d}f_{d}(\Delta )$ if $\Delta$ has dimension d. Thus the Hopf trace theorem applied to the identity map just reproduces the Euler–Poincaré formula. This proves, for example, the d-dimensional Euler polyhedron formula, not only for polytopes, but also for general spheres, shellable or not (as discussed in Ziegler [77]). The Hopf trace formula also has powerful combinatorial applications, see Ziegler [78]. However, for us its main consequence is the following theorem, which is a vast generalization of the Brouwer fixed point theorem.

Theorem A.2 (The Lefschetz fixed point theorem)

Let $\Delta$ be a finite simplicial complex, and k an arbitrary field. If a self-map $f: \ \|\Delta \|\ \longrightarrow \ \|\Delta \|$ has Lefschetz number L _k (f) ≠ 0, then f and every map homotopic to f have a fixed point.

In particular, if $\Delta$ is $\mathbb{Z}_{p}$ -acyclic for some prime p, then every continuous map $f: \ \|\Delta \|\ \longrightarrow \ \|\Delta \|$ has a fixed point.

(A complex is $\mathbb{Z}_{p}$-acyclic if its reduced homology with $\mathbb{Z}_{p}$-coefficients vanishes. That is, in terms of homology it looks like a contractible space, say a d-ball.)

Proof (Sketch)

For a finite simplicial complex $\Delta$, the polyhedron $\|\Delta \|$ is compact. So if f does not have a fixed point, there is some ɛ > 0 such that | f(x) − x | > ɛ for all $x \in \Delta$. Now take a subdivision $\Delta '$ of $\Delta$ into simplices of diameter smaller than ɛ, and a simplicial approximation of error smaller than ɛ∕2, so that the simplicial approximation $f': \Delta ' \rightarrow \Delta '$, which is homotopic to f, does not have a fixed point, either.

Now apply the trace theorem to see that L _k (f) is zero, contrary to the assumption, where the induced map f _∗0 ^′ = f _∗0 in 0-dimensional homology is the identity. □

Note that Brouwer’s fixed point Theorem 2.4 is the special case of Theorem A.2 when $\Delta$ triangulates a ball.

For a reasonably large class of spaces, a converse to the Lefschetz fixed point theorem is also true: If L(f) = 0, then f is homotopic to a map without fixed points. See Brown [21, Chap. VIII].

1.2 The Theorems of Smith and Oliver

In addition to the usual game of connections between graphs, posets, complexes and spaces, we will now add groups. Namely we will discuss some useful topological effects caused by symmetry, that is, by finite group actions.

A (finite) group G acts on a (finite) simplicial complex $\Delta$ if each group element corresponds to a permutation of the vertices of $\Delta$, where composition of group elements corresponds to composition of permutations, in such a way that g(A) : =  {gv: v ∈ A} is a face of $\Delta$ for all g ∈ G and for all $A \in \Delta$. This action on the vertices is extended to the geometric realization of the complex $\Delta$, so that G acts as a group of simplicial homeomorphisms $g: \ \|\Delta \|\ \longrightarrow \ \|\Delta \|$.

The action is faithful if only the identity element in G acts as the identity permutation. In general, the set $G_{0}\:=\ \{g \in G:\, gv = v\mbox{ for all }v \in \mbox{ vert}(\Delta )\}$ is a normal subgroup of G. Hence we get that the quotient group G∕G ₀ acts faithfully on $\Delta$, and we usually only consider faithful actions. In this case, we can interpret G as a subgroup of the symmetry group of the complex $\Delta$. The action is vertex transitive if for any two vertices v, w of $\Delta$ there is a group element g ∈ G with gv = w.

A fixed point (also known as stable point) of a group action is a point $x \in \|\Delta \|$ that satisfies gx = x for all g ∈ G. We denote the set of all fixed points by $\Delta ^{G}$. Note that $\Delta ^{G}$ is in general not a subcomplex of $\Delta$.

Example A.3

Let $\Delta = 2^{[3]}$ be the complex of a triangle, and let $G = \mathbb{Z}_{3}$ be the cyclic group (a proper subgroup of the symmetry group $\mathfrak{S}_{3}$), acting such that a generator cyclically permutes the vertices, 1 ↦  2 ↦  3 ↦  1.

This is a faithful action; its fixed point set consists of the center of the triangle only—this is not a subcomplex of $\Delta$, although it corresponds to a subcomplex of the barycentric subdivision $\mbox{ sd}(\Delta )$.

Lemma A.4 (Two barycentric subdivisions)

 

• (1) After replacing $\Delta$ by its barycentric subdivision (informally, let $\Delta:=\mathrm{ sd}(\Delta )$ ), we get that the fixed point set $\Delta ^{G}$ is a subcomplex of  $\Delta$ .

• (2) After replacing $\Delta$ once again by its barycentric subdivision (so now $\Delta:=\mathrm{ sd}^{2}(\Delta ))$ , we even get that the quotient space $\|\Delta \|/G$ can be constructed from $\Delta$ by identifying all faces with their images under the action of G. That is, the equivalence classes of faces of  $\Delta$ , with the induced partial order, form a simplicial complex that is homeomorphic to the quotient space $\|\Delta \|/G$ .

We leave the proof as an exercise. It is not difficult; for details and further discussion see Bredon [18, Sect. III.1].

“Smith Theory” was started by P. A. Smith [69] in the thirties. It analyzes finite group actions on compact spaces (such as finite simplicial complexes), providing relations between the structure of the group to its possible fixed point sets. Here is one key result.

Theorem A.5 (Smith [68])

If P is a p-group (that is, a finite group of order | P | = p ^t for a prime p and some t > 0), acting on a complex $\Delta$ that is $\mathbb{Z}_{p}$ -acyclic, then the fixed point set $\Delta ^{P}$ is $\mathbb{Z}_{p}$ -acyclic as well. In particular, it is not empty.

Proof (Sketch)

The key is that, with the preparations of Lemma A.4, the maps that f induces on the chain groups (with $\mathbb{Z}_{p}$ coefficients) nicely restrict to the chain groups on the fixed point set $\Delta ^{P}$. Passing to traces and using the Hopf trace theorem, one can derive that $\Delta ^{P}$ is non-empty. A more detailed analysis leads to the “transfer isomorphism” in homology, which proves that $\Delta ^{P}$ must be acyclic.

See Bredon [18, Thm. III.5.2] and Oliver [60, p. 157], and also de Longueville [47, Appendix D and E]. □

On the combinatorial side, one has an Euler characteristic relation due to Floyd [25] [18, Sect. III.4]:

$$\displaystyle{\chi (\Delta )\ +\ (\,p - 1)\chi (\Delta ^{\mathbb{Z}_{p} })\ \ =\ \ p\,\chi (\Delta /\mathbb{Z}_{p}).}$$

If P is a p-group (in particular for $P = \mathbb{Z}_{p}$), then this implies that

$$\displaystyle{\chi (\Delta ^{P}) \equiv \chi (\Delta )\pmod p,}$$

using induction on t, where | P | = p ^t.

Theorem A.6 (Oliver [60, Lemma I])

If $G = \mathbb{Z}_{n}$ is a cyclic group, acting on a $\mathbb{Q}$ -acyclic complex $\Delta$ , then the action has a fixed point.

In this case the fixed point set $\Delta ^{G}$ has the Euler characteristic of a point, $\chi (\Delta ^{G}) = 1$ .

Proof

The first statement follows directly from the Lefschetz fixed point theorem: Any cyclic group is generated by a single element g, this element has a fixed point, this fixed point of g is also a fixed point of all powers of g, and hence of the whole group G.

For the second part, take p ^t to be a maximal prime power that divides n, consider the corresponding subgroup isomorphic to $\mathbb{Z}_{p^{t}}$, and use induction on t and the transfer homomorphism, as for the previous proof. □

Unfortunately, results like these may give an overly optimistic impression of the generality of fixed point theorems for acyclic complexes. There are fixed point free finite group actions on balls: Examples were constructed by Floyd and Richardson and others; see Bredon [18, Sect. I.8].

On the positive side we have the following result due to Oliver, which plays a central role in Sect. 4.5.

Theorem A.7 (Oliver’s Theorem I [60, Prop. I])

If G has a normal subgroup P ⊲ G that is a p-group, such that the quotient G∕P is cyclic, acting on a complex $\Delta$ that is $\mathbb{Z}_{p}$ -acyclic, then the fixed point set $\Delta ^{G}$ is $\mathbb{Z}_{p}$ -acyclic as well. In particular, it is not empty.

This is as much as we will need in this chapter. Oliver proved, in fact, a more general and complete theorem that includes a converse.

Theorem A.8 (Oliver’s Theorem II [60])

Let G be a finite group. Every action of G on a $\mathbb{Z}_{p}$ -acyclic complex $\Delta$ has a fixed point if and only if G has the following structure:

G has normal subgroups P ⊲ Q ⊲ G such that P is a p-group, G∕Q is a q-group (for a prime q that need not be distinct from p), and the quotient Q∕P is cyclic.

In this situation one always has $\chi (\Delta ^{G}) \equiv 1\bmod q$ .

Notes The Lefschetz–Hopf fixed point theorem was announced by Lefschetz for a restriced class of complexes in 1923, with details appearing three years later. The first proof for the general version was by Hopf in 1929. There are generalizations, for example to Absolute Neighborhood Retracts; see Bredon [19, Cor. IV.23.5] and Brown [21, Chap. IIII]. We refer to Brown’s book [21].

We refer to Bredon [18, Chapter III] for a nice textbook treatment of Smith Theory. The book by de Longueville [47, Appendix E] also has a very accessible discussion of the fixed point theorems of Smith and Oliver. The exercises concerning fixed point sets of poset maps P → P are drawn from Baclawski and Björner [6].

1.2.1 Exercises

• 1. Verify directly that if f maps ∥T∥ to ∥T∥, where T is a graph-theoretic tree, then f has a fixed point.

  How would you derive this from the Lefschetz fixed point theorem?

• 2. Let P be a poset (finite partially ordered set), and denote by $\Delta (P)$ its order complex (whose faces are the totally ordered subsets). Suppose that f:  P → P is an order-preserving mapping with fixed point set P ^f: = {x ∈ P∣f(x) = x}.

  • (a) Show that if $\Delta (P)$ is acyclic over some field, then

    $$\displaystyle{\mu (P^{f}) = 0,}$$

    where μ(P ^f) denotes the Möbius function (reduced Euler characteristic) of $\Delta (P^{f})$. In particular, P ^f is not empty.

  • (b) Does it follow also that P ^f itself is acyclic?

• 3. Suppose now that f:  P → P is order-reversing and let P _f : = {x ∈ P∣x = f ²(x) ≤ f(x)}. Show that if $\Delta (P)$ is acyclic over some field, then

  $$\displaystyle{\mu (P_{f}) = 0.}$$

  In particular, if f has no fixed edge (i.e., no x such that x = f ²(x) < f(x)) then f has a unique fixed point.