On Graphs, Progressions and Communication

Friday, November 30, 2012 - 10:30am - 11:30am
Keller 3-180
Noga Alon (Tel Aviv University)
Tools from Extremal Graph Theory are helpful in the study of problems
in Additive Number Theory, Theoretical Computer Science, and Information
Theory. I will illustrate this fact by several closely related examples
focusing on a recent one in a joint work with Moitra and Sudakov.

The main combinatorial question addressed, whose study was initiated by
Ruzsa and Szemeredi, is that of estimating the maximum possible density of
a graph consisting of a union of pairwise edge disjoint large induced
matchings. This is strongly related to questions in additive number
theory, theoretical computer science and communication complexity.
MSC Code: