Title: Sperner's Lemma and Connection Games
Speaker: David Molnar, Rutgers University
Date: Tuesday, December 2, 2014 12:00 - 1:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Seminar hosted by James Abello, DIMACS
Abstract:
The game of Hex is the most well-known of the great iceberg of connection games. Hex's cousin The Game of Y is played on a triangular board, with the goal to connect all three sides. A beautiful proof using Sperner's Lemma shows that the game cannot end in a draw. From this the fact that Hex cannot end in a draw follows as a corollary.
In early 2008, Mark Steere published two new connection games, Atoll and Begird, which generalize Hex and Y, respectively. Atoll has received some attention through online play and a feature in Games magazine. Atoll is played on a grid of hexagons surrounded by eight 'islands'; the goal is to connect two opposite islands one one's color. One way to prove that there must be a winner in a game of Atoll, Begird, and in fact infinitely many generalizations, uses a generalized version of Sperner's Lemma. I will discuss this generalization and its consequences.