Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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@math.uiuc.edu. This material is based .
