Random graphs: $p \mapsto \mathbb{P}[G(n,p) \text{ has property } P]$ is a decreasing function for hereditary properties 
Definition: A graph $G$ has a herditary property $P$ if for every graph $G$ that
has property $P$, every spanning subgraph of $G$ (i.e. every subgraph on the same
vertex set as $G)$ also has property $P$.


Show that if $P$ is a hereditary property, then $$f_P(p): [0,1] \ni p \mapsto \mathbb{P}[G(n,p) \text{ has property } P] \in [0,1]$$
is a decreasing function.
Remark : Here $G(n,p)$ denotes the randomised graph a.k.a. Erdos-Renyi graph.

I mean we probably need to start with $p_1 < p_2$ and we need to show that $$\mathbb{P}[G(n,p_1) \text{ has property } P] > \mathbb{P}[G(n,p_2) \text{ has property } P].$$
To do so I think it might be a good idea to find a $p_0 \in (p_1,p_2)$ such that
$$\mathbb{P}[G(n,p_2) \text{ has property } P] + \mathbb{P}[G(n,p_0) \text{ has property } P] = \mathbb{P}[G(n,p_1) \text{ has property } P].$$
However, I do not see how to start with a formal argument. Could you please give me a hint?
Edit: I think I got the answer: Choose $p_0$ such that $1-p_2 = (1-p_1)(1-p_0)$ and note that $p_0 > 0$. This entails that for every edge $e$
$$e \notin G(n,p_2) \Leftrightarrow e \notin G(n,p_1) \cup G(n,p_0).$$
Thus $$\mathbb{P}[G(n,p_1) \text{ has property } P]  = \mathbb{P}[G(n,p_2) \text{ has property } P] + \mathbb{P}[G(n,p_0) \text{ has property } P]$$
and since $\mathbb{P}[G(n,p_0) \text{ has property } P] > 0$ we are done.
 A: The approach is the right one, but the claim that $$\mathbb{P}[G(n,p_1) \text{ has } P]  = \mathbb{P}[G(n,p_2) \text{ has } P] + \mathbb{P}[G(n,p_0) \text{ has } P]$$ is not quite correct.
What is true is that:

*

*$G(n,p_2)$ has property $P$ with the same probability as the union $G(n,p_1) \cup G(n,p_0)$, assuming $G(n,p_1)$ and $G(n,p_0)$ are chosen independently.

*If $G(n,p_1) \cup G(n,p_0)$ has property $P$, then in particular both $G(n,p_1)$ and $G(n,p_0)$ have property $P$.

*The probability that $G(n,p_1)$ and $G(n,p_0)$ both have property $P$ is the product $$\mathbb P[G(n,p_1) \text{ has }P] \cdot \mathbb P[G(n,p_0) \text{ has }P].$$
Therefore
\begin{align}
\mathbb P[G(n,p_2) \text{ has }P] &= \mathbb P[G(n,p_1) \cup G(n,p_0) \text{ has }P] \\
  &\le \mathbb P[G(n,p_1) \text{ has }P] \cdot \mathbb P[G(n,p_0) \text{ has }P].
\end{align}
We get an inequality because we're passing from a statement "$G(n,p_1) \cup G(n,p_0)$ has property $P$" to a consequence of that statement "both $G(n,p_1)$ and $G(n,p_0)$ have property $P$", but the consequence could also happen if the original statement does not.
Finally, $\mathbb P[G(n,p_1) \text{ has }P] \cdot \mathbb P[G(n,p_0) \text{ has }P] \le \mathbb P[G(n,p_1) \text{ has }P]$ because $\mathbb P[G(n,p_0) \text{ has }P] \le 1$, giving us the final conclusion we wanted.
