Efficient Removal without Efficient Regularity

by Lior Gishboliner and Asaf Shapira

Oded's comments

A famous open problem consists of determining the (query) complexity of testing triangle-freeness in the dense graph model. It is known for two decades that this complexity is super-polynomial in $1/\eps$, but it is only upper bounded by a tower function (in $\eps$). I find it quite puzzling that the complexity of testing triangle-freeness is greater than the complexity of testing Bipartitness, and the current work indicates that this is not due to the fact that triangle-free graphs have huge regular partitions (since the same holds for induce C4-freeness). Furthermore, this recent work provides a more dramatic demonstration of the fact that subgraph freeness properties can be tested without relying on a regularity lemma, a fact that was already demonsterated by Alon with respect to bipartite subgraphs.

The original abstract

Obtaining an efficient bound for the triangle removal lemma is one of the most outstanding open problems of extremal combinatorics. Perhaps the main bottleneck for achieving this goal is that triangle-free graphs can be highly unstructured. For example, triangle-free graphs might have only regular partitions (in the sense of Szemer\'edi) of tower-type size. And indeed, essentially all the graph properties P for which removal lemmas with reasonable bounds were obtained, are such that every graph satisfying P has a small regular partition. So in some sense, a barrier for obtaining an efficient removal lemma for property P was having an efficient regularity lemma for graphs satisfying P. In this paper we consider the property of being induced C4-free, which also suffers from the fact that a graph might satisfy this property but still have only regular partitions of tower-type size. By developing a new approach for this problem we manage to overcome this barrier and thus obtain a merely exponential bound for the induced C4 removal lemma. We thus obtain the first efficient removal lemma that does not rely on an efficient version of the regularity lemma. This is the first substantial progress on a problem raised by Alon in 2001, and more recently by Alon, Conlon and Fox.

See arXiv:1709.08159.

Back to list of Oded's choices.