THE CRITICAL BIAS FOR THE HAMILTONICITY GAME IS (1+o(1))n/ln n

摘要

A Maker-Breaker game is a triple (H, a, b), where H = (V, E) is a hypergraph with vertex set V, called the board of the game, and edge set E, a family of subsets of V called winning sets. The parameters a and b are positive integers, related to the so-called game bias. The game is played between two players, called Maker and Breaker, who change turns occupying previously unclaimed elements of V; Maker claims a elements in his turn, Breaker answers by claiming b elements. We assume that Breaker moves first. The game ends when all board elements have been claimed by either of the players. (In the very last move, if the board does not contain enough elements to claim for the player whose turn is now, that player claims all remaining elements of the board.) Maker wins if and only if he has occupied one of the winning sets e E E by the end of the game. Breaker wins otherwise, i.e., if he manages to occupy at least one element of ("to break into") every winning set by the end of the game. The most basic case is when a b = 1, which is the so-called unbiased game. Here we will be concerned with 1 : b games.