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 the Chv´tal-Erd˝s triangle game a o. | On the Chvatal-Erdos triangle game Jozsef Balogh and Wojciech Samotj Submitted Oct 13 2010 Accepted Mar 22 2011 Published Mar 31 2011 Mathematics Subject Classification 05C57 05C35 91A24 91A43 91A46 Abstract Given a graph G and positive integers n and q let G G n q be the game played on the edges of the complete graph Kn in which the two players Maker and Breaker alternately claim 1 and q edges respectively. Maker s goal is to occupy all edges in some copy of G Breaker tries to prevent it. In their seminal paper on positional games Chvatal and Erdos proved that in the game G K3 n q Maker has a winning strategy if q 2n 2 5 2 and if q 2ựũ then Breaker has a winning strategy. In this note we improve the latter of these bounds by describing a randomized strategy that allows Breaker to win the game G K3 n q whenever q 2 1 24 yjn. Moreover we provide additional evidence supporting the belief that this bound can be further improved to a 2 ơ 1 ựũ. 1 Introduction In a positional game the two players traditionally called Maker and Breaker alternately occupy previously unoccupied elements of a given finite set X. Maker wins if he manages to completely occupy one of the members of a prescribed set system HQ 2X otherwise Breaker wins. A particular family of positional games originates from a seminal paper of Chvatal and Erdos 4 . Let P be a monotone graph property. In the biased P-game Maker and Breaker are alternately claiming 1 and at most q edges of the complete graph Kn per round respectively. Maker s goal is to build a graph with property P Breaker wins the game if he prevents Maker from achieving this goal after all n edges of Kn have been occupied. Chvatal and Erdos 4 asked about the threshold for the bias q in such a Department of Mathematics University of Illinois 1409 W Green Street Urbana IL 61801 USA and Department of Mathematics University of California San Diego 9500 Gilman Drive La Jolla CA 92093 USA. E-mail address jobal@. This material is based .
