At the end is the list of references cited in this brief note.This is a brief note on the games of Hex and Y (with a new proof), and the related topic of hypergraphs.
Perhaps you might add some of these ideas to your "Cut-the-Knot" pages on Hex and Y.
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 T(T(H)) = H. Proving this theorem is a good exercize.
(for a reference to the preceding theorem, see the paper by Seymour (below), 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: NxN-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:
A) g(all vertices of H) = 1
B) If g(X) = 1, then g(Y) = 1 for all Y containing X as a subset.
C) 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 have 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 Hocberg/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.
- Gregory K. Van Patten (gkvanpatten@gmail.com)
References:
"Introduction to Graph Theory" by D.B. West, Prentice-Hall, c. 1996.
https://www.stats.ox.ac.uk/people/academic_staff/colin_mcdiarmid/?a=4151
(the preceding links to an online version of "On the bandwidth of triangulated triangles",
by R. Hochberg, C. McDiarmid, M. Saks, Discrete Mathematics, 138 (1995), 261-265.
https://www.math.gatech.edu/~thomas/TEACH/8863in06/SCRIBE/pfafequiv.pdf
"On the two-colouring of hypergraphs", by P. Seymour, Quart. J. Math., Oxford (2), 25 (1974), 303-312.
"Introduction to Graph Theory" by D.B. West, Prentice-Hall, c. 1996.
Printer-friendly copy
Email this topic to a friend
