## 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.