A solution to Kneser's Critical problem

Matthew J. Devos, Princeton University

Tuesday, March 4, 4:30 PM, CORE 431

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.


Back to Discrete Math/Theory of Computing seminar