Random graphs: $p \mapsto \mathbb{P}[G(n,p) \text{ has property } P]$ is a decreasing function for hereditary properties

Question

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.

Answer 1

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:

1. $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.
2. 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$.
3. 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.