Threshold phenomena in random graph colouring and satisfiability
Allan Borodin, Michael S. O. Molloy, Demetrios Achlioptas · 1999
We study threshold phenomena pertaining to the colourability of random graphs and the satisfiability of random formulas. Consider a random graph G(n, p) on n vertices formed by including each of the n2 possible edges independently of all others with probability p. For a fixed integer k, let fk( n, d) = Pr[G(n, d/n) is k-colourable]. Erdos asked the following fundamental question: for k ≥ 3, is there a constant c k such that for any e>0, limn→∞ fkn,ck-e =1,and lim n→∞fkn,c k+e=0 1 We prove that for every k ≥ 3, there exists a function tk(n) such that (1) holds upon replacing ck by tk(n), thus establishing that indeed k-colourability has a sharp threshold. Let dk=supdmlimn→ ∞fkn,d =1. Note that if ck exists then, by definition, ck=dk. For the basic and most studied case k = 3 we prove 3.84<d3<5.05. These are the best known bounds for d 3. Our lower bound improves upon d3≥3.35l which corresponds to the critical probability for the emergence of a subgraph with minimum degree 3 in G(n, p). Thus, we also settle completely a long-standing question of Bollobas, establishing a (large) gap between the appearance of a subgraph with minimum degree 3 and of a 4-chromatic subgraph. The proof is algorithmic and we outline an asymptotically tight analysis of the underlying algorithm. Our upper bound improves upon d3 < 5.15 of Molloy and Reed, illustrating how an idea of Kirousis et al., developed for random k-SAT, can be viewed as a general refinement of the “first moment” method. Finally, we give the first mathematically rigorous results for a new model of random satisfiability which interpolates between random 2-SAT and random 3-SAT. The techniques are very similar with those developed for random graph colouring. Among other things we prove the following, rather surprising, proposition. It is well-known that a random formula on n variables with rn 2-clauses is almost surely (a.s.) satisfiable if r 1. We prove that for any r < 1 and any λ < 2/3, a random formula with rn 2-clauses and λ n 3-clauses is a.s. satisfiable.