论文标题
根据程度序列的渐近枚举和两分图的枚举
Asymptotic enumeration of digraphs and bipartite graphs by degree sequence
论文作者
论文摘要
我们为具有给定度序列的两部分图的数量以及具有给定的内和外序序列的无环形图形提供了渐近公式，用于广泛的参数。我们的结果涵盖了中等范围的密度，并缩小了稀疏和致密范围已知的结果之间的差距。就两分图而言，这些结果由Greenhill，McKay和Wang在2006年和Canfield，Greenhill和McKay在2008年证明。我们的方法还涵盖了稀疏范围，在无环形挖掘的情况下，少得多。对于我们的结果覆盖的密度范围，它们暗示具有M边缘的随机两分图的度序列由一系列独立的二项式随机变量进行准确模拟，条件是每个部分的变量之和等于m。类似的模型也适用于无环的挖掘。
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. Our results cover medium range densities and close the gaps between the results known for the sparse and dense ranges. In the case of bipartite graphs, these results were proved by Greenhill, McKay and Wang in 2006 and by Canfield, Greenhill and McKay in 2008, respectively. Our method also essentially covers the sparse range, for which much less was known in the case of loopless digraphs. For the range of densities which our results cover, they imply that the degree sequence of a random bipartite graph with m edges is accurately modelled by a sequence of independent binomial random variables, conditional upon the sum of variables in each part being equal to m. A similar model also holds for loopless digraphs.
