Computer Science/Discrete Mathematics Seminar I

We consider biased positional games, played on the edge set of a complete graph Kn on n vertices. These games are played by two players, called Maker and Breaker, who take turns in claiming previously unoccupied edges of Kn. Maker claims a single edge at each turn, while Breaker answers by claiming b>=1 edges. Maker wins if by the end of the game his graph satisfies a given monotone graph property P, otherwise the win is Breaker's. We prove that if the game bias b satisfies b=(1-o(1))n/\log_2n, then Maker has a winning strategy in both the Hamiltonicity and the k-connectivity games (for every fixed k). This improves and extends best known estimates for the critical bias for Maker's win in these games, due to Beck and others. The proof combines the so called generalized Erdos-Selfridge criterion for Breaker's win in biased games derived by Beck, a recently obtained sufficient condition for Hamiltonicity due to Hefetz, Krivelevich and Szabo, and a new approach based on the existence of hypergraphs with few hyperedges and large covering number. A similar result can be proven for the biased Avoider-Enforcer Hamiltonicity game. A joint work with Tibor Szabo, ETH Zurich.