Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

$ K\sb {l+1}$-free graphs: asymptotic structure and a 0-$ 1$ law


Authors: Ph. G. Kolaitis, H. J. Prömel and B. L. Rothschild
Journal: Trans. Amer. Math. Soc. 303 (1987), 637-671
MSC: Primary 05C15; Secondary 03C13
MathSciNet review: 902790
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 first-order 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 [Enhancements On Off] (What's this?)

  • [1] B. Bollobás [1980], Extremal graph theory, Academic Press, New York, 1980.
  • [2] B. Bollobás and P. Erdös [1973]; On the structure of edge graphs, Bull. London Math. Soc. 5 (1973), 317-321. MR 0335347 (49:129)
  • [3] K. J. Compton [1984], A logical approach to asymptotic combinatorics I: First-order properties, Adv. in Math. (to appear). MR 893471 (88k:03065)
  • [4] 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. 19-27.
  • [5] R. Fagin [1976], Probabilities on finite models, J. Symbolic Logic 41 (1976), 50-58. MR 0476480 (57:16042)
  • [6] R. Fraissé [1954], Sur l'extension aux relations des quelques propriétés des orders, Ann. Sci. Ecole Norm. Sup. 71 (1954), 361-388. MR 0069239 (16:1006b)
  • [7] C. W. Henson [1971], A family of countable homogeneous graphs, Pacific J. Math. 38 (1971), 69-83. MR 0304242 (46:3377)
  • [8] C. W. Henson [1972], Countable homogeneous relational structure and $ {\aleph _0}$-categorical theories, J. Symbolic Logic 37 (1972), 494-500. MR 0321727 (48:94)
  • [9] Ch. Jordan [1939], Calculus of finite differences, Rottig and Romwalters, Budapest Sopron, Hungary, 1939.
  • [10] D. J. Kleitman and B. L. Rothschild [1975], Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc. 205 (1975), 205-220. MR 0369090 (51:5326)
  • [11] Ph. G. Kolaitis, H.-J. Prömel and B. L. Rothschild [1985], Asymptotic enumeration and a 0-$ 1$ law for $ m$-clique free graphs, Bull. Amer. Math. Soc. 13 (1985), 160-162. MR 799802 (87c:05068)
  • [12] A. H. Lachlan and R. E. Woodrow [1980], Countable ultrahomogeneous undirected graphs, Trans. Amer. Math. Soc. 262 (1980), 51-94. MR 583847 (82c:05083)
  • [13] R. Rado [1964], Universal graphs and universal functions, Acta Arith. 9 (1964), 331-340. MR 0172268 (30:2488)
  • [14] R. E. Woodrow [1976], There are four countable ultrahomogeneous graphs without triangles, J. Combin. Theory B 27 (1979), 168-179. MR 546859 (81f:05141)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C15, 03C13

Retrieve articles in all journals with MSC: 05C15, 03C13


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1987-0902790-6
PII: S 0002-9947(1987)0902790-6
Article copyright: © Copyright 1987 American Mathematical Society