5
$\begingroup$

Assume that we have a complete graph $G = \{V,E\}$, where $V$ is the vertices set and $E$ is the edges set. We randomly select $n$ unique edges from $G$ ($n \le |E|$), and these edges cover $m$ vertices.

The problem is: what is the probability distribution for $m$?

=========================================

I read a helpful post: Given a random labelled simple graph with n edges, when is it more likely to get a graph with more edges than vertices?

==========================================

Now I am trying to transform this problem to picking random element pairs from a set, and I find this post could be helpful since it asked a very similar question. https://stackoverflow.com/questions/15793172/efficiently-generating-unique-pairs-of-integers

Could anyone please help me?

$\endgroup$
  • $\begingroup$ Please see here. What have you tried? $\endgroup$ – Nobody Aug 5 '16 at 14:41
  • $\begingroup$ Let $|V|=N$. The first vertice has $N-1$ neighbours, the next $N-2$ (without the first), etc. To choose an edge is like to choose one pair (vertice,neighbour). You need to choose $n$. It seems to be sth like stars and bars $\endgroup$ – Michael Freimann Aug 5 '16 at 14:59
1
$\begingroup$

To start with some notation, let's assume $G=(V,E)$ is the complete graph with $N$ vertices. For a subset $X\subset E$, let $V_X$ denote the vertices of $X$. So the question is to find the probability of $|V_X|=m$ for random $X$ of size $n$.

For any set $U\subset V$ of size $m$, we can find the number of sets $X\subset E$ with $V_X=U$ using the inclusion-exclusion principle $$ a_{n,m}=\sum_{r=0}^m (-1)^{m-r} \binom{m}{r}\binom{\binom{r}{2}}{n} $$ which corresponds to an alternating sum over sets $X$ and $W$ such that $V_X\subset W\subset U$ with $r=|W|$ in such a way that cases with $V_X=U$ sum to one and all others sum to zero. I've added a more detailed explanation below.

The number of sets $U\subset V$ of size $m$ is $\binom{N}{m}$, so the number of ways to pick $X\subset E$ and $U\subset V$ of sizes $n$ and $m$ is $$ A_{n,m}=a_{n,m}\cdot\binom{N}{m} =\sum_{r=0}^m (-1)^{m-r} \binom{N}{m}\binom{m}{r}\binom{\binom{r}{2}}{n} $$ where the total number of ways to pick $X\subset E$ of size $n$ is $$ A_n=\sum_m A_{n,m}=\binom{\binom{N}{2}}{n} $$ as expected.

So the probability of getting $|V_X|=m$ for a random $X\subset E$ of size $n$ is $$ p_{m|n}=\frac{A_{n,m}}{A_n}. $$


Here's a more detailed explanation of the use of the inclusion-exclusion principle in this particular case.

The problem is that, while you can easily count the number of sets $X\subset E$ with $V_X\subset U$ for any $U\subset V$, but it's harder to only count the $X$ what make $V_X=U$. So what we want to do is to count all $X$ with $V_X\subset U$, and than subtract all those for which $V_X$ is smaller than $U$.

For any $W\subset V$, the number of subsets $X\subset E$ of size $n$ with $V_X\subset W$ is $$ A_n(W)=\binom{\binom{|W|}{2}}{n} $$ since there are $\binom{|W|}{2}$ edges between the vertices of $W$.

If we start with $A_n(U)$, we have counted all $X$ with $V_X\subset U$: not only $X$ with $V_X=U$, but also those for which $V_X$ is smaller than $U$. E.g. if $V_X=U\setminus\{u\}$ for some $u$, it is counted in $A_n(U)$. So a first step is to subtract those: $$A_n(U)-\sum_{u\in U}A_n(U\setminus\{u\}).$$ This counts $X$ with $V_X=U$ once, while $X$ with $V_X=U\setminus\{u\}$ for some $u\in U$ are not counted. However, $X$ with $V_X=U\setminus\{u_1,u_2\}$ have been subtracted twice and have to be added back in: $$ A_n(U)-\sum_{u\in U}A_n(U\setminus\{u\}) +\sum_{\{u_1,u_2\}\subset U} A_n(U\setminus\{u_1,u_2\}. $$ And so we go on alternatingly adding and subtracting until we get $$ \sum_{W\subset U}(-1)^{|U\setminus W|} A_n(W) $$ as the number of $X$ so that $V_X=U$. Now insert that $W\subset U$ with $|W|=r$ can be selected in $\binom{m}{r}$ different ways and $|U\setminus W|=m-r$, and you get the sum for $a_{n,m}$.

$\endgroup$
  • $\begingroup$ Thanks very much for your kindly help. The answer is precise and clear but I am still trying to understand the part about calculating $a_{m,n}$. I am reading the WIKI page of the "inclusion-exclusion principle", could you please give me a little illustrations of this part? Thank you! $\endgroup$ – bigorange66 Aug 7 '16 at 11:38
  • $\begingroup$ @bigorange66 Have added an explanation with some extra details. Put it at the end so the main part of the answer remains more concise. $\endgroup$ – Einar Rødland Aug 7 '16 at 12:24
  • $\begingroup$ Thank you very much! Now I fully understand the idea! However, I find it is difficult to calculate the result when the graph is big. That is, the number of combinations could 'overflow' on my Matlab. I am trying to figure out a way to solve this problem. $\endgroup$ – bigorange66 Aug 7 '16 at 18:44

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.