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
    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