A sparse regular approximation lemma

DOI10.1090/TRAN/7414MaRDI QIDQ4633762zbMATH OpenOpenAlexWikidataFDO

Authors Guy Moshkovitz, Asaf Shapira

Publication date 6 May 2019

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

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

zbMATH Keywords

Szemerédi's regularity lemma

Mathematics Subject Classification ID

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

Abstract: We introduce a new variant of Szemer'edi's regularity lemma which we call the "sparse regular approximation lemma" (SRAL). The input to this lemma is a graph $G$ of edge density $p$ and parameters $epsilon,delta$, where we think of $delta$ as a constant. The goal is to construct an $epsilon$-regular partition of $G$ while having the freedom to add/remove up to $delta|E(G)|$ edges. As we show here, this weaker variant of the regularity lemma already suffices for proving the graph removal lemma and the hypergraph regularity lemma, which are two of the main applications of the (standard) regularity lemma. This of course raises the following question: can one obtain quantitative bounds for SRAL that are significantly better than those associated with the regularity lemma? Our first result answers the above question affirmatively by proving an upper bound for SRAL given by a tower of height $O(log1/p)$. This allows us to reprove Fox's upper bound for the graph removal lemma. Our second result is a matching lower bound for SRAL showing that a tower of height $Omega(log1/p)$ is unavoidable. We in fact prove a more general multicolored lower bound which is essential for proving lower bounds for the hypergraph regularity lemma.

Recommendations

• Bounds for graph regularity and removal lemmas
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Extremal results in sparse pseudorandom graphs
• Szemerédi's regularity Lemma for matrices and sparse graphs
• On regularity lemmas and their algorithmic applications

Cites work

• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• A new proof of the graph removal lemma
• A short proof of Gowers' lower bound for the regularity lemma
• A variant of the hypergraph removal lemma
• Bounds for graph regularity and removal lemmas
• Efficient testing of large graphs
• Entropy and information theory.
• Extremal problems on set systems
• Graph removal lemmas
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 3202900 (Why is no real title available?)
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Probability Inequalities for Sums of Bounded Random Variables
• Quick approximation to matrices and applications
• Regular Partitions of Hypergraphs: Regularity Lemmas
• Regularity Lemma for k-uniform hypergraphs
• Regularity lemmas for graphs
• Szemerédi's lemma for the analyst
• Szemerédi's regularity Lemma for matrices and sparse graphs
• Szemerédi's regularity lemma revisited
• The counting lemma for regular k‐uniform hypergraphs

Cited in

(11)

• A tight bound for hypergraph regularity
• Extremal results in sparse pseudorandom graphs
• SPARSE PARTITION REGULARITY
• Estimating parameters associated with monotone properties
• \(L_p\) regular sparse hypergraphs: box norms
• The induced removal lemma in sparse graphs
• A unified view of graph regularity via matrix decompositions
• Local-vs-global combinatorics
• Testing versus estimation of graph properties, revisited
• Asymmetric results about graph homomorphisms
• Small subsets inherit sparse \(\varepsilon\)-regularity

This page was built for publication: A sparse regular approximation lemma

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