2 added 62 characters in body

It is known that the sequence $d_1 \geq d_2 \geq \ldots \geq d_n$ of nonnegative integers is the degree sequence of a graph if and only if the sum of the $d_i$ is even and we have $\sum_{i = 1}^k d_i \leq k(k - 1) + \sum_{i = k + 1}^n \min(d_i, k)$ for all $k \in \{1, \ldots, n\}$. (This is the Erdős–Gallai theorem.) There is also a simple algorithm (the Havel-Hakimi algorithm) for producing a graph with a given valid degree sequence.

Is there a simple characterization of pairs $\{(a_1 \geq \ldots \geq a_m), (b_1 \geq \ldots \geq b_n)\}$ of sequences of nonnegative integers such that there exists a bipartite graph with the property that the degrees of the vertices in one part are given by the $a_i$ and the degrees of the vertices in the other part is given by the $b_j$?

An obvious necessary condition is that $\sum a_i = \sum b_j$, but this is also clearly not sufficient. One can also ask for an algorithm analogous to Havel-Hakimi.

1

# Classification of degree (bi-)sequences of bipartite graphs?

It is known that the sequence $d_1 \geq d_2 \geq \ldots \geq d_n$ of nonnegative integers is the degree sequence of a graph if and only if the sum of the $d_i$ is even and we have $\sum_{i = 1}^k d_i \leq k(k - 1) + \sum_{i = k + 1}^n \min(d_i, k)$ for all $k \in \{1, \ldots, n\}$. (This is the Erdős–Gallai theorem.) There is also a simple algorithm (the Havel-Hakimi algorithm) for producing a graph with a given valid degree sequence.

Is there a simple characterization of pairs $\{(a_1 \geq \ldots \geq a_m), (b_1 \geq \ldots \geq b_n)\}$ of sequences of nonnegative integers such that there exists a bipartite graph with the property that the degrees of the vertices in one part are given by the $a_i$ and the degrees of the vertices in the other part is given by the $b_j$?

An obvious necessary condition is that $\sum a_i = \sum b_j$, but this is also clearly not sufficient.