# On a transversal theorem of Montejano and Karasev

Andreas F. Holmsen

###### Abstract.

We give a new proof a theorem of Montejano and Karasev [5] regarding
$k$-dimensional transversals to small families of convex sets. While the
result in [5] uses technical algebraic and topological tools, our proof is a
simple application of the Borsuk–Ulam theorem. Additionally, in certain cases
we obtain stronger results than those in [5].

##  1\. Introduction

Let $F_{1},\dots,F_{n}$ be finite families of convex sets in $\mathbb{R}^{d}$.
We say that the families $F_{1},\dots,F_{n}$ satisfy the colorful intersection
property if $C_{1}\cap\cdots\cap C_{n}\neq\emptyset$ for any choice of
$C_{1}\in F_{1},\dots,C_{n}\in F_{n}$.

Given $n=d+1$ finite families of convex sets in $\mathbb{R}^{d}$ which satisfy
the colorful intersection property, the colorful Helly theorem [1] asserts
that there is a point that intersects every member of one of the families
$F_{i}$. (Even more can be said; If $n=d+k$ there is a point that intersects
every member of $k$ of the families.)

On the other hand, what can be said when $n\leq d$ ? In this case, the
conclusion of the colorful Helly theorem clearly fails; Simply take each
$F_{i}$ to be a family of hyperplanes in general position. Nevertheless, the
colorful intersection property imposes non-trivial geometric constraints on
the families. For instance, if $n=d$ it is easy to see that for any direction
there exists a family $F_{i}$ whose members can be intersected by a line in
that given direction. (Just project to a hyperplane orthogonal to the given
direction and apply the colorful Helly theorem.)

These observations have led to a number of interesting results and conjectures
concerning families satisfying the colorful intersection property [3, 4, 5].
Here we focus on the remarkable results by Montejano and Karasev [5], which
state that under certain conditions on $n$, $|F_{i}|$ and $d$, the colorful
intersection property implies that that one of the families $F_{i}$ admits a
$k$-transversal, that is, a $k$-dimensional affine flat that intersects every
memebr of $F_{i}$. In its simplest non-trivial form, their theorem can be
formulated as follows (See also [4, Theorem 3.2]):

Consider 3 red convex sets and 3 blue convex sets in $\mathbb{R}^{3}$, and
suppose every red set intersects every blue set. Then all the red sets can be
intersected by a line or all the blue sets can be intersected by a line.

The general theorems of Montejano and Karasev rely on a number of technical
tools (multiplication formulas for Schubert cocycles, Steifel–Whitney
characteristic classes, Lusternik–Schnirelmann category of the Grassmannian),
and simpler proofs are of considerable interest. In this respect, Strausz [6]
recently gave an elementary proof of the statement above based on the non-
planarity of the complete bipartite graph $K_{3,3}$.

The purpose of this note is to give an elementary proof of the
Montejano–Karasev theorem. (Our proof is based on the Borsuk–Ulam theorem, but
it seems unlikely that this type of results can be proven without using any
topology.) In particular, we establish the following.

######  Theorem 1.

Let $k_{1},\dots,k_{n}$ be non-negative integers and set
$m=k_{1}+\cdots+k_{n}$. For each $1\leq i\leq n$, let $F_{i}$ be a family of
$k_{i}+2$ convex sets in $\mathbb{R}^{n+m-1}$, and suppose the families
$F_{1},\dots,F_{n}$ satisfy the colorful intersection property. Then one of
the families $F_{i}$ admits a $k_{i}$-transversal.

######  Remark.

Let us point out some particular cases of Theorem 1.

  1. (a)

The case $n=1$ is tautological, as this corresponds to a single family $F_{1}$
of $k+2$ convex sets in $\mathbb{R}^{k}$.

  2. (b)

The case $n=2$ with $k_{1}=d-1$ and $k_{2}=0$ follows from the separation
theorem for convex sets in $\mathbb{R}^{d}$. If the two members of $F_{2}$ are
disjoint (i.e. they do not have a 0-transversal), then there is a hyperplane
that strictly separates them. By the colorful intersection property every
member of $F_{1}$ must cross this hyperplane.

  3. (c)

The case $n\geq 2$ and $k_{1}=\cdots=k_{n}=0$ corresponds to $n$ families,
each consisting of two convex sets in $\mathbb{R}^{n-1}$. The colorful Helly
theorem implies that the members of one of the $F_{i}$ must intersect.

  4. (d)

In the case $n=2$ we have $k_{1}+2$ red convex sets and $k_{2}+2$ blue convex
sets in $\mathbb{R}^{k_{1}+k_{2}+1}$ such that every red set intersects every
blue set. The conclusion is that the red sets admit a $k_{1}$-transversal or
the blue sets admit a $k_{2}$-transversal. This is a special case of a result
of Montejano and Karasev [5, Corollary 7 with $k=1$]. (See also [4, Theorem
3.2].)

  5. (e)

For $n>2$ Theorem 1 strengthens a result of Montejano and Karasev [5, Theorem
8]. Their result states that if $F_{1},\dots,F_{n}$ are families of $k+2$
convex sets in $\mathbb{R}^{n+k}$ which satisfy the colorful intersection
property, then one of the families has a $k$-transversal. (See also Theorems
3.3 and 3.4 in [4].) Our Theorem 1 shows that dimension of the ambient space
can be increased to $n(k+1)-1$ without affecting the conclusion.

##  2\. Optimality of dimension in Theorem 1

Before getting to the proof of Theorem 1 we give an example which shows that
the dimension $n+m-1$ can not be increased to $n+m$. Let $X$ be a set of
$2n+m$ points in $\mathbb{R}^{n+m}$ and consider a partition
$X=X_{1}\cup\dots\cup X_{n}$ where $|X_{i}|=k_{i}+2$. We assume that $X$ is in
general position in the sense that any subset of size $n+m$ spans a unique
affine hyperplane and the affine spans of the $X_{i}$ form a generic
collection of flats. Let $\pi_{i}$ denote the orthogonal projection map from
$\mathbb{R}^{n+m}$ to the affine span of $X_{i}$, and let

$F_{i}=\\{\pi^{-1}(x):x\in X_{i}\\}.$

Since each member of $F_{i}$ is a flat of dimension $n+m-(k_{i}+1)$, if we
pick one member from each $F_{i}$, then they will generically intersect in a
unique point. In other words, the families $F_{1},\dots,F_{n}$ satisfy the
colorful intersection property. Moreover, $F_{i}$ does not admit a
$k_{i}$-transversal. To see this, suppose $\gamma$ is a $k_{i}$-dimensional
flat that intersects every member of $F_{i}$. Then $X_{i}$ must be contained
in $\pi_{i}(\gamma)$, contradicting the affine independence of $X_{i}$.

##  3\. Two geometric lemmas

The proof of Theorem 1 requires two simple geometric lemmas. They are both
quite standard (and most likely known in some form or another), but for
completeness we include proofs.

The first lemma can be thought of as an extension of Radon’s lemma. It was
previously observed by Goodman and Pollack [2], and also plays a role in the
argument by Strausz [6].

######  Lemma 2.

Let $F=\\{C_{1},\dots,C_{k+2}\\}$ be a family of convex sets in
$\mathbb{R}^{d}$. Then $F$ has a $k$-dimensional transversal if and only if
there exists a partition $[k+2]=A\cup B$ such that

$\text{\em conv}\big{(}{\textstyle\bigcup\limits_{i\in
A}}C_{i}\big{)}\cap\text{\em conv}({\textstyle\bigcup\limits_{j\in
B}}C_{j})\neq\emptyset$

###### Proof.

Suppose there is a $k$-dimensional transversal $\gamma$ to $F$. For each
member $C_{i}\in F$ choose a point $p_{i}\in\Gamma\cap C_{i}$. Applying
Radon’s lemma to the set $\\{p_{1},\dots,p_{k+2}\\}$ contained in the
$k$-dimensional affine subspace $\gamma$ gives us the desired partition.

For the opposite direction suppose there is a partition $[k+2]=A\cup B$ and a
point $p\in\text{conv}\big{(}{\textstyle\bigcup_{i\in
A}}C_{i}\big{)}\cap\text{conv}({\textstyle\bigcup_{j\in B}}C_{j})$. For each
$i\in A$ we can choose a point $p_{i}\in C_{i}$ such that $p\in\text{conv
}\\{p_{i}\\}_{i\in A}$. Similarly, we can choose points $p_{j}\in C_{j}$ such
that $p\in\text{conv }\\{p_{j}\\}_{j\in B}$. Clearly the affine span of
$\\{p_{i}\\}_{i\in A\cup B}$ intersects every member of $F$ and has dimension
at most $|A|+|B|-2=k$. ∎

The second lemma is a simple application of the separation theorem for convex
sets.

######  Lemma 3.

Let $v_{1},\dots,v_{n}\in\mathbb{R}^{d}$ and
$(b_{1},\dots,b_{n})\in\mathbb{R}^{n}$. Suppose there exists vectors
$u,w\in\mathbb{R}^{d}$ such that

$w\cdot v_{i}<b_{i}<u\cdot v_{i}$

for every $1\leq i\leq n$. Then there exists a vector $v\in\mathbb{R}^{d}$
such that $v\cdot v_{i}>0$ for every $1\leq i\leq n$.

###### Proof.

If the conclusion of the Lemma does not hold then the origin is contained in
the convex hull of the $v_{i}$, so there exists a linear dependency
$\sum_{i\in I}t_{i}v_{i}=0$ with $t_{i}>0$ for some $\emptyset\neq
I\subset[n]$. This is a contradiction since

$0=w\cdot\big{(}\textstyle{\sum\limits_{i\in
I}}t_{i}v_{i}\big{)}=\textstyle{\sum\limits_{i\in I}}t_{i}(w\cdot
v_{i})<\textstyle{\sum\limits_{i\in I}}t_{i}b_{i}<\textstyle{\sum\limits_{i\in
I}}t_{i}(u\cdot v_{i})=u\cdot\big{(}\textstyle{\sum\limits_{i\in
I}}t_{i}v_{i}\big{)}=0.\qed$

##  4\. Proof of Theorem 1

Set $d=n+m-1$, and suppose that none of the subfamilies $F_{i}$ admits a
$k_{i}$-transversal. Define $K_{i}$ to be the abstract simplicial complex
whose vertex set $V(K_{i})$ consists of the nonempty proper subfamilies of
$F_{i}$ and whose faces are the chains ordered by inclusion. In other words,

$K_{i}\vcentcolon=\\{\sigma_{1}\subset\sigma_{2}\subset\cdots\subset\sigma_{r}:\emptyset\neq\sigma_{j}\subsetneq
F_{i}\\}.$

Note that $K_{i}$ is isomorphic to the barycentric subdivision of the
$k_{i}$-skeleton of the $(k_{i}+1)$-dimensional simplex, and is therefore
homeomorphic to $S^{k_{i}}$. Furthermore, we observe that
$\upsilon_{i}(\sigma)\vcentcolon=F_{i}\setminus\sigma$ defines a free
simplicial involution on $K_{i}$ since taking complements reverses inclusions

$\sigma_{1}\subset\sigma_{2}\subset\cdots\subset\sigma_{r}\xmapsto{\>\;\upsilon_{i}\;\>}\upsilon_{i}({\sigma}_{r})\subset\cdots\subset\upsilon_{i}({\sigma}_{2})\subset\upsilon({\sigma}_{1}).$

If we group the vertices of $K_{i}$ into complementary pairs
$\\{\sigma,\upsilon_{i}({\sigma})\\}$, then Lemma 2 implies that for each
complementary pair there exists an affine hyperplane
$h_{\\{\sigma,\upsilon_{i}({\sigma})\\}}$ in $\mathbb{R}^{d}$ which strictly
separates the members of $\sigma$ from the members of
$\upsilon_{i}({\sigma})$. Let $H_{\sigma}$ and $H_{\upsilon_{i}(\sigma)}$
denote the opposite open halfspaces bounded by
$h_{\\{\sigma,\upsilon_{i}({\sigma})\\}}$ which contain the members of
$\sigma$ and $\upsilon_{i}(\sigma)$, respectively, and let $f_{i}(\sigma)$ and
$f_{i}(\upsilon_{i}(\sigma))$ be their outward unit normal vectors. In this
way, we obtain a mapping

$f_{i}:V(K_{i})\to S^{d-1},$

which satisfies $f_{i}(\sigma)=-f_{i}(\upsilon_{i}(\sigma))$.

Let $K$ be the join $K=K_{1}*K_{2}*\cdots*K_{n}$ which comes equipped with the
free simplicial involution
$\upsilon=\upsilon_{1}*\upsilon_{2}*\cdots*\upsilon_{n}$. Note that $K$ is
homeomorphic to $S^{d}$. We define a map $f:V(K)\to S^{d-1}$ given by

$f(\sigma)=f_{i}(\sigma)\iff\sigma\in V(K_{i}),$

which obviously satisfies $f(\sigma)=-f(\upsilon(\sigma))$. By taking the
affine extension of $f$ we get a continuous equivariant map
$\hat{f}:K\to\mathbb{R}^{d}$ for which the following holds.

######  Claim.

For any simplex $S\in K$, the origin is not contained in $\hat{f}(S)$

Assuming this claim is true, the proof the theorem is complete since $\hat{f}$
would contradict the Borsuk–Ulam theorem.

It remains to prove the claim. Consider a maximal simplex $S\in K$. The
vertices of $S$ can be expressed as $n$ chains

$\begin{array}[]{ccccccc}\sigma^{(1)}_{1}&\subset&\sigma^{(1)}_{2}&\subset&\cdots&\subset&\sigma^{(1)}_{k_{1}+1}\\\
\sigma^{(2)}_{1}&\subset&\sigma^{(2)}_{2}&\subset&\cdots&\subset&\sigma^{(2)}_{k_{2}+1}\\\
&&&\vdots&&&\\\
\sigma^{(n)}_{1}&\subset&\sigma^{(n)}_{2}&\subset&\cdots&\subset&\sigma^{(n)}_{k_{n}+1}\end{array}$

where $\sigma^{(i)}_{j}$ is a subfamily of $F_{i}$ with
$|\sigma^{(i)}_{j}|=j$. For every $1\leq i\leq n$ let us denote
$\sigma^{(i)}_{1}=\\{C_{i}\\}$ and
$\nu_{i}(\sigma^{(i)}_{k_{i}+1})=\\{D_{i}\\}$. We observe that

$C_{i}\subset{\textstyle\bigcap\limits_{j=1}^{k_{i}+1}}H_{\sigma^{(i)}_{j}}\;\;\;\text{
and
}\;\;\;D_{i}\subset{\textstyle\bigcap\limits_{j=1}^{k_{i}+1}}H_{\upsilon_{i}(\sigma^{(i)}_{j})}$

so by the colorful intersection property, it follows that the intersections
$\bigcap_{i=1}^{n}C_{i}$ and $\bigcap_{i=1}^{n}D_{i}$ are both nonempty. This
implies

${\textstyle\bigcap\limits_{\sigma\in
S}}H_{\sigma}\neq\emptyset\;\;\;\text{and}\;\;\;{\textstyle\bigcap\limits_{\sigma\in
S}}H_{\upsilon(\sigma)}\neq\emptyset.$

Since $H_{\sigma}$ and $H_{\upsilon(\sigma)}$ are opposite open halfspaces
bounded by $h_{\\{\sigma,\upsilon(\sigma)\\}}$, it follows from Lemma 3 that
$0\notin\text{conv}\hskip 0.85355ptf(S)=\hat{f}(S)$. This completes the proof
of the claim and of Theorem 1.

##  5\. Final remarks

The paper by Montejano and Karasev [5] contains several other interesting
results that are not covered by our Theorem 1. In particular, Corollary 7 in
[5] gives conditions for when families of size greater than $k+2$ have a
$k$-transversal. For example they show the following:

Let $F_{1},F_{2},F_{3}$ be families of convex sets in $\mathbb{R}^{5}$
satisfying the colorful intersection property, and suppose
$|F_{1}|=|F_{2}|=|F_{3}|=5$. Then one of the families $F_{i}$ admits a
2-transversal.

We have not been able to prove the statement above using the proof method of
Theorem 1. The main issue seems to be that for families of size greater than
$k+2$ we do not have a good combinatorial characterization for the existence
of a $k$-transversal as in Lemma 2.

Question. What is the optimal dimension in Corollary 7 in [5] ?

## References

  * [1] I. Bárány, A generalization of Carathéodory’s theorem, Discrete Math. 40, 141–152 (1982)
  * [2] J. E. Goodman and R. Pollack, Hadwiger’s transversal theorem in higher dimensions, J. Amer. Math. Soc. 1, 301–309 (1988)
  * [3] L. Martínez–Sandoval, E. Roldán–Pensado and N. Rubin, Further Consequences of the Colorful Helly Hypothesis, Discrete Comput. Geom. 63, 848–866 (2020)
  * [4] L. Montejano, Transversals, topology and colorful geometric results, In Geometry – Intuitive, discrete, and convex, Bolyai Society Mathematical Studies 24, 205–218 (2013)
  * [5] L. Montejano and R. Karasev, Topological transversals to a family of convex sets, Discrete Comput. Geom. 46, 283–300 (2011).
  * [6] R. Strausz, How do 9 points look like in $\mathbb{E}^{3}$?, Ann. Comb. (to appear)