zbMATH — the first resource for mathematics

A critical point for random graphs with a given degree sequence. (English) Zbl 0823.05050
Let \(\lambda_ 0,\lambda_ 1,\dots\) be a sequence of non-negative real numbers summing to 1. This paper considers random graphs with \(n\) vertices and approximately \(\lambda_ i n\) vertices of degree \(i\). Let \(Q\) be the sum of the quantities \(i(i- 2)\lambda_ i\) over \(i= 1,2,\dots\). It is shown (under some restrictions) that if \(Q> 0\) then with probability \(\to 1\) as \(n\to \infty\), such graphs have a ‘giant component’, whereas if \(Q< 0\) then all components are small. This result and the proof method yield new insight on the classical ‘double-jump’ threshold for usual random graphs, and can be applied in investigations concerning the chromatic number of sparse random graphs.

05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
Full Text: DOI
[1] Azuma, Weighted sums of certain dependent random variables, Tokuku Math. J. 19 pp 357– (1967) · Zbl 0178.21103
[2] Bender, The asymptotic number of labelled graphs with given degree sequences, J. Combinat. Theory (A) 24 pp 296– (1978) · Zbl 0402.05042
[3] Bollobás, Random Graphs (1985)
[4] Bollobás, Martingales, Isoperimetric inequalities and random graphs, Colloq. Math. Soc. Janós Bolyai 52 pp 113– (1987)
[5] Bollobás, On matchings and Hamiltonian cycles in random graphs, Ann. Discrete Math. 28 pp 23– (1985)
[6] Bollobás, Random graphs of small order. Random Graphs ’83, Ann. Discrete Math. 28 pp 47– (1985)
[7] Chvátal, Almost all graphs with 1.44n edges are 3-colorable, Random Struct. Alg. 2 pp 11– (1991) · Zbl 0715.05026
[8] Erdös, On the evolution of random graphs, Magayr Tud. Akad. Mat. Kutato Int. Kozl. 5 pp 17– (1960)
[9] Feller, An Introduction to Probability Theory and its Applications 1 (1966) · Zbl 0138.10207
[10] Flajolet, The first cycles in an evolving graph, Discrete Math. 75 pp 167– (1989) · Zbl 0696.05045
[11] Flajolet, The birth of the giant component, Random Struct. Alg. 4 (1993)
[12] Gallai, Kritische graphen I, Magayr Tud. Akad. Mat. Kutato Int. Kozl. 8 pp 165– (1963)
[13] Łuczak, Component behaviour near the critical point of the random graph process, Random Struct. Alg. 1 pp 287– (1990) · Zbl 0745.05048
[14] Łuczak, Sparse random graphs with a given degree sequence, Random Graphs 2 pp 165– (1992) · Zbl 0817.05057
[15] Łuczak, The chromatic number of random graphs at the doublejump threshold, Combinatorica 9 pp 39– (1989) · Zbl 0715.05056
[16] C. McDiarmid On the method of bounded differences Surveys in Combinatorics, Proc. Twelfth British Combinatorial Conference 1989 148 188
[17] McKay, Asymptotics for symmetric 0-1 matrices with prescribed row sums, Ars Combinat. 19A pp 15– (1985) · Zbl 0568.05032
[18] M. Molloy The chromatic number of sparse random graphs 1992
[19] Robinson, Almost all cubic graphs are Hamiltonian, Random Struct. Alg. 3 pp 117– (1992) · Zbl 0755.05075
[20] R. W. Robinson N. C. Wormald Almost all regular graphs are Hamiltonian
[21] N. C. Wormald Some problems in the enumeration of labelled graphs 1978
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.