Asymptotic enumeration of digraphs and bipartite graphs by degree sequence

DOI10.1002/RSA.21105zbMATH Open1522.05012arXiv2006.15797OpenAlexW3037707435MaRDI QIDQ6074864FDOQ6074864

Authors: Anita Liebenau, Nicholas Wormald 

Publication date: 19 October 2023

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

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. 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.

Full work available at URL: https://arxiv.org/abs/2006.15797

Recommendations

• Degree sequences of random digraphs and bipartite graphs
• Random dense bipartite graphs and directed graphs with specified degrees
• The number of graphs and a random graph with a given degree sequence
• Asymptotic enumeration of graphs with given degree sequence
• Asymptotic enumeration by degree sequence of graphs of high degree

zbMATH Keywords

digraphsdegree sequencerandom graphsasymptotic enumerationbipartite graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07) Asymptotic enumeration (05A16) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Transversal theory. An account of some aspects of combinatorial mathematics
• The enumeration of arrays and a generalization related to contingency tables
• Some problems in the enumeration of labelled graphs
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• Random dense bipartite graphs and directed graphs with specified degrees
• Degree sequences of random digraphs and bipartite graphs
• Title not available (Why is that?)
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
• Title not available (Why is that?)
• Asymptotics and random matrices with row-sum and column sum-restrictions
• The number of matchings in random regular graphs and bipartite graphs
• The asymptotic number of non-negative integer matrices with given row and column sums
• The number of graphs and a random graph with a given degree sequence
• On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
• Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums
• The asymptotic number of integer stochastic matrices
• The degree sequence of a random graph. I. The models
• Complex martingales and asymptotic enumeration

Cited In (11)

• Title not available (Why is that?)
• Random dense bipartite graphs and directed graphs with specified degrees
• Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• The number of graphs and a random graph with a given degree sequence
• Complex martingales and asymptotic enumeration
• Title not available (Why is that?)
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Degree sequences of random digraphs and bipartite graphs
• Asymptotic enumeration of Cayley digraphs
• Asymptotic enumeration of graphs with given degree sequence

This page was built for publication: Asymptotic enumeration of digraphs and bipartite graphs by degree sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074864)