Transactions on Combinatorics (Mar 2018)
Majorization and the number of bipartite graphs for given vertex degrees
Abstract
The emph{bipartite realisation problem} asks for a pair of non-negative, 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 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=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
