Phase transitions in discrete structures

Abstract

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.