Paper Info
Title
A Strategy for Maker in the Clique Game which Helps to Tackle some Open Problems by Beck
Abstract
We study Maker/Breaker games on the edges of the complete graph, as introduced by Chvatal and Erdos. We show that in the (m:b) clique game played on K_{N}, the complete graph on N vertices, Maker can achieve a K_{q} for q = (m/(log_{2}(b + 1)) - o(1)) * log N, which partially solves an open problem by Beck. Moreover, we show that in the (1:1) clique game played on K_{N} for a sufficiently large N, Maker can achieve a K_{q} in only 2^(2q/3) moves, which improves the previous best bound and answers a question of Beck. Finally we consider the so called tournament game. A tournament is a directed graph where every pair of vertices is connected by a single directed edge. The tournament game is played on K_{N}. At the beginning Breaker fixes an arbitrary tournament T_{q} on q vertices. Maker and Breaker then alternately take turns at claiming one unclaimed edge e and selecting one of the two possible orientations. Maker wins if his graph contains a copy of the goal tournament T_{q}; otherwise Breaker wins. We show that Maker wins the tournament game on K_{N} with q = (1 - o(1))*log_{2}(N) which supports the random graph intuition: the threshold for q is asymptotically the same for the game played by two "clever'' players and the game played by two ``random'' players. This last result solves an open problem of Beck which he included in his list of the seven most humiliating open problems.
Year
Venue
Keywords
2009
Clinical Orthopaedics and Related Research
directed graph,complete graph,random graph,discrete mathematics,game theory
Field
DocType
Volume
Complete graph,Binary logarithm,Mathematical economics,Combinatorics,Tournament,Random graph,Open problem,Clique,Vertex (geometry),Directed graph,Mathematics
Journal
abs/0909.4
Citations 
PageRank 
References 
0
0.34
1
Authors
1
Name
Order
Citations
PageRank
Heidi Gebauer18311.07