Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to find the probability of a bernoulli random graph on $n=10$ vertices with probability that an edge connects any pair of vertices is $p=\frac{1}{6}$ as $n\to \infty$.

This is what I have:

$\lim_{n\to \infty}$ P($G$ contains $K_7$) = $\lim_{n\to \infty}$ P(at least $7$ vertices are all connected to each other)

= $1 -lim_{n\to \infty}$ P(at most $6$ vertices are all connected to each other)

= $1 -lim_{n\to \infty}$ P($2$) + P($3$) + P($4$) + p($5$) + P($6$)

My expression for the probability is where I think I go wrong. Here is just one part of it:

P($6) = {n\choose 6}\cdot p^{\dfrac{6\cdot 5}{2}}$

The reasoning is that there are ${n\choose 6}$ distinct subsets of size $6$ out of $n$ possible vertices. Then there are $\dfrac{6(6-1)}{2}$ edges in $K_6$. Since each edge has probability $p$ of occurring and each occurrence is independent of the others by definition of bernoulli random graph we raise $p$ to the $\dfrac{6\cdot 5}{2}$ power. Furthermore each distinct subset is independent and so we multiply this by ${n\choose 6}$

What must be wrong is the fact that the expression for P($6$) will be infinite since $p^{\dfrac{6\cdot 5}{2}}$ is a finite term.

  1. Where exactly did I go wrong?
  2. How can I improve my reasoning in combinatorics/probability?
share|improve this question

1 Answer 1

If you see probabilities coming out more than 1, chances are you are double-counting something. Consider if the graph is completely connected, i.e. $G=K_n$. Then this graph will contribute to your calculation of $P(6)$ in every subset, since it contains many copies of $K_7$, but it is only one graph, so you shouldn't overcount it.

The probability that a Bernoulli graph on $n$ vertices has $K_7$ as a subgraph is 1 minus the probability that every subset of 7 vertices is not completely connected. There are ${n\choose7}$ subsets of seven vertices in $G$, and there are ${7\choose2}=21$ edges in $K_7$, so the probability that all edges are connected is $p^{21}$, and the probability that not all edges are connected in a given subset is $1-p^{21}$. Thus the probability that this is true for every subset is $(1-p^{21})^{n\choose7}$, and the limit of one minus this as $n\to\infty$ is $1$. But the different subsets are not disjoint, so the probabilities are correlated, which changes this calculation a bit. Anyone know how to calculate that part of it? (I don't think it will change the result, though.)

Edit: A more rigorous approach to this estimate is to construct the graph $G'$ from $G$ by partitioning the vertices into groups of 7 and removing all edges connecting different groups, so that $G'$ is a collection of disconnected subsets of $K_7$. (The last group of size less than 7 can bee ignored, i.e. completely disconnected.) Clearly $G'\subseteq G$, so if $G'$ contains $K_7$, then so does $G$ (but not vice-versa). Now we can cleanly calculate $P(K_7\subseteq G')=1-(1-p^{21})^{\lfloor n/7\rfloor}\to1$ as $n\to\infty$, but $P(K_7\subseteq G')\leq P(K_7\subseteq G)\leq1$, so $P(K_7\subseteq G)=1$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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