Thresholds and Expectation Thresholds
Jeff Kahn, Gil Kalai · Combinatorics Probability Computing · 2007
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.