Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Balanced online Ramsey games in random graphs"

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: Balanced online Ramsey games in random graphs. | Balanced online Ramsey games in random graphs Anupam Prakash Department of Computer Science and Engineering IIT Kharagpur India anupam@berkeley.edu Reto Spohely Henning Thomas Institute of Theoretical Computer Science Institute of Theoretical Computer Science ETH Zurich Switzerland ETH Zurich Switzerland rspoehel@inf.ethz.ch hthomas@inf.ethz.ch Submitted Aug 25 2008 Accepted Jan 14 2009 Published Jan 23 2009 Mathematics Subject Classification 05C80 05C15 Abstract Consider the following one-player game. Starting with the empty graph on n vertices in every step r new edges are drawn uniformly at random and inserted into the current graph. These edges have to be colored immediately with r available colors subject to the restriction that each color is used for exactly one of these edges. The player s goal is to avoid creating a monochromatic copy of some fixed graph F for as long as possible. We prove explicit threshold functions for the duration of this game for an arbitrary number of colors r and a large class of graphs F. This extends earlier work for the case r 2 by Marciniszyn Mitsche and Stojakovic. We also prove a similar threshold result for the vertex-coloring analogue of this game. 1 Introduction Consider the following one-player game. Starting with the empty graph on n vertices in every step r new edges are drawn uniformly at random and inserted into the current graph. These edges have to be colored immediately with r available colors subject to the restriction that each color is used for exactly one of these edges. The player s goal is to avoid creating a monochromatic copy of some fixed graph F for as long as possible. We call this game the balanced online F-avoidance edge-coloring game with r colors . Now at UC Berkeley USA. Part of this research was done while the author was visiting ETH Zurich as an intern. yThe author was supported by Swiss National Science Foundation grant 200021-108158. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R11 1 For which