2
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Thanks, trying to follow this. Where did the 15 in $15 \choose 4$ come from? $\endgroup$ – Rohit Pandey Feb 11 at 0:49
  • $\begingroup$ 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. $\endgroup$ – Robert Israel Feb 11 at 0:56
  • $\begingroup$ 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? $\endgroup$ – Rohit Pandey Feb 11 at 1:30
  • $\begingroup$ I mean exactly $1$. $\endgroup$ – Robert Israel Feb 11 at 3:39
  • 1
    $\begingroup$ "At least one" in the case at hand is $1$, $2$ or $5$, so you just add those probabilities. $\endgroup$ – Robert Israel Feb 11 at 5:15
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, so it sounds like there is no easy closed form to this one. $\endgroup$ – Rohit Pandey Feb 11 at 0:06
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Feb 11 at 0:11
  • $\begingroup$ 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$. $\endgroup$ – Rohit Pandey Feb 11 at 0:16

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.