2
$\begingroup$

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.

$\endgroup$

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.