Threshold phenomena in random structures (Q1095948): Difference between revisions

The physical theory of phase transition explains sudden changes of phase in materials that undergo gradual changes of some parameter like temperature. There are analogs of phase transition in the theory of random graphs, initiated by Erdős and Rényi. This paper gives a nontechnical but precise account, without proofs, of some of the beautiful discoveries of Erdős and Rényi about threshold phenomena in graphs, describes an application of their methods to interval graphs, and gives some examples of threshold phenomena under other definitions of randomness and in combinatorial structues other than graphs. The paper offers some speculations on possible applications of random combinatorial structures to telecommunications, neurobiology, and the origin of life.