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 2963885173 2811269531 2046633098 1610636547 2115831572 2052952091 2279830512 2088272899 2157562188 2065826935 1999757901
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. In this paper we establish a substantially improved lower bound on the k-color ability threshold of the random graph G(n, m) with n vertices and m edges. The new lower bound is ≈ 1.39 less than the 2k ln (k)-ln (k) first-moment upper bound (and approximately 0.39 less than the 2k ln (k) - ln(k) - 1 physics conjecture). By comparison, the best previous bounds left a gap of about 2+ln(k), unbounded in terms of the number of colors [Achlioptas, Naor: STOC 2004]. Furthermore, we prove that, in a precise sense, our lower bound marks the so-called condensation phase transition predicted on the basis of physics arguments [: PNAS 2007]. Our proof technique is a novel approach to the second moment method, inspired by physics conjectures on the geometry of the set of k-colorings of the random graph. The @math -online Ramsey game is a combinatorial game between two players, Builder and Painter. Starting from an infinite set of isolated vertices, Builder draws an edge at each step and Painter immediately paints the edge red or blue. Builder's goal is to force Painter to create either a red @math or a blue @math using as few edges as possible. The online Ramsey number @math is the minimum number of edges Builder needs to guarantee a win in the @math -online Ramsey game. By analyzing the special case where Painter plays randomly, we obtain an exponential improvement [ r (n,n) 2^ (2- 2 )n + O(1) ] for the lower bound on the diagonal online Ramsey number, as well as a corresponding improvement [ r (m,n) n^ (2- 2 )m + O(1) ] for the off-diagonal case, where @math is fixed and @math . Using a different randomized Painter strategy and the Lopsided Lov 'asz Local Lemma, we prove that @math , determining this function up to a polylogarithmic factor. We also improve the upper bound in the off-diagonal case for @math . In connection with the online Ramsey game with random Painter, we study the problem of finding a copy of a target graph @math in a sufficiently large unknown Erd o s--R ' e nyi random graph @math using as few queries as possible, where each query reveals whether or not a particular pair of vertices are adjacent. We call this problem the Subgraph Query Problem. We determine the order of the number of queries needed for complete graphs up to five vertices and prove general bounds for this problem. We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval I there is a color that appears exactly once in I. We present several deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring Ω(√n) colors in the worst case. We then modify this approach, to obtain an efficient deterministic algorithm that uses a maximum of Θ(log2 n) colors. Next, we present two randomized solutions. The first algorithm requires an expected number of at most O(log2 n) colors, and produces a coloring which is valid with high probability, and the second one, which is a variant of our efficient deterministic algorithm, requires an expected number of at most O(log n log log n) colors but always produces a valid coloring. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order, and present an incomplete analysis that indicates that, with high probability, it uses only O(log n) colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case. The average-case behavior for disks, and cases involving other planar ranges, are still open. For many random constraint satisfaction problems such as random satisfiability or random graph or hypergraph coloring, the best current estimates of the threshold for the existence of solutions are based on the first and the second moment method. However, in most cases these techniques do not yield matching upper and lower bounds. Sophisticated but non-rigorous arguments from statistical mechanics have ascribed this discrepancy to the existence of a phase transition called condensation that occurs shortly before the actual threshold for the existence of solutions and that affects the combinatorial nature of the problem (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborova: PNAS 2007). In this paper we prove for the first time that a condensation transition exists in a natural random CSP, namely in random hypergraph 2-coloring. Perhaps surprisingly, we find that the second moment method applied to the number of 2-colorings breaks down strictly before the condensation transition. Our proof also yields slightly improved bounds on the threshold for random hypergraph 2-colorability. For many random constraint satisfaction problems, by now there exist asymptotically tight estimates of the largest constraint density for which solutions exist. At the same time, for many of these problems, all known polynomial-time algorithms stop finding solutions at much smaller densities. For example, it is well-known that it is easy to color a random graph using twice as many colors as its chromatic number. Indeed, some of the simplest possible coloring algorithms achieve this goal. Given the simplicity of those algorithms, one would expect room for improvement. Yet, to date, no algorithm is known that uses (2 - epsiv)chi colors, in spite of efforts by numerous researchers over the years. In view of the remarkable resilience of this factor of 2 against every algorithm hurled at it, we find it natural to inquire into its origin. We do so by analyzing the evolution of the set of k-colorings of a random graph, viewed as a subset of 1,...,k n, as edges are added. We prove that the factor of 2 corresponds in a precise mathematical sense to a phase transition in the geometry of this set. Roughly speaking, we prove that the set of k-colorings looks like a giant ball for k ges 2chi, but like an error-correcting code for k les (2 - epsiv)chi. We also prove that an analogous phase transition occurs both in random k-SAT and in random hypergraph 2-coloring. And that for each of these three problems, the location of the transition corresponds to the point where all known polynomial-time algorithms fail. To prove our results we develop a general technique that allows us to establish rigorously much of the celebrated 1-step replica-symmetry-breaking hypothesis of statistical physics for random CSPs. Over the past decade, physicists have developed deep but non-rigorous techniques for studying phase transitions in discrete structures. Recently, their ideas have been harnessed to obtain improved rigorous results on the phase transitions in binary problems such as random @math -SAT or @math -NAESAT (e.g., Coja-Oghlan and Panagiotou: STOC 2013). However, these rigorous arguments, typically centered around the second moment method, do not extend easily to problems where there are more than two possible values per variable. The single most intensely studied example of such a problem is random graph @math -coloring. Here we develop a novel approach to the second moment method in this problem. This new method, inspired by physics conjectures on the geometry of the set of @math -colorings, allows us to establish a substantially improved lower bound on the @math -colorability threshold. The new lower bound is within an additive @math of a simple first-moment upper bound and within @math of the physics conjecture. By comparison, the best previous lower bound left a gap of about @math , unbounded in terms of the number of colors [Achlioptas, Naor: STOC 2004]. Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish connections between the deterministic and randomized complexities in the LOCAL model. Each result has a very compelling take-away message: 1. Fast @math -coloring of trees requires random bits: Building on the recent lower bounds of , we prove that the randomized complexity of @math -coloring a tree with maximum degree @math is @math , whereas its deterministic complexity is @math for any @math . This also establishes a large separation between the deterministic complexity of @math -coloring and @math -coloring trees. 2. Randomized lower bounds imply deterministic lower bounds: We prove that any deterministic algorithm for a natural class of problems that runs in @math rounds can be transformed to run in @math rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires @math time deterministically. 3. Deterministic lower bounds imply randomized lower bounds: We prove that the randomized complexity of any natural problem on instances of size @math is at least its deterministic complexity on instances of size @math . This shows that a deterministic @math lower bound for any problem implies a randomized @math lower bound. It also illustrates that the graph shattering technique is absolutely essential to the LOCAL model. The problem of coloring a graph with the minimum number of colors is well known to be NP-hard, even restricted to k-colorable graphs for constant k ≥ 3. On the other hand, it is known that random k-colorable graphs are easy to k-color. The algorithms for coloring random k-colorable graphs require fairly high edge densities, however. In this paper we present algorithms that color randomly generated k-colorable graphs for much lower edge densities than previous approaches. In addition, to study a wider variety of graph distributions, we also present a model of graphs generated by the semi-random source of Santha and Vazirani (M. Santha and U. V. Vazirani, J. Comput. System Sci.33 (1986), 75-87) that provides a smooth transition between the worst-case and random models. In this model, the graph is generated by a "noisy adversary"-an adversary whose decisions (whether or not to insert a particular edge) have some small (random) probability of being reversed. We show that even for quite low noise rates, semi-random k-colorable graphs can be optimally colored with high probability. We study deterministic, distributed algorithms for two weak variants of the standard graph coloring problem. We consider defective colorings, i.e., colorings where nodes of a color class may induce a graph of maximum degree d for some parameter d>0. We also look at colorings where a minimum number of multi-chromatic edges is required. For an integer k>0, we call a coloring k-partially proper if every node v has at least min k,deg(v) neighbors with a different color. We show that for all d∈ 1,...,Δ , it is possible to compute a O(Δ2 d2)-coloring with defect d in time O(log*n) where Δ is the largest degree of the network graph. Similarly, for all k∈ 1,...,Δ , a k-partially proper O(k2)-coloring can be computed in O(log*n) rounds. As an application of our weak defective coloring algorithm, we obtain a faster deterministic algorithm for the standard vertex coloring problem on graphs with moderate degrees. We show that in time O(Δ+log*n), a (Δ+1)-coloring can be computed, a task for which the best previous algorithm required time O(Δ*log(Δ) + log*n). The same result holds for the problem of computing a maximal independent set. Consider an n-vertex graph G = (V, E) of maximum degree Δ, and suppose that each vertex v ∈ V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, that is, it proceeds in discrete rounds. In the distributed vertex coloring problem, the objective is to color G with Δ + 1, or slightly more than Δ + 1, colors using as few rounds of communication as possible. (The number of rounds of communication will be henceforth referred to as running time.) Efficient randomized algorithms for this problem are known for more than twenty years [ 1986; Luby 1986]. Specifically, these algorithms produce a (Δ + 1)-coloring within O(log n) time, with high probability. On the other hand, the best known deterministic algorithm that requires polylogarithmic time employs O(Δ2) colors. This algorithm was devised in a seminal FOCS’87 paper by Linial [1987]. Its running time is O(log* n). In the same article, Linial asked whether one can color with significantly less than Δ2 colors in deterministic polylogarithmic time. By now, this question of Linial became one of the most central long-standing open questions in this area. In this article, we answer this question in the affirmative, and devise a deterministic algorithm that employs Δ1+o(1) colors, and runs in polylogarithmic time. Specifically, the running time of our algorithm is O(f(Δ)log Δ log n), for an arbitrarily slow-growing function f(Δ) = ω(1). We can also produce an O(Δ1+η)-coloring in O(log Δ log n)-time, for an arbitrarily small constant η > 0, and an O(Δ)-coloring in O(Δe log n) time, for an arbitrarily small constant e > 0. Our results are, in fact, far more general than this. In particular, for a graph of arboricity a, our algorithm produces an O(a1+η)-coloring, for an arbitrarily small constant η > 0, in time O(log a log n). We consider a well-known distributed colouring game played on a simple connected graph: initially, each vertex is coloured black or white; at each round, each vertex simultaneously recolours itself by the colour of the simple (strong) majority of its neighbours. A set of vertices M is said to be a dynamo, if starting the game with only the vertices of M coloured black, the computation eventually reaches an all-black configuration.The importance of this game follows from the fact that it models the spread of faults in point-to-point systems with majority-based voting; in particular, dynamos correspond to those sets of initial failures which will lead the entire system to fail. Investigations on dynamos have been extensive but restricted to establishing tight bounds on the size (i.e., how small a dynamic monopoly might be).In this paper we start to study dynamos systematically with respect to both the size and the time (i.e., how many rounds are needed to reach all-black configuration) in various models and topologies.We derive tight tradeoffs between the size and the time for a number of regular graphs, including rings, complete d-ary trees, tori, wrapped butterflies, cube connected cycles and hypercubes. In addition, we determine optimal size bounds of irreversible dynamos for butterflies and shuffle-exchange using simple majority and for DeBruijn using strong majority rules. Finally, we make some observations concerning irreversible versus reversible monotone models and slow complete computations from minimal dynamos.