Random dense bipartite graphs and directed graphs with specified degrees

DOI10.1002/RSA.20273MaRDI QIDQ3055774zbMATH OpenOpenAlexFDO

Authors Catherine Greenhill, Brendan D. McKay

Publication date 9 November 2010

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

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

zbMATH Keywords

0-1 matrixasymptotic enumerationbipartite graphdigraphdirected graphrandom graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Let S and T be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence S in one part and T in the other; equivalently, binary matrices with row sums S and column sums T. In particular, we find precise formulae for the probabilities that a given bipartite graph is edge-disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out-degrees S and in-degrees T. In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums S and column sums T.

Recommendations

• Degree sequences of random digraphs and bipartite graphs
• Asymptotic enumeration of digraphs and bipartite graphs by degree sequence
• Subgraphs of dense random graphs with specified degrees
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• Subgraphs of random graphs with specified degrees

Cites work

• Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums
• Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• Asymptotic Enumeration of Eulerian Circuits in the Complete Graph
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• Asymptotic enumeration of tournaments with a given score sequence
• Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph
• Hamilton Cycles in Random Regular Digraphs
• scientific article; zbMATH DE number 3773632 (Why is no real title available?)
• scientific article; zbMATH DE number 91021 (Why is no real title available?)
• scientific article; zbMATH DE number 1052843 (Why is no real title available?)
• Random dense bipartite graphs and directed graphs with specified degrees
• The asymptotic number of non-negative integer matrices with given row and column sums
• The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs
• The number of matchings in random regular graphs and bipartite graphs
• Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all

Cited in

(16)

• The switch Markov chain for sampling irregular graphs and digraphs
• 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
• Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications
• Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs
• Subgraphs of dense random graphs with specified degrees
• Random dense bipartite graphs and directed graphs with specified degrees
• Directed weighted random graphs with an increasing bi-degree sequence
• Induced subgraphs in sparse random graphs with given degree sequences
• The number of graphs and a random graph with a given degree sequence
• Directed random graphs with given degree distributions
• Degree sequences of random digraphs and bipartite graphs
• Factorisation of the complete bipartite graph into spanning semiregular factors
• Asymptotic enumeration of digraphs and bipartite graphs by degree sequence
• The rank of the sandpile group of random directed bipartite graphs
• On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

This page was built for publication: Random dense bipartite graphs and directed graphs with specified degrees

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