tailieunhanh - Báo cáo toán học: "Discrepancy games"

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: Discrepancy games. | Discrepancy games Noga Alon Schools of Mathematics and Computer Science Raymond and Beverly Sackler Faculty of Exact Sciences Tel Aviv University Tel Aviv 69978 Israel and IAS Princeton NJ 08540 USA nogaa@ Michael Krivelevich School of Mathematical Sciences Raymond and Beverly Sackler Faculty of Exact Sciences Tel Aviv University Tel Aviv 69978 Israel krivelev@ Joel Spencer Ỉ Department of Mathematics and Computer Science Courant Institute NYU NY USA spencer@ Tibor Szabo Institut fur Theoretische Informatik ETH Zentrum IFW CH - 8092 Zurich Switzerland szabo@ Submitted Apr 8 2005 Accepted Aug 27 2005 Published Sep 29 2005 Mathematics Subject Classifications 90D42 05C65 Abstract We investigate a game played on a hypergraph H V E by two players Balancer and Unbalancer. They select one element of the vertex set V alternately until all vertices are selected. Balancer wins if at the end of the game all edges e 2 E are roughly equally distributed between the two players. We give a polynomial time Research supported in part by a USA-Israel BSF grant by the Israel Science Foundation by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University and by the Von Neumann Fund. 1 Research supported in part by USA-Israel BSF Grant 2002-133 and by grant 64 01 from the Israel Science Foundation. 1 Research supported in part by a USA-Israel BSF Grant. THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R51 1 algorithm for Balancer to win provided the allowed deviation is large enough. In particular it follows from our result that if H is n-uniform and has m edges then Balancer can achieve having between n 2 ạ ln 2m n 2 and n 2 ựln 2m n 2 of his vertices on every edge e of H. We also discuss applications in positional game theory. 1 Introduction In the classical theory of Maker Breaker positional games a hypergraph H V E is given and the players Maker and Breaker take turns in occupying a previously unoccupied element of the