Dan Cranston

Maker-breaker games: Buliding a large chain in a poset

Abstract. In a maker-breaker game, we fix a base set X and a collection of winning subsets F. The players Maker and Breaker alternate choosing elements from X and Maker wins if he eventually chooses all the elements in some subset in F. Otherwise Breaker wins. (A good example to keep in mind is a modified version of Tic-Tac-Toe, where the first player wins if he gets 3-in-a-row and the second player wins if and only if she stops the first player from winning.)

We consider the problem when the base set X is the set of elements of a partially ordered set (poset) P and Maker's winning set F is the collection of chains in P of a given length. When the poset P is a product of chains, we determine precisely the maximum length chain in P that Maker can attain.

We also consider a variation of the problem where Maker must choose the winning elements of the chain in order. By using surprising connections with Conway's Angel/Devil game, we determine precise bounds for many cases of this variation, as well.

This is joint work with Bill Kinnersley, Kevin Milans, Greg Puleo, and Doug West.