Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Concentration inequalities for finding rainbow matchings

Andrey Kupavskii (IAS)

Location:  Hill 705
Date & time: Monday, 25 November 2019 at 2:00PM - 3:00PM

Abstract: Consider a k-partite k-uniform hypergraph on [n]^k. It is not difficult to see that any such hypergraph with more than (s-1)n^{k-1} edges contains a matching of size s. Aharoni and Berger asked a "transversal" variant of this question: given s hypergraphs, each having more than (s-1)n^{k-1} edges, can we guarantee the existence of an s-matching with the i-th edge coming from the i-th hypergraph? In this talk, I will present our progress on this problem using a certain concentration inequality for the intersection of a family with a random matching.

Joint work with Sergei Kiselev.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.