Threshold phenomena in random structures
type: Item
instance of: scholarly article
title: Threshold phenomena in random structures
zbMATH Open document ID: 0633.05065
DOI: 10.1016/0166-218X(88)90008-X
author: Joel E. Cohen
published in: Discrete Applied Mathematics
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 94A05
Mathematics Subject Classification ID: 92B05
zbMATH DE Number: 4029635
zbMATH Keywords: random graphs
zbMATH Keywords: threshold phenomena
zbMATH Keywords: interval graphs
zbMATH Keywords: random combinatorial structures
MaRDI profile type: Publication
cites work: Cliques in random graphs
cites work: Q4187859
cites work: The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph
cites work: Q4192104
cites work: Q3286850
cites work: Q3926624
cites work: Recurrence properties of Processes with stationary independent increments
cites work: The Life and Works of Boris Vladimirovich Gnedenko: A Survey
cites work: Q4112673
cites work: A variational problem for random Young tableaux
cites work: An introduction to a mathematical theory of chemical reaction networks. I, II
cites work: Combinatorial Classification of Chemical Mechanisms
cites work: Q4192066
Wikidata QID: Q127330054
description: scientific article; zbMATH DE number 4029635