A limit law of almost \(l\)-partite graphs (Q2869907)

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.NEWLINENEWLINEIn order to establish this result, the article further develops the theory of \textit{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\).NEWLINENEWLINEThe proofs are elementary but technically intricate, and the article is accessible to a reader willing to invest the effort.