When does the zero-one law hold?
When does the zero-one law hold?
复制标题
零一定律什么时候成立？
DOI：
--
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
J. Spencer
中科院分区：
文献类型：
--
作者：
T. Luczak;J. Spencer
在1960年保罗Erdbs和阿尔弗雷德Renyi [ER]开始的主题随机图。1985年的书贝拉Bollobas [B]提供了这个领域的标准参考。在现代术语中，随机图G（n，p）是顶点集[n] = { 1，.，n}，其中每对顶点i，j以独立概率p相邻。更准确地说，G（n，p）是顶点集[n]上的图空间上的概率空间。对于图的任何性质A，存在一个概率，记为Pr[G（n，p）1 = A]，G（n，p）满足A. Erd 6s和Renyi在他们的标题《论随机图的演化》中设想了一个动态过程，G（n，p）随着p从0到1的变化而改变特征。他们发现（和他们的许多后继者一样），对于许多自然性质，A Pr[G（n，p）t= A]通常接近于零或接近于一，并且在很窄的范围内从零跳到一（或再跳回来）。p的这个临界范围的位置取决于n。例如，设A是包含三角形的属性。有（n）n3 /6 3个潜在的三角形，每个三角形都是G（n，p）中概率为p 3的三角形，因此G（n，p）中三角形的期望数量渐近为n3 p3/6。这表明临界范围p = 8（1/n）。事实上，Erdos和Renyi证明，如果p = p（n）l/n，则limn gc*Pr[G（n，p）l= A] = 1。（记法：f（n）g（n）表示limn-，oo f（n）/g（n）= +ox。）他们称p（n）= l/n为该性质A的阈值函数。作为其他示例，连通性具有阈值函数（logn）/n，包含四个点上的团具有阈值函数n 2/3，包含边具有（容易！）阈值函数n 2，并且位于三角形中的每个顶点具有阈值函数（log n）13 n 23。这是观察阈值函数似乎是形式（log n）n fl与a，f，合理的动机，我们目前的研究路线。关于性质A的可能的阈值函数，我们能说些什么呢？如果我们对A不加限制的话，就不多了。例如，边的数量是偶数的属性不显示阈值函数行为。如果我们限制
In 1960 Paul Erdbs and Alfred Renyi [ER] began the subject of random graphs. The 1985 book of Bela Bollobas [B] provides the standard reference for this field. In modem terminology the random graph G(n, p) is a graph on vertex set [n] = { 1, ... , n} where each pair i, j of vertices are adjacent with independent probability p. More accurately, G(n, p) is a probability space over the space of graphs on vertex set [n]. For any property A of graphs there is a probability, denoted Pr[G(n, p) l= A], that G(n, p) satisfies A. In their very title, "On the evolution of random graphs," Erd6s and Renyi envisioned a dynamic process, G(n, p) changing character as p moved from zero to one. They discovered (as did their many successors) that for many natural properties A Pr[G(n, p) t= A] was usually near zero or near one and made the jump from near zero to near one (or back again) in a very narrow range. The placement of this critical range of p depended on n. For example, let A be the property of containing a triangle. There are (n) n3 /6 3 potential triangles, each is a triangle in G(n, p) with probability p 3, and so the expected number of triangles in G(n, p) is asymptotically n3p3/6. This suggests the critical range p = 8(1/n). Indeed, Erdos and Renyi proved that if p = p(n) l/n then limn gc*Pr[G(n,p) l= A] = 1. (Notation: f(n) g(n) means limn-,oo f(n)/g(n) = +ox.) They called p(n) = l/n a threshold function for this property A. As other examples, connectivity has threshold function (logn)/n, containing a clique on four points has threshold function n 2/3, containing an edge has (easily!) threshold function n 2, and every vertex lying in a triangle has threshold function (log n) 13n 23. It was the observation that threshold functions seemed to be of the form (log n)n fl with a, f, rational that motivated our current line of research. What can we say about the possible threshold functions of properties A ? Not much if we place no restrictions on A. For example, the property that the number of edges is even shows no threshold function behavior. If we restrict