Description
Time: 2:15-3:15
Title: On tricolored-sum-free sets and Green's Boolean Removal Lemma
(Part II, continued from last week)
Abstract: A tricolored-sum-free set in F_2^n is a collection of triples
{(a_i,b_i,c_i)}_{I=1..m} such that
a) for each I, a_i+b_i+c_i=0
b) If a_i+b_j+c_k = 0, then I=j=k.
The notion of a tricoloured-sum-free set generalizes the notion of a
capset to F_2^n. The basic question here is: How large can a
tricolored-sum-free set be?
We will see the following two (recent) results.
i) Kleinberg's upper bound of 6\binom{n}{n/3} for a tricolored-sum-free
set. This in conjunction with a previous result of his establishing a
lower bound of \binom{n}{n/3}2^{-\sqrt{16n/3}} gives almost asymptotically
tight results.
ii) Ben Green (in 2005) proved the following BOOLEAN REMOVAL LEMMA:
Given \epsilon>0 there exists \delta depending only on epsilon such
that the
following holds: Write N=2^n. If X,Y,Z are subsets of F_2^n if by deleting
\epsilon N elements from X,Y, Z altogether, one can eliminate all
arithmetic triangles (triples (x,y,z) with \in X,y\in Y,z\in Z such that
x+y+z=0) then there are at most \delta N^2 arithmetic triangles in
(X,Y,Z). Green's proof establishes a bound for1/(\delta) which is a tower
of 2s of length poly(1/\epsilon). We will look at a recent result of Fox
and Lovasz (junior) who obtained an almost tight bound for this
delta-epsilon dependence with \delta =O(\epsilon^{O(1)}).