## A limit law of almost $$l$$-partite graphs.(English)Zbl 1325.03033

This article concludes that for any integers $$1 \leq s_1 \leq \cdots \leq s_l$$, if $${\mathcal K} = {\mathcal K}_{1, s_1, \ldots, s_l}$$ is the complete $$(l + 1)$$-partite graph whose parts consist of $$1$$, $$s_1,\dots,s_l$$ vertices, respectively, and if $$\mathbf {Forb}(\mathcal K)$$ is the set of graphs not having $$\mathcal K$$ as a subgraph, then $$\mathbf {Forb}(\mathcal K)$$ has a (labelled) first order limit law.
In order to establish this result, the article further develops the theory of almost $$l$$-partite graphs. Given positive integers $$l$$ and $$d$$, let $$\mathbf P_n (l, d)$$ be the set of $$n$$-vertex graphs that can be partitioned into $$l$$ parts so that each vertex is adjacent to at most $$d$$ vertices in its own part: thus $$\mathbf P_n(l, 0)$$ is the set of $$l$$-partite graphs. The primary result in this paper is that for each positive integer $$l$$, $$\mathbf P(l, 1)$$ admits a (labelled) first order zero-one law, while for each positive integer $$d > 1$$, $$\mathbf P(l, d)$$ admits a first order limit law but also first order properties whose limit is neither $$0$$ nor $$1$$.
The proofs are elementary but technically intricate, and the article is accessible to a reader willing to invest the effort.

### MSC:

 03C13 Model theory of finite structures 05C80 Random graphs (graph-theoretic aspects)
Full Text:

### References:

  Probabilities on finite models 41 pp 50– (1976)  Kibernetyka 2 pp 17– (1969)  Finite model theory (1999)  Graph theory (2005)  DOI: 10.1016/0890-5401(88)90032-6 · Zbl 0665.03028  DOI: 10.1016/0001-8708(87)90019-3 · Zbl 0646.60012  Number theoretic density and logical limit laws 86 (2001)  DOI: 10.1016/j.jctb.2010.11.001 · Zbl 1239.05098  DOI: 10.1002/rsa.20242 · Zbl 1227.05216  The strange logic of random graphs 22 (2001) · Zbl 0976.05001  DOI: 10.1090/S0894-0347-1988-0924703-8  DOI: 10.1007/BF01305238 · Zbl 0770.05063  DOI: 10.1145/1094622.1094627 · Zbl 1367.03064  Discrete Mathematics and Theoretical Computer Science 14 pp 229– (2012)  DOI: 10.1016/j.apal.2011.12.001 · Zbl 1257.03057  Transactions of the American Mathematical Society 303 pp 637– (1987)  DOI: 10.1017/S0963548300000833 · Zbl 0793.05087  DOI: 10.4310/JOC.2010.v1.n4.a3 · Zbl 1244.05202  International Colloquium on Combinatorial Theory 2 pp 19– (1976)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.