
<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Departments of Computer Science & Mathematics<br class="">Combinatorics & Theoretical Seminar<br class=""><br class="">Tuesday, October 25, 2016<br class="">3:00 pm<br class="">Ryerson 251<br class=""><br class=""><b class="">Laszlo Lovasz</b><br class="">MIT & Stanford<br class=""><a href="http://www.math.mit.edu/~lmlovasz/" class="">http://www.math.mit.edu/~lmlovasz/</a><br class=""><br class="">Abstract:<br class=""><br class=""><div style="text-align: justify;" class="">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.</div><br class="">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.<br class=""><br class="">Joint work with Jacob Fox<div class=""><br class=""></div><div class="">Host: Prof. Laszlo Babai</div><div class=""><br class=""></div><div class="">Refreshments will be served prior to the talk at 2:30 pm in Ry. 255<br class=""><br class=""></div></body></html>