𝐾_{𝑙+1}-free graphs: asymptotic structure and a 0-1 law

Kolaitis, Ph. G.; Prömel, H. J.; Rothschild, B. L.

doi:10.1090/S0002-9947-1987-0902790-6

$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

1980

Extremal graph theory

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/0001-8708(87)90019-3

1976

Asymptotic enumeration of

free graphs

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

1939

Calculus of finite differences

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/S0002-9947-1975-0369090-9
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/S0273-0979-1985-15403-5
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/S0002-9947-1980-0583847-2
R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331–340. MR 172268, DOI 10.4064/aa-9-4-331-340
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/0095-8956(79)90078-9