Videos

On Graphs, Progressions and Communication

Presenter
November 30, 2012
Keywords:
  • Graph theory
MSC:
  • 97K31
Abstract
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.