2017 GVSU Summer Mathematics REU Project:
Anti-Games on Steiner Triple Systems
This page gives an overview of David Clark's project for the 2017 GVSU Summer Mathematics Research Experience for Undergraduates.
Desirable experience for applicants • What this project is not • How to apply
SET is a popular card game with strong mathematical structure. The game is played with 81 cards that have shapes printed on them. The shapes on each card have four attributes: color, number, filling, and shape. Each attribute has three possible values. For example, the card below would be described as "Two green striped ovals":
In the game, 12 cards are laid out and players attempt to locate sets of cards.
Another way to phrase the "set rule" is: If two cards in a set share an attribute, then so must the third. Two examples of a set:
One interesting consequence is this:
SET has been very well studied (for example, see the classic paper The Card Game SET by Davis and MacLagan). In particular, SET is an example of a ternary affine geometry. This in turn is a kind of finite geometry -- a (finite) collection of points and lines that follow many of the rules of traditional geometries, but in a finite setting. The interesting consequence from above can be rephrased in geometric terms as the familiar statement: "Any two points determine a unique line."
In Summer 2013, two of my students invented a new game played with SET cards called "Anti-SET". Anti-SET is played as follows:
- Exactly two players, called "Xavier" and "Olivia" can play the game.
- All 81 SET cards are laid out in front of them.
- Players alternate taking one available card into their hand.
- The first player to hold a set loses the game.
These students found a winning strategy for Anti-SET:
You can visualize this strategy abstractly as in the image below, where each card is listed by X (Xavier) or O (Olivia) depending on which player took them. The subscripts indicate the order in which they were picked.
The proof of this theorem involved tools from linear algebra, modern (abstract) algebra, and combinatorics.
In 2014, we generalized this strategy to a larger class of geometric objects called ternary affine geometries, of which SET is one example. In these geometries, the points are the "cards" we play on, and lines are the "sets". It turns out that Anti-SET can be played on an infinite class of ternary affine geometries -- these are basically the same as SET, but with additional properties (beyond number, color, shading, and shape).
What will this research involve?
This summer research will involve generalizing Anti-SET to a broader category of combinatorial objects called Steiner Triple Systems (STSs).
Here's an example of an anti-game played on a Steiner Triple System with 7 points, also called the Fano Plane:
The primary tools, techniques, and activities we will use will be:
- Playing sample games on a variety of concrete examples of STSs and analyzing the results. The goal is to determine if a winning strategy exists for one player, which player that is, and what the strategy is. This could be done using computer searches as well.
- Generalizing these results as broadly as we can. What properties of an STS determines who can win? What general statements can we make about these games?
- Looking for and understanding special structures within the points of an STS that help determine the winning strategy, as well as ways to allow a losing player to prolong the game.
I expect this to be more subtle than the story for the original SET game. We will begin by reviewing the techniques and arguments used by previous students, which I expect will be helpful as we study STSs.
Desirable experience for applicants
Applicants should like discrete mathematics, aka Combinatorics. It will help to be comfortable with basic counting techniques (such as combinations and permutations) and combinatorial proofs (counting the same thing in two different ways, so as to find a formula).
Experience with Steiner Triple Systems and finite geometries is not necessary. We will learn key background material together as part of the project.
What this project is not
This project is not about game theory. I am not interested in studying Nash equilibria, pareto-optimal choices, etc. Instead, I am interested in analyzing combinatorial objects and learning how their properties affect this game.