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.
Let T(H) be the family of minimal transversals of a Sperner Family, H. Then
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
Interesting note: N×N-sized Hex boards (considered as graphs), for
If we call a T(H) the blocker of H, then a hypergraph is called self-blocking if
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
- g(all vertices of H) = 1
- If g(X) = 1, then g(Y) = 1 for all Y containing X as a subset.
- 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.
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
- D. B. West, Introduction to Graph Theory, Prentice-Hall, c. 1996.
- 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]
- R. Thomas, Some equivalent problems
- P. Seymour, On the two-colouring of hypergraphs, Quart. J. Math., Oxford (2), 25 (1974), 303-312.
Copyright © 1996-2018 Alexander Bogomolny