<p>It doesn't sound hopeful in general. </p>

<p>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}$. </p>

<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}$. </p>

<p>So something more than just the two properties you wrote down will be needed....</p>

CC BY-SA 3.0
2014-07-14T21:20:22.867Z
2014-07-15T14:41:20.043Z
2014-07-15T14:41:20.043Z
James Martin
<p>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.</p>

<p>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</p>

<ol>
<li>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$)</li>
<li>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'. </li>
</ol>

<p>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}$</p>

<p>Any references would be very helpful? </p>

CC BY-SA 3.0
2014-07-15T08:35:09.907Z
What properties are you looking at? Is there a reason to ask this question here, rather than Math.SE?
Niel de Beaudrap
CC BY-SA 3.0
2014-07-15T10:20:22.020Z
Upon inspection, I see that you already have. Please do not cross-post questions simultaneously to two fora, especially when it is not obviously on-topic for one of them (i.e. this forum in this case).
Niel de Beaudrap
CC BY-SA 3.0
2014-07-15T15:14:30.440Z
[erdos-renyi](http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model) model. there are many papers on the subj but not sure if any are directly related to the question. [re NdBs comment, apparently nothing is "obviously on topic" here based on routine total downvotes...]
vzn
CC BY-SA 3.0
2014-07-15T21:21:52.267Z
@vzn: There are many papers in theoretical computer science about arithmetic as well, but this does not make arithmetic in itself a topic in theoretical computer science. There's no question of computability, or the complexity of computation, or related elements in this question; hence it is off-topic. I'm not sure why you find that so controversial.
Niel de Beaudrap
CC BY-SA 3.0
2014-07-15T21:46:51.843Z
erdos-renyi graphs are a large area of study in TCS & lie at the heart of some rare hardness proofs. let votes (incl for closing) speak for themselves on relevance. re your comment on skimming thought you said "obviously not on topic". anyway seems generally bogus to me (although admittedly widespread) for anyone to refer to anything as "obviously not on topic" on virtually any stackexchange esp borderline cases given that all se's (esp research sites) have substantial negative/close vote activity, indicating that a large number of users do not find what is on topic at all "obvious"....
vzn
CC BY-SA 3.0
2014-07-16T04:16:45.743Z
@vzn: I think that part of your frustration might be stemming from the fact that you are switching the order of my adjectives. "Not obviously" $\ne$ "obviously not". In any case, if you find that *this particular* problem relates clearly to "rare hardness proofs" for problems in theoretical computer science, you are welcome to point out how this comes about.
Niel de Beaudrap
CC BY-SA 3.0
2014-07-16T05:29:10.030Z
"frustation", not. more like longterm annoyance that it seems like its official se policy that strictly no "benefit of doubt" is ever given to questioners on borderline questions & that sometimes this is in conflict with basic courtesy. only two more votes & this question is killed! any more _motivated volunteers_ out there? heck maybe even will join the _elite_ club & vote to kill it myself just out of pure _random_ amusement and your _characteristically highly persuasive_ argument :) if you cant beat em join em right?
vzn
<graph-theory><pr.probability><randomness><randomized-algorithms>
Proving properties of Random Graphs
NAg
# Proving properties of Random Graphs

(Asked by: username_0 on 2014-06-27)

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?

**Tags:** graph-theory, pr.probability, randomness, randomized-algorithms
> **Comments:**
> **username_1**: What properties are you looking at? Is there a reason to ask this question here, rather than Math.SE?  
> **username_1**: Upon inspection, I see that you already have. Please do not cross-post questions simultaneously to two fora, especially when it is not obviously on-topic for one of them (i.e. this forum in this case).  
> **username_2**: [erdos-renyi](http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model) model. there are many papers on the subj but not sure if any are directly related to the question. [re NdBs comment, apparently nothing is "obviously on topic" here based on routine total downvotes...]  
> **username_1**: @vzn: There are many papers in theoretical computer science about arithmetic as well, but this does not make arithmetic in itself a topic in theoretical computer science. There's no question of computability, or the complexity of computation, or related elements in this question; hence it is off-topic. I'm not sure why you find that so controversial.  
> **username_2**: erdos-renyi graphs are a large area of study in TCS & lie at the heart of some rare hardness proofs. let votes (incl for closing) speak for themselves on relevance. re your comment on skimming thought you said "obviously not on topic". anyway seems generally bogus to me (although admittedly widespread) for anyone to refer to anything as "obviously not on topic" on virtually any stackexchange esp borderline cases given that all se's (esp research sites) have substantial negative/close vote activity, indicating that a large number of users do not find what is on topic at all "obvious"....  
> **username_1**: @vzn: I think that part of your frustration might be stemming from the fact that you are switching the order of my adjectives. "Not obviously" $\ne$ "obviously not". In any case, if you find that *this particular* problem relates clearly to "rare hardness proofs" for problems in theoretical computer science, you are welcome to point out how this comes about.  
> **username_2**: "frustation", not. more like longterm annoyance that it seems like its official se policy that strictly no "benefit of doubt" is ever given to questioners on borderline questions & that sometimes this is in conflict with basic courtesy. only two more votes & this question is killed! any more _motivated volunteers_ out there? heck maybe even will join the _elite_ club & vote to kill it myself just out of pure _random_ amusement and your _characteristically highly persuasive_ argument :) if you cant beat em join em right?  

---

## 1 answers

### Answer by username_3 on 2014-07-14. Score: 7

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....


---

