|
|
|
|
majorization and the number of bipartite graphs for given vertex degrees
|
|
|
|
|
|
|
|
نویسنده
|
berger annabell
|
|
منبع
|
transactions on combinatorics - 2018 - دوره : 7 - شماره : 1 - صفحه:19 -30
|
|
چکیده
|
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'}).$
|
|
کلیدواژه
|
bigraphic sequence ,matrices with fixed row and column sums ,contingency tables with fixed margins ,bipartite realisation problem ,gale-ryser theorem.
|
|
آدرس
|
martin-luther university of halle-wittenberg, department of computer science, germany
|
|
پست الکترونیکی
|
berger@informatik.uni-halle.de
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|