Current Developments in Mathematics

Volume 2018

Phase transitions of random constraint satisfaction problems

Pages: 213 – 264

DOI: https://dx.doi.org/10.4310/CDM.2018.v2018.n1.a5

Author

Allan Sly (Department of Mathematics, Princeton University, Princeton, New Jersey, U.S.A.)

Abstract

Random constraint satisfaction problems, such as the random $K\textrm{-SAT}$ model and colourings of random graphs naturally emerge in the study of combinatorics and theoretical computer science. Ideas from statistical physics describe a series of phase transitions these models undergo as the density of constraints increases. Throughout we will focus on the example of the maximal independent set of a random regular graph as a simple example of this phenomena and then conclude by describing the additional technical challenges needed to establish the Satisfiability Conjecture for large $K$.

Full Text (PDF format)

Published 17 December 2019