Regularity lemmas for stable graphs

DOI10.1090/S0002-9947-2013-05820-5zbMath1283.05234arXiv1102.3904WikidataQ105983441 ScholiaQ105983441MaRDI QIDQ5401732

Saharon Shelah, Maryanthe 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

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

Related Items

Structure and regularity for subsets of groups with finite VC-dimension ⋮ Infinite stable graphs with large chromatic number ⋮ NOTES ON THE STABLE REGULARITY LEMMA ⋮ Ramsey properties of algebraic graphs and hypergraphs ⋮ On the complexity of finite subgraphs of the curve graph ⋮ MODEL THEORY AND COMBINATORICS OF BANNED SEQUENCES ⋮ Graphons arising from graphs definable over finite fields ⋮ Bounds for graph regularity and removal lemmas ⋮ On 3‐graphs with no four vertices spanning exactly two edges ⋮ Minimum degree and the graph removal lemma ⋮ On partial cubes, well-graded families and their duals with some applications in graphs ⋮ Stable formulas in ordered structures ⋮ A note on the Erdős-Hajnal property for stable graphs ⋮ Continuous stable regularity ⋮ Formalising Szemerédi's Regularity Lemma and Roth's Theorem on Arithmetic Progressions in Isabelle/HOL ⋮ Quantitative structure of stable sets in finite abelian groups ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Regular partitions of gentle graphs ⋮ Semantic limits of dense combinatorial objects ⋮ RAMSEY GROWTH IN SOME NIP STRUCTURES ⋮ Keisler's order is not simple (and simple theories may not be either) ⋮ On Vapnik‐Chervonenkis density over indiscernible sequences ⋮ Unnamed Item ⋮ The stable regularity lemma revisited ⋮ DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ A group version of stable regularity ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ 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 ⋮ Quantitative structure of stable sets in arbitrary finite groups ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs ⋮ DOMINATION AND REGULARITY

Cites Work

• On the Normal Approximation to the Hypergeometric Distribution
• Edge distribution and density in the characteristic sequence
• Lower bounds of tower type for Szemerédi's uniformity lemma
• EXAMPLES IN DEPENDENT THEORIES
• The characteristic sequence of a first-order formula
• Regularity partitions and the topology of graphons
• Vapnik-Chervonenkis Classes of Definable Sets
• On sets of integers containing k elements in arithmetic progression
• The Algorithmic Aspects of the Regularity Lemma
• Hypergraph sequences as a tool for saturation of ultrapowers
• Groups, measures, and the NIP
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item