Regularity lemmas for stable graphs

DOI10.1090/S0002-9947-2013-05820-5MaRDI QIDQ5401732zbMATH OpenWikidataFDO

Authors S. Shelah, M. Malliaris

Publication date 12 March 2014

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

Szemerédi's regularity lemmaSzemerédi theorySzemerédi-type partition theorems

Mathematics Subject Classification ID

Classification theory, stability, and related concepts in model theory (03C45) Structural characterization of families of graphs (05C75) Applications of model theory (03C98)

Abstract: Let G be a finite graph with the non-k-order property (essentially, a uniform finite bound on the size of an induced sub-half-graph). A major result of the paper applies model-theoretic arguments to obtain a stronger version of Szemer'edi's regularity lemma for such graphs, Theorem 5.18, in which there are no irregular pairs, the bounds are significantly improved, and each component satisfies an indivisibility condition. Motivation for this work comes from a coincidence of model-theoretic and graph-theoretic ideas. Namely, it was known that the "irregular pairs" in the statement of Szemer'edi's regularity lemma cannot be eliminated, due to the counterexample of half-graphs. The results of this paper show in what sense this counterexample is the only essential difficulty. The proof is largely model-theoretic (though written to be accessible to finite combinatorialists): arbitrarily large half-graphs coincide with model-theoretic instability, so in their absence, structure theorems and technology from stability theory apply. In addition to the theorem quoted, we give several other regularity lemmas with different advantages, in which the indivisibility condition on the components is improved (at the expense of letting the number of components grow with |G|) and extend some of these results to the larger class of graphs without the independence property.

Recommendations

• The stable regularity lemma revisited
• Regularity lemma for distal structures
• Can a Graph Have Distinct Regular Partitions?
• Bounds for graph regularity and removal lemmas
• Can a graph have distinct regular partitions?

Cites work

• scientific article; zbMATH DE number 3126031 (Why is no real title available?)
• scientific article; zbMATH DE number 3141601 (Why is no real title available?)
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 2113455 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• Classification theory for abstract elementary classes
• Edge distribution and density in the characteristic sequence
• Examples in dependent theories
• Groups, measures, and the NIP
• Hypergraph sequences as a tool for saturation of ultrapowers
• Lower bounds of tower type for Szemerédi's uniformity lemma
• On sets of integers containing k elements in arithmetic progression
• On the Normal Approximation to the Hypergeometric Distribution
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Regularity partitions and the topology of graphons
• The Algorithmic Aspects of the Regularity Lemma
• The characteristic sequence of a first-order formula
• Vapnik-Chervonenkis Classes of Definable Sets

Cited in

(41)

• On partial cubes, well-graded families and their duals with some applications in graphs
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• Quantitative structure of stable sets in arbitrary finite groups
• Regular partitions of gentle graphs
• On 3‐graphs with no four vertices spanning exactly two edges
• Semantic limits of dense combinatorial objects
• Quantitative structure of stable sets in finite abelian groups
• Discrete metric spaces: structure, enumeration, and 0-1 laws
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• A group version of stable regularity
• On the complexity of finite subgraphs of the curve graph
• Structure and regularity for subsets of groups with finite VC-dimension
• Ramsey properties of algebraic graphs and hypergraphs
• Definable regularity lemmas for NIP hypergraphs
• Keisler's order is not simple (and simple theories may not be either)
• On regular-stable graphs
• Stable formulas in ordered structures
• Graphons arising from graphs definable over finite fields
• Erdös-Hajnal properties for powers of sparse graphs
• A note on the Erdős-Hajnal property for stable graphs
• The stable regularity lemma revisited
• Formalising Szemerédi's Regularity Lemma and Roth's Theorem on Arithmetic Progressions in Isabelle/HOL
• Minimum degree and the graph removal lemma
• Transducing paths in graph classes with unbounded shrubdepth
• On Vapnik‐Chervonenkis density over indiscernible sequences
• DOMINATION AND REGULARITY
• Algorithmic properties of sparse digraphs
• Infinite stable graphs with large chromatic number. II
• Model theory and agnostic online learning via excellent sets
• Infinite stable graphs with large chromatic number
• Combinatorics and algorithms for quasi-chain graphs
• Combinatorics and algorithms for quasi-chain graphs
• On finite sets of small tripling or small alternation in arbitrary groups
• A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
• Bounds for graph regularity and removal lemmas
• Ramsey growth in some NIP structures
• MODEL THEORY AND COMBINATORICS OF BANNED SEQUENCES
• Bounds on half graph orders in powers of sparse graphs
• NOTES ON THE STABLE REGULARITY LEMMA
• Regularity lemma for distal structures
• Continuous stable regularity

This page was built for publication: Regularity lemmas for stable graphs

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