How likely is an LLD degree sequence to be graphical? (Q1774191)

From MaRDI portal
Revision as of 10:43, 10 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    degree distributions
    0 references
    graphical sequences
    0 references
    order statistics
    0 references
    0 references
    0 references