Thresholds and expectation thresholds

Jeff Kahn, Gil Kalai

Research output: Contribution to journalArticle

24 Scopus citations

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 languageEnglish (US)
Pages (from-to)495-502
Number of pages8
JournalCombinatorics Probability and Computing
Volume16
Issue number3
DOIs
StatePublished - 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