Tverberg type theorems for matroids
Pavel Paták


DeepNAT: Deep Convolutional Neural Network for Segmenting Neuroanatomy
    Martin Reuter^b,c, Tassilo Klein^d
    December 30, 2023
======================================================================




In this paper we show a variant of colorful Tverberg's theorem which is valid in any matroid:
Let S be a sequence of non-loops in a matroid M of finite rank m with closure operator . Suppose that S is colored
in such a way that the first color does not appear more than r-times and each other color appears at most (r-1)-times.
Then S can be partitioned into r rainbow subsequences S_1,…, S_r such that
∅⊊ S_1⊆ S_2⊆…⊆ S_r. In particular, ∅≠⋂_i=1^r  S_i.
A subsequence is called rainbow if it contains each color at most once.

The conclusion of our theorem is weaker than the conclusion of the original Tverberg's theorem in ^d, 
which states that ⋂ S_i≠∅, whereas we only claim that ⋂ S_i≠∅.
On the other hand, our theorem strengthens the Tverberg's theorem in several other ways:
[label=*)]

  * it is applicable to any matroid (whereas Tverberg's theorem can only be used in ^d), 

  * instead of ⋂ S_i≠∅ we have 
the stronger condition ∅⊊ S_1⊆ S_2⊆…⊆ S_r, and

  * we add color constraints that are even stronger than the color constraints in the colorful version of Tverberg's theorem.

  
Recently, we used the first property and applied the non-colorful version of this theorem to homology groups 
with GF(p) coefficients to obtain several non-embeddability results, for details we refer to <cit.>.




§ INTRODUCTION



Tverberg's theorem <cit.> states that given (d+1)(r-1)+1 points[We allow repetitions among these points.] 
in ^d, it is possible to split these points into r sets
S_1,…, S_r with intersecting convex hulls, that is with 
⋂ S_i≠∅.

If one replaces convex hulls with affine hulls, one obtains a valid statement (Lemma <ref>),
which has the advantage of being applicable to any field <cit.>.
Lemma <ref> is also easier to prove than the original Tverberg's theorem. 
Since the proof only uses properties of closure operators, the statement does generalize
to any matroid (Lemma <ref>).
In both these cases the conclusion can be strengthened a bit: instead of S_1∩… S_r≠∅,
one can require ∅⊊ S_1⊆ S_2⊆…⊆ S_r.

In this paper we study the variant of Tverberg's theorem for matroidal closures
and show that it allows a colorful version – a generalization where the original points
are colored and one furthermore requires that no resulting set S_i, i=1,…, r
contains two or more points of the same color.

While the version without colors is straightforward <cit.> 
the proof of the colorful version
is more subtle. 
Moreover, our proof method yields an efficient algorithm that finds the required sets in polynomial time.




 §.§ Terminology

Before we state our results formally, let us introduce some notations and terminology
which will allow us to nicely present the statements and proofs.
We assume that the reader is acquainted with the basic matroid theory.
We always use the symbols r and m to denote non-negative integers.
We use the symbols , ,  and  for matroidal closure, affine closure, convex hull
and rank function, respectively.

If M is a set, we consider a sequence S=(m_i)_i∈ I of elements from M
as a set of pairs {(i,m_i)| i∈ I}.
With this convention we can use the set theoretic terminology for sequences: 
|S| is the length of the sequence, S'⊆ S means that S' is a subsequence of S,
we know what it means for two subsequences to be disjoint,
we can use the operation S∖ S' of (sequence) difference, etc.

If S={(i,m_i)| i∈ I} is a sequence and we need to refer to the set {m_i| i∈ I},
we use the symbol S^set.

If Ψ is a map from the subsets of M (for example a closure operator, rank function),
and S=(m_i)_i∈ I is a sequence in M, we use a shorthand Ψ(S):=Ψ(S^set).
To make formulas and equations shorter, we leave out the parantheses after the operators , ,  and 
when there is no danger of confusion.

A coloring of a sequence S={(i,m_i)| i∈ I} is any map c S→ C into some set C of colors,
that is, c assigns to each pair (i,m_i) a color from C. The sequence S is rainbow with respect to c,
if the restriction of c to S is injective.



 §.§ Main results


Let us first state the non-colorful variant of Tverberg's theorem for affine hulls
and its easy generalization to matroidal closures.


 Let S be a sequence of points in an affine space 𝔸
 of dimension d. If[We do not require d to be finite,
 therefore the slightly unusual formulation.] |S|>(d+1)(r-1), 
 then there exist r pairwise disjoint subsequences S_1,…, S_r of S with ⋂_i=1^r  S_i≠∅.
 In fact, there are r pairwise disjoint subsequences S_1,…, S_r satisfying 
 ∅≠ S_1⊆ S_2⊆…⊆ S_r.



 Let M be a (finitary[Finitary matroids are generalization
 of matroids to not necessary finite ground sets. They add the following axiom to the usual axioms for finite matroids:
 If y∈(X), then there exists a finite set X'⊆ X such that y∈(X'). With these addition,
 such terms as rank or basis can be correctly defined.]) matroid of rank m with closure operator  and S be a sequence of points in M 
 with |S|>m(r-1).
 Then there exist r pairwise disjoint subsequences S_1,…, S_r of S
 satisfying ∅⊊ S_1⊆ S_2⊆…⊆ S_r.


In <cit.> we only stated that there exists sets S_i with ∅≠⋂ S_i.
However, the proof there implies Lemma <ref>, and (if one replaces  with the closure
operator  of a matroid) Lemma <ref>.
In the case of matroids of finite rank, both lemmas can also be obtain as a direct consequence of Theorem <ref>.

In <cit.> we applied Lemma <ref> to homology groups over finite fields. This enabled us to prove some inequalities for simplicial complexes embeddable into various manifolds.
Our colorful matrodial Tverberg (Theorem <ref>) provides a control
of the resulting sets, which enables us to further improve the bounds from <cit.>. For the details
of the improvement, see the author's thesis <cit.>.

We are now ready to state the main results of this paper.


 Let M be a matroid of a finite rank m and S be a sequence of non-loops in M 
 colored by some colors in such a way that at most m elements of S are colored by the first color,
 at most m-1 by the second color, at most m-1 by the third color, etc.
 If |S|>m(r-1), 
 then there exist r pairwise disjoint rainbow subsequences S_1,…, S_r of S,
 such that ∅⊊ S_1⊆ S_2⊆…⊆ S_r.
 
 Furthermore, if the time required to decide whether a point x∈ M lies in the closure of a set Y⊆ M is bounded by u,
 then the subsequences S_1,…, S_r can be found in time polynomial in r, m, u and |S|.


In the proof of Theorem <ref> we encounter another version
of colorful matroidal Tverberg's theorem.


 Let M be a matroid of a finite rank m and S a sequence of non-loops in M
 colored by m colors in such a way that at least r elements of S are colored by the first color,
 at least r-1 by the second color, at least r-1 by the third, …, at least r-1 by the mth color. 
 
 Then there exist r pairwise disjoint rainbow subsequences S_1,…, S_r of S
 such that ∅⊊ S_1⊆ S_2⊆…⊆ S_r.
 
 Furthermore, if the time required to decide whether a point x∈ M lies in the closure of a set Y⊆ M is bounded by u,
 then the subsequences S_1,…, S_r can by found in time polynomial in r, m, u and |S|.

Note the different conditions on the number of points of each color.
In Theorem <ref> these conditions are used to ensure
that we have enough colors. 
In Theorem <ref> we already have the right number of colors,
but the conditions ensure that the length of S is sufficient.

Moreover, these results are tight:

 Lemma <ref>, Lemma <ref>, Theorem <ref>
 and Theorem <ref> are sharp. To be precise, for any r and any matroid M of rank m there
 exists a sequence S of non-loops in M with |S|=m(r-1) such that any division of S into  r disjoint subsequences S_1,…, S_r satisfies ⋂ S_i =∅.


Tverberg-type theorems in ^d

Let us now compare our main results with the related theorems valid in ^d.

In this section Δ_n denotes the n-dimensional simplex.

Tverberg's theorem can be stated as follows: If fΔ_(d+1)(r-1)→^d is an affine map,
there are r pairwise disjoint faces σ_1,…, σ_r of Δ_(d+1)(r-1)
with ⋂_i=1^r f(σ_i)≠∅. This is the reason why 
Tverberg's theorem is also called affine Tverberg's theorem. To avoid confusion, we have decided not to use the name
“affine Tverberg” for Lemma <ref>.

If r is a prime power, Özaydin <cit.> showed that the same result holds for an arbitrary continuous map f.
The statement is known as topological Tverberg. It was a long-standing open problem, whether topological Tverberg can be extended to other values of r.
The negative answer came in 2015, when Frick (based on the previous work of Mabillard and Wagner <cit.>)
constructed first counterexamples <cit.>. Counterexamples for other values of d and r followed shortly afterwards. <cit.>

If r is a prime, there is a colorful version of (topological) Tverberg's theorem <cit.> as well:
Suppose that the vertices of K=Δ_(d+1)(r-1) are colored in such a way, that no color is used
more than (r-1)-times. 
Then for every continuous map fΔ_(d+1)(r-1)→^d, there are r pairwise disjoint rainbow[Containing
each color at most once.]
faces σ_1,…, σ_r of Δ_(d+1)(r-1) with ⋂_i=1^r f(σ_i)≠∅.

The colorful version provides more control over the resulting sets σ_1,…,σ_r.


Even if f is an affine map, the only known proof uses topological methods and needs the assumption that r is prime.
Whether this assumption can be relaxed in the affine situation is an open question.
Moreover, the topological proof does not provide any way how to find the pairwise disjoint faces, it merely shows their existence.

We see that Theorem <ref> does not require r to be a prime number, it relaxes the conditions on the colors from topological version a bit and provides an efficient algorithm for finding the desired sets.

We also note that Bárány, Kalai and Meshulam proved another, very different 
Tverberg Type Theorem for Matroids <cit.>,
they considered continuous maps from the matroidal complex and showed the following:
If b(M) denotes the maximal number of disjoint bases in a matroid M of rank d+1,
then for any continuous map f from the matroidal complex M into ^d there
exists t≥√(b(M))/4 disjoint independent sets σ_1,…, σ_t∈ M such that
⋂_i=1^tf(σ_i)≠∅.





§ TIGHTNESS

We postpone the technical proofs of our main results, Theorems <ref> and <ref> to the end of the paper. First we prove Proposition <ref> showing their tightness. 
The proof is a variant of the standard construction for showing that Tverberg's theorem is tight.

We start with an auxiliary lemma.
 
 Let M be a matroid with finite basis B. Then for any two sets U,V⊆ B
            
    (U)∩(V) =(U∩ V).

 
 
  Since the operator  is monotone, the inclusion
  (U∩ V)⊆(U)∩(V) is obvious.
  Let us now prove the opposite inclusion.
  
  Let x∈(U)∩(V) be an arbitrary element. We want to show that x∈(U∩ V).
  If x is a loop, x∈∅⊆(U∩ V). So assume that x is not a loop.
  
  Let U'⊆ U and V'⊆ V be inclusion minimal subsets with x∈(U') and x∈(V'), respectively.
  Since we assume that x is not a loop, U'≠∅≠ V'.
  
  We will show by contradiction that U'=V', hence proving the claim.
  If U'≠ V', we may up to symmetry assume that there is
  an element u'∈ U' which does not lie in V'.
  
  
  From the inclusion minimality of U' follows that x∈((U'∖{u'})∪{u'})∖(U'∖{u'}). 
  The exchange principle yields u'∈(U'∖{u'}∪{x}).
  Similarly v'∈(V'∖{v'}∪{x}) for an arbitrary v'∈ V'.
  
  The set U'∪ V' is independent being a subset of a basis B.
  By construction (U'∖{u'}∪ V'∖{v'}∪{x})=(U'∪ V').
  Comparing the ranks of both sides and using the fact that u'∉ V', we see that v' has to belong to U'. 
  Since v' was arbitrary, this implies V'⊊ U' – in contradiction with U' being minimal with x∈(U').
 

We can now finally prove Proposition <ref>.

 Let B=(e_1,…,e_m) be a basis of the matroid M.
 It suffices to take 
 
    S=e_1,e_1,…, e_1_(r-1)×, e_2,e_2,…, e_2_(r-1)×,…, e_m,e_m,…, e_m_(r-1)×.

 Let S_1,…, S_r be disjoint subsequences of S.
 Then
 
    ⋂_i=1^r (S_i) =  (⋂_i=1^r S_i^set)=(∅),

 where the first equality follows by inductive application of Lemma <ref> and the second equality uses the fact that each element e_j is missing in at least one sequence S_i.


We also note that the assumption in Theorem <ref> that there are at most r points of the first color is necessary.
Otherwise, one can consider the sequence S=(1,2,3,4,…, n, n+1) in ^1 where the first n elements are red
and the last element n+1 is blue. Then although the length of S can be arbitrary,
there are no three disjoint rainbow subsequences S_1, S_2, S_3 with 
S_1∩ S_2∩ S_3≠∅.
On the other hand, it is not true that this condition is necessary in every matroid. 
For example, consider the affine line over the field with two elements.



§ THE PROOF

We begin the proof by showing that Theorem <ref> implies
Theorem <ref>. 

The reduction of Theorem <ref> to Theorem <ref> 
follows a well known pattern, a similar reduction previously appeared in the proof 
of the optimal colored Tverberg theorem <cit.> or 
in Sarkaria's proof for the prime power Tverberg theorem <cit.>, 
see also de Longueville's exposition <cit.>.
Nevertheless, there are subtle differences because we are working in greater generality
and because we need to take algorithmic aspects into consideration.


Assume that the assumptions of Theorem <ref> are satisfied.
We show how to turn the sequence S and the matroid M with closure operator  into a sequence S' and matroid M'
with closure operator ' that satisfy the assumptions of Theorem <ref>.
Moreover, we construct S',M',' and the coloring of S' in a such way that 
the sets S_1:=S_1'∩ S, S_2:=S_2'∩ S, …, S_r:=S_r'∩ S
will satisfy ∅⊊(S_1)⊆(S_2)⊆…⊆(S_r)
iff and only if '∅⊊'(S'_1)⊆'(S'_2)⊆…⊆'(S'_r)
and the rainbowness of S_i' will imply that S_i is rainbow. 

Let m be the rank of M and d the number of colors used in S.
From the conditions follows that d-m≥ 0.

If the length of S is strictly larger than m(r-1)+1,  we throw the superfluous elements of S away. 
This does not add a point of any color, therefore all assumptions of Theorem <ref> remain preserved. 
So we may assume that the length of S is precisely m(r-1)+1.

We form M' from M by adding (d-m) new coloops[A coloop is an element x
that is independent on any set that does not contain x. In other words,
we form M' as the direct sum of M with the uniform matroid U_d-m^d-m.] x_1,…, x_d-m. 
Now we form the sequence S' by appending (x_1,x_1, …,x_1_(r-1)×, x_2,x_2, …,x_2_(r-1)×,…x_d-m, …, x_d-m_(r-1)) to S.

Clearly we can color the new elements of S'
so that in total there are exactly r points of the first color, and exactly r-1 points
of every other color.

We see that S', M' satisfy the assumptions of Theorem <ref>.
It follows that there are r rainbow subsequences S'_1,…, S'_r of S'
satisfying '∅⊊' S'_1⊆' S'_2⊆…⊆ S'_r.

Since the points x_i are coloops and since each one of them was added exactly (r-1)-times,
it follows that they cannot contribute to ⋂_i=1^r ' (S'_1).
Consequently, ⋂_i=1^r (S∩ S'_i)≠∅
and ∅⊊(S∩ S'_1)⊆(S∩ S'_2)⊆…⊆(S∩ S'_r).

We conclude that S_1:=S∩ S_1', S_2:=S∩ S_2', …, S_r:=S∩ S_r'
are the required subsequences of S.

Observe that the reduction is polynomial in r, m, u and |S|.



Now we can start with the proof of Theorem <ref>.
Here we describe the main idea. We let S_r be a rainbow independent subsequence of the maximal rank.
In an ideal case (S_r)=M and we may obtain the remaining 
subsequences S_1,…, S_r-1 by apply induction on the sequence S∖ S_r inside M.

However, we may be unlucky. It may happen that no such S_r
satisfies (S_r)=M, see Fig. <ref>.


We see that in this case
we could simply take the subsequence S'=(a_1,a_4,a_5,a_6,a_7)
and unify colors blue and red into one color (say violet).
Then S' lives in a submatroid of rank 1 and satisfies
the conditions of Theorem <ref>, so
we may use induction. We obtain subsequences S_1,S_2,S_3 of S'
satisfying ∅⊊(S_1)⊆(S_2)⊆(S_3).
These are clearly also subsequences of S.
Moreover they are not only rainbow in the violet-orange coloring,
but also in the original blue-orange-red coloring. 

In the proof we show that if (S_r)≠ M,
we may always resolve the situation by an analogous trick. 

Let us now carry out the technical details. Since we promised an algorithmic solution,
we describe an algorithm that finds the desired subsequences.

 First we compute m'= S. Since instead of S we can consider
 the subsequence S' formed by the elements
 colored by the first m' colors (while preserving all assumptions of Theorem <ref>), 
 we may assume that M=(S).
 
 Now we find an inclusion maximal independent rainbow subsequence RI_r of S.
 This can clearly be done in time polynomial in r, u, m and |S|.
 
 We will proceed in the proof by induction on the triple (r,m,m- RI_r) (in lexicographical ordering).
 If r=1 or m=1 the statement is trivial, so assume r>1, m>1.
 
 If m- RI_r=0, then (RI_r)=M.
 Because RI_r is rainbow, S∖ RI_r and M satisfy the assumptions of Theorem <ref>
 for r'=r-1 . By applying induction we obtain r-1 disjoint rainbow subsequences S_1,…, S_r-1 of S∖ RI_r
 with ∅⊊(S_1)⊆(S_2)⊆…⊆(S_r-1).
 If we now set S_r=RI_r we see that S_1,…, S_r are the desired disjoint rainbow subsequences
 with ∅⊊(S_1)⊆(S_2)⊆…⊆(S_r-1)⊆(S_r).
 
 Therefore we may assume that 
 
    (RI_r)⊊ M


 We would like to increase RI_r by adding a point of a color
 that is not yet used in RI_r. Unfortunately, this is not possible without replacing some
 points of RI_r first. Our algorithm uses a cycle to find out which points to replace and how.
 Within the cycle we need to keep track of “replacement rules” which makes this part a bit technical.
 Moreover, there are three possibilities what can occur at one iteration of the cycle:
 [label=*)]
 
  * either we construct a larger independent rainbow set RI_r, 
 
  * we find the desired sets S_1,…, S_r in a smaller submatroid, or
 
  * we adjust the replacement rules.
 
 
 

  
The cycle
 In the kth step (k=0,1,2,…) of the cycle the replacement rules consist of the following data:
 
  
  * set K_k of colors (this set corresponds to colors that we may use while replacing some points),
  
  * subsequence I_k of RI_r (eventually we would like to replace the subsequence I_k of RI_r by another sequence I_k^p),
  
  * for each element p whose color is in K_k and which does not lie in (I_k) a subsequence I_k^p of S
        (we want to replace I_k with I_k^p, hence increasing the length of our subsequence by one)
 
 To simplify the terminology, if T is a subsequence of S,
 let c(T) denote the set of all the colors used by elements of T.
 If U is a set of colors, let C_U be the subsequence of S
 formed by all elements with color from U.
 
We want the data to satisfy the following conditions:

 
  * c(I_k)⊊ K_k,
 
  * c(I_k^p)=c(I_k)∪{c_k^p} for some  c_k^p∈ K_k∖ c(RI_r),
 
  * |I_k^p|=|I_k|+1,
 
  * p∈ I_k^p and (I_k^p∖{p})=(I_k)
 
  * RI_r∩ C_K_k=I_k and K_k⊈c(RI_r)

Note that conditions <ref> and <ref> imply that I_k^p only contains
elements that have the same colors as points in I_k plus one additional point
that has color c_k^p, which is not yet present in RI_r.

The first step (k=0) is easy. We set I_0:=∅ and let K_0 be all the colors of S
except for those already used in RI_r. 
No element p∈ C_K_0 is contained in[C_K_0 are the elements of S whose
color lies in K_0 and we assume that S contains only non-loop elements.] (I_0)=∅,
so we need to define the set I_0^p for every such p. We simply put I_0^p:={p}.

Now we check that the above defined sets satisfy all the prescribed conditions.
Note that by (<ref>), S⊈(RI_r). 
This together with the fact that RI_r is independent
implies that |RI_r|<m. Since we have m colors, there is a color that is not used in RI_r. 
In other words, K_0 is nonempty.

Hence conditions <ref>–<ref> are satisfied trivially 
(with c_k^p=c(p) in condition <ref>).


So suppose that the sets K_k, I_k and I_k^p are already constructed. 
Since I_k⊆ RI_r there are three cases that may occur:

 
  * C_K_k⊆(I_k),
 
  * C_K_k⊈(RI_r) or
 
  * C_K_k⊆(RI_r) and C_K_k⊈(I_k).


We deal with the particular cases separately:


  §.§.§ Case <ref>: C_K_k⊆(I_k)

In this case, we may apply the trick we used for Fig. <ref>.
Let us describe it formally.

We set M':= I_k and m':=(I_k). M has rank m and by (<ref>) 
we know that M⊈(RI_r).
It follows that (RI_r)<m and since I_k⊆ RI_r, we also have m'=(I_k)<m. 

Condition <ref> implies c(I_k)⊊ K_k, so there is a point p∈ C_K_k∖ C_c(I_k).

Because I_k is rainbow and independent and I_k=m', c(I_k) has m' distinct elements,
say k_1,…, k_m'. We define S':=C_{k_1,…, k_m'}∪{p}.
In S' we recolor p and all points of color k_1 by a new color z.

Because S'⊆ C_K_k (we evaluate C_K_k with respect to the original coloring), 
the assumption C_K_k⊆(I_k) (Case <ref>) implies
that S' is a sequence of elements from M'. Also in S' there are m' colors, at least r elements of color z
and at least r-1 elements of all the remaining colors. 
Therefore, the assumptions of Theorem <ref> are satisfied
for m'<m. By induction we obtain the desired disjoint rainbow subsequences S_1,…, S_r of S' (which itself is a subsequence of S) 
with ∅⊊(S_1)⊆(S_2)⊆…⊆(S_r).
These subsequences are rainbow with respect to the new coloring of S'.
By the construction of the new coloring these subsequences
are also rainbow in the original coloring of S.



  §.§.§ Case <ref>: C_K_k⊈(RI_r)

In this case, we construct a new independent rainbow subsequence RI_r' with |RI_r'|=|RI_r|+1:
We pick a point p∈ C_K_k with p∉(RI_r) 
and set RI_r':=(RI_r∖ I_k)∪ I_k^p.

Before we show that such RI_r' is a rainbow independent subsequence 
of size |RI_r|+1, we prove 
the following auxiliary equality:

    (RI_r') = (RI_r∪{p}).


Indeed,

    (RI_r')    =   ((RI_r∖ I_k)∪ I_k^p) 
       =   ((RI_r∖ I_k)∪ (I_k^p∖{p})∪{p}),

where the last equality uses the fact that p∈ I_k^p from condition <ref>.
Because any closure operator  satisfies 

    (B∪ C) = (B∪ C)    for any two sets B,C⊆ M,

we may rewrite the expression further to

    (RI_r') = ((RI_r∖ I_k)∪(I_k^p∖{p})∪{p}).

By condition <ref> (I_k^p∖{p})=(I_k),
which reduces the equality to:

    (RI_r') =  ((RI_r∖ I_k)∪(I_k)∪{p}).

Using (<ref>) again, we obtain

    (RI_r')    =   ((RI_r∖ I_k)∪ I_k∪{p})

Since I_k⊆ RI_r, Equation (<ref>) follows.

Using the fact that I_k⊆ RI_r, 
we are now ready to verify that RI_r' is a rainbow independent subsequence with |RI_r'|=|RI_r|+1.




  * |RI_r'|=|RI_r|+1:
|RI_r'| = |(RI_r∖ I_k)∪ I_k^p|.
Because RI_r is rainbow, condition[c(I_k^p)= c(I_k) ∪{c_k^p}, for some c_k^p∈ K_k∖ c(RI_r)⊆ K_k∖ c(I_k)] <ref> implies
that the sequences RI_r∖ I_k and I_k^p do not share any color.
In particular, they are disjoint and |RI_r'|=|RI_r∖ I_k| + |I_k^p|.
Since |I_k^p|=|I_k|+1 (condition <ref>), |RI_r'| = |RI_r∖ I_k| + |I_k| + 1.
Because I_k⊆ RI_r, we have |RI_r'|= |RI_r| + 1.  

  * RI_r' is rainbow:
I_k^p contains one element of color that is not used in RI_r, otherwise it uses the same colors as I_k.
Because RI_r'=(RI_r∖ I_k)∪ I_k^p, we see that P'_r uses exactly |RI_r|+1 colors.
This, together with the previous item, yields that P'_r is rainbow.

  * RI_r' is independent:
From the equality (<ref>) we get (RI_r') = (RI_r ∪{p}).
Moreover, we have chosen a point p which satisfies p∉(RI_r), so (RI_r') =  RI_r + 1.
Since RI_r was independent and RI_r' has exactly one element more,
the independence of RI_r' follows.

Let RI_r” be an inclusion maximal independent rainbow subsequence of S
that contains RI_r'.
We may now start our algorithm again but this time we replace the maximal independent rainbow subset
RI_r by RI_r”.
We have decreased the quantity (m- C_r) and preserved m and r.
By induction we obtain the desired disjoint rainbow subsequences S_1,…, S_r with ∅⊊ S_1 ⊆ S_2⊆…⊆ S_r.






  §.§.§ Case <ref>: C_K_k⊆(RI_r) and C_K_k⊈(I_k)

In this case, we show how to construct sets K_k+1, I_k+1 and 
for every p∈ C_K_k+1 with p∉(I_k+1) we construct a subsequence I_k+1^p.

We choose I_k+1 to be any inclusion minimal subsequence I_k+1⊆ RI_r satisfying 

    C_K_k⊆ I_k+1.

Because we assume that C_K_k⊆(RI_r), such set I_k+1 does exist.
We further define 

    K_k+1:=K_k∪ c(I_k+1).


Before we construct I_k+1^p, we prove the following auxiliary claim:



    I_k⊊ I_k+1    and     I_k⊊ I_k+1.



By condition <ref>, I_k⊊ C_K_k.
By Eq. (<ref>), we have I_k ⊆ I_k+1.
By construction both I_k and I_k+1 are subsequences of the independent sequence 
RI_r which together with the preceding yields I_k⊆ I_k+1. 
Condition <ref> and the fact that we are in case <ref> yields
I_k⊆ C_K_k⊈ I_k.
Since also C_K_k⊆ I_k+1, we see that I_k+1≠ I_k and I_k+1≠ I_k.


Now we construct sets I_k+1^p for all points p∈ C_K_k+1 satisfying p∉ I_k+1.
Let p be such a point.
By definition of I_k+1, C_K_k⊆ I_k+1, so p cannot lie in C_K_k.
Equation (<ref>) implies c(p)∈(K_k+1∖ K_k) ⊆ c(I_k+1). 
Because I_k+1⊆ RI_r is a rainbow set[RI_r is rainbow!], there exists a unique element r∈ I_k+1 with c(r)=c(p).
Since we assume p∉ C_K_k, we have c(r)=c(p)∉ K_k⊇ c(I_k), where the last inclusion follows from condition <ref>.
In particular, c(r)∉ c(I_k), hence

    r∈ I_k+1∖ I_k.

Since I_k+1 is an inclusion minimal subsequence of RI_r for which C_K_k⊆ I_k+1,
there exists an element q∈ C_K_k such that 
q∉(I_k+1∖{r}). 
Since q∈ C_K_k⊆ I_k+1,
the exchange principle implies r∈((I_k+1∖{r})∪{q}).

It easily follows that

    I_k+1 = ((I_k+1∖{r})∪{q}).


Claim <ref> together with (<ref>) imply that I_k⊆ I_k+1∖{r}. Since q
was chosen to satisfy q∉(I_k+1∖{r}), we have q∉ I_k as well.
Together with q∈ C_K_k, this implies that I_k^q is defined.
We set[We note that I_k+1^p does depend on the choice of q, i.e.,
if we choose another q∈ C_K_k that satisfies q∉(I_k+1∖{r}),
we obtain a different set I_k+1^p.]

    I_k+1^p:=I_k+1∖(I_k∪{r})∪ I_k^q∪{p}.



It remains to show that our assignment satisfies conditions <ref>–<ref>.




  * Condition <ref>:
By (<ref>), we have c(I_k+1)⊆ K_k+1.
Condition <ref> implies that K_k contains a color that is not used in RI_r
and since I_k+1⊆ RI_r, which together with (<ref>) yields
K_k+1≠ c(I_k+1). Condition <ref> follows.

  * Condition <ref>:
Condition <ref> states that c(I_k^q)=c(I_k) ∪{c_k^q} for some c_k^q∈ K_k∖ RI_r, in particular
c(I_k)⊆ c(I_k^q). 
Together with the fact that elements p and r have the same color (c(p)=c(r)), (<ref>) yields 
c(I_k+1^p) = c(I_k+1∖ I_k)∪ c(I_k^q). If we now apply condition <ref> for I_k^q
and Claim <ref>, we see that c(I_k+1^p) = c(I_k+1) ∪{c_k+1^p}, where c_k+1^p = c_k^q.
Note that K_k⊆ K_k+1, hence c_k+1^p∈ K_k+1∖ c(RI_r). Condition <ref> follows.


  * Condition <ref>:
By definition I_k+1^p = I_k+1∖(I_k∪{r})∪ I_k^q ∪{p}.
Because I_k+1 is a subset of the rainbow set RI_r, I_k+1 is itself rainbow.
Together with c(I_k^q) = c(I_k) ∪{c_k^q}, where c_k^q∉ c(RI_r)⊇ c(I_k+1),
this implies that the sets I_k+1∖ I_k and I_k^q are disjoint. 
Since r∈ I_k+1∖ I_k (Equation (<ref>)), c(p)=c(r)∈ c(I_k+1)∖ c(I_k) and c(I_k^q)∩ c(RI_r)=c(I_k) (conditions <ref> and <ref>),
we have p,r∉ I_k^q and p,r∉ I_k.
From p∉ I_k+1 follows p∉ I_k+1. Since r∈ I_k+1,
we have |I_k+1^p| = |I_k+1∖ I_k| - |{r}| + |{p}| + |I_k^q| = |I_k+1∖ I_k| + |I_k| + 1,
where the last equality uses the induction hypothesis for k.
Claim <ref> then yields |I_k+1^p|=|I_k+1| + 1 as desired.


  * Condition <ref>:
By definition ((<ref>)) p∈ I_k+1^p, so we only need to verify that (I_k+1^p∖{p})) =  I_k+1.
Let us compute.
Using the fact that q∈ I_k^q from condition <ref> and (<ref>)
we may rewrite (I_k+1^p∖{p}) as follows:

    (I_k+1^p∖{p})    =   ((I_k+1∖ (I_k∪{r}))∪ I_k^q)
       =   ((I_k+1∖ (I_k∪{r}))∪ (I_k^q∖{q}∪{q}))
       =   ((I_k+1∖ (I_k∪{r}))∪(I_k^q∖{q})∪{q}).

Now we use condition <ref> for k ((I_k^q∖{q})=  I_k). We obtain

    (I_k+1^p∖{p}) 
        =   ((I_k+1∖ (I_k∪{r})∪(I_k)∪{q})
       =   ((I_k+1∖{r})∪{q})
       =    I_k+1,

where the last equality follows from (<ref>).


  * Condition <ref>:
By definition K_k+1=K_k∪ c(I_k+1). This implies C_K_k+1 = C_K_k∪ C_c(I_k+1).
Hence RI_r ∩ C_K_k+1 = (RI_r∩ C_K_k)∪ (RI_r∩ C_c(I_k+1)).
By the induction assumption RI_r∩ C_K_k=I_k. Because RI_r⊇ I_k+1 is rainbow,
RI_r∩ C_c(I_k+1)=I_k+1. Claim <ref> then implies RI_r∩ C_K_k+1=I_k+1 as desired.
Because K_k⊈c(RI_r) and K_k⊆ K_k+1, we have K_k+1⊈c(RI_r) as well.

It follows that we may increase k and continue in the loop.

In each step of the cycle we either terminate and output the desired subsequences,
or we construct a sequence I_k+1 whose rank is strictly larger than the rank of I_k (Claim <ref>).
Since the rank of I_k+1 is from above bounded by (M) it follows that
the loop terminates after at most (M) iterations.

Verifying that all other steps can be done in time polynomial in r, m, u and |S| and 
that they are repeated only polynomial number of times is easy.




§ OPEN PROBLEMS

Rota basis conjecture <cit.> is a well known problem in matroid theory which has a close connection to our
colorful matroidal Tverberg's theorem. Let us restate it so that the similarity is clearly visible.

Let M be a matroid of rank m. Let S be a sequence of m^2 elements colored
by m colors such that points of each color form a basis.
Do there always exist m pairwise disjoint rainbow subsequences S_1,…, S_m of S
with S_1= S_2=… =  S_r=M?

In its full generality the conjecture has only been verified for m=1,2,3 <cit.>.
The conjecture is also known to be true in several special cases <cit.>.
Proof of Theorem <ref> indicates the difficulties that appear if one
tries to prove Rota's basis conjecture purely combinatorially.


GMP+16

[BGR15]anotherMatroidalTverberg
I. Bárány, Kalai G., and Meshulam R.
A Tverberg type theorem for matroids.
ArXiv e-prints, 2015.
Available online at <http://arxiv.org/abs/1607.01599>.

[BMZ15]Blagojevic:Optimal_Tverberg
P. V. M. Blagojević, B. Matschke, and G. M. Ziegler.
Optimal bounds for the colored Tverberg problem.
J. Eur. Math. Soc., 17(4):739–754, 2015.

[Cha95]chan-1995
W. Chan.
An exchange property of matroid.
Discrete Mathematics, 146(1):299 – 302, 1995.

[dL02]deLongueville:exposition
M. de Longueville.
Erratum to: “Notes on the topological Tverberg theorem”.
Discrete Math., 247(1-3):271–297, 2002.

[Fri15]Frick
F. Frick.
Counterexamples to the topological Tverberg conjecture.
ArXiv e-prints, 2015.
Available online at <http://arxiv.org/abs/1502.00947>.

[GH06]Geelen-2006
J. Geelen and P. J. Humphries.
Rota's basis conjecture for paving matroids.
SIAM J. Discrete Math., 20(4):1042–1045, 2006.

[Gly10]Glynn-2010
D. G. Glynn.
The conjectures of Alon–Tarsi and Rota in dimension prime minus
  one.
24(2):394–399, 2010.

[GMP+15]ourKuhnel
X. Goaoc, I. Mabillard, P. Paták, Z. Patáková, M. Tancer, and U. Wagner.
On generalized Heawood inequalities for manifolds: a Van
  Kampen-Flores-type nonembeddability result.
Extended abstract in Proceedings of SoCG'15, 2015.

[GMP+16]ourKuhnelArXiv
X. Goaoc, I. Mabillard, P. Paták, Z. Patáková, M. Tancer, and U. Wagner.
On generalized Heawood inequalities for manifolds: a Van
  Kampen-Flores-type nonembeddability result.
preprint on arXiv:, 2016.

[HR94]rota-1994
R. Huang and G.-C. Rota.
On the relations of various conjectures on latin squares and
  straightening coefficients.
Discrete Mathematics, 128(1):225 – 236, 1994.

[MW14]Mabillard
I. Mabillard and U. Wagner.
Eliminating Tverberg points, I. An Analogue of the Whitney
  trick.
Proceedings of the Thirtieth Annual Symposium on Computational
  Geometry (New York, NY, USA), SOCG'14, ACM, pages 171–180, 2014.

[MW15]Uli:TverbergThree
I. Mabillard and U. Wagner.
Eliminating Higher-Multiplicity Intersections, III.
  Codimension 2.
preprint on arXiv: 1601.00876, 2015.

[Onn97]Onn-1997
S. Onn.
A colorful determinantal identity, a conjecture of Rota, and
  Latin squares.
104(2):156–159, February 1997.

[Öza87]Ozaydin:Tverberg
M. Özaydin.
Equivariant maps for the symmetric group.
Unpublished manuscript, 1987.
Available online at <http://digital.library.wisc.edu/>
  <1793/63829>.

[Pat15]patak:thesis
P. Paták.
Using algebra in geometry.
PhD thesis, Charles University, 2015.
avaible online at <http://kam.mff.cuni.cz/ patak/thesis.pdf>.

[Sar00]Sarkaria:Tverberg
K. S. Sarkaria.
Tverberg partitions and Borsuk-Ulam theorems.
Pacific J. Math., 196(1):231–241, 2000.

[Tve66]Tverberg
H. Tverberg.
A generalization of Radon's theorem.
J. London Math. Soc., 41:123–128, 1966.






