The colorful world of rainbow sets
Ron Aharoni
Technion
April 8, 2021, 12:30 in Zoom (Meeting ID: 982 7927 6897; Passcode: 625228)
Abstract
A rainbow set is the image of a partial choice function, for a given collection S of sets.
There are two types of problems in the field:
(1) We may wish to have a large rainbow set, for example representing all sets in S, while having the image small in some sense. Hall's theorem is of this type - the "small-ness" of the image is in this case injectivity.
(2) We may wish the image to be large in some sense (for example, spanning in some matroid).
Two topological theorems are relevant. One, the A-Berger theorem, gives conditions for the existence of type (1) rainbow sets, and the Kalai-Meshulam theorem provides conditions for the existence of a rainbow set of the second type.
In fact, the two theorems are equivalent, upon using matroid duality and Alexander duality.
I will tell some applications, and open problems.
There are two types of problems in the field:
(1) We may wish to have a large rainbow set, for example representing all sets in S, while having the image small in some sense. Hall's theorem is of this type - the "small-ness" of the image is in this case injectivity.
(2) We may wish the image to be large in some sense (for example, spanning in some matroid).
Two topological theorems are relevant. One, the A-Berger theorem, gives conditions for the existence of type (1) rainbow sets, and the Kalai-Meshulam theorem provides conditions for the existence of a rainbow set of the second type.
In fact, the two theorems are equivalent, upon using matroid duality and Alexander duality.
I will tell some applications, and open problems.
