Phase transitions in discrete structures

  • Amin Coja-Oghlan

    J.W. Goethe-Universität, Frankfurt a.M., Germany
Phase transitions in discrete structures cover
Download Chapter PDF

A subscription is required to access this book chapter.


Many important parameters of random discrete structures such as random graphs, formulas and codes undergo phase transitions. While some phase transitions such as the emergence of a giant component in the Erd˝os-Rényi random graph are very well understood, other, less understood ones resemble phase transitions in statistical physics models of disordered systems. This paper gives an impression of what we know about this latter class with the particular example of the random graph colouring problem.