Koponen, Vera Asymptotic probabilities of extension properties and random \(l\)-colourable structures. (English) Zbl 1257.03057 Ann. Pure Appl. Logic 163, No. 4, 391-438 (2012). 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 [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 represented if it is isomorphic to a structure of \(\mathbf K\), then say that \(\mathbf K\) 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 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. Reviewer: Gregory Loren McColm (Tampa) Cited in 7 Documents MSC: 03C13 Model theory of finite structures 60C05 Combinatorial probability 60F20 Zero-one laws 68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) Keywords:asymptotic probability; amalgamation property; colouring; extension axioms; forbidden structures; finite model theory; hereditary property; pregeometry; zero-one law Citations:Zbl 0789.03031 PDFBibTeX XMLCite \textit{V. Koponen}, Ann. Pure Appl. Logic 163, No. 4, 391--438 (2012; Zbl 1257.03057) Full Text: DOI arXiv References: [1] Agnarsson, G.; Halldórsson, M. M., Strong colorings of hypergraphs, (Persiano, G.; Solis-Oba, R., Approximation and Online Algorithms. Approximation and Online Algorithms, Lecture Notes in Computer Science, vol. 3351 (2005), Springer Verlag) · Zbl 1124.05316 [2] Aigner, M., Combinatorial Theory (1997), Springer-Verlag · Zbl 0858.05001 [3] Alon, N.; Balogh, J.; Bollobás, B.; Morris, R., The structure of almost all graphs in a hereditary property, Journal of Combinatorial Theory, Series B, 101, 85-110 (2011) · Zbl 1217.05193 [4] Balogh, J.; Bollobás, B.; Simonovits, M., The typical structure of graphs without given excluded subgraphs, Random Structures and Algorithms, 34, 305-318 (2009) · Zbl 1227.05216 [5] Balogh, J.; Bollobás, B.; Simonovits, M., The fine structure of octahedron-free graphs, Journal of Combinatorial Theory, Series B, 101, 67-84 (2011) · Zbl 1239.05098 [6] Berge, C., Hypergraphs (1989), Elsevier Science Publ. · Zbl 0312.05122 [7] Bollobás, B., Random Graphs (2001), Cambridge University Press · Zbl 0997.05049 [8] Burris, S. N., (Number Theoretic Density and Logical Limit Laws. Number Theoretic Density and Logical Limit Laws, Mathematical Surveys and Monographs, vol. 86 (2001), American Mathematical Society) · Zbl 0995.11001 [9] Burris, S.; Yeats, K., Sufficient conditions for labelled 0-1 laws, Discrete Mathematics & Theoretical Computer Science, 10, 147-156 (2008) · Zbl 1139.03023 [10] Cherlin, G., Combinatorial problems connected with finite homogeneity, Contemporary Mathematics, 131, Part 3, 3-30 (1992) · Zbl 0762.05078 [11] Cherlin, G.; Hrushovski, E., (Finite Structures with Few Types. Finite Structures with Few Types, Annals of Mathematics Studies, vol. 152 (2003), Princeton University Press) · Zbl 1024.03001 [12] Djordjevic, M., On first-order sentences without finite models, The Journal of Symbolic Logic, 69, 329-339 (2004) · Zbl 1081.03029 [13] Djordjević, M., The finite submodel property and \(\omega \)-categorical expansions of pregeometries, Annals of Pure and Applied Logic, 139, 201-229 (2006) · Zbl 1093.03015 [14] Ebbinghaus, H-D.; Flum, J., Finite Model Theory (1999), Springer Verlag [15] Evans, D. M., \( \aleph_0\)-categorical structures with a predimension, Annals of Pure and Applied Logic, 116, 157-186 (2002) · Zbl 1002.03022 [16] P. Erdös, D.J. Kleitman, B.L. Rothschild, Asymptotic enuemeration of \(K_n\); P. Erdös, D.J. Kleitman, B.L. Rothschild, Asymptotic enuemeration of \(K_n\) [17] Fagin, R., Probabilities on finite models, The Journal of Symbolic Logic, 41, 50-58 (1976) · Zbl 0341.02044 [18] Glebskii, Y. V.; Kogan, D. I.; Liogonkii, M. I.; Talanov, V. A., Volume and fraction of satisfiability of formulas of the lower predicate calculus, Kibernetyka, 2, 17-27 (1969) [19] Hadley, G. F., Nonlinear and Dynamic Programming (1964), Addison-Wesley · Zbl 0179.24601 [20] Hardy, G. H.; Littlewood, J. E.; Pólya, G., Inequalities (1934), Cambridge University Press · Zbl 0010.10703 [21] Henson, W., Countable homogeneous relational structures and \(\aleph_0\)-categorical theories, The Journal of Symbolic Logic, 37, 494-500 (1972) · Zbl 0259.02040 [22] Hodges, W., Model Theory (1993), Cambridge University Press [23] E. Hrushovski, Simplicity and the Lascar group, manuscript (2003).; E. Hrushovski, Simplicity and the Lascar group, manuscript (2003). [24] Immerman, N., Upper and lower bounds for first-order expressibility, Journal of Computer and Systems Sciences, 25, 76-98 (1982) · Zbl 0503.68032 [25] Jensen, T. R.; Toft, B., Graph Coloring Problems (1995), Wiley-Interscience · Zbl 0971.05046 [26] Kolaitis, Ph. G.; Prömel, H. J.; Rothschild, B. L., \(K_{l + 1}\)-free graphs: asymptotic structure and a 0-1 law, Transactions of The American Mathematical Society, 303, 637-671 (1987) · Zbl 0641.05025 [27] Maclaurin, C., A second letter to Martin Folkes, Esq.; concerning the roots of equations, with the demonstration of other rules in algebra, Philosophical Transactions, 36, 59-96 (1729) [28] Oberschelp, W., Asymptotic 0-1 laws in combinatorics, (Jungnickel, D., Combinatorial Theory. Combinatorial Theory, Lecture Notes in Mathematics, vol. 969 (1982), Springer Verlag), 276-292 · Zbl 0515.05001 [29] Poizat, B., Deux ou trois choses que je sais de \(L^n\), The Journal of Symbolic Logic, 47, 641-658 (1982) · Zbl 0507.03014 [30] Prömel, H. J.; Steger, A., The asymptotic number of graphs not containing a fixed color-critical subgraph, Combinatorica, 12, 463-473 (1992) · Zbl 0770.05063 [31] Prömel, H. J.; Steger, A., Random \(l\)-colourable graphs, Random Structures and Algorithms, 6, 21-37 (1995) · Zbl 0817.05052 [32] Prömel, H. J.; Steger, A.; Taraz, A., Asymptotic enumeration, global structure, and constrained evolution, Discrete Mathematics, 229, 213-233 (2001) · Zbl 0965.05016 [33] Winkler, P., Random structures and zero-one laws, (Sauer, N. W.; etal., Finite and Infinite Combinatorics in Sets and Logic (1993), Kluwer Academic Publishers), 399-420 · Zbl 0845.05083 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.