Abstract | ||
---|---|---|
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, 2005Research supported in part by the Israel Science Foundation, Grant No. 0329745. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1002/rsa.v26:1/2 | Random Struct. Algorithms |
Keywords | Field | DocType |
random graphs,phase transition | Discrete mathematics,Combinatorics,Random graph,Swift,Phase transition,Hypergraph,struct,Probabilistic logic,Phenomenon,Mathematics | Journal |
Volume | Issue | ISSN |
26 | 1-2 | 1042-9832 |
Citations | PageRank | References |
29 | 1.76 | 0 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ehud Friedgut | 1 | 440 | 38.93 |