Open Collections

Tight colorful Tverberg for matroids.

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Convex and discrete geometry; Algebraic topology; Combinatorics

video/mp4

Author affiliation: Hebrew University of Jerusalem

2017-06-07

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/61857

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/