Majorization and the number of bipartite graphs for given vertex degrees

The \emph{bipartite realisation problem} asks for a pair of non-negative‎, ‎non-increasing integer lists a:=(a_۱,\ldots,a_n) and b:=(b_۱,\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 Gale-Ryser 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=۱}^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