Abstract :
The emph{bipartite realisation problem} asks for a pair of nonnegative, non-increasing integer lists $a:=(a_1,ldots,a_n)$ and $b:=(b_1,ldots,b_{n })$ if there is a labeled bipartite graph $G(U,V,E)$ (no loops or multiple edges) such that each vertex $u_i in U$ has degree $a_i$ and each vertex $v_i in V$ degree $b_i.$ The GaleRyser theorem provides characterisations for the existence of a realisation $G(U,V,E)$ that are strongly related to the concept of emph{majorisation}. We prove a generalisation; list pair $(a,b)$ has more realisations than $(a ,b),$ if $a $ majorises $a.$ Furthermore, we give explicitly list pairs which possess the largest number of realisations under all $(a,b)$ with fixed $n$, $n $ and $m:=sum_{i=1}^n a_i.$ We introduce the notion~emph{minconvex list pairs} for them. If $n$ and $n $ divide $m,$ minconvex list pairs turn in the special case of two constant lists $a=(frac{m}{n},ldots,frac{m}{n})$ and $b=(frac{m}{n },ldots,frac{m}{n }).$
Keywords :
bigraphic sequence , matrices with fixed row and column sums , contingency tables with fixed margins , bipartite realisation problem , Gale , Ryser theorem.