Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

$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), 637-671 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 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
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
  • © Copyright 1987 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 303 (1987), 637-671
  • MSC: Primary 05C15; Secondary 03C13
  • DOI: https://doi.org/10.1090/S0002-9947-1987-0902790-6
  • MathSciNet review: 902790