3
$\begingroup$

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?

1 Answers 1

3

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