### 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 p_{c} for that p for which the probability that G contains (a copy of) H is 1/2. Then (conjecture) p_{c} = O(P_{E} 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 1 2007 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Thresholds and expectation thresholds'. Together they form a unique fingerprint.

## Cite this

Kahn, J., & Kalai, G. (2007). Thresholds and expectation thresholds.

*Combinatorics Probability and Computing*,*16*(3), 495-502. https://doi.org/10.1017/S0963548307008474