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 lemma tower function graph removal lemma weak partition regular approximation theorem strong regularity lemma tower-type bound weak 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

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