Semantic limits of dense combinatorial objects
From MaRDI portal
Publication:5138464
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)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5942358 (Why is no real title available?)
- scientific article; zbMATH DE number 4200246 (Why is no real title available?)
- scientific article; zbMATH DE number 3896009 (Why is no real title available?)
- scientific article; zbMATH DE number 4027516 (Why is no real title available?)
- scientific article; zbMATH DE number 3678157 (Why is no real title available?)
- scientific article; zbMATH DE number 3630786 (Why is no real title available?)
- scientific article; zbMATH DE number 1215499 (Why is no real title available?)
- scientific article; zbMATH DE number 1022519 (Why is no real title available?)
- scientific article; zbMATH DE number 1024386 (Why is no real title available?)
- scientific article; zbMATH DE number 3248792 (Why is no real title available?)
- scientific article; zbMATH DE number 2209719 (Why is no real title available?)
- A measure-theoretic approach to the theory of dense hypergraphs
- An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
- An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
- Classification of measurable functions of several variables and invariantly distributed random matrices
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- EXTREMAL THEORY OF ORDERED GRAPHS
- Finitely forcible graphons
- Flag algebras
- Forbidden paths and cycles in ordered graphs and matrices
- Generalizations of the removal lemma
- Gowers norm, function limits, and parameter estimation
- Graph limits and exchangeable random graphs
- INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES
- Interval graph limits
- Large networks and graph limits
- Limits of Boolean functions on \(\mathbb{F}_p^n\)
- Limits of dense graph sequences
- Limits of permutation sequences
- Measure theory. Vol. I and II
- Method for construction of (3,4)-graphs
- Metrics for sparse graphs
- Model theory
- Nonlinear large deviations
- On exchangeable random variables and the statistics of large graphs and hypergraphs
- On the Fon-Der-Flaass interpretation of extremal examples for Turán's \((3,4)\)-problem
- On the statistics of vision: The Julesz conjecture
- Poset limits and exchangeable random posets
- Poset limits can be totally ordered
- Probabilistic Symmetries and Invariance Principles
- Quasi-random graphs
- Quasi-random graphs and graph limits
- Quasi-random tournaments
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- Rainbow triangles in three-colored graphs
- Ramsey multiplicity of linear patterns in certain finite abelian groups
- Regularity lemmas for stable graphs
- Representations for partially exchangeable arrays of random variables
- Sparse graphs: metrics and random models
- Symmetries on random arrays and set-indexed processes
- Testability and repair of hereditary hypergraph properties
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- The random graph
- Threshold graph limits and random threshold graphs
- Uncountable graphs and invariant measures on the set of universal countable graphs
- Undecidability of linear inequalities in graph homomorphism densities
- Undecidable theories
- Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
Cited in
(10)- First and second order signatures of extreme uniform hypergraphs and their relationship with vectors of the vertex degrees
- A duality theoretic view on limits of finite structures
- 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)
