On graphs decomposable into induced matchings of linear size

On graphs decomposable into induced matchings of linear size

-
Hao Huang , Emory University
Fine Hall 224

A ``Ruzsa-Szemeredi graph'' is a graph on n vertices whose edge set can be partitioned into induced matchings of size cn. The study of these graphs goes back more than 35 years and has connections with number theory, combinatorics, complexity theory and information theory. In this talk we will discuss the history and some recent developments in this area. In particular, we show that when c>1/4, there can be only constantly many matchings. On the other hand, for c=1/4, the maximum number of induced matchings is logarithmic in n. This is joint work with Jacob Fox and Benny Sudakov.