Colloquium: Tuesday, November 5, 2019. Speaker: Ron Aharoni (Technion). Title: “Topic: The colorful world of rainbow sets”.
Given a family of sets, a partial choice function chooses an element from some of them. The range of the function is then called a “rainbow set” (the “colors” being the sets). There are two types of conditions that are usually imposed on the function: either the domain should be large and the range small, or that the domain in small and the range large. The classical case of the first type is Hall’s marriage theorem, where all men are to be married, and the function is supposed to be injective, a classical case of the second type is the Lov’\asz-Barany colorful Caratheodory theorem, in which the range should contain a given vector in its convex hull. Results in the first are usually Hall-like, meaning “cooperative” – if the union of every k sets is large (in terms of k), then there exists a choice function with “small” range. 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 also for the second family.
Tea will be served before the talk (at 13:50).
