Optimal conditions for $(L_1;L_2)$ to be forcibly bigraphic

Abstract

Let $L_1=([a_1,b_1],\dots ,[a_m,b_m])$ and $L_2=([c_1,d_1],\dots ,[c_n,d_n]$) be two sequences of intervals consisting of nonnegative integers with $b_1\ge \cdots \ge b_m$ and $d_1\ge \cdots \ge d_n$. In this paper, we first give two optimal conditions for the sequences of intervals $L_1$ and $L_2$ such that each pair $(P;Q)$ with $P=(p_1,\dots ,p_m)$, $Q=(q_1,\dots ,q_n)$, $a_i\le p_i\le b_i$ for $1\le i\le m$, $c_i\le q_i\le d_i$ for $1\le i\le n$ and $\sum _{i=1}^m{p}_i=\sum _{i=1}^n{q}_i$ is bigraphic. One of them is optimal sufficient condition and the other one optimal necessary condition. We also present a characterization of $(L_1;L_2)$ that is forcibly bigraphic on sequences of intervals. This is an extension of the well-known theorem on bigraphic sequences due to Gale and Ryser