$K_ {l+1}$free graphs: asymptotic structure and a $0$$1$ law
HTML articles powered by AMS MathViewer
 by Ph. G. Kolaitis, H. J. Prömel and B. L. Rothschild PDF
 Trans. Amer. Math. Soc. 303 (1987), 637671 Request permission
Abstract:
The structure of labeled ${K_{l + 1}}$free graphs is investigated asymptotically. Through a series of stages of successive refinement the structure of "almost all" such graphs is found sufficiently precisely to prove that they are in fact $l$colorable ($l$partite). With the asymptotic information obtained it is shown also that in the class of ${K_{l + 1}}$free graphs there is a firstorder labeled $0$$1$ law. With this result, and those cases already known, we can say that any infinite class of finite undirected graphs with amalgamations, induced subgraphs and isomorphisms has a $0$$1$ law.References

B. Bollobás [1980], Extremal graph theory, Academic Press, New York, 1980.
 Béla Bollobás and Paul Erdős, On the structure of edge graphs, Bull. London Math. Soc. 5 (1973), 317–321. MR 335347, DOI 10.1112/blms/5.3.317
 Kevin J. Compton, A logical approach to asymptotic combinatorics. I. First order properties, Adv. in Math. 65 (1987), no. 1, 65–96. MR 893471, DOI 10.1016/00018708(87)900193 P. Erdös, D. J. Kleitman and B. L. Rothschild [1976], Asymptotic enumeration of ${K_n}$free graphs, International Colloquium on Combinatorial Theory, Atti dei Convegni Lincei 17, Vol. 2, Rome, 1976, pp. 1927.
 Ronald Fagin, Probabilities on finite models, J. Symbolic Logic 41 (1976), no. 1, 50–58. MR 476480, DOI 10.2307/2272945
 Roland Fraïssé, Sur l’extension aux relations de quelques propriétés des ordres, Ann. Sci. Ecole Norm. Sup. (3) 71 (1954), 363–388 (French). MR 0069239, DOI 10.24033/asens.1027
 C. Ward Henson, A family of countable homogeneous graphs, Pacific J. Math. 38 (1971), 69–83. MR 304242, DOI 10.2140/pjm.1971.38.69
 C. Ward Henson, Countable homogeneous relational structures and $\aleph _{0}$categorical theories, J. Symbolic Logic 37 (1972), 494–500. MR 321727, DOI 10.2307/2272734 Ch. Jordan [1939], Calculus of finite differences, Rottig and Romwalters, Budapest Sopron, Hungary, 1939.
 D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc. 205 (1975), 205–220. MR 369090, DOI 10.1090/S00029947197503690909
 Ph. G. Kolaitis, H. J. Prömel, and B. L. Rothschild, Asymptotic enumeration and a $0$$1$ law for $m$clique free graphs, Bull. Amer. Math. Soc. (N.S.) 13 (1985), no. 2, 160–162. MR 799802, DOI 10.1090/S027309791985154035
 A. H. Lachlan and Robert E. Woodrow, Countable ultrahomogeneous undirected graphs, Trans. Amer. Math. Soc. 262 (1980), no. 1, 51–94. MR 583847, DOI 10.1090/S00029947198005838472
 R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331–340. MR 172268, DOI 10.4064/aa94331340
 Robert E. Woodrow, There are four countable ultrahomogeneous graphs without triangles, J. Combin. Theory Ser. B 27 (1979), no. 2, 168–179. MR 546859, DOI 10.1016/00958956(79)900789
Additional Information
 © Copyright 1987 American Mathematical Society
 Journal: Trans. Amer. Math. Soc. 303 (1987), 637671
 MSC: Primary 05C15; Secondary 03C13
 DOI: https://doi.org/10.1090/S00029947198709027906
 MathSciNet review: 902790