Thresholds and Expectation Thresholds

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 p E 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.