Degree sequences of random digraphs and bipartite graphs

DOI10.4310/JOC.2016.V7.N1.A2zbMATH Open1331.05198arXiv1302.2446OpenAlexW1561063814MaRDI QIDQ5963385FDOQ5963385

Fiona Skerman, Brendan D. McKay

Publication date: 19 February 2016

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

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.

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

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

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)

Cited In (15)

• Title not available (Why is that?)
• Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence
• On the Method of Typical Bounded Differences
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• In-degree sequence in a general model of a random digraph
• Speed and concentration of the covering time for structured coupon collectors
• Asymptotic enumeration of digraphs and bipartite graphs by degree sequence
• Directed weighted random graphs with an increasing bi-degree sequence
• On perfectly friendly bisections of random graphs
• Modularity of Erdős‐Rényi random graphs
• Degree sequences of digraphs with highly irregular property
• The maximum and minimum degrees of random bipartite multigraphs
• 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
• Degree sequence of random permutation 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)