Probability that two vertices are connected in a configuration model

Question

Let CM$_n(\boldsymbol{d})$ $(n \gg 4)$ denotes a configuration model with $n$ vertices and degree sequence $\boldsymbol{d}$. Let $l_n$ be the total number of half-edges. Here, two vertices are connected if there is at least one edge between them.

Let $v_0, v_1, v_2, v_3$ be vertices in CM$_n(\boldsymbol{d})$ such that $d_{v_0} = 1, d_{v_1} = d_{v_2} = d_{v_3} = 2$. How do you compute the probability that $v_0$ and $v_1$ are connected? Is it $\frac{1}{3}$ because $v_0$ can be either connected to one of $v_i, i = 1, 2, 3$? But $v_0$ can form self-loop, can't it?

Also, what is the probability that $v_1$ and $v_2$ are connected? The vertex $v_1$ in this case can form a multi-edge with $v_2$. But once that happen, there will be two seperate sub-graphs I believe.

A hint on how to solve this problem would be appreciated.

Answer 1

The probability that $v_0$ and $v_1$ are adjacent would only be $\frac13$ if $v_0, v_1, v_2, v_3$ are the only vertices, but in that case we'd run into a further problem, because the number of half-edges is odd. I will take the beginning of your question at face value and assume that there are $n \gg 4$ vertices, and $l_n$ half-edges.

Then the probability that $v_0$ and $v_1$ are adjacent is $\frac2{l_n-1}$: the single half-edge out of $v_1$ can be connected to $l_n-1$ other half-edges, and two of them result in an adjacency between $v_0$ and $v_1$. Because there is only one half-edge at $v_0$, there can't be a self-loop: that happes when two half-edges at the same vertex are joined together.

For $v_1$ and $v_2$, there are more possibilities:

• There is a $\frac1{l_n-1}$ chance of a self-loop at $v_1$, in which case the two vertices are not adjacent.
• If there is no self-loop, then the probability that neither half-edge at $v_1$ gets paired with a half-edge at $v_2$ is $(1 - \frac2{l_n-2})(1 - \frac2{l_n-3})$. (The first half-edge has can be paired with $l_n-2$ other half-edges that are not at $v_1$. Then, the second half-edge has $l_n-3$ options.)

Therefore $1 - \frac1{l_n-1} - (1 - \frac2{l_n-2})(1 - \frac2{l_n-3})$ is the probability that $v_1$ and $v_2$ are adjacent.

For higher degrees, we could continue like this, considering several cases for the number of self-loops at one endpoint.