2

After Theorem 2.1 on page 36 (second edition) he states

Note that the argument above shows that if $Q$ is a nontrivial monotone increasing property then

$$P_{p_2}(Q) \ge P_{p_1}(Q) + \{1 - P_{p_1}(Q)\}P_p(Q) \ge P_{p_1}(Q) + P_{p_1}(E^n)P_p(K^n) > P_{p_1}(Q).$$

What are $E^n$ and $K^n$? In the section on notation $E$ is usually some sort of expectation, and the complete graph on $n$ vertices is $K_n$, not $K^n$. Can someone shed some light on this?

Andrew Uzzell
  • 1,677
Fequish
  • 709

1 Answers1

1

Bollobas uses superscripts, rather than subscripts, to denote the number of vertices of a graph. So, $K^n$ is indeed the complete graph on $n$ vertices and $E^n$ is its complement, the empty graph on $n$ vertices.

Also, $P_p(H)$ denotes the probability that a graph with distribution $\mathcal{G}(n,p)$ is isomorphic to $H$ (see the top of p. 35). Since $Q$ is assumed to be a nontrivial monotone increasing property, then $K^n$ must have $Q$ and $E^n$ must not have $Q$. So, $1-P_{p_1}(Q) \geq P_{p_1}(E^n)$ and $P_p(Q) \geq P_p(K^n)$.

Andrew Uzzell
  • 1,677