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

From MaRDI portal





scientific article; zbMATH DE number 2162803
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; zbMATH DE number 2162803

      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