Positional Games

After scattered results, the theory of positional games originates from an important paper of Erdős and Selfridge. Later the theory was greatly developed by József Beck. Besides being an interesting field on its own, positional games inspired the technique of derandomization from theoretical computer science, most notably the algorithmization of the Local Lemma.
In the usual setup two players, Maker and Breaker, play against each other by alternately occupying one previously unoccupied element of a given finite set (the board). Maker wins if he succeeds in completely occupying one of the members of a given setsystem F (the family of winning sets), otherwise Breaker wins. There is a large literature on graph games, i.e., when the board is the edgeset of some graph, say the complete graph. Often the game is won by Maker and thus Chvatal and Erdős suggested to give Breaker a break in the form of a bias: at every move he is allowed to take b elements of the board instead of just one (which is called the (1:b) biased game).

• The Local Lemma is tight for SAT (with H. Gebauer, G. Tardos), 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)(2011), 664-674.


• Global Maker-Breaker games on sparse graphs (with D. Hefetz, M. Krivelevich, M. Stojaković), European Journal of Combinatorics, 32(2011), 162-177.


• Avoider-Enforcer: the rules of the game (with D. Hefetz, M. Krivelevich, M. Stojaković), Journal of Combinatorial Theory (Series A), 117 (2010), 152-163.


• Asymptotic random graph intuition for the biased connectivity game (with H. Gebauer), Random Structures and Algorithms , 35 (2009), 431-443.


• Hamilton cycles in highly connected and expanding graphs (with D. Hefetz, M. Krivelevich), Combinatorica , 29 (2009), 547-568.


• How long can a graph be kept planar? (with V. Anuradha, C. Jain, J. Snoeyink), Electronic Journal of Combinatorics, 15(1) (2008), N14.
  An extended abstract appeared at the 17th Fall Workshop on Computational and Combinatorial Geometry.


• Biased positional games and small hypergraphs with large covers (with M. Krivelevich) Electronic Journal of Combinatorics, 15(1) (2008), R70.
  In this paper we deal with/resolve two problems of Beck concerning Hamiltonicity games. In the Maker-Breaker version Chvátal and Erdős proved that if Breaker plays with bias (1+o(1))n/log n then he is able to isolate a vertex in Maker's graph, so in particular wins the Hamiltonicity game as well. From the other side, Beck showed that if Breaker's bias is only ((log2)/27 - o(1))n/log n then Maker can still build a Hamilton cycle. Here we improve this to (log2 - o(1))n/log n, which is now equal to the best known lower bound for the critical bias in the (much easier) connectivity game. For the Avoider-Enforcer version of the Hamiltonicity game earlier (with D. Hefetz) we established that the critical bias is at least is of order n/log n up to a logloglogn/loglogloglogn-factor. Here we erase this extra factor with an extra twist. Somewhat surprisingly, the lower bound for the critical bias becomes better than the lower bound for the Maker-Breaker version: Enforcer can force Avoider to build a Hamilton cycle even if Enforcer's bias is (1-o(1))n/log n.


• A sharp threshold for the Hamilton cycle Maker-Breaker game (with D. Hefetz, M. Krivelevich, M. Stojaković), Random Structures and Algorithms, 34 (2009) 112-122.
  The result of unbiased (i.e., (1:1)) Maker-Breaker games is studied when the board is the random graph G(n,p). The property of "being a Maker's win" is a monotone increasing one for any fixed graph game F, so the existence of a threshold probability p_F when Breaker's win turns into Maker's win is provided by the classic theorem of Bollobás and Thomason. The highlight of the paper is a "positional game theoretic analogue" of the theorems of Pósa, and Komlós and Szemerédi for the threshold of Hamiltonicity in random graphs. It is well known that the first Hamilton cycles appear in G(n,p) when the probability p is about logn/n. We prove that not only there is a Hamilton cycle in G(n,p) when p=(1+epsilon)logn/n, but Maker can occupy one while playing against a skilled adversary (i.e., Breaker)!


• Fast winning strategies in Maker-Breaker games (with D. Hefetz, M. Krivelevich, M. Stojaković), Journal of Combinatorial Theory (Series B), 99 (2009), 39-47.
  In a (1:1) Maker/Breaker positional game on the edges of the complete graph the questions of how to win is usually not a problem. In this paper we rather study the question of how fast. That is, what is the smallest number of moves in which Maker can occupy a winning set. A trivial lower bound is of course the size of a winning set. We find that in a number of natural games, like perfect matching, Hamiltonicity and k-connectedness this can be achieved: Maker hardly needs to make any moves which later turns out to be superflous. In partcicular we prove that Maker can build a Hamilton cycle in just n+2 moves. Another interesting feature of the paper is that our strategy for building a k-connected graph in essentially kn/2 moves is only an existence argument, using random graphs. We also study the corresponding question for Avoider/Enforcer games. Here, since Enforcer usually wins the (1:1) game, Avoider's goal is to postpone his loss as long as possible, and have a slow losing strategy. A trivial general upper bound on the number of moves is the extremal number ex(n, F) of the family F of winning sets, while a trivial lower bound is the half of ex(n, F). It turns out that any of these two could practically be tight.


• Fast winning strategies in Avoider-Enforcer games (with D. Hefetz, M. Krivelevich, M. Stojaković) Graphs and Combinatorics, 25(2009), 533-544.


• Planarity, coloring and minor games (with D. Hefetz, M. Krivelevich, M. Stojaković), SIAM Journal on Discrete Mathematics, 22 (2008), 194-212.
  A very intriguing paradigm in the theory of biased graph games is the mysterious relationship to the theory of random graphs. On the one hand, in a usual Maker/Breaker positional game where the players are assumed to be clever, there is the critical bias b_F of Breaker at which the game changes hands, and becomes a Breaker's win instead of a Maker's win. On the other hand, in a positional game where the players are assumed to be dumb (for us this means that they play randomly) one can talk about the threshold dumb-bias db_F at which the game changes hands almost surely. The graph of DumbMaker at the end of a dumb-game is of course nothing else but a random graph with the appropriate number of edges. And the threshold dumb-bias db_F is of course essentially nothing else but n²/2m_F, where m_F is the threshold edge-number for the appearance of the property F in the random graph. Chvatal and Erdős showed that the clever-bias and the dumb-bias are of the same order of magnitude for the connectivity game (when Maker's goal is the occupation of a spanning tree). This is true despite the fact that neither of the player's strategies in the clever-game involve any randomness. Beck proved a similar result for the Hamiltonicity game and discovered numerous other occurences of this "random graph intuition". In this paper we determine the clever biases of several Maker/Breaker games, like non-planarity, non-k-colorability and the game in which Maker's goal is to build a K_k-minor. We find that the random graph intuition is not valid to the constant factor. For example the critical clever- and dumb-biases of the non-planarity game, though are of the same order of magnitude, are a constant factor two away from each other. We investigate the Avoider-Enforcer versions as well, but as usual, our Avoider strategies are ad-hoc and probably do not provide the best possible result. A better understanding of how to win as Avoider would really be interesting!


• Bart-Moe games, JumbleG and Discrepancy (with D. Hefetz, M.Krivelevich), European Journal of Combinatorics, 28, (2007), 1131-1143.
  A generalization of the JumbleG-paper to the (p:1) biased game: we give a strategy for Maker to build a pseudorandom graph of density p/(p+1). The player's names are motivated by the Simpsons. They represent the fact that the first player plays as BreakerandAvoider and the second player as MakerorEnforcer. The similar question in the (1:q) game, when Maker's goal is to build a pseudorandom graph of density 1/(q+1), poses an unexpected challange. This was resolved by Beck in his soon(?) to be published book "Tic-Tac-Toe Theory" (Cambridge University Press).


• Avoider-Enforcer games (with D. Hefetz, M.Krivelevich), Journal of Combinatorial Theory (Series A), 114 (2007), 840-853.
  Avoider/Enforcer games are the misere version of Maker/Breaker games: the player called Avoider wins if he succeeds in not occupying any winning set, otherwise Enforcer wins. A threshold bias theory, similar to that of Maker/Breaker games, of biased Avoider/Enforcer games is developed. Unexpected difficulties arise. For example, despite being a very plausible claim, "taking more edges than its required bias can only hurt a player's chance of winning an Avoider/Enforcer game" is (very) not true in general. There are, although somewhat artificial, games for which the winner of the game depends on the parity of the bias. Note that the corresponding "plausible claim" about Maker/Breaker games, that "taking less moves than the required bias can only hurt a player's chances of winning a Maker/Breaker game" is more or less obviously true! For Avoider/Enforcer games we do not even know whether a critical bias exists for such natural games, as perfect matching or Hamiltonicity. On the positive side, the critical bias exists and is determined for the game of connectivity. Somewhat surprisingly, and contrary to the Maker/Breaker version, the critical bias is linear in n (as opposed to n/log n). Our original motivation for this research was a problem of Beck who asked whether Enforcer, playing with a bias of n/logn can still force that Avoider builds a Hamilton cycle. We come awfully close, missing the bound only by a logloglogn/loglogloglogn-factor. The core of the proof is a new pseudorandom criterion for Hamiltonicity, contained in here.


• Discrepancy games (with N. Alon, M. Krivelevich, J. Spencer), Electronic Journal of Combinatorics, 12(2005), R51.
  Two new and probably nicer proofs are given to the theorem discussed in the paper below. Also, the statement is formulated in a more general discrepancy-setup: playing (1:1) on an arbitrary hypergraph, Maker is able to achieve that by the end he occupies roughly half of each hyperedge (not more and not less!).


• The game of JumbleG, (with A. Frieze, M. Krivelevich, O. Pikhurko), Combinatorics, Probability and Computing, 14 (2005) 783-793.
  We consider Maker/Breaker games played on the edges of the complete graph. We give a strategy for Maker to create a pseudorandom graph of density 1/2. Applying known results for pseudorandom graphs, this also gives a strategy for Maker in several other games studied earlier; for example Maker is able to build (1+o(1))n/4 edge-disjoint Hamiltonian cycles.


• Positional games on random graphs, (with M. Stojaković) Random Structures & Algorithms, 26 (2005) 204--223.
  We initiate the study of positional games on random graphs. In the traditional setup of Maker/Breaker games if Maker's goal is too "easy" one is aiming to determine the smallest bias b such that Breaker, playing b moves against one move of Maker, can prevent Maker from achieving his goal. In this paper we investigate a different way to reduce Maker's power: the random thinning of the board. The threshold probability where a Breaker's win suddenly turns into a Maker's win is determined or estimated for several basic games, like connectivity, perfect matching, Hamiltonicity or clique. Sometimes there is a remarkable connection to the corresponding threshold bias of the biased games.


• On Erdős' Eulerian Trail Game, (with Á. Seress) Graphs and Combinatorics, 15 (1999), 233-237.
  This paper deals with a combinatorial game which is not really a Maker/Breaker-type game in the sense that here one of the players (called Trailmaker) wins if the two players build something (an Eulerian trail) together. Each player has to start his edge where the other player finished. The problem originates from Paul Erdős and we resolve it completely, even in the biased case.