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)}).

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)}).

Description

Ramanujan Hall

Date

Thu, March 16, 2017

Start Time

2:10pm IST

Priority

5-Medium

Access

Public

Created by

DEFAULT ADMINISTRATOR

Updated

Wed, March 15, 2017 9:37pm IST