A Strategy for Maker in the Clique Game which Helps to Tackle some Open Problems by Beck

Details A Strategy for Maker in the Clique Game which Helps to Tackle some Open Problems by Beck A Strategy for Maker in the Clique Game which Helps to Tackle some Open Problems by Beck

2009-09-24

arxiv.org/abs/0909.4362v2

Computer Science

Computer Science and Game Theory

12 pages, no figure

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Strategy for Maker in the Clique Game which Helps to Tackle some Open Problems by Beck does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Strategy for Maker in the Clique Game which Helps to Tackle some Open Problems by Beck, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Strategy for Maker in the Clique Game which Helps to Tackle some Open Problems by Beck will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-424859