Semantic limits of dense combinatorial objects

DOI10.1070/RM9956zbMATH Open1498.03068arXiv1910.08797MaRDI QIDQ5138464FDOQ5138464

Authors: Leonardo Nagami Coregliano, Alexander Razborov 

Publication date: 3 December 2020

Published in: Russian Mathematical Surveys (Search for Journal in Brave)

Abstract: 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 one 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 notable exception of [Ashwini Aroskar and James Cummings. Limits, regularity and removal for finite structures. Technical Report arXiv:1412.2014 [math.LO], arXiv e-print, 2014.]), we base our account on the same concepts from the first-order logic and the model theory as in the theory of flag algebras. We show how our definition naturally encompasses a host of previously considered cases (graphons, hypergraphons, digraphons, permutons, posetons, colored graphs, etc.), and we extend the fundamental properties of existence and uniqueness to this more general case. We also give an intuitive general proof of the continuous version of the Induced Removal Lemma based on the completeness theorem for propositional calculus. We capitalize on the notion of an open interpretation that often allows to transfer methods and results from one situation to another. Again, we show that some previous arguments can be quite naturally framed using this language.

Full work available at URL: https://arxiv.org/abs/1910.08797

Recommendations

• A model theory approach to structural limits.
• First-order limits, an analytical perspective
• Limits of order types
• A measure-theoretic approach to the theory of dense hypergraphs
• Flag algebras

zbMATH Keywords

extremal combinatoricsmodel theorygraph limitsflag algebrasexchangeable arrays

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Combinatorial probability (60C05) Model theory of finite structures (03C13) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Models of other mathematical theories (03C65)

Cites Work

• Limits of dense graph sequences
• Limits of permutation sequences
• Measure theory. Vol. I and II
• Large networks and graph limits
• Title not available (Why is that?)
• Representations for partially exchangeable arrays of random variables
• Graph limits and exchangeable random graphs
• Title not available (Why is that?)
• Flag algebras
• Title not available (Why is that?)
• INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES
• Generalizations of the removal lemma
• Model theory
• Undecidable theories
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Quasi-random graphs
• On the Fon-Der-Flaass interpretation of extremal examples for Turán's \((3,4)\)-problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• A measure-theoretic approach to the theory of dense hypergraphs
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Classification of measurable functions of several variables and invariantly distributed random matrices
• Forbidden paths and cycles in ordered graphs and matrices
• Title not available (Why is that?)
• The random graph
• An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
• Rainbow triangles in three-colored graphs
• Probabilistic Symmetries and Invariance Principles
• Interval graph limits
• Nonlinear large deviations
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Title not available (Why is that?)
• An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions
• Finitely forcible graphons
• Poset limits and exchangeable random posets
• Testability and repair of hereditary hypergraph properties
• Sparse graphs: metrics and random models
• Poset limits can be totally ordered
• Uncountable graphs and invariant measures on the set of universal countable graphs
• On exchangeable random variables and the statistics of large graphs and hypergraphs
• Title not available (Why is that?)
• Threshold graph limits and random threshold graphs
• Undecidability of linear inequalities in graph homomorphism densities
• Symmetries on random arrays and set-indexed processes
• Limits of Boolean functions on \(\mathbb{F}_p^n\)
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• Title not available (Why is that?)
• Quasi-random tournaments
• EXTREMAL THEORY OF ORDERED GRAPHS
• Title not available (Why is that?)
• Metrics for sparse graphs
• Quasi-random graphs and graph limits
• On the statistics of vision: The Julesz conjecture
• Method for construction of (3,4)-graphs
• Regularity lemmas for stable graphs
• Gowers norm, function limits, and parameter estimation
• Ramsey multiplicity of linear patterns in certain finite abelian groups

Cited In (9)

• First and second order signatures of extreme uniform hypergraphs and their relationship with vectors of the vertex degrees
• Enumerative theory for the Tsetlin library
• Natural quasirandomness properties
• The cut metric for probability distributions
• On the abstract chromatic number and its computability for finitely axiomatizable theories
• Limits of order types
• Upper Bound for the Number of Concepts of Contranominal-Scale Free Contexts
• A model theory approach to structural limits.
• Concentration estimates for functions of finite high‐dimensional random arrays

This page was built for publication: Semantic limits of dense combinatorial objects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138464)