Premium
Asymptotic enumeration of digraphs and bipartite graphs by degree sequence
Author(s) -
Liebenau Anita,
Wormald Nick
Publication year - 2023
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21105
Subject(s) - bipartite graph , combinatorics , mathematics , enumeration , degree (music) , sequence (biology) , cover (algebra) , dense graph , complete bipartite graph , discrete mathematics , range (aeronautics) , binomial (polynomial) , graph , 1 planar graph , line graph , statistics , genetics , mechanical engineering , physics , materials science , biology , acoustics , engineering , composite material
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 withm $$ 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 tom $$ 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.