# Majorization and the number of bipartite graphs for given vertex degrees

Document Type: Research Paper

Author

Department of Computer Science Martin-Luther University Halle-Wittenberg

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

Main Subjects

### References

 M. Aigner and E. Triesch, Realizability and uniqueness in graphs, Discrete Math., 136 (1994) 3–20.

 A. Barvinok, Enumerating contingency tables via random permanents, Combin. Probab. Comput., 17 (2008) 1–19.

 A. Barvinok, Matrices with prescribed row and column sums, Linear Algebra Appl., 436 (2012) 820–844.

 I. Bezáková, N. Bhatnagar and E. Vigoda, Sampling binary contingency tables with a greedy start, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, New York, 2006 414–423.

 E. Bender and E. R. Canfield, The asymptotic number of labeled graphs with given degree sequences, J. Combina-torial Theory Ser. A, 24 (1978) 296-307.

 A. Barvinok, Z. Luria, A. Samorodnitsky and A. Yong, An approximation algorithm for counting contingency tables, Random Structures and Algorithms, 37 (2010) 25–66.

 B. Bollabas, A probabilistic proof of an asymptotic formula for the number of labeled regular graphs, European J. Combin., 1 (1980), 311 – 316.

 Richard Brualdi, Algorithms for constructing matrices with prescribed row and column sum vectors, Discrete Math., 306 (2006) 3054 – 3062.

 Richard Brualdi, Combinatorial matrix classes, Cambridge University Press, 2006.

 E. R. Canfield, C. Greenhill and B. D. McKay, Asymptotic enumeration of dense (0,1) matrices with specified line sums, J. Combinatorial Theory Ser. A, 115 (2008) 32-66.

 V. Chvátal and P. L. Hammer, Aggregation of inequalities in integer programming, Studies in integer programming (Proc. Workshop, Bonn, 1975), 1 North-Holland, Amsterdam, 1977.

 C. M. da Fonseca and R. Mamede, On (0,1)-matrices with prescribed row and column sum vectors, Discrete Math., 309 (2009) 2519 – 2527.

 M. Dyer, R. Kannan and J. Mount, Sampling contingency tables, Random Structures Algorithms, 10 (1997) 487–506.

 R. Fernandes and H. F. da Cruz, An extension of brualdis algorithm for the construction of matrices with prescribed row and column sum vectors, Discrete Math., 313 (2013) 2365 – 2379.

 http://www-history.mcs.st-andrews.ac.uk/Biographies/Ferrers.html, 2017.

 D. Gale, A theorem on flows in networks, Pacific J. Math., 7 (1957) 1073–1082.

 S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a simple graph, J. SIAM Appl. Math., 10 (1962) 496–506.

 V. Havel, A remark on the existence of finite graphs, Casopis Pest. Math., 80 (1955), 477–480.

 G. H. Hardy, J. E. Littlewood and G. Polya, Some simple inequalities satisfied by convex functions, Messenger Math., 58 (1929) 145–152.

 G. H. Hardy, J. E. Littlewood and G. Polya, Inequalities, 1st ed. Cambridge Univ. Press, 1934.

 P. L. Hammer, U. N. Peled and X. Sun, Difference graphs, Discrete Appl. Math., 28 (1990) 35-44.

 M. Jerrum, A. Sinclair and E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J. ACM, 51 (2004) 671–697.

 A. W. Marshall and I. Olkin, Inequalities: theory of majorization and its applications, Academic Press, New York, 1979.

[MP95] N. V. R. Mahadev and U. N. Peled, Threshold graphs and related topics, Annals of Discrete Mathematics, North Holland, The Netherlands, 1995.

 R. F. Muirhead, Some methods applicable to identities and inequalities of symmetric algebraic functions of n letters, Proceedings of the Edinburgh Mathematical Society, 21 (1902) 144–162.

 B. McKay and N. Wormald, Asymptotic enumeration by degree sequence of graphs with degrees o(n1/2), Combina-torica, 11 (1991) 369–382.

 E. Ordentlich, F. Parvaresh, R. M. Roth, Asymptotic enumeration of binary matrices with bounded row and column weights, Published in 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), 2011 154–158.

 B. R. Pérez-Salvador, S. de-los Cobos-Silva, M. Angel Gutiérrez-Ándrade and A. Torres-Chazaro, A reduced formula for the precise number of (0,1)-matrices in a(r,s), Discrete Math., 256 (2002) 361–372.

 H. J. Ryser, Combinatorial properties of matrices of zeros and ones, Canad J. Math., 9 (1957) 371–377.

 J. J. Sylvester and F. Franklin, A constructive theory of partitions, arranged in three acts, an interact and an exodion, Amer. J. Math., 5 (1882) 251–330.