Asymptotic probabilities of extension properties and random \(l\)-colourable structures (Q764265): Difference between revisions

Let \(\mathbf K = \bigcup_n \mathbf K_n\) be a class of structures closed under isomorphism and such that for each \(n\), \(\mathbf K_n\) consists of structures of domain \([n] = \{ 1, \ldots, n \}\). One of the major threads in finite model theory is associated with the connection between certain combinatorial properties of \(\mathbf K\) and zero-one laws for first-order logic. (For example, Fraïssé's theorem -- see [\textit{W. Hodges}, Model theory. Cambridge: Cambridge University Press (1993; Zbl 0789.03031)] -- asserts that if \(\mathbf K\) satisfies three combinatorial properties, then the ``almost sure'' set of sentences includes all relevant extension axioms.) This article is a substantial contribution to this thread, introducing a number of combinatorial properties \(\mathbf K\) might satisfy to some effect on zero-one laws for extension axioms. Some are variants of extant properties, e.g., the disjoint amalgamation property: whenever \(\mathcal B, \mathcal C \in \mathbf K\) have as their intersection a structure in \(\mathbf K\), then they are substructures of some \(\mathcal D \in \mathbf K\). A family of these properties concern taking a structure \(\mathcal M \in \mathbf K\) and replacing a substructure \(\mathcal A \subseteq \mathcal M\) with another structure \(\mathcal B\) of the same domain as \(\mathcal A\); denote the structure resulting from this substitution by \(\mathcal M [ \mathcal A \vartriangleright \mathcal B ]\). For example, if we call a structure \textit{represented} if it is isomorphic to a structure of \(\mathbf K\), then say that \(\mathbf K\) \textit{admits the substitution} \([ \mathcal A \vartriangleright \mathcal B ]\) if making that substitution (if possible) in any represented structure results in a represented structure. In this article, the extension axioms are of interest in themselves, and several results have a format similar to the following. Suppose that \(\mathbf K\) satisfies a property \(P\), and consider a property \((*)\). If \(\mathbf K\) also satisfies \((*)\), then the conjunction of the extension axioms holds almost surely on \(\mathbf K\); on the other hand, if \(\mathbf K\) does not satisfy \((*)\), then the proportion of structures in \(\mathbf K_n\) satisfying this conjunction is bounded away from \(1\) as \(n \to \infty\). To give the flavor, consider part of one dichotomy appearing in this article; in this example, call a structure \textit{permitted} if it is a substructure of a structure of \(\mathbf K\). One result in this article is that if \(\mathbf K\) is hereditary (i.e., closed under finitely generated substructures), satisfies the joint amalgamation property, and there exist permitted \(\mathcal A\), \(\mathcal B\), and \(\mathcal M\) such that \([ \mathcal A \vartriangleright \mathcal B ]\) is admitted but \(\mathcal M [ \mathcal B \vartriangleright \mathcal A ]\) is not permitted, then the proportion of \(\mathbf K_n\) structures satisfying the conjunction of the relevant extension axioms is bounded away from \(1\) as \(n \to \infty\). The article is essentially an organized array of tests of (conjunctions of) reasonable properties of sets of structures, determining which result in almost sure theories of relevant extension axioms, and which do not. It is organized around pregeometries so that, while relational structures are the simplest examples, the results also pertain to structures with constants and functions, and thus nontrivial closure properties. The results were developed for uniform distributions on the classes \(\mathbf K_n\), and for ``uniformly conditional probability measures'' which permit the construction of some very uniform-like distributions. The article starts with very helpful background, but surprisingly for an article this substantial and this long, relies heavily on external references, especially [loc. cit.]; a reader may find it useful to have a copy handy.