UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO
PROGRAMA DE MAESTRÍA Y DOCTORADO EN CIENCIAS MATEMÁTICAS Y
DE LA ESPECIALIZACIÓN EN ESTADÍSTICA APLICADA
COLORFUL THEOREMS IN DISCRETE AND CONVEX GEOMETRY
TESIS
QUE PARA OPTAR POR EL GRADO DE:
MAESTRO EN CIENCIAS
PRESENTA:
CUAUHTEMOC GOMEZ NAVARRO
DIRECTOR
DR. EDGARDO ROLDÁN PENSADO
CENTRO DE CIENCIAS MATEMÁTICAS, UNAM
CIUDAD DE MÉXICO, JUNIO DEL 2022.
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
  
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
  
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
  
 
2
Agradecimientos
El éxito en la vida no consiste en ganar todas tus batallas,
sino en nunca rendirse en las que valen la pena.
Quiero agradecer a las personas que han aportado a mi formación personal y académica.
A mi mamá, mi papá y mis dos hermanos por todos los momentos que hemos pasado juntos.
Un especial agradecimiento a mi mamá, por su apoyo incondicional en todo momento.
A mi director de tesis, Edgardo Roldán, por sus observaciones, comentarios y sugerencias. Le
agradezco por escucharme cada vez que creo haber demostrado un nuevo resultado matemático,
por la confianza que me ha tenido, y por el tiempo que le ha dedicado a los problemas y
conjeturas que le he contado. Por todo lo que he aprendido trabajando a su lado.
A mi tutora de maestŕıa, Isabel Hubard, por todos sus consejos, por todo lo que he aprendido
de ella y por la revisión de esta tesis.
A Leonardo Mart́ınez, porque ha léıdo con mucho cuidado mis dos tesis (de licenciatura y
de maestŕıa). Le agradezco todas las observaciones, correcciones y sugerencias que ayudaron a
mejorar este trabajo. También le quiero agradecer por invitarme a ser su ayudante de maestŕıa,
a escribir un art́ıculo en Espacio Matemático y a dar una plática en el Encuentro Nacional de
Computación.
A Pablo Soberón, por la lectura cuidadosa de esta tesis. Por las correcciones, comentarios
y observaciones que me ayudaron a aprender más.
A Luis Montejano, por la revisión de este trabajo, por ser un gran profesor y un ejemplo a
seguir. Gracias por invitarme a dar una plática en el Seminario Preguntón.
A todos los profesores de los que he aprendido matemáticas. En particular, quiero agradecer
a Edgardo Roldán, Isabel Hubard, Leonardo Mart́ınez, Luis Montejano, Pablo Soberón, Juan
José Montellano, Vinicio Gómez, Javier Bracho, Ricardo Strausz, Amanda Montejano, Adriana
Hansberg, Alejandro Illanes, Francisco Marmolejo, Javier Páez, Alejandro Daŕıo y Ernesto
Arellano.
A todos los entrenadores que tuve en la Olimpiada de Matemáticas de la Ciudad de México,
porque fue ah́ı donde gané el gusto por resolver problemas. En especial, quiero agradecer a Jorge
Garza, Diego Calzadilla (Gogo), Ian Gleason, Luis Fernando Pardo, Gerardo Franco, Sergio
Zamora, Julio Dı́az, César Rodŕıguez y Luis Eduardo Garćıa. Gracias por todo el tiempo que
le dedicaron a los entrenamientos y elaboración de problemas. También a todos los alumnos,
amigos y compañeros que tuve en la olimpiada, porque también he aprendido mucho de ellos.
Al Instituto de Matemáticas y al Posgrado de la UNAM, por ser su alumno durante la
maestŕıa. A Conacyt por la beca de posgrado.
3
4
Contents
Introduction 7
Introducción 11
1. Convex geometry 15
1.1. Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2. Carathéodory, Radon and Helly . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3. Transversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2. Colorful theorems 23
2.1. Colorful Carathéodory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2. Colorful Helly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3. Colorful Radon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3. Very colorful theorems 29
3.1. Colorful Carathéodory-type theorems . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2. Colorful Helly-type theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4. Colorful theorems for line transversals 39
4.1. KKM theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2. A colorful Helly-type theorem in R
2 . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.3. A colorful Helly-type problem in R
3 . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.4. Colorful Eckhoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5. Conclusions 61
Bibliography 65
5
6 CONTENTS
Introduction
Convex sets are geometrical objects with very interesting properties and have been studied
in several branches of mathematics. In particular, discrete and convex geometry is a branch
of discrete mathematics with the goal of studying the combinatorial properties of convex sets.
The classical theorems in discrete and convex geometry are the theorems of Carathéodory [8]
(in 1907), Radon [34] (in 1921) and Helly [18] (in 1923). In order to start seeing the geometrical
and combinatorial ideas we state Carathéodory’s theorem [8] and Helly’s theorem [18].
Carathédory’s theorem states that if a point a ∈ R
d is in the convex hull of some set A ⊂ R
d,
then there exist at most d+ 1 points in A such that their convex hull contains the point a. In
other words, in order to know if a point is in the convex hull of some set A we only need to
know if the point is in the convex hull of a finite subset (of size at most d+ 1) of A.
Helly’s theorem states that if a finite family of convex sets in R
d satisfies that every d+1 or
fewer of them have non-empty intersection, then the whole family has non-empty intersection.
In fact, the result is also true for infinite families of compact convex sets. In other words, Helly’s
theorem states that we only need information concerning the intersection of finite subfamilies
(of size d+ 1) in order to know if the whole family has non-empty intersection.
On the other hand, there are several theorems in discrete mathematics which have colorful
versions. For example, Lovász proved the Colorful Helly theorem in 1973 (see [4]). In addition,
in 1982 Bárány [4] proved the Colorful Carathéodory theorem.
The Colorful Helly theorem states that if we have d+1 finite families F1, . . . ,Fd+1 of convex
sets in R
d such that for every choice of sets C1 ∈ F1, . . . , Cd+1 ∈ Fd+1, the intersection
⋂d+1
i=1 Ci
is non-empty, then there exists i ∈ {1, . . . , d + 1} such that the family Fi has non-empty
intersection.
The Colorful Carathéodory theorem states that if we have d + 1 finite sets A1, . . . , Ad+1
of points in R
d such that the origin is contained in the convex hull of every set Ai, for i =
1, . . . , d + 1, then there exist d + 1 points a1 ∈ A1, . . . , ad+1 ∈ Ad+1 such that the origin is
contained in the convex hull of {a1, . . . , ad+1}.
Note that we recover Helly’s theorem from the Colorful Helly theorem when all the families
are equal. Therefore, the Colorful Helly theorem is a generalization of Helly’s theorem. By
a similar argument, the Colorful Carathéodory theorem is a generalization of Carathéodory’s
theorem. In general, Colorful theorems are usually generalizations of their uncolored versions.
The name colorful comes from thinking that every family is colored (and every family has
a different color). Then colorful theorems follow some of the following two ideas.
• In the hypothesis of colorful theorems we have information concerning rainbow subfamilies
7
8 INTRODUCTION
and the conclusion is concerning subfamilies of the same color.
• In the hypothesis of colorful theorems we have information concerning subfamilies of the
same color and the conclusion is concerning rainbow subfamilies.
For example, in the Colorful Helly theorem we have information concerning the intersection
of rainbow subfamilies and the conclusion is concerning the intersection of a subfamily of the
same color. On the other hand, in the Colorful Carathéodory theorem we have information
concerning sets of the same color and the conclusion is concerning a rainbow set.
This work has two purposes. On the one hand, we present a collection of several colorful
theorems in discrete and convex geometry by introducing the ideas of proofs intuitively in low
dimensions. On the other hand, we also present new results concerning colorful theorems and
improve bounds of colorful theorems.
In Chapter 1 we see an introduction to convex geometry and present the definitions and
notation that we use in this work. We present the classical theorems of convex geometry:
Carathéodory [8], Helly [18] and Radon [34]. We also see Eckhoff’s theorems concerning
transversals.
In Chapter 2 we prove the classical colorful theorems in convex geometry: Colorful Helly
(done by Lovász in 1973, see [4]), Colorful Carathéodory (done by Bárány [4] in 1982) and
Colorful Radon (done by Lovász in 1989, see [2]).
In Chapter 3 we see the following two generalizations of the classical colorful theorems.
• Pach, Holmsen and Tverberg [21] (in 2008) and independently Arocha, Bárány, Bracho,
Fabila and Montejano [1] (in 2009) proved that we can weaken the hypothesis of the
Colorful Carathéodory theorem and obtain the same conclusion. They proved that if
we have d + 1 finite sets A1, . . . , Ad+1 of points in R
d such that the origin is contained
in the convex hull of Ai ∪ Aj, for every 1 ≤ i < j ≤ d + 1, then there exist d + 1
points a1 ∈ A1, . . . , ad+1 ∈ Ad+1 such that the origin is contained in the convex hull
of {a1, . . . , ad+1}. In addition, we prove that this result cannot be generalized in two
different senses.
• In 2020, Mart́ınez-Sandoval, Roldán-Pensado and Rubin [28] wondered if there are further
consequences with the hypothesis of the Colorful Helly theorem. They proved that for
each dimension d ≥ 2 there exist numbers f(d) and g(d) with the following property.
If F1, . . . ,Fd are finite families of convex sets in R
d such that for every choice of sets
C1 ∈ F1, . . . , Cd ∈ Fd the intersection
⋂d
i=1 Ci is non-empty, then either there is a family
Fj that can be pierced by f(d) points, or the family
⋃d
i=1 Fi can be crossed by g(d) lines.
In particular, they proved that their result in the plane (d = 2) holds with f(2) = 1 and
g(2) = 4.
In Chapter 4 we present our results. First, we see the topological preliminaries that we use
to prove our results. Then we do the following:
• We improve the 2-dimensional case of the theorem by Mart́ınez-Sandoval, Roldán-Pensado
and Rubin [28]; we prove that the 2-dimensional case of their theorem also holds with
INTRODUCTION 9
f(2) = 1 and g(2) = 2. We prove that if F1, . . . ,Fn are finite families of convex sets in R
2
(with n ≥ 2), such that A∩B 6= ∅ for every A ∈ Fi and B ∈ Fj (with i 6= j), then either
there exists j ∈ {1, 2, . . . , n} such that
⋃
i 6=j Fi can be pierced by 1 point, or the family
⋃n
i=1 Fi can be crossed by 2 lines. Furthermore, we also prove that if K is a compact
convex set in the plane and F1, . . . ,Fn are finite families of translates of K (with n ≥ 2),
such that A ∩ B 6= ∅ for every A ∈ Fi and B ∈ Fj (with i 6= j), then either there exists
j ∈ {1, 2, . . . , n} such that
⋃
i 6=j Fi can be pierced by 3 points, or the family
⋃n
i=1 Fi can
be crossed by 1 line. We also prove similar results for families of homothets, circles and
rectangles.
• We state an open problem proposed by Mart́ınez-Sandoval, Roldán-Pensado and Rubin
[28]. The problem is if there exists n ∈ Z
+ such that for any two families A, B of convex
sets in R
3 so that A ∩ B 6= ∅ holds for all A ∈ A and B ∈ B, one of the families A or B
can be crossed by n lines. We show a particular case of this problem (for small families)
solved by Montejano and Karasev ([32], [33]) and give an elementary proof (for small
families) by Strausz [41]. In addition, we propose a geometrical idea to reduce the open
problem to a topological problem.
• We prove colorful versions of Eckhoff’s theorems.
We prove that if F1, . . . ,F4 are finite families of connected sets in R
2 such that every four
sets A1 ∈ F1, A2 ∈ F2, . . . , A4 ∈ F4 have a line transversal, then there is a family Fi that
can be crossed by 2 lines.
We also prove that if F1, . . . ,F6 are finite families of connected sets in R
2 such that every
three sets A1 ∈ Fi1 , A2 ∈ Fi2 , A3 ∈ Fi3 , for 1 ≤ i1 < i2 < i3 ≤ 6, have a line transversal,
then there is a family Fi that can be crossed by 3 lines.
In addition, we prove the following theorem. Let K be a compact convex set in R
2. If
F1,F2,F3 are finite families of translates of K such that every three sets A1 ∈ F1, A2 ∈
F2, A3 ∈ F3 have a line transversal, then there is a family Fi that can be crossed by 4
lines.
Finally, we present new problems and conjectures related to these colorful versions of
Eckhoff’s theorems.
10 INTRODUCTION
Introducción
Los conjuntos convexos son objetos geométricos con propiedades muy interesantes y han
sido estudiados en varias áreas de las matemáticas. En particular, geometŕıa discreta y convexa
es una rama de las matemáticas discretas que tiene el propósito de estudiar las propiedades
combinatorias de conjuntos convexos. Los teoremas clásicos en geometŕıa discreta y convexa son
los teoremas de Carathéodory [8] (en 1907), Radon [34] (en 1921) y Helly [18] (en 1923). Para
empezar a ver las ideas geométricas y combinatorias enunciamos el teorema de Carathéodory
[8] y el teorema de Helly [18].
El teorema de Carathédory nos dice que si un punto a ∈ R
d está en la envolvente convexa
de un conjunto A ⊂ R
d, entonces existen a lo más d + 1 puntos en A tal que su envolvente
convexa contiene el punto a. En otras palabras, para saber si un punto está en la envolvente
convexa de un conjunto A solo necesitamos saber si el punto está en la envolvente convexa de
un subconjunto finito (de tamaño a lo más d+ 1) de A.
El teorema de Helly nos dice que si una familia finita de conjuntos convexos en R
d cumple que
cada d+1 o menos de ellos tienen intersección no vaćıa, entonces toda la familia tiene intersección
no vaćıa. De hecho, el resultado también es cierto para familias infinitas de conjuntos convexos
y compactos. En otras palabras, el teorema de Helly nos dice que solo necesitamos información
sobre la intersección de subfamilias finitas (de tamaño d+1) para saber si toda la familia tiene
intersección no vaćıa.
Por otro lado, hay muchos teoremas en matemáticas discretas que tiene versiones coloreadas.
Por ejemplo, Lovász probó el teorema de Helly coloreado en 1973 (ver [4]). Además, en 1982
Bárány [4] probó el teorema de Carathéodory coloreado.
El teorema de Helly coloreado nos dice que si tenemos d+1 familias finitas F1, . . . ,Fd+1 de
conjuntos convexos en R
d tal que para cada elección de conjuntos C1 ∈ F1, . . . , Cd+1 ∈ Fd+1,
la intersección
⋂d+1
i=1 Ci es no vaćıa, entonces existe i ∈ {1, . . . d+ 1} tal que la familia Fi tiene
intersección no vaćıa.
El teorema de Carathéodory coloreado nos dice que si tenemos d + 1 conjuntos finitos
A1, . . . , Ad+1 de puntos en R
d tal que el origen está contenido en la envolvente convexa de cada
conjunto Ai, para i = 1, . . . , d + 1, entonces existen d + 1 puntos a1 ∈ A1, . . . , ad+1 ∈ Ad+1 tal
que el origen está contenido en la envolvente convexa de {a1, . . . , ad+1}.
Note que el caso particular del teorema de Helly coloreado donde todas las familias son
la misma familia, es el teorema de Helly. Por lo tanto, el teorema de Helly coloreado es una
generalización del teorema de Helly. Por un argumento similar, el teorema de Carathéodory co-
loreado es una generalización del teorema de Carathéodory. En general, los teoremas coloreados
11
12 INTRODUCCIÓN
la mayoŕıa de las veces son generalizaciones de sus versiones no coloreadas.
El nombre coloreado es porque podemos pensar que cada familia está coloreada (y cada
familia tiene un color diferente). Entonces los teoremas coloreados siguen alguna de las siguientes
dos ideas.
• En las hipótesis de los teoremas coloreados tenemos información sobre subfamilias arcóıris
y la conclusión es sobre subfamilias del mismo color.
• En las hipótesis de los teoremas coloreados tenemos información sobre subfamilias del
mismo color y la conclusión es sobre subfamilias arcóıris.
Por ejemplo, en el teorema de Helly coloreado tenemos información sobre la intersección de
subfamilias arcóıris y la conclusión es sobre la intersección de una subfamilia del mismo color.
Por otro lado, en el teorema de Carathéodory coloreado tenemos información sobre conjuntos
del mismo color y la conclusión es sobre un conjunto arcóıris.
Este trabajo tiene dos propósitos. Por un lado, presentamos una colección de varios teoremas
coloreados en geometŕıa discreta y convexa, introduciendo las ideas de las pruebas intuitivamen-
te en dimensiones bajas. Por otro lado, también presentamos nuevos resultados sobre teoremas
coloreados y mejoramos cotas de teoremas coloreados.
En el Caṕıtulo 1 vemos una introducción a geometŕıa convexa y presentamos las definiciones
y la notación que usamos en este trabajo. Presentamos los teoremas clásicos de geometŕıa
convexa: Carathéodory [8], Helly [18] y Radon [34]. También vemos los teoremas de Eckhoff
sobre transversales.
En el Caṕıtulo 2 probamos los teoremas clásicos coloreados en geometŕıa convexa: Helly
coloreado (por Lovász en 1973, ver [4]), Carathéodory coloreado (por Bárány [4] en 1982) y
Radon coloreado (por Lovász en 1989, ver [2]).
En el Caṕıtulo 3 vemos las siguientes dos generalizaciones de los teoremas coloreados clásicos.
• Pach, Holmsen y Tverberg [21] (en 2008) e independientemente Arocha, Bárány, Bracho,
Fabila y Montejano [1] (en 2009) probaron que podemos debilitar las hipótesis del teorema
de Carathéodory coloreado y obtener la misma conclusión. Ellos probaron que si tenemos
d+1 conjuntos finitos A1, . . . , Ad+1 de puntos en R
d tal que el origen está contenido en la
envolvente convexa de Ai∪Aj para cada 1 ≤ i < j ≤ d+1, entonces existen d+1 puntos
a1 ∈ A1, . . . , ad+1 ∈ Ad+1 tal que el origen está contenido en la envolvente convexa de
{a1, . . . , ad+1}. Además, nosotros probamos que este resultado no puede ser generalizado
en dos sentidos diferentes.
• En el 2020, Mart́ınez-Sandoval, Roldán-Pensado y Rubin [28] se preguntaron si hay más
consecuencias usando las mismas hipótesis del teorema de Helly coloreado. Ellos probaron
que para cada dimensión d ≥ 2 existen números f(d) y g(d) con la siguiente propiedad.
Si F1, . . . ,Fd son familias finitas de conjuntos convexos en R
d tal que para cada elección
de conjuntos C1 ∈ F1, . . . , Cd ∈ Fd la intersección
⋂d
i=1 Ci es no vaćıa, entonces hay
una familia Fj que puede ser pinchada por f(d) puntos, o la familia
⋃d
i=1 Fi puede ser
atravezada por g(d) ĺıneas. En particular, ellos probaron que su resultado en el plano
(d = 2) se cumple con f(2) = 1 y g(2) = 4.
INTRODUCCIÓN 13
En el Caṕıtulo 4 presentamos nuestros resultados. Primero vemos los preliminares topológi-
cos que usamos para probar nuestros resultados. Después, vemos los siguientes resultados y
problemas:
• Nosotros mejoramos el caso 2-dimensional del teorema de Mart́ınez-Sandoval, Roldán-
Pensado y Rubin [28]; nosotros probamos que el caso 2-dimensional de su teorema también
se cumple con f(2) = 1 y g(2) = 2. Probamos que si F1, . . . ,Fn son familias finitas de
conjuntos convexos en R
2 (con n ≥ 2), tal que A∩B 6= ∅ para cada A ∈ Fi y B ∈ Fj (con
i 6= j), entonces existe j ∈ {1, 2, . . . , n} tal que
⋃
i 6=j Fi puede ser pinchado por 1 punto,
o la familia
⋃n
i=1 Fi puede ser atravezada por 2 ĺıneas. Además, también probamos que
si K es un conjunto convexo y compacto en el plano y F1, . . . ,Fn son familias finitas de
trasladados de K (con n ≥ 2), tal que A∩B 6= ∅ para cada A ∈ Fi y B ∈ Fj (con i 6= j),
entonces existe j ∈ {1, 2, . . . , n} tal que
⋃
i 6=j Fi puede ser pinchado por 3 puntos, o la
familia
⋃n
i=1 Fi puede ser atravezada por 1 ĺınea. También probamos resultados similares
para familias de homotéticos, ćırculos y rectángulos.
• Vemos un problema abierto propuesto por Mart́ınez-Sandoval, Roldán-Pensado y Rubin
[28]. El problema es si existe n ∈ Z
+ tal que para todas dos familias A, B de conjuntos
convexos en R
3 tal que A∩B 6= ∅ se cumple para cada A ∈ A y B ∈ B, una de las familias
A o B puede ser cruzado por n ĺıneas. Vemos un caso particular de este problema (para
familias pequeñas) resuelto por Montejano y Karasev ([32], [33]) y vemos una prueba
elemental (para familias pequeñas) por Strausz [41]. Además, nosotros proponemos una
idea geométrica para reducir el problema abierto a un problema topológico.
• Nosotros probamos versiones coloreadas de los teoremas de Eckhoff.
Probamos que si F1, . . . ,F4 son familias finitas de conjuntos conexos en R
2 tal que cada
cuatro conjuntos A1 ∈ F1, A2 ∈ F2, . . . , A4 ∈ F4 tienen una ĺınea transversal, entonces
hay una familia Fi que puede ser cruzada por 2 ĺıneas.
Probamos que si F1, . . . ,F6 son familias finitas de conjuntos conexos en R
2 tal que cada
tres conjuntos A1 ∈ Fi1 , A2 ∈ Fi2 , A3 ∈ Fi3 , para 1 ≤ i1 < i2 < i3 ≤ 6, tienen una ĺınea
transversal, entonces hay una familia Fi que puede ser cruzada por 3 ĺıneas.
Además, nosotros también probamos el siguiente teorema. Sea K un conjunto compacto
y convexo en R
2. Si F1,F2,F3 son familias finitas de trasladados de K tal que cada tres
conjuntos A1 ∈ F1, A2 ∈ F2, A3 ∈ F3 tienen una ĺınea transversal, entonces hay una
familia Fi que puede ser cruzada por 4 ĺıneas.
Finalmente, presentamos nuevos problemas y conjeturas relacionados con estas versiones
coloreadas de los teoremas de Eckhoff.
14 INTRODUCCIÓN
Chapter 1
Convex geometry
In this chapter we give an introduction to convex geometry. In Section 1.1 we see the
definitions and the notation that we use in this thesis. In Sections 1.2 and 1.3 we see some of
the classical theorems in convex geometry.
1.1. Convexity
Most of the results in this work are concerning convex sets. Intuitively, a convex set is a set
without holes. To formally define a convex set, we have to recall the definition of a segment.
For any two points a, b ∈ R
d, we define the segment [a, b] as the set
[a, b] = {αa+ βb : α, β ≥ 0, α + β = 1}.
Definition 1.1. A set C ⊂ R
d is convex if for every two points a, b ∈ C, the segment [a, b] is
contained in C.
To give the first example of a convex set, let us recall that a hyperplane H in R
d is a set
H = {x ∈ R
d : u · x = a},
for some u ∈ R
d \ {0} and a ∈ R. The hyperplane H = {x ∈ R
d : u · x = a} define two half
spaces denoted as H+ = {x ∈ R
d : u · x ≥ a} and H− = {x ∈ R
d : u · x ≤ a}. An immediate
observation is that the hyperplane H and the half spaces H+ and H− are convex sets.
For the second example of a convex set, we need the following definition.
Definition 1.2. Let x = (x1, . . . , xd), y = (y1, . . . , yd) ∈ R
d be two different points. Let j =
min{i : xi 6= yi}. If xj < yj we say that x is less than y with the lexicographical order and
denote it as x <lex y (if xj > yj, then x >lex y). For every two points x, y ∈ R
d, we denote
x ≤lex y if x is less than y with the lexicographic order or x = y.
Note that for any point q ∈ R
d, the set C = {x ∈ R
d : x <lex q} is a convex set.
Let A ⊂ R
d. We say that
α1a1 + · · ·+ αnan
15
16 CHAPTER 1. CONVEX GEOMETRY
is a convex combination of elements of A, if {a1, . . . , an} ⊂ A, α1 + · · ·+αn = 1 and αi ≥ 0 for
all i = 1, . . . , n.
The convex hull of A, denoted by conv(A), is the set of all the convex combinations of
elements of A. Note that conv(A) is the smallest convex set that contains A.
In this work we focus on the combinatorial properties of convex sets. For instance, an
important observation is that the intersection of convex sets is also a convex set. We are
interested in the necessary conditions for a family of convex sets to have non-empty intersection.
Another goal is to impose hypotheses to a family to get weaker conclusions; for example,
sometimes the goal is to intersect the family by few points or few lines instead of having it
intersect. Now, we present the definitions and the notation we use in these geometric results.
An affine subspace is a set x + L, where x ∈ R
d is some vector and L is a linear subspace
of Rd. A k-flat is an affine subspace of dimension k. For instance, a line is a 1-flat and an
hyperplane is a (d− 1)-flat in R
d.
Let F be a family of sets in R
d. A set T ⊂ R
d is a transversal to the family F if every set
C ∈ F intersects the set T . Additionally, if T is a k-flat and is transversal to the family F , we
say that T is a k-flat transversal. For example, a line transversal is a line that intersects every
member of F , and a hyperplane transversal is a hyperplane that intersects every member of F .
Let F be a family of sets in R
d and let n ∈ Z
+. We say that the family F can be pierced by
n points if there exist n points p1, . . . , pn ∈ R
d such that every set C ∈ F intersects some of the
points p1, . . . , pn (in other words, P = {p1, . . . , pn} is a transversal to the family F). We say
that the family F can be crossed by n lines if there exist n lines l1, . . . , ln ∈ R
d such that every
set C ∈ F intersects some of the lines l1, . . . , ln (in other words, l1 ∪ · · · ∪ ln is a transversal to
the family F).
Although the results in this thesis are concerning convex sets, sometimes convexity is not
sufficient to prove the results. For that reason there are results where we need additional
hypotheses. For example, sometimes the results hold only for families of translates of some
compact convex set or families of constant width sets.
Given K ⊂ R
d, we say that K + x (for some x ∈ R
d) is a translate of K. Given K ⊂ R
d
compact convex set, for every direction u ∈ S
d−1, there are two tangent hyperplanes l1, l2 to
K such that l1 and l2 are orthogonal to u and the strip bounded by the two hyperplanes l1, l2
contains K. The width of the strip is the width of K in the direction u (see Figure 1.1).
(x− y) · u
x
y
l1
l2
Figure 1.1: Definition of the width of K in the direction u.
1.2. CARATHÉODORY, RADON AND HELLY 17
Formally, we define the width of K in the direction u as
max{(x− y) · u : x, y ∈ K}.
We say that K ⊂ R
d is of constant width if K has the same width in every direction.
Let K,L be two disjoint compact convex sets in the plane. It is known that there are exactly
four tangent lines to K and L (see [13] or [29, page 260]). These lines are called the inner or
outer common tangents of K and L (see Figure 1.2).
K L
l1
l2
l3
l4
Figure 1.2: The lines l1 and l2 are the inner common tangents of K and L, and the lines l3 and
l4 are the outer common tangents of K and L.
1.2. Carathéodory, Radon and Helly
In this section we state the three classical theorems in convex geometry: Carathéodory’s
theorem [8], Helly’s theorem [18] and Radon’s lemma [34]. We do not prove these theorems in
this section. Despite this, the reader interested in the proofs of the theorems in this section
can consult [29] and [5].
We begin with Carathédory’s theorem, proved by Carathédory [8] in 1907. According to
Bárány (see [5, page 9]), this theorem is probably the first result in combinatorial convexity.
Carathédory’s theorem states that if a point a ∈ R
d is in the convex hull of some set A ⊂ R
d,
then there exist at most d+ 1 points in A such that their convex hull contains the point a (see
Figure 1.3). In other words, in order to know if a point is in the convex hull of some set A we
only need to know if the point is in the convex hull of a finite subset (of size at most d+ 1) of
A.
Theorem 1.3. (Carathéodory’s theorem) Let A ⊂ R
d and a ∈ conv(A). Then there exists
B ⊂ A with |B| ≤ d+ 1 such that a ∈ conv(B).
In Section 2.1 we show the Colorful Carathéodory theorem (proved by Bárány [4] in 1982),
that implies the Carathéodory theorem (Theorem 1.3). Additionally, in Section 3.1 we give a
generalization of the Colorful Carathéodory theorem (proved by Holmsen, Pach and Tverberg
[21] in 2008 and independently by Arocha, Bárány, Bracho, Fabila and Montejano [1] in 2009).
18 CHAPTER 1. CONVEX GEOMETRY
Figure 1.3: In the plane, Caratheodory’s theorem states that if a point is in the convex hull of
some set of points, then the point is in the convex hull of at most 3 points.
Now, we shall see Helly’s theorem, which is probably the most famous theorem in convex
and discrete geometry. According to Bárány (see [5, page 29]), Helly discovered his theorem in
1913, but he did not publish it until 1923 [18] due to the First World War.
Helly’s theorem states that if we have a finite family of convex sets in R
d such that every
d+ 1 or fewer of them have a non-empty intersection, then the whole family has a non-empty
intersection (see Figure 1.4). In other words, Helly’s theorem states that we only need informa-
tion concerning the intersection of finite subfamilies of size d+ 1 in order to know if the whole
family has a non-empty intersection.
Figure 1.4: In the plane, Helly’s theorem states that if a family has empty intersection, then
there are three sets in the family with empty intersection.
Theorem 1.4. (Helly’s theorem). Let F = {C1, C2, . . . , Cn} be a finite family of convex sets in
R
d such that for every I ⊂ {1, 2, . . . , n} with |I| ≤ d+1, the intersection
⋂
i∈I Ci is non-empty.
Then
⋂
F 6= ∅.
In Section 2.2 we show the Colorful Helly theorem (proved by Lovász in 1973), that implies
Helly’s theorem. Additionally, in Section 3.2 we give a generalization of the Colorful Helly
theorem (proved by Mart́ınez-Sandoval, Roldán-Pensado and Rubin [28] in 2020).
Note that Helly’s theorem holds for finite families, however Helly’s theorem does not hold
for infinite families as we see in Example 1.5.
1.2. CARATHÉODORY, RADON AND HELLY 19
Example 1.5. For any i ∈ Z
+, let H+
i be the half space defined by the equation x1 ≥ i. Let
F = {H+
i }i∈Z+. For i1 < i2 < · · · < id+1 positive integers, we have that
H+
i1
∩H+
i2
∩ · · · ∩H+
id+1
= H+
id+1
6= ∅,
then the family F satisfies the hypothesis of Helly’s theorem (Theorem 1.4). However,
⋂
F = ∅.
Despite this, Helly’s theorem is also true for infinite families if we assume that the sets are
compact (see [5, Theorem 7.3] or [29, Theorem 1.3.3]).
Theorem 1.6. (Infinite Helly theorem) Let F = {Ci : i ∈ J} be a infinite family of compact
convex sets in R
d such that for every I ⊂ J with |I| = d + 1, the intersection
⋂
i∈I Ci is
non-empty. Then
⋂
F 6= ∅.
In fact, although in Helly’s theorem (Theorem 1.4) we do not need the sets to be compact, we
can assume that the sets are compact without losing generality. Indeed, if F = {C1, C2, . . . , Cn}
are convex sets satisfying the hypothesis of Theorem 1.4 and we denote CI =
⋂
i∈I Ci, then for
each I so that CI 6= ∅, we can choose pI ∈ CI . Then, let
Ki = conv({pI : CI 6= ∅, i ∈ I}).
We notice that the setsKi are compact convex sets satisfying the hypothesis of Theorem 1.4 and
Ki ⊂ Ci. Hence, if
⋂n
i=1 Ki is non-empty,
⋂n
i=1 Ci is non-empty. Therefore, in Helly’s theorem
(Theorem 1.4) we can assume without loss of generality that the sets are also compact.
On the other hand, we have a connection between intersections of convex sets and intersec-
tions of half-spaces.
Theorem 1.7. Let C1, . . . , Cn be convex sets in R
d, with n ≥ 2. Then
⋂n
i=1 Ci = ∅ if and
only if there are hyperplanes H1, . . . , Hn such that the closed half-spaces H+
1 , . . . , H
+
n satisfy
Ci ⊂ H+
i for all i and
⋂n
i=1 H
+
i = ∅.
The proof of Theorem 1.7 can be consulted in [5, page 30]. The particular case when n = 2
is a very useful lemma in discrete geometry and is known as the separation theorem.
We finish this section with Radon’s lemma. In 1921, Radon [34] gave an elementary and
beautiful proof of Helly’s theorem (Theorem 1.4). The idea was to take a point in the inter-
section of every subfamily of size d + 1, then Radon studied the combinatorial properties of
the points in order to prove Helly’s theorem. In particular, Radon [34] proved the following
theorem (see Figure 1.5).
Theorem 1.8. (Radon’s theorem). Let A be a set of d+ 2 points in R
d. Then there exists two
disjoint subsets A1, A2 ⊂ A such that conv(A1) ∩ conv(A2) 6= ∅.
In Section 2.3 we see a Colorful Radon theorem (by Lovász, see [2]) and a proof by Soberón
[37], which is very similar to the proof of Radon’s lemma.
20 CHAPTER 1. CONVEX GEOMETRY
Figure 1.5: The two examples of Radon’s theorem in the plane.
1.3. Transversals
In Section 1.2 we saw Helly’s theorem (Theorem 1.4) which states that a finite family of
convex sets in R
d has non-empty intersection if each d + 1 sets of the family have non-empty
intersection. A natural question is whether we have a similar conclusion if in the hypothesis
we only have that each d sets of the family have non-empty intersection. A first answer is the
following Proposition.
Proposition 1.9. Let F be a finite family of convex sets in R
d such that the intersection of
every d sets in F is non-empty. Then F has a line transversal.
Sometimes, mathematicians restrict the results to some families and obtain stronger results
for these families. For instance, Grunbaum [16] (in 1959) proved the following theorem for
families of homothets of a convex set.
Theorem 1.10. For any integer d ≥ 1 there exists an integer c = c(d) such that the following
holds. If F is a finite family of homothets of a convex set in R
d and any two members of F
have non-empty intersection, then F can be pierced by c points.
The special case of circles in the plane was solved by Danzer [10] (in 1956, but not published
until 1986).
Theorem 1.11. Let F be a finite family of circles in R
2 such that the intersection of every 2
sets in F is non-empty. Then F can be pierced by 4 points.
In addition, Karasev [23] (in 2000) proved the following theorem for families of translates
of a compact convex set in the plane (in fact, Karasev [24] also proved similar results in higher
dimensions).
Theorem 1.12. Let K be a compact convex set in R
2. Let F be a finite family of translates
of K such that the intersection of every 2 sets in F is non-empty. Then F can be pierced by 3
points.
It is also known (see [17, page 7]) the following result concerning rectangles with sides
parallel to the coordinate axes in the plane.
Theorem 1.13. Let F be a finite family of rectangles with sides parallel to the coordinate axes
in R
2 such that the intersection of every 2 sets in F is non-empty. Then F 6= ∅ (in other
words, F can be pierced by 1 point).
1.3. TRANSVERSALS 21
In Section 3.2 we see colorful versions of Proposition 1.9. In Section 4.2 we see colorful
versions of Theorems 1.10, 1.11, 1.12 and 1.13.
Proposition 1.9 shows that we can weaken the hypothesis of Helly’s theorem (Theorem 1.4)
and obtain interesting results regarding transversals. Now, we want to answer what conclusions
we can obtain if now the hypothesis concerns line transversals (instead of information concerning
intersections).
Let F be a family of sets in the plane. We say that the family F has the property T (r)
if every r sets in F have a line transversal. Motivated by Helly’s theorem (Theorem 1.4), we
wonder whether there exists r ∈ Z
+ such that for any finite family F (of convex sets) in the
plane, if the family F has the property T (r), then F has a line transversal. However, Santaló
[35] (in 1940) and Danzer [9] (in 1957) observed that for any integer n ≥ 3 there is a family of
n convex sets in the plane satisfying the property T (n − 1) while the family does not have a
line transversal.
Even though a family satisfying the property T (r) does not necessary have a line transversal,
we wonder if such families can be crossed by few lines. In 1969, Eckhoff [11] proved that any
finite family of convex sets in the plane satisfying the property T (4) can be crossed by 2 lines.
Theorem 1.14. Let F be a finite family of connected sets in R
2. If every four sets in F have
a line transversal (in other words, F has the property T (4)), then the family F can be crossed
by 2 lines (the lines can actually be chosen to be orthogonal).
The following question was if there exists n ∈ Z
+ such that any finite family (of convex
sets) in the plane satisfying the property T (3) can be crossed by n lines. In 1973, Eckhoff [12]
gave an example of a finite family of compact convex sets in the plane satisfying the property
T (3) and the family cannot be crossed by 2 lines. Fortunately, in 1974, Kramer [26] proved
that any finite family of convex sets in the plane satisfying the property T (3) can be crossed by
5 lines. In 1993, Eckhoff [13] proved that actually the finite families of convex sets in the plane
with the property T (3) can be crossed by 4 lines. So during several years an open question was
if such families can be crossed by 3 lines. In 2021, McGinnis and Zerbib [31] proved that any
finite family of connected sets in the plane that satisfies the property T (3) can be crossed by 3
lines, and the problem is over.
Theorem 1.15. Let F be a finite family of connected sets in R
2. If every three sets in F have
a line transversal (in other words, F has the property T (3)), then the family F can be crossed
by 3 lines.
It is known that Theorems 1.14 and 1.15 are also true for infinite families if we assume that
the sets are compact (see [11]).
In addition, in Theorems 1.14 and 1.15 we can assume that the sets are compact and we
do not lose generality. This is because for a finite family F = {A1, A2, . . . , An} satisfying the
hypothesis of Theorem 1.15 (or Theorem 1.14) we define another family of compact sets as
follows. For every three sets in the family F we choose a line transversal for these sets. Then,
for every set in the family F and every one of these lines that intersects the set, take a point
in the intersection of the set and the line. Let X be the set of all these points. Note that the
family
G = {conv(Ai ∩X) : Ai ∈ F}
22 CHAPTER 1. CONVEX GEOMETRY
of compact sets satisfies the hypothesis of Theorem 1.15 (or Theorem 1.14). Besides, for each
Ai ∈ F , we have that conv(Ai ∩X) ⊂ conv(Ai). Hence, if the family G can be crossed by few
lines, F can also be crossed by few lines. Therefore, in Theorems 1.14 and 1.15 we can assume
without loss of generality that the sets are also compact.
In Section 4.4 we prove colorful versions of Theorems 1.14 and 1.15, which are generalizations
of these theorems. The main tools to prove our results (the colorful versions of Theorems 1.14
and 1.15) are the Colorful KKM theorem (Theorem 4.4 in Section 4.1) and the following lemma.
In fact, the following lemma has been very useful to prove theorems concerning line transversals
in the plane, in particular was used in [26] and [13].
Lemma 1.16. Let C1, C2, C3 ⊂ R
2 be convex sets. The following two conditions are equivalent:
(i) There is no line transversal for C1, C2, C3.
(ii) For each i ∈ {1, 2, 3}, the set Ci can be strictly separated by a line of
⋃
j 6=i Cj.
In fact, Lemma 1.16 is also true in arbitrary dimension (proved by Goodman, Pollack and
Wenger in 1996 [15]), although we do not use it in this work.
Lemma 1.17. Let C1, C2, . . . , Cd+1 ⊂ R
d be convex sets. The following two conditions are
equivalent:
(i) There is no hyperplane transversal for C1, C2, . . . , Cd+1.
(ii) For each non-empty I ⊂ {1, 2, . . . , d + 1}, the sets
⋃
i∈I Ci can be strictly separated by a
hyperplane of
⋃
j /∈I Cj.
Furthermore, Goodman, Pollack and Wenger proved the following stronger result concerning
k-flats.
Lemma 1.18. Let C1, C2, . . . , Ck+2 ⊂ R
d be convex sets. The following two conditions are
equivalent:
(i) There is no k-flat transversal for C1, C2, . . . , Ck+2.
(ii) For each non-empty I ⊂ {1, 2, . . . , k + 2}, the sets
⋃
i∈I Ci can be strictly separated by a
hyperplane of
⋃
j /∈I Cj.
Chapter 2
Colorful theorems
In this chapter we see generalizations of the classical theorems in convex geometry, which
are known as colorful theorems. According to Bárány (see [5, page 49]), Lovász proved the
Colorful Helly theorem in 1973, although he did not publish it. In 1982, Bárány [4] proved
the Colorful Carathéodory theorem and gave another proof of the Colorful Helly theorem. In
addition, Lovász proved a Colorful Radon theorem and his proof was published in [2]. In the
next sections we prove these colorful theorems by introducing the ideas of the proofs in low
dimensions.
2.1. Colorful Carathéodory
Imagine we have red points and blue points in the real line. Suppose that the convex hull
of the red points contains the origin and the convex hull of the blue points also contains the
origin (see Figure 2.1). Since the convex hull of the red points contains the origin, there must
be a negative red point and a positive red point. Analogously, there must be a negative blue
point and a positive blue point. Therefore, we can take a negative red point and a positive blue
point and the convex hull of them also contains the origin. If we have a red point and a blue
point we say that the segment joining these two points is a rainbow segment. We can notice
that we proved that there is a rainbow segment containing the origin. In fact, if now we take
a negative blue point and a positive red point, then the convex hull of them also contains the
origin. Therefore, there are at least two rainbow segments containing the origin.
O
Figure 2.1: An example of blue points containing the origin and red points containing the
origin.
A natural question is if we have similar results in higher dimensions. Let A1, A2, . . . , An be
finite point sets in R
d. We say that T ⊂
⋃n
i=1 Ai is a rainbow set and conv(T ) is a rainbow
simplex if |T ∩Ai| ≤ 1 for each 1 ≤ i ≤ n. If we suppose that a ∈
⋂n
i=1 conv(Ai) for some point
a ∈ R
d, the question is if there are rainbow simplexes containing the point a. For example, we
have the following result in the plane.
23
24 CHAPTER 2. COLORFUL THEOREMS
Proposition 2.1. Let A1, A2, A3 be finite point sets in R
2 and a ∈ R
2 so that a ∈
⋂3
i=1 conv(Ai).
Then, for each a1 ∈ A1, there exist a2 ∈ A2, a3 ∈ A3 so that a ∈ conv({a1, a2, a3}). In
particular, there are at least as many rainbow simplexes containing a as the cardinality of A1.
Proof. Let a1 ∈ A1. Since a ∈ conv(A2), by the 2-dimensional case of Carathéodory’s theorem
(Theorem 1.3), there are three points b1, b2, b3 ∈ A2 such that a ∈ conv({b1, b2, b3}). Set
B = {b1, b2, b3}.
Let l be the line through a1 and a. Denote by l+ and l− the closed half-planes bounded by
l. By the pigeon-hole principle one of the half-planes bounded by l contains at least 2 points
of B, without loss of generality l+ contains at least 2 points of B. Since a ∈ conv(B), then l−
contains at least 1 point of B. Without loss of generality, b1, b2 are in l+ and b3 is in l−.
For any i = 1, 2, 3, let li be the line trough bi and a, and let l+i be the closed half-plane
bounded by li that does not contain a1 (see Figure 2.2). Let R1 = l+1 ∩ l−, R2 = l+2 ∩ l−,
R3 = l+3 ∩ l+, and R4 = R
2 \ (
⋃3
i=1 Ri).
a
a1 b1
b2
b3
ll1
l2
l3
Figure 2.2: Illustration for the proof of Theorem 2.1.
If A3 ∩ (
⋃3
i=1 Ri) = ∅, then A3 ⊂ R4 and hence A3 does not contain the point a, a contra-
diction. Otherwise, we can assume that A3 ∩ (
⋃3
i=1 Ri) 6= ∅. Then there is j ∈ {1, 2, 3} such
that A3 ∩Rj 6= ∅.
Let cj ∈ A3 ∩Rj. Therefore, conv({a1, bj, cj}) is a rainbow simplex that contains a.
Note that we have the following reformulation of Proposition 2.1 using only 2 colors.
Proposition 2.2. Let A1, A2 be finite point sets in R
2 and a ∈ R
2 so that a ∈
⋂2
i=1 conv(Ai).
Then, for each x /∈
⋃2
i=1 Ai, there exist a1 ∈ A1, a2 ∈ A2 so that a ∈ conv{x, a1, a2}.
We have a similar result in arbitrary dimensions and it is known as the Colorful Carathéodory
theorem made by Bárány [4] in 1982. The idea of the proof is to use the extremal principle.
Theorem 2.3. (Colorful Carathéodory). Let A1, A2, . . . , Ad+1 be finite point sets in R
d and
a ∈ R
d so that a ∈
⋂d+1
i=1 conv(Ai). Then there exist a1 ∈ A1, a2 ∈ A2, . . . , ad+1 ∈ Ad+1 so that
a ∈ conv{a1, a2, . . . , ad+1}.
Proof. Let T = {a1, a2, . . . , ad+1} be a rainbow set (with ai ∈ Ai for every i = 1, . . . , d + 1)
such that the distance of conv(T ) to a is the smallest possible. If the distance of conv(T ) to a
2.1. COLORFUL CARATHÉODORY 25
is 0, then a ∈ conv(T ) and we are done. Otherwise, we assume that the distance of conv(T ) to
a is greater than 0 in order to get a contradiction.
Let p ∈ conv(T ) be the point of conv(T ) closest to a. Let H be the hyperplane containing
p and orthogonal to the segment [a, p], and denote by H+ the closed halfspace bounded by H
and containing a. Let
B(a, p) = {x ∈ R
d : ‖a− x‖ < ‖a− p‖}
be the open ball centered at a through p (see Figure 2.3).
a1 a2
a3
a
p
b
H
H+
H−
Figure 2.3: Illustration for the proof of Theorem 2.3 (in the plane).
We claim that conv(T ) ⊂ H−, where H− is the closed halfspace bounded by H which does
not contain a. Indeed, if there exists y ∈ conv(T ) ∩ (H+ \ H), then the segment [p, y] meets
B(a, p) at a point q. Note that q ∈ B(a, p) is a point in conv(T ) closer to a than p, contradicting
that p ∈ conv(T ) is the point of conv(T ) closest to a. Then conv(T ) ⊂ H−.
Since conv(T ) ⊂ H−, we have that p ∈ H ∩ conv(T ) = conv(H ∩ T ). By the Carathéodory
theorem (Theorem 1.3) in dimension d− 1, there exist at most d points in T ∩H such that the
convex hull of them contains p. Without loss of generality,
p ∈ conv({a1, a2, . . . , ad}).
Since a ∈ conv(Ad+1), then there exists b ∈ Ad+1 ∩ (H+ \H). Let
S = {a1, a2, . . . , ad, b}.
Since p ∈ conv({a1, a2, . . . , ad}), then the segment [b, p] is contained in conv(S). Note that [b, p]
meets B(a, p) at a point r, then r ∈ B(a, p) is a point in conv(S) closer to a than p. Hence
conv(S) is a rainbow simplex closer to a than conv(T ), a contradiction.
Note that Theorem 2.3 implies Theorem 1.3. Indeed, if A ⊂ R
d and a ∈ conv(A), then the
sets Ai = A for i = 1, . . . , d+ 1 satisfy the hypothesis of Theorem 2.3, thus there exist at most
d+ 1 points in A such that their convex hull contains the point a.
26 CHAPTER 2. COLORFUL THEOREMS
2.2. Colorful Helly
Imagine we have red intervals and blue intervals in the real line. Suppose that every red
interval and every blue interval have non-empty intersection. Then we want to prove that either
the red intervals have non-empty intersection or the blue intervals have non-empty intersection
(see Figure 2.4). We begin this section with two different proofs of this fact.
( ) ( )( )( )(( ))
r1 r2 r3 r4r5 r6
b1 b2b3 b4b5 b6
Figure 2.4: An example of three red intervals, (r1, r2), (r3, r4), (r5, r6), and three blue intervals,
(b1, b2), (b3, b4), (b5, b6), such that every red interval intersect every blue interval. In this example
the blue intervals have non-empty intersection.
In the first proof we use the 1-dimensional case of Helly’s theorem. If every two red intervals
have non-empty intersection, then by Helly’s theorem (Theorem 1.4) the red intervals have
non-empty intersection. Otherwise, there are two disjoint red intervals (r1, r2), (r3, r4), with
r1 < r2 < r3 < r4. Since every blue interval intersects the intervals (r1, r2), (r3, r4), then
r2 + r3
2
is in every blue interval. Therefore, the blue intervals have non-empty intersection.
In the second proof we do not use the 1-dimensional case of Helly’s theorem, however it is
less intuitive. The idea is to use the extremal principle. For every interval (x1, x2) (either red
interval or blue interval), we consider its minimal point with the lexicographic order, that is
the point x1. Let X be the set of all the points which are the minimal point of some interval
(either red interval or blue interval). In other words,
X = {x1 ∈ R : there is x2 ∈ R such that (x1, x2) is either a red interval or a blue interval}.
Let x = maxX. Without loss of generality, we assume x is the minimal point of some red
interval (x, y). We claim that x is in every blue interval. Let (b1, b2) be any blue interval.
Since x = maxX, then b1 < x. In addition, the intervals (b1, b2) and (x, y) have non-empty
intersection, then b2 > x. Therefore, x ∈ (b1, b2) and the blue intervals have non-empty
intersection.
As in the last section, we have a similar result in arbitrary dimensions and it is known as the
Colorful Helly theorem made by Lovász (see [4] and [5, page 49]). Let F1, . . . ,Fn be families
of convex sets in R
d. We say that F ⊂
⋃n
i=1 Fi is a rainbow subfamily if |F ∩ Fi| ≤ 1 for each
1 ≤ i ≤ n. The Colorful Helly theorem states that if every rainbow subfamily of size d+ 1 has
non-empty intersection, then there is some family Fi with non-empty intersection. The proof
is very similar to the second proof that we saw of the 1-dimensional case, in particular, we use
the extremal principle.
Theorem 2.4. (Colorful Helly). Let F1, . . . ,Fd+1 be finite families of convex sets in R
d such
that for every choice of sets C1 ∈ F1, . . . , Cd+1 ∈ Fd+1, the intersection
⋂d+1
i=1 Ci is non-empty.
Then there exists i ∈ {1, . . . , d+ 1} such that
⋂
Fi 6= ∅.
Proof. We can assume, without loss of generality, that the sets in the families Fi are compact
(see Section 1.2). Then for every rainbow subfamily of size d, we consider the lexicographically
2.3. COLORFUL RADON 27
minimum of its intersection. We take a rainbow subfamily of size d such that the lexicograph-
ically minimum of its intersection is maximum among all the lexicographically minimum of
intersections of rainbow subfamilies. Without loss of generality, we assume that
{C1, C2, . . . , Cd}
is a rainbow subfamily, with Ci ∈ Fi for each 1 ≤ i ≤ d, and such that the lexicographically
minimum p of
⋂d
i=1 Ci is maximum. We claim that p ∈
⋂
Fd+1.
Let Cd+1 ∈ Fd+1 be any convex set in the family Fd+1. By hypothesis,
⋂d+1
i=1 Ci 6= ∅, then
let q be the lexicographically minimum of
⋂d+1
i=1 Ci (note that in particular q ∈ Cd+1). We will
prove that p = q.
C
C1
C2
C3
Figure 2.5: Illustration for the proof of Theorem 2.4 (in the plane).
Since
⋂d+1
i=1 Ci ⊂
⋂d
i=1 Ci, then p ≤lex q. In order to prove that q ≤lex p, we define the
convex set C = {x ∈ R
d : x <lex q} (see Figure 2.5). Then
F = {C1, . . . , Cd, Cd+1, C}
is a family of convex sets such that
⋂
F =
⋂d+1
i=1 Ci ∩ C = ∅. By Helly’s theorem (Theorem
1.4) and since
⋂d+1
i=1 Ci 6= ∅, we have that there is a subfamily G of {C1, . . . , Cd, Cd+1} of size
d such that
⋂
G ∩ C = ∅. Let r be the minimum lexicographically of
⋂
G, then q ≤lex r. By
the maximality of p, we have that r ≤lex p. Thus, q ≤lex r ≤lex p and p = q (note that then
G = {C1, C2, . . . , Cd}). Therefore, p ∈
⋂
Fd+1 and
⋂
Fd+1 6= ∅.
Note that Theorem 2.4 implies Theorem 1.4. Indeed, if F is a family of convex sets satisfying
the hypothesis of Theorem 1.4, then the families Fi = F for i = 1, . . . , d + 1 satisfy the
hypothesis of Theorem 2.4, thus
⋂
F 6= ∅.
2.3. Colorful Radon
The result of this section is known as the colorful Radon theorem and was proved by Lovász
(see [2]) using the Borsuk-Ulam theorem [3]. The ingenious proof presented here is by Soberón
[37] and is very elemental.
Theorem 2.5. (Colorful Radon) Let F1, . . . , Fd+1 be sets of 2 points each of Rd. Then the
union
⋃d+1
i=1 Fi can be partitioned into 2 sets A1, A2 such that |Ai ∩ Fj| = 1 for each i, j and
conv(A1) ∩ conv(A2) 6= ∅.
28 CHAPTER 2. COLORFUL THEOREMS
Figure 2.6: An example of the colorful Radon theorem in the plane.
Proof. Let Fi = {xi, yi} be a set of two points in R
d, for each 1 ≤ i ≤ d+1. Since {x1−y1, x2−
y2, . . . , xd+1 − yd+1} is a set of d + 1 points in R
d, then the d + 1 vectors xi − yi are linearly
dependent. Then there exists d + 1 real numbers α1, . . . , αd+1 ∈ R such that not all of them
are 0 and
d+1
∑
i=1
αi(xi − yi) = 0.
If there is αi < 0, we relabel the names of the points xi, yi and change the sign of αi, then we
can assume that all the αi are non negative. In addition, since each αi ≥ 0 and not all of them
are 0, we can use scalar multiplication and so we can also assume that
∑d+1
i=1 αi = 1. Then we
have the following convex combinations:
p =
d+1
∑
i=1
αixi =
d+1
∑
i=1
αiyi.
Therefore, A1 = {x1, . . . , xd+1} and A2 = {y1, . . . , yd+1} satisfy that we want with
p ∈ conv(A1) ∩ conv(A2).
The proof of Soberón is very similar to the proof of Radon’s theorem (Theorem 1.8), despite
that no one had thought of this clever proof.
Chapter 3
Very colorful theorems
Pach, Holmsen and Tverberg [21] (in 2008) and independently Arocha, Bárány, Bracho,
Fabila and Montejano [1] (in 2009) proved a generalization of the Colorful Carathéodory the-
orem (Theorem 2.3). In 2020, Mart́ınez-Sandoval, Roldán-Pensado and Rubin [28] proved a
generalization of the Colorful Helly theorem (Theorem 2.4).
In this chapter we prove these generalizations of the Colorful Carathéodory theorem and
the Colorful Helly theorem.
3.1. Colorful Carathéodory-type theorems
In Section 2.1 we proved Proposition 2.1, which is stronger than the 2-dimensional Color-
ful Carathéodory theorem (Theorem 2.3). The generalization of Proposition 2.1 to arbitrary
dimensions is also true. In other words, if A1, A2, . . . , Ad+1 are finite point sets in R
d such that
a ∈
⋂d+1
i=1 conv(Ai), then for each a1 ∈ A1, there is a rainbow set T = {a1, a2, . . . , ad+1} such
that a ∈ conv(T ). In particular, there are at least as many rainbow simplexes containing a as
the cardinality of A1. This result is stronger than the Colorful Carathéodory theorem (Theorem
2.3).
Proposition 3.1. Let A1, A2, . . . , Ad+1 be finite point sets in R
d and a ∈ R
d such that a ∈
⋂d+1
i=1 conv(Ai). Then, for each a1 ∈ A1, there exist a2 ∈ A2, a3 ∈ A3, . . . , ad+1 ∈ Ad+1 so that
a ∈ conv({a1, a2, . . . , ad+1}).
Notice that when |Ai| = d+ 1 for all i = 1, . . . , d+ 1, then there are at least d+ 1 rainbow
simplexes containing a. Moreover, Sarrabezolles [36] (in 2015) proved that, in this case, there
are at least d2 + 1 rainbow simplexes containing a.
In this section, we prove the following stronger result (Theorem 3.2) found by Arocha,
Bárány, Bracho, Fabila and Montejano [1] and independently by Holmsen, Pach and Tverberg
[21]. First, we see the proof of Theorem 3.2 by Arocha, Bárány, Bracho, Fabila and Montejano
[1]. Then, we prove that Theorem 3.2 implies Proposition 3.1.
Theorem 3.2. Let A1, A2, . . . , Ad+1 be finite point sets in R
d and a ∈ R
d such that a ∈
conv(Ai ∪ Aj) for all 1 ≤ i < j ≤ d+ 1. Then there exist a1 ∈ A1, a2 ∈ A2, . . . , ad+1 ∈ Ad+1 so
that
a ∈ conv({a1, a2, . . . , ad+1}).
29
30 CHAPTER 3. VERY COLORFUL THEOREMS
Proof. Let T = {a1, a2, . . . , ad+1} be a rainbow set (with ai ∈ Ai for every i = 1, . . . , d+1) such
that conv(T ) is closest to a among all the rainbow simplexes. If the distance of conv(T ) to a
is 0, then a ∈ conv(T ) and we are done. Otherwise, we assume that the distance of conv(T ) to
a is greater than 0 in order to get a contradiction.
Let p ∈ conv(T ) be the point of conv(T ) closest to a. Let H be the hyperplane containing
p and orthogonal to the segment [a, p], and denote by H+ the closed halfspace bounded by H
and containing a.
By the same arguments of the proof of Theorem 2.3 we have that conv(T ) ⊂ H− (where
H− is the closed halfspace bounded by H which does not contain a) and p is in the convex hull
of at most d points in T ∩H. Without loss of generality,
p ∈ conv({a1, . . . , ad}).
If there exists b ∈ Ad+1 ∩ (H+ \ H), then conv({a1, . . . , ad, b}) is a rainbow simplex closer to
a than conv(T ) (by the same argument of the last paragraph of the proof of Theorem 2.3),
contradicting the minimality of conv(T ). Hence Ad+1 ⊂ H−.
Since Ad+1 ⊂ H− and a ∈ conv(Ai∪Aj) for all 1 ≤ i < j ≤ d+1, then for each i = 1, . . . , d,
there is a point bi ∈ Ai such that bi ∈ H+ \H.
We claim that p is in the relative interior of conv({a1, . . . , ad}). We assume on the contrary
that p is in the convex hull of at most d − 1 points of {a1, . . . , ad}, without loss of generality
p ∈ conv({a1, . . . , ad−1}). Then conv({a1, . . . , ad−1, bd, ad+1}) is a rainbow simplex closer to
a than conv(T ) (by the same argument of the last paragraph of the proof of Theorem 2.3),
contradicting the minimality of conv(T ). Thus, p is in the relative interior of conv({a1, . . . , ad}).
Let L1 be the half-line starting at a and containing p. Let bd+1 be the point such that
ad+1, a, bd+1 are in the same line and ‖a − ad+1‖ = ‖a − bd+1‖. Since Ad+1 ⊂ H−, then
ad+1 ∈ H− and bd+1 ∈ H+. Let L2 be the half-line starting at a and containing bd+1. Let
L = L1 ∪ L2 (see Figure 3.1). The homotopy group Πd−2(R
d \ L) is non-zero and in fact, the
(d− 1)-dimensional simplex conv({a1, . . . , ad}) is an essential (d− 2)-cycle (because p is in the
relative interior of conv({a1, . . . , ad})).
a1
a2
a3
a
p
b1
H
H+
H−
b2
L1
L2
Figure 3.1: Illustration for the proof of Theorem 3.2 (in the plane). In this example
conv({b1, b2, a3}) is a rainbow simplex that contains a.
3.1. COLORFUL CARATHÉODORY-TYPE THEOREMS 31
Denote by E = {e1, . . . , ed} the standard orthonormal basis of Rd. The d-dimensional cross-
polytope is conv(E ∪ −E). Let Ωd−1 be the boundary of the d-dimensional cross-polytope.
Observe that a subset of d vertices of Ωd−1 spans a facet if and only if it does not contain
antipodal points. For any i ∈ {1, . . . , d}, we color ei and −ei of the same color of ai. Then
every facet of Ωd−1 is a (d− 1)-dimensional rainbow simplex. Let U be the interior of the facet
conv(E).
Let f : Ωd−1 \ U → R
d be the piecewise linear map defined as follows. For i = 1, . . . , d, we
set f(ei) = ai and f(−ei) = bi. Then we extend f linearly. Note that f preserves colors, hence
f sends rainbow simplexes in rainbow simplexes.
By definition, f(E) = {a1, . . . , ad} and conv({a1, . . . , ad}) is an essential (d − 2)-cycle of
Πd−2(R
d \L), then f(Ωd−1 \U) must intersect L. Let σ = {z1, . . . , zd} 6= E be a set of vertices
of Ωd−1 such that conv(σ) is a facet of Ωd−1 \ U and L ∩ conv(f(σ)) 6= ∅. Since every facet
of Ωd−1 is a (d − 1)-dimensional rainbow simplex and f preserves colors, then conv(f(σ)) is a
(d− 1)-dimensional rainbow simplex. Since L ∩ conv(f(σ)) 6= ∅, we have that either
L1 ∩ conv(f(σ)) 6= ∅ or L2 ∩ conv(f(σ)) 6= ∅.
If L1 ∩ conv(f(σ)) 6= ∅, then there exists a point q ∈ L1 ∩ conv(f(σ)) which is closer to a
than p. Hence the rainbow simplex conv(f(σ) ∪ ad+1) is closer to a than T , contradicting the
minimality of T .
If L2 ∩ conv(f(σ)) 6= ∅, then conv(f(σ) ∪ ad+1) is a rainbow simplex that contains a.
The following proposition is a reformulation of Proposition 3.1 and is a corollary of Theorem
3.2.
Proposition 3.3. Let A1, A2, . . . , Ad be finite point sets in R
d and a ∈ R
d such that a ∈
⋂d
i=1 conv(Ai). Then, for each x ∈ R
d \
⋃d
i=1 Ai, there exist a1 ∈ A1, a2 ∈ A2, . . . , ad ∈ Ad so
that
a ∈ conv({a1, a2, . . . , ad, x}).
Proof. Let x ∈ R
d \
⋃d
i=1 Ai and Ad+1 = {x}. The sets A1, A2, . . . , Ad, Ad+1 satisfy the hypoth-
esis of Theorem 3.2, then there exist a1 ∈ A1, a2 ∈ A2, . . . , ad ∈ Ad, x ∈ Ad+1 such that
a ∈ conv({a1, a2, . . . , ad, x}).
Let A1, A2, . . . , Ad+1 be finite point sets in R
d and a ∈ R
d. The Colorful Carathéodory
theorem (Theorem 2.3) states that if a ∈
⋂d+1
i=1 conv(Ai), then there is a rainbow simplex
containing a. Theorem 3.2 states that if a ∈ conv(Ai ∪ Aj) for all 1 ≤ i < j ≤ d + 1, then
there is a rainbow simplex containing a. A natural question is whether we only need that
a ∈ conv(Ai ∪ Aj ∪ Ak) for all 1 ≤ i < j < k ≤ d + 1, to conclude that there is a rainbow
simplex containing a. However, the answer to this question is no. The counterexample is given
in Example 3.4 (see Figure 3.2).
Example 3.4. For each 1 ≤ i ≤ d−1, let Ai = {ei,−ei}, where {e1, e2, . . . , ed} is the standard
basis of Rd. Let Ad = {ed} and Ad+1 = {2ed}. The sets A1, A2, . . . , Ad+1 satisfy that the origin
is in the convex hull of conv(Ai ∪ Aj ∪ Ak) for all 1 ≤ i < j < k ≤ d + 1. However, there is
32 CHAPTER 3. VERY COLORFUL THEOREMS
no rainbow simplex containing the origin. Indeed, if the origin 0 was a convex combination of
a rainbow simplex, then
0 = α1a1 + · · ·+ αd−1ad−1 + αded + αd+12ed,
where ai ∈ {ei,−ei}, for 1 ≤ i ≤ d − 1. Then α1 = α2 = · · · = αd−1 = 0 and αd + 2αd+1 = 0.
However, αd + αd+1 = 1 and αd+1 ≥ 0 (because it is a convex combination), this contradicts
that αd + 2αd+1 = 0. Therefore, there is no rainbow simplex containing the origin.
e1−e1
e2
2e2
0
Figure 3.2: The 2-dimensional case of Example 3.4.
Despite this, it is true that if we have d+2 finite point sets A1, A2, . . . , Ad+2 in R
d (instead
of d+ 1 finite point sets) such that a ∈ conv(Ai ∪ Aj ∪ Ak) for all 1 ≤ i < j < k ≤ d+ 2, then
there is a rainbow simplex containing a. In general, Soberón [38] (in 2018) and Holmsen [19]
(in 2016) found the following result, which can be proved following the same arguments of the
proof of Theorem 3.2 (as was noted in [38]).
Theorem 3.5. Let A1, A2, . . . , An be finite point sets in R
d, with n ≥ d + 1, and a ∈ R
d
such that a ∈ conv
(
⋃
i∈I Ai
)
for all I ⊂ {1, . . . , n} with |I| = n − d + 1. Then there exist
a1 ∈ A1, a2 ∈ A2, . . . , an ∈ An so that
a ∈ conv({a1, a2, . . . , an}).
Another natural question is if in Theorem 3.2 there are several rainbow simplexes containing
a. However, Example 3.6 shows that it is possible to have only 1 rainbow simplex containing a
(see Figure 3.3).
Example 3.6. For each 1 ≤ i ≤ d, let Ai = {ei,−ei}, and let Ad+1 = {(e1+e2+ · · ·+ed)}. The
sets A1, A2, . . . , Ad+1 satisfy the hypothesis of Theorem 3.2, where a is the origin. However,
there is only 1 rainbow simplex containing the origin. Indeed, if the origin 0 is a convex
combination of a rainbow simplex, then
0 = α1a1 + · · ·+ αdad + αd+1(e1 + e2 + · · ·+ ed),
where ai ∈ {ei,−ei}, for 1 ≤ i ≤ d. Then, for each 1 ≤ i ≤ d, αd+1 ∈ {αi,−αi}. Since
α1+ · · ·+αd+1 = 1 and αi ≥ 0 for every i ∈ {1, . . . , d+1}, then αi = αd+1 =
1
d+1
and ai = −ei
for every i ∈ {1, . . . , d}. Therefore,
conv({−e1,−e2, . . . ,−ed, e1 + e2 + · · ·+ ed})
is the only rainbow simplex containing the origin.
3.2. COLORFUL HELLY-TYPE THEOREMS 33
e1−e1
e2 e1 + e2
0
−e2
Figure 3.3: The 2-dimensional case of Example 3.6.
3.2. Colorful Helly-type theorems
Motivated by Theorem 3.2, we could think that, in the Colorful Helly theorem (Theorem
2.4), there is a second color that can be pierced by few points. Unfortunately, that is false as
we see in Example 3.7.
Example 3.7. For each 1 ≤ i ≤ d, let Fi be a set of hyperplanes orthogonal to the xi-axis, and
let Fd+1 = {Rd}. The families satisfy the hypothesis of the Colorful Helly theorem (Theorem
2.4) and the family Fd+1 is the family with non-empty intersection. Moreover, every family Fi,
for 1 ≤ i ≤ d, needs an arbitrary large number of points in order to be pierced (see Figure 3.4).
Figure 3.4: The 2-dimensional case of Example 3.7.
Despite that it is not true that a second color can be crossed by few points in the Colorful
Helly theorem, the purpose of this section is prove that we can say something concerning the
remaining colors.
Let F1, . . . ,Fd+1 be finite families of convex sets in R
d such that for every choice of sets
C1 ∈ F1, . . . , Cd+1 ∈ Fd+1, the intersection
⋂d+1
i=1 Ci is non-empty. By the Colorful Helly theorem
(Theorem 2.4), there is a family with non-empty intersection, without loss of generality the
family F1 has non-empty intersection.
We project the families F2,F3, . . . ,Fd+1 to a (d − 1)-dimensional hyperplane H and, for
each i ∈ {2, 3, . . . , d + 1}, let Gi be the family of all the projections of sets in the family Fi.
Note that the families G2,G3, . . . ,Gd+1 satisfy the hypothesis of the (d−1)-dimensional Colorful
Helly theorem in the hyperplane H, then all the sets in one of the families G2,G3, . . . ,Gd+1 have
34 CHAPTER 3. VERY COLORFUL THEOREMS
a common point, without loss of generality the sets in the family G2 have a common point g2.
The line whose the projection is the point g2 is a line transversal of the family F2.
If now we consider the remaining d−1 families, projecting to a (d−2)-dimensional hyperplane
and applying the Colorful Helly theorem in dimension d − 2, we obtain that there is another
family with a 2-flat transversal. We can follow the same argument d times to say something
concerning all the families. We have proved the following proposition.
Proposition 3.8. Let F1, . . . ,Fd+1 be finite families of convex sets in R
d such that for every
choice of sets C1 ∈ F1, . . . , Cd+1 ∈ Fd+1, the intersection
⋂d+1
i=1 Ci is non-empty. Then there
exists a permutation π ∈ Sd+1 such that for each i ∈ {1, . . . , d + 1} the family Fπ(i) has a
(i− 1)-flat transversal.
We have the following reformulation of Proposition 3.8 using only d colors.
Proposition 3.9. Let F1, . . . ,Fd be finite families of convex sets in R
d such that for every
choice of sets C1 ∈ F1, . . . , Cd ∈ Fd, the intersection
⋂d
i=1 Ci is non-empty. Then there exists a
permutation π ∈ Sd such that for each i ∈ {1, . . . , d} the family Fπ(i) has a i-flat transversal.
Note that Proposition 3.9 is a colorful version of Proposition 1.9.
Motivated by Proposition 3.8, a natural question is what additional consequences we can
obtain with the same hypothesis of the Colorful Helly theorem (Theorem 2.4). Let F1, . . . ,Fd
be finite families of convex sets in R
d satisfying the hypothesis of the Colorful Helly theorem. By
Theorem 2.4 we know that there is a family with non-empty intersection. Mart́ınez-Sandoval,
Roldán-Pensado and Rubin [28] proved that either there is an additional family whose sets can
be pierced by few points or all the sets in the union of the d+ 1 families can be crossed by few
lines.
Theorem 3.10. For each dimension d ≥ 2 there exist numbers f(d) and g(d) (depending only
on the dimension) with the following property. Let F1, . . . ,Fd+1 be finite families of convex sets
in R
d such that for every choice of sets C1 ∈ F1, . . . , Cd+1 ∈ Fd+1, the intersection
⋂d+1
i=1 Ci
is non-empty. Let i ∈ {1, . . . , d + 1} such that
⋂
Fi 6= ∅ (by Theorem 2.4). Then one of the
following statements must also hold:
1. an additional family Fj, for j ∈ {1, . . . , d+ 1} \ {i}, can be pierced by f(d) points, or
2. the family
⋃d+1
i=1 Fi can be crossed by g(d) lines.
We have the following reformulation of Theorem 3.10 using only d colors.
Theorem 3.11. For each dimension d ≥ 2 there exist numbers f(d) and g(d) (depending only
on the dimension) with the following property. Let F1, . . . ,Fd be finite families of convex sets
in R
d such that for every choice of sets C1 ∈ F1, . . . , Cd ∈ Fd, the intersection
⋂d
i=1 Ci is
non-empty. Then one of the following statements holds:
1. there is a family Fj, for j ∈ {1, . . . , d}, that can be pierced by f(d) points, or
2. the family
⋃d
i=1 Fi can be crossed by g(d) lines.
Note that Theorem 3.11 is a strong colorful version of Proposition 1.9. Since the proof of
Theorem 3.11 is very involved, we only see the main ideas of its proof. In particular, we prove
the 2-dimensional case of Theorem 3.11. We begin with the following lemma that was proved
in [28] in order to prove Theorem 3.11.
3.2. COLORFUL HELLY-TYPE THEOREMS 35
Lemma 3.12. Let A and B be finite families of convex sets in R
d such that A ∩ B 6= ∅ for
every A ∈ A and B ∈ B. Then either
(1)
⋂
A 6= ∅, or
(2) B can be crossed by d hyperplanes.
Proof. If
⋂
A 6= ∅, we are done. Otherwise, we assume that
⋂
A = ∅. Then by Helly’s
theorem (Theorem 1.4) there are n convex sets A1, . . . , An ∈ A, with 2 ≤ n ≤ d + 1, such
that
⋂n
i=1 Ai = ∅. By Theorem 1.7, there exist n hyperplanes H1, . . . , Hn such that the closed
half-spaces H+
1 , . . . , H
+
n satisfy Ai ⊂ H+
i for all i and
⋂n
i=1 H
+
i = ∅. We claim that the family
B can be crossed by the n− 1 hyperplanes H1, H2, . . . , Hn−1, where n− 1 ≤ d (see Figure 3.5).
A1
A2
A3
B
H1H2
H3
Figure 3.5: Illustration for the proof of Lemma 3.12.
By contradiction, suppose that a set B ∈ B does not intersect any of the hyperplanes Hi,
for i = 1, 2, . . . , n − 1. Then B must be contained in an open region bounded by the n − 1
hyperplanes H1, H2, . . . , Hn−1, in other words, B ⊂
⋂n−1
i=1 H∗
i where ∗ ∈ {+,−}. By hypothesis,
Ai ∩B 6= ∅ for each 1 ≤ i ≤ n− 1, then B ⊂
⋂n−1
i=1 H+
i . Since
⋂n
i=1 H
+
i = ∅ and B ⊂
⋂n−1
i=1 H+
i ,
then B ∩H+
n = ∅. Hence B ∩ An = ∅, contradicting the hypothesis.
Applying Lemma 3.12 twice in dimension d = 2, we have that either one of the two families
has non-empty intersection or every one of the families can be crossed by 2 lines. Then as
a corollary of Lemma 3.12, Mart́ınez-Sandoval, Roldán-Pensado and Rubin also proved that
the 2-dimensional case of Theorem 3.11 holds with f(2) = 1 and g(2) = 4. In Section 4.2
we improve the last result; we prove that the 2-dimensional case of Theorem 3.11 holds with
f(2) = 1 and g(2) = 2.
On the other hand, the following lemma [28] is a generalization of Lemma 3.12 and is the
main result needed to prove Theorem 3.11.
Lemma 3.13. For any 1 ≤ k ≤ d and m ≥ 1 there exist numbers F (m, k, d) and G(m, k, d)
with the following property. Let A and B be finite families of convex sets in R
d so that the
family
I(A,B) = {A ∩B : A ∈ A, B ∈ B}
can be crossed by m k-flats. Then one of the following conditions is satisfied:
36 CHAPTER 3. VERY COLORFUL THEOREMS
1. A can be pierced by F (m, k, d) points, or
2. B can be crossed by G(m, k, d) (k − 1)-flats.
The proof of Lemma 3.13 is very sophisticated and can be consulted in [28]. Note that in
Lemma 3.13 the hypothesis that I(A,B) can be crossed by m k-flats implies that every two
sets A ∈ A, B ∈ B intersect, then the family I(A,B) can be crossed by R
d. Thus, by Lemma
3.12, the particular case of Lemma 3.13 in which k = d and m = 1 holds with F (1, d, d) = 1
and G(1, d, d) ≤ d.
We are now ready to prove Theorem 3.11. Before we see the rigorous proof, we will see the
idea of the proof. The idea is to apply Lemma 3.13 d− 1 times. For each 1 ≤ i ≤ d we define
I(Fi, . . . ,Fd) =
{
d
⋂
j=i
Aj : Aj ∈ Fj
}
.
First, we apply Lemma 3.13 (or Lemma 3.12) to the families A = F1 and B = I(F2, . . . ,Fd).
If A = F1 can be pierced by 1 point, we are done. Otherwise, the family B = I(F2, . . . ,Fd)
can be crossed by d hyperplanes. Then, in the case where the family B = I(F2, . . . ,Fd) can be
crossed by d hyperplanes, we apply Lemma 3.13 to the families A = F2 and B = I(F3, . . . ,Fd).
Thus, A = F2 can be pierced by F (d, d − 1, d) points or B = I(F3, . . . ,Fd) can be crossed
by G(d, d − 1, d) (d − 2)-flats. In the first case we are done, in the second case we continue
applying Lemma 3.13 using the families I(Fi, . . . ,Fd). Following the same argument several
times we have that either there is a family that can be pierced by few points or the last family
(Fd) can be crossed by few lines. Since the labeling of the families was arbitrary, we can choose
d different labelings such that every family is the last family in one of the labelings. Therefore,
there is a family that can be pierced by few points or all the families can be crossed by few
lines.
Proof of Theorem 3.11. Let F1, . . . ,Fd be finite families of convex sets in R
d satisfying the
hypothesis of Theorem 3.11. We set
M(i, d) =



1 for i = 1,
d for i = 2,
G(M(i− 1, d), d− i+ 2, d) for 3 ≤ i ≤ d− 1.
Since for every choice of sets C1 ∈ F1, . . . , Cd ∈ Fd the intersection
⋂d
i=1 Ci is non-empty, the
families A = F1 and B = I(F2, . . . ,Fd) satisfy the hypothesis of Lemma 3.13. Then, A = F1
can be pierced by 1 point or B = I(F2, . . . ,Fd) can be crossed by M(2, d) = d hyperplanes. In
the first case we are done. Otherwise, we assume that none of the families Fi, for 1 ≤ i ≤ d−1,
can be pierced by F (M(i, d), d − i + 1, d) points, then applying d − 1 times Lemma 3.13, the
last family Fd can be crossed by G(M(d− 1, d), 2, d) lines.
Applying the last argument to d different labelings such that every family is the last family
in one of the labelings, we prove Theorem 3.11 with
f(d) = max{F (M(i, d), d− i+ 1, d) : 1 ≤ i ≤ d− 1}, and
g(d) = d ·G(M(d− 1, d), 2, d).
3.2. COLORFUL HELLY-TYPE THEOREMS 37
Finally, Mart́ınez-Sandoval, Roldán-Pensado and Rubin [28] also proved that if f(d), g(d)
are numbers satisfying Theorem 3.11, then g(d) ≥
⌈
d+1
2
⌉
. In Section 4.2, we see the construction
of Mart́ınez-Sandoval, Roldán-Pensado and Rubin in the plane that shows that if f(2), g(2) are
numbers satisfying the 2-dimensional case of Theorem 3.11, then g(2) ≥
⌈
2+1
2
⌉
= 2.
38 CHAPTER 3. VERY COLORFUL THEOREMS
Chapter 4
Colorful theorems for line transversals
In this chapter we prove colorful theorems in low dimensions. Most of the results in this
chapter are our own, although there are also other people’s results in this chapter. Some of our
main tools are the KKM theorem and the Colorful KKM theorem. For that reason, in Section
4.1 we see the KKM theorem and the colorful KKM theorem. In Section 4.2 we improve the 2-
dimensional case of Theorem 3.11; in fact, we give the best numbers satisfying the 2-dimensional
case of Theorem 3.11. In Section 4.3 we see an open problem proposed in [28], some ideas that
have been used to prove particular cases and we give an idea in order to prove the general case
of the open problem. In Section 4.4 we prove colorful versions of Theorems 1.14 and 1.15, we
also present new problems and conjectures.
4.1. KKM theorem
There are a lot of problems in discrete mathematics that have been solved using tools from
topology. For instance, the Borsuk-Ulam theorem [3] and the KKM theorem [25] are some of
the results from topology most used to solve problems from discrete mathematics. The reader
interested in the history of applications of topology in discrete mathematics can consult [30].
In this section we state the KKM theorem and some of its equivalent theorems.
In 1929, Knaster, Kuratowski and Mazurkiewicz [25] proved the called KKM theorem. Let
∆n =
{
(x1, . . . , xn+1) ∈ R
n+1 : xi ≥ 0,
n+1
∑
i=1
xi = 1
}
denote the n-dimensional simplex in R
n+1 that is the convex hull of {e1, . . . , en+1}, the standard
orthonormal basis of Rn+1.
Theorem 4.1. (KKM theorem). Let {O1, O2, . . . , On+1} be an open cover (or closed cover) of
∆n such that:
a) ei ∈ Oi for each i ∈ {1, 2, . . . , n+ 1}, and
b) conv{ei : i ∈ I} ⊂
⋃
i∈I Oi for each I ⊂ {1, 2, . . . , n+ 1}.
Then
⋂n+1
i=1 Oi 6= ∅.
39
40 CHAPTER 4. COLORFUL THEOREMS FOR LINE TRANSVERSALS
The KKM theorem is equivalent to Sperner’s lemma [40] and Brouwer’s fixed point theo-
rem [7]. In fact, Knaster, Kuratowski and Mazurkiewicz [25] proved the KKM theorem using
Sperner’s lemma (a combinatorial lemma). In 1994, Krasa and Yannelis [27] gave another
elementary proof of the KKM theorem using Brouwer’s fixed point theorem.
Theorem 4.2. (Sperner’s lemma). Let ∆ be a n-dimensional simplex with vertices v1, v1, . . . , vn+1.
Let T be a triangulation of ∆ and let
f : V (T ) −→ {1, 2, . . . , n+ 1}
be a coloration such that:
a) f(vi) = i for each 1 ≤ i ≤ n+ 1, and
b) if x ∈ conv({vi : i ∈ I}), then f(x) ∈ I, for each I ⊂ {1, 2, . . . , n+ 1}.
Then there are an odd number of rainbow simplexes of the triangulation T of dimension n. In
particular, there is at least one rainbow simplex in the triangulation.
Theorem 4.3. (Brouwer’s fixed point theorem). Every continuous function f : Bd → Bd,
where Bd = {x ∈ R
d : ‖x‖ ≤ 1} is a closed ball, has a fixed point; that is, there exists x ∈ Bd
such that f(x) = x.
In 1984, Gale [14] proved a colorful version of the KKM theorem (Theorem 4.1).
Theorem 4.4. (Colorful KKM theorem). For i, j = 1, . . . , n+ 1 let Oj
i be open sets (or closed
sets) such that for every j, {Oj
1, O
j
2, . . . , O
j
n+1} is an open cover (or closed cover) of ∆n such
that:
a) ei ∈ Oj
i for each i ∈ {1, 2, . . . , n+ 1}, and
b) conv{ei : i ∈ I} ⊂
⋃
i∈I O
j
i for each I ⊂ {1, 2, . . . , n+ 1}.
Then there exists a permutation π ∈ Sn+1 such that
⋂n+1
i=1 O
π(i)
i 6= ∅.
Note that Theorem 4.4 implies Theorem 4.1. Indeed, if O = {O1, O2, . . . , On+1} is an open
cover satisfying the hypothesis of Theorem 4.1, then the open covers Oj = O for j = 1, . . . , n+1
satisfy the hypothesis of Theorem 4.4 and thus
⋂n+1
i=1 Oi 6= ∅.
Recently, Soberón [39] proved the following generalization of Theorem 4.4.
Theorem 4.5. Let k ≤ n be positive integers. For i = 1, . . . , k and j = 1, . . . , n, let Oj
i be open
sets (or closed sets) such that for every I ∈
(
[n]
n−k+1
)
, the family
{
⋃
j∈I
Oj
1, . . . ,
⋃
j∈I
Oj
k
}
is an open cover (or closed cover) of ∆k−1 that satisfies the hypothesis of Theorem 4.1. Then
there exists an injective function π : [k] −→ [n] such that
⋂k
i=1 O
π(i)
i 6= ∅.
Notice that we recover Theorem 4.4 from Theorem 4.5 when k = n.
4.2. A COLORFUL HELLY-TYPE THEOREM IN R
2 41
4.2. A colorful Helly-type theorem in R
2
In Section 3.2 we saw that Mart́ınez-Sandoval, Roldán-Pensado and Rubin [28] proved that
the 2-dimensional case of Theorem 3.11 holds with f(2) = 1 and g(2) = 4. In this section, using
the KKM theorem (Theorem 4.1), we improve this result. We prove that the 2-dimensional
case of Theorem 3.11 holds with f(2) = 1 and g(2) = 2.
We begin with the following particular case of our result which has a very elementary proof.
Theorem 4.6. Let A,B be finite families of rectangles with sides parallel to the coordinate
axes in R
2. Suppose that A ∩ B 6= ∅ for every A ∈ A and B ∈ B. Then one of the following
statements holds:
1. one of the families A or B can be pierced by 1 point, or
2. the family A∪ B can be crossed by 2 lines (the lines can actually be chosen to be orthog-
onal).
Proof. We project all the rectangles in the family A ∪ B to the x axis, then we obtain two
finite families of intervals satisfying the hypothesis of the 1-dimensional Colorful Helly theorem
(Theorem 2.4). Thus one of the families, A or B, has a line transversal orthogonal to the x
axis. Without loss of generality, the family A has a line transversal l1 orthogonal to the x axis.
Now we project all the rectangles in the family A ∪ B to the y axis and, by the same
argument, one of the families, A or B, has a line transversal l2 orthogonal to the y axis. Note
that l1 is orthogonal to l2. Let p be the point intersection of the lines l1 and l2 (see Figure 4.1).
x
y l1
l2p
Figure 4.1: Illustration for the proof of Theorem 4.6.
First we suppose that l2 is transversal to A. Then l1 and l2 are line transversals to the
family A. Since A is a family of rectangles with parallel sides to the axes and l1, l2 are parallel
to the axes, then every rectangle in the family A contains the point p.
Now we suppose that l2 is transversal to B. Then l1 is transversal to the family A and l2
is transversal to the family B. Therefore, the family A ∪ B can be crossed by two orthogonal
lines (l1 and l2).
Note that we proved Theorem 4.6 using only tools from combinatorial geometry. To prove
the general case we also need tools from topology. We prove that the 2-dimensional case of
Theorem 3.11 holds with f(2) = 1 and g(2) = 2. In other words, we prove that if A,B are
42 CHAPTER 4. COLORFUL THEOREMS FOR LINE TRANSVERSALS
finite families of convex sets in R
2 such that A∩B 6= ∅ for every A ∈ A and B ∈ B, then either
one of the families A or B can be pierced by 1 point or the family A ∪ B can be crossed by 2
lines.
The geometrical idea to prove our result is the following. If there are two lines crossing
the family A ∪ B, we are done. Otherwise, for any two lines in the plane with non-empty
intersection there is a set in the family A ∪ B contained in the interior of one of the 4 regions
bounded by the two lines. Then, by using the KKM theorem (Theorem 4.1) and following ideas
similar to the ones used in [31], we prove that, in this case, there are two lines l1, l2 with point
intersection p and four sets C1, C2, C3, C4 in the same family (either A or B) so that every set
Ci is contained in the interior of one of the 4 regions bounded by the lines l1, l2, each set Ci in
a different region (see Figure 4.2). Using the convexity, we prove that the point p is contained
in every set in the other family.
l1l2
p
Figure 4.2: If there are no two lines crossing the family A ∪ B, then there are two lines l1, l2
with point intersection p such that p ∈
⋂
A or p ∈
⋂
B.
Theorem 4.7. Let A,B be finite families of convex sets in R
2 such that A ∩ B 6= ∅ for every
A ∈ A and B ∈ B. Then one of the following statements holds:
1. one of the families A or B can be pierced by 1 point, or
2. the family A ∪ B can be crossed by 2 lines.
Proof. We can assume, without loss of generality, that the sets in both finite families are
compact (see Section 1.2). Hence, we may scale the plane such that every set in A ∪ B is
contained in the unit disk. Let f(t) be a parametrization of the unit circle defined by
f(t) = (cos(2πt), sin(2πt)).
To each point x = (x1, . . . , x4) ∈ ∆3 we associate 4 points on the unit circle given by
fi(x) = f
(
i
∑
j=1
xj
)
,
4.2. A COLORFUL HELLY-TYPE THEOREM IN R
2 43
for 1 ≤ i ≤ 4. Let l1(x) = l3(x) = [f1(x), f3(x)] and l2(x) = l4(x) = [f2(x), f4(x)]. For
i = 1, . . . , 4 let Ri
x be the interior of the region bounded by li−1(x), li(x) and the arc on the
unit circle connecting fi−1(x) and fi(x), where i− 1 is taken modulo 4 (see Figure 4.3).
f1(x)
f2(x)
f3(x)
f4(x) = (1, 0)
R1
x
R2
x
R3
x
R4
x
Figure 4.3: Illustration for the proof of Theorem 4.7.
Notice that f4(x) = (1, 0) for each x ∈ ∆3. Also, the points x1, x2, x3, x4 are always in
counter-clockwise order.
For i = 1, . . . , 4, let Oi be the set of points x ∈ ∆3 such that Ri
x contains a set C ∈ A ∪ B.
Since the sets C ∈ A∪B are compact, Oi is open. If there is some x ∈ ∆3 for which x /∈
⋃4
i=1 Oi,
then since the sets in A ∪ B are convex, every set in A ∪ B must intersect
⋃2
i=1 li(x), and we
are done. Otherwise, we assume that ∆3 =
⋃4
i=1 Oi. Observe that if x ∈ conv{ei : i ∈ I} for
some I ⊂ {1, . . . , 4}, then Rj
x = ∅ for j /∈ I, and therefore x ∈
⋃
i∈I Oi.
The last paragraph shows that the second statement of the theorem holds or {O1, . . . , O4}
is an open cover that satisfies the hypothesis of the KKM theorem (Theorem 4.1). Then there
is a point y = (y1, . . . , y4) ∈ ∆3 such that y ∈
⋂4
i=1 Oi. In other words, each one of the open
regions Ri
y contains a set Ci ∈ A ∪ B (in particular Ri
y 6= ∅ and yi 6= 0 for all i ∈ {1, . . . , 4}).
Since A ∩ B 6= ∅ for every A ∈ A and B ∈ B (by hypothesis), then the sets C1, . . . , C4 are
in the same family (either A or B). Without loss of generality, we assume C1, . . . , C4 are in the
family A. Let p be the point intersection of the lines l1(y) = l3(y) and l2(y) = l4(y). Take any
set B ∈ B. Since B ∩ Ci 6= ∅ for every i ∈ {1, . . . , 4} and B is convex, then B intersects the
line segments [p, f4(y)] and [p, f2(y)]. Therefore, p ∈ B and the first statement of the theorem
holds.
In fact, using the same proof we have proved the following stronger result.
Theorem 4.8. Let F1, . . . ,Fn be finite families of convex sets in R
2 with n ≥ 2. Suppose that
A ∩ B 6= ∅ for every A ∈ Fi and B ∈ Fj with i 6= j. Then one of the following statements
holds:
1. there exists j ∈ {1, 2, . . . , n} such that
⋃
i 6=j Fi can be pierced by 1 point, or
2. the family
⋃n
i=1 Fi can be crossed by 2 lines.
Proof. If the family
⋃n
i=1 Fi can be crossed by 2 lines, we are done. Otherwise, following
the same ideas of the proof of Theorem 4.7 and using the same notation, we have that there
is a point y = (y1, . . . , y4) ∈ ∆3 such that each one of the open regions Ri
y contains a set
Ci ∈
⋃n
i=1 Fi.
44 CHAPTER 4. COLORFUL THEOREMS FOR LINE TRANSVERSALS
Since A ∩ B 6= ∅ for every A ∈ Fi and B ∈ Fj with i 6= j, then the sets C1, . . . , C4 are in
the same family. Without loss of generality, we assume C1, . . . , C4 are in the family F1. Let p
be the point intersection of the lines l1(y) = l3(y) and l2(y) = l4(y). Take any set B ∈
⋃
i 6=1 Fi.
Since B ∩ Ci 6= ∅ for every i ∈ {1, . . . , 4} and B is convex, then B intersects the line segments
[p, f4(y)] and [p, f2(y)]. Therefore, p ∈ B and the family
⋃
i 6=1 Fi can be pierced by 1 point.
We already proved that the 2-dimensional case of Theorem 3.11 holds with f(2) = 1 and
g(2) = 2. Now a natural question is if there exists n ∈ Z
+ such that the 2-dimensional case
of Theorem 3.11 holds with f(2) = n and g(2) = 1, however this is false. In Section 3.2
we saw that Mart́ınez-Sandoval, Roldán-Pensado and Rubin [28] proved that if f(d), g(d) are
numbers satisfying Theorem 3.11, then g(d) ≥
⌈
d+1
2
⌉
. In Example 4.9 we see the construction
of Mart́ınez-Sandoval, Roldán-Pensado and Rubin in the plane that prove that if f(2), g(2) are
numbers satisfying the 2-dimensional case of Theorem 3.11, then g(2) ≥
⌈
2+1
2
⌉
= 2.
Example 4.9. Let n ∈ Z
+. We want to construct two families, A,B satisfying the hypothesis
of the 2-dimensional case of Theorem 3.11 while neither A or B can be pierced by n points nor
A ∪ B can be crossed by 1 line.
Let A be a triangle in the plane with one edge parallel to the x-axis. Let A = {A1, . . . , A2n+1}
be a family of triangles in the plane such that any triangle Ai has an edge parallel to the x-axis,
the three vertices of Ai are in the relative interior of the edges of A (two vertices of Ai are in
different edges of A), and any three different triangles Ai, Aj, Ak have empty intersection. We
can construct the family A recursively, as follows. We start with two arbitrary triangles A1
and A2 satisfying the conditions of the family A, and at each step i > 2 we place the horizontal
edge of Ai sufficiently close to the horizontal edge of A so that Ai does not intersect all previous
pairwise intersections (see Figure 4.4). By construction, we need at least n+1 points to pierce
the family A.
Let E1, E2, E3 be the edges of A. Since every triangle Ai intersects the edges of A, we can
take three segments F1, F2, F3, every segment Fi contained in the relative interior of Ei, such
that every segment Fi intersects every triangle in the family A. For each segment Fi, we take
n translates of Fi pairwise disjoint so that they still intersect every triangle in the family A.
Let B be the set of the 3n defined segments (see Figure 4.4). By construction, we need at least
3n > n+ 1 points to pierce the family B.
In order to cross A ∪ B, in particular we have to cross the interiors of the three edges
E1, E2, E3, hence we need at least 2 lines to cross the family A ∪ B.
Theorem 4.7 and Example 4.9 show that the best numbers f(2), g(2) satisfying the 2-
dimensional case of Theorem 3.11 are f(2) = 1 and g(2) = 2.
Despite that the 2-dimensional case of Theorem 3.11 does not hold with g(2) = 1, we prove
that in the case where the families are translates of a compact convex set in the plane, Theorem
3.11 holds with f(2) = 3 and g(2) = 1. This result is joint work with Edgardo Roldán-Pensado.
Theorem 4.10. Let K be a compact convex set in R
2. Let F1, . . . ,Fn be finite families of
translates of K, with n ≥ 2. Suppose that A ∩ B 6= ∅ for every A ∈ Fi and B ∈ Fj with i 6= j.
Then one of the following statements holds:
1. there exists j ∈ {1, 2, . . . , n} such that
⋃
i 6=j Fi can be pierced by 3 points, or
2. the family
⋃n
i=1 Fi can be crossed by 1 line.
4.2. A COLORFUL HELLY-TYPE THEOREM IN R
2 45
Figure 4.4: Illustration for Example 4.9 in the case where n = 2. The family A is the set of
blue triangles and the family B is the set of red segments.
Proof. For every direction u ∈ S
1, let lu be the line through u and the origin. For every u ∈ S
1,
we project all the sets in the family
⋃n
i=1 Fi to the line lu, then we obtain a finite family of
intervals in the line lu.
If there exists u ∈ S
1 such that every two intervals in the line lu have non-empty intersection,
then by the 1-dimensional Helly theorem (Theorem 1.4), the intervals in the line lu have a
common point p. Thus, if ku is the line whose the projection (to the line lu) is the point p,
then ku is a line transversal to the family
⋃n
i=1 Fi, and we are done (see Figure 4.5).
u
S1
lup
ku
Figure 4.5: If the intervals in the line lu have a common point p, then ku is a line transversal
to the family
⋃n
i=1 Fi.
Otherwise, for every u ∈ S
1, there are two disjoint intervals in the line lu. Hence, for
every u ∈ S
1, there are two sets Au, Bu in the family
⋃n
i=1 Fi that are separated by a line mu
orthogonal to lu (see Figure 4.6). Since Au ∩ Bu = ∅, then Au and Bu must be in the same
family Fi, for some i ∈ {1, . . . , n}.
We color the sphere S1 as follows. We color u ∈ S
1 of color i if there are two sets Au, Bu ∈ Fi
that are separated by a line mu orthogonal to lu. Let Oi be the set of u ∈ S
1 such that u has
46 CHAPTER 4. COLORFUL THEOREMS FOR LINE TRANSVERSALS
u
S1
lu
mu
Au Bu
Figure 4.6: If there are two disjoint intervals in the line lu, then there are two sets Au, Bu in
the family
⋃n
i=1 Fi that are separated by a line mu orthogonal to lu.
color i. Since K is a compact set, then the sets Oi are open. Notice that we already proved
that S1 =
⋃n
i=1 Oi. We have two cases.
First we suppose that at least two sets from O1, . . . , On are non-empty. Since the sets
O1, . . . , On are open and S
1 =
⋃n
i=1 Oi, then there exist i, j ∈ {1, . . . , n} with i 6= j and
u ∈ Oi ∩Oj 6= ∅. Hence there exist two lines mu, nu orthogonal to lu and sets Au, Bu ∈ Fi and
Cu, Du ∈ Fj such that Au ⊂ m+
u \mu, Bu ⊂ m−
u \mu, Cu ⊂ n+
u \nu and Du ⊂ n−
u \nu (see Figure
4.7). Notice that we can assume without loss of generality that (m+
u \ mu) ∩ (n−
u \ nu) = ∅.
Then Au ∈ Fi and Du ∈ Fj satisfy that Au ∩Du = ∅, contradicting the hypothesis.
lu
mu
Au Bu
nu
Cu Du
Figure 4.7: In this example, Au ∩Du = ∅.
Then there exists j ∈ {1, . . . , n} such that S1 = Oj. Hence for every u ∈ S
1 there exists a
line mu orthogonal to lu and sets Au, Bu ∈ Fj such that Au ⊂ m+
u \ mu and Bu ⊂ m−
u \ mu.
We claim that, for every u ∈ S
1, the line mu is transversal to
⋃
i 6=j Fi. Indeed, if u ∈ S
1 and
C ∈
⋃
i 6=j Fi, by hypothesis we have that Au∩C 6= ∅ and Bu∩C 6= ∅. Since Au ⊂ m+
u \mu and
Bu ⊂ m−
u \mu, then C must intersect the line mu (see Figure 4.8). Thus, the family
⋃
i 6=j Fi
has a line transversal in every direction.
Now we claim that every two sets in
⋃
i 6=j Fi intersect. If there are two sets C,D ∈
⋃
i 6=j Fi
such that C ∩D = ∅, then C and D can be separated by a line l. Hence C and D do not have
line transversal in the same direction of l, a contradiction (see Figure 4.9).
Therefore, every two sets in
⋃
i 6=j Fi intersect and by Theorem 1.12, the family
⋃
i 6=j Fi can
be pierced by 3 points.
4.2. A COLORFUL HELLY-TYPE THEOREM IN R
2 47
lu
mu
Au BuC
Figure 4.8: For every u ∈ S
1 and C ∈
⋃
i 6=j Fi, the line mu intersects C.
l
C D
Figure 4.9: If the convex sets C,D ∈
⋃
i 6=j Fi can be separated by a line l, then
⋃
i 6=j Fi does
not have line transversal in the same direction of l.
Notice that we used that the families are translates of K in the last part of the proof.
Actually, we used that every two sets in
⋃
i 6=j Fi intersect. Grunbaum [16], Danzer [10] and
Karasev [23] [24] have studied families (in the plane) such that every two sets in the family
have non-empty intersection, and for some families of this type they proved that the whole
family can be pierced by few points. For example, Theorems 1.10, 1.11, 1.12 and 1.13 show
some families of this type. Then we observe that with the same proof of Theorem 4.10 we have
similar results for families of this type.
Theorem 4.11. Let F1, . . . ,Fn be finite families of compact convex sets in R
2, with n ≥ 2
and the following property: if there exists j ∈ {1, 2, . . . , n} such that every two sets in
⋃
i 6=j Fi
intersect, then
⋃
i 6=j Fi can be pierced by c points. Suppose that A ∩ B 6= ∅ for every A ∈ Fi
and B ∈ Fj with i 6= j. Then one of the following statements holds:
1. there exists j ∈ {1, 2, . . . , n} such that
⋃
i 6=j Fi can be pierced by c points, or
2. the family
⋃n
i=1 Fi can be crossed by 1 line.
Proof. If the family
⋃n
i=1 Fi can be crossed by 1 line, we are done. Otherwise, as in the proof
of Theorem 4.10, we have that there exists j ∈ {1, . . . , n} such that every two sets in
⋃
i 6=j Fi
intersect. Therefore, by hypothesis, the family
⋃
i 6=j Fi can be pierced by c points.
In particular, by Theorems 1.10, 1.11 and 1.13, we have the following corollaries.
48 CHAPTER 4. COLORFUL THEOREMS FOR LINE TRANSVERSALS
Theorem 4.12. Let K be a compact convex set in R
2. Let F1, . . . ,Fn be finite families of
homothets of K, with n ≥ 2. Suppose that A∩B 6= ∅ for every A ∈ Fi and B ∈ Fj with i 6= j.
Then one of the following statements holds:
1. there exists j ∈ {1, 2, . . . , n} such that
⋃
i 6=j Fi can be pierced by c points (where c is the
number that there exists in Theorem 1.10), or
2. the family
⋃n
i=1 Fi can be crossed by 1 line.
Theorem 4.13. Let F1, . . . ,Fn be finite families of circles in R
2, with n ≥ 2. Suppose that
A ∩ B 6= ∅ for every A ∈ Fi and B ∈ Fj with i 6= j. Then one of the following statements
holds:
1. there exists j ∈ {1, 2, . . . , n} such that
⋃
i 6=j Fi can be pierced by 4 points, or
2. the family
⋃n
i=1 Fi can be crossed by 1 line.
Theorem 4.14. Let F1, . . . ,Fn be finite families of rectangles with sides parallel to the coordi-
nate axes in R
2, with n ≥ 2. Suppose that A ∩B 6= ∅ for every A ∈ Fi and B ∈ Fj with i 6= j.
Then one of the following statements holds:
1. there exists j ∈ {1, 2, . . . , n} such that
⋃
i 6=j Fi can be pierced by 1 point, or
2. the family
⋃n
i=1 Fi can be crossed by 1 line.
In summary, Theorems 4.10, 4.11, 4.12, 4.13 and 4.14 show some special families where the
2-dimensional case of Theorem 3.11 holds with g(2) = 1. In particular, Theorem 4.14 shows
that for rectangles with sides parallel to the coordinate axes in R
2, the 2-dimensional case of
Theorem 3.11 holds with f(2) = 1 and g(2) = 1, hence Theorem 4.14 improves the result of
Theorem 4.6.
On the other hand, we wonder if we can improve the numbers in Theorem 4.10. We propose
the following problem.
Problem 4.15. Let K be a compact convex set in R
2. Let F1, . . . ,Fn be finite families of
translates of K, with n ≥ 2. Suppose that A ∩ B 6= ∅ for every A ∈ Fi and B ∈ Fj with i 6= j.
Is it true that one of the following statements holds?
1. there exists j ∈ {1, 2, . . . , n} such that
⋃
i 6=j Fi can be pierced by 1 point, or
2. the family
⋃n
i=1 Fi can be crossed by 1 line.
Jerónimo-Castro, Magazinov and Soberón [22] proved that in the case where the families
are circles of the same radius there is a stronger conclusion.
Theorem 4.16. Let F1, . . . ,Fn be finite families of circles of the same radius in R
2, with
n ≥ 2. Suppose that A ∩ B 6= ∅ for every A ∈ Fi and B ∈ Fj with i 6= j. Then there exists
j ∈ {1, 2, . . . , n} such that
⋃
i 6=j Fi can be pierced by 3 points.
Theorem 4.16 is a colorful version of Theorem 1.12 in the case of circles with the same
radius. Jerónimo-Castro, Magazinov and Soberón [22] also conjectured that Theorem 4.16
holds for families of translates of K, for any compact convex set K in R
2. In other words, they
conjectured a colorful version of Theorem 1.12.
4.3. A COLORFUL HELLY-TYPE PROBLEM IN R
3 49
Conjecture 4.17. Let K be a compact convex set in R
2. Let F1, . . . ,Fn be finite families of
translates of K, with n ≥ 2. Suppose that A ∩ B 6= ∅ for every A ∈ Fi and B ∈ Fj with i 6= j.
Then there exists j ∈ {1, 2, . . . , n} such that
⋃
i 6=j Fi can be pierced by 3 points.
We believe that Theorem 4.10 can be useful to prove Conjecture 4.17.
4.3. A colorful Helly-type problem in R
3
We already proved the 2-dimensional case of Theorem 3.11. Another natural question is if
with 2 color classes we have a similar conclusion in R
3. Mart́ınez Sandoval, Roldán-Pensado
and Rubin [28] presented the following problem.
Problem 4.18. Is it true that there exists n ∈ Z
+ such that for any two families A, B of
convex sets in R
3 so that A ∩ B 6= ∅ holds for all A ∈ A and B ∈ B, one of the families A or
B can be crossed by n lines?
The last problem is still open. Actually, the next weaker problem is also open.
Problem 4.19. Is it true that there exists n ∈ Z
+ such that for any family F of convex sets
in R
3 so that A ∩ B 6= ∅ holds for all A,B ∈ F , the family F can be crossed by n lines?
In this section we prove a particular case of Problem 4.18 by Montejano [32] and we give
an idea to solve Problem 4.19.
Montejano [32] proved that Problem 4.18 holds for small families of convex sets. Imagine
three red convex sets and three blue convex sets in R
3 such that every red set and every blue
set have non-empty intersection. Montejano proved that either there is a line transversal to the
red sets or there is a line transversal to the blue sets.
If we project the two families to a line, we obtain two finite families of intervals satisfying
the hypothesis of the 1-dimensional Colorful Helly theorem (Theorem 2.4), then the intervals
of one of the families have a common point, without loss of generality the blue intervals have
a common point b. The plane whose the projection is the point b is a plane transversal to the
blue sets (see Figure 4.10). However, we only have a plane transversal to one of the families
and we want a line transversal to one of the families. Montejano and Karasev ([32], [33]),
following the last argument in every direction and using topology proved that there is a line
transversal to one of the families. Although Montejano and Karasev proved the last particular
case of Problem 4.18, Montejano wanted to see an elementary proof. Strausz [41] gave an
elementary proof based on the non-planarity of the complete bipartite graph K3,3. We will see
the elementary proof by Strausz [41].
Theorem 4.20. Let A,B,C be three red convex sets in R
3 and let U, V,W be three blue convex
sets in R
3. Suppose that every red convex set intersect every blue convex set. Then either there
is a line transversal to the red convex sets or there is a line transversal to the blue convex sets.
Proof. By contradiction, suppose that there are no line transversals to the red convex sets nor
to the blue convex sets. Then, by Lemma 1.18, each red convex set can be separated by a
plane from the other two red convex sets. Analogously, each blue convex set can be separated
by a plane from the other two blue convex sets. Let HA be a plane such that A ⊂ H+
A and
B ∪ C ⊂ H−
A , and let a ∈ S
2 be the unitary normal vector of the plane HA. Analogously, we
50 CHAPTER 4. COLORFUL THEOREMS FOR LINE TRANSVERSALS
Figure 4.10: Montejano’s problem in R
2 is easy projecting the sets to a line and applying the
1-dimensional case of Colourful Helly. However, with the same argument in R
3 we only have a
plane transversal to one of the families instead of a line transversal to one of the families.
define the planes HB, HC , HU , HV , HW and the unitary normal vectors b, c, u, v, w ∈ S
2. We
color the vectors a, b, c red and the vectors u, v, w blue.
Now, we join each red vector to each blue vector with a spherical segment. Then we have
K3,3 drawn in S
2, thus there must be a crossing (by Kuratowski’s theorem). Without loss of
generality, the spherical segment through a ∈ S
2 and u ∈ S
2 intersects the spherical segment
through c ∈ S
2 and w ∈ S
2.
Since A ∩ U 6= ∅, then there exists q ∈ A ∩ U ⊂ (H+
A ∩H+
U ). Since A ⊂ H−
C and U ⊂ H−
W ,
then A ∩ U ⊂ H−
C ∩ H−
W . Therefore, q ∈ (H+
A ∩ H+
U ) \ (H
+
C ∪ H+
W ). Analogously, there exists
r ∈ (H+
C ∩ H+
W ) \ (H+
A ∪ H+
U ). In order to prove that this is a contradiction, we prove the
following lemma in arbitrary dimension.
Lemma. Let H+
A , H
+
U , H
+
C , H
+
W be half spaces in R
d with unitary normal vectors a, u, c, w ∈
S
d−1, respectively. If
(H+
A ∩H+
U ) \ (H
+
C ∪H+
W ) 6= ∅,
and
(H+
C ∩H+
W ) \ (H+
A ∪H+
U ) 6= ∅,
then the spherical segment au and the spherical segment cw are disjoint.
Proof. Let q ∈ (H+
A ∩ H+
U ) \ (H+
C ∪ H+
W ) and r ∈ (H+
C ∩ H+
W ) \ (H+
A ∪ H+
U ). Without loss of
generality, we suppose that 0 ∈ HA ∩HU and let p ∈ HC ∩HW . In other words,
HA = {x ∈ R
d : a · x = 0},
HU = {x ∈ R
d : u · x = 0},
HC = {x ∈ R
d : c · x = c · p} = {x ∈ R
d : c · (x− p) = 0},
HW = {x ∈ R
d : w · x = w · p} = {x ∈ R
d : w · (x− p) = 0}.
4.3. A COLORFUL HELLY-TYPE PROBLEM IN R
3 51
Then, since q ∈ (H+
A ∩H+
U )\(H
+
C ∪H+
W ) and r ∈ (H+
C ∩H+
W )\(H+
A ∪H+
U ), we have the following
eight inequalities:
a · q > 0 u · q > 0
c · (q − p) < 0 w · (q − p) < 0
c · (r − p) > 0 w · (r − p) > 0
a · r < 0 u · r < 0
To prove the lemma, we suppose, by contradiction, that z is in the intersection of the spherical
segment au and the spherical segment cw. Then there exists i, j,m, n > 0 such that z =
ia+ ju = mc+ nw.
On the one hand, z · q = (ia+ ju) · q > 0 and z · (q − p) = (mc+ nw) · (q − p) < 0. Thus,
0 < z · q < z · p.
On the other hand, z · r = (ia+ ju) · r < 0 and z · (r− p) = (mc+ nw) · (r− p) > 0. Thus,
0 > z · r > z · p,
a contradiction.
Since the spherical segment through a ∈ S
2 and u ∈ S
2 intersects the spherical segment
through c ∈ S
2 and w ∈ S
2, by the lemma, we have a contradiction.
Recently, Holmsen [20] gave a new proof of Theorem 4.20 (which is a particular case of
Problem 4.18) using the Borsuk-Ulam theorem [3]. On the other hand, Bárány [6] proved a
particular case of Problem 4.19. However, both Problem 4.18 and Problem 4.19 are still open.
We finish this section with an idea to prove Problem 4.19.
An idea to Problem 4.19.
We suspect Problem 4.19 holds with n ≥ 3. The idea goes as follows. For every orthonormal
base {u, v, w} in R
3 let lu, lv, lw be lines through the origin such that u ∈ lu, v ∈ lv, w ∈ lw. We
project the convex sets in the family F to the line lu, then we obtain a family of intervals in
the line lu satisfying the hypothesis of the 1-dimensional Helly theorem (Theorem 1.4). Since
every two sets in F have a non-empty intersection, then the intervals have a common point
f ∈ lu (by Theorem 1.4). Let Hu be the hyperplane where the projection is the point f ∈ lu.
Note that Hu is orthogonal to u ∈ S
2 and is transversal to the family F . Analogously, there
exist hyperplanes Hv, Hw such that Hv, Hw are orthogonal to v, w ∈ S
2 (respectively) and are
transversal to the family F . Let ku, kv, kw be the pairwise intersections of the hyperplanes
Hu, Hv, Hw.
We believe that there exists an orthogonal base {u, v, w} such that the three lines ku, kv, kw
and perhaps together with other lines cross the family F . A new topological result might be
needed to prove our claim.
52 CHAPTER 4. COLORFUL THEOREMS FOR LINE TRANSVERSALS
4.4. Colorful Eckhoff
In 2021, McGinnis and Zerbib [31] proved Theorem 1.15 using the KKM theorem (Theorem
4.1). We observed that following the same ideas of McGinnis and Zerbib and using the Colorful
KKM theorem (Theorem 4.4) we can obtain colorful versions of Theorems 1.14 and 1.15. Af-
terwards, McGinnis and Zerbib also noticed the colorful versions and uploaded a second version
of their paper. In this section we prove colorful versions of Theorems 1.14 and 1.15.
We begin with the colorful version of Theorem 1.14. Let F1, . . . ,F4 be finite families of
connected sets in R
2. Suppose that every four sets A1 ∈ F1, A2 ∈ F2, A3 ∈ F3, A4 ∈ F4 have
a line transversal. We prove that there exists i ∈ {1, . . . , 4} such that the family Fi can be
crossed by 2 lines. This result is joint work with Edgardo Roldán-Pensado.
The geometrical idea of our proof goes as follows. If there are two lines crossing one of the
families, we are done. Otherwise, we suppose, by contradiction, that for each family Fi and for
each two lines in the plane with non-empty intersection there is a set in the family Fi contained
in the interior of one of the 4 regions bounded by the two lines. Then using the colorful KKM
theorem (Theorem 4.4) we prove that there are two lines l1, l2 (with non-empty intersection)
and four sets Ci ∈ Fi, for i = 1, . . . , 4, so that every set Ci is contained in the interior of one
of the 4 regions bounded by the lines l1, l2, each set Ci in a different region (see Figure 4.11).
Then the sets C1, C2, C3, C4 do not have a line transversal, a contradiction.
C1
C2
C3
C4
Figure 4.11: If there are no two lines crossing one of the families Fi, then there are four sets
Ci ∈ Fi, for i = 1, . . . , 4, such that the sets C1, C2, C3, C4 do not have a line transversal.
Theorem 4.21. Let F1, . . . ,F4 be finite families of connected sets in R
2. If every four sets
A1 ∈ F1, A2 ∈ F2, . . . , A4 ∈ F4 have a line transversal, then there exists i ∈ {1, . . . , 4} such
that the family Fi can be crossed by 2 lines.
Proof. We can assume, without loss of generality, that the sets in the four finite families are
compact (see section 1.3). Hence, we may scale the plane such that every set in Fj is contained
in the unit disk, for each j ∈ {1, . . . , 4}. For each point x = (x1, . . . , x4) ∈ ∆3 and every
i = 1, . . . , 4 we define fi(x), li(x) and Ri
x as in the Proof of Theorem 4.7 (see Figure 4.12).
For i, j = 1, . . . , 4, let Oj
i be the set of points x ∈ ∆3 such that Ri
x contains a set F ∈ Fj.
Since the sets F ∈ Fj are compact, Oj
i is open for all i, j. If there is some x ∈ ∆3 and
j ∈ {1, . . . , 4} for which x /∈
⋃4
i=1 O
j
i , then since the sets in Fj are connected, every set in
Fj must intersect
⋃2
i=1 li(x), and we are done. Otherwise, we assume for contradiction that
4.4. COLORFUL ECKHOFF 53
f1(x)
f2(x)
f3(x)
f4(x) = (1, 0)
R1
x
R2
x
R3
x
R4
x
Figure 4.12: Illustration for the proof of Theorem 4.21.
∆3 =
⋃4
i=1 O
j
i for all j. Observe that if x ∈ conv{ei : i ∈ I} for some I ⊂ {1, . . . , 4}, then
Rk
x = ∅ for k /∈ I, and therefore x ∈
⋃
i∈I O
j
i for all j.
The last paragraph shows that, for all j, {Oj
1, . . . , O
j
4} is an open cover that satisfies the
hypothesis of the Colorful KKM theorem (Theorem 4.4), then there exists some permutation
π ∈ S4 and a point y = (y1, . . . , y4) ∈
⋂4
i=1 O
π(i)
i . In other words, each of the open regions Ri
y
contains a set Ci ∈ Fπ(i) (in particular Ri
y 6= ∅ and yi 6= 0 for all i ∈ {1, . . . , 4}).
Then the sets C1, C2, C3, C4 do not have a line transversal, a contradiction.
Note that Theorem 4.21 implies Theorem 1.14. Indeed, if F is a family satisfying the
hypothesis of Theorem 1.14, then Fi = F for i = 1, . . . , 4 satisfy the hypothesis of Theorem
4.21 and thus the family F can be crossed by 2 lines.
Further, if we use Theorem 4.5 (instead of Theorem 4.4) we have the following stronger
result.
Theorem 4.22. Let F1, . . . ,Fn be finite families of connected sets in R
2, with n ≥ 4. Suppose
that every four sets A1 ∈ Fi1 , A2 ∈ Fi2 , A3 ∈ Fi3 , A4 ∈ Fi4, for 1 ≤ i1 < i2 < i3 < i4 ≤ n,
have a line transversal. Then there exists I ⊂ {1, . . . , n}, with |I| = n− 3, such that the family
⋃
i∈I Fi can be crossed by 2 lines.
Proof. We assume for contradiction that for every I ⊂ {1, . . . , n}, with |I| = n− 3, the family
⋃
i∈I Fi cannot be crossed by 2 lines. Then, following the same arguments of the proof of
Theorem 4.21 and using the same notation, we have that for every I ∈
(
[n]
n−4+1
)
, the family
{
⋃
j∈I
Oj
1, . . . ,
⋃
j∈I
Oj
4
}
is an open cover of ∆3 that satisfies the hypothesis of Theorem 4.1. Then, by Theorem 4.5,
there is an injective function π : [4] −→ [n] and a point y ∈
⋂4
i=1 O
π(i)
i 6= ∅. In other words,
each of the open regions Ri
y contains a set Ci ∈ Fπ(i). Then the sets C1, . . . , C4 do not have a
line transversal, a contradiction.
Now we prove a colorful version of Theorem 1.15. Let F1, . . . ,F6 be finite families of
connected sets in R
2. Suppose that every three sets A1 ∈ Fi1 , A2 ∈ Fi2 , A3 ∈ Fi3 , for 1 ≤ i1 <
54 CHAPTER 4. COLORFUL THEOREMS FOR LINE TRANSVERSALS
i2 < i3 ≤ 6, have a line transversal. We prove that there exists i ∈ {1, . . . , 6} such that the
family Fi can be crossed by 3 lines. This result is joint work with Edgardo Roldán-Pensado.
The proof is very similar to the proof of Theorem 4.21. The idea goes as follows. If there are
three lines crossing one of the families, we are done. Otherwise, we suppose, by contradiction,
that for each family Fi and for every three lines in the plane there is a set in the family Fi not
crossing the three lines. Then using the Colorful KKM theorem (Theorem 4.4) we prove that
there are three lines l1, l2, l3 separating three sets C1, C2, C3 from three different families (see
Figure 4.13). By Lemma 1.16, the sets C1, C2, C3 do not have a line transversal, a contradiction.
C1
C2
C3
Figure 4.13: If there are no three lines crossing one of the families Fi, then there are three
sets C1, C2, C3 from three different families such that the sets C1, C2, C3 do not have a line
transversal.
Theorem 4.23. Let F1, . . . ,F6 be finite families of connected sets in R
2. If every three sets
A1 ∈ Fi1 , A2 ∈ Fi2 , A3 ∈ Fi3, for 1 ≤ i1 < i2 < i3 ≤ 6, have a line transversal, then there exists
i ∈ {1, . . . , 6} such that the family Fi can be crossed by 3 lines.
Proof. We can assume, without loss of generality, that the sets in the six finite families are
compact (see section 1.3). Hence, we may scale the plane such that every set in Fj is contained
in the unit disk, for each j ∈ {1, . . . , 6}. Let f(t) be a parametrization of the unit circle defined
by f(t) = (cos(2πt), sin(2πt)).
To each point x = (x1, . . . , x6) ∈ ∆5 we associate 6 points on the unit circle given by
fi(x) = f
(
i
∑
j=1
xj
)
,
for 1 ≤ i ≤ 6. Let l1(x) = l4(x) = [f1(x), f4(x)], l2(x) = l5(x) = [f2(x), f5(x)] and l3(x) =
l6(x) = [f3(x), f6(x)]. For i = 1, . . . , 6 let Ri
x be the interior of the region bounded by
li−1(x), li(x) and the arc on the unit circle connecting fi−1(x) and fi(x), where i − 1 is taken
modulo 6 (see Figure 4.14).
Notice that f6(x) = (1, 0) for each x ∈ ∆5. Also, the points x1, x2, . . . , x6 are always in
counter-clockwise order.
For i, j = 1, . . . , 6, let Oj
i be the set of points x ∈ ∆5 such that Ri
x contains a set F ∈ Fj.
Since the sets F ∈ Fj are compact, Oj
i is open for all i, j. If there is some x ∈ ∆5 and
j ∈ {1, . . . , 6} for which x /∈
⋃6
i=1 O
j
i , then since the sets in Fj are connected, every set in
4.4. COLORFUL ECKHOFF 55
f1(x)f2(x)
f3(x)
f4(x)
f5(x)
f6(x) = (1, 0)
R1
x
R2
x
R3
x
R4
x
R5
x
R6
x
Figure 4.14: Illustration for the proof of Theorem 4.23.
Fj must intersect
⋃3
i=1 li(x), and we are done. Otherwise, we assume for contradiction that
∆5 =
⋃6
i=1 O
j
i for all j. Observe that if x ∈ conv{ei : i ∈ I} for some I ⊂ {1, . . . , 6}, then
Rk
x = ∅ for k /∈ I, and therefore x ∈
⋃
i∈I O
j
i for all j.
The last paragraph shows that, for all j, {Oj
1, . . . , O
j
6} is an open cover that satisfies the
hypothesis of the colorful KKM theorem (Theorem 4.4), then there exists some permutation
π ∈ S6 and a point y = (y1, . . . , y6) ∈
⋂6
i=1 O
π(i)
i . In other words, each of the open regions Ri
y
contains a set Ci ∈ Fπ(i) (in particular Ri
y 6= ∅ and yi 6= 0 for all i ∈ {1, . . . , 6}).
Observe that the regions R1
y, R
3
y, R
5
y are pairwise disjoint or the regions R2
y, R
4
y, R
6
y are pair-
wise disjoint. Without loss of generality, we assume R1
y, R
3
y, R
5
y are pairwise disjoint. Then by
Lemma 1.16, the sets C1, C3, C5 do not have a line transversal, a contradiction.
Note that Theorem 4.23 implies Theorem 1.15. Indeed, if F is a family satisfying the
hypothesis of Theorem 1.15, then Fi = F for i = 1, . . . , 6 satisfy the hypothesis of Theorem
4.23 and thus the family F can be crossed by 3 lines.
Further, if we use Theorem 4.5 (instead of Theorem 4.4) we have the following stronger
result.
Theorem 4.24. Let F1, . . . ,Fn be finite families of connected sets in R
2, with n ≥ 6. Suppose
that every three sets A1 ∈ Fi1 , A2 ∈ Fi2 , A3 ∈ Fi3, for 1 ≤ i1 < i2 < i3 ≤ n, have a line
transversal. Then there exists I ⊂ {1, . . . , n}, with |I| = n − 5, such that the family
⋃
i∈I Fi
can be crossed by 3 lines.
Proof. We assume for contradiction that for every I ⊂ {1, . . . , n}, with |I| = n− 5, the family
⋃
i∈I Fi cannot be crossed by 3 lines. Then, following the same arguments of the proof of
Theorem 4.23 and using the same notation, we have that for every I ∈
(
[n]
n−6+1
)
, the family
{
⋃
j∈I
Oj
1, . . . ,
⋃
j∈I
Oj
6
}
is an open cover of ∆5 that satisfies the hypothesis of Theorem 4.1. Then, by Theorem 4.5,
there is an injective function π : [6] −→ [n] and a point y ∈
⋂6
i=1 O
π(i)
i 6= ∅. In other words,
each of the open regions Ri
y contains a set Ci ∈ Fπ(i).
56 CHAPTER 4. COLORFUL THEOREMS FOR LINE TRANSVERSALS
Observe that the regions R1
y, R
3
y, R
5
y are pairwise disjoint or the regions R2
y, R
4
y, R
6
y are pair-
wise disjoint. Without loss of generality, we assume R1
y, R
3
y, R
5
y are pairwise disjoint. Then by
Lemma 1.16, the sets C1, C3, C5 do not have a line transversal, a contradiction.
The colorful version of Theorem 1.15 that we wanted to prove uses 3 colors instead of 6
colors. Although we have not been able to prove a colorful version of Theorem 1.15 using only
3 colors, we prove the following theorem concerning finite families of translates of a compact
convex set using only 3 colors.
Theorem 4.25. Let K be a compact convex set in R
2. Let F1,F2,F3 be finite families of
translates of K in R
2. If every three sets A1 ∈ F1, A2 ∈ F2, A3 ∈ F3 have a line transversal,
then there exists i ∈ {1, 2, 3} such that the family Fi can be crossed by 4 lines.
Proof. Let C be the set of all the rainbow pairs (Ci, Cj) such that Ci and Cj are disjoint. In
other words,
C = {(Ci, Cj) | Ci ∈ Fi, Cj ∈ Fj, i 6= j, Ci ∩ Cj = ∅}.
If C is empty, then we project the sets of the three families in some fixed line and so we
obtain three families of segments satisfying the hypothesis of the 1-dimensional case of the
Colorful Helly theorem (Theorem 2.4). Thus, by the Colorful Helly theorem (Theorem 2.4) on
the line, there is i ∈ {1, 2, 3} such that Fi has a line transversal, and we are done.
Otherwise, choose a pair (Ci, Cj) ∈ C for which the angle between the inner common
tangents of (Ci, Cj) is minimal among all pairs in C. Without loss of generality, we assume that
(C1, C2) ∈ C, with C1 ∈ F1, C2 ∈ F2, is one of the pairs for which the angle between the inner
common tangents is minimal.
We claim that the 4 common tangents of (C1, C2) cross the family F3. Let l1, l2 be the
inner common tangents of C1 and C2. Let l3, l4 be the outer common tangents of C1 and
C2. We denote by l+1 , l
+
2 , l
+
3 , l
+
4 the half-planes bounded by l1, l2, l3, l4, respectively, such that
C1 ⊂
⋂4
i=1 l
+
i .
We define the regions R1, . . . , R6 as follows. Let R1 be the interior of l+1 ∩ l+2 , let R2 the
interior of l−1 ∩ l−2 , let R3 be the interior of l+1 ∩ l−2 ∩ l−3 , let R4 be the interior of l−1 ∩ l+2 ∩ l−4 ,
let R5 be the interior of l+1 ∩ l−2 ∩ l+3 and let R6 be the interior of l−1 ∩ l+2 ∩ l+4 . See Figure 4.15.
C1 C2
l1l2
l3
l4
R1 R2
R3
R4
R5
R6
Figure 4.15: Illustration for the proof of Theorem 4.25.
4.4. COLORFUL ECKHOFF 57
If there is a set C3 ∈ F3 contained in the region R1, then the angle between the inner
common tangents of (C2, C3) ∈ C is less than the angle between the inner common tangents of
(C1, C2), contradicting the choice of the pair (C1, C2), see Figure 4.16. Analogously, if there is
a set C3 ∈ F3 contained in the region R2, then the angle between the inner common tangents of
(C1, C3) ∈ C is less than the angle between the inner common tangents of (C1, C2), contradicting
the choice of the pair (C1, C2). Thus, there are no sets in the family F3 contained in the regions
R1 or R2.
C1 C2
l1l2
αβ
ω
γ
C3
Figure 4.16: Notice that α = β + ω + γ, then α > β.
If there is a set C3 ∈ F3 contained in the region R3, then by Lemma 1.16, the sets C1 ∈
F1, C2 ∈ F2, C3 ∈ F3 do not have a line transversal, a contradiction. Analogously, if there is a
set C3 ∈ F3 contained in the region R4, then by Lemma 1.16, the sets C1 ∈ F1, C2 ∈ F2, C3 ∈ F3
do not have a line transversal, a contradiction. Thus, there are no sets in the family F3 contained
in the regions R3 or R4.
Since the sets in the three families are translates of K, then every set in the family F3 has
the same width of C1 and C2 in the direction orthogonal to the lines l3, l4. Thus, there are no
sets in the family F3 contained in the regions R5 or R6.
Therefore, every set in the family F3 must intersects some of the lines l1, l2, l3, l4.
Note that using the same proof, we have that Theorem 4.25 is also true for finite families
of congruent copies of a compact convex set of constant width.
Theorem 4.26. Let K be a compact convex set of constant width in R
2. Let F1,F2,F3 be
finite families of congruent copies of K in R
2. If every three sets A1 ∈ F1, A2 ∈ F2, A3 ∈ F3
have a line transversal, then there exists i ∈ {1, 2, 3} such that the family Fi can be crossed by
4 lines.
In particular, Theorems 4.25 and 4.26 hold for translates of circles of the same radius.
Theorem 4.27. Let F1,F2,F3 be finite families of circles of the same radius in R
2. If every
three circles A1 ∈ F1, A2 ∈ F2, A3 ∈ F3 have a line transversal, then there exists i ∈ {1, 2, 3}
such that the family Fi can be crossed by 4 lines.
An interesting question is if we can improve the number of lines in the conclusion of Theo-
rems 4.25, 4.26 and 4.27.
58 CHAPTER 4. COLORFUL THEOREMS FOR LINE TRANSVERSALS
Problem 4.28. Let K be a compact convex set in R
2. Let F1,F2,F3 be finite families of
translates of K in R
2 such that every three sets A1 ∈ F1, A2 ∈ F2, A3 ∈ F3 have a line
transversal. Is there exists i ∈ {1, 2, 3} such that the family Fi can be crossed by 3 (or 2) lines?
On the other hand, we still wonder if there is a colorful version of Theorem 1.15 using 3
colors.
Problem 4.29. Is there exists n ∈ Z
+ with the following property? Let F1,F2,F3 be finite
families of connected sets in R
2. If every three sets A1 ∈ F1, A2 ∈ F2, A3 ∈ F3 have a line
transversal, then there exists i ∈ {1, 2, 3} such that the family Fi can be crossed by n lines.
In addition, we conjecture the following colorful version of Theorem 1.15 that uses 4 colors.
Conjecture 4.30. There exists n ∈ Z
+ with the following property. Let F1,F2,F3,F4 be
finite families of connected sets in R
2. If every three sets A1 ∈ Fi1 , A2 ∈ Fi2 , A3 ∈ Fi3, for
1 ≤ i1 < i2 < i3 ≤ 4, have a line transversal, then there exists i ∈ {1, . . . , 4} such that the
family Fi can be crossed by n lines.
We tried to prove that Conjecture 4.30 holds with n = 3, however we did not succeed.
The idea was the following: for each i ∈ {1, ..., 4} we applied the KKM theorem (Theorem
4.1) to the family Fi, then following the same ideas of the proof of Theorem 4.23, we have
that there are three sets Ai
1, A
i
2, A
i
3 in the family Fi such that the sets Ai
1, A
i
2, A
i
3 do not have
a line transversal. Using the 12 convex sets Ai
j, for i = 1, 2, 3, 4 and j = 1, 2, 3, we wanted
to prove that there are 3 sets in different families without line transversal, which would be a
contradiction. It gave rise to the following conjecture.
Conjecture 4.31. Let F1,F2,F3,F4 be families of connected sets in R
2, each family with 3
sets. If every three sets A1 ∈ Fi1 , A2 ∈ Fi2 , A3 ∈ Fi3, for 1 ≤ i1 < i2 < i3 ≤ 4, have a line
transversal, then there exists i ∈ {1, 2, 3, 4} such that Fi has a line transversal.
However, Conjecture 4.31 is false. The counterexample is given in Example 4.32 and Figure
4.17.
Example 4.32. Let
F1 = {[(−20, 6), (−2, 6)], [(2, 6), (20, 6)], [(−8, 12), (8, 12)]},
F2 = {[(−8, 2), (8, 2)], [(−8, 6), (−8, 24)], [(8, 6), (8, 24)]},
F3 = {[(−8, 8), (8, 8)], [(−17, 10), (−1, 10)], [(1, 10), (17, 10)]},
F4 = {[(−8, 4), (8, 4)], [(−10, 6), (−10, 24)], [(10, 6), (10, 24)]}
be families of segments in the plane. The families F1,F2,F3,F4 satisfy the hypothesis of Con-
jecture 4.31. However, none of the four families has a line transversal (see Figure 4.17).
Even though Conjecture 4.31 is false, it does not imply that Conjecture 4.30 is false. Moti-
vated by Theorem 4.25, we still believe Conjecture 4.30 is true, although maybe n will be very
large.
4.4. COLORFUL ECKHOFF 59
Figure 4.17: Illustration for Example 4.32.
60 CHAPTER 4. COLORFUL THEOREMS FOR LINE TRANSVERSALS
Chapter 5
Conclusions
As we mentioned in the Introduction, this work is a survey of colorful theorems in discrete
and convex geometry. Chapters 1 and 2 were introductory. In Chapter 3 we saw Theorems 3.2
([1], [21]) and 3.11 ([28]) which are generalizations of the Colorful Carathéodory theorem and
the Colorful Helly theorem, respectively.
The original contributions of this Thesis are the following theorems and observations.
• In Example 3.4 we showed that we can not continue to weaken the hypothesis of Theorem
3.2. In Example 3.6 we showed that in Theorem 3.2 we can only ensure the existence of
1 rainbow simplex.
• In Theorem 4.7 we gave and proved the best numbers satisfying the 2-dimensional case
of Theorem 3.11 (f(2) = 1 and g(2) = 2). Furthermore, we proved Theorem 4.8 which is
stronger than Theorem 4.7. In addition, in Theorem 4.6 we proved a particular case of
Theorem 4.7 with an elementary proof. We also proved Theorems 4.10, 4.11, 4.12, 4.13
and 4.14 concerning some special families where the 2-dimensional case of Theorem 3.11
holds with g(2) = 1. Finally, we proposed Problem 4.15 and we believe that Theorem
4.10 can be useful to prove Conjecture 4.17.
• We proved Theorems 4.21 and 4.23 (colorful versions of Eckhoff’s theorems), although
McGinnis and Zerbib [31] after wrote a paper with these results. Additionally, we proved
Theorems 4.25 and 4.26 (and Theorem 4.27 which is a particular case of Theorems 4.25
and 4.26) concerning families of translates of a compact convex set or families of congruent
copies of a compact convex set of constant width. An interesting question is if in Theorem
4.25 we can improve the 4 lines (in the conclusion) by 3 or 2 lines (Problem 4.28). Finally,
in Problem 4.29 and Conjecture 4.30 we wonder if we can improve the number of families
(or colors) in Theorem 4.23.
61
62 CHAPTER 5. CONCLUSIONS
Bibliography
[1] J. L. Arocha, I. Bárány, J. Bracho, R. Fabila, and L. Montejano. Very Colorful Theorems.
Discrete Comput. Geom., 42(2):142–154, 2009.
[2] I. Bárány and D. G. Larman. A colored version of Tverberg’s theorem. Journal of the
London Mathematical Society, 2(2):314–320, 1992.
[3] K. Borsuk. Drei Sätze über die n-dimensionale euklidische Sphäre. Fundamenta Mathe-
maticae, 20:177–190, 1933.
[4] I. Bárány. A generalization of Carathéodory theorem. Discrete Math., 40:141–152, 1982.
[5] I. Bárány. Combinatorial Convexity, volume 77. American Mathematical Society, Provi-
dence, Rhode Island, 2021.
[6] I. Bárány. Pairwise intersecting convex sets and cylinders in R
3. arXiv preprint
arXiv:2104.02148, 2021.
[7] L. E. J. Brouwer. Über Abbildung von Mannigfaltigkeiten. Mathematische Annalen,
71(1):97–115, 1911.
[8] C. Carathéodory. Uber den Variabilitatsbereich der Koeffizienten von Potenzreihen. Math.
Annalen, 64:95–115, 1907.
[9] L. Danzer. Über ein Problem aus der kombinatorischen Geometrie. Archiv der Mathematik,
8(5):347–351, 1957.
[10] L. Danzer. Zur Lösung des Gallaischen Problems über Kreisscheiben in der euklidischen
Ebene. Studia Sci. Math. Hungar., 21:111–134, 1986.
[11] J. Eckhoff. Transversalenprobleme vom Gallaischen Typ. PhD thesis, Dissertation, Uni-
versität Göttingen, 1969.
[12] J. Eckhoff. Transversalenprobleme in der Ebene. Archiv der Mathematik, 24(1):195–202,
1973.
[13] J. Eckhoff. A Gallai-type transversal problem in the plane. Discrete Comput. Geom.,
9(2):203–214, 1993.
[14] D. Gale. Equilibrium in a discrete exchange economy with money. International Journal
of Game Theory, 13(1):61–64, 1984.
63
64 BIBLIOGRAPHY
[15] J. E. Goodman, R. Pollack, and R. Wenger. Bounding the number of geometric permuta-
tions induced by k-transversals. Journal of Combinatorial Theory, Series A, 75(2):187–197,
1996.
[16] B. Grünbaum. On intersections of similar sets. Portugal Math., 18:155–164, 1959.
[17] H. Hadwiger and H. Debrunner. Combinatorial Geometry in the plane. Dover Publications,
1966.
[18] E. Helly. Uber Mengen konvexer Korper mit gemeinschaftlichen Punkten. Jahres-berichte
der Deutschen Math.-Verein., 32:175–176, 1923.
[19] A. F. Holmsen. The intersection of a matroid and an oriented matroid. Advances in
Mathematics, 290:1–14, 2016.
[20] A. F. Holmsen. On a transversal theorem of Montejano and Karasev. arXiv preprint
arXiv:2112.07907, 2021.
[21] A. F. Holmsen, J. Pach, and H. Tverberg. Points sorrounding the origin. Combinatorica,
28(6):633–644, 2008.
[22] J. Jerónimo-Castro, A. Magazinov, and P. Soberón. On a problem by Dol’nikov. Discrete
Mathematics, 338(9):1577–1585, 2015.
[23] R. N. Karasev. Transversals for families of translates of a two-dimensional convex compact
set. Discrete Comput. Geom., 24(2):345–354, 2000.
[24] R. N. Karasev. Piercing Families of Convex Sets with the d-Intersection Property in R
d.
Discrete Comput. Geom., 39(4):766–777, 2008.
[25] B. Knaster, C. Kuratowski, and S. Mazurkiewicz. Ein Beweis des Fixpunktsatzes für
n-dimensionale Simplexe. Fundamenta Mathematicae, 14(1):132–137, 1929.
[26] D. Kramer. Transversalenprobleme vom Hellyschen und Gallaischen Typ. PhD thesis,
Dissertation, Universität Dortmund, 1974.
[27] S. Krasa and N. C. Yannelis. An elementary proof of the Knaster-Kuratowski-
Mazurkiewicz-Shapley theorem. Economic Theory, 4(3):467–471, 1994.
[28] L. Mart́ınez-Sandoval, E. Roldán-Pensado, and N. Rubin. Further Consequences of the
Colorful Helly Hypothesis. Discrete Comput. Geom., 63(4):848–866, 2020.
[29] J. Matoušek. Lectures on discrete geometry, volume 212. Springer-Verlag, New York, 2002.
[30] J. Matoušek. Using the Borsuk-Ulam theorem: lectures on topological methods in combi-
natorics and geometry. Springer, 2003.
[31] D. McGinnis and S. Zerbib. Line transversals in families of connected sets the plane. arXiv
preprint arXiv:2103.05565, 2021.
[32] L. Montejano. Transversals, Topology and Colorful Geometric Results. Bolyai Society
Mathematica Studies, 24:1–14, 2010.
BIBLIOGRAPHY 65
[33] L. Montejano and R. N. Karasev. Topological transversals to a family of convex sets.
Discrete Comput. Geom., 46(2):283–300, 2011.
[34] J. Radon. Mengen konvexer Korper, die einen gemeinsamen Punkt enthalten. Math. Ann.,
83:113–115, 1921.
[35] L. Santaló. Un teorema sobre conjuntos de paralelepipedos de aristas paralelas. Publ. Inst.
Mat. Univ. Nac. Litoral, 2(4):49–60, 1940.
[36] P. Sarrabezolles. The colourful simplicial depth conjecture. Journal of Combinatorial
Theory, Series A, 130:119–128, 2015.
[37] P. Soberón. Equal coefficients and tolerance in coloured Tverberg partitions. Combinator-
ica, 35(2):235–252, 2015.
[38] P. Soberón. Robust Tverberg and colourful Carathéodory results via random choice. Com-
binatorics, Probability and Computing, 27(3):427–440, 2018.
[39] P. Soberón. Fair distributions for more participants than allocations. arXiv preprint
arXiv:2110.03600, 2021.
[40] E. Sperner. Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes. In Abh.
Math. Sem. Univ. Hamburg, volume 6, pages 265–272. Springer, 1928.
[41] R. Strausz. How do 9 Points Look Like in E
3 ? Annals of Combinatorics, pages 1–5, 2022.