Hypergraph removal lemmas via robust sharp threshold theorems

increases. In this paper we present `robust' versions of the theorem, which assert that it holds also if the function is `almost' monotone, and admits a much weaker notion of symmetry. Unlike the original proof of the theorem which relies on hypercontractivity, our proof relies on a `regularity' lemma (of the class of Szemer'edi's regularity lemma and its generalizations) and on the `invariance principle' of Mossel, O'Donnell, and Oleszkiewicz which allows (under certain conditions) replacing functions on the cube

{0, 1}^{n}

with functions on Gaussian random variables. The hypergraph removal lemma of Gowers (2007) and independently of Nagle, R"odl, Schacht, and Skokan (2006) says that if a

k

-uniform hypergraph on

n

vertices contains few copies of a fixed hypergraph

H

, then it can be made

H

-free by removing few of its edges. While this settles the `hypergraph removal problem' in the case where

k

and

H

are fixed, the result is meaningless when

k

is large (e.g.

k > l o g l o g l o g n

). Using our robust version of the Friedgut-Kalai Theorem, we obtain a hypergraph removal lemma that holds for

k

up to linear in

n

for a large class of hypergraphs. These contain all the hypergraphs such that both their number of edges and the sizes of the intersections of pairs of their edges are upper bounded by some constant.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Hypergraph removal lemmas via robust sharp threshold theorems

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