Zero-one laws for sparse random graphs
Zero-one laws for sparse random graphs
复制标题
DOI：
10.1090/s0894-0347-1988-0924703-8
复制
发表时间：
1988
影响因子：
3.9
通讯作者：
S. Shelah;J. Spencer
中科院分区：
文献类型：
--
作者：
S. Shelah;J. Spencer
对于随机图理论家（参见，例如，Bollobas [1]一般参考）p“任何常数”不是唯一的，甚至不是最有趣的情况。相反，他们考虑p = p（n），一个接近零的函数。在他们的开创性论文中，Erd 6s和Renyi [5]表明，对于许多有趣的A，存在一个函数p（n），他们称之为阈值函数，因此如果r（n）< p（n）则f（n，r（n），A）-+ 0，而如果p（n）< r（n）则f（n，r（n），A）1-+。（符号：p < r表示lim p/r = 0。所有极限都是当n接近无穷大时。）假设p = p（n）满足零一定律，如果对GRA中的所有A，limf（n，p，A）= 0或1。我们将部分描述满足零一定律的p = p（n）。
For random graph theorists (see, e.g., Bollobas [1] for general reference) p "any constant" is not the only, not even the most interesting case. Rather, they consider p = p(n), a function approaching zero. In their seminal paper, Erd6s and Renyi [5] showed that for many interesting A there is a function p(n), which they called a threshold function, so that if r(n) < p(n) then f(n, r(n), A) -+ 0 while if p(n) < r(n) then f(n, r(n), A) 1-+ . (Notation: p < r means lim p/r = 0. All limits are as n approaches infinity.) Let us say p = p(n) satisfies the Zero-One Law if for all A in GRA, limf(n, p, A) = 0 or 1. We shall partially characterize those p = p(n) which satisfy the Zero-One Law.