Degree sequences of random digraphs and bipartite graphs

DOI10.4310/JOC.2016.V7.N1.A2MaRDI QIDQ5963385zbMATH OpenOpenAlexFDO

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

allocationbipartite graphcontiguitycoupon collectiondegree sequencedigraphdirected graphoccupancyrandom graph

Mathematics Subject Classification ID

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

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

(19)

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

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)