Combinatorics Seminar

When: Sunday, December 1, 10am
Where: Schreiber 309
Speaker: Ron Aharoni, Technion
Title: The colorful world of rainbow sets

Abstract:

Given a family of sets, a partial choice function chooses an element from some of them. There are two types of conditions that are usually imposed on the function: either the domain should be large and the image small, or that the domain in small and the image large. The classical case of the first type is Hall's marriage theorem, a classical case of the second type is the Lovász-Barany colorful Caratheodory theorem, in which the image is supposed to be "large" in the sense that it contains in its convex hull a given vector.

Sufficient conditions for the existence of functions of the first type are usually Hall-like, meaning "cooperative" - the union of every $k$ sets should be large (in terms of $k$). In results around the second type each of the sets is required to be large, individually. We show that this is not divine decree: there are Hall-like theorems (and conjectures) also for the second family.

Joint work(s) with Joseph Briggs, Ron Holzman, Zilin Jiang, Minki Kim, Jinha Kim and Dani Kotlar.