Contents Online

# 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

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

Published 17 December 2019