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.

redesigned by barak soreq