\documentclass[12pt]{article} \usepackage{e-jc} %\documentclass[a4paper]{article} %%%% Packages %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage{a4} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amscd} \usepackage{amsthm} \usepackage{epsfig} %\usepackage[all]{xy} \usepackage{color} \usepackage{bbm} \usepackage{graphicx} %\usepackage{psfrag} \usepackage{hyperref} \usepackage{enumerate} \usepackage{multirow} %% zeigt die labels an %\usepackage{showkeys} %%%% Raender, Farben, .... %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% keine Absatz einruecken %\setlength{\parindent}{0em} %%% Absatzabstand verkleinern %\setlength{\parskip}{0.1ex} %\setlength{\baselineskip}{0.1ex} %%% Box-Raender: Dicke setzen \setlength{\fboxrule}{1.2pt} %%% Farben definieren %\definecolor{gruen}{rgb}{0,.9,.3} %%%%% Abkuerzungen, ... einlesen %%%%%%%%%%%%%%%%%%%%%%%%%%%% %\include{kommandos} %%% Zahlen \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} %%% Beweis \newcommand{\bprf}{\begin{proof}[Proof]} \newcommand{\eprf}{\end{proof}} %%%% Nummerierung fortlaufend: Chapter.Section.Nr_in_section \newtheorem{thm}{Theorem} \newtheorem{obs}[thm]{Observation} \newtheorem{conj}[thm]{Conjecture} \newtheorem{cor}[thm]{Corollary} \newtheorem{prop}[thm]{Proposition} \newtheorem{lem}[thm]{Lemma} \theoremstyle{definition} \newtheorem{rem}[thm]{Remark} %%%%% Dokumentanfang %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \title{On the number of colored Birch and \\Tverberg partitions} \author{{\Large Stephan Hell} } %\date{\today} \maketitle %\color{cyan} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{abstract} In 2009, Blagojevi\'c, Matschke \& Ziegler established the first tight colored Tverberg theorem. We develop a colored version of our previous results (2008): Evenness and non-trivial lower bounds for the number of colored Tverberg partitions. Both properties follow from similar results on the number of colored Birch partitions. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{section}{Introduction}\label{sec-intro} In 1966, Tverberg~\cite{tverberg66:_theor} showed that any $(d+1)(r-1)+1$ points in $d$-dimensional space $\R^d$ can be partitioned into $r$ blocks whose convex hulls have a non-empty intersection. This result is known as {\it Tverberg's theorem}, and it has several proofs, and many generalizations, see Matou\v{s}ek~\cite[Sect.~6.5]{matou03:_using_borsuk_ulam} for details. The first {\it colored Tverberg theorem} is due to B\'ar\'any \& Larman~\cite{barany92}; see Ziegler \cite{z11:_col-tvp_ams} for a recent account of the story. In 2009, Blagojevi\'c, Matschke \& Ziegler~\cite{bmz10:_col-tp} established an {\it optimal} colored Tverberg theorem. Since then, their results have been reproved by themselves~\cite{bmz11:_col-tvp}, Matou\v{s}ek, Tancer \& Wagner~\cite{mtw11:_col-geom-ctvp}, and Vre\'{c}ica \& \v{Z}ivaljevi\'c~\cite{vrecica-zival-11:chessboard}. \begin{thm}[{\cite[Thm~2.2]{bmz10:_col-tp}}]\label{thm-ctv-bmz11}Let $d \geq 1$, $r \geq 2$ prime, $N:=(d+1)(r-1)$, and $f:\Delta_N\rightarrow \R^d$ continuous, where the $N+1$ vertices of the simplex $\Delta_N$ have $d+2$ different colors, and the color classes satisfy $|C_0|=|C_1|=\ldots=|C_d|=r-1$ and $|C_{d+1}|=1$. Then $\Delta_N$ has $r$ disjoint faces $F_1,F_2,\ldots,F_r$ satisfying: \[ |F_i\cap C_j|\leq 1\text{ for every }i\in\{1,\ldots,r\},j\in\{0,\ldots,d+1\}\text{, and }\bigcap_{i=1}^r f(F_i) \not = \emptyset.\] \end{thm} Faces satisfying the left condition are called {\it rainbow} faces. Any point in the intersection is called a {\it colored Tverberg point}. In the following, we focus on the case when $f$ is an {\it affine} map. In this case, one can think of the set $f({\rm vert}(\Delta_N))\subset\R^d$ as $N+1$ colored points satisfying the above color condition which can be partitioned into $r$ rainbow partition blocks $B_1,B_2,\ldots,B_r$, where $B_i=f({\rm vert}(F_i))$ for all $i$, such that their convex hulls intersect: \[ \bigcap_{i=1}^r \text{conv} (B_i) \not = \emptyset.\] Both Tverberg's theorem, and Theorem~\ref{thm-ctv-bmz11} settle the existence of one (!) partition. In the uncolored case, Sierksma conjectured that there are at least $((r-1)!)^d$ unordered partitions based on a particular point configuration; see~\cite{matou03:_using_borsuk_ulam}. This conjecture is open for $d\geq 2$. {\it Lower bounds} for the number of Tverberg partitions have first been obtained by Vu\'ci\'c \& \v{Z}ivaljevi\'c~\cite{vz93:_notes_sierk} when $r$ is prime, and by the author~\cite{hell07:_tverb} when $r$ is a prime power. Then the first lower bound was shown that holds for arbitrary $r$ in~\cite{hell08:_birch}. Up to now, no non-trivial lower bounds have been known in the colored case, not even a good conjecture. This is what we provide here: {\it Existence implies lower bounds for the number of colored Tverberg partitions.} Here, a set of points is in {\it general position} if no $k+2$ points are on a common $k$-dimensional affine subspace. \begin{thm}\label{thm-num-ctv}Let $d \geq 1$, $r \geq 2$ prime, $N:=(d+1)(r-1)$, and $f:\Delta_N\rightarrow \R^d$ affine, where the $N+1$ vertices of $\Delta_N$ have $d+2$ different colors, and the color classes satisfy: $|C_0|=|C_1|=\ldots=|C_d|=r-1$ and $|C_{d+1}|=1$. Then the number of unordered colored Tverberg partitions $T_r(f)$ satisfies the following four properties: \begin{enumerate}[\rm (i)] \item\label{it-ctv-even}Parity: $T_r(f)$ is even for $r\geq 2d+2$. \item\label{it-ctv-lower-d1}Tight lower bound for $d=1$: $T_r(f)\geq \lceil \frac{r-1}{2}\rceil ! \cdot \lfloor \frac{r-1}{2}\rfloor !$ \item\label{it-ctv-lower-plane}Lower bound (planar case): $T_r(f)\geq 8\cdot 3^{r-8}$, for $d=2$ and $r\geq 8$. \item\label{it-ctv-lower}Lower bound (general case): $T_r(f) \geq 2^{r-2d-1}$, for $d \geq 2$ and $r\geq 2d+2$. \end{enumerate} \end{thm} The proof of (\ref{it-ctv-lower-d1}) is an easy exercise. Furthermore, we will see that: \begin{enumerate} \item The assumption $r$ prime is needed for the existence of at least one partition. Alternatively, $r$ arbitrary and $T_r(f)>0$ are sufficient conditions. \item Any lower bound $\ell$ on the number of colored Tverberg points for a given map~$f$ improves our lower bounds for the number of colored Tverberg partitions by a factor of $\ell$. \item Computer experiments indicate that the lower bounds for $d>1$ are far from being optimal. \end{enumerate} In Section~\ref{sec-proof-ctv}, we introduce the concept of colored Birch partitions, then we come up with our second main result (Theorem~\ref{thm-num-cbp}): Properties for the number of colored Birch partitions. These properties imply Theorem~\ref{thm-num-ctv}, similar to the proof of its uncolored version in~\cite{hell08:_birch}. Section~\ref{sec-proof-cbp} comes with a proof of Theorem~\ref{thm-num-cbp}. In Section~\ref{sec-rem}, we compare the outcome of different approaches aiming for potential minimal point configurations. \end{section} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{section}{Reduction to colored Birch partitions}\label{sec-proof-ctv} Assuming that the $(d+1)(r-1)+1$ points of Theorem~\ref{thm-ctv-bmz11} are in general position, the partition blocks consist of at most $d+1$ points. One possible solution is a single point that lies in the convex hulls of $r-1$ many $(d+1)$-element sets. The other extreme case would be $d$ partition blocks of exactly (!) $d$ points each, intersecting in a single point, plus $r-d$ many $(d+1)$-element sets that all contain the intersection point, where $d\leq r$. In all cases, we have at least $r-d-1$ many $(d+1)$-element sets $B_1, B_2,\ldots , B_{r-d-1}$ which (i) contain a common point in their convex hulls, and which (ii) are rainbow sets in the following way: each of them contains each of the colors $0,1,\ldots, d$ exactly once, that is, $|B_i\cap C_j|=1$ for all $0\leq j\leq d$ and all $1\leq i \leq r-d-1$. This observation leads to the concept of colored Birch partitions. {\bf Definition.} Let $p\in\R^d$ be a point, and $k\geq 1$ a natural number. Given a set X of $k(d+1)$ colored points in $\R^d$ of $d+1$ different colors such that each color class $C_0,C_1,\ldots, C_d$ contains exactly $k$ points, we call a partition $B_1,B_2,\ldots,B_k$ a {\it colored Birch partition of $X$ to the point $p$} if each block $B_i$ contains exactly $d+1$ points, uses every color exactly once, and contains $p$ in its convex hull. Let $\text{cBP}_k(X)$ be the number of all unordered colored Birch partitions of $X$ to $p$. Again, {\it unordered} means that two partitions are regarded as the same if one can be obtained from the other by a permutation of the $k$ partition blocks. The partitions in the first paragraph are examples of colored Birch partitions to the single point resp.~the intersection point. Placing $p$ outside the convex hull of $X$ one gets $\text{cBP}_k(X)=0$. Let us formulate our second main result. \begin{thm}\label{thm-num-cbp}For $d\geq 1$, let $p\in\R^d$ be a point, and $k\geq 1$ a natural number. For any set X of $k(d+1)$ colored points in $\R^d$ of $d+1$ different colors such that each color class $C_0,C_1,\ldots, C_d$ contains exactly $k$ points, and $X\cup\{p\}$ in general position, the number of colored Birch partitions $\text{cBP}_k(X)$ has the following four properties: \begin{enumerate}[\rm (i)] \item\label{it-cb-even}$\text{cBP}_k(X)$ is even for $k\geq d+2$. \item\label{it-cb-lower-d1}$\text{cBP}_k(X)>0\,\,\Longrightarrow\,\,\text{cBP}_k(X)\geq \lceil \frac{k}{2}\rceil ! \cdot \lfloor \frac{k}{2}\rfloor !$ for $d=1$. \item\label{it-cb-lower-plane}$\text{cBP}_k(X)>0\,\,\Longrightarrow\,\,\text{cBP}_k(X)\geq 8\cdot 3^{k-6}$ for $d=2$ and $k\geq 6$. \item\label{it-cb-lower}$\text{cBP}_k(X)>0\,\,\Longrightarrow\,\,\text{cBP}_k(X)\geq 2^{k-d-1}$ for $d \geq 2$ and $k\geq d+2$. \end{enumerate} \end{thm} Computer experiments for dimensions 2, and 3 show that the lower bounds (\ref{it-cb-lower-plane}) and (\ref{it-cb-lower}) are tight: For $4\leq k \leq 9$ in dimension 2, and for $5\leq k \leq 8$ in dimension~3. In Figure~\ref{fig-bp}, an example for tightness where $d=2$, and $k=4$ is given.\vspace{0.5ex} {\bf Example 1.} The condition $k\geq d+2$ in Property~(\ref{it-cb-even}) is necessary as our computer experiments came up with counter-examples for $d=2,3,4$, and $k=d+1$. Here, we construct a planar set $X$ such that ${cBP}_3(X)$ is odd. In the planar setting, a point configuration can be represented as a colored word of length $3k$ on the alphabet $\{+,-\}$: Choose a line through $p$. This line hits at most one point from $X$, and it divides the plane into two half-spaces. Choose one of the two half-spaces. Then sweep the line through $p$ over the chosen half-space counter-clockwise. The ray hits all points exactly once, and the sweeping leads to a linear order on the points in $X$. This determines a colored word of length $3k$ on the alphabet $\{+,-\}$ in the following way: Write for every point of $X$ the letter $+$ when the line hits a point in the chosen half-space, and $-$ in the other case. While writing the letters, keep for each letter track of its color. Every possibility of partitioning a colored word of length $3k$ into $k$ colored subwords of the form $+-+$, or $-+-$ corresponds one-to-one to a colored Birch partition of $X$. One can check that the alternating word $+-+-+-+-+$ of length $9$ with a cyclic coloring $0,1,2,0,1,2,0,1,2$ corresponds to a colored point configuration with $\text{cBP}_3(X)=3$ being odd. Namely, one partition is $\{0,1,2\}, \{3,4,5\}, \{6,7,8\}$, where the letters are numbered from left to right. The other two are $\{0,1,8\},\{2,3,4\},\{5,6,7\}$, and $\{0,7,8\},\{1,2,3\},\{4,5,6\}$.\vspace{0.5ex} \begin{figure} \centering \includegraphics[width=9cm]{bild-k12-2zerl} \caption{Planar example for $k=4$ showing tightness of the lower bounds~(\ref{it-cb-lower}).} \label{fig-bp} \end{figure} {\bf Example 2.} It is a natural question to ask whether there is a topological version of Theorem~\ref{thm-num-cbp}. As in the case of the colored Tverberg theorem, the colored points in $\R^d$ can be seen as images of an affine map $f:\Delta_{k(d+1)}\rightarrow \R^d$. The definition of $\text{cBP}_k(f)$ can be adapted to continuous maps in a straightforward way. We construct a continuous example $\tilde{f}$ showing that $\text{cBP}_k(\tilde{f})=1$ for any $k$. Start with a set $X$ of colored points such that its convex hull does not contain~$p$. Then $\text{cBP}_k(X)=0$. $X$ determines an affine map $f:\Delta_{k(d+1)}\rightarrow \R^d$ uniquely. Choose a partition of the vertex set of $\Delta_{k(d+1)}$ into rainbow $d$-simplices $B_1, \ldots, B_k$. Modify $f$ in the interior of every simplex $B_i$ such that its image hits the point $p$. Our modified map $\tilde{f}$ has by construction the colored Birch partition $B_1, \ldots, B_k$. Any other way of partitioning of $\Delta_{k(d+1)}$ comes with at least one $d$-simplex for which $\tilde{f}$ has not been modified. Therefore $\text{cBP}_k(\tilde{f})=1$.\vspace{0.5ex} First we prove Theorem~\ref{thm-num-ctv} using Theorem~\ref{thm-num-cbp}. A proof of Theorem~\ref{thm-num-cbp} is given in the next section. \begin{proof}[Proof of Theorem~\ref{thm-num-ctv}] The existence of at least one colored Tverberg partitions follows from Theorem~\ref{thm-ctv-bmz11}. In the worst case, the partition consists of $d$ partition blocks of exactly $d$ points each, intersecting in a single point, plus $r-d$ many $(d+1)$-element sets $B_1, B_2,\ldots , B_{r-d}$ that all contain the intersection point in their convex hulls; here we need $r \geq d$. The first $d+1$ colors show up exactly $r-d$ times if the unique point of color $d+1$ does not end up in one of the $B_i$'s. In that case, this single point is recolored with the unique color showing up $r-d-1$ times. In both cases, each property of $T_r(f)$ follows directly from the corresponding property for colored Birch partitions for $k=r-d$ given in Theorem~\ref{thm-num-cbp}. \end{proof} \end{section} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{section}{Proof of Theorem~\ref{thm-num-cbp}}\label{sec-proof-cbp} Property~(\ref{it-cb-lower-d1}) is an easy exercise. We first prove Property~(\ref{it-cb-even}) inductively; here the key part is the base case $k=d+2$. In a second step, we show that Property~(\ref{it-cb-even}) implies Properties~(\ref{it-cb-lower-plane}) and~(\ref{it-cb-lower}). {\bf Prerequisites:} We will use an approach similar to the uncolored case in~\cite{hell08:_birch}: One of our points will be moved while all the others remain fixed. During this moving process, we will keep track of the parity for the number of colored Birch partitions. In the following, we assume $d\geq 2$. Let $k\geq 2$, fix $p$ to be the origin $o\in\R^d$, and assume without restriction that all $k(d+1)$ colored points of $X$ are on the unit sphere $S^{d-1}\subset \R^d$. If all points lie in the northern hemisphere of $S^{d-1}$, then $\text{cBP}_{k}(X)=0$, as the origin is not in the convex hull of $X$. Below we do the following: We move one colored point $q$ while fixing all others. Let $q$ be a point of $X$. Instead of looking at $q$, we follow its antipode $-q$ as for any $d$-element subset $S\subset X\setminus\{ q\}$, one has: \begin{eqnarray*} o\in\text{conv} (S\cup\{q\}) \;\Longleftrightarrow\; -q\in\text{cone}(S). \end{eqnarray*} From now on, we restrict ourselves to $d$-element subsets $S\subset X$ such that $S\cup \{q\}$ is rainbow. Every $d$-element subset $S$ defines a cone in $\R^d$, all these cones decompose the sphere $S^{d-1}\subset \R^d$ into cells. As long as $-q$ moves inside one of these cells, $\text{cBP}_{k}(X)$ does not change. At some point, we are forced to move $-q$ from one cell to another. At that point $\text{cBP}_{k}(X)$ might change. A boundary hyperplane of a cell is defined through a $(d-1)$-element subset $H\subset S$. Our moving procedure can be chosen so that our cell decomposition is nice, and that $-q$ crosses a boundary hyperplane of the cell in a transversal way. Before looking at colored Birch partitions, let's look at the set $\cal A$ of all rainbow $d$-simplices containing the origin. If $-q$ crosses a hyperplane defined through a subset $H$, then $\cal A$ might change. Let $H'=H\cup\{q\}$. For all colored simplices that do not contain $H'$ as a face, nothing changes. For the other simplices $\Delta$ the following property switches: \begin{eqnarray}\label{crossing} o\in\text{conv} (\Delta) \text{ before the crossing.}\;\Longleftrightarrow \; o\not\in\text{conv}(\Delta)\text{ afterwards.} \end{eqnarray} A colored Birch partition of $X$ consists of $k$ disjoint rainbow $d$-simplices containing the origin. If $-q$ crosses a hyperplane defined through $H\subset X$, then some colored Birch partitions vanish, and new colored Birch partitions come up. In fact, all Birch partitions, that include a simplex $\Delta$, $H'\subset\Delta$, which contains the origin before the crossing, vanish. The new ones include a simplex $\Delta$, $H'\subset\Delta$, which contains the origin after the crossing, but only if $X\setminus\Delta$ admits a colored Birch partition into $k-1$ partition blocks. In our proof, we need a special case of Deza et al.~\cite[Theorem~3.5]{deza06:_colour} which we reprove to make the reader familiar with the argument used below. \begin{lem}[{\cite[Theorem~3.5]{deza06:_colour}}]\label{lem-key} For $d\geq 2$, and a given set X of $2(d+1)$ colored points in $\R^d$ of $d+1$ different colors such that each color occurs exactly twice, the number of colored $d$-simplices containing the origin is even. \end{lem} \bprf Let $X=\{p_0,p_1,\ldots,p_{2d+1}\}$ such that the points $p_{2i}$, and $p_{2i+1}$ are of color $i$, for all $0\leq i\leq d$. Without restriction, we choose $q=p_0$, and the boundary hyperplane of our cell spanned by $H=\{p_2,p_4,\ldots,p_{2(d-1)}\}$. If $-q$ crosses the hyperplane through $H$, then exactly two colored $d$-simplices $\{p_0,p_2,\ldots,p_{2(d-1)},p_{2d}\}$, and $\{p_0,p_2,\ldots,p_{2(d-1)},p_{2d+1}\}$ are affected as observed in~(\ref{crossing}). In any case, the parity for the number of colored $d$-simplices containing the origin does not change. \eprf \begin{proof}[\bf Proof of Theorem~\ref{thm-num-cbp}, Property~(\ref{it-cb-even})] This follows -- as in the uncolored case -- via induction from its base case $k=d+2$. Let $k\geq d+3$, and $x$ a point of color 0. Let $B_1,B_2,\ldots,B_l$ be all rainbow $d$-simplices containing the origin, and using the point $x$. For every $i\in [l]$ the set $X\setminus B_i$ has an even number of colored Birch partitions by assumption. Adding up all these even numbers leads to $\text{cBP}_k(X)$. Let $k=d+2$, and $X$ be our set of $(d+1)(d+2)$ colored points. We will repeat the following step $d$ times, and then we will finally apply Lemma~\ref{lem-key} to complete our proof.\\ {\bf Step 1:} Let $q$ be a point of $X$, and the boundary hyperplane -- that is crossed transversally -- be spanned by a rainbow set $H_1$. Assume without restriction that in $H_1\cup\{q\}$ the $d$ colors $0,1,2,\ldots,d-1$ show up. For every $s\in C_d$, the colored $d$-simplex $H_1\cup\{q,s\}$ will change its property of containing the origin -- as observed in~(\ref{crossing}) -- so that some colored Birch partitions vanish, and new ones come up. Again, new ones come up if the rest admits a colored Birch partition into $d+1$ blocks. To prove the evenness of $\text{cBP}_{d+2}(X)$ it is sufficient to show that \begin{eqnarray}\label{hilfslemma} \text{$\text{cBP}_{d+1}(X_1)=\sum_{s\in C_{d}^1} \text{cBP}_{d+1}(X_1\setminus \{s\})$ is even.} \end{eqnarray} Here, the set $X_1=X\setminus H_1$ consists of $(d+1)^2+1$ points: The $d$ new color classes $C_0$ to $C_{d-1}$ are of size $d+1$, and color class $C_d$ of size $d+2$. Therefore, the expression $\text{cBP}_{d+1}(X_1)$ stands for the sum over the $d+2$ possibilities to drop one of the $d+2$ points of color $d$ from $X_1$. Define the new color classes $C_i^1$ to be $C_i$ minus the point of color $i$ in $H_1\cup\{q_1\}$, for $0\leq i\leq d$. In Step 1, we have reduced the partition parameter $k$ from $d+2$ to $d+1$ by $1$, and the number of points from $(d+1)(d+2)$ to $(d+1)^2+1$ by~$d$. In repeating this step $d$ times, we will end up with $k=d+2-d=2$, and $(d+1)(d+2)-d^2=3d+2$ many points. Finally, the color class $C^d_0$ will be of size $2$, and $C^d_1$ to $C^d_d$ of size $3$.\\ {\bf General Step $i$, $2\leq i\leq d$:} Assume that we have reduced our problem to showing that \[ \text{cBP}_{d+3-i} (X_{i-1}) = \sum_{s_1\in C^{i-1}_d,s_2\in C^{i-1}_{d-1},\ldots,s_{i-1}\in C^{i-1}_{d-i+2}} \text{cBP}_{d+3-i}\left( X_{i-1}\setminus \{ s_1,s_2,\ldots,s_{i-1} \} \right) \] is even, where $X_{i-1}$ has color classes $C^{i-1}_0,C^{i-1}_1,\ldots, C^{i-1}_d$ such that $|C^{i-1}_j|=d+4-i$ for $j\geq d-i+2$, and $|C^{i-1}_j|=d+3-i$ otherwise. Let $q_i$ be a point of $X_{i-1}$, and the boundary hyperplane -- that is crossed transversally -- be spanned by a subset $H_{i}$ of $X_{i-1}$ such that $G_i=H_i\cup\{q_i\}$ is rainbow. $G_i$ is a $d$-element set, and the number of colors is $d+1$. We distinguish two cases: %\begin{enumerate}[{Case (i},1)] %\item\label{fall1} $G_i\cap C^{i-1}_{d-i+2}=\emptyset$. %\item\label{fall2} $G_i\cap C^{i-1}_{d-i+2}=\emptyset$. %\end{enumerate} \begin{enumerate}[{Case (i},1)] \item\label{fall1} $G_i\cap C^{i-1}_{j_1}=\emptyset$ for $j_1\in [d-i+2,d]$. \item\label{fall2} $G_i\cap C^{i-1}_{j_2}=\emptyset$ for $j_2\in [0,d-i+1]$. \end{enumerate} In Case~(i,\ref{fall1}), one of the larger color classes $C_{j_1}^{i-1}$ misses $G_i$, and in the other case, one of the smaller color classes $C^{i-1}_{j_2}$. As our arguments are independent of $j_1$, $j_2$, and of the order in which they show up, we assume without restriction that $j_1=d-i+2$, and $j_2=d-i+1$. This assumption simplifies our notation. In Case~(i,\ref{fall1}), we show that a pairing for the colored Birch partitions shows up: For every point $r\in C^{i-1}_{d-i+2}$, the property of containing the origin changes for the colored $d$-simplices $G_i\cup \{r\}$ while $q_i$ crosses the hyperplane through $H_i$, due to~(\ref{crossing}). A $d$-simplex $G_i\cup \{r\}$ contributes to the number of colored Birch partitions if the rest admits a Birch partition into $d+2-i$ blocks. The latter property is independent of the current moving process. In fact, $G_i\cup \{r\}$ contributes a summand to \[\text{cBP}_{d+3-i}\left( X_{i-1}\setminus \{ s_1,s_2,\ldots s_{i-2},s_{i-1} \} \right), \] where $s_1\in C^{i-1}_d,s_2\in C^{i-1}_{d-1},\ldots,s_{i-1}\in C^{i-1}_{d-i+2}$, and $r\not=s_{i-1}$, in a positive, or negative way. This contribution can be concretized to be \[\text{cBP}_{d+2-i}\left( X_{i-1}\setminus (G_i\cup\{ s_1,s_2,\ldots,s_{i-1},r \}) \right). \] But the same contribution shows up for the colored $d$-simplex $G_i\cup \{s_{i-1}\}$ in the summand \[\text{cBP}_{d+3-i}\left( X_{i-1}\setminus \{ s_1,s_2,\ldots,s_{i-2},r \} \right), \] again in a positive, or negative way. In any case, the parity of $\text{cBP}_{d+3-i}(X_{i-1})$ remains unchanged. In Case~(i,\ref{fall2}), let $r$ be the unique point in $G_i\cap C^{i-1}_{d-i+2}$. Then all summands \[\text{cBP}_{d+3-i}\left( X_{i-1}\setminus \{ s_1,s_2,\ldots,s_{i-2},r \} \right) \] do not change, as any colored $d$-simplex not containing $G_i$ is not affected. We fix a point $s\in C^{i-1}_{d-i+2}$, such that $s\not= r$. For every point $t\in C_{d-i+1}^{i-1}$, the property of containing the origin changes for the colored $d$-simplex $G_i\cup \{t\}$, when $q_i$ crosses the hyperplane through $H_i$. Every simplex $G_i\cup \{t\}$ contributes \[\text{cBP}_{d+2-i}\left( X_{i-1}\setminus (G_i\cup \{s,t\})\right)\] to $\text{cBP}_{d+3-i}\left( X_{i-1}\setminus \{s\}\right)$ in a positive, or negative way. %Note that the expression above is a sum. %for d>2 ??? Hence, it is sufficient for Case~(i,\ref{fall2}) to show that all these contributions sum up to an even number: \[\text{cBP}_{d+2-i}(X_i)= \sum_{s_1\in C^{i}_d,s_2\in C^{i}_{d-1},\ldots,s_{i}\in C^{i}_{d-i+1}}\ \text{cBP}_{d+2-i}\left( X_{i}\setminus \{ s_1,s_2,\ldots,s_{i} \} \right), \] where $X_i=X_{i-1}\setminus G_i$. $X_i$ has color classes $C^i_j$, where $C^i_j$ is obtained from $C^{i-1}_j$ by deleting the point of color $j$ in $G_i$ for all $0\leq j\leq d$. Note that $|C^i_j|=d+3-i$, for $j\geq d-i+1$; otherwise $|C^i_j|=d+2-i$. Case~(i,\ref{fall2}) of Step $i$ reduces our original problem in the following way: The parameter $k=d+3-i$ is reduced by $1$ to $k=d+2-i$, and the number of points is reduced by $d$.\\ {\bf After step $d$:} The outcome of this procedure is a colored set $X_d$ with the color class $C^d_0$ of size $2$, and color classes $C^d_1$ to $C^d_d$ of size $3$. It remains to prove that \[ \text{cBP}_2 (X_d) = \sum_{s_1\in C^d_d,s_2\in C^d_{d-1},\ldots,s_d\in C^d_1}\ \text{cBP}_2\left( X_d\setminus \{ s_1,s_2,\ldots,s_d \} \right) \text{ is even.}\] For this, let $q_{d+1}$ be a point of $X_d$, and the boundary hyperplane -- that is crossed transversally -- be spanned by a subset $H_{d+1}$ of $X_d$ such that $G_{d+1}=H_{d+1}\cup\{q_{d+1}\}$ is rainbow. We distinguish two cases \begin{enumerate}[{Case (d+1,}1)] \item\label{final-fall1} $G_{d+1}\cap C^d_j=\emptyset$ for $j\in[1,d$]. \item\label{final-fall2} $G_{d+1}\cap C^d_0=\emptyset$. \end{enumerate} In Case~(d+1,\ref{final-fall1}), a pairing shows up as in the previous steps. In Case~(d+1,\ref{final-fall2}), let $C^d_0=\{t_1,t_2\}$. The property of containing the origin changes for the two $d$-simplices $G_{d+1}\cup \{t_1\}$, and $G_{d+1}\cup \{t_2\}$. The $d$-simplex $G_{d+1}\cup \{t_j\}$ contributes \[ \text{cBP}_{1}\left(X_d\setminus (G_i\cup \{t_j\})\right)\] to the above sum. %As only one point of color $0$ is left, The expression %\linebreak $\text{cBP}_{1}\left(X_d\setminus (G_i\cup \{t_j\})\right)$ reduces to the number of colored $d$-simplices containing the origin. If we sum up both contributions this leads to the number colored $d$-simplices containing the origin for the set $X_d\setminus G_{d+1}$. Finally, Lemma~\ref{lem-key} implies evenness for this set. \end{proof} \begin{proof}[\bf Proof of Property~(\ref{it-cb-even}) implies Properties~(\ref{it-cb-lower-plane}) and~(\ref{it-cb-lower})] For $d\geq 2$, let us first prove \begin{eqnarray} \text{cBP}_k(X)>0\,\Longrightarrow\,\text{cBP}_k(X)\geq 2^{k-d-1}\text{ for }d\geq 2 \text{ and }k\geq d+2, \end{eqnarray} via an induction on $k\geq d+2$. This settles Property~(\ref{it-cb-lower}). Property~(\ref{it-cb-even}) implies the base case $k=d+2$: \[\text{cBP}_k(X)>0\,\,\Longrightarrow\,\,\text{cBP}_k(X)\geq 2=2^{k-d-1}.\] Let now $k\geq d+3$, and be $\text{cBP}_k(X)>0$. Then there is a colored Birch partition $B_1,B_2,\ldots,B_k$ of $X$. For $1\leq i\leq k$, let $x_i$ be the point of color $0$ such that $x_i \in B_i$. Note that for any non-empty subset $I$ of the index set $[k]$, the set $\bigcup_{i\in I}B_i$ has again a colored Birch partition. Using the base case for $\bigcup_{i\in [4]}B_i$, we obtain a second colored Birch partition $B'_1,B'_2,B'_3,B'_4$ such that $x_i\in B'_i$ for all $i\in[4]$. Without loss of generality, we can assume $B_1\not=B'_1$. Applying the assumption to the set $X\setminus B_1$, we obtain at least $2^{k-d-2}$ colored Birch partitions of $X$ starting with $B_1$. Finally, applying the assumption to the set $X\setminus B'_1$, we obtain again at least $2^{k-d-2}$ Birch partitions of $X$ starting with $B'_1$. The construction of the sets $B_1$ and $B'_1$ leads to the factor of $2$. To prove Property~(\ref{it-cb-lower-plane}), we show in the two subsequent paragraphs that a third set $B''_1$ can be constructed for $d=2$, and $k\geq 7$ so that all three sets a) contain a fixed point $x$, and b) are pairwise distinct. Therefore, the factor $3$ shows up in the lower bound for $d=2$ and $k\geq 7$. For $x_1\in B_1$, the set $B'_1$ can be constructed as above. Now $B'_1$ contains a point $y\not= x_1$ that is not in $B_1$, and without loss of generality we can assume $y\in B_2$. Therefore $B_2\not=B'_2$. The set $\{4,5,6,7\}$ has $\binom{4}{2}=6$ subsets $I$ with two elements. For every subset $I=\{ i_1,i_2\}$, we apply the base case to $B_1\cup B_3 \cup B_{i_1}\cup B_{i_2}$ so that we obtain each time a new colored Birch partition $B^I_1,B^I_3,B^I_{i_1},B^I_{i_2}$, such that $x_1\in B^I_1$, $x_3\in B^I_3$, and $x_j\in B^I_j$ for both $j\in I$. If $B_1\not=B^I_1$ for one subset $I$, then $B'_1$ and $B^I_1$ are distinct by construction. Choosing $B''_1=B^I_1$ completes our proof. If $B_1=B^I_1$ for all subsets $I$, then we proceed as follows: For every $I$, there is a pair of $(i,j)$ from $I\cup\{3\}$ so that $B_i\not=F^I_i$ and $B_j\not=B^I_j$. A pair of the form $(3,j)$ is the outcome of at most three index sets, and a pair of the form $(i,j)$ of at most two index sets, where $i,j\in \{4,5,6,7\}$. As we have in total $6$ pairs of indices, one index $j\in \{3,4,5,6,7\}$ shows up in at least two pairs for two subsets $I_1,I_2$. Choosing the sets $B_j$, $B^{I_1}_j$, and $B^{I_2}_j$ completes our proof. \end{proof} \end{section} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{section}{On minimal point configurations}\label{sec-rem} %%% Rem in Reduction Teil nach Beweis von Main Result oder am Anfang der letzten Section? Let us conclude this paper with a discussion on lower bounds for the number of colored Tverberg partitions in the affine setting of Theorem~\ref{thm-ctv-bmz11}. The table below shows minimal numbers based on four different approaches for $d=2$, and $r$ up to~$8$. {\bf Remark on Theorem~\ref{thm-num-ctv}.} In general, our lower bounds for the number of colored Tverberg partitions might not be optimal as we assumed that there is (1) only one colored Tverberg point being (2) the intersection point of $d$ partition blocks of exactly $d$ points each. We have not found any (uncolored) example having both properties at the same time. Assuming that the colored Tverberg point is one of the vertices of $\Delta_N$ leads to a lower bound of $8\cdot 3^{r-7}$ resp.~$2^{r-d-2}$ for sufficiently large $r$. This observation is based on our computer experiments. In the table, there is a quite a gap between our lower bounds, and the minimal numbers. {\bf Sierkma's configuration with colors.} The point configuration due to\linebreak Sierksma~\cite[Sect.~6.6]{matou03:_using_borsuk_ulam} given by $r-1$ points clustered around each of the vertices of a standard $d$-simplex in $\R^d$ plus one point in its center seemed to be a good candidate for a minimal configuration, also in the colored case. The uncolored Sierksma configuration is extremal in two ways: It has one only Tverberg point, but this Tverberg point comes with a large number of Birch partitions. Colors force points to end up in different partitions blocks. Note that points of the same cluster end up in different blocks anyway. Any colored Tverberg partition is a Tverberg partition of the uncolored configuration. Our aim is to distribute every color as much as possible among the clusters so that the color constraint is most ``harmful''. The coloring of the Sierksma configuration which seems to lead to the smallest number of colored Tverberg partitions is obtained as follows: The point in the center is of color $d+1$. The $r-1$ points of every vertex are colored so that each of the colors $0,1,\ldots,d $ shows up $(r-1)/(d+1)$ times, or $\lceil (r-1)/(d+1)\rceil$ resp.~$\lfloor (r-1)/(d+1)\rfloor$ if $r$ is not a multiple of $d+1$. In that case, the remaining $(r-1)$ modulo $(d+1)$ points of vertex $i$, where $0\leq i\leq d$, are colored in a cyclic way with colors $i, i+1, \ldots $ (modulo $d$). The number of colored Tverberg partitions for this colored configuration can be calculated for every dimension $d$ via recursion formulas. We give the recursion for $d=2$. The generalization to higher dimensions is straightforward. Let $cs(r_1,g_1,b_1,r_2,g_2,b_2,r_3,g_3,b_3)$ be the number of colored Tverberg partitions of the Sierksma configuration equipped with the coloring from above, such that in cluster $i$ there are $r_i$ points of color red, $g_i$ points of color green, $b_i$ points of color blue. Due to the natural symmetry of the standard $d$-simplex, the numbers $cs(r_1,g_1,b_1,r_2,g_2,b_2,r_3,g_3,b_3)$ are invariant under permutations of the symmetric group $\Sigma_3$. For $r_1>0$ and any $\sigma\in\Sigma_3$, the numbers $cs(r_1,g_1,b_1,r_2,g_2,b_2,r_3,g_3,b_3)$ have the following properties: \begin{footnotesize} %\begin{small} \begin{eqnarray*} cs(1,0,0,0,1,0,0,0,1) & = & 1, \\ cs(1,1,0,1,0,1,0,1,1) & = & 1, \\ cs(r_1,g_1,b_1,r_2,g_2,b_2,r_3,g_3,b_3) & = & g_2\cdot b_3\cdot cs(r_1-1,g_1,b_1,r_2,g_2-1,b_2,r_3,g_3,b_3-1) \\ & & +\, b_2 \cdot g_3\cdot cs(r_1-1,g_1,b_1,r_2,g_2,b_2-1,r_3,g_3-1,b_3),\\ cs(r_1,g_1,b_1,r_2,g_2,b_2,r_3,g_3,b_3) & = & %cs(r_{\sigma(1)},g_{\sigma(1)},b_{\sigma(1)},r_{\sigma(2)},g_{\sigma(2)},b_{\sigma(2)},r_{\sigma(3)},g_{\sigma(3)},b_{\sigma(3)}) \\ cs(r_{\sigma(1)},\ldots, b_{\sigma(3)}). \end{eqnarray*} \end{footnotesize} %\end{small} The numbers $cs(1,0,0,0,1,0,0,0,1)$ up to $cs(3,3,2,3,2,3,2,3,3)$ are shown in the table below. {\bf Polygonal configurations in the plane.} Linda Kleist~\cite{note_linda11} who wrote her bachelor thesis under the supervision of Ziegler studied colored point configurations for $r\leq 6$, and $d=2$: The vertices of a regular 3(r-1)-gon plus its center point. Minimizing over all colorings, this construction led to larger numbers than Sierkma's configuration with colors. Her minimal numbers are shown below. {\bf Random configurations in the plane.} While placing colored points randomly in a square, we obtained minimal numbers shown in the table below. Looking at $100000$ examples for $r=5$ has led to five colored sets with 10 colored Tverberg partitions. All minimal examples have several Tverberg points: One of the points of $X$, and intersection points of two segments. We have not been able to detect another common pattern. These examples kept us from coming up with a conjecture for the number of colored Tverberg partitions based on Sierksma's configuration, and the coloring from above. All Java files, and examples of this project are available on request via email. %%The last column of our table shows the lower bound of Theorem~\ref{thm-num-ctv}. \begin{center} \begin{tabular}{|c|c|c|c|c|} \hline \multirow{3}{*}{$r$} & Minimum for & Minimum for poly- & Minimum for & Lower bound\\ & colored Sierksma & gonal configurations & random & of \\ & configurations & due to Kleist & configurations & Theorem~\ref{thm-num-ctv}\\ \hline 2 & 1 & 1 & 1 & 1\\\hline 3 & 1 & 1 & 1 & 1\\\hline 4 & 2 & 2 & 2 & - \\\hline 5 & 12 & 16 & 10 & 1\\\hline 6 & 80 & 80 & 80 & - \\\hline 7 & 640 & - & 864 & 4\\\hline 8 & 9216 & - & $>10000$& -\\\hline \end{tabular} \end{center} In conclusion, our discussion suggests 1) that finding minimal colored configurations is not easy, 2) that random configurations do not lead to minimal examples for $r>6$, and 3) that our lower bound is not tight.\\ \subsection*{Acknowledgements} The author is grateful to Pavle Blagojevi\'c for critical comments, and to G\"unter M.~Ziegler for critical remarks which led to an improvement of the paper. We thank the referees for their comments which led to a substantial improvement of the presentation of our results. \end{section} %%%%%%% Literatur %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\bibliographystyle{plain} %\bibliography{../../bibtex/all} \begin{thebibliography}{10} \bibitem{barany92} Imre B\'ar\'any and David~G.~Larman. \newblock A colored version of {T}verberg's theorem. \newblock {\em J.~London Math.~Soc.~(2)}, 45:314--320, 1992. \bibitem{bmz10:_col-tp} Pavle V.~M.~Blagojevi\'c, Benjamin Matschke, and G\"unter~M.~Ziegler. \newblock Optimal bounds for the colorful {T}verberg problem. \newblock Preprint, October 2009, 9 pages, \url{http://arXiv.org/abs/0910.4987}; {\em J.~European Math.~Soc.}, to appear. \bibitem{bmz11:_col-tvp} Pavle V.~M.~Blagojevi\'c, Benjamin Matschke, and G\"unter~M.~Ziegler. \newblock Optimal bounds for a colorful {T}verberg-{V}re\'cica type problem. \newblock {\em Adv.~Math.}, 226:5198--5215, 2011. \bibitem{deza06:_colour} Antoine Deza, Sui Huang, Tamon Stephan, and Tam\'as Terlaky. \newblock Colourful simplicial depth. \newblock {\em Discrete Comp.~Geom.}, 35:597--615, 2006. \bibitem{hell07:_tverb} Stephan Hell. \newblock On the number of {T}verberg partitions in the prime power case. \newblock {\em Europ.~J.~of Comb.}, 28:347--355, 2007. \bibitem{hell08:_birch} Stephan Hell. \newblock On the number of {B}irch partitions. \newblock {\em Discrete Comput.~Geom.}, 40:586--594, 2008. \bibitem{note_linda11} Linda Kleist. \newblock Zehn bunte {P}unkte in der {E}bene. \newblock {\em Mitteilungen der DMV}, 19:124, 2011. \newblock Contribution to a puzzle of Matschke, and Ziegler, MDMV {\bf 18} (2010). \bibitem{matou03:_using_borsuk_ulam} Ji{\v r}{\'i} Matou{\v s}ek. \newblock {\em Using the {B}orsuk--{U}lam theorem}. \newblock Universitext. Springer--Verlag, Berlin, 2003. \newblock Lectures on topological methods in combinatorics and geometry. \bibitem{mtw11:_col-geom-ctvp} Ji\v{r}\'{i} Matou\v{s}ek, Martin Tancer, and Uli Wagner. \newblock A geometric proof of the colored {T}verberg theorem. \newblock {\em Discrete Comput.~Geom.}, 47(2):245--265, 2012. \bibitem{tverberg66:_theor} Helge Tverberg. \newblock A generalization of {R}adon's theorem. \newblock {\em J.~London Math.~Soc}, 41:123--128, 1966. \bibitem{vrecica-zival-11:chessboard} Sinisa~T.~Vre\'{c}ica and Rade~T.~\v{Z}ivaljevi\'c. \newblock Chessboard complexes indomitable. \newblock {\em J.~Comb.~Theory, Ser.~A}, 118:2157--2166, 2011. \bibitem{vz93:_notes_sierk} Aleksandar Vu\v{c}i\'c and Rade~T.~\v{Z}ivaljevi\'c. \newblock Notes on a conjecture of {S}ierksma. \newblock {\em Discrete Comput.~Geom.}, 9:339--349, 1993. \bibitem{z11:_col-tvp_ams} G\"unter~M.~Ziegler. \newblock 3{N} colored points in a plane. \newblock {\em Notices of the AMS}, 58:550--557, 2011. \end{thebibliography} %\begin{thebibliography}{10} % %\bibitem{barany92} %\textsc{I.~B\'ar\'any and D.~G. Larman}, \emph{A colored version of % {T}verberg's theorem}, J.~London Math.~Soc.~(2) \textbf{45} (1992), % pp.~314--320. % %\bibitem{bmz10:_col-tp} %\textsc{P.~V.~M. Blagojevi\'c, B.~Matschke, and G.~M. Ziegler}, \emph{Optimal % bounds for the colorful {T}verberg problem}. %\newblock Preprint, October 2009, 9 pages, % \url{http://arXiv.org/abs/0910.4987}; J.~European Math.~Soc., to appear. % % %\bibitem{bmz11:_col-tvp} %\textsc{P.~V.~M. Blagojevi\'c, B.~Matschke, and G.~M. Ziegler}, \emph{Optimal % bounds for a colorful {T}verberg-{V}re\'cica type problem}, Adv.~Math. % \textbf{226} (2011), pp.~5198--5215. % %\bibitem{deza06:_colour} %\textsc{A.~Deza, S.~Huang, T.~Stephan, and T.~Terlaky}, \emph{Colourful % simplicial depth}, Discrete Comp.~Geom. \textbf{35} (2006), pp.~597--615. % %\bibitem{hell07:_tverb} %\textsc{S.~Hell}, \emph{On the number of {T}verberg partitions in the prime % power case}, Europ.~J.~of Comb. \textbf{28} (2007), pp.~347--355. % %\bibitem{hell08:_birch} %\textsc{S.~Hell}, \emph{On the number of {B}irch partitions}, Discrete % Comput.~Geom. \textbf{40} (2008), pp.~586--594. % %\bibitem{note_linda11} %\textsc{L.~Kleist}, \emph{Zehn bunte {P}unkte in der {E}bene}, Mitteilungen der % DMV \textbf{19} (2011), p.~124. %\newblock Contribution to a puzzle of Matschke, and Ziegler in MDMV {\bf 18} % (2010). % %\bibitem{matou03:_using_borsuk_ulam} %\textsc{J.~Matou{\v s}ek}, \emph{Using the {B}orsuk--{U}lam theorem}, % Universitext, Springer--Verlag, Berlin, 2003. %\newblock Lectures on topological methods in combinatorics and geometry. % %\bibitem{mtw11:_col-geom-ctvp} %\textsc{J.~Matou\v{s}ek, M.~Tancer, and U.~Wagner}, \emph{A geometric proof of % the colored {T}verberg theorem}, Discrete Comput.~Geom. \textbf{47}, no.~2 % (2012), pp.~245--265. % %\bibitem{tverberg66:_theor} %\textsc{H.~Tverberg}, \emph{A generalization of {R}adon's theorem}, J.~London % Math.~Soc \textbf{41} (1966), pp.~123--128. % %\bibitem{vrecica-zival-11:chessboard} %\textsc{S.~T. Vre\'{c}ica and R.~T. \v{Z}ivaljevi\'c}, \emph{Chessboard % complexes indomitable}, J.~Comb.~Theory, Ser.~A \textbf{118} (2011), % pp.~2157--2166. % %\bibitem{vz93:_notes_sierk} %\textsc{A.~Vu\v{c}i\'c and R.~T. \v{Z}ivaljevi\'c}, \emph{Notes on a conjecture % of {S}ierksma}, Discrete Comput.~Geom. \textbf{9} (1993), pp.~339--349. % %\bibitem{z11:_col-tvp_ams} %\textsc{G.~M. Ziegler}, \emph{3{N} colored points in a plane}, Notices of the % AMS \textbf{58} (2011), pp.~550--557. % %\end{thebibliography} Email-address: \href{mailto:stephan@hell-wie-dunkel.de}{stephan@hell-wie-dunkel.de} \end{document}