The Structure of Hereditary Properties and Colourings of Random Graphs |
| |
Authors: | Béla Bollobás Andrew Thomason |
| |
Institution: | (1) Department of Mathematical Sciences, University of Memphis; Memphis TN 38152, USA and Trinity College; Cambridge, England; E-mail: bollobas@msci.memphis.edu and b.bollobas@dpmms.cam.ac.uk, US;(2) Department of Pure Mathematics and Mathematical Statistics; 16, Mill Lane, Cambridge CB2 1SB, England; E-mail: a.g.thomason@dpmms.cam.ac.uk, UK |
| |
Abstract: | 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 Mathematics
147, Amer. Math. Soc., Providence, 1993, pp. 167-178), Alekseev (Discrete Math. Appl.
3 (1993) 191-199) and the authors ( Algorithms and Combinatorics
14 Springer-Verlag (1997) 70–78) provided an approximation which was used by the authors (Random Structures and Algorithms
6 (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.
Received April 20, 1999 |
| |
Keywords: | AMS Subject Classification (1991) Classes: 05C80 05C75 05C15 |
本文献已被 SpringerLink 等数据库收录! |
|