***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Eli Berger (U Haifa)

Thursday 25th September, 3:00 in Fine Hall 224.

Title: Lower bounds for rainbow matchings size


Let M_1,..., M_m be matchings in some graph G. A rainbow matching is a
matching with at most one edge from each of M_1,...M_m. Let n be some 
natural number. In this talk, I will discuss sufficient conditions for
the existence of a rainbow matching of size n. In particular, I will 
show that one such condition is

sum_{i=n}^m (|M_i| - n + 1) \geq 5 n \log_2(n)

(where here we assume that each of M_1,..., M_{n-1} is at least as big as
M_n,..., M_m.)

In particular, this holds when m \geq n + \sqrt{5 n \log_2(n)} and each of
M_1,..., M_m has size at least n + \sqrt{5 n \log_2(n)}. This improves a
similar result by Correia, Pokrovskiy, and Sudakov with 20 n^{7/8} instead of
\sqrt{5 n \log_2(n)}.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)