# zbMATH — the first resource for mathematics

How likely is an LLD degree sequence to be graphical? (English) Zbl 1079.05023
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.

##### MSC:
 05C07 Vertex degrees 05C80 Random graphs (graph-theoretic aspects) 60G70 Extreme value theory; extremal stochastic processes
##### Keywords:
degree distributions; graphical sequences; order statistics
Full Text:
##### References:
  Aiello, W., Chung, F. and Lu, L. (2001). A random graph model for power law graphs. Experiment. Math. 10 53–66. · Zbl 0971.05100 · doi:10.1080/10586458.2001.10504428 · emis:journals/EM/expmath/volumes/10/10.html · eudml:227051  Albert, R. and Barabási, A. (2002). Statistical mechanics of complex networks. Rev. Modern Phys. 74 47–97. · Zbl 1205.82086 · doi:10.1103/RevModPhys.74.47  Bollobás, B. (2001). Random Graphs , 2nd ed. Cambridge Univ. Press. · Zbl 0979.05003  Bollobás, B. and Riordan, O. (2003). Mathematical results on scale-free random graphs. In Handbook of Graphs and Networks : From the Genome to the Internet (S. Bornholdt and H. G. Schuster, eds.) 1–34. Wiley–VCH, New York. · Zbl 1062.05080  Choudum, S. A. (1986). A simple proof of the Erdős–Gallai theorem on graph sequences. Bull. Austral. Math. Soc. 33 67–70. · Zbl 0571.05048 · doi:10.1017/S0004972700002872  Durrett, R. (1996). Probability : Theory and Examples , 2nd ed. Duxbury, N. Scituate, MA. · Zbl 1202.60001  Epstein, B. and Sobel, M. (1953). Life testing. J. Amer. Statist. Assoc. 48 486–502. · Zbl 0051.36502 · doi:10.2307/2281004  Erdős, P. and Gallai, T. (1960). Graphs with given degree of vertices. Mat. Lapok 11 264–274. · Zbl 0103.39701  Janson, S., Luczak, T. and Rucinski, A. (2000). Random Graphs. Wiley, New York.  Jerrum, M., McKay, B. and Sinclair, A. (1992). When is a graphical sequence stable? In Random Graphs (A. Frieze and T. Luczak, eds.) 2 101–115. Wiley, New York. · Zbl 0819.05052  Jerrum, M. and Sinclair, A. (1990). Fast uniform generation of regular graphs. Theoret. Comput. Sci. 73 91–100. · Zbl 0694.68044 · doi:10.1016/0304-3975(90)90164-D  Leadbetter, M. R., Lindgren, G. and Rootzén, H. (1983). Extremes and Related Properties of Random Sequences and Processes. Springer, New York. · Zbl 0518.60021  Pittel, B. (1999). Confirming two conjectures about the integer partitions. J. Combin. Theory Ser. A 88 123–135. · Zbl 0937.05008 · doi:10.1006/jcta.1999.2986  Rényi, A. (1953). On the theory of ordered samples. Acta Math. Acad. Sci. Hungar. 4 191–231. · Zbl 0052.14202 · doi:10.1007/BF02127580  Sierksma, G. and Hoogeveen, H. (1991). Seven criteria for integer sequences being graphic. J. Graph Theory 15 223–231. · Zbl 0752.05052 · doi:10.1002/jgt.3190150209  Steger, A. and Wormald, N. (1999). Generating random graphs quickly. Combin. Probab. Comput. 8 377–396. · Zbl 0935.05082 · doi:10.1017/S0963548399003867
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.