***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Andrey Kupavskii (U. Oxford and IAS)
Thursday 10th October, 3:00 in Fine Hall 224.
Title: Concentration inequalities for finding rainbow matchings
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.
----------------------------------
Next week: Yufei Zhao
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)