Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: On winning fast in Avoider-Enforcer games. | On winning fast in Avoider-Enforcer games János Barát Department of Computer Science and Systems Technology University of Pannonia Egyetem u. 10 8200 Veszprem Hungary barat@ Milos Stojakovic Department of Mathematics and Informatics University of Novi Sad Serbia akovic@ Submitted Oct 22 2009 Accepted Mar 27 2010 Published Apr 5 2010 Mathematics Subject Classifications 91A43 91A24 Abstract We analyze the duration of the unbiased Avoider-Enforcer game for three basic positional games. All the games are played on the edges of the complete graph on n vertices and Avoider s goal is to keep his graph outerplanar diamond-free and k-degenerate respectively. It is clear that all three games are Enforcer s wins and our main interest lies in determining the largest number of moves Avoider can play before losing. Extremal graph theory offers a general upper bound for the number of Avoider s moves. As it turns out for all three games we manage to obtain a lower bound that is just an additive constant away from that upper bound. In particular we exhibit a strategy for Avoider to keep his graph outerplanar for at least 2n 8 moves being just 6 short of the maximum possible. A diamond-free graph can have at most d n r37-41 edges and we prove that Avoider can play for at least d n 3 moves. Finally if k is small compared to n we show that Avoider can keep his graph k-degenerate for as many as e n moves where e n is the maximum number of edges a k-degenerate graph can have. Supported by OTKA Grant PD 75837 and Janos Bolyai Research Scholarship of the Hungarian Academy of Sciences. tPartly supported by Ministry of Science and Technological Development Republic of Serbia and Provincial Secretariat for Science Province of Vo jvo dina. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R56 1 1 Introduction In this paper we deal with Avoider-Enforcer positional games. For a hypergraph F the game is played by two players Avoider and Enforcer. They alternately
