ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

13. Combinatorics

1991 MS Classification: 05C Bollobás, Béla, University of Memphis, USA, and University of Cambridge, England Hereditary properties of graphs: asymptotic enumeration, global structure, and colouring

We shall study the asymptotic behaviour of rather general properties of graphs. The basic questions we address are simply how many graphs there are with a given property, and what the structure of a typical graph is with that property. Under the mild assumption that the property is hereditary, significant progress has been made in recent years towards answering these questions. A property of graphs is an infinite class of graphs closed under isomorphism. A natural measure of the size of a property P is the sequence (c_{n}) = (c_{n}(P)) defined by |P^{n}| = 2^{c_{n}\binom{n}{2}}, where P^{n} is the set of graphs in P with vertex set [n] = {1, 2, …, n}. What can one say about the sequence (c_{n}(P)) for various classes of properties? More generally, what can one say about the probability ℙ_{n,p}(P) that a random graph G_{n,p} ∈ G(n, p) belongs to P? In order to study this probability, define (d_{n,p}) by ℙ_{n,p}(P) = 2^{−d_{n,p}\binom{n}{2}}. If p = 1/2, so that G(n, p) is the set of all 2^{\binom{n}{2}} graphs on [n] with the uniform distribution, then ℙ_{n,1/2}(P) = 2^{(c_{n}−1)\binom{n}{2}}, that is, d_{n,1/2} = 1 − c_{n}. Ideally, one would like to find precise approximations of c_{n} and d_{n,p} in terms of simple characteristics of P; better still, one would like to achieve this by finding a property P_{0} that is easily described and approximates P in the sense that P_{0} ⊂ P and the probability of P_{0}^{n} is almost as large as that of P^{n}. For example, as shown by Erdős, Kleitman and Rothschild, in the uniform case G(n, 1/2), the class T of triangle-free graphs can be approximated by the class B of bipartite graphs: B ⊂ T and |B^{n}|/|T^{n}| → 1, so that c_{n}(T ) = \frac{1}{2} + \frac{5}{2n} + O(\frac{log n}{n^{2}}). Kolaitis, Prömel and Rothschild extended this result to the properties of being K_{r+1}-free and r-partite. For a general property P, nothing of interest can be said about the sequences (c_{n}) and (d_{n,p}). However, for the rather large and important class of hereditary properties, it was shown by Alekseev, and by Thomason and the author (continuing earlier work of Prömel, Steger, and others) that (c_{n}) is monotonically decreasing and so converges. A property P is said to be hereditary if it is invariant under the deletion of vertices: if a graph G is in P then every induced subgraph of G is in P. For a family F = {F_{1}, F_{2}, … } of graphs, the class Her(F) consisting of all graphs that contain no F_{i} as an induced subgraph is a hereditary property, and every hereditary property is of this form. In order to find an approximation of a hereditary property P by a simple property and thereby describe c(P) = lim_{n→∞} c_{n}(P) in terms of easily determined characteristics of P, define an (r, s)-colouring of a graph H as a colouring of the vertices of H with colours 1, 2, …, r, such that two vertices of colour i are adjacent if and only if i ≤ s. Denote by P_{r,s} the hereditary property of all (r, s)-colourable graphs, and define the colouring number r(P) of a hereditary property P as

r(P) = max{r : there exists s ∈ {0, 1, …, r} such that P_{r,s} ⊂ P}.

The colouring number r(P) is finite unless P is the trivial property of all graphs, and it is immediate that c(P_{r,s}) = r(P_{r,s}) = 1 − 1/r. If P is a nontrivial property with colouring number r = r(P), and P_{r,s} ⊂ P then P_{r,s} is precisely the desired approximation of P:

c(P) = c(P_{r,s}) = 1 − 1/r.

Given a hereditary property P, the P-chromatic number χ_{P}(G) of a graph G is the minimal integer k for which the vertex set of G has a partition into k parts such that each part spans a graph which belongs to P. Thus if P consists of all graphs with no edges then χ_{P}(G) is just the usual chromatic number χ(G). It has been known for ten years that, for every 0 < p < 1, almost every random graph G_{n,p} has chromatic number (k_{p} + o(1))n/ log n, where k_{p} = − log(1−p)/2, and in 1995 this was extended to the P-chromatic number of random graphs for an arbitrary hereditary property P, but only for the case p = 1/2. For p ≠ 1/2 the picture is much more intricate. For a hereditary property P and a fixed probability 0 < p < 1, the sequence (d_{n,p}(P)) is also monotonic, so tends to a limit d_{p}(P). Although for p ≠ 1/2 we cannot find an easily described property approximating P, nevertheless we can find a sequence of properties P_{j} ⊂ P with d_{p}(P_{j}) → d_{p}(P). This approximation can be used to prove rather sharp results about the P-chromatic number of a random graph G_{n,p}, for all constant values of p. The new results are joint work with Andrew Thomason; for related results, see his poster entitled Hereditary hypergraph properties.

References: V. E. Alekseev, On the entropy values of hereditary classes of graphs, Discrete Math. Appl. 3 (1993), 191–199. B. Bollobás, The chromatic number of random graphs, Combinatorica 8 (1988) 49–55. B. Bollobás and A. Thomason, Hereditary and monotone properties of graphs, in “The Mathematics of Paul Erdős II” (R. L. Graham and J. Nešetřil, eds.) Algorithms and Combinatorics 14 Springer-Verlag (1997) 70–78.

B. Bollobás and A. Thomason, Generalized chromatic numbers of random graphs, Random Structures and Algorithms 6 (1995) 353–356. P. Erdős, P. Frankl and V. Rödl, The asymptotic enumeration of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs and Combinatorics 2 (1986), 113–121. P. Erdős, D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of K_{n}-free graphs, in International Colloquium on Combinatorial Theory, Atti dei Convegni Lincei 17, Vol. 2, Rome, 1976, pp. 19–27. Ph. G. Kolaitis, H. J. Prömel and B. L. Rothschild, K_{l+1}-free graphs: asymptotic structure and a 0-1-law, Trans. Amer. Math. Soc. 303 (1987) 637–671. H. J. Prömel and A. Steger, The asymptotic structure of H-free graphs, in Graph Structure Theory (N. Robertson and P. Seymour, eds), Contemporary Mathematics 147, Amer. Math. Soc. , Providence, 1993, pp. 167–178.