When: Sunday, April 23, 10am
Where: Schreiber 309
Speaker: Eli Berger (Haifa)
Title: Fair representation
If a set V is partitioned to subsets V_1...V_m and X is a subset of V, we say that X fairly represents the sets V_1...V_m if $|X \cap V_i| \geq [|X| |V_i| / |V|$ for each i=1...m (here [ ] stands for rounding down). Several results and conjectures in combinatorics can be formulated in term of the existence of a fairly representing set with particular properties. In the talk, I will discuss several such results and conjectures, and in particular the case where we want X to be a matching in a graph, an independent set in a graph or a matroid or a common independent set in two or more matroids.
