Consider the following random process: The vertices of a binomial random graph Gn,p are revealed one by one, and at each step only the edges induced by the already revealed vertices are visible. Our goal is to assign to each vertex one from a fixed number r of available colors immediately and irrevocably without creating a monochromatic copy of some fixed graph F in the process. Our first main result is that for any F and r, the threshold function for this problem is given by p0F,r,n = n-1 m*1F,r, where m*1F,r denotes the so-called online vertex-Ramsey density of F and r. This parameter is defined via a purely deterministic two-player game, in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. Our second main result states that for any F and r, the online vertex-Ramsey density m*1F,r is a computable rational number.
The question of finding valid -colorings of random graphs online was first considered by Friedgut , who proved a threshold result for the case where @math is a triangle and @math colors are available @cite_13 . @cite_16 @cite_1 , the greedy strategy was analyzed for the edge-coloring setting, and results similar to Theorem were derived for the case of @math colors. @cite_9 , we presented the upper bound approach via deterministic two-player games discussed above; this approach was applied by Balogh and Butterfield to derive new upper bounds for the case where @math is a triangle and @math colors are available @cite_6 . It would be very interesting to determine whether a general result analogous to Theorem holds for the edge-coloring setting. Various edge-coloring Builder-Painter games were studied in the context of deterministic Ramsey theory. The smallest number of moves Builder needs to win in the deterministic edge-coloring game without any restrictions is called the and was studied by many researchers @cite_29 @cite_25 @cite_22 @cite_33 @cite_37 @cite_19 @cite_20 . Variants of the game where Builder is subject to various restrictions were studied in @cite_27 @cite_12 @cite_4 .
@cite_37 @cite_4 @cite_22 @cite_33 @cite_9 @cite_29 @cite_1 @cite_6 @cite_19 @cite_27 @cite_12 @cite_16 @cite_13 @cite_25 @cite_20
2015596743 1524397983 2083596217 2135737379
In the online F-avoidance edge-coloring game with r colors, a graph on n vertices is generated by randomly adding a new edge at each stage. The player must color each new edge as it appears; the goal is to avoid a monochromatic copy of F. Let N"0(F,r,n) be the threshold function for the number of edges that the player is asymptotically almost surely able to paint before he she loses. Even when F=K"3, the order of magnitude of N"0(F,r,n) is unknown for r>=3. In particular, the only known upper bound is the threshold function for the number of edges in the offline version of the problem, in which an entire random graph on n vertices with m edges is presented to the player to be r edge-colored. We improve the upper bound for the online triangle-avoidance game with r colors, providing the first result that separates the online threshold function from the offline bound for r>=3. This supports a conjecture of Marciniszyn, Spohel, and Steger that the known lower bound is tight for cliques and cycles for all r. When graph Ramsey theory is viewed as a game, "Painter" 2-colors the edges of a graph presented by "Builder". Builder wins if every coloring has a monochromatic copy of a fixed graph @math . In the on-line version, iteratively, Builder presents one edge and Painter must color it. Builder must keep the presented graph in a class @math . Builder wins the game @math if a monochromatic copy of @math can be forced. The on-line degree Ramsey number @math is the least @math such that Builder wins @math when @math is the class of graphs with maximum degree at most @math . Our results include: 1) @math if and only if @math is a linear forest or each component lies inside @math . 2) @math , where @math . 3) @math for a tree @math , where @math and @math are two largest vertex degrees. 4) @math , with @math except for finitely many odd values of @math . 5) @math when @math . The lower bounds come from strategies for Painter that color edges red whenever the red graph remains in a specified class. The upper bounds use a result showing that Builder may assume that Painter plays "consistently". Consider the following probabilistic one-player game: The board is a graph with @math vertices, which initially contains no edges. In each step, a new edge is drawn uniformly at random from all nonedges and is presented to the player, henceforth called Painter. Painter must assign one of @math available colors to each edge immediately, where @math is a fixed integer. The game is over as soon as a monochromatic copy of some fixed graph @math has been created, and Painter's goal is to “survive” for as many steps as possible before this happens. We present a new technique for deriving upper bounds on the threshold of this game, i.e., on the typical number of steps Painter will survive with an optimal strategy. More specifically, we consider a deterministic two-player variant of the game where the edges are chosen not randomly, but by a second player Builder. However, Builder has to adhere to the restriction that, for some real number @math , the ratio of edges to vertices in all subgraphs of the evolving board ne... We study the following one-person game against a random graph process: the Player's goal is to @math -colour a random sequence of edges @math of a complete graph on @math vertices, avoiding a monochromatic triangle for as long as possible. The game is over when a monochromatic triangle is created. The online version of the game requires that the Player should colour each edge as it comes, before looking at the next edge.While it is not hard to prove that the expected length of this game is about @math , the proof of the upper bound suggests the following relaxation: instead of colouring online, the random graph is generated in only two rounds, and the Player colours the edges of the first round before the edges of the second round are thrown in. Given the size of the first round, how many edges can there be in the second round for the Player to be likely to win? In the extreme case, when the first round consists of a random graph with @math edges, where @math is a positive constant, we show that the Player can win with high probability only if constantly many edges are generated in the second round.