# Probability graph will have some nodes with full-mesh connectivity.

There is a graph with $$n$$ nodes. This makes for $$n \choose 2$$ edges. We know for sure $$l$$ of these $$n \choose 2$$ edges are present and the rest are absent. What is the probability that for some $$k<\min(l,n)$$ (in fact we should have $${k \choose 2} \leq l$$), there will be a sub-graph with full-mesh connectivity between those $$k$$ nodes (meaning every one of those $$k$$ nodes is connected to every other one of them). For example, when $$n=5$$, $$k=3$$ and $$l=3$$, I think there are $$5 \choose 3$$ ways of forming graphs where $$3$$ nodes form a full-mesh and $$10 \choose 3$$ ways of having three edges connected in general ($${5 \choose 2 } =10$$). So this probability should become: $$\frac{5 \choose 3}{10 \choose 3}$$. I'm particularly interested in the cases where $$n=7$$ and $$k=4$$.

My attempt: first, we choose $$k$$ nodes nodes that are going to form a full mesh. Number of ways of doing this is - $$n \choose k$$. Now, we have remaining $$u = l - {k \choose 2}$$ of the edges which are present. Overall, there are $$v = {n \choose 2}-{k \choose 2}$$ edges (present or absent) remaining. So the probability should become:

$$\frac{{v \choose u}{n \choose k}}{{n \choose 2} \choose l}$$

I feel I might be double-counting some cases. Is there anyway to verify this formula independently or even a simple pair of second eyes will help.

• Are you assuming a uniform distribution over all graphs of size $n$ with $l$ links? – d.k.o. Feb 10 at 23:53
• That is correct. – Rohit Pandey Feb 10 at 23:54
• Sorry, that was a typo. Just fixed. – Rohit Pandey Feb 11 at 0:00

As Ross notes, it's a complicated computation in general. Let's try your example with $$n=7$$, $$k=4$$, $$l=10$$. For each $$4$$-element subset $$S$$ of $$[1..n]$$ let $$A(S)$$ be the event that $$S$$ is a clique (which is the actual graph-theory term for what you call a "full mesh"). For each of the $${7 \choose 4}$$ sets of $$4$$ vertices, $$\mathbb P(A(S)) = {15 \choose 4}/{21 \choose 10} = \frac{5}{1292}$$. Given that $$S$$ is a clique, that has $$6$$ edges, leaving just $$4$$ more edges. In particular, you can't have two edge-disjoint $$4$$-cliques, or even two that share a single edge (i.e. two vertices). You could have two $$4$$-cliques sharing three vertices (say $$\{a,b,c,d\}$$ and $$\{b,c,d,e\}$$). Either $$a$$ and $$e$$ are also joined, so this is a $$5$$-clique (which has not just two but $$5$$ $$4$$-cliques), or they are not. The first case accounts for all $$10$$ edges, while in the second case there is one other edge which could be any of $$11$$ possibilities. Thus the probability of $$5$$ $$4$$-cliques is $${7 \choose 5}/{21 \choose 10} = 1/16796$$. The probability of $$2$$ $$4$$-cliques is $${7 \choose 3}{4 \choose 2}\cdot 11/{21 \choose 10} = 55/8398$$. The expected number of $$4$$-cliques is $${7 \choose 4} {15 \choose 4}/{21 \choose 10} = 175/1292$$, so the probability of $$1$$ $$4$$-clique must be $$\frac{175}{1292} - 2 \cdot \frac{55}{8398} - 5 \cdot \frac{1}{16796} = \frac{1025}{8398}$$

• Thanks, trying to follow this. Where did the 15 in $15 \choose 4$ come from? – Rohit Pandey Feb 11 at 0:49
• Given a set of $4$ vertices, to select a configuration which makes this a $4$-clique you take all $6$ edges joining these $4$ vertices plus $4$ of the $21 - 6 = 15$ other possible edges. – Robert Israel Feb 11 at 0:56
• Do you think it might be possible to write code for this where I can pass in $n$, $k$ and $l$, or is manual inspection of each case (value of $l$) the only option? Also, you say "probability of 1 4-clique". You really mean any one 4-clique, correct? Or exactly one? – Rohit Pandey Feb 11 at 1:30
• I mean exactly $1$. – Robert Israel Feb 11 at 3:39
• "At least one" in the case at hand is $1$, $2$ or $5$, so you just add those probabilities. – Robert Israel Feb 11 at 5:15

Your approach is a good one but you double count cases where there are two different sets of $$k$$ vertices with a full mesh. I think it will be a difficult inclusion/exclusion calculation because you might just have a full mesh on $$k+1$$ vertices, you might have a full mesh on $$k+1$$ with one or a few edges missing, or you might have two disjoint sets of $$k$$ vertices.

• Thanks, so it sounds like there is no easy closed form to this one. – Rohit Pandey Feb 11 at 0:06
• For your $n=7,k=4$ it may not be so bad. You don't have enough other vertices to make a disjoint set. You need $6$ edges for a full mesh on four. To make a second full mesh would require three edges out of four from one remaining vertex. If $l$ is not too much bigger than $6$ the chance of another full mesh will be small. – Ross Millikan Feb 11 at 0:11
• Hmm, I see.. overall I need to estimate the probability there will be a 4-mesh when each edge has reliability (probability of working) $q$. I was thinking of looping over $l$ from $6$ to $21$. So it will probably get ugly for higher values of $l$. – Rohit Pandey Feb 11 at 0:16