tailieunhanh - Báo cáo toán học: "Biased Positional Games and Small Hypergraphs with Large Covers"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Biased Positional Games and Small Hypergraphs with Large Covers. | Biased Positional Games and Small Hypergraphs with Large Covers Michael Krivelevich Tibor Szabo y Submitted Feb 24 2007 Accepted May 1 2008 Published May 5 2008 Mathematics Subject Classification 91A43 91A46 05C65 Abstract We prove that in the biased 1 b Hamiltonicity and k-connectivity MakerBreaker games k 0 is a constant played on the edges of the complete graph Kn Maker has a winning strategy for b log 2 o 1 n log n. Also in the biased 1 b Avoider-Enforcer game played on E Kn Enforcer can force Avoider to create a Hamilton cycle when b 1 o 1 n log n. These results are proved using a new approach relying on the existence of hypergraphs with few edges and large covering number. 1 Introduction Positional games involve two players who alternately occupy the elements of a given set V the board of the game. The focus of their attention is a given family F d . ekg c 2 of subsets of V usually called the family of winning sets. The players exchange turns occupying one previously unoccupied element of V. The game ends when there are no unoccupied elements of V. The game is specified completely by defining who wins in every final position or more generally for every possible game scenario. An interested reader is invited to read several survey papers of Jozsef Beck on the subject see . 4 and also his forthcoming book 5 for an extensive background on this fascinating subject. There are several types of positional games depending on how the identity of the winner is determined. In this paper we restrict our attention to two of them. School of Mathematical Sciences Raymond and Beverly Sackler Faculty of Exact Sciences Tel Aviv University Tel Aviv 69978 Israel. Email krivelev@. Research supported in part by a USA-Israel BSF grant by a grant from the Israel Science Foundation and by the Pazy Memorial Award. yInstitute of Theoretical Computer Science ETH Zurich CH-8092 Switzerland. Email sz-abo@. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R70 1 .