[Colloquium] Theory Seminars at Computer Science

[Donna Brooms via Colloquium]

Departments of Computer Science & Mathematics
Combinatorics & Theoretical Seminar

Tuesday, October 25, 2016
3:00 pm
Ryerson 251

Laszlo Lovasz
MIT & Stanford
http://www.math.mit.edu/~lmlovasz/

Abstract:

Let p be a fixed prime. A triangle in F_p^n is an ordered triple (x,y,z) of points satisfying x+y+z=0. Let N=p^n, (the size of F_p^n). Green proved an arithmetic triangle removal lemma which says that for every epsilon>0 and prime p, there is a delta>0 such that if X, Y, and Z are subsets of F_p^n and the number of triangles in X x Y x Z is at most delta times N^2 (so a delta fraction of all possible triangles), then we can delete epsilon times N elements from X, Y, and Z and remove all triangles. Green posed the problem of improving the quantitative bounds on the arithmetic triangle removal lemma, and, in particular, asked whether a polynomial bound holds. Despite considerable attention, prior to our work, the best known bound, due to Fox, showed that 1/delta can be taken to be an exponential tower of twos of height logarithmic in 1/epsilon.

In this talk, we will discuss our solution to Green's problem. We prove an essentially tight bound for Green's arithmetic triangle removal lemma in F_p^n. We show that for any fixed p, a polynomial bound holds, and further determine the best possible exponent for each prime p. The proof uses Kleinberg, Sawin, and Speyer's essentially sharp bound on multicolored sum-free sets, which builds on the recent breakthrough on the cap set problem by Croot-Lev-Pach, and the subsequent work by Ellenberg-Gijswijt, Blasiak-Church-Cohn-Grochow-Naslund-Sawin-Umans, and Alon.

Joint work with Jacob Fox

Host: Prof. Laszlo Babai

Refreshments will be served prior to the talk at 2:30 pm in Ry. 255

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20161021/85a46f2b/attachment.html>