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 ACMSIAM Symposium on Discrete Algorithms (SODA)(2011), 664674.

Global MakerBreaker games on sparse graphs
(with D. Hefetz, M. Krivelevich, M. Stojaković),
European Journal of Combinatorics, 32(2011), 162177.

AvoiderEnforcer: the rules of the game
(with D. Hefetz, M. Krivelevich, M. Stojaković),
Journal of Combinatorial Theory (Series A), 117
(2010), 152163.

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

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

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 MakerBreaker 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 AvoiderEnforcer 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/loglogloglognfactor.
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 MakerBreaker version:
Enforcer can force Avoider to build a Hamilton cycle even if Enforcer's
bias is (1o(1))n/log n.

A sharp threshold for the
Hamilton cycle MakerBreaker game
(with D. Hefetz, M. Krivelevich, M. Stojaković),
Random Structures and Algorithms, 34
(2009) 112122.
The result of unbiased (i.e., (1:1)) MakerBreaker 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 MakerBreaker games
(with D. Hefetz, M. Krivelevich, M. Stojaković),
Journal of Combinatorial Theory (Series B),
99
(2009), 3947.
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
kconnectedness 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
kconnected 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 AvoiderEnforcer games
(with D. Hefetz, M. Krivelevich, M. Stojaković)
Graphs and Combinatorics, 25(2009), 533544.

Planarity, coloring and minor games
(with D. Hefetz, M. Krivelevich, M. Stojaković),
SIAM Journal on Discrete Mathematics, 22
(2008), 194212.
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
dumbbias db_{F} at which the game changes hands
almost surely. The graph of DumbMaker
at the end of a dumbgame is of course nothing else but a random graph
with the appropriate number of edges. And the threshold dumbbias
db_{F} is of course essentially nothing else
but n^{2}/2m_{F}, where m_{F} is
the threshold edgenumber
for the appearance of the property F in the random graph.
Chvatal and Erdős showed that the cleverbias and the dumbbias
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 clevergame 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 nonplanarity, nonkcolorability
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
dumbbiases of the nonplanarity game, though are of the same order of
magnitude, are a constant factor two away from each other.
We investigate the AvoiderEnforcer versions as well, but as usual,
our Avoider strategies are adhoc and probably do not provide the
best possible result.
A better understanding of how to win as Avoider would really be interesting!

BartMoe games, JumbleG and Discrepancy
(with D. Hefetz, M.Krivelevich),
European Journal of Combinatorics, 28,
(2007), 11311143.
A generalization of the JumbleGpaper 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
"TicTacToe Theory" (Cambridge University Press).

AvoiderEnforcer games (with D. Hefetz, M.Krivelevich),
Journal of Combinatorial Theory (Series A), 114
(2007), 840853.
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/loglogloglognfactor.
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 discrepancysetup:
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) 783793.
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 edgedisjoint
Hamiltonian cycles.

Positional games on random graphs, (with M. Stojaković)
Random Structures & Algorithms,
26 (2005) 204223.
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), 233237.
This paper deals with a combinatorial game which is not really
a Maker/Breakertype 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.
Last modified: Sun Jun 30 23:04:55 CEST 2013