We determine the exact value of the freezing threshold, r f k , for k -colourings of a random graph when k ≥ 14. We prove that for random graphs with density above r f k , almost every colouring is such that a linear number of vertices are frozen, meaning that their colour cannot be changed by a sequence of alterations whereby we change the colours of o ( n ) vertices at a time, always obtaining another proper colouring. When the density is below r f k , then almost every colouring is such that every vertex can be changed by a sequence of alterations where we change O (log n ) vertices at a time. Frozen vertices are a key part of the clustering phenomena discovered using methods from statistical physics. The value of the freezing threshold was previously determined by the nonrigorous cavity method.

We determine the exact freezing threshold, rf, for a family of models of random boolean constraint satisfaction problems, including NAE-SAT and hypergraph 2-colouring, when the constraint size is sufficiently large. If the constraint-density of a random CSP, F, in our family is greater than rf then for almost every solution of F, a linear number of variables are frozen, meaning that their colours cannot be changed by a sequence of alterations in which we change o(n) variables at a time, always switching to another solution. If the constraint-density is less than rf, then almost every solution has o(n) frozen variables. Freezing is a key part of the clustering phenomenon that is hypothesized by non-rigorous techniques from statistical physics. The understanding of clustering has led to the development of advanced heuristics such as Survey Propogation. It has been suggested that the freezing threshold is a precise algorithmic barrier: that for densities below rf the random CSPs can be solved using very simple algorithms, while for densities above rf one requires more sophisticated techniques in order to deal with frozen clusters.

We consider random instances of constraint satisfaction problems (CSPs) where each variable has domain size $O(1)$, each constraint is on $O(1)$ variables, and the constraints are chosen from a specified distribution. The number of constraints is $cn$, where $c$ is a constant. We prove that for every possible distribution, either the resolution complexity is almost surely polylogarithmic for sufficiently large $c$, or it is almost surely exponential for every $c>0$. We characterize the distributions of each type. To do so, we introduce a closure operation on constraint sets which yields the set of all constraints that, in some sense, appear implicitly in the random CSP.

We rigorously determine the exact freezing threshold, rkf, for k-colourings of a random graph. We prove that for random graphs with density above rkf, almost every colouring is such that a linear number of variables are frozen, meaning that their colours cannot be changed by a sequence of alterations whereby we change the colours of o(n) vertices at a time, always obtaining another proper colouring. When the density is below rkf, then almost every colouring has at most o(n) frozen variables. This confirms hypotheses made using the non-rigorous cavity method. It has been hypothesized that the freezing threshold is the cause of the "algorithmic barrier", the long observed phenomenon that when the edge-density of a random graph exceeds hf k ln k(1+ok(1)), no algorithms are known to find k-colourings, despite the fact that this density is only half the k-colourability threshold.

We determine the exact threshold of satisfiability for random instances of a particular NP-complete constraint satisfaction problem (CSP). This is the first random CSP model for which we have determined a precise linear satisfiability threshold, and for which random instances with density near that threshold appear to be computationally difficult. More formally, it is the first random CSP model for which the satisfiability threshold is known and which shares the following characteristics with random $k$-SAT for $k \geq 3$: The problem is NP-complete, the satisfiability threshold occurs when there is a linear number of clauses, and a uniformly random instance with a linear number of clauses asymptotically almost surely has exponential resolution complexity.

We study the Glauber dynamics Markov chain for [Formula: see text]-colorings of trees with maximum degree [Formula: see text]. For [Formula: see text], we show that the mixing time on the complete tree is [Formula: see text]. For [Formula: see text] we extend our analysis to show that the mixing time on any tree is at most [Formula: see text]. Our proof uses a weighted canonical paths analysis and introduces a variation of the block dynamics that exploits the differing relaxation times of blocks.

Given a discrete random walk on a finite graph $G$, the vacant set and vacant net are, respectively, the sets of vertices and edges which remain unvisited by the walk at a given step $t$. Let $\Gamma(t)$ be the subgraph of $G$ induced by the vacant set of the walk at step $t$. Similarly, let $\widehat \Gamma(t)$ be the subgraph of $G$ induced by the edges of the vacant net. For random $r$-regular graphs $G_r$, it was previously established that for a simple random walk the graph $\Gamma(t)$ of the vacant set undergoes a phase transition in the sense of the phase transition on Erdös--Renyi graphs $G_{n,p}$. Thus, for $r \ge 3$ there is an explicit value $t^*=t^*(r)$ of the walk such that for $t\leq (1-\epsilon)t^*$, $\Gamma(t)$ has a unique giant component, plus components of size $O(\log n)$, whereas for $t\geq (1+\epsilon)t^*$ all the components of $\Gamma(t)$ are of size $O(\log n)$. In this paper we establish the threshold value $\widehat t$ for a phase transition in the graph $\widehat \Gamma(t)$ of the vacant net of a simple random walk on a random $r$-regular graph. We obtain the corresponding threshold results for the vacant set and vacant net of two modified random walks. These are a nonbacktracking random walk and, for $r$ even, a random walk which chooses unvisited edges whenever available. This allows a direct comparison of thresholds between simple and modified walks on random $r$-regular graphs. The main findings are the following: As $r$ increases, the threshold for the vacant set converges to $n \log r$ in all three walks. For the vacant net, the threshold converges to $rn/2 \; \log n$ for both the simple random walk and the nonbacktracking random walk. When $r\ge 4$ is even, the threshold for the vacant net of the unvisited edge process converges to $rn/2$, which is also the vertex cover time of the process.

We prove that every graph with maximum degree Δ can be properly (Δ + 1)-coloured so that no colour appears more than O(logΔ/log logΔ) times in the neighbourhood of any vertex. This is best possible up to the constant factor in the O(–) term. We also provide an efficient algorithm to produce such a colouring.

We consider random instances of constraint satisfaction problems where each variable has domain size O(1), each constraint is on O(1) variables and the constraints are chosen from a specified distribution. The number of constraints is cn where c is a constant. We prove that for every possible distribution, either the resolution complexity is almost surely polylogarithmic for sufficiently large c, or it is almost surely exponential for every c > 0. We characterize the distributions of each type. To do so, we introduce a closure operation on a set of constraints which yields the set of all constraints that, in some sense, appear implicitly in the random CSP.

We consider random instances of constraint satisfaction problems where each variable has domain size d and each constraint contains t restrictions on k variables. For each $(d,k,t)$ we determine whether the resolution complexity is a.s. constant, polynomial, or exponential in the number of variables. For a particular range of $(d,k,t)$, we determine a sharp threshold for resolution complexity where the resolution complexity drops from a.s. exponential to a.s. polynomial when the clause density passes a specific value.

We determine the exact threshold of satisfiability for random instances of a particular NP-hard constraint satisfaction problem. The problem appears to share many of the threshold characteristics of random k-SAT for k /spl ges/ 3; for example, we prove the problem almost surely has high resolution complexity. We also prove the analogue of the (2+p)-SAT conjecture for a class of problems that includes this problem and XOR-SAT.

We prove that the Glauber dynamics on the C-colorings of a graph G on n vertices with girth g and maximum degree $\Delta$ mixes rapidly if (i) $C=q\Delta$ and $q>q^*$, where $q^*=1.4890\ldots$ is the root of $(1-{\rm e}^{-1/q})^2+q{\rm e}^{-1/q}=1$; and (ii) $\Delta\geq D\log n$ and $g\geq D\log\Delta$ for some constant D=D(q). This improves the bound of roughly $1.763\Delta$ obtained by Dyer and Frieze [ Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 2001] for the same class of graphs. Our bound on this class of graphs is lower than the bound of $11\Delta/6\approx1.833\Delta$ obtained by Vigoda [J. Math. Phys., 41 (2000), pp. 1555--1569] for general graphs.

We consider random instances of constraint satisfaction problems where each variable has domain size d, and each constraint contains t restrictions on k variables. For each (d, k, t) we determine whether the resolution complexity is a.s. constant, polynomial or exponential in the number of variables. For a particular range of (d, k, t) we determine a sharp threshold for resolution complexity where the resolution complexity drops from a.s. exponential to a.s. polynomial when the clause density passes a specific value.

We introduce a class of models for random constraint satisfaction problems. This class includes and generalizes many previously studied models. We characterize those models from our class which are asymptotically interesting in the sense that the limiting probability of satisfiability changes significantly as the number of constraints increases. We also discuss models which exhibit a sharp threshold for satisfiability in the sense that the limiting probability jumps from 0 to 1 suddenly as the number of constraints increases.

(MATH) We prove that the Glauber dynamics on the C-colourings of a graph G on n vertices with girth g and maximum degree $\D$ mixes rapidly if (i) $C=q\D$ and $q>q^*$ where $q^*=1.4890... $ is the root of $(1-\rme^{-1/q})^2+q\rme^{-1/q}=1$; and (ii) $\D\geq D\log n$ and $g\geq D\log\D$ for some constant $D=D(q)$. This improves the corresponding result with $q\geq1.763\D$ obtained by Dyer and Frieze [FOCS01] for the same class of graphs.

We introduce a class of models for random Constraint Satisfaction Problems. This class includes and generalizes many previously studied models. We characterize those models from our class which exhibit thresholds for satisfiability in the sense that the limiting probability of satisfiability changes significantly as the number of constraints increases. We also discuss models which exhibit sharp thresholds in the sense that the limiting probability jumps from 0 to 1 suddenly.

We give the first example of a sharp threshold in proof complexity. More precisely, we show that for any sufficiently small � and � � �, random formulas consisting of 2-clauses and 3-clauses, which are known to be unsatisfiable almost certainly, almost certainly require resolution and Davis-Putnam proofs of unsatisfiability of exponential size, whereas it is easily seen that random formulas with 2-clauses (and 3-clauses) have linear size proofs of unsatisfiability almost certainly. A consequence of our result also yields the first proof that typical random 3-CNF formulas at ratios below the generally accepted range of the satisfiability threshold (and thus expected to be satisfiable almost certainly) cause natural Davis-Putnam algorithms to take exponential time to find satisfying assignments.

We consider for graphs of maximum degree Δ, the problem of determining whether χG) > Δ-k for various values of k. We obtain sharp theorems characterizing when the barrier to Δ-k colourability must be a local condition, i.e. a small subgraph, and when it can be global. We also show that for large fixed Δ, this problem is either NP-complete or can be solved in linear time, and we determine precisely which values of k correspond to each case prove that Hitting Set with sets of size B is hard to approximate to within a factor $B^{1/19}$. The problem can be approximated to within a factor B [19], and it is the Vertex Cover problem for B=2. The relationship between hardness of approximation and set size seems to have not been explored before.

Copyright © 1998 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM, Inc., fax +1 (212) 869-0481, or [email protected]. © ACM, 1998. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing (1998). http://doi.acm.org/10.1145/276698.276866

We provide a polynomial time algorithm which finds a total coloring of any graph with maximum degree $\D$, $\D$ sufficiently large, using at most $\D+8\log^8\D$ colors. This improves the best previous upper bound on the total chromatic number of $\D+18\D^{1/3}\log(3\D)$.

We introduce a natural k-coloring algorithm and analyze its performance on random graphs with constant expected degree c (G/sub n,p=c/n/). For k=3 our results imply that almost all graphs with n vertices and 1.923 n edges are 3-colorable. This improves the lower bound on the threshold for random 3-colorability significantly and settles the last case of a long-standing open question of Bollobas. We also provide a tight asymptotic analysis of the algorithm. We show that for all k/spl ges/3, if c/spl les/k In k-3/2k then the algorithm almost surely succeeds, while for any /spl epsiv/>0, and k sufficiently large, if c/spl ges/(1+/spl epsiv/)k In k then the algorithm almost surely fails. The analysis is based on the use of differential equations to approximate the mean path of certain Markov chains.