Séminaire CAESAR
de combinatoire additive
Séance du 10 mars 2011
(11 heures, École polytechnique, CMLS, salle
de conférence):
Daniel KRÁL'
(Univerzita Karlova, Prague, République tchèque)
Algebraic analogues of the graph-theoretic removal lemma
We study algebraic analogues of the graph Removal Lemma.
Vaguely speaking, the 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 eps>0,
there exists delta>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 \in S^m is at most delta N^{m-k}, then it is possible
to destroy all solutions x \in S^m of A x = 0 by removing
at most eps N elements from the set S.
The conjecture includes the statement of the well-known
theorem of Szemeredi on the existence of arbitrary long
arithmetic progressions in dense subsets of integers as
one of its special cases (through a suitable choice of
the matrix A). We will briefly discuss this in the talk.
We prove the 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^2)-uniform hypergraphs.
Retour à la page d'accueil du
séminaire