Thresholds for colourability and satisfiability in random graphs and Boolean formulae (Q2741177)

A comparison is made between a colourability problem for random graphs and a satisfiability problem for random Boolean formulae. The graph problem concerns the \(k\)-colourability of a random graph of order \(n\) and size \(cn\), and the Boolean problem concerns the satisfiability of a random Boolean formula in \(n\) variables with \(dn\) clauses of a common size \(k\). For each \(k\), suprema of \(c\) and \(d\) and the existence of limits are investigated as \(n\) tends to infinity. A survey is given of results for the well-understood case \(k=2\) and for less penetrated cases \(k>2\). In particular, techniques are discussed which have recently been developed to prove upper and lower bounds on \(c\) and \(d\) for \(k=3\).NEWLINENEWLINEFor the entire collection see [Zbl 0964.00035].