ON THE INDEPENDENCE NUMBER OF RANDOM GRAPHS

被引：110

作者：

FRIEZE, AM

机构：

[1] Department of Mathematics, Carnegie Mellon University, Pittsburgh

来源：

DISCRETE MATHEMATICS | 1990年 / 81卷 / 02期

关键词：

D O I：

10.1016/0012-365X(90)90149-C

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let α(Gn,p) denote the independence number of the random graph Gn,p. Let d=np. We show that if ε{lunate} > 0 is fixed then with probability going to 1 as n → ∞ ∥α(Gn,p)- 2n d(logd-loglogd-log2+1)∥≤ ε{lunate}n d provided dε{lunate}≤d=o(n), where dε{lunate} is some fixed constant. © 1990.

引用

页码：171 / 175

页数：5

共 8 条

[1]

BOLLOBAS B, 1976, MATH PROC CAMBRIDGE, V80, P419, DOI 10.1017/S0305004100053056

[2]

BOLLOBAS B, IN PRESS COMBINATORI

[3]

Bollobas B., 1985, RANDOM GRAPHS

[4] COLORING RANDOM GRAPHS [J].

GRIMMETT, GR ;

MCDIARMID, CJH .

MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1975, 77 (MAR) :313-324

[5]

Matula David W., 1970, P 2 CHAP HILL C COMB, P356

[6] EXPOSE-AND-MERGE EXPLORATION AND THE CHROMATIC NUMBER OF A RANDOM GRAPH [J].

MATULA, DW .

COMBINATORICA, 1987, 7 (03) :275-284

[7]

SHAMIR E, IN PRESS COMBINATORI

[8]

Stout W, 1974, ALMOST SURE CONVERGE

← 1 →