Source-linked AI summary
Positional Games
Michael Krivelevich
TL;DR
The survey addresses how two-player positional games can be formalized and analyzed, and how they connect to Ramsey theory, probabilistic combinatorics, and related areas. It introduces the basic settings and proof tools, then surveys results including strong-game first-player guarantees, Maker-Breaker criteria, and random-graph threshold behavior. The paper also identifies unresolved difficulties, especially the limited general tools and enormous bounds available for strong games.
Problem
The survey addresses how positional games can be mathematically analyzed across recreational and abstract graph or hypergraph settings, including their connections to other combinatorial disciplines.
Method
The paper surveys basic notions, game types, proof strategies, recent advances, open problems, and connections involving probabilistic intuition in deterministic games.
Results
The survey records that First Player can guarantee at least a draw in every strong game and that random-graph intuition can predict threshold behavior in deterministic games.
Takeaways & Limitations
Positional-game analysis combines strategy stealing, Ramsey-type arguments, potential functions, and probabilistic reasoning across strong and Maker-Breaker games.
Takeaways & Limitations
Strong-game analysis remains constrained by inexplicit strategy-stealing proofs, astronomic Ramsey-type bounds, and unresolved basic games.
Abstract
from arXiv · showhide
Positional games are a branch of combinatorics, researching a variety of two-player games, ranging from popular recreational games such as Tic-Tac-Toe and Hex, to purely abstract games played on graphs and hypergraphs. It is closely connected to many other combinatorial disciplines such as Ramsey theory, extremal graph and set theory, probabilistic combinatorics, and to computer science. We survey the basic notions of the field, its approaches and tools, as well as numerous recent advances, standing open problems and promising research directions.
1. Introductory words
Positional games provide a mathematical framework for two-player games on graphs and hypergraphs, linking recreational examples with modern combinatorics. This survey introduces the field, reviews recent progress and open problems, and emphasizes probabilistic reasoning in deterministic games.
- Positional games formalize two-player games ranging from Tic-Tac-Toe and Hex to abstract games on graphs and hypergraphs.
- The field has matured into a central branch of modern combinatorics with connections to Ramsey theory and other combinatorial disciplines.
- The survey combines a gentle introduction with coverage of recent progress, standing challenges, and open problems.
- The survey highlights the ubiquitous role of probabilistic intuition in analyzing entirely deterministic positional games.
- Because of space limitations, many proofs are omitted or presented only as outlines.
2. Basic setting and examples
Positional games are perfect-information contests in which players claim board elements and pursue designated winning sets, with outcomes determined under optimal play. The section develops this framework through standard examples and representative results, including draw, win, and quantitative bounds.
- A positional game uses a board X, winning-set hypergraph H, and possibly bias parameters p and q specifying how many vertices each player claims per turn.
- Tic-Tac-Toe is a 3-uniform strong game with eight winning lines, and optimal play results in a draw.
- If n ≥3d −1, the d-dimensional geometric-line game on [n]^d is a draw.
- A pairing strategy assigns disjoint point pairs to geometric lines, allowing either player to guarantee not losing.
- If a multigraph has two edge-disjoint spanning trees, Connector wins the connectivity game.
- In the row-column game, Beck gives a lower bound of n/2 + 32√n elements in some line, while Székely gives an upper bound of n/2 + O(√log n).
- Under perfect play, each game has exactly one outcome: a first-player win, second-player win, or draw.
3. Strong games
Strong games award victory to the first player who fully occupies a winning set, otherwise ending in a draw. Strategy stealing and Ramsey-type arguments establish broad results, but their inexplicitness and weak bounds leave most basic strong games unresolved.
- In a strong game, players alternately claim vertices, and the first player wins by fully occupying a winning set; otherwise the game is a draw.
- First Player can guarantee at least a draw in every strong game through strategy stealing.
- Consequently, every strong game has only two possible outcomes: First Player’s win or a draw.
- If no final drawing position exists, Ramsey-type reasoning implies that First Player has a winning strategy.
- For every n, sufficiently large d makes the d-dimensional geometric-line game a First Player win by the Hales-Jewett theorem.
- Strong-game analysis remains difficult because strategy stealing is inexplicit, Ramsey bounds can be astronomic, and adding a winning set can change a win into a draw.
4. Maker-Breaker games
Maker-Breaker games separate the goals of completing and blocking winning sets, connecting game outcomes to hypergraph colorability and potential-function methods. The survey presents criteria for both players, asymptotic examples, and links to strong games.
- Maker wins by occupying a winning set, while Breaker wins by claiming at least one element from every winning set; draws are impossible.
- Maker-Breaker games resemble strong games but differ because Maker need not complete a winning set first and the outcome cannot be a draw.
- If Breaker wins a Maker-Breaker game, the underlying hypergraph is 2-colorable.
- The Erdős-Selfridge criterion uses a potential function to provide a concrete Breaker-win condition and a polynomial-time winning algorithm.
- For an r-uniform hypergraph, Beck’s criterion guarantees a Maker win when |H| > 2^r−3·∆2(H)·|X|.
- In the arithmetic-progression game, the largest Maker-winnable progression length satisfies s(n) = (1 + o(1)) log2 n.
5. Biased games, threshold bias
Biased Maker-Breaker games give players unequal numbers of moves, and threshold bias measures when Breaker can first prevent Maker’s objective. The section develops Box Game and probabilistic criteria, then presents asymptotically sharp thresholds for several games on K_n.
- Biased Maker-Breaker games let Maker and Breaker claim m and b elements per move, respectively, with m = 1 the most commonly studied case.
- Box Game: The Box Game uses pairwise disjoint winning sets and serves as a basic model for biased Maker-Breaker games.BoxMaker claims elements from disjoint boxes while BoxBreaker destroys boxes.
- Box Game: The uniform Box Game changes hands around p = s/ ln n, identifying the scale at which the bias shifts the winner.
- Breaker criteria: Breaker’s biased Erdős-Selfridge criterion supplies a sufficient condition for a winning strategy in a general (p : q) game.The criterion is presented as an extension of the unbiased Breaker criterion.
- Threshold bias: For positive-minimum-degree games on K_n, Breaker’s threshold bias is at most (1 + o(1))n/ ln n, while connectivity has a matching asymptotic scale.The same n/ ln n scale also governs the minimum-degree and Hamiltonicity games.
- Threshold bias: At bias b = (1 −ǫ)n/ ln n, Maker wins the connectivity, fixed-minimum-degree, and Hamiltonicity games for sufficiently large n, so all three thresholds are asymptotic to n/ ln n.The cited results cover connectivity, minimum degree at least c, and Hamiltonicity.
6. Avoider-Enforcer games
Avoider-Enforcer games reverse the Maker-Breaker objective: Avoider tries not to fully claim a losing set, while Enforcer tries to force one. Their bias behavior is often non-monotone, but threshold results and potential-function criteria provide partial structure.
- Definitions: Avoider-Enforcer games assign Avoider and Enforcer at least or exactly a elements and b elements per turn, with Enforcer winning when Avoider fully claims a losing set.The monotone version uses at least a and b claims and restores bias monotonicity, unlike strict rules.
- Definitions: Strict-rule bias behavior can be non-monotone: Avoider wins at biases (1:1) and (2:2), but Enforcer wins at (1:2) on two disjoint 2-sets.This motivates the monotone-rule reformulation.
- Thresholds: For strict connectivity, exact lower and upper threshold biases are obtained, with Enforcer winning when the host graph contains b+1 pairwise edge-disjoint spanning trees.The spanning-tree condition is an Avoider-Enforcer analogue of Lehman’s Maker-Breaker theorem.
- Thresholds: Threshold biases for connectivity, perfect matching, and Hamiltonicity under monotone rules are asymptotically n/ln n.For strict connectivity, both threshold biases can instead be far from the monotone threshold.
- Open limitations: For non-planarity and non-k-colorability, threshold biases are at most 200n/ln n, but the exact biases remain unresolved.For constant-size losing sets, available results are sparse; the triangle game has monotone threshold Θ(n^3/2).
- Tools: Potential-function criteria give sufficient conditions for Avoider wins in biased games, including a criterion applicable when losing sets have size at most r.The criteria work under both strict and monotone rules, although one criterion has no sensitivity to b.
7. More boards, more games
Positional games extend beyond complete graphs to sparse, random, and evolving boards, while also tracking winning time and adapting fast weak-game strategies to strong games. These settings yield threshold, sparsification, and structural results across several game types.
- Sparse and random boards: Sparse-board questions ask when Breaker wins on random graphs or how few edges suffice for Maker to create a prescribed structure.For bounded-degree target graphs H, a host graph with at most cn edges can support a Maker win.
- Sparse and random boards: In a random graph process, Maker begins winning Hamiltonicity exactly when the last vertex of degree below 4 disappears, with high probability.Equivalently, τ(˜G,MHAM)=τ(˜G,δ4).
- Sparse and random boards: For fixed k≥4 and p≤cn^(-2/(k+1)), Breaker wins the unbiased K_k-game on G(n,p) with high probability.The triangle case has a different threshold, p=n^(-5/9), linked to the appearance of K5−e.
- Sparse and random boards: For every d>0, every bounded-maximum-degree target graph H has a host graph with at most cn edges where Maker wins the unbiased H-game.These questions are viewed as game analogues of size Ramsey numbers, though general size-Ramsey bounds do not directly yield the stated result.
- Winning time and strong games: Maker-Breaker Hamiltonicity has move number n+1 for all sufficiently large n, while strong perfect matching, Hamiltonicity, and spanning k-connectivity games are First Player wins for large n.Fast Maker-Breaker strategies underpin the strong-game results and yield explicit First Player strategies.
- Other game classes: Maker can create any prescribed k-vertex tournament for k=(2−o(1))log2 n, and this bound is asymptotically optimal.
8. Open problems and challenges
The survey highlights open problems across positional-game types, including strong, Maker-Breaker, Avoider-Enforcer, and Chooser-Picker games. It also reviews major gaps in local Breaker criteria and identifies connections to probabilistic combinatorics and computer science.
- Other directions: Chooser-Picker and Picker-Chooser games remain largely uncharted, with many natural problems still open.The survey presents these games as a promising area for further research.
- Strong games: For the strong clique game, an explicit strategy guaranteeing a first-player win within a bounded number of moves remains unknown, even for q = 5.Strategy stealing proves a win for sufficiently large n but gives a highly inexplicit strategy.
- Weak Maker-Breaker games: In the degree game, d/4 is the best known minimum-degree guarantee for Maker, while improving it to (1/4 + ε)d remains open.For d ≫ log n, discrepancy results yield (1/2 − o(1))d.
- Weak Maker-Breaker games: A further Maker-Breaker challenge asks whether sufficiently high chromatic number in G guarantees Maker a graph of chromatic number at least r under every fixed bias b.The stated problem requires a constant C = C(b, r) for all graphs with chromatic number at least C.
- Neighborhood conjecture: The neighborhood conjecture remains a central open problem because existing Breaker criteria do not account for the hypergraph’s local structure.The survey connects this problem to the Lovász Local Lemma, satisfiability, and computer science.
- Avoider-Enforcer games: The strict Avoider-Enforcer Hamiltonicity game has an unresolved threshold bias, with a gap between b− ≥ (1 − o(1))n/ln n and b+ ≤ n/2 − 1.The survey also calls for a general theory of Avoider-Enforcer H-games, which have mostly been studied individually.