How likely is an LLD degree sequence to be graphical?

DOI10.1214/105051604000000693MaRDI QIDQ1774191zbMATH OpenOpenAlexFDO

Authors Richard Arratia, Thomas M. Liggett

Publication date 29 April 2005

Published in The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

degree distributionsgraphical sequencesorder statistics

Mathematics Subject Classification ID

Vertex degrees (05C07) Random graphs (graph-theoretic aspects) (05C80) Extreme value theory; extremal stochastic processes (60G70)

Abstract: Given i.i.d. positive integer valued random variables D_1,...,D_n, one can ask whether there is a simple graph on n vertices so that the degrees of the vertices are D_1,...,D_n. We give sufficient conditions on the distribution of D_i for the probability that this be the case to be asymptotically 0, {1/2} or strictly between 0 and {1/2}. These conditions roughly correspond to whether the limit of nP(D_igeq n) is infinite, zero or strictly positive and finite. This paper is motivated by the problem of modeling large communications networks by random graphs.

Review text

Let \(D(1),\dots, D(n)\) be a sequnce of independent identically distributed positive integer-valued random variables, and let \(P(n)\) be the probability that the sequence is graphical, i.e. that there is a simple graph on \(n\) vertices with degrees given by the \(n\) values in the sequence. By investigating the limit of \(nP(D(i)>n-1)\) as \(n\) tends to infinity, sufficient conditions are obtained that \(P(n)\) has a limit \(0\) or \(1/2\) or strictly in between. The proof is based on a representation of order statistics by unit exponential random variables.

Recommendations

• scientific article; zbMATH DE number 747036
• Which cospectral graphs have same degree sequences
• Degree sequences in graphs
• scientific article; zbMATH DE number 713480
• Graphs with a given degree sequence
• scientific article; zbMATH DE number 68911
• Graphs and degree sequences. II
• Random graphs with a given degree sequence
• The condition for a sequence to be potentially \(A_{L,M}\)-graphic
• Approximating degree sequences with regular graphic sequences (extended abstract)

Cites work

• A Random Graph Model for Power Law Graphs
• A simple proof of the Erdos-Gallai theorem on graph sequences
• Confirming two conjectures about the integer partitions
• Extremes and related properties of random sequences and processes
• Fast uniform generation of regular graphs
• Generating Random Regular Graphs Quickly
• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 747036 (Why is no real title available?)
• Life Testing
• On the theory of order statistics
• Probability. Theory and examples.
• Random graphs.
• Robustness and Vulnerability of Scale-Free Random Graphs
• Seven criteria for integer sequences being graphic
• Statistical mechanics of complex networks

Cited in

(8)

• Typical distances in the directed configuration model
• Empirical spectral distributions of sparse random graphs
• Ensemble nonequivalence in random graphs with modular structure
• scientific article; zbMATH DE number 4215043 (Why is no real title available?)
• Network-ensemble comparisons with stochastic rewiring and von Neumann entropy
• scientific article; zbMATH DE number 747036 (Why is no real title available?)
• Directed random graphs with given degree distributions
• Inference using noisy degrees: differentially private -model and synthetic graphs

This page was built for publication: How likely is an LLD degree sequence to be graphical?

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