The Zarankiewicz Problem By Professor Larry Guth, MIT, The Class of 1960 Scholars Program

The Zarankiewicz Problem By Professor Larry Guth, MIT, The Class of 1960 Scholars Program, Monday September 11, 1:00 – 1:50PM, Wege Auditorium, Thompson Chemistry Labs 123

Abstract: This talk will be about one of my favorite math problems.  It’s simple enough to explain to high school students and it’s well beyond any methods that people have found so far.

The first version of the problem is called the No Rectangles game.  Suppose we have an N x N grid of dots.  We are allowed to color some of the dots red, but there is a rule that we cannot put red dots on all four corners of any rectangle.  How many red dots can we put in this grid?

This particular problem is understood, but many variations are open.

Here is what I like about it.  First suppose we write a simple (greedy) computer algorithm which plays the No Rectangles game and tries to put as many red dots as it can.  We will analyze how many red dots the simple computer algorithm is able to put.  Then I’ll describe to you the optimal strategy, which does much better than the simple algorithm.  The optimal strategy involves a lot of mathematical structures from the undergrad and high school curriculum: points and lines, polynomials, integers modulo p.  It’s interesting to me that these classical mathematical structures appear in this problem which doesn’t sound immediately related to any of them.  Beyond this point, there are many open questions.  Do all the good solutions of the No Rectangles game connect with these mathematical structures?  Would a fancier computer algorithm find them?  Would it find something else?  What happens for different variations of the No Rectangles game?