Title of article :
Majorization and the number of bipartite graphs for given vertex degrees
Author/Authors :
Berger ، Annabell - Martin-Luther University of Halle-Wittenberg
Pages :
12
From page :
19
To page :
30
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.
Journal title :
Transactions on Combinatorics
Serial Year :
2018
Journal title :
Transactions on Combinatorics
Record number :
2448959
Link To Document :
بازگشت