Consider a bipartite graph $G=(X,Y)$, such that the degree of a left node $x \in X$ is $l$, and the degree of a right node $y \in Y$ is $r$. The number of edges is $|E|=|X|l=|Y|r$.

Pick $w$ nodes in $X$ in random. We take a subgraph of $G$ by connecting at random the $wl$ sockets of the chosen $w$ nodes to distinct right nodes $Y' \subseteq Y$. That is, the sample space is all the permutations from the $wl$ sockets to sockets in $Y$. In a valid subgraph, at least two sockets of each $y' \in Y'$ is connected.

I want to calculate the probability of a valid subgraph with a particular right-degree distribution. That is, what is the probability of a valid subgraph that has $c_1$ right-nodes of degree $r_1$, $c_2$ right-nodes of degree $r_2$ and so on.

I know how to calculate the probability that a subgraph is valid, which is

$$\frac{{{\rm{coef}}\left( {{{\left( {{{\left( {1 + y} \right)}^r} - 1 - ry} \right)}^{\left| Y \right|}},{y^{wl}}} \right)}}{{{|X|l \choose wl}}},$$ where ${{\rm{coef}}\left( {f\left( x \right),{x^i}} \right)}$ is the $i$th coefficient $f_i$ of $f\left( x \right) = \sum\limits_{i \ge 0} {{f_i}{x^i}}$. However, I am not sure how to proceed.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.