×

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
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] 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
[2] 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
[3] Bollobás, B. (2001). Random Graphs , 2nd ed. Cambridge Univ. Press. · Zbl 0979.05003
[4] 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
[5] 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
[6] Durrett, R. (1996). Probability : Theory and Examples , 2nd ed. Duxbury, N. Scituate, MA. · Zbl 1202.60001
[7] Epstein, B. and Sobel, M. (1953). Life testing. J. Amer. Statist. Assoc. 48 486–502. · Zbl 0051.36502 · doi:10.2307/2281004
[8] Erdős, P. and Gallai, T. (1960). Graphs with given degree of vertices. Mat. Lapok 11 264–274. · Zbl 0103.39701
[9] Janson, S., Luczak, T. and Rucinski, A. (2000). Random Graphs. Wiley, New York.
[10] 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
[11] 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
[12] 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
[13] 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
[14] 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
[15] 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
[16] 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.