Bounds for graph regularity and removal lemmas

DOI10.1007/s00039-012-0171-xzbMath1256.05114arXiv1107.4829OpenAlexW1691611448WikidataQ56675393 ScholiaQ56675393MaRDI QIDQ1930904

Jacob Fox, David Conlon

Publication date: 14 January 2013

Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

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

zbMATH Keywords

Szemerédi's regularity lemmatower functiongraph removal lemmaweak partitionregular approximation theoremstrong regularity lemmatower-type boundweak regularity lemma of Frieze and Kannan

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (49)

Popular progression differences in vector spaces II ⋮ NOTES ON THE STABLE REGULARITY LEMMA ⋮ Finitely forcible graph limits are universal ⋮ Testing graphs against an unknown distribution ⋮ Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ Induced arithmetic removal: complexity 1 patterns over finite fields ⋮ Fast Property Testing and Metrics for Permutations ⋮ Weak regularity and finitely forcible graph limits ⋮ Hereditary quasirandomness without regularity ⋮ Efficient Removal Lemmas for Matrices ⋮ Efficient removal lemmas for matrices ⋮ Erdős-Hajnal conjecture for graphs with bounded VC-dimension ⋮ Tower-type bounds for Roth's theorem with popular differences ⋮ Extremal graph theory and finite forcibility ⋮ Estimating the distance to a hereditary graph property ⋮ A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing ⋮ On partial cubes, well-graded families and their duals with some applications in graphs ⋮ Graphs isomorphisms under edge-replacements and the family of amoebas ⋮ Approximating the Rectilinear Crossing Number ⋮ Some Cubic Time Regularity Algorithms for Triple Systems ⋮ Local-vs-global combinatorics ⋮ An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions ⋮ Easily Testable Graph Properties ⋮ On Regularity Lemmas and their Algorithmic Applications ⋮ Three-color Ramsey number of an odd cycle versus bipartite graphs with small bandwidth ⋮ Finitely forcible graphons with an almost arbitrary structure ⋮ Extremal results in sparse pseudorandom graphs ⋮ Regular partitions of gentle graphs ⋮ Efficient Testing without Efficient Regularity ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ A sparse regular approximation lemma ⋮ Graph summarization with quality guarantees ⋮ Monochromatic bounded degree subgraph partitions ⋮ A short proof of Gowers' lower bound for the regularity lemma ⋮ The critical window for the classical Ramsey-Turán problem ⋮ An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ The Induced Removal Lemma in Sparse Graphs ⋮ An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions ⋮ Graphs with Few 3‐Cliques and 3‐Anticliques are 3‐Universal ⋮ Weak regularity and finitely forcible graph limits ⋮ The Cut Metric for Probability Distributions ⋮ On the Query Complexity of Estimating the Distance to Hereditary Graph Properties ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Estimating parameters associated with monotone properties ⋮ Approximating the rectilinear crossing number ⋮ A tight bound for hypergraph regularity ⋮ Ramsey numbers of books and quasirandomness

Cites Work

• A new proof of the graph removal lemma
• Szemerédi's lemma for the analyst
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Quick approximation to matrices and applications
• Partitioning complete bipartite graphs by monochromatic cycles
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Ramsey numbers for sparse graphs
• Random sampling and approximation of MAX-CSPs
• Property testing and its connection to learning and approximation
• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• The Algorithmic Aspects of the Regularity Lemma
• Testing subgraphs in large graphs
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• Robust Characterizations of Polynomials with Applications to Program Testing
• Regularity Lemmas and Combinatorial Algorithms
• Can a Graph Have Distinct Regular Partitions?
• Probability Inequalities for Sums of Bounded Random Variables
• Regularity lemmas for stable graphs
• Address of the Chairman of the Fields Medal Commitee
• Regular Partitions of Hypergraphs: Regularity Lemmas
• On Certain Sets of Integers
• Quasi-random graphs
• Testing subgraphs in directed graphs
• Efficient testing of large graphs
• Holes in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Bounds for graph regularity and removal lemmas