Proving properties of Random Graphs

Question

I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas.

Consider the random graph model $G_{n,p}$ where its a random graph on n vertices and each edge is selected with probability $p$. I want to prove that a certain property $P$ is satisfied by graphs in this model with high probability ($\rightarrow 1$ as $n \rightarrow \infty$). I know/can prove the following two facts

1. Conditioned on the event that the graph obtained from the sample is regular, the probability of the property being satisfied is very high (something like $1 - 1/n^c$)
2. Given any graph G and any other graph G' that can be obtained by removing edges from G. If G satisfies the property then so does G'.

Can the above two statements be enough to make a general statement about the probability of the satisfaction of the property in $G_{n,p}$

Any references would be very helpful?

Answer 1

It doesn't sound hopeful in general.

For example, let $P$ be the statement "all vertices have degree 0 or 1". Let $p=1/n$ and $n$ even. Then conditioned on the event of being regular, with high probability the graph is 0-regular or 1-regular, so $P$ holds with high probability. Also $P$ is preserved by removing edges. But it is certainly not the case that $P$ holds with high probability under $G_{n,p}$.

Even in other situations (say, fixed $p$ as $n\to\infty$), I would expect that there are events $P$ of the form "maximum degree less than $d$" which satisfy your 1. and 2. but don't hold w.h.p. for $G_{n,p}$.

So something more than just the two properties you wrote down will be needed....