Random bipartite graph with lower bounded degrees

Question

Let $i$ be a positive integer and $V_1, V_2$ be the vertex sets of a bipartite graph. We want to sample uniformly at random a bigraph in the set of bigraphs with vertex set $V_1 \cup V_2$ such that for each $v \in V_1$, it has at least $i$ neighbors in $V_2$ and for each $u \in V_2$, it has at least one neighbor in $V_1$.

Is there any efficient way to do this?

Answer 1

A plausible method is rejection sampling, along the following lines:

1. For every vertex $v \in V_1$, choose a uniformly random subset of size $\ge i$ from $V_2$, and add edges from $v$ to that subset.
2. If there is any vertex in $V_2$ of degree $0$, throw everything away and start over.

In step $1$, the graphs that satisfy the degree condition in $V_1$ are sampled uniformly at random. So if we repeat until the degree condition in $V_2$ is also satisfied, we end up sampling uniformly from the set of graphs that satisfy both kinds of conditions.

Unless $V_2$ is much much larger than $V_1$, this will still be reasonably efficient. Let $n_1 = |V_1|$ and $n_2 = |V_2|$. Each edge in a graph created in step $1$ exists with probability $> \frac12$: the condition that $\deg(v) \ge i$ only makes edges more likely relative to the baseline. Therefore the probability that a given vertex in $V_2$ is isolated is less than $2^{-n_1}$, and the probability that any vertex in $V_2$ is isolated is less than $n_2 \cdot 2^{-n_1}$.

In particular, when $n_2 \le 2^{n_1 - 1}$, the probability of failure is less than $\frac12$, and the average number of times we have to do step 1 is less than $2$.

Answer 2

It seems unlikely to find a uniform method.

If $|V_1|=m$ and $|V_2|=n,$ then this is equivalent to $A_1,\dots,A_m\subseteq \{1,\dots,n\},$ with each $|A_k|\geq i.$

The total number of such graphs can be counted by inclusion/exclusion. Let $U$ be the set of all $(A_1,\dots,A_m)$ with just the condition that each $k$ has at Least $i$ elements. Let $U_j$ be the set of such tuples where none of the $A_i$ contains $j,$ $j=1,\dots,n.$

Then the total such graphs is:

$$\sum_{j=0}^{n}(-1)^j\binom nj f(n-j,i)^m\tag1$$

where $$f(k,i)=\sum_{p=i}^k \binom kp,$$ the number of subsets of a set of $p$ elements with size at least $i.$

That exponent $m$ in the sum, and the fact that $f$ has no closed form, makes this a very tricky count.

Let’s take $i=2,m=3,n=4.$

Then $f(4,2)=11,f(3,2)=4,f(2,2)=1$ and the other values of $f$ are zero.

So the value is: $$11^3-4\cdot 4^3+6\cdot 1^3=1081=23\cdot 47.$$

So to have a uniform selection from these answers, you can’t just flip a coin some finite number of times. That results in $2^T$ outcomes, for some $T.$ Indeed, you need to have a set of equal outcomes to your numbers which is a multiple of $1081.$

And even then, it’s not obvious how to translate that to an element of $U.$

I suppose you could do more examples and see if you get a good pattern. It looks interesting that $1081$ is a triangular number.

---

If $m=5,n=4,i=3,$ then the count is:

$$5^5-4\cdot 1^5=3121$$

which is prime. That makes an incremental bounded process highly unlikely to work.

---

A non-bounded process, such as doing trials and checking if you match the conditions and starting over if you don’t, is probably the best you can do. You can possibly do a semi-smart trial generator - one where you generate uniformly some superset of the graphs you want.