DIMACS Discrete Math/Theory of Computing Seminar

Title: A solution to Kneser's Critical problem

Speaker: Matthew J. Devos, Princeton University

Date: Tuesday, March 4, 2003

Date: February 4, 2003, 4:30-5:30

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract: In 1953 Martin Kneser proved an addition theorem which gives a natural lower bound on |A+B| for any pair A,B of finite subsets of an (additive) abelian group. Three years later he posed the problem of characterizing those pairs A,B for which |A+B| < |A| + |B|. Such pairs are now called critical. We have recently proved a structure theorem which resolves Kneser's problem. It shows that every critical pair has a recursive structure based on arithmetic progressions and two other configurations. The goal of this talk is to describe the structure of critical pairs and to sketch a proof of this theorem.