Premium
Hunting for sharp thresholds
Author(s) -
Friedgut Ehud
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20042
Subject(s) - hypergraph , probabilistic logic , phenomenon , mathematics , random graph , statistical physics , swift , state (computer science) , struct , discrete mathematics , computer science , algorithm , statistics , physics , quantum mechanics , graph , programming language
A basic phenomenon in random structures such as random graphs is the threshold phenomenon, where a system undergoes a swift qualitative change as result of a small change in a parameter guiding its probabilistic structure. In an earlier paper [J Amer Math Soc 12 (1999), 1017–1054] a general criterion was presented for structures to undergo such a phase transition. In this paper we give a survey of the state of the art in applying the aforementioned criterion, exemplify the techniques by proving the existence of a sharp threshold for hypergraph colorability, and present some related open problems. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 26, 2005