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.

IntroductionPrevious WorkWhat will this research involve?
Desirable experience for applicantsWhat this project is notHow to apply


Introduction

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.

A set consists of exactly 3 cards such that each attribute is either the same on all 3 cards, or different on all 3 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:

Two cards determine a set: For any two cards, there exists exactly one card that will form a set with them.

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


Previous work

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:

Winning strategy for Xavier: The first player (Xavier) chooses any card. Thereafter, after Olivia's move, Xavier always chooses the unique card that forms a set with his first choice and Olivia's most recent choice.

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

A Steiner Triple System on n points is a set of objects called points together with a collection of subsets of the points called blocks, such that each block contains exactly 3 points, and each pair of points appears in exactly one block.

STSs share many of the key geometric features which made a winning strategy possible for Anti-SET. In particular, the requirement that every pair of points appear in exactly one block is exactly analogous to the fact that any two cards determine a unique set. However, STSs have more "wiggle room" than affine geometries, and so games will be that much more interesting!

Here's an example of an anti-game played on a Steiner Triple System with 7 points, also called the Fano Plane:

In this case, Xavier lost at the very end. Does that always happen?

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.


How to Apply

You can find application information and instructions on the GVSU Summer Mathematics REU home page.