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

From MaRDI portal





scientific article
Language Label Description Also known as
default for all languages
No label defined
    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
      degree distributions
      0 references
      graphical sequences
      0 references
      order statistics
      0 references

      Identifiers