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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom