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.


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


[1] Probabilities on finite models 41 pp 50– (1976)
[2] Kibernetyka 2 pp 17– (1969)
[3] Finite model theory (1999)
[4] Graph theory (2005)
[5] DOI: 10.1016/0890-5401(88)90032-6 · Zbl 0665.03028
[6] DOI: 10.1016/0001-8708(87)90019-3 · Zbl 0646.60012
[7] Number theoretic density and logical limit laws 86 (2001)
[8] DOI: 10.1016/j.jctb.2010.11.001 · Zbl 1239.05098
[9] DOI: 10.1002/rsa.20242 · Zbl 1227.05216
[10] The strange logic of random graphs 22 (2001) · Zbl 0976.05001
[11] DOI: 10.1090/S0894-0347-1988-0924703-8
[12] DOI: 10.1007/BF01305238 · Zbl 0770.05063
[13] DOI: 10.1145/1094622.1094627 · Zbl 1367.03064
[14] Discrete Mathematics and Theoretical Computer Science 14 pp 229– (2012)
[15] DOI: 10.1016/j.apal.2011.12.001 · Zbl 1257.03057
[16] Transactions of the American Mathematical Society 303 pp 637– (1987)
[17] DOI: 10.1017/S0963548300000833 · Zbl 0793.05087
[18] DOI: 10.4310/JOC.2010.v1.n4.a3 · Zbl 1244.05202
[19] 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.