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

[1] M. Aigner and E. Triesch, Realizability and uniqueness in graphs, Discrete Math., 136 (1994) 3–20.
[2] A. Barvinok, Enumerating contingency tables via random permanents, Combin. Probab. Comput., 17 (2008) 1–19.
[3] A. Barvinok, Matrices with prescribed row and column sums, Linear Algebra Appl., 436 (2012) 820–844.
[4] 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.
[5] 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.
[6] A. Barvinok, Z. Luria, A. Samorodnitsky and A. Yong, An approximation algorithm for counting contingency tables, Random Structures and Algorithms, 37 (2010) 25–66.
[7] B. Bollabas, A probabilistic proof of an asymptotic formula for the number of labeled regular graphs, European J. Combin., 1 (1980), 311 – 316.
[8] Richard Brualdi, Algorithms for constructing matrices with prescribed row and column sum vectors, Discrete Math., 306 (2006) 3054 – 3062.
[9] Richard Brualdi, Combinatorial matrix classes, Cambridge University Press, 2006.
[10] 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.
[11] 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.

[12] C. M. da Fonseca and R. Mamede, On (0,1)-matrices with prescribed row and column sum vectors, Discrete Math., 309 (2009) 2519 – 2527.
[13] M. Dyer, R. Kannan and J. Mount, Sampling contingency tables, Random Structures Algorithms, 10 (1997) 487–506.
[14] 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.
[15] http://www-history.mcs.st-andrews.ac.uk/Biographies/Ferrers.html, 2017.
[16] D. Gale, A theorem on flows in networks, Pacific J. Math., 7 (1957) 1073–1082.
[17] 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.
[18] V. Havel, A remark on the existence of finite graphs, Casopis Pest. Math., 80 (1955), 477–480.
[19] G. H. Hardy, J. E. Littlewood and G. Polya, Some simple inequalities satisfied by convex functions, Messenger Math., 58 (1929) 145–152.
[20] G. H. Hardy, J. E. Littlewood and G. Polya, Inequalities, 1st ed. Cambridge Univ. Press, 1934.
[21] P. L. Hammer, U. N. Peled and X. Sun, Difference graphs, Discrete Appl. Math., 28 (1990) 35-44.
[22] 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.
[23] 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.
[24] 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.
[25] B. McKay and N. Wormald, Asymptotic enumeration by degree sequence of graphs with degrees o(n1/2), Combina-torica, 11 (1991) 369–382.
[26] 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.
[27] 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.
[28] H. J. Ryser, Combinatorial properties of matrices of zeros and ones, Canad J. Math., 9 (1957) 371–377.
[29] 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.

Files

Cited by

History

  • Receive Date: 31 January 2017
  • Revise Date: 20 April 2017
  • Accept Date: 24 April 2017
  • Published Online: 01 March 2018

Share

How to cite

Statistics