Regularity lemmas for stable graphs
From MaRDI portal
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
Cites work
- Classification theory for abstract elementary classes
- Edge distribution and density in the characteristic sequence
- Examples in dependent theories
- Groups, measures, and the NIP
- 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?)
- 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
(53)- On the complexity of finite subgraphs of the curve graph
- Bounds for graph regularity and removal lemmas
- Regularity lemma for distal structures
- A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
- Structure and regularity for subsets of groups with finite VC-dimension
- On partial cubes, well-graded families and their duals with some applications in graphs
- Regular partitions of gentle graphs
- Keisler's order is not simple (and simple theories may not be either)
- Bounds on half graph orders in powers of sparse graphs
- The stable regularity lemma revisited
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- On regular-stable graphs
- A note on the Erdős-Hajnal property for stable graphs
- scientific article; zbMATH DE number 878896 (Why is no real title available?)
- On finite sets of small tripling or small alternation in arbitrary groups
- Quantitative structure of stable sets in arbitrary finite groups
- Definable regularity lemmas for NIP hypergraphs
- Infinite stable graphs with large chromatic number
- NOTES ON THE STABLE REGULARITY LEMMA
- Ramsey properties of algebraic graphs and hypergraphs
- MODEL THEORY AND COMBINATORICS OF BANNED SEQUENCES
- Graphons arising from graphs definable over finite fields
- Algorithmic properties of sparse digraphs
- Quantitative structure of stable sets in finite abelian groups
- Semantic limits of dense combinatorial objects
- Ramsey growth in some NIP structures
- Discrete metric spaces: structure, enumeration, and 0-1 laws
- A group version of stable regularity
- On Vapnik‐Chervonenkis density over indiscernible sequences
- Erdös-Hajnal properties for powers of sparse graphs
- DOMINATION AND REGULARITY
- Combinatorics and algorithms for quasi-chain graphs
- Combinatorics and algorithms for quasi-chain graphs
- On 3‐graphs with no four vertices spanning exactly two edges
- Minimum degree and the graph removal lemma
- Stable formulas in ordered structures
- Continuous stable regularity
- Formalising Szemerédi's Regularity Lemma and Roth's Theorem on Arithmetic Progressions in Isabelle/HOL
- Transducing paths in graph classes with unbounded shrubdepth
- Infinite stable graphs with large chromatic number. II
- Model theory and agnostic online learning via excellent sets
- Zarankiewicz bounds from distal regularity lemma
- Mekler's construction and Murphy's law for 2-nilpotent groups
- A note on Erdős-Hajnal property for graphs with VC dimension 2
- A polynomial Ramsey statement for bounded VC-dimension
- Induced subgraph density. VI: Bounded VC-dimension
- Randomized communication and implicit graph representations
- The unstable formula theorem revisited via algorithms
- Decomposition horizons and a characterization of stable hereditary classes of graphs
- A structure theorem for pseudosegments and its applications
- Higher arity stability and the functional order property
- Planar graphs with separation are dp-minimal
- Advances in algorithmic meta theorems (invited paper)
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)
