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?

  • $\begingroup$ What properties are you looking at? Is there a reason to ask this question here, rather than Math.SE? $\endgroup$ – Niel de Beaudrap Jul 15 '14 at 8:35
  • 1
    $\begingroup$ 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). $\endgroup$ – Niel de Beaudrap Jul 15 '14 at 10:20
  • $\begingroup$ erdos-renyi 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...] $\endgroup$ – vzn Jul 15 '14 at 15:14
  • 1
    $\begingroup$ @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. $\endgroup$ – Niel de Beaudrap Jul 15 '14 at 21:21
  • $\begingroup$ 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".... $\endgroup$ – vzn Jul 15 '14 at 21:46

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.