The graph expectation threshold of a finite simple graph 
in the random graph 
is the smallest probability 
for which every subgraph of 
has expectation value
at least 
for its number of copies (Kahn and Kalai 2007). Here 
has at least one edge and at
most 
vertices, with 
, and each possible edge
of 
is present independently with probability 
. Writing 
for the number of subgraphs
of 
isomorphic to 
, the definition is
![p_E(n,H)=inf{p in [0,1]:E[N(G(n,p),F)]>=1/2 for every F subset= H}.](/images/equations/GraphExpectationThreshold/NumberedEquation1.svg) |
Copies are ordinary subgraphs, so additional edges between the chosen vertices are allowed. The use
of expected count 1 instead of 
changes 
by a factor of at most 2.
The containment threshold is
![p_c(n,H)=inf{p in [0,1]:Pr(N(G(n,p),H)>0)>=1/2}.](/images/equations/GraphExpectationThreshold/NumberedEquation2.svg) |
One has 
,
since containing 
also supplies a copy of each subgraph 
.
For the single-edge graph 
,
put 
.
Then 
and 
.
The second Kahn-Kalai conjecture asks whether 
is at most a universal constant times 
, even when 
varies with 
(Kahn and Kalai 2007).
This graph expectation threshold differs from the integral expectation threshold 
, where 
is the increasing graph property
of containing a copy of 
. In particular, 
, so an upper
bound in terms of 
alone does not establish the second Kahn-Kalai conjecture.
