BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Tight colorful Tverberg for matroids. Patak, Pavel


Colorful Tverberg theorem states that given a set of $(r-1)(d+1)+1$ points in $\mathbb{R}^d$ divided into $m$ color classes of size at most $(r-1)$, there exist $r$ rainbow simplices whose intersection is non-empty. Simplex is called rainbow, if all its vertices are points of different colors. Here we prove the same bounds for matroidal version of the problem. Since a simplex is the convex hull of its vertices the conclusion of the original colorful Tverberg can be restated as "The intersection of convex hulls of some r rainbow sets is non-empty". In the matroidal version, we replace convex hulls with any (matroidal) closure operator (e.g. affine hulls). The advantage of the "affine closure" version is that it is valid even for fields for which convex hulls are not defined, we may weaken the assumptions and assume that one of the color classes has size at most r and the remaining have size at most r-1, and that the rainbow sets can be found algorithmically. On the other hand, the conclusions of the theorem are weaker. We show that the theorem is tight and present some application of it.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International