On the Games of Hex and Y
Gregory K. Van Patten

This is a brief note on the games of Hex and Y (with a new proof), and the related topic of hypergraphs. For what follows, the Hex and Y boards are represented as near-planar triangulations, with stones placed on the vertices.

A hypergraph H is a family of sets. Each set in the family is sometimes called an edge of the hypergraph. The vertices of H are the elements in the union over all edges of H.

A Transversal of a hypergraph H is a set having non-empty intersection with every edge of H. A transversal T is a Minimal Transversal of H, if no proper subset of T is a transversal of H.

A Sperner Family (also called a Clutter, or an Independent System, or an Antichain) is a hypergraph in which no edge is a subset of another.

Theorem 1

Proving this theorem is a good exercise.

(For a reference to the preceding theorem, see the paper by Seymour, or do a Wikipedia.com search for self-blocking hypergraph, or Condenser, or Clutter.)

The game of Hex provides a way to visualize this theorem. The set of minimal winning paths for Black form the Sperner Family, H. Then T(H) are the minimal winning paths for White. Then by symmetry, we see that T(T(H)) = H is true, for the Hex board.

Interesting note: N×N-sized Hex boards (considered as graphs), for N ≥ 3, contain isomorphic, edge-disjoint spanning trees (I have only found examples for small boards, but I suspect it is true generally; see textbook by West, problem 2.1.41). This is interesting, because this same property holds for the game called Bridg-It, or Gale, and implies that the first player has a simple winning strategy, no matter where the first move is placed (see textbook by West, theorem 2.1.15). However, the same idea does not work for Hex.

If we call a T(H) the blocker of H, then a hypergraph is called self-blocking if T(H) = H. I have also seen such hypergraphs called self-transversal.

It is not hard to see that the following is an equivalent way of defining a self trans-transversal hypergraph. Suppose that function g maps the set of subsets of set S into {0, 1}, and g satisfies:

1. g(all vertices of H) = 1
2. If g(X) = 1, then g(Y) = 1 for all Y containing X as a subset.
3. If g(X) = 1, then g(complement of X) = 0.

If these three conditions hold, then the collection of minimal sets mapping to 1, under g, form a self-transversal hypergraph. A set X mapping to 1, under g, is minimal if any proper subset of X maps to 0, under g.

Suppose the following game is played on a self-transversal hypergraph H: Two players take turns coloring vertices. On his turn, player-1 colors vertices black, while player-2 colors vertices white. If a player colors all vertices in a hyperedge with his color, then he wins. If H is self-transversal, then this game will always have a winner.

Let S be a set of integers that add up to an odd sum, N. Then all minimal subsets of S, which add to more than N/2, form a self-transversal hypergraph.

The Fano Plane forms a self-transversal hypergraph.

Theorem 2

The minimal winning sets of any generalized Y-game form a self-transversal hypergraph.

("generalized Y" means that the game is played on an arbitrary near-planar triangulation) This theorem follows from a brilliant application of Sperner's Lemma! See the proof of Lemma 6 in the Hochberg/McDiarmid/Saks paper. This result is repeated in the proof of Lemma 8.3.23 of West's textbook.

I will call a Hex or Y board "standard", if it's graph is a tiling by equilateral triangles.

Conjecture: The three smallest standard Y-boards are the only ones forming uniform self-transversal hypergraphs (all hyperedges the same size).

Observation: The standard Y-board with side length = 3, forms a self-transversal hypergraph such that the complement hypergraph (consisting of the complements of each edge) is also self-transversal.

References

1. D. B. West, Introduction to Graph Theory, Prentice-Hall, c. 1996.
2. R. Hochberg, C. McDiarmid, M. Saks, On the bandwidth of triangulated triangles, Discrete Mathematics, 138 (1995), 261-265. (online version") [also Proc. 14th Brit. Comb. Conf. Keele 1993; referenced in the textbook by West]
3. R. Thomas, Some equivalent problems
4. P. Seymour, On the two-colouring of hypergraphs, Quart. J. Math., Oxford (2), 25 (1974), 303-312.

Copyright © 1996-2009 Alexander Bogomolny