  A local order parameter which is important in the analysis of phase
transitions in frustrated combinatorial problems is the probability that a node
is frozen in a particular state. There is a percolative transition when an
infinite connected cluster of these frozen nodes emerges. In this contribution,
we develop theories based on this percolation process and discuss its relation
to conventional connectivity percolation and its generalisation to
k-connectivity percolation. The emergence of frozen order may also be
considered to be a form of constraint percolation (CP) which enables us to draw
analogies with rigidity percolation and its associated matching problems. We
show that very simple CP processes on Bethe lattices lead to the replica
symmetric equations for KSAT, coloring and the Viana-Bray model.
