0
$\begingroup$

Let G be an undirected graph consisting of N nodes. Let each node in G be connected with two other nodes selected randomly from the remaining nodes with equal probability. What is the probability that the graph G has more than one connected components?

I hope the question well formed.

EDIT. I understand, I didn't form the question properly. Let me give some background from where the problem is arising.

Say N vectors are chosen uniformly over unit circle. Each vector can be expressed as a linear combination of two other vectors from the set. Suppose the two vectors are chosen simply by picking those which have largest inner product with a vector. Now form an $N \times N$ coefficient matrix where each column contains the representation of a vector in terms of others. Naturally the diagonal is all 0. Let $C$ be this coefficient matrix. Now, compute $W = |C| + |C^T|$ as sum of absolute values of $C$ and it's transpose. Think of $W$ as the adjacency matrix of a graph of $N$ nodes corresponding to the vectors. Each node is connected to at least two other nodes. But it may be connected to more nodes also. Is it highly probable that this graph has more than one connected components? A closed form expression for the probability is not required as long as some bound can be obtained.

$\endgroup$
  • $\begingroup$ Is allowed multiple edges between two nodes? Every node has necessarily degree two? Could you explain better the dynamic? $\endgroup$ – Rodrigo Ribeiro Feb 24 '15 at 16:58
0
$\begingroup$

The problem is not quite well-posed. Once it is (randomly) specified that node $a$ connects to node $b$, the probability of some other node $c$ connecting to $a$ (or $b$) can't be the same as the probability of $c$ connecting to some fourth node $d$; at least, not for all choices of $c$ and $d$.

You could make this a well-posed problem as followed: Consider the (finite) set $S$ of all undirected graphs consisting of $N$ (distinguishable) nodes. Undirected graph $G$ is chosen from among the elements of $S$, with equal probability of all elements. What is the probability that $G$ has more than one connected component.

With that rewording, the probability of only one connected component becomes the number of ways to arrange $N$ elements into a single cycle (which is $\frac{1}{2}(N-1)!$) divided by the sum over numbers of cycles $k$ of the number of ways of arranging $N$ objects into $k$ cycles.

If there were at most 2 cycles allowed (which is the case for $N \in \{ 6,7,8 \}$ the denominator would be $$ \frac{1}{2}(N-1)! + \sum_{i=3}^{\lfloor N/2 \rfloor} \binom{N}{i}\frac{1}{2}(i-1)! \frac{1}{2}(N-i-1)! + [N\text{ even}]\frac{1}{4}\binom{N}{N/2}\left[\left( \frac{N}{2}-1\right)!\right]^2 $$ So for example, the probability of just one connected component is $\frac{3}{4}$ for $N=6$, $\frac{24}{31}$ for $N=7$, and $\frac{20}{41}$ for $N=8$. As you open the possibility of three or more connected components, the expressions become messier, and I'm not sure you would be able to find a nice closed-form expression for the probability in general.

$\endgroup$

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.