How likely is an LLD degree sequence to be graphical? (Q1774191)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | How likely is an LLD degree sequence to be graphical? |
scientific article |
Statements
How likely is an LLD degree sequence to be graphical? (English)
0 references
29 April 2005
0 references
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.
0 references
degree distributions
0 references
graphical sequences
0 references
order statistics
0 references