Joshua Brody: Amazingly dense Ruzsa-Szemeredi graphs, plus applications

Register for lunch at doodle.com/kza639ruxxk4mffn by Sunday, September 9, at 8 pm.  

ABSTRACT

An induced matching of a graph G=(V,E) is a matching M such that no two edges of M are joined by an edge in G. A Ruzsa-Szemeredi graph is a graph G, together with an edge coloring, such the set of edges of any particular color forms an induced matching on G. Researchers have found surprising applications of Ruzsa-Szemeredi graphs in a wide range of areas, including communication over shared channels, linearity testing, and communication complexity. For these applications, we generally want graphs that (1) are as dense as possible, but (2) use as few colors as possible.

In this talk, I'll present a recent construction of Alon, Moitra, and Sudakov from STOC 2012 which seems too good to be true. They construct a graph which is nearly complete, but can be decomposed into a slightly superlinear number of induced matchings. This is essentially the best one can hope for. Time permitting, I'll also present an application or two.

This talk assumes only basic knowledge of graph theory. (i.e. I'll start by describing what induced matchings are, and go from there)

This talk mostly covers work from the STOC 2012 paper "Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications" by Noga Alon, Ankur Moitra, and Benny Sudakov.  

ABOUT THE THEORY READING GROUP

The reading group meetings are intended to run for 3 hours plus minus, during which time we will have the possibility to first get an overview of some interesting research results and then study them in some depth.

We start at noon with a light lunch, and as soon as people are seated there is a presentation for 45-60 minutes. This should be an accessible talk, not requiring any particular prerequisites. Then there is a short break. Up to this point the whole exercise should be pretty much indistinguishable from a regular (lunch) seminar.

After the break, we return for ca two hours of more technical discussions. Now we open up the hood, look at the formal definitions, and prove at least some of the key ingredients in the results including all the gory technical details glossed over in a polished seminar presentation. This part will typically be on the board, and should hopefully be very interactive.

However, for those who feel that the first one-hour regular seminar was enough for today, it is perfectly fine to just discretely drop out during the break. No questions asked.