Degree sequences of random digraphs and bipartite graphs

DOI10.4310/JOC.2016.V7.N1.A2MaRDI QIDQ5963385zbMATHOpenAlexFDO

Authors Brendan D. McKay, Fiona Skerman

Publication date 19 February 2016

Published in Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

random graphoccupancybipartite graphallocationcontiguitydegree sequencedigraphdirected graphcoupon collection

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Combinatorial probability (60C05) Vertex degrees (05C07)

Abstract: We investigate the joint distribution of the vertex degrees in three models of random bipartite graphs. Namely, we can choose each edge with a specified probability, choose a specified number of edges, or specify the vertex degrees in one of the two colour classes. This problem can alternatively be described in terms of the row and sum columns of random binary matrix or the in-degrees and out-degrees of a random digraph, in which case we can optionally forbid loops. It can also be cast as a problem in random hypergraphs, or as a classical occupancy, allocation, or coupon collection problem. In each case, provided the two colour classes are not too different in size nor the number of edges too low, we define a probability space based on independent binomial variables and show that its probability masses asymptotically equal those of the degrees in the graph model almost everywhere. The accuracy is sufficient to asymptotically determine the expectation of any joint function of the degrees whose maximum is at most polynomially greater than its expectation.

Recommendations

• Asymptotic enumeration of digraphs and bipartite graphs by degree sequence
• In-degree sequence in a general model of a random digraph
• Random dense bipartite graphs and directed graphs with specified degrees
• The maximum and minimum degrees of random bipartite multigraphs
• The degree sequence of a random graph. I. The models

Cited in

(18)

• scientific article; zbMATH DE number 1743827 (Why is no real title available?)
• On the method of typical bounded differences
• On the number of non-zero elements of joint degree vectors
• Degree sequences of digraphs with highly irregular property
• The degree sequences of Buckley-Osthus scale-free graphs
• Power-law decay of the degree-sequence probabilities of multiple random graphs with application to graph isomorphism
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• The maximum and minimum degrees of random bipartite multigraphs
• Speed and concentration of the covering time for structured coupon collectors
• Random dense bipartite graphs and directed graphs with specified degrees
• Asymptotic enumeration of digraphs and bipartite graphs by degree sequence
• Degree sequence of random permutation graphs
• Directed weighted random graphs with an increasing bi-degree sequence
• Modularity of Erdős-Rényi random graphs
• In-degree sequence in a general model of a random digraph
• On perfectly friendly bisections of random graphs
• Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence
• Bernoulli trials of fixed parity, random and randomly oriented graphs

This page was built for publication: Degree sequences of random digraphs and bipartite graphs

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