Featured event

rubberband ball

Summer SILO @ the Red Gym: Jordan Ellenberg

Event Details

When: May 26, 2016, 4:00 PM

Location: On Wisconsin C, Armory and Gymnasium (Red Gym)

Contact: echall@wisc.edu

A big conjecture in combinatorics that unexpectedly got proved last week and what this has to do with matrix multiplication

Jordan Ellenberg, Professor, Department of Mathematics, UW-Madison
There’s a popular folk question about the card game Set: how many cards can you have on the table before there’s necessarily a legal play? The answer, which is pretty tricky to work out, and which is larger than most people expect, is 20. This is one case of a famous old problem in combinatorics, the “cap set problem”: If S is a subset of (Z/3Z)^n, which has no three elements summing to 0, how large can S be? About 15 years ago it was proved by Meshulam that the size of such a set is O(3^n/n). A few years ago that was slightly improved to O(3^n / n^{1+eps}). Then suddenly last week, by a combination of work by Ernie Coot, Vsevolod Lev, Peter Pach, Dion Gijswijt, and me, that upper bound suddenly shrunk to O(2.756^n). The paper is 2 pages long and explaining the whole proof would not be enough material for a whole talk! This is another startling success of “the polynomial method,” which, starting with the 2008 theorem of Ze’ev Dvir (who just spoke here at Applied Algebra Days) has had an amazing run of providing short proofs of old problems that were thought to be hard.

I will explain how this theorem is proved, state the implications for matrix multiplication (which I haven’t understood yet but might by Thursday), philosophize about simultaneous low rank and sparsity, and talk about some related problems I think might be ripe for solution now.

My blog post:
https://quomodocumque.wordpress.com/2016/05/13/bounds-for-cap-sets/

Terry’s blog post:
https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/

The paper relating all this to matrix multiplication:
http://math.stanford.edu/~church/BCCGU-On-cap-sets-and-the-group-theoretic-approach-to-matrix-multiplication.pdf

During the summer, SILO will meet at 4pm on Thursdays in “On Wisconsin C” in the Red Gym.

The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group.

SILO is a lecture series with speakers from the UW faculty, graduate students or invited researchers that discuss mathematical related topics. The seminars are organized by WID’s Optimization research group.

SILO’s purpose is to provide a forum that helps connect and recruit mathematically-minded graduate students.