Paperlane

no. 16 · Tuesday 17 November 2026

The transversal game

Žarko Ranđelović

math.CO · v3 · 15 pp

Abstract

Two players take turns claiming empty cells from an $n\times n$ grid. The first player (if any) to occupy a transversal (a set of $ n $ cells having no two cells in the same row or column) is the winner. What is the outcome of the game given optimal play? Our aim in this paper is to show that for $n\ge 4$ the first player has a winning strategy. This answers a question of Erickson. We also consider variants of the game in which the family of winning transversals is restricted, both in the original game and in its Maker–Breaker version.

comments
15 pages
fields
Combinatorics
pdf ↗ page arXiv:2401.16768 ↗