Asymptotic enumeration of digraphs and bipartite graphs by degree sequence. Issue 2 (25th July 2022)

• Record Type: Journal Article
• Authors: Liebenau, Anita; Wormald, Nick
• Is Part Of: Random structures & algorithms. Volume 62:Issue 2(2023)
• Page Start: 259
• Page End: 286
• Publication Date: 2022-07-25
• Subjects: asymptotic enumeration -- bipartite graphs -- degree sequence -- digraphs -- random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21105
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We provide asymptotic formulae for the numbers of bipartite graphs with given degree sequence, and of loopless digraphs with given in‐ and out‐degree sequences, for a wide range of parameters including the biregular case. In particular, for bipartite graphs with part sizes that are not highly unequal, our results cover an existing gap in known results between the sparse and dense cases that were proved by Greenhill, McKay, and Wang in 2006 and by Canfield, Greenhill, and McKay in 2008, respectively. For the range of parameters which our results cover, they imply that the degree sequence of a random bipartite graph with m $$ m $$ edges and given part sizes is accurately modeled by a sequence of independent binomial random variables, conditional upon the sum of variables in each part being equal to m $$ m $$ . This extends the known behavior in the sparse and dense cases to essentially the full spectrum of possible densities. A similar model also holds for loopless digraphs.