Thresholds for colourability and satisfiability in random graphs and Boolean formulae

MaRDI QIDQ2741177zbMATH OpenFDO

Authors Michael Molloy

Publication date 29 March 2002

zbMATH Keywords

Boolean formulaechromatic numberscolourabilityrandom \(k\)-SATrandom graphssatisfiability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25)

Review text

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].

Recommendations

• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The resolution complexity of random graph \(k\)-colorability
• scientific article; zbMATH DE number 1380613
• scientific article; zbMATH DE number 1256700

Cited in

(3)

• Research problems from the 18th British Combinatorial Conference
• The resolution complexity of random graph \(k\)-colorability
• On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs

This page was built for publication: Thresholds for colourability and satisfiability in random graphs and Boolean formulae

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2741177)