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

order statisticsgraphical sequencesdegree distributions

Mathematics Subject Classification ID

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

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.

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

• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 747036 (Why is no real title available?)
• 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
• 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)

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

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)