# 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

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 *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 *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

- 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.

### 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

### References

- 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.

|Contact| |Front page| |Contents| |Algebra| |Games|

Copyright © 1996-2018 Alexander Bogomolny