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.