Semantic limits of dense combinatorial objects

L. N. Coregliano ; A. A. Razborov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 75 (2020) no. 4, pp. 627-723

Résumé

The theory of limits of discrete combinatorial objects has been thriving for the last decade or so. The syntactic, algebraic approach to the subject is popularly known as ‘flag algebras’, while the semantic, geometric approach is often associated with the name ‘graph limits’. The language of graph limits is generally more intuitive and expressible, but a price that one has to pay for it is that it is better suited for the case of ordinary graphs than for more general combinatorial objects. Accordingly, there have been several attempts in the literature, of varying degree of generality, to define limit objects for more complicated combinatorial structures. This paper is another attempt at a workable general theory of dense limit objects. Unlike previous efforts in this direction (with the notable exception of [5] by Aroskar and Cummings), our account is based on the same concepts from first-order logic and model theory as in the theory of flag algebras. It is shown how our definitions naturally encompass a host of previously considered cases (graphons, hypergraphons, digraphons, permutons, posetons, coloured graphs, and so on), and the fundamental properties of existence and uniqueness are extended to this more general case. Also given is an intuitive general proof of the continuous version of the Induced Removal Lemma based on the compactness theorem for propositional calculus. Use is made of the notion of open interpretation that often allows one to transfer methods and results from one situation to another. Again, it is shown that some previous arguments can be quite naturally framed using this language. Bibliography: 68 titles.

Détail

Keywords: model theory, graph limits, flag algebras, exchangeable arrays, extremal combinatorics.