Abstract
We consider relations between thresholds for monotone set properties and simple lower bounds for such thresholds. A motivating example (Conjecture 2): Given an n-vertex graph H, write PE for the least p such that, for each subgraph H′ of H, the expected number of copies of H′ in G = G(n,p) is at least 1, and pc for that p for which the probability that G contains (a copy of) H is 1/2. Then (conjecture) pc = O(PE log n). Possible connections with discrete isoperimetry are also discussed.
Original language | English (US) |
---|---|
Pages (from-to) | 495-502 |
Number of pages | 8 |
Journal | Combinatorics Probability and Computing |
Volume | 16 |
Issue number | 3 |
DOIs | |
State | Published - May 2007 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics