- March 5, 2012: the percolation result simplifies and more is true:
given an arbitrary graph G and site percolation with parameter p, the expectation of the number
of times that a graph H is embedded is f(p) = pord(H) vH, where
vH is the number of times that the graph H is embedded in G originally.
Similarly for bond percolation, the expectation is g(p) psize(H) vH.
So, the decorrelation argument in the proof of Proposition 1 is not needed.
The argument is very simple, well known and was used also
here:
let K be a specific embedding of H in G. Now look at the
event AK that K is present in the site (rsp bond) Erdoes-Renyi probability space. It is
pord(H) (rsp. psize(H)). Now the expectation for site percolation
E[ vH ] = sumK pord(K) = vH pord(H).
(rsp. sumK psize(K) = vH psize(H)).
It does not matter that the events AK for different embeddings K are correlated,
when different embeddings overlap.