Current Developments in Mathematics

Volume 2018

Phase transitions of random constraint satisfaction problems

Pages: 213 – 264



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


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

Published 17 December 2019