Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

A sparse regular approximation lemma


Authors: Guy Moshkovitz and Asaf Shapira
Journal: Trans. Amer. Math. Soc. 371 (2019), 6779-6814
MSC (2010): Primary 05C35, 05D99
DOI: https://doi.org/10.1090/tran/7414
Published electronically: February 22, 2019
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce a new variant of Szemerédi'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 \vert E(G)\vert$ 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(\log 1/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 (\log 1/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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C35, 05D99

Retrieve articles in all journals with MSC (2010): 05C35, 05D99


Additional Information

Guy Moshkovitz
Affiliation: School of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel
Email: guymosko@tau.ac.il

Asaf Shapira
Affiliation: School of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel
Email: asafico@tau.ac.il

DOI: https://doi.org/10.1090/tran/7414
Received by editor(s): November 3, 2016
Received by editor(s) in revised form: August 28, 2017
Published electronically: February 22, 2019
Additional Notes: The second author was supported in part by ISF Grant 1028/16 and ERC-Starting Grant 633509.
Article copyright: © Copyright 2019 American Mathematical Society