KAIST Discrete Math Seminar

We study algebraic analogues of the graph Removal Lemma. Vaguely speaking, the graph Removal Lemma says that if a given graph does not contain too many subgraphs of a given kind, then all the subgraphs of this kind can be destroyed by removing few edges. In 2005, Green conjectured the following analogue of it for systems of equations over integers:

For every k x m integral matrix A with rank k and every ε>0, there exists δ>0 such that the following holds for every N and every subset S of {1,…N}: if the number of solutions of A x = 0 with x ∈ S^m is at most δ N^{m-k}, then it is possible to destroy all solutions x ∈ S^m of A x = 0 by removing at most ε N elements from the set S.

We prove this conjecture by establishing its variant for not necessarily homogenous systems of equations over finite fields. The core of our proof is a reduction of the statement to the colored version of hypergraph Removal Lemma for (k+1)-uniform hypergraphs. Independently of us, Shapira obtained the same result using a reduction to the colored version of hypergraph Removal Lemma for O(m²)-uniform hypergraphs. The talk will be self-contained and no previous knowledge of the area related to the graph Removal Lemma will be assumed.

Joint work with Oriol Serra and Lluis Vena.