The Structure of Hereditary Properties and Colourings of Random Graphs
The Structure of Hereditary Properties and Colourings of Random Graphs
复制标题
遗传属性的结构和随机图的着色
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
A. Thomason
中科院分区：
文献类型：
--
作者：
B. Bollobás;A. Thomason
在概率空间？第二，是否存在一个常数使得随机图的全色数几乎必定是？第二个问题是Scheinerman提出的（SIAM J. Discrete Math.5（1992）74-80），这两个问题密切相关，在p=1/2的情况下，已经有了答案。Prömel和Steger（Contemporary Mathematics 147，Amer. Math. Soc.，普罗维登斯，1993年，第100页。167-178）、Alekseev（Discrete Math.Appl.3（1993）191-199）和作者（Algorithms and Combinatorics 14 Springer-Verlag（1997）70-78）提供了一种近似，作者（Random Structures and Algorithms 6（1995）353-356）使用该近似来回答p=1/2的半色性问题。然而，近似的性能，以及工作p=1/2完全失败。在本文中，我们描述了一类的属性，近似，在以下意义上：对于任何所需的精度近似，有一个属性在我们的类，近似到这个水平的准确性。正如所料，我们的类包括在p=1/2的情况下使用的简单性质。在回答我们的两个问题中的第二个问题，即关于的-色数的主要困难是，在小-图的数目，一般来说，大的变化。如果我们用一个简单的近似值来代替，方差会更小，但它仍然不够小。我们克服了这一点，而不是考虑一个非常严格的非遗传子属性的近似属性;方差的小图的数量是足够小的，我们的目的，和结构的充分限制，使我们能够显示这一点的一个很好的分析。
in the probability space ? Second, does there exist a constant such that the -chromatic number of the random graph is almost surely ? The second question was posed by Scheinerman (SIAM J. Discrete Math.5 (1992) 74–80).The two questions are closely related and, in the case p=1/2, have already been answered. Prömel and Steger (Contemporary Mathematics147, Amer. Math. Soc., Providence, 1993, pp. 167-178), Alekseev (Discrete Math. Appl.3 (1993) 191-199) and the authors ( Algorithms and Combinatorics14 Springer-Verlag (1997) 70–78) provided an approximation which was used by the authors (Random Structures and Algorithms6 (1995) 353–356) to answer the -chromatic question for p=1/2. However, the approximating properties that work well for p=1/2 fail completely for .In this paper we describe a class of properties that do approximate in , in the following sense: for any desired accuracy of approximation, there is a property in our class that approximates to this level of accuracy. As may be expected, our class includes the simple properties used in the case p=1/2.The main difficulty in answering the second of our two questions, that concerning the -chromatic number of , is that the number of small -graphs in has, in general, large variance. The variance is smaller if we replace by a simple approximation, but it is still not small enough. We overcome this by considering instead a very rigid non-hereditary subproperty of the approximating property; the variance of the number of small -graphs is small enough for our purpose, and the structure of is sufficiently restricted to enable us to show this by a fine analysis.