Journal of Combinatorics

Volume 3 (2012)

Number 4

Chain-making games in grid-like posets

Pages: 633 – 649

DOI: http://dx.doi.org/10.4310/JOC.2012.v3.n4.a3

Authors

Daniel W. Cranston (Department of Mathematics, Virginia Commonwealth University, U.S.A.)

William B. Kinnersley (Department of Mathematics, Ryerson University, Canada)

Kevin G. Milans (Department of Mathematics, West Virginia University, U.S.A.)

Gregory J. Puleo (Department of Mathematics, University of Illinois, U.S.A.)

Douglas B. West (Department of Mathematics, Zhejiang Normal University, China; Department of Mathematics, University of Illinois, U.S.A.)

Abstract

We study the Maker-Breaker game on chains in a poset. In a chain-product poset, the maximum size of a chain that Maker can guarantee building is $k-$[$r/2$], where $k$ is the maximum size of a chain in the poset and $r$ is the maximum size of a factor chain. We also study a variant where Maker must build a chain in increasing order, called the ordered chain game. Within the bottom $k$ levels of a product of $d$ chains of size at least $k$, Walker can guarantee a chain that hits all levels if $d\ge14$; this result uses a solution to Conway's Angel-Devil game. When $d=2$, the maximum that Walker can guarantee is only $2/3$ of the levels; when $d=3$, Walker cannot guarantee all levels, as shown by Clarke, Finbow, Fitzpatrick, Messenger, and Nowakowski by studying a related game. It is unknown whether Walker can guarantee all levels when $4\le d\le 13$. In the product of two chains of equal size, Walker can guarantee $2/3$ of the levels asymptotically.

Full Text (PDF format)