 
 
 
UNIVERSIDAD NACIONAL AUTÓNOMA DE MEXICO 
PROGRAMA DE MAESTRÍA Y DOCTORADO EN CIENCIAS MATEMÁTICAS Y 
DE LA ESPECIALIZACIÓN EN ESTADÍSTICA APLICADA 
  
 
 
 
EXPLORACIONES EN GEOMETRÍA COMBINATORIA: CIRCUNRADIOS DISTINTOS, 
TEOREMAS TIPO HALL GEOMÉTRICOS, TEOREMAS TIPO TURÁN FRACCIONALES, 
MATROIDES DE CAMINOS LATICES Y TRANSVERSALES DE KNESER 
 
 
 
TESIS 
QUE PARA OPTAR POR EL GRADO DE: 
DOCTOR EN CIENCIAS 
 
 
 
PRESENTA: 
LEONARDO IGNACIO MARTÍNEZ SANDOVAL 
 
 
TUTORES PRINCIPALES 
 
LUIS MONTEJANO PEIMBERT 
INSTITUTO DE MATEMÁTICAS, UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO 
 
JORGE LUIS RAMÍREZ ALFONSÍN 
INSTITUT MONTPELLIÉRAIN ALEXANDER GROTHENDIECK, UNIVERSITÉ DE 
MONTPELLIER 
 
MIEMBROS DEL COMITÉ TUTOR 
 
JAVIER BRACHO CARPIZO  
INSTITUTO DE MATEMÁTICAS, UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO 
 
GERÓNIMO URIBE BRAVO  
INSTITUTO DE MATEMÁTICAS, UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO 
 
 
MÉXICO D.F., NOVIEMBRE DE 2015 
 
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. 
 
  
 
Explorations in combinatorial geometry:
Distinct circumradii, geometric Hall-type theorems,
fractional Turán-type theorems, lattice path matroids
and Kneser transversals
Leonardo Ignacio Mart́ınez Sandoval
PhD. Advisors:
Luis Montejano Peimbert
Jorge Luis Ramı́rez Alfonśın
November 25, 2015
Contents
1 Points defining triangles with distinct circumradii 21
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2 Erdős argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3 Small cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4 General case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2 Geometric Hall-type theorems 27
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.2 Our result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.1.3 Outline of paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Proof of Theorem 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3 A better upper bound by topological methods . . . . . . . . . . . . . . . . 31
2.3.1 The general position complex . . . . . . . . . . . . . . . . . . . . . 31
2.3.2 Colorful simplices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4 Proof of Theorem 2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.4.1 The completion of a simplicial complex . . . . . . . . . . . . . . . . 33
2.4.2 The Nerve theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3
4 CONTENTS
2.4.3 The q-star property . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.5 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.6 A Hall-type theorem for Sλ-free graphs . . . . . . . . . . . . . . . . . . . . 37
2.7 Proof of Theorem 2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3 Fractional Turán-type theorems 43
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1.1 Background and motivation . . . . . . . . . . . . . . . . . . . . . . 43
3.1.2 Results and outline . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2 Exact Turán numbers and extremal graphs . . . . . . . . . . . . . . . . . . 47
3.2.1 {P2, 2K2}-free graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.2 {P2, ℓK1}-free graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.3 Ramsey meets Turán: {3K1, Kr}-free graphs . . . . . . . . . . . . . 49
3.3 Linear fractional Turán-type theorem . . . . . . . . . . . . . . . . . . . . . 51
3.4 A bound for the chromatic number . . . . . . . . . . . . . . . . . . . . . . 53
4 Some algebraic results on lattice path matroids 55
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Lattice path matroids and snakes . . . . . . . . . . . . . . . . . . . . . . . 57
4.3 The Merino-Welsh conjecture for lattice path matroids . . . . . . . . . . . 65
5 Kneser transversals 73
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.1.2 Complete Kneser transversals . . . . . . . . . . . . . . . . . . . . . 75
5.1.3 Outline of chapter and results . . . . . . . . . . . . . . . . . . . . . 76
CONTENTS 5
5.2 Kneser transversals from Radon partitions . . . . . . . . . . . . . . . . . . 78
5.2.1 A lower bound for m∗(k, d, λ) in the non-trivial range . . . . . . . . 80
5.3 Matroids and cyclic polytopes . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.3.1 Some combinatorial tools . . . . . . . . . . . . . . . . . . . . . . . . 83
5.3.2 Upper bound of ζ(k, d, λ) . . . . . . . . . . . . . . . . . . . . . . . . 86
5.3.3 Lower bound of ζ(k, d, λ) . . . . . . . . . . . . . . . . . . . . . . . . 89
5.3.4 Asymptotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.4 Some exact values of m∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6 Appendix: Definitions and basic theory 97
6.1 Basic notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.2 Graphs, digraphs and hypergraphs . . . . . . . . . . . . . . . . . . . . . . 97
6.2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.2.2 Classical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.3 Convex geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.4 Matroids and oriented matroids . . . . . . . . . . . . . . . . . . . . . . . . 101
6.5 Bézout’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.6 Combinatorial topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Introduction
Combinatorial geometry is a broad and beautiful branch of mathematics. This PhD
Thesis consists of the study of five different topics in this area. Even though the problems
and the tools used to tackle them are diverse, they share a unifying goal:
To explore the interaction between combinatorial and geometric structures
The results of these explorations can be found in Chapters from 1 to 5. Each of them
can be read independently. At the beginning of each topic we provide some words on the
motivation of the problem, its relation to classical and current research, the coauthors
with which the work was done and where have the results been presented. Afterwards,
each chapter contains the main body of each contribution.
Throughout the exposition we will assume familiarity with basic definitions and results
on the following topics: graph theory, convex geometry, matroid and oriented matroid
theory, algebraic geometry and homology. Nevertheless, for completeness and reference
most of this basic theory can be found in the Appendix.
Summary
In Chapter 1 we study a problem by Paul Erdős: for a positive integer k, how many
points in general position do we need in the plane so that we can always find a k-subset
of them defining triangles with distinct circumradii? This question was posed in 1975 and
Erdős himself proposed a solution in 1978. However, the proof inadvertently left out a
non-trivial case. We deal with the case using basic tools from algebraic geometry and we
provide a polynomial bound for the needed number of points.
Chapter 2 and Chapter 3 share a theme in common: what kind of results can we get
when we place classical theorems from graph theory in geometric contexts? In both cases
the answer is fruitful.
7
8 CONTENTS
Specifically, in Chapter 2 we are interested in providing geometric extensions of Hall’s
criterion for matchings in bipartite graphs (1935). We obtain geometric Hall-type the-
orems for pairwise disjoint convex sets and for points in general position in euclidean
space. The tools of this chapter are topological, and are motivated by a remarkable
method introduced by Aharoni and Haxell in 2000 and its generalizations.
On the other hand, in Chapter 3 we begin with a fractional Helly theorem from 1979
by A. Liu and M. Katchalski to motivate a combinatorial result. We explore combinato-
rial conditions on families of graphs that allow us to have sharpened variants of Turán’s
theorem. We find interesting relations between the Turán numbers, the chromatic num-
bers and the clique numbers of graphs in the family. The tools in this chapter are only
combinatorial.
Chapters 4 and 5 are related to matroid and oriented matroid theory respectively.
In Chapter 4 we focus on obtaining some results for the well studied class of lattice
path matroids introduced by Bonin, de Mier and Noy in 2003. The main contribution is
proving for this class the validity of a 1999 conjecture of Merino and Welsh concerning
an inequality involving certain values of the Tutte polynomial. In order to do this, we
introduce and study snakes, a special class of “thin” lattice path matroids.
Finally, in Chapter 5 we explore a variant of a transversal problem posed by J.L.
Arocha, J. Bracho, L. Montejano and J.L. Ramı́rez-Alfonśın in 2010. In their original
work, they realized that if we have few points in euclidean space then it is possible to
find a transversal of a given dimension that goes through all the convex hulls of k-subsets
of points. Similarly, they show that it is impossible to find such a transversal when we
have many points. The authors give some specific bounds and they also leave some open
problems. If the definition of transversal is slightly more restrictive, then the problem can
be tackled using oriented matroid theory. We provide the details of the relation and we
give bounds for the family of cyclic polytopes.
Acknowledgments
This journey has been possible thanks to many people. I would like to give my thanks
here.
To my parents, Perla Sandoval and Ignacio Mart́ınez, who gave me life and who have
given to my brother and me all their support. With life we can interact with all that
past generations have left behind and we can also leave behind valuable things for future
generations.
To my brother, Emilio Mart́ınez, a partner in family and science, with whom I share
both humor and thirst for knowledge. He has given me abundant advice on productivity,
CONTENTS 9
health, sport, music and many other complementary topics.
To other members of my family who have supported me in various ways through my
path in mathematics.
To my advisors: Luis Montejano Peimbert and Jorge Ramı́rez Alfonśın.
Luis Montejano claims that for any creative process (like that of mathematics) it is
necessary to have freedom, courage and naiveness. Being consistent to these principles,
he has given me a good amount of freedom together with a good amount of guidance. He
has given me his support to start various projects on my own and he has also invited me
to participate in some others.
Jorge Ramı́rez played a key role in the interaction with Univerité de Montpellier. He
helped me in every aspect to make possible the joint agreement with France: mathematics,
lodging, paperwork, language, etc.
To Norma Morales, for joining me in a large part of this adventure. I feel lucky for
the mutual help, the trust and the affection that we have developed.
To Lalo, for being a constant partner in mathematics and in various additional projects.
For the various conversations we have had, for his advise and his point of view. To
Edgardo Roldán, for sharing with me a lot of his mathematical experience. To Fernando
Campos with whom, even though our professional paths have splitted, there still exists a
close friendship since our undergraduate studies. To Maŕıa José with whom there exists a
similar close friendship since middle school and with whom I can talk about many different
topics.
To the Olimpiada Mexicana de Matemáticas and many people involved in its organiza-
tion. Specially to Toño who has invited me these years to be part of his team to promote
mathematics in Mexico and who has given me his trust for being the mexican Team
Leader for the International Mathematical Olympiad. To Jeśus Jerónimo, for introducing
combinatorial geometry to me. To Malú, Luis Miguel, Miguel Raggi, Marco, David Tor-
res, José Luis Campos, Irving, Hugo, Daniel, Rogelio, Mila, David Cosśıo, Nacho, Héctor,
Chino, Eugenio, Fernanda, Rita. I have learned a lot from all of you.
To the students in the Olympiad that I have trained. I have also learned a lot from
you. Specially from Diego Roque, Juan Ortiz and Adán Medrano.
To the mathematicians from Unidad Juriquilla del Insituto de Matemáticas: Déborah,
Gaby, Adriana, Amanda, Liz, Mirna, Maribel, Nancy, Jendry, Adolfo, Gerardo, Juan
Carlos, Gabriel, Isaac, Adrián, Alejandro, Jorge. These years I have truly felt part of a
strong community and a growing project. This is also the correct paragraph to thank
Natalia Garca for being a good friend and “older sister”. For sharing her experience
in mathematical finance with me at the beggining of my graduate studies. To Lucha,
10 CONTENTS
Araceli, Belia and Andrea, because all their support is essential for the development of
mathematics in Querétaro.
To other friends: Abi, Jorge Garza, Gogo, Ian, Alex, Paco, Daniel, Mart́ın, Sashi,
Andrea, Adriana, Pit, Memo, Alf, Sara, Luis Pedro. Each one of you is an example that
the path through life is filled with marvelous people.
To Javier Bracho and Gerónimo Uribe, members of the thesis committee. At the be-
ginning of my doctoral studies Gerónimo told me that studying a PhD was like swimming
in the ocean looking for an island. It was an excellent metaphor. I hope that he enjoys
this archipelago that we have found. Javier Bracho was my undergraduate advisor. I
have had some conversations with him about mathematics and a few about life.
To Angélica, Lucy, Mary and Tere from Posgrado en Ciencias Matemáticas, who year
after year give their best effort so that the paperwork in the office is as efficient as possible.
To Lourdes Esteva and Silvia Ruiz who have both been coordinators of the Posgrado.
To Catalina Stern, Manuel Falconi, Rosaura Ruiz for giving me their trust and support
for creating and developing a project in problem-solving and participation in international
mathematics competitions for university students. To Alma Rosa, Concha Ruiz, Ruth,
Elena, Alicia, Angélica, Raúl for the support to make it possible. We have achieved great
goals in these past few years.
Of course, studying this PhD would not have been possible without going through
a previous stage. For this reason, I would like to reiterate my thanks to all those who
appear in the corresponding section in my undergraduate thesis.
Financial support
The work for this dissertation has been possible thanks to the generous support of various
projects and institutions.
The main support has been given by CONACyT grant (beca CONACyT) 277462. The
academic interchange between UNAM and Université de Montpellier has been possible
thanks to the joint program ECOS-CONACyT-ANUIES, with reference numbers M13M01
and 229515.
Additional support for traveling and for presenting the work in various venues has been
provided by CONACyT project 166036, Kaleidoscope, LAGOS (2013, 2015), Coloquio
Vı́ctor Neumann-Lara de teoŕıa de gráficas y sus aplicaciones (2013, 2014, 2015), CIMAT,
UAEH, UMSNH, Sociedad Matemática Mexicana, Instituto de Matemáticas (UNAM),
Posgrado en Ciencias Matemáticas (UNAM).
Introducción
La geometŕıa combinatoria es una rama amplia y bella de las matemáticas. Esta tesis de
doctorado está conformada por el estudio de cinco temas diferentes en esta área. Aunque
los problemas y las herramientas que se usan para lidiar con ellos son diversos, comparten
una meta que los une:
Explorar la interacción entre estructuras combinatorias y geométricas
Los resultados de estas exploraciones pueden encontrarse en los caṕıtulos del 1 al 5.
Cada uno de éstos puede leerse de manera independiente. Al inicio de cada tema se
presentan algunas palabras para motivar el problema, su relación con la investigación
clásica y actual, los coautores con los que se trabajó y dónde se han presentado los
resultados. Posteriormente en cada caṕıtulo se encuentra el contenido principal de cada
contribución.
A lo largo de la exposición asumiremos familiaridad con las definiciones y resultados
básicos en teoŕıa de gráficas, geometŕıa convexa, teoŕıa de matroides y matroides orienta-
dos, geometŕıa algebraica y homoloǵıa. Sin embargo, como referencia, la mayor parte de
esta teoŕıa básica se puede encontrar en el apéndice.
Sumario
En el Caṕıtulo 1 estudiamos un problema de Paul Erdős: para un entero positivo k,
¿cuántos puntos en posición general necesitamos en el plano para que siempre podamos
encontrar k de ellos que definan triángulos con circunradios distintos? Esta pregunta fue
hecha en 1975 y Erdős mismo propuso una solución en 1978. Sin embargo, la prueba
dejó fuera de manera no intencional un caso no trivial. Lidiamos con este caso usando
herramientas básicas de geometŕıa algebraica y damos una cota polinomial para el número
necesario de puntos.
11
12 CONTENTS
Los caṕıtulos 2 y 3 comparten un tema en común: ¿qué tipos de resultados podemos
obtener cuando ponemos teoremas clásicos de teoŕıa de gráficas en contextos geométricos?
En ambos casos la respuesta es provechosa.
Espećıficamente, en el Caṕıtulo 2 estamos interesados en dar extensiones geométricas
del criterio de Hall para emparejamientos en gráficas bipartitas (1935). Obtenemos teo-
remas tipo Hall para convexos disjuntos y para puntos en posición general en el espacio
euclideano. Las herramientas de este caṕıtulo son topológicas y están motivadas por el
notable método que introdujeron Aharoni y Haxell en 2000 y en sus generalizaciones.
Por otro lado, en el Caṕıtulo 3 comenzamos con un teorema de Helly fraccional de
1979 de A. Liu y M. Katchalski para motivar un resultado combinatorio. Exploramos
condiciones combinatorias que debe tener una familia de gráficas que nos permitan obtener
versiones refinadas del teorema de Turán. Encontramos relaciones interesantes entre los
números de Turán, los números cromáticos y los números de clan de la familia. Las
herramientas usadas son únicamente combinatorias.
Los caṕıtulos 4 y 5 están relacionados con teoŕıa de matroides y de matroides orientados
respectivamente. En el Caṕıtulo 4 nos enfocamos en obtener algunos resultados para la
bien conocida clase de matroides de caminos latices introducida por Bonin, de Mier y Noy
en 2003. La principal contribución es probar que para esta clase se satisface una conjetura
de 1999 hecha por Merino y Welsh con respecto a una desigualdad que involucra algunos
valores del polinomio de Tutte. Para hacer est, introducimos el concepto de serpientes,
una clase especial de matroides de caminos latices “flacos”.
Finalmente, en el Caṕıtulo 5 exploramos una variante de un problema de transversales
propuesto por J.L. Arocha, J. Bracho, L. Montejano y J.L Ramı́rez-Alfonśın en 2010. En
su trabajo original, ellos se
Agradecimientos
Este camino por el doctorado ha sido posible gracias al apoyo de mucha gente. Me gustaŕıa
agradecerles.
A mis padres, Perla Sandoval e Ignacio Mart́ınez, quienes me dieron la vida y nos
han dado todo su apoyo en el transcurso de ella a mi hermano y a mi. Con la vida
interactuamos con lo que generaciones pasadas nos han dejado y con ella también dejamos
cosas valiosas a las generaciones que están por venir.
A mi hermano, Emilio Mart́ınez, compañero en la familia y la ciencia, con quien no sólo
comparto el humor, sino también el apetito de conocimiento. Él me ha dado abundantes
consejos en productividad, salud, deporte, música y otras varias áreas complementarias
CONTENTS 13
más.
Al resto de mi familia que de distintas formas me ha apoyado en este camino por las
matemáticas.
A mis asesores de tesis: Luis Montejano Peimbert y Jorge Ramı́rez Alfonśın.
Luis Montejano afirma que para cualquier proceso creativo (como el de las matemáticas)
se necesita libertad, valent́ıa e ingenuidad. Siendo consistente a estos principios, me otorgó
abundante libertad durante todo el doctorado, acompañada de una buena orientación. Me
ha dado su apoyo en varios proyectos que he emprendido por decisión propia y también
me ha animado a participar en otros más.
Jorge Ramı́rez fue un actor clave en la interacción con la Université de Montpellier.
Me apoyó en todos los aspectos para poder realizar el doctorado en convenio de cotutela
con Francia: matemáticas, hospedaje, trámites, idioma, etc.
A Norma Morales, por acompañarme en una gran parte de esta aventura. Me siento
afortunado por el apoyo mutuo, la confianza y el cariño que hemos desarrollado.
A Lalo, por ser un compañero constante en las matemáticas y en los proyectos adi-
cionales. Por las varias conversaciones que hemos tenido, por sus consejos y su punto de
vista. A Edgardo Roldán, por compartir mucha de su experiencia matemática conmigo.
A Fernando Campos con quien, aunque estos años nuestros rumbos profesionales nos han
separado, sigue habiendo lazos estrechos formados durante la licenciatura. A Maŕıa José
Gutiérrez, con quien existen también lazos similares desde la secundaria y con quien puedo
platicar de una infinidad de temas.
A la Olimpiada Mexicana de Matemáticas y varias personas involucradas con ella.
Sobre todo a Toño, quien en estos años me ha invitado a su equipo de trabajo para
promover las matemáticas en el páıs y quien me ha dado la confianza de asistir a la
Olimpiada Internacional de Matemáticas como el ĺıder del equipo mexicano. A Jesús
Jerónimo por presentarme la geometŕıa combinatoria. A Malú, Luis Miguel, Miguel Raggi,
Marco, David Torres, José Luis Campos, Irving, Hugo, Daniel, Rogelio, Mila, David
Cosśıo, Nacho, Héctor, Chino, Eugenio, Fernanda, Rita. He aprendido mucho de todos
ustedes.
A los alumnos de la Olimpiada que he entrenado, a través de quienes también he
aprendido bastante. Principalmente a Diego Roque, Juan Ortiz y Adán Medrano.
A los matemáticos de la Unidad Juriquilla del Instituto de Matemáticas: Déborah,
Gaby, Adriana, Amanda, Liz, Mirna, Maribel, Nancy, Jendry, Adolfo, Gerardo, Juan
Carlos, Gabriel, Isaac, Adrián, Alejandro, Jorge. Realmente en estos años me he sentido
parte de una comunidad fuerte y de un proyecto en crecimiento. Este también es el
párrafo correcto para agradecer a Natalia Garćıa por ser una buena amiga y “hermana
14 CONTENTS
mayor”. Por compartirme de su experiencia en matemáticas financieras al inicio de mi
doctorado. A Lucha, Araceli, Belia y Andrea quienes su apoyo para que las matemáticas
sigan creciendo en Querétaro es fundamental.
A varios amigos más: Abi, Jorge Garza, Gogo, Ian, Alex, Paco, Daniel, Mart́ın, Sashi,
Andrea, Adriana, Pit, Memo, Alf, Sara, Luis Pedro. Todos ustedes son ejemplo de que el
camino por la vida está plagado de gente magńıfica.
A Javier Bracho y Gerónimo Uribe, miembros del Comité Tutor. Al inicio del doc-
torado Gerónimo me dijo que estudiar un doctorado era como nadar en el mar buscando
una isla. Fue una metáfora excelente. Espero que disfrute de este archipiélago que hemos
encontrado. Javier Bracho fue mi asesor de tesis de licenciatura y he tenido distintas
conversaciones matemáticas y algunas de la vida con él.
A Angélica, Lucy, Mary y Tere de la oficina del Posgrado en Ciencias Matemáticas,
quien año tras año dan su mejor esfuerzo para que los distintos trámites se lleven a cabo
de manera ágil. A Lourdes Esteva y Silvia Ruiz, ambas coordinadoras del programa.
A Catalina Stern, Manuel Falconi, Rosaura Ruiz por brindarme la confianza y el apoyo
para llevar a cabo un proyecto de resolución de problemas y participación en competencias
universitarias de matemáticas. A Alma Rosa, Concha Ruiz, Ruth, Elena, Alicia, Angélica,
Raúl por el apoyo para llevarlo a cabo. Hemos logrado mucho en estos años.
Por supuesto, el doctorado no hubiera sido posible sin pasar por la etapa anterior. Por
esta razón, me gustaŕıa reiterar mi agradecimiento a todos aquellos que aparecen en la
sección correspondiente en mi tesis de licenciatura.
Apoyo financiero
El trabajo contenido en este manuscrito ha sido posible gracias al apoyo generoso de
numerosos proyectos e instituciones.
El apoyo principal fue dado por CONACyT a través de la beca para estudios de
posgrado número 277462. El intercambio académico entre la UNAM y la Université
de Montpellier fue posible gracias al convenio conjunto ECOS-CONACyT-ANUIES con
números de referencia M13M01 y 229515.
El apoyo adicional para viajar y presentar el trabajo en varios foros ha sido otorgado
por el proyecto 166036 de CONACyT, Kaleidoscope, LAGOS (2013, 2015), Coloquio
Vı́ctor Neumann-Lara de teoŕıa de gráficas y sus aplicaciones (2013, 2014, 2015), CIMAT,
UAEH, UMSNH, Sociedad Matemática Mexicana, Instituto de Matemáticas (UNAM),
Posgrado en Ciencias Matemáticas (UNAM).
Introduction (Français)
La géométrie combinatoire est une large et belle branche des mathématiques. Cette thèse
doctorale se compose de l’étude de cinq sujets différents dans ce domaine. Même si les
problèmes et les techniques utilisés pour y faire face sont divers, ils partagent le même
objectif:
Étudier l’interaction entre les structures combinatoires et géométriques
Les résultats de ces recherches peuvent être trouvées dans les chapitres 1 à 5. Chacun
d’entre eux peut être lu indépendamment. Au début de chaque sujet, nous fournissons
quelques mots sur la motivation, sa relation avec des recherches connues et actuelles, les
co-auteurs avec lesquels le travail a été effectué et où les résultats sont soumis ou publiés.
Tout au long de l’exposé, nous supposerons que le lecteur est familier avec les définitions
et les résultats de base sur les sujets suivants: la théorie des graphes, la géométrie convexe,
la théorie des matröıdes et des matröıdes orientés, la géométrie algébrique et l’homologie.
Néanmoins, la plupart des théories de base figure dans l’annexe.
Résumé
Dans le chapitre 1, nous étudions le problème suivant : pour un entier positif k, combien
de points en position générale devons-nous prendre dans le plan de sorte que nous pouvons
toujours trouver k d’entre eux définissant des triangles avec un rayon du cercle circonscrit
distinct ? Cette question a été posée par Paul Erdős en 1975 qui a lui même proposé une
solution en 1978. Toutefois, la preuve a omis par inadvertance un cas non trivial. Nous
avons repris ce cas et donné une solution à la question en utilisant des outils de base de la
géométrie algébrique et nous fournissons une borne polynomiale pour le nombre de points
nécessaires.
Les chapitres 2 et 3 ont un sujet en commun : quel genre de résultats pouvons-nous
15
16 CONTENTS
obtenir lorsque nous plaçons des théorèmes classiques de la théorie des graphes dans des
contextes géométriques? Dans les deux cas, la réponse est fructueuse.
Plus précisément, dans le chapitre 2, nous sommes intéressés par de généralisations
géométriques du critère de Hall pour les couplages dans les graphes bipartits (1935). Nous
obtenons des théorèmes géométriques type Hall pour des ensembles convexes disjoints
et pour points en position générale dans l’espace euclidien. Les outils de ce chapitre
sont topologiques, et l’approche est motivés par une méthode remarquable introduite par
Aharoni et Haxell en 2000 ainsi que par ses généralisations.
D’autre part, dans le chapitre 3, nous commençons par un théorème de Helly fractionné
de 1979 due à A. Liu et M. Katchalski pour motiver un résultat combinatoire. Nous
étudions des conditions combinatoires que des familles de graphes doivent avoir pour
permettre d’obtenir des versions plus fine du théorème de Turán. Nous trouvons des
liens intéressants entre les nombres de Turán, les nombres chromatiques et les nombres
de clique dans la famille. Les outils de ce chapitre sont purement combinatoires.
Les chapitres 4 et 5 sont respectivement liés à la théorie des matröıdes et des matröıdes
orientés. Dans le chapitre 4, nous nous concentrons sur l’obtention des résultats pour la
bien connue classe des matröıde chemin du réseau introduite par Bonin, de Mier et Noy
en 2003. La contribution principale est de prouver pour cette classe la validité d’une
conjecture de Merino et Welsh (1999) sur une inégalité de certaines valeurs du polynôme
de Tutte. Pour ce faire, nous introduisons et étudions des serpents, une classe spéciale de
matröıdes chemin du réseau “mince”.
Enfin, dans le chapitre 5, nous étudions une variante d’un problème des transversales
posé par J.L. Arocha, J. Bracho, L. Montejano et J.L. Ramı́rez-Alfonśın en 2010. Dans
leur travaux originaux, ils ont rémarqué que si nous avons peu de points dans l’espace
euclidien alors il est possible de trouver une transversale d’une dimension donnée qui
travers les enveloppes convexes de tous les k-ensembles de points. De même, ils montrent
qu’il est impossible de trouver une telle transversale lorsque nous avons beaucoup de
points. Les auteurs donnent des bornes spécifiques et ils laissent aussi quelques problèmes
ouverts. Si la définition de transversale est légèrement plus restrictive, alors le problème
peut être étudié en utilisant la théorie des matröıdes orientés. Dans la présente thèse,
nous fournissons les détails de cette relation et nous donnons des bornes pour la famille
de polytopes cycliques.
Remerciements
Ce travail a èté réalisé grâce à l’appui de divers personnes qui je souhaite vivement re-
mercier.
CONTENTS 17
À mes parents, Perla Sandoval et Ignacio Mart́ınez, qui m’ont donné la vie et qui nous
ont toujours soutenus, mon frére et moi. Grâce à la vie nous interagissons avec tout ce que
les générations passées ont laissé et nous pouvons également laisser des traces précieuses
pour les générations futures.
À mon frère Emilio Mart́ınez, un partenaire dans la familie et dans la science, avec
qui je partage à la fois l’humour et la soif de connaissance. Il m’a donné de nombreux
conseils sur la productivité, la santé, le sport, la musique et bien d’autres sujets.
Aux autres membres de ma famille qui m’ont soutenu de diverses manières au cours
de mon parcours en mathématiques.
À mes directeurs de thèse : Luis Montejano Peimbert et Jorge Ramı́rez Alfonśın.
Luis Montejano affirme que pour tout processus créatif (comme celui des mathématiques),
il est nécessaire d’avoir la liberté, du courage et de la näıveté. En étant cohérent avec
ces principes, il m’a donné une bonne quantité de liberté avec une bonne quantité de
conseils. Il m’a donné son appui pour démarrer différents projets et il m’a également
invité à participer à quelques autres.
Jorge Ramı́rez a joué un rôle clé dans l’interaction avec l’Université de Montpel-
lier. Il m’a aidé dans tous les aspects pour rendre possible l’accord avec la France: les
mathématiques, l’hébergement, les démarches administratives, la langue, etc.
À Norma Morales, pour m’accompagner dans une grande partie de cette aventure.
Je me sens chanceux pour l’aide mutuelle, la confiance et l’affection que nous avons
développées.
À Lalo, pour être un partenaire constant en mathématiques et dans divers autres
projets. Pour les différentes conversations que nous avons eues, pour ses conseils et son
point de vue. À Edgardo Roldán, pour partager avec moi beaucoup de son expérience
mathématique. À Fernando Campos avec qui, même si nos parcours professionnels nous
ont séparé, il existe toujours une amitié proche depuis nos études universitaires. À Maŕıa
José, avec qui une amitié proche existe depuis l’école secondaire et avec laquelle je peux
parler de nombreux sujets différents.
À l’Olimpiada Mexicana de Matemáticas et de nombreuses personnes impliquées dans
son organization. Spécialement à Toño qui m’a invité ces années à faire partie de son
équipe pour promouvoir les mathématiques au Mexique et qui m’a accordé sa confiance
pour être le leader de l’équipe mexicaine pour l’Olympiade Internationale de Mathématiques.
À Jesús Jerónimo, pour son introduction à la géométrie combinatoire. À Malú, Luis
Miguel, Miguel Raggi, Marco, David Torres, José Luis Campos, Irving, Hugo, Daniel,
Rogelio, Mila, David Cosśıo, Nacho, Héctor, Chino, Eugenio, Fernanda, Rita. J’ai beau-
coup appris de vous tous.
18 CONTENTS
Pour les élèves de l’Olympiade que j’ai formés. J’ai également beaucoup appris de
vous. Spécialement de Diego Roque, Juan Ortiz et Adán Medrano.
Aux mathématiciens de Unidad Juriquilla del Instituto de Matemáticas: Déborah,
Gaby, Adriana, Amanda, Liz, Mirna, Maribel, Nancy, Jendry, Adolfo, Gerardo, Juan
Carlos, Gabriel, Isaac, Adrián, Alejandro, Jorge. Ces années je me suis senti intégré dans
une communauté solide et dans un projet en croissance. Sans oublier Natalia Garćıa qui
je remercie pour son amitié et pour partager son expérience en finance mathématique avec
moi au début de mes études supérieures. À Lucha, Araceli, Belia et Andrea, parce que
tout leur travail est essentiel pour le développement des mathématiques à Querétaro.
À d’autres amis: Abi, Jorge Garza, Gogo, Ian, Alex, Paco, Daniel, Mart́ın, Sashi,
Andrea, Adriana, Pit, Memo, Alf, Sara, Luis Pedro. Chacun de vous est un exemple que
le chemin de la vie est parsemé de gens merveilleux.
À Javier Bracho et Gerónimo Uribe, membres du comité de thèse. Au début de mes
études de doctorales, Gerónimo m’a dit que faire un doctorat était comme nager dans
l’océan à la recherche d’une ı̂le. Ce fut une métaphore excellente. Je souhaite qu’il aime
cet archipel que nous avons trouvé. Javier Bracho était mon conseiller de mes études
universitaires. J’ai eu quelques conversations avec lui à propos des mathématiques et
quelques-unes sur la vie.
À Angélica, Lucy, Mary et Tere du bureau du Posgrado en Ciencias Matemáticas, qui
ont fait, année après année, de leur mieux pour que les démarches administratives soient
le plus efficace possible. À Lourdes Esteva et Silvia Ruiz, qui ont toutes deux été les
coordinatrices du Posgrado.
À Catalina Stern, Manuel Falconi, Rosaura Ruiz pour me donner leur confiance et
soutien pour créer et développer un projet de résolution de problèmes et de participation
à des compétitions internationales de mathématiques pour les étudiants universitaires. À
Alma Rosa, Concha Ruiz, Ruth, Elena, Alicia, Angélica, Raúl pour leur aide afin de le
rendre possible. Nous avons réalisé de grands objectifs dans ces quelques dernières années.
Bien sûr, l’étude de ce doctorat n’aurait pas été possible sans passer par une étape
précédente. Pour cette raison, je voudrais réitérer mes remerciements à tous ceux qui
apparaissent dans les remerciements de ma thèse de Licence.
Aide financière
Le travail de cette thèse a été possible grâce au généreux soutien de divers projets et
institutions.
CONTENTS 19
Le soutien principal a été donné par CONACyT subvention 277462. L’interaction
entre l’UNAM et l’Université de Montpellier a été possible grâce au programme ECOS-
CONACyT-ANUIES, avec les numéros de référence M13M01 et 229515.
Un soutien supplémentaire pour voyager et pour présenter le travail dans divers lieux a
été fourni par le project CONACyT 166036, Kaleidoscope, LAGOS (2013, 2015), Coloquio
Vı́ctor Neumann-Lara de teoŕıa de gráficas y sus aplicaciones (2013, 2014, 2015), CIMAT,
UAEH, UMSNH, Sociedad Matemática Mexicana, Instituto de Matemáticas (UNAM),
Posgrado en Ciencias Matemáticas (UNAM).
Chapter 1
Points defining triangles with
distinct circumradii
In this chapter we study a problem posed by Paul Erdős concerning sets of points that
define triangles with distinct circumradii. Erdős solved the problem himself, however, in
his solution he inadvertently left out a non-trivial case. In this Chapter we present a way
to complete the proof.
We use Bézout’s theorem on the intersection of two algebraic curves. It is a joint
work with Edgardo Roldán Pensado. The presentation is strongly based on the paper [49]
published in Acta Mathematica Hungarica.
1.1 Introduction
In 1975 [29], inspired by the observations from Esther Szekeres and his results with George
Szekeres, Paul Erdős posed the following problem:
Problem 1.1. Is it true that for every k there is an nk such that if there are given nk
points in the plane in general position (i.e. no three on a line no four on a circle) one
can always find k of them so that all the
(
k
3
)
triples determine circles of distinct radii?
This problem is similar to the Erdős-Szekeres Theorems [27]. As is the case with these
theorems, the existence of nk can be established using Ramsey Theory if the existence
of n6 can be verified. To do this, consider the Ramsey number R(k, n6; 6) and take this
number of points in the plane in general position. Color a 6-tuple of points green if
all 20 triangles determined by these points have distinct circumradii and red otherwise.
Then Ramsey’s Theorem [61] gives us either a subset with n6 elements such that all 6-
21
22CHAPTER 1. POINTS DEFINING TRIANGLESWITH DISTINCT CIRCUMRADII
tuples are red or a subset with k elements such that all 6-tuples are green. The first
option is impossible by the definition of n6 and the second one implies that the k points
determine triangles with distinct circumradii. However, establishing the existence of n6 is
not completely trivial and the bound obtained from this method is an exponential tower.
Three years later, in 1978, Erdős published a paper [30] where he claimed a positive
answer to the question with nk ≤ 2
(
k−1
2
)(
k−1
3
)
+ k. However, he inadvertently left out
a non-trivial case for which his method does not work. It seems that Erdős remained
unaware of this and even restated the result in 1985 [31] giving partial credit to E. Straus.
In this chapter we address this issue and give a polynomial bound for nk.
Theorem 1.1. Let k be a positive integer and let nk be the smallest integer such that the
following holds: For any nk points in the plane in general position (i.e. no four on a line
or circle) there are k of them so that all their triples determine circles of distinct radii.
Then nk = O(k9).
We prove this in Section 1.4. Note that we redefined nk and changed the general
position condition to what we think is a more suitable one, since a line is just a circle of
infinite radius. In Section 1.2 we examine Erdős’ argument. The proof of Theorem 1.1 is
based on a very similar method but slightly more involved.
In Section 1.3 we analyze nk for k = 4, 5 and give explicit bounds for them. These are
used in the proof of 1.1. To be precise we prove the following.
Theorem 1.2. The first two non-trivial values of nk satisfy n4 ≤ 9 and n5 ≤ 37.
Before we continue, we fix some notation to be used throughout the paper. If F
is a set,
(
F
m
)
denotes the set of unordered m-tulpes of F . Given points A,B,C in the
plane, |AB| is the length of the segment AB, |ABC| is the area of the triangle ABC and
R(ABC) is the circumradius of the triangle ABC.
1.2 Erdős argument
Now we look at the argument from [30], in which Erdős claims nk ≤ k +
(
k−1
2
)(
k−1
3
)
.
Erdős’ argument. We start with a set F of n ≥ k +
(
k−1
2
)(
k−1
3
)
points in the plane in
general position and chooses a maximal set G ⊂ F so that all the triples in
(
G
3
)
determine
circles of distinct radii. Let l = |G| and assume that l < k. Denote the circumradii by
r1, . . . , r(l3)
1.3. SMALL CASES 23
Since G is maximal, every point of F \ G must lie in a circle of radius ri through two
points of G. But because the points are in general position, there can be at most one
point in such a circle. Note that there are
(
l
3
)
radii,
(
l
2
)
pairs of points, and at most
two circles of a certain radius through two points. Therefore n − l ≤ 2
(
l
3
)(
l
2
)
, which is a
contradiction.
There is a problem here. Namely, that a point of F \ G must not necessarily be
in one of the circles described above. For example, a point X ∈ F \ G could satisfy
R(ABX) = R(CDX), with A,B,C,D ∈ F , without being in any of the circles described
above and not contradict the maximality of G. To fix the gap in this argument, we give
a polynomial bound for the number of such points X.
1.3 Small cases
Here we show that nk is bounded for k ≤ 5, as we need this for the general case. The proofs
are mostly combinatorial. In fact the only geometric property we use is the following: if
3 triangles have the same circumradius and share an edge, then 4 of their vertices lie on
a circle.
Proof of first part of Theorem 1.2. Assume we have a set F of 9 points in general position
and among every 4 of them there are two triangles with equal circumradius. Then to every
G ⊂ F consisting of 4 points we can assign two pairs of points, say f(G) = {A,B} ⊂ G
and g(G) = {C,D} ⊂ G, such that R(ABC) = R(ABD). These are functions f, g :
(
F
4
)
→
(
F
2
)
. Here f(G) are the points that form the common base of the triangles with
equal circumradius in G and g(G) are the other two vertices.
There are 126 sets of 4 points and only 36 pairs of points, therefore there is a pair
of points, say {A,B}, such that f−1({A,B}) has at least 4 elements. Since there are
only 7 points in F \ {A,B}, there are G1,G2 ∈ f−1({A,B}) such that g(G1) ∩ g(G2) 6= ∅.
Assume that G1 = {A,B,C,D} and G2 = {A,B,C,E}, then R(ABC) = R(ABD) =
R(ABE). But this implies that 4 points lie in some circle, contradicting the general
position assumption.
Proof of second part of Theorem 1.2. Assume we have a set F of 37 points and in ev-
ery set G ⊂ F of 5 points there are two triangles with equal circumradius. These
two triangles must have a vertex in common, let f(G) = A be this vertex and let
g(G) = {{B,C}, {D,E}} ⊂
(
G
2
)
be the other vertices of the triangles so that R(ABC) =
R(ADE).
24CHAPTER 1. POINTS DEFINING TRIANGLESWITH DISTINCT CIRCUMRADII
Since there are only 37 points, there is a point A assigned by f to 1
37
(
37
5
)
of the 5-tuples.
These 5-tuples are mapped by g into a total of 2
37
(
37
5
)
pairs of points in G so there is a
pair, say {B,C}, in
⌈
2
37
(
37
5
)
/
(
37
2
)⌉
= 36 of them.
Now consider the 5-tuples G such that {B,C} ∈ g−1(G), and for each of these take the
other pair {DG, EG} ∈ g−1(G). Note that R(ADGEG) = R(ABC) for all such G, giving
a total of 37 triangles with equal circumradius and a common vertex A. Since there are
only 36 points in F \ {A}, there must be another point belonging to 3 of these triangles.
But these three triangles have an edge in common, therefore 4 of their vertices lie in a
circle contradicting the general position assumption.
1.4 General case
Here we prove Theorem 1.1, but we need some additional definitions and lemmas.
Consider {A,B} and {C,D} two different pairs of points on the plane. We are inter-
ested in the locus of the points X such that R(ABX) = R(CDX), which we denote by
C(AB,CD). Since the circumradius of a triangle satisfies
R(ABX) =
|AX| |BX| |AB|
4 |ABX| ,
C(AB,CD) is the algebraic curve of degree at most 6 defined by the zero set of
|AX|2 |BX|2 |AB|2 |CDX|2 − |CX|2 |DX|2 |CD|2 |ABX|2 .
Now assume we have a set F of n points in general position, let G be a maximal subset
of those points such that all its triples determine circles of distinct radii and set l = |G|.
Since G is maximal, each of the remaining n − l points must lie on one of the following
curves.
1. A circle through 2 points of G with radius ri for some i.
2. The curve C(AB,CD) with {A,B} and {C,D} distinct pairs of points of G.
Our goal is to bound the number of points in F \ G, but first we address a particular
case of our main theorem.
Lemma 1.1. Let D be an irreducible algebraic curve of degree at most 6. Then for every
integer k there exists an integer mk = O(k5) such that the following holds: every set
F ⊂ D with mk points in general position contains a subset G with k points such that all
its triples determine circles of distinct radii.
1.4. GENERAL CASE 25
Proof. Take m points in general position on D, let G be a maximal set of these points
such that all its triples determine circles of distinct radii and let l = |G|. By Theorem 1.2
we may assume l ≥ 5.
Each of the remaining m− l points must lie on one of the two curves described above.
In Case (1), we use Erdős’ argument: there are
(
l
3
)
possible radii,
(
l
2
)
possible pairs
and since the points are in general position, there are at most two points for each radius
and each pair. This bounds above the number of points in Case (1) by 2
(
l
2
)(
l
3
)
.
In Case (2), there are 1
2
(
l
2
)
(
(
l
2
)
−1) ways to choose the pairs {A,B} and {C,D}. Con-
sider the curve C(AB,CD), by Bézout’s Theorem [23], either D is an irreducible compo-
nent of C(AB,CD) or D∩C(AB,CD) contains at most 36 points. But if D ⊂ C(AB,CD),
then G = {A,B} ∪ {C,D} because any other point of G would lie on C(AB,CD) and
thus repeat a radius. This contradicts l ≥ 5. Therefore D ∩ C(AB,CD) has at most 36
points. This bounds above the number of points in Case (2) by 36
2
(
l
2
)
(
(
l
2
)
− 1).
So the number of points in F \ G is
m− l ≤ 2
(
l
2
)(
l
3
)
+ 36
(( l
2
)
2
)
,
from which the desired bound follows.
Now the proof of Theorem 1.1 is straightforward.
Proof of Theorem 1.1. Once again, assume F has n points and l is the size of the maximal
G ⊂ F with all its triples having distinct circumradii. For the remaining n− l points we
have the same two cases.
We can bound the number of points in Case (1) by 2
(
l
2
)(
l
3
)
. For Case (2) we use
Lemma 1.1 to obtain a bound of 1
2
(
l
2
)
(
(
l
2
)
− 1)ml. This gives
n− l ≤ 2
(
l
2
)(
l
3
)
+
(( l
2
)
2
)
ml,
which implies that nk = O(k9).
Chapter 2
Geometric Hall-type theorems
Hall’s criterion for matchings in bipartite graphs can be thought as a result on systems
of distinct representatives for a family of sets. We can ask for geometric generalizations
of this theorem when we have sets of geometric objects and we change the property of
being distinct to a more geometric one like “being in general position” or “being pairwise
disjoint”.
In this chapter we present works in two directions. In Sections 2.1 to 2.5 we provide
a condition for finding a system of general position representatives. This is a joint work
with Andreas F. Holmsen and Luis Montejano Peimbert. The content of these sections is
strongly based on the paper [38] published in Proceedings of the American Mathematical
Society.
In Section 2.6 we state a Hall-type theorem to find a system of independent represen-
tatives in a graph. We get as a geometric corollary a criterion to find pairwise-disjoint
representatives of a family of unit balls in euclidean space. In Section 2.7 we prove the
theorem using Sperner’s lemma. This is a joint work with Luis Montejano Peimbert. The
content of these sections was presented in the VII Latin-American Algorithms, Graphs
and Optimization Symposium (LAGOS 2013), and it is essentially an adaptation of the
extended abstract [48] presented for the conference.
2.1 Introduction
2.1.1 Background
Let F = {S1, . . . , Sm} be a family of finite subsets of a common ground set E. A system
of distinct representatives is an m-element subset {x1, . . . , xm} ⊂ E such that xi ∈ Si for
27
28 CHAPTER 2. GEOMETRIC HALL-TYPE THEOREMS
all 1 ≤ i ≤ m. A classical result in combinatorics is Hall’s marriage theorem [34] which
states that a family F = {S1, . . . , Sm} has a system of distinct representatives if and only
if
∣
∣
⋃
i∈I Si
∣
∣ ≥ |I| for every non-empty subset I ⊂ {1, . . . ,m}.
In 2000, Aharoni and Haxell [6] presented a remarkable generalization of Hall’s theo-
rem. Let F = {H1, . . . , Hm} be a family of hypergraphs on a common vertex set V . A
system of disjoint representatives is an m-element set {E1, . . . , Em} of pairwise (vertex)
disjoint edges such that Ei ∈ Hi for all 1 ≤ i ≤ m. The Aharoni and Haxell result gives
a sufficient condition for a family of hypergraphs to have a system of disjoint representa-
tives, and their result reduces to the Hall’s theorem in the case when the Hi are 1-uniform
hypergraphs. Their result was used to prove Ryser’s conjecture for 3-uniform hypergraphs
[1], but perhaps more importantly, their proof introduced topological techniques into this
classical branch of combinatorics. The connections with topological combinatorics were
further investigated and generalized in [2], [4], [3], [5], [36], [39], [53], [54].
2.1.2 Our result
The purpose of this paper is to introduce a discrete geometric generalization of Hall’s
marriage theorem. We say that a subset X ⊂ Rd is in general position if every subset of
size at most d + 1 is affinely independent. Let F = {X1, . . . , Xm} be a family of finite
sets in Rd. A system of general position representatives is a subset {x1, . . . , xm} in general
position such that xi ∈ Xi for all 1 ≤ i ≤ m. For a finite set X ⊂ Rd let ϕ(X) denote the
maximal size of a subset of X in general position. We have the following.
Theorem 2.1. For every integer d ≥ 1 there exists a function fd : N → N such that the
following holds. Let F = {X1, . . . , Xm} be a family of finite sets in Rd. If
ϕ
(
⋃
i∈I
Xi
)
≥ fd(|I|)
for every non-empty subset I ⊂ {1, . . . ,m}, then F has a system of general position
representatives.
Notice that for d = 1, a set is in general position if its elements are pairwise distinct.
Therefore we can set f1(k) = k, in which case Theorem 2.1 reduces to Hall’s theorem.
Once the existence of the functions fd(k) has been established, a natural goal is to
obtain good general upper bounds on these functions. In general we are interested in
asymptotic bounds, that is, when d is fixed and the number of sets in the family F grows.
Let us illustrate how the the size of F = {X1, . . . , Xm} plays a role. Supposem ≤ d+1.
We claim that if ϕ
(⋃
i∈I Xi
)
≥ |I| for every non-empty subset I ⊂ {1, . . . ,m}, then F
2.1. INTRODUCTION 29
has a system of general position representatives (which is the same condition as in Hall’s
theorem). This follows from the matroid intersection theorem due to Edmonds [26]. To
see this, let the ground set be the disjoint union E = X1∪̇ · · · ∪̇Xm. (We allow for the
same point to appear in several Xi, but we keep track of its multiplicity.) Let M1 be the
matroid on E whose independent sets are the affinely independent subsets, and let M2
be the partition matroid induced by X1, . . . , Xm. Let r1 and r2 be the respective rank
functions. Given a subset S ⊂ E, let I ⊂ {1, . . . ,m} be the maximal subset such that
⋃
i∈I Xi ⊂ S. We then have r1(S) ≥ r1
(⋃
i∈I Xi
)
and r2(E − S) ≥ m− |I|. The matroid
intersection theorem implies that F has a system of general position representatives if
r1(S) ≥ |I| for every non-empty subset S ⊂ E. This inequality holds by our hypothesis
since r1(S) = min{d+ 1, ϕ(S)} ≥ min{d+ 1, ϕ
(⋃
i∈I Xi
)
} ≥ |I|.
It is also easily seen that when m > d + 1, the condition ϕ
(⋃
i∈I Xi
)
≥ |I| is not
sufficient to guarantee a system of general position representatives. Suppose |X1| = · · ·
= |Xm−1| = 1 and that
⋃m−1
i=1 Xi is in general position in Rd. From every hyperplane
spanned by a d-tuple from
⋃m−1
i=1 Xi choose an additional point, at random, to be included
in the set Xm. Thus Xm consists of
(
m−1
d
)
points in general position. For every non-empty
subset I ⊂ {1, . . . ,m} we have ϕ
(⋃
i∈I Xi
)
≥ |I|, but F has no system of general position
representatives.
2.1.3 Outline of paper
We will present two proofs for the existence of the functions fd(k). The first proof uses
an elementary pigeon-hole argument and gives an upper bound in O(kd+1). This is given
in Section 2.2. Our second proof uses more sophisticated techniques and gives an upper
bound in O(kd). This is given in Section 2.3, while the main auxiliary result (Theorem 2.3)
is proved in Section 2.4. We do not know if this bound is optimal, and it is an interesting
problem to determine better bounds on fd(k). The reader familiar with matroids will
notice that many of our arguments rely on properties of the underlying matroid of the
point set. This leads to generalizations of our results which will be discussed further in
Section 2.5. (All matroids arising in our setting are loopless, so this will be implicitly
assumed throughout.)
Just as the seminal result of Aharoni and Haxell, our second proof of Theorem 2.1 relies
on topological methods, and we assume the reader is familiar with some basic notions of
combinatorial topology. By using a result of Kalai and Meshulam [40, Proposition 3.1]
(also appearing implicitly in [2], [6], and [53]), Theorem 2.1 can be reduced to the problem
of showing that a certain simplicial complex is highly connected. We remind the reader
that a topological space X is k-connected if every map f : Si → X extends to a map
f̂ : Bi+1 → X for i = −1, 0, 1, . . . , k. Here Bi+1 denotes the (i+1)-dimensional ball whose
boundary is the i-dimensional sphere Si, and (−1)-connected means non-empty. The
following observation is sufficient for our application: A simplicial complex is k-connected
30 CHAPTER 2. GEOMETRIC HALL-TYPE THEOREMS
if and only if its (k + 1)-skeleton is k-connected.
Before getting to the details, let us conclude with a few words about the simplicial
complex arising in our second proof of Theorem 2.1. It was made explicit in [53], that
the key idea in the Aharoni and Haxell result is to capture pairwise disjointness among
the members in a family of sets. This can be encoded by the disjointness graph of the
family, and the resulting simplicial complex is the clique complex of the disjointness graph.
However, the general position property is not a pairwise condition (for d ≥ 2), and to
encode the subsets in general position requires a simplicial complex, the independence
complex of the underlying matroid of the point configuration. This in turn requires a
higher-dimensional version of a clique complex, which we call the completion. A crucial
observation concerning the completion of a complex is Lemma 2.2, which gives a local
combinatorial condition on a simplicial complex which guarantees that its completion is
k-connected.
2.2 Proof of Theorem 2.1
For positive integers d and k let
Ad(k) :=
{
k if k ≤ d+ 1
d
(
k−1
d
)
+ 1 if k > d+ 1.
Notice that Ad(k) is in O(kd).
Lemma 2.1. Let k be a positive integer. If S and T are sets in general position in Rd
where |S| = k − 1 and |T | ≥ Ad(k), then there exists a point p in T such that S ∪ {p} is
in general position.
Proof. For k ≤ d+ 1 the result is a consequence of the augmentation property of the un-
derlying matroid of a set of points in Rd (the independent sets are the affinely independent
sets). Suppose now that k ≥ d + 2 and that T is a set of points in general position with
|T | ≥ Ad(k). Notice that S spans
(
k−1
d
)
affine hyperplanes. In each of these hyperplanes
there can be at most d points from T since T is in general position. Therefore there exists
a point p in T which does not lie in any of these hyperplanes, implying that S ∪ {p} is in
general position.
Now let Bd(k) = k(Ad(k)− 1) + 1. Notice that Bd(k) is in O(kd+1).
Theorem 2.2. Let F = {X1, . . . , Xm} be a family of finite sets in Rd. If
ϕ
(
⋃
i∈I
Xi
)
≥ Bd(|I|)
2.3. A BETTER UPPER BOUND BY TOPOLOGICAL METHODS 31
for every non-empty subset I ⊂ {1, . . . ,m}, then F has a system of general position
representatives.
Proof. By the hypothesis, ϕ (
⋃m
i=1 Xi) ≥ m(Ad(m)− 1)+1. By the pigeon-hole principle,
there are at least Ad(m) points in general position belonging to one of the sets X1, . . . , Xm,
so we may assume ϕ(Xm) ≥ Ad(m). Using the hypothesis for I = {1, . . . ,m − 1}, the
same reasoning implies that there are Ad(m − 1) points in general position belonging to
one of the sets X1, . . ., Xm−1, so we may assume ϕ(Xm−1) ≥ Ad(m − 1). Proceeding
downwards we may assume that ϕ(Xi) ≥ Ad(i) for each i ∈ {1, . . . ,m}.
Now we use Lemma 2.1 upwards. We take a point p1 ∈ X1. Suppose we have selected
points pi ∈ Xi for i ∈ {1, 2, . . . , k−1} such that {p1, . . . , pk−1} is in general position. Then
Lemma 2.1 allows us to select a point pk ∈ Xk such that {p1, . . . , pk} is in general position.
We continue up to k = m to get the desired system of general position representatives.
2.3 A better upper bound by topological methods
2.3.1 The general position complex
Let X ⊂ Rd be a finite (multi)set. Let us define the general position complex of X,
denoted by G(X), to be the simplicial complex
G(X) := {S ⊂ X : S is in general position in Rd}.
Note that we allow for X to have repeated points. The number of vertices of G(X) is
the cardinality of X, counting multiplicities. A key observation is that the connectivity
of G(X) can be bounded below in terms of d and ϕ(X).
Theorem 2.3. For all integers d ≥ 1 and k ≥ −1 there exists a minimal positive integer
gd(k) such that the following holds. If X ⊂ Rd is a finite (multi)set with ϕ(X) ≥ gd(k),
then G(X) is k-connected.
A closely related simplicial complex is the independence complex of X, denoted by
M(X), defined as
M(X) := {S ⊂ X : S is affinely independent}.
The simplices of M(X) are the independent sets of a matroid, the underlying matroid
of X, which has rank r = min{ϕ(X), d + 1} = dimM(X) + 1. Note that M(X) is the
(r − 1)-skeleton of G(X).
32 CHAPTER 2. GEOMETRIC HALL-TYPE THEOREMS
Remark 2.1. We postpone the proof of Theorem 2.3, but here we note the following
special cases.
• For d = 1, a multiset X consists of n = ϕ(X) distinct points with mutliplicities
m1, . . . ,mn. The corresponding general position complex is the join of n discrete
sets of points. That is, G(X) = V1 ∗ · · · ∗ Vn, where |Vi| = mi. If |Vi| = 1 for any i,
then G(X) is contractible. If |Vi| > 1 for all i it is known that G(X) is homotopic
to a wedge of (n − 1)-dimensional spheres which is (n − 2)-connected. Therefore
g1(k) = k + 2.
• If k ≤ d − 1, then gd(k) = k + 2. In this case G(X) = M(X), and the claim
follows from the well-known fact that the independence complex of a rank r matroid
is (r − 2)-connected (see e.g. [9, 11]).
2.3.2 Colorful simplices
Let K be a simplicial complex on the vertex set V , and let V = V1∪· · ·∪Vm be a partition.
A simplex S ∈ K is called colorful if |S ∩ Vi| = 1 for all 1 ≤ i ≤ m. For a non-empty
subset I ⊂ {1, . . . ,m} let KI denote the induced subcomplex K
[⋃
i∈I Vi
]
.
The following sufficient condition for the existence of a colorful simplex in K was
given in [40, Proposition 3.1] (where it is stated in terms of rational homology rather than
connectedness), and in a more general form in [2, Theorem 4.5].
Proposition 2.1 (Kalai and Meshulam). Let K be a simplicial complex on the vertex set
V with partition V = V1 ∪ · · · ∪ Vm. If the induced subcomplex KI is (|I| − 2)-connected
for every non-empty subset I ⊂ {1, . . . ,m}, then K contains a colorful simplex.
Second proof of Theorem 2.1. Let F = {X1, . . . , Xm} be a family of finite sets in Rd and
let X = X1∪̇ · · · ∪̇Xm (that is, counting multiplicities). The members of F induce a
partition of the vertex set of G(X), and F has a system of general position represen-
tatives if and only if the general position complex G(X) contains a colorful simplex. If
ϕ
(⋃
i∈I Xi
)
≥ gd(|I| − 2) for every non-empty subset I ⊂ {1, . . . ,m}, then, by Theorem
2.3, G(X) satisfies the conditions of Lemma 2.1. Therefore fd(k) can be bounded above
by gd(k − 2).
Remark 2.2. In the next section we give an upper bound on gd(k) which is in O(kd).
2.4. PROOF OF THEOREM 2.3 33
2.4 Proof of Theorem 2.3
2.4.1 The completion of a simplicial complex
Let k be a positive integer and S a set with |S| ≥ k. The collection of all subsets of S of
size at most k is denoted by
[S]k := {T ⊂ S : |T | ≤ k}.
Let us also define [S]0 := ∅.
Let K be a simplicial complex of dimension d on the vertex set V . For the proof of
Theorem 2.3 we need the following simplicial complexes associated with K.
For a vertex v ∈ V , let stK(v) denote the star of v, which is defined as
stK(v) := {S ⊂ V : S ∪ {v} ∈ K}.
Notice that stK(v) is always non-empty since v ∈ stK(v).
For a vertex v ∈ V , let ΓK(v) denote the neighborhood complex of v, which is defined
as
ΓK(v) := stK(v) ∪ {S ⊂ V − {v} : S ∈ K, |S| = d+ 1, [S]d ⊂ stK(v)}.
Notice that if K is 0-dimensional, then ΓK(v) = K.
For j ≥ d, let ∆j(K) denote the j-completion of K, which is defined as
∆j(K) := K ∪ {S ⊂ V : |S| ≥ j + 2, [S]j+1 ⊂ K}.
Notice that if K is 0-dimensional then ∆0(K) is the (|V | − 1)-dimensional simplex. Let
us also define ∆j(∅) := ∅.
We note a few more basic facts. If L is a subcomplex of K and v is a vertex of L, then
stL(v) ⊂ stK(v) and ΓL(v) ⊂ ΓL(v). Also, if j > dimK, then ∆j(K) = K. Consequently,
if L is a subcomplex of K, then ∆d(L) ⊂ ∆d(K).
Proposition 2.2. Let K be a simplicial complex of dimension d and let {Ki}i∈I be a
finite family of subcomplexes of K. Then
∆d
(
⋂
i∈I
Ki
)
=
⋂
i∈I
∆d(Ki).
34 CHAPTER 2. GEOMETRIC HALL-TYPE THEOREMS
Proof. Since
⋂
i∈I Ki ⊂ Ki, we have ∆d
(⋂
i∈I Ki
)
⊂ ∆d(Ki). Therefore ∆d
(⋂
i∈I Ki
)
⊂
⋂
i∈I ∆d(Ki).
For the other direction, suppose S ∈ ⋂i∈I ∆d(Ki). If |S| ≤ d+ 1, then S ∈ ⋂i∈I Ki ⊂
∆d
(⋂
i∈I Ki
)
. If |S| ≥ d+ 2, then [S]d+1 ⊂ Ki for every i ∈ I. That is, [S]d+1 ⊂
⋂
i∈I Ki,
and therefore S ∈ ∆d
(⋂
i∈I Ki
)
.
Proposition 2.3. Let K be a simplicial complex of dimension d on the vertex set V and
let v ∈ V . Then
st∆d(K)(v) = ∆d (ΓK(v)) .
Proof. We first show that st∆d(K)(v) ⊂ ∆d(ΓK(v)). Suppose S ∈ st∆d(K)(v), which, by
definition, means that
S ∪ {v} ∈ ∆d(K) = K ∪ {T ⊂ V : |S| ≥ d+ 2, [S]d+1 ⊂ K}.
If |S ∪ {v}| ≤ d + 1, then S ∪ {v} ∈ K. This implies that S ∈ stK(v), and since
stK(v) ⊂ ΓK(v) ⊂ ∆d(ΓK(v)) we have S ∈ ∆d(ΓK(v)).
If |S ∪{v}| ≥ d+2, then [S ∪{v}]d+1 ⊂ K. This implies that for every T ∈ [S−{v}]d
we have T ∈ stK(v), and consequently [S]d+1 ⊂ ΓK(v). Therefore S ∈ ∆d(ΓK(v)).
It remains to show that ∆d(ΓK(v)) ⊂ st∆d(K)(v). Suppose S ∈ ∆d(ΓK(v)).
If |S| ≤ d+1, then S ∈ ΓK(v). Furthermore, if |S−{v}| ≤ d it follows that S ∈ stK(v).
Since K ⊂ ∆d(K) we have S ∈ st∆d(K)(v). On the other hand, if v /∈ S and |S| = d + 1,
then, by definition, we have S ∈ K and [S]d ⊂ stK(v). This implies that [S∪{v}]d+1 ⊂ K,
and it follows that S ∪ {v} ∈ ∆d(K), which shows that S ∈ st∆d(K)(v).
If |S| ≥ d + 2, then [S]d+1 ⊂ ΓK(v). This implies that for every T ∈ [S − {v}]d
we have T ∈ stK(v), and for every T ∈ [S − {v}]d+1 we have T ∈ K. It follows that
[S ∪ {v}]d+1 ⊂ K, and therefore S ∪ {v} ∈ ∆d(K), which shows that S ∈ st∆d(K)(v).
2.4.2 The Nerve theorem
Let F be a finite family of sets. The nerve of F , denoted by N(F ), is the simplicial
complex on the vertex set F whose simplices are the intersecting subfamilies of F , that is
N(F ) := {G ⊂ F :
⋂
S∈G
S 6= ∅}.
We will use the following version of the Nerve theorem which is a consequence of [10,
Theorem 6].
2.4. PROOF OF THEOREM 2.3 35
Theorem 2.4 (Björner). Let K be a simplicial complex and F = {Ki}i∈I a finite family
of subcomplexes such that K =
⋃
i∈I Ki. Suppose every non-empty intersection
⋂
t∈T Kt is
(k+1−|T |)-connected, T ⊂ I. Then K is k-connected if and only if N(F ) is k-connected.
2.4.3 The q-star property
Let K be a simplicial complex of dimension d on the vertex set V . For any integer q ≥ 1,
we say that K is q-star if |V | > q, and for every subset Y ⊂ V of size q there exists a
vertex v ∈ V − Y such that S ∪ {v} ∈ K for every simplex S ∈ K[Y ] with |S| ≤ d. The
following is an extension of a result on clique complexes appearing in [39, Theorem 3.1],
and in a more general form in [53, Theorem 1.5].
Lemma 2.2. Let K be a simplicial complex of dimension d and let k be a non-negative
integer. If K is (2k + 2)-star, then its d-completion ∆d(K) is k-connected.
Proof. For d = 0 the statement holds because ∆0(K) is a simplex which is contractible.
We may therefore assume d ≥ 1.
If a complex K of dimension d ≥ 1 is 2-star, then K is connected which implies that
∆d(K) is also connected. So the statement is clearly true for k = 0, and we proceed by
induction on k.
Suppose K is (2k+2)-star for k > 0 and let V be the vertex set of K. For each vertex
v ∈ V , let Kv = st∆d(K)(v). Define the family of subcomplexes F = {Kv}v∈V . Clearly we
have
∆d(K) =
⋃
v∈V
Kv.
For a non-empty subset W ⊂ V , let KW =
⋂
v∈W Kv. Theorem 2.4 implies that ∆d(K)
is k-connected, if we can show the following.
(i) KW is (k + 1− t)-connected for every non-empty subset W ⊂ V with |W | = t.
(ii) The nerve N(F ) is k-connected.
Part (i). For every v ∈ V , Kv is a cone which is contractible, and hence k-connected.
Now consider W ⊂ V with |W | = t ≥ 2, and let LW =
⋂
v∈W ΓK(v). By Propositions 2.2
and 2.3 we have
KW =
⋂
v∈W
st∆d(K)(v) = ∆d
(
⋂
v∈W
ΓK(v)
)
= ∆d(LW ).
36 CHAPTER 2. GEOMETRIC HALL-TYPE THEOREMS
By induction, it therefore suffices to prove that LW is (2(k+ 1− t) + 2)-star. Also notice
that for t ≥ 2 we have 2k + 2 − t ≥ 2(k + 1 − t) + 2, so it suffices to show that LW is
(2k + 2− t)-star.
LetX be the vertex set of LW . Clearly a vertex v belongs toX if and only if {v, w} ∈ K
for all w ∈ W . This implies that |X| > 2k + 2− t, since K is (2k + 2)-star.
Next, we observe that for every Y ⊂ X with |Y | = 2k + 2 − t we can find a set
Z ⊂ X ∪ W with |Z| = 2k + 2 such that Y ∪ W ⊂ Z. Since K is (2k + 2)-star, there
exists v ∈ V − Z such that
S ∪ {v} ∈ K for every S ∈ K[Z] with |S| ≤ d. (∗)
It follows from our previous observation that v ∈ X.
Let S ∈ LW [Y ] with |S| ≤ dimLW ≤ d. We need to show that S ∪ {v} ∈ LW , that
is, S ∪ {v} ∈ ΓK(w) for every w ∈ W . Notice that S ∪ {w} ⊂ Z, so (∗) may be applied
provided |S ∪ {w}| ≤ d.
If |S ∪ {w}| ≤ d, then (∗) implies that S ∪ {w} ∪ {v} ∈ K. This just means that
S ∪ {v} ∈ stK(w), and consequently S ∪ {v} ∈ ΓK(w).
If |S ∪{w}| = d+1, then |S| = d, w /∈ S, and S ∪{w} ∈ K. For every T ∈ [S ∪{w}]d,
it follows from (∗) that T ∪{v} ∈ K. In particular S ∪{v} ∈ K and [S ∪{v}]d ⊂ stK(w),
and since |S ∪ {v}| = d+ 1, we conclude that S ∪ {v} ∈ ΓK(w).
This shows that LW is (2k + 2− t)-star.
Part (ii). Clearly KW is non-empty for any subset W ⊂ V with |W | = 2k + 2.
Therefore the (2k + 1)-skeleton of the nerve N(F ) is complete, which implies that N(F )
is 2k-connected.
Proof of Theorem 2.3. Let K = M(X), the independence complex of X. Clearly the
general position complex of X is the d-completion of K, that is, G(X) = ∆d(K). We
want to show that G(X) is k-connected provided ϕ(X) is sufficiently large. In view of
Remark 2.1, we may assume that k ≥ d. We will show that if ϕ(X) > d
(
2k+2
d
)
, then K
is (2k + 2)-star. This implies that G(X) is k-connected by Lemma 2.2. Let S ⊂ X with
|S| = 2k+2. Let H denote the set of affine hyperplanes spanned by affinely independent
d-tuples in S. Therefore, if ϕ(X) > d
(
2k+2
d
)
≥ d|H|, then there exists a point x ∈ X
which is not contained in the affine hull of any subset T ⊂ S with |T | ≤ d. This gives an
upper bound on gd(k) in O(kd).
2.5. CONCLUDING REMARKS 37
2.5 Concluding remarks
The natural problem that arises is to try to determine better (or exact) bounds for the
functions gd(k). We have shown that gd(k) = k+2 for k ≤ d− 1 and gd(k) ≤ d
(
2k+2
d
)
+1,
otherwise, but we hardly believe this to be optimal. In fact, the exact same proof (and
bound) works in a more general setting, which we now describe.
Let M be a matroid of rank r on the ground set E. We say that a subset S ⊂ E is
uniform if S is independent or |S| > r and every member of [S]r is independent. The set
of all uniform subsets of a matroid M form a simplicial complex, which call the uniformity
complex of M . Obviously, the uniformity complex of a matroid is the (r − 1)-completion
of its independence complex. If we let µ(M) denote the maximum size of a uniform subset
of M , then we have the following generalization of Theorem 2.3.
Theorem 2.5. For all integers r ≥ 2 and k ≥ −1 there exists a minimal positive integer
hr(k) such that the following holds. If M is matroid of rank r and µ(M) ≥ hr(k), then
the uniformity complex of M is k-connected.
Proof. The same argument (as in the proof of Theorem 2.3) shows that if µ(M) > (r −
1)
(
2k+2
r−1
)
, then the independence complex of M is (2k+2)-star. The theorem then follows
from Lemma 2.2.
We find it likely that there should be a sharp distinction in the asymptotic behavior
between the function hr(k) and the corresponding function gr−1(k). More generally, we
find it reasonable to expect the orientability of the matroidM to have a strong quantitative
effect on the connectivity of the uniformity complex, but we lack any evidence to support
this. In fact, the only exact value we know (apart from what is covered by Remark 2.1)
is g2(2) = h3(2) = 7.
In conclusion we mention that, in view of Theorem 2.5, it is straightforward to apply
Proposition 2.1 to obtain an analogue of Theorem 2.1 for uniform systems of representa-
tives. Further generalizations can also be obtained by using the more general version of
Lemma 2.1 appearing in [2, Theorem 4.5]. We leave the details to the reader.
2.6 A Hall-type theorem for Sλ-free graphs
We refer to the Appendix for the preliminaries. In this section we are interested in proving
the following result.
Theorem 2.6. Let λ ≥ 2 and m ≥ 1 be positive integers. Let G be a Sλ-free graph.
Suppose we have S = {S1, . . . , Sm} a family of finite sets of vertices of G.
38 CHAPTER 2. GEOMETRIC HALL-TYPE THEOREMS
If for every I ⊆ [m] the graph induced by ∪j∈ISj has independence number at least
(|I| − 1)(λ− 1) + 1,
then there exists an independent set of representatives for S.
We would like to point out that this theorem is indeed a generalization of Hall’s
theorem. Suppose we have a finite bipartite graph with partition sets X = {v1, . . . , vk}
and Y in which Hall’s condition is satisfied, that is, every set S ⊆ X has at least |S|
elements in its neighborhood. Since Y is independent, it is S2-free. Then taking Sj as the
neighbors of vj we obtain using Theorem 2.6 a matching that covers X.
Another remark is that G may be infinite, as long as S and each Si is finite. Before
proving Theorem 2.6 we will explore some of its corollaries in geometry.
We draw some unit disks on the plane and take k colors. We paint each disk with at
least one color. The aim is to find conditions on the coloring so that we are able to find
k pairwise-disjoint unit disks, one of each color. We provide a Hall-type condition.
Proposition 2.4. Let m ≥ 1 be an integer and S = {S1, S2, . . . , Sm} be a family of finite
sets of unit disks on the plane. If for every I ⊆ [m] we have at least 5|I| − 4 pairwise-
disjoint unit disks in ∪j∈ISj, then we can find a system of pairwise-disjoint unit disk
representatives for S.
Proof. Consider the graph G in which the vertices are all the unit disks of the plane and
in which two distinct vertices are adjacent if the disks intersect. The proposition will
follow immediately from Theorem 2.6 if we can prove that this graph G is S6-free. This
is a well-known result, but we prove it here for completeness.
Suppose that G has S6 as an induced subgraph. Then by considering the centers of
the disks, this means that we can find a point C and some points around it ordered in a
clockwise order C1, C2, . . ., C6 such that d(C,Ci) ≤ 2 for i = 1, . . . , 6 but d(Ci, Cj) > 2
for any pair of distinct indices. Since the angles ∠C1CC2, ∠C2CC3, . . ., ∠C6CC1 add up
to 2π, then one of them must be less than or equal to π
3
. By relabeling the points we
may assume that ∠C1CC2 ≤ π
3
and ∠CC2C1 ≥ π
3
. Therefore, d(C1, C2) ≤ d(C,C1) ≤ 2,
a contradiction. This proves that G is S6-free.
We can prove a similar result in d-dimension. For this, we define κ(d) as the maximum
number of non-overlapping unit spheres in R such that each one touches another given
unit sphere. In the literature, κ(d) is known as the kissing number and has been studied
extensively (for example, in [46, 55, 62]). The following lemma allows us to generalize our
previous result.
2.6. A HALL-TYPE THEOREM FOR Sλ-FREE GRAPHS 39
Lemma 2.3. Let d be a positive integer and consider the graph G in which the vertices are
all the unit balls of Rd and in which two distinct vertices are adjacent if the corresponding
balls intersect. If λ is the smallest integer such that G is Sλ-free, then κ(d) ≥ λ− 1.
Proof. Since G is not Sλ−1 free, we can find an induced K1,λ−1 subgraph. By considering
the centers of the corresponding unit balls, we can find some points C, C1, . . ., Cλ−1 such
that d(C,Ci) ≤ 2 for i ∈ [λ − 1] but d(Ci, Cj) > 2 for any pair of distinct indices. In
particular, for any distinct indices i and j we must have ∠CiCCj >
π
3
. Consider C ′
i and
C ′
j the points of intersection of the sphere of radius 2 centered at C and the rays
−−→
CCi,−−→
CCj respectively. Since ∠C ′
iCC ′
j >
π
3
, we have d(C ′
i, C
′
j) > 2.
Therefore, we may translate the corresponding unit balls away from C so that they
touch the unit ball with center C and preserve intersections. By considering the bound-
aries of these translated balls, we get an arrangement of λ − 1 pairwise-disjoint spheres
that touch a given sphere, and therefore κ(d) ≥ λ− 1.
If a graph G is Sλ-free, then it is also Sλ′-free for any λ′ ≥ λ. Therefore, Lemma
2.3 implies that the graph G is Sκ(d)+1-free. From this observation and Theorem 2.6 the
following result follows:
Theorem 2.7. Let m and d be positive integers and S = {S1, S2, . . . , Sm} be a family of
finite sets of unit balls on Rd. If for every I ⊆ [m] we have at least
κ(d)(|β| − 1) + 1
pairwise-disjoint unit balls in ∪j∈I , then we can find a system of pairwise-disjoint unit
ball representatives for S.
Remark 2.3. • The work in [46, 55] proves that κ(3) = 12 and κ(4) = 24. Therefore
for each I ⊆ [m] it is enough to ask for 12|I| − 11 and 24|I| − 23 disjoint disks
in dimensions 3 and 4 respectively. For higher dimensions we may use the upper
bounds of κ(d) in the literature. For any dimension we get a Hall-type condition
that is linear in |I|.
• We can similarly define the kissing number for a family of convex sets of Rd and
use it to get analogous Hall-type results.
• The kissing number could give a non-optimal bound since it deals with non-overlapping
spheres. For example, κ(2) = 6 and thus Theorem 2.7 requires 6|β|−5 disjoint disks.
However, we have proved in Proposition 2.4 that the weaker requirement 5|β| − 4 is
enough.
40 CHAPTER 2. GEOMETRIC HALL-TYPE THEOREMS
2.7 Proof of Theorem 2.6
In this section we prove Theorem 2.6. The proof uses triangulations of a simplex and
Sperner’s lemma, so we refer to the Appendix for basic definitions and results. Let T be
a triangulation of the k-simplex ∆k. The support supp(x) of a point x ∈ T is the unique
face of ∆k that contains x in its relative interior. We will use the following result due to
Aharoni and Haxell ([6]):
Lemma 2.4. The k-dimensional simplex ∆k has a triangulation T such that:
• For any two points that are connected in the 1-dimensional skeleton of T the support
of one is contained in the support of the other.
• For each point x of T the neighbors of x on the boundary of supp(x) form a (possibly
empty) simplex of T .
We call such a triangulation economically hierarchic. With these ideas in mind, lets
prove Theorem 2.6. As a reminder, we have a Sλ-free graph G and a family of finite sets
of vertices S = {S1, S2, . . . , Sm}.
Consider ∆m−1 and name its vertices 1, 2, . . . ,m. For each I ⊆ [k] we define GI as
the graph induced by ∪j∈ISj and 〈I〉 as the face of ∆m−1 with vertex set I. We also set
f(d) := (d− 1)(λ− 1)+ 1. We have as a hypothesis that GI has independence number at
least f(|I|).
Let T be an economically hierarchic triangulation of ∆m−1. We will show how to label
each point x of T with an ordered pair (i, v) of an index i ∈ [m] and a vertex v ∈ Si in
such a way that:
(1) If supp(x) = 〈I〉 then i ∈ I.
(2) If x and y are neighbors that get labels (i, v) and (j, w) with i 6= j then v 6= w and
vw is not and edge of G.
We will proceed inductively on dim(supp(x)). If dim(supp(x)) = 0, then x is a vertex
of ∆m−1. But for each index i we have at least f(|{i}|) = f(1) = 1 vertex in Si, so we
can label each vertex i of ∆k−1 with a pair (i, v) so that v ∈ Si.
Suppose we have managed to label all the vertices with support of dimension less than
d for some d ≤ m so that the labeling satisfies (1) and (2). We will now extend the
labeling to the vertices whose support has dimension d. Let I be a subset of [m] such
that |I| = d. Since the independence number of GI is at least f(d), then there exists an
2.7. PROOF OF THEOREM 2.6 41
independent set MI of GI with f(d) elements. We fix this MI and for each v ∈ MI lets fix
an arbitrary index i(v) ∈ I such that v ∈ Si(v). We may take, for example, the smallest
such index. It is important to fix this index from now on.
Now consider a vertex x of T which its support is 〈I〉. Since T is economically hi-
erarchic, each neighbor y of x for which we have dim(supp(y)) < d, lies on a face of
supp(x). Furthermore, the neighbors of x with support of dimension less than d form
a lower dimensional simplex, and in particular they are d − 1 or fewer. Let y be one
of the previously labeled neighbors of x and let (j, w) be its label. We will analyze two
situations:
• w ∈ MI . In this case there are no more elements of MI adjacent to w.
• w /∈ MI . Here at most λ − 1 vertices of MI can be adjacent to w (in G), since
otherwise these vertices and w would form a Sλ star in G.
Since MI has f(d) > (d − 1)(λ − 1) vertices, then there must exist a vertex v ∈ MI
such that it is neither equal nor adjacent in G to any vertex in a label of a previously
labeled neighbor of x. We assign the label (v, iv) to x.
This states how to label the vertices with support 〈I〉. We do the same for each d-
subset I of [m]. Now we are left to prove that this new labeling is well-defined and still
satisfies (1) and (2). By construction, in every new label we have v ∈ Si(v) and i(v) ∈ I,
so the new labels are well-defined and satisfy (1). To prove (2) we take x and y adjacent
vertices with respective labels (i, v) and (j, w). We may assume supp(x) ⊇ supp(y). Since
T is economically hierarchic, we need to deal with the following three cases:
• dim(supp(x)) < d. In this case, (2) follows from the inductive hypothesis.
• dim(supp(x)) = d and supp(x) ) supp(y). In this case we have just labeled the
vertex x and we chose the label in such a way that v is not adjacent nor equal to
w, and thus we have (2).
• dim(supp(x)) = d and supp(x) = supp(y). Here (2) follows from the fact that both
v and w come from the same MI . This is an independent set of vertices in G. If
v = w, then iv = iw and we have nothing to prove. If v 6= w, then v and w are not
adjacent in G and thus they satisfy (2).
This shows how to produce a labeling of the vertices of T that satisfies both (1)
and (2). By (1), the first coordinates of the labels satisfy the hypothesis of Sperner’s
lemma. Therefore, Sperner’s lemma guarantees the existence of a multicolored simplex
in the triangulation. By condition (2), the vertices of S in the labels of this multicolored
simplex form a system of independent representatives for S.
Chapter 3
Fractional Turán-type theorems
Turán’s theorem is a result in extremal graph theory that relates the number of edges
of a graph and the largest complete subgraph it contains. If we restrict ourselves to a
family of graphs with geometrical constraints, then it is possible to get sharper Turán-type
results. An example of this is the family of interval graphs, for which a classical result by
Katchalski and Liu provides a fractional version of Helly’s theorem.
In this chapter we explore the combinatorial properties that a family of graphs must
satisfy so that we can find similar Turán-type results. We also provide connections to
this topic and other well-studied graph invariants. This is a joint work with Luis Monte-
jano Peimbert. The results have been presented in the VIII Latin-American Algorithms,
Graphs and Optimization Symposium (LAGOS 2015). The following sections consist of
an adaptation and extension of the extended abstract [50] presented for the conference.
3.1 Introduction
3.1.1 Background and motivation
This work relates three classic topics: clique numbers, graph colorings and Turán numbers.
For basic definitions and notation we refer to the Appendix.
Intuitively, a graph with a fixed number of vertices and many edges should have a
large clique number. Turán’s theorem [66] is a result in extremal graph theory which
makes this idea precise.
Theorem 3.1 (Simple Turán’s theorem). Let G be a graph with n vertices and r a positive
43
44 CHAPTER 3. FRACTIONAL TURÁN-TYPE THEOREMS
integer. If G has more than
(
1− 1
r − 1
)
· n
2
2
edges, then ω(G) ≥ r.
Turán’s theorem can be stated in terms of the usual notation in extremal graph theory.
For a family of graphs F we say that a graph is F-free if it does not have any graph of
F as an induced subgraph. We denote by ex(n;F) the maximum number of edges that
a F -free graph on n vertices can have. We denote by EX(n;F) the extremal graphs, that
is, F -free graphs with n vertices and ex(n;F) edges.
In these terms, the simple Turań’s theorem gives a bound for ex(n, {Kr}). How-
ever, Turán proved a stronger version of the theorem that also characterizes the extremal
graphs. Consider the following construction. For positive integers n and r, we split [n]
in r − 1 sets V1, . . ., Vr−1 as evenly as possible, that is, so that no two sets have size
difference larger than 1. The Turán graph Tn,r has vertex set [n] and two vertices u and
v are adjacent if and only if they belong to different Vi’s.
Theorem 3.2 (Turán’s theorem). We have
ex(n, {Kr}) = |E(Tn,r)| and EX(n, {Kr}) = {Tn,r}.
Note that asymptotically the expression
(
1− 1
r−1
)
· n2
2
is a proportion of the possible
(
n
2
)
edges that the graph could have. Therefore, Turán’s theorem states that a large
proportion of the edges guarantees the existence of a large clique of a fixed size. Could
it be possible to improve the size of this clique? For example, could it be possible that
a large proportion of edges yields a clique that is proportionally large? In general, the
answer is no.
Example 3.1. There are graphs with 99.99% of the maximum number of edges, but with-
out a clique that uses at least 0.01% of the vertices.
Easy examples can be found among Turán graphs. Nevertheless, there exist some fam-
ilies of graphs in which there is a stronger Turán-type theorem. Consider the following
example. An interval graph, is constructed as follows. The vertices are some bounded
intervals in R. We place an edge if the corresponding intervals have non-empty intersec-
tion. We denote the family of all the possible interval graphs by GI . A classic result in
convexity by Katchalski and Liu [42] can be stated in the following terms:
Theorem 3.3. Let G ∈ GI be an interval graph with n vertices and α ∈ [0, 1] a real
number. If G has more than
α ·
(
n
2
)
edges, then ω(G) ≥ α
2
· n.
3.1. INTRODUCTION 45
This result usually yields a larger clique in the family GI . For example, consider a
graph G with n vertices and more than n2
4
edges. Turán’s theorem only guarantees the
existence of a triangle. But if G is an interval graph, Theorem 3.3 yields a clique of size n
4
.
Note that in particular this expression goes to infinity as n goes to infinity. Moreover, α
and α
2
differ only in a constant factor. These observations motivate the following questions
that make more precise the task of finding a better Turán-type theorem for a family of
graphs.
• What are the conditions that a family of graphs must satisfy so that there exists
a constant β ∈ (0, 1) such that a proportion of α ∈ (0, 1) of the number of edges
guarantees that ω(G) ≥ αβ · |V (G)|?
• What are the conditions that a family of graphs must satisfy so that a proportion
of α ∈ (0, 1) of the number of edges guarantees that ω(G) → ∞ as |V (G)| → ∞?
In order to study these questions, we use as test cases families of F -free graphs. This
is equivalent to studying the functions ex(n;F ∪ {Kr}) and EX(n;F ∪ {Kr}). Therefore,
we call ex(n;F ∪ {Kr}) the Turán number for F . Note that if r ≥ n + 1, then we can
clearly have at most
(
n
2
)
edges, and the problem is not interesting. Therefore, we assume
from now on that r ≤ n.
To obtain more general results, we relate the motivating questions to obtaining bounds
for the chromatic number of a graph in terms of the clique number. In a proper coloring
all the vertices of a clique must get different colors and therefore χ(G) ≥ ω(G). A classic
question in chromatic graph theory is to determine if there is an upper bound for χ(G) in
terms of ω(G). The answer is negative. Even a triangle-free can have an arbitrarily large
chromatic number ([28], [25], [71], [56]) . Therefore, the families of graphs for which there
exists a function f such that χ(G) ≤ f(ω(G)) have been a subject of interest ([33]).
On the other hand, it is possible to bound χ(G) by above using a function that depends
on |V (G)| and ω(G). A trivial bound is χ(G) ≤ |V (G)|. A better bound is the following
known result Ver qué ejercicio/libro.
Proposition 3.1. Let G be a graph. Then:
χ(G) ≤ 1
2
· |V (G)|+ 1
2
· ω(G).
In the trivial bound the coefficient of |V (G)| is 1. In the bound of Proposition 3.1 the
coefficient is 1
2
. How small can we make this coefficient? It turns out that we can make
the coefficient of |V (G)| arbitrarily close to 0 and still be able to complete the bound
using a function of ω(G).
46 CHAPTER 3. FRACTIONAL TURÁN-TYPE THEOREMS
Table 3.1: Exact Turán numbers and extremal graphs
F Constraints ex(n,F ∪ {Kr}) EX(n,F ∪ {Kr})
P2, 2K2
(
r−1
2
)
Kr−1
P2, ℓK1 n ∈ [r, (ℓ− 1)(r − 1)− 1] q
(
r−1
2
)
+
(
s
2
)
qKr−1 ∪Ks
3K1 n = 3, r = 3 2 P2
n = 4, r = 3 4 C4
n = 5, r = 3 5 C5
n = 4, r = 4 5 K2,1,1
n = 5, r = 4 8 K2,2,1
n = 6, r = 4 12 K2,2,2
n = 7, r = 4 15 See proof
n = 8, r = 4 Between 18 and 20 See proof
3.1.2 Results and outline
We start by analyzing the Turán numbers of some families of graphs. In Section 3.2
we provide exact values for ex(n;F ∪ {Kr}) and a complete characterization of extremal
graphs for the families in Table 3.1. Remember we are assuming n ≥ r.
Theorem 3.4. Table 3.1 provides the exact values of ex(n; {P2, 2K2} ∪ {Kr}) and the
only extremal graphs.
The value of ex({P2, ℓK1} ∪ {Kr}) is well-defined only for n ≤ (ℓ − 1)(r − 1). Table
3.1 provides the exact value and the only extremal graph.
If we forbid independent sets of 3 vertices and the graph has many vertices, then we
cannot avoid having a large clique. In general, Ramsey’s theorem [61] starts to play a
role and the results get more complex.
Theorem 3.5. The value of ex(n; {3K1} ∪ {K3}) is well-defined only for n ≤ 5. Table
3.1 provides the exact values and the only extremal graphs.
The value of ex(n; {3K1} ∪ {K4}) is well-defined only for n ≤ 8. Table 3.1 provides
exact values for 4 ≤ n ≤ 7 and the only extremal graphs. It also provides correct bounds
for n = 8.
In Section 3.3 we prove a more general result for families of graphs. We find a triple
relation between the existence of a linear Turán-type theorem, a linear bound on Turán
numbers, and a linear bound for the chromatic number in terms of the clique number.
Theorem 3.6. Let G be a family of graphs closed under induced subgraphs. Then the
following three statements are equivalent:
3.2. EXACT TURÁN NUMBERS AND EXTREMAL GRAPHS 47
• (Linear Turán-type theorem) There exists a real number β ∈ (0, 1) such that
for G ∈ G if |E(G)| ≥ α ·
(
|V (G)|
2
)
, then ω(G) ≥ αβ · |V (G)|.
• (Linear Turán numbers) There exists a real number C such that for every G ∈ G
we have |E(G)| ≤ C · ω(G) · |V (G)|.
• (Linear chromatic bound) There are real numbers c and d such that
– for every G ∈ G we have χ(G) ≤ c · ω(G) and
– for every B ∈ G, B bipartite, we have |E(B)| ≤ d · |V (B)|.
Finally, in Section 3.4 we provide a version of Proposition 3.1 in which the coefficient
of |V (G)| can be as small as desired.
Proposition 3.2. Let ǫ > 0 be a real number. Then there exists a function fǫ such that
for every graph G we have
χ(G) ≤ ǫ · |V (G)|+ fǫ(ω(G)).
Using this proposition we prove our second result on Turán-type variants. It is a
criterion for making the clique number go to infinity in a family of graphs but just requiring
a fixed proportion of the possible total number of edges. The only condition that is
required is that the bipartite graphs of the family are sparse.
Theorem 3.7. Let G be a family of graphs closed under induced subgraphs for which there
exists a constant C such that for any bipartite graph B of G we have |E(B)| ≤ C · |V (B)|.
For any α ∈ (0, 1) and every integer M there exists an integer N such that if
G ∈ G, |V (G)| > N and |E(G)| ≥ α ·
(|V (G)|
2
)
,
then ω(G) > M .
3.2 Exact Turán numbers and extremal graphs
In this section we prove Theorem 3.4 and Theorem 3.5.
48 CHAPTER 3. FRACTIONAL TURÁN-TYPE THEOREMS
3.2.1 {P2, 2K2}-free graphs
First we show that ex(n; {P2, 2K2} ∪ {Kr}) is at most
(
r−1
2
)
.
A graph is P2-free if and only if it is transitive. Therefore, a P2-free graph is a union of
disjoint complete graphs. We also also supposing that the graphs are 2K2-free. Therefore,
at most one of the graphs in the disjoint union of complete graphs has more than one
vertex.
This means that a graph in the family on n vertices consists of k vertices forming a
clique and n− k vertices forming an independent set. All the edges come from the clique
and they are
(
k
2
)
in total. If we have more that
(
r−1
2
)
edges, then this means k ≥ r, and
therefore the graph is not Kr-free.
The only situation in which we have
(
r−1
2
)
edges is when k = r− 1. This characterizes
the extremal graphs.
3.2.2 {P2, ℓK1}-free graphs
Let ℓ ≥ 2 be an integer. We will now find the maximum number of edges that a {P2, ℓK1}-
free graph G on n vertices can have so that its clique number is less than r.
As before, a P2-free graph is a disjoint union of complete graphs. Since G is also ℓK1
free, this means that it is a union of at most ℓ − 1 complete graphs. Suppose that G is
partitioned in complete graphs of orders
a1 ≥ a2 ≥ . . . ≥ aℓ−1.
If n > (ℓ− 1)(r− 1), then by the pidgeon-hole principle a1 ≥ r, and we get ω(G) ≥ r,
a contradiction. Therefore n ≤ (ℓ− 1)(r − 1). In this case, we are trying to maximize
ℓ−1∑
i=1
(
ai
2
)
subject to the restrictions ai ≥ 0, ai ≤ r−1 and a1+ . . .+ar−1 = n. This can be solved
using Karamata’s inequality [41], a classic tool from convex functions comparisons. We
write n = q(r − 1) + s where q is a positive negative integer and s is in {0, 1, . . . , r − 2}.
Consider
• The convex function f(x) =
(
x
2
)
3.2. EXACT TURÁN NUMBERS AND EXTREMAL GRAPHS 49
• The (ℓ− 1)-tuple A = (a1, a2, . . . , aℓ−1)
• The (ℓ − 1)-tuple B = (r − 1, r − 1, . . . , r − 1, s, 0, . . . , 0), where we have q entries
equal to r − 1.
Clearly B majorizes A, and therefore by Karamata’s inequality we have
ℓ−1∑
i=1
(
ai
2
)
≤ q
(
t
2
)
+
(
s
2
)
.
This is the inequality we wanted to prove according to Theorem 3.4. The characteri-
zation of extremal graphs is now immediate. Karamata’s equality is obtained only when
A equals B. This means that the extremal graph consists of q copies of Kr−1 and a copy
of Ks.
3.2.3 Ramsey meets Turán: {3K1, Kr}-free graphs
We now study {3K1, Kr}-free graphs for r = 3, 4 to prove Theorem 3.5. Let a and b be
positive integers. Ramsey’s theorem [61], guarantees that there exists a positive integer
R(a, b) such that a graph with this number or more vertices has either Ka or bK1 as an
induced subgraph. Therefore, a {3K1, Kr}-free graph can only have at most R(3, r) − 1
vertices.
It is a classical result in graph theory that the exact values for R(3, 3) and R(3, 4)
are 6 and 9 respectively. Therefore, we are only interested in graphs with at most 5 or 8
vertices respectively.
Proof for r = 3. In this case we are avoiding triangles.
If we have 3 vertices, then P2 has 2 edges and no triangles. Clearly this is the maximum
number of edges we can have, or otherwise we get K3.
If we have 4 vertices, since we want to avoid triangles Turán’s theorem bounds the
edges by 4. The (unique) Turán’s graph T4,3 is C4, which is indeed 3K1-free.
If we have 5 vertices, the cycle graph C5 provides an example with 5 edges. We
will show that it is maximal and unique. Suppose |E(G)| ≥ 6. Using the formula
2|E(G)| =∑ d(v) we conclude that there exist a vertex with at least 3 neighbors u, v and
w. No two of them can be adjacent (or we would get a triangle), but then the three of
them are independent, contradicting that G is 3K1-free. If we have five edges, the same
50 CHAPTER 3. FRACTIONAL TURÁN-TYPE THEOREMS
argument shows that the degree of every vertex must be 2. Therefore, G is a union of
disjoint cycles. Since G has 5 vertices, it must be the 5-cycle.
The case r = 4 is slightly more elaborated. We have to consider graphs with 4, 5, 6, 7
and 8 vertices. For the first four values we have exact Turán numbers. For the last one
we have a bound.
Proof for r = 4. The maximality and uniqueness for 4, 5 and 6 vertices is given by Turán’s
theorem and Turán graphs K2,1,1, K2,2,1 and K2,2,2 respectively. The examples are correct
because all of them are 3K1-free.
This argument stops working for 7 vertices because in this case the corresponding
Turán’s graph is K3,2,2 and it is not 3K1-free. By uniqueness of Turán graphs, we now
know
ex(7; {3K1} ∪ {K4}) ≤ 15.
We will now present a construction that has 15 edges.
• Let U = {u1, u2}, V = {v1, v2} and W = {w1, w2, w3}. The vertex set will be the
disjoint union of U , V and W .
• All the vertices from U are adjacent to all the vertices from V and W .
• We connect all vertices from V to all vertices from W except for the pairs v1w1 and
v2w2.
• {w1, w2} is an edge.
This graph is K4-free because a K4 would require w1, w2, one vertex from U and one
from V . But then we cannot take either v1 or v2, so the K4 is impossible.
Moreover, it is 3K1-free. If we wanted an independent 3-set, we cannot take a vertex
from U (because they are completely connected with V ∪W ). It cannot have v1 because
it is only non-adjacent to the adjacent vertices w1 and v2. Analogously it cannot have v2.
Therefore, it must be W , but W is not independent. This shows that the example works.
Uniqueness
We will now consider graphs on 8 vertices. The upper bound of 20 is again given
by Turán’s theorem and the fact that Turán’s graph for this case is not 3K1-free. The
construction that shows that we can have at least 18 edges is the following one:
3.3. LINEAR FRACTIONAL TURÁN-TYPE THEOREM 51
• Vertex-sets U = {u1, u2}, V = {v1, v2, v3} and W = {w1, w2, w3}.
• Vertices from V connected to vertices from W except for v1w1
• v1v3 and w1w3
• u1 connected to every vertex except u2, v1 and w3.
• u2 connected to every vertex except u1, w1 and v3.
An independent 3-set cannot have u1 because its non-neighbors form the triangle
v1u2w3. By symmetry, it cannot have u2 either. Similarly, it cannot have v1 because its
non-neighbors form the triangle u1v2w1 and by symmetry it cannot have w1 either. It
cannot have w3 and v3 too because they only have 2 non-neighbors. Since we only have
2 vertices left, we do not have 3K1 as an induced subgraph. A clique on 4 vertices can
have at most one vertex from U . If we take one then we have to take two from V or from
W . Without loss of generality, we may assume they are taken from V . However, no two
connected vertices from V share a neighbor in U . If we do not take a vertex from U , then
we take two from V and two from W . We are forced to select v1, v3, w1 and w3. But
v1w1 is not an edge. We have shown that a K4 and a 3K1 are impossible, and then we
have obtained the desired lower bound.
As a remark, the example shown in the proof is different from the usual example that
shows R(3, 4) ≥ 9.
3.3 Linear fractional Turán-type theorem
In this section we provide the proof of Theorem 3.6. We begin by proving that the linear
chromatic bound implies the linear bound for Turán numbers.
Proof of Theorem 3.6. Suppose that G ∈ G has n vertices and ω(G) = r. By hypothesis
χ(G) ≤ cr. Then we can partition the vertices of G in cr independent classes A1, A2, . . .,
Acr. For two classes Ai and Aj let Gi,j denote the subgraph of G induced by Ai ∪ Aj.
Since the family is closed under induced subgraphs, then Gi,j is in G for every pair of
indices. Moreover, since it is a bipartite graph by the second condition we have that
|E(Gi,j)| ≤ d(|Ai|+ |Aj|).
52 CHAPTER 3. FRACTIONAL TURÁN-TYPE THEOREMS
Then
|E(G)| =
∑
1≤i<j≤cr
|E(Gi,j)| ≤
∑
1≤i<j≤cr
d(|Ai|+ |Aj|) =
d(cr − 1)
cr∑
i=1
|Ai| = d(cr − 1)n ≤ dcrn
This means we can set C = dc to get a linear bound on Turán numbers as it is stated
in Theorem 3.6.
Suppose now that we have linear Turán numbers and that C is the constant in the
hypothesis. We will prove that a linear Turán-type theorem holds. Let α ∈ (0, 1) be a
real number and let G be a graph on n vertices. We may assume n ≥ 3. If we suppose
|E(G)| ≥ α
(
n
2
)
then
|E(G)| ≥ α
(
n
2
)
= C · α(n− 1)
2C
· n > C
αn
4C
· n.
We claim that ω(G) ≥ α
4C
· n. Otherwise, ω(G) ≤
⌊
αn
4C
⌋
. Using the bound on Turán
numbers we have
|E(G)| ≤ Cn
⌊αn
4C
⌋
≤ C · αn
4C
· n,
and this is a contradiction to the inequality obtained above. Then we have ω(G) ≥ αn
4C
.
This proves that we have a linear Turán-type theorem with β = 1
4C
.
We are only left to prove that a linear Turán-type theorem implies a linear chromatic
bound. Suppose we have a family G with a linear Turán-type theorem and let G be a
graph in G with n vertices. We may assume that β < 1. We consider α = 2|E(G)|
n2 . Notice
α < 1.
Since |E(G)| = α · n2
2
> α
(
n
2
)
, then we can use the linear Turán-type condition to get
ω(G) ≥ αβ · n =
2α · |E(G)|
n
or
3.4. A BOUND FOR THE CHROMATIC NUMBER 53
|E(G)| ≤ ω(G)
2β
· n. (3.1)
If G is bipartite, then (3.1) gives |E(G)| ≤ n
β
, which is one of the required bounds.
To bound χ(G) we will prove by induction on n that χ(G) ≤ 2
β
· ω(G). If G has just
one vertex then we have to prove 1 ≤ 2
β
, which follows from β ≤ 1.
Suppose now that the statement holds for graphs with less than n vertices and suppose
G has n vertices. We know that 2|E(G)|
n
is the average degree. Therefore, by (3.1) the
average degree is less than or equal to ω(G)
β
and therefore there is a vertex v with degree
at most ωG
β
.
The graph G− v has fewer vertices and it is in G. Then, by the inductive hypothesis
χ(G − v) ≤ 2ω(G−v)
β
≤ 2ω(G)
β
. We color G using at most 2ω(G)
β
colors. Since deg(v) ≤
ω(G)
β
< 2ω(G)
β
, we can color v properly. This finishes the proof.
3.4 A bound for the chromatic number
In this section we show that we can make the coefficient of |V (G)| in Proposition 3.1 as
small as desired. Afterwards, we use this inequality to obtain conditions for a Turán-type
result that makes the clique number go to infinity.
Proof of Proposition 3.2. Let m be the least positive integer such that 1
m
< ǫ. Let G be
a graph with clique number r. Consider the Ramsey number R(r+1,m) (see Subsection
3.2.3). We will prove that the following holds:
χ(G) ≤ ǫ · |V (G)|+R(r + 1,m).
Since χ(G) ≤ |V (G)|, the result is immediate if |V (G)| ≤ R(r + 1,m). Otherwise,
|V (G)| > R(r + 1,m). In this case, we write |V (G)| = qm + s + R(r + 1,m) where q is
a positive integer and s is a number in {0, 1, . . . ,m − 1}. By Ramsey’s theorem we can
find either a complete subgraph on r+ 1 vertices or an independent graph on m vertices.
However, the clique number is r, so the first option is impossible. Therefore, we can find
an independent set A1 of m vertices.
54 CHAPTER 3. FRACTIONAL TURÁN-TYPE THEOREMS
If we repeat the argument, we can find q disjoint sets of independent vertices A1, A2,
. . ., Aq+1 each one consisting of m vertices. We can use a color for each of these sets. For
the rest of the vertices, we need at most R(r + 1,m) + (s −m) more colors, so we have
provided a coloring that uses at most q + 1 + s−m+R(r + 1,m) colors and
q + 1 + s−m+R(r + 1,m) ≤ q +R(r + 1,m) ≤ 1
m
· |V (G)|+R(r + 1,m).
Therefore χ(G) ≤ 1
m
· |V (G)|+R(r + 1,m), as desired.
We can now prove Theorem 3.7.
Proof. Suppose that the theorem does not hold. Therefore, we can find a real number
α ∈ (0, 1), an integer M and a graph G in G with as many vertices n as we desire such
that ω(G) ≤ M .
As in the proof of Theorem 3.6, we have that |E(G)| ≤ Cn · χ(G). By Proposition
3.2, for any ǫ > 0 we can find a fǫ such that
|E(G)| ≤ Cǫn2 + fǫ(ω) · n ≤ Cǫn2 + fǫ(M) · n.
On the other hand, by hypothesis we know that
|E(G)| ≥ α
(
n
2
)
.
This means
α
(
n
2
)
≤ Cǫn2 + fǫ(M) · n.
If we set ǫ < α
C
and n is large enough, we get a contradiction.
Chapter 4
Some algebraic results on lattice
path matroids
Lattice path matroids are a well-studied and fruitful class of matroids. They were intro-
duced by Bonin, de Mier and Noy in 2003. In this chapter we study “thin” lattice path
matroids which we call snakes. We use them as building blocks to prove the validity of a
1999 conjecture by Merino and Welsh for the whole class of lattice path matroids.
This is a joint work with Kolja Knauer and Jorge Luis Ramı́rez Alfonśın. The content
of this chapter is based on the preprint [44].
4.1 Introduction
In this chapter we are interested in a conjecture relating some values of the Tutte poly-
nomial of a graph or a matroid. For a graph G, let τ(G) be the number of spanning trees
of G. Let α(G) be the number of acyclic orientations and α∗(G) the number of totally
cyclic orientations of G. The following conjectures have been raised in [22] and [52]:
Conjecture 4.1 (Graphic Merino-Welsh conjectures). For any 2-connected and loopless
graph G we have:
1. max (α(G), α∗(G)) ≥ τ(G).
2. (Additive) α(G) + α∗(G) ≥ 2 · τ(G).
3. (Multiplicative) α(G) · α∗(G) ≥ τ(G)2.
55
56 CHAPTER 4. SOME ALGEBRAIC RESULTS ON LATTICE PATH MATROIDS
Notice that Conjecture 4.1.3 is the strongest version since it implies Conjecture 4.1.2,
which in turn implies Conjecture 4.1.1. Nevertheless, the multiplicative version turns out
to be the most manageable. There are many partial results concerning these conjectures
in [20], [22], [52], [58] and [65]. As noticed in [22] and [52] Conjecture 4.1 can be stated
in terms of the Tutte polynomial TG of the graph G since
τ(G) = TG(1, 1), α(G) = TG(2, 0) and α∗(G) = TG(0, 2)
Thus we have the following natural generalization for matroids:
Conjecture 4.2 (Matroidal Merino-Welsh conjectures). Let M be a matroid without loops
or coloops and TM its Tutte polynomial. Then:
1. max (TM(2, 0), TM(0, 2)) ≥ TM(1, 1).
2. (Additive) TM(2, 0) + TM(0, 2) ≥ 2 · TM(1, 1).
3. (Multiplicative) TM(2, 0) · TM(0, 2) ≥ TM(1, 1)2.
Notice that not allowing loops and coloops is a fundamental hypothesis for the mul-
tiplicative version since a loop would imply T (2, 0) = 0 and a coloop would imply
T (0, 2) = 0.
The validity of Conjecture 4.2.1 for paving and Catalan matroids is proved in [20]. In
both cases it was assumed that the ground set either contains two disjoint bases or it is
the union of two bases.
The main contribution of this paper is to prove the validity of Conjecture 4.2.3 for the
class of lattice path matroids. This family contains, in particular, the family of Catalan
matroids.
Theorem 4.1. Let M be a loopless-coloopless lattice path matroid that is not a direct sum
of trivial snakes. Then
TM(2, 0) · TM(0, 2) ≥ 4
3
· TM(1, 1)2.
Our theorem is an improvement by a multiplicative constant, and thus it directly
implies the multiplicative version of Conjecture 4.2. Furthermore, it helps to characterize
the cases in which equality holds (Corollary 4.2).
The basic definitions from matroid theory can be found in the Appendix. In Section
4.2, we introduce lattice path matroids. We define snakes, which are matroids that can
4.2. LATTICE PATH MATROIDS AND SNAKES 57
be thought of as “thin” lattice path matroids. We provide a characterization of snakes
implying that they are graphic matroids. We also provide explicit formulas for the number
of trees, acyclic orientations and totally cyclic orientations of snakes.
Finally, in Section 4.3 we prove our main result (Theorem 4.1).
4.2 Lattice path matroids and snakes
In this section we address the class of lattice path matroids first introduced by Bonin,
de Mier, and Noy [15]. We define them following the description of Bonin and de Mier
[14]. Many different aspects have been studied for this class: minor results [13], algebraic
geometry notions [64, 63, 24], complexity of computing the Tutte polynomial [16, 67], and
results around the base matroid polytope [21, 19, 8].
The general idea is as follows. We are interested in lattice paths in the plane that start
at (0, 0) and that at each step either go North or East one unit. Sometimes we describe
such paths as a sequence of letters N and E.
Let m and r be two non-negative integers and let P and Q be two lattice paths that
start at (0, 0) and end at (m, r). Furthermore, suppose that P never goes above Q. Figure
4.1 shows an example. Now, consider a lattice path R from (0, 0) to (m, r) that lies neither
below P nor above Q. In order to get to the end, it must make exactly m East steps and
r North steps. So the indices in which North steps are made yield a r−subset of [m+ r].
If we consider all such r−subsets ranging over all the paths between P and Q, we get
a set of bases of a matroid on [m + r] of rank r. A matroid that can be constructed in
this way is called a lattice path matroid. Given P and Q, we usually name the matroid
M [P,Q]. From now on we abbreviate “lattice path matroid” as LPM.
(0,0)
(5,8)
P
Q
Q={1,4,5,9,10} 
Q=NEENNEEENENE
E
P={5,8,10,12,13} 
P=EEEENEENENENN
Figure 4.1: Lattice paths P and Q from (0, 0) to (5, 8) Representations of P and Q as
subsets of [5 + 8] and as words in the alphabet {E,N}.
It is known that LPMs are part of a larger family of matroids called transversal
58 CHAPTER 4. SOME ALGEBRAIC RESULTS ON LATTICE PATH MATROIDS
matroids. The k-Catalan matroid is the LPM M [P,Q] with P = {1, 3, . . . , 2k − 1} =
NENE · · ·NE
︸ ︷︷ ︸
k−pairs
and Q = {k + 1, k + 2, · · · , 2k} = E · · ·E
︸ ︷︷ ︸
k
N · · ·N
︸ ︷︷ ︸
k
.
We will later use the fact that an LPM is connected if and only if the paths P and
Q touch only at (0, 0) and (p, q). We can detect loops and coloops in the diagram. If P
and Q share a horizontal (resp. vertical) edge at step e, then e is a loop (resp. a coloop).
Therefore, loopless-coloopless LPMs are those in which P and Q do not share vertical or
horizontal edges. In particular, connected LPMs are LC.
In this paper we define a special class of LPMs, whose members are called snakes.
An LPM is called snake, if it can be represented by a diagram without interior lattice
points, as the one in Figure 4.2. Formally, a connected snake will be represented as
S(a1, a2, . . . , an) when it is the connected LPM that encloses a1 squares to the right, then
a2 squares up, then a3 squares to the right and so on, where the last square counted by
ai coincides with the first square counted by ai+1. Note that we are allowing some ai’s
to be equal to one (making no turn). Even though these snakes can be expressed with a
simpler expression, sometimes this flexibility in notation will be useful. We call S(1) the
trivial snake.
a1
a3
a4
a2
Figure 4.2: Notation for snakes.
The rest of this section is devoted to find exact formulas for some values of the Tutte
polynomial for snakes: T (S; 2, 0), T (S; 0, 2) and T (S; 1, 1). These formulas will be useful
in Section 4.3. In order to do this, we rather regard snakes as graphic matroids.
4.2. LATTICE PATH MATROIDS AND SNAKES 59
Theorem 4.2. If M is a connected lattice path matroid then the following statements are
equivalent
1. M is a snake.
2. M is graphic.
3. M is binary.
Proof. Let M be a connected snake. We prove that M is graphic. See Figure 4.3 for an
example. In the representation of M as transversal matroid, each row ri of the diagram
corresponds to an interval Ii consisting of the possible moments in which we may have
crossed the row upwards. Each two consecutive intervals share precisely one element.
We construct a graph G on r(M)+1 vertices: one vi for each row ri of the diagram and
a special vertex x. Now there is an edge vi ∼ vj corresponding to each element of Ii ∩ Ij.
Note that since M is a snake this is either 1 if i and j are consecutive or 0, otherwise.
Furthermore introduce for every i and every element contained only in Ii an edge vi ∼ x.
r1
r2
r3
r4 v1 v2 v3 v4
x
1 2 3 4
4 5
5 6 7
7 8
1 2
3
6 8
4 5 7
Figure 4.3: The graphic representation of a snake.
We show that the spanning trees of G are in bijection with transversals of I1, . . . , Ir(M).
Let T be a spanning tree of G. Let T be rooted at x and orient T away from x. Now,
associate the element corresponding to an edge of the tree to the vertex it is oriented
to. This is a mapping proving that the edges of T form a transversal of I1, . . . , Ir(M).
Conversely, given a transversal of I1, . . . , Ir(M), since I1, . . . , Ir(M) are intervals whose
sequences of left endpoints and right endpoints are strictly increasing, respectively, we
can associate it with the unique assignment, where elements are assigned in increasing
order to intervals in increasing order of left endpoints. Orienting the corresponding edges
towards the vertices they are assigned to gives a tree rooted at x: If there was a cycle,
two elements were assigned to the same Ii or some edge was directed towards x.
For the statements (2) and (3) we use two classical results in matroid theory [59]. If
M is graphic then it is binary. and M is not binary if and only if it contains U2,4 as a
minor (which is the case if M is not a snake since it M has an an interior point inducing
60 CHAPTER 4. SOME ALGEBRAIC RESULTS ON LATTICE PATH MATROIDS
locally an LPM M [P,Q] with P = NNEE and Q = EENN which corresponds to a U2,4
as a minor. Thus, M is not binary.
Theorem 4.2 clearly extends to disconnected LPMs. The proof of Theorem 4.2 suggests
that the graphs corresponding to snakes look like fans. This motivates the following
definition.
We call a graph F a multi-fan if there exist a positive integer ℓ and vectors a, b of
positive integers:
a = (a1, a2, . . . , aℓ)
b = (b1, b2, . . . , bℓ−1)
such that F consists of a path
P = (v11, . . . , v
b1
1 , v12, . . . , v
b2
2 , . . . , v1ℓ−1, . . . , v
bℓ−1
ℓ−1 , v
1
ℓ )
plus a vertex x with multi-edges of multiplicity ai ≥ 1 to each v1i . We denote the multi-fan
with these parameters by F (a, b). See Figure 4.4 for an example.
Note that the usual fan coincides with the multi-fan with parameters a = (1, 1, . . . , 1)
and b = (1, 1, . . . , 1). Also, a multi-fan is a series parallel graph created by alternately
adding parallel edges from x to the v1i ’s and adding series edges from each vi to vi+1. We
will make the correspondence between multi-fans and snakes more explicit in Corollary 4.1.
x
′
u
1
2
u
1
3
u
1
ℓ−1u
1
1
a
′
1
a
′
ℓ−1
b
′
2
b
′
ℓ−2
b
′
1
a
′
2
a
′
3
a
′
ℓ−2
x
v
1
2
v
1
3
v
1
ℓ−1
v
1
ℓ
v
1
1
a1
aℓ
b2 bℓ−1b1
a2
a3
aℓ−1
u
1
ℓ−2
Figure 4.4: Dual multi-fans.
We now provide exact formulas for the number of acyclic and totally cyclic orientations
of multi-fans.
4.2. LATTICE PATH MATROIDS AND SNAKES 61
Lemma 4.1. The number of acyclic orientations of F (a, b) is
2ℓ
ℓ−1∏
j=1
(
2bj − 1
2
)
.
Proof. For an acyclic orientation each bundle of ai multi-edges from x to v1i has to be
oriented either entirely from x to v1i or the other way around. The path of length bi
connecting v1i and v1i+1 creates a directed cycle if and only if the orientations of the
bundles form x to v1i and x to v1i+1 are opposite and the path on bi is completely directed
accordingly.
We associate a {0, 1}-vector z of length ℓ − 1, where zi = 0 if the bundles from x to
v1i and x to v1i+1 are oriented the same way and zi = 1, otherwise. Now we can count the
number of acyclic orientations.
If ℓ > 1 then we have
2
∑
z∈{0,1}ℓ−1
ℓ−1∏
i=1
(2bi − zi),
orientations and if ℓ = 1 we have 2.
We prove that this equals the claimed value by induction on ℓ. If ℓ = 1 then both
formulas give 2. For a more natural induction base suppose ℓ = 2. Now the first formula
gives 2(2b1 − 1 + 2b1) which coincides with the claimed formula being: 22(2b1 − 1
2
). The
induction works by splitting the set of vectors z in the sum into those having zl−1 = 1
and those having zl−1 = 0 that ordinate 0. We obtain:
2
∑
z∈{0,1}ℓ−1,zl−1=1
ℓ−2∏
i=1
(2bi − zi)(2
bℓ−1 − 1) + 2
∑
z∈{0,1}ℓ−1,zl−1=0
ℓ−2∏
i=1
(2bi − zi)2
bℓ−1 ,
which after applying induction hypothesis yields:
2ℓ−1
ℓ−2∏
j=1
(
2bj − 1
2
)
((2bℓ−1 − 1) + 2bℓ−1).
Since ((2bℓ−1 − 1) + 2bℓ−1) = 2(2bℓ−1 − 1
2
) we obtain the result.
62 CHAPTER 4. SOME ALGEBRAIC RESULTS ON LATTICE PATH MATROIDS
It is immediate to check the following observation (via planar duality).
Observation 1. Denote by δ1 := min(1, a1 − 1) and δℓ := min(1, aℓ − 1). Then omitting
0-terms from the sequences a′ = (δ1, b1 + 1 − δ1, . . . , bℓ−1 + 1 − δℓ, δℓ) and b′ = (a1 −
1, a2, . . . , aℓ − 1) yields: F (a, b)∗ = F (a′, b′).
Since acylicity and total cyclicity are dual in the plane, Lemma 4.1 and Observation 1
yield to the following.
Lemma 4.2. The number of totally cyclic orientations of F (a, b) is
2ℓ+1
(
2a1−1 − 1
2
)(
2aℓ−1 − 1
2
) ℓ−1∏
j=2
(
2aj − 1
2
)
.
Now we translate this results to snakes. As a consequence of the proof of Theorem 4.2
we get the following:
Corollary 4.1. A connected LPM is a snake iff it is the cycle matroid of a multi-fan.
Proof. Consider a connected snake S(a1, . . . , an). We may suppose without loss of gen-
erality that that n is odd, otherwise, we may add a 1 at the end without changing the
snake. Theorem 4.2 provides a construction that shows that the matroid of this snake is
equivalent to the cycle matroid of the multi-fan F (a, a′), where
a = (a1, a3 − 1, . . . , an−2 − 1, an)
a′ = (a2 − 1, a4 − 1, . . . , an−1 − 1).
For the converse, the cycle matroid of a multi-fan is graphic, and thus by Theorem 4.2
it is a snake.
Combining Lemma 4.1, Lemma 4.2 and Corollary 4.1 we obtain
Proposition 4.1. For any positive integers n, a1, . . ., an we have
T (S(a1, . . . , an), 0, 2) · T (S(a1, . . . , an), 2, 0)) = 22
n∏
i=1
(2ai − 1). (4.1)
4.2. LATTICE PATH MATROIDS AND SNAKES 63
Now we turn our attention to T (S; 1, 1). We will count the number of bases of a snake
directly from its diagram. Let F (n) be the set of all binary sequences b = (b1, . . . , bn) of
length n such that there are no two adjacent 1’s.
Proposition 4.2. For any positive integers n, a1, . . ., an we have
T (S(a1, . . . , an), 1, 1) =
∑
b∈F (n+1)
n∏
i=1
(ai − 1)1−|bi+1−bi| (4.2)
Furthermore, the following recursion holds:
T (S(a1, . . . , an), 1, 1) = T (S(a1, . . . , an−1), 1, 1)+
(an − 1)T (S(a1, . . . , an−1 − 1), 1, 1).
(4.3)
Proof. Consider the snake S(a1, . . . , an). If n = 1 and a1 = 1, on both sides of the
equation we have 2. In any other case, the snake has at least two squares. By duality, we
may suppose that the snake starts with two adjacent horizontal squares.
We will label some points with 0’s and 1’s on paths P and Q. As we explain the
labeling, Figure 4.5 may be used as a reference for the case n = 4. We label as follows.
On the snake consider C1 the first square, Cn+1 the last square and for each i ∈ {2, . . . , n}
let Ci be the (i− 1)-th square in which the snakes changes direction. For each square Ci
let ui be its upper left vertex and vi its lower right vertex. We label each ui with 1 if i is
odd and with 0 if i is even. We label each vi with the label opposite to the one in ui.
Consider a lattice path. For each i ∈ [n+1] this lattice path has to go through exactly
one of the vertices ui, vi. Therefore, for each lattice path we can assign a binary sequence
of length n+ 1. We claim that the formula in Equation 4.2 counts the number of lattice
paths according to their corresponding binary sequences.
First, it is impossible to go consecutively from a vertex labeled 1 to another vertex
labeled 1. Therefore all the possible binary sequences are in F (n + 1). Now we take a
binary sequence B = (b1, . . . , bn+1) and we count to how many lattice paths it corresponds.
Consider the segment of the path that goes from the vertices in square Ci to the vertices
in square Ci+1.
• If we go from the vertex with label 0 to the vertex with label 1 or vice versa, there
is exactly one way in which we can do it.
• There are exactly ai − 1 ways to go from the vertex with label 0 to the vertex with
label 0.
64 CHAPTER 4. SOME ALGEBRAIC RESULTS ON LATTICE PATH MATROIDS
C1
C
3 C
C2
C5
4
1
0
0
1
1
0
0
1
1 0
Figure 4.5: Labeling of zeros and ones of S(a1, a2, a3, a4).
Thus if the binary sequence is B, we can go from the vertices in Ci to the vertices in
Ci+1 in (ai − 1)1−|bi+1−bi| ways, and therefore there are
n∏
i=1
(ai − 1)1−|bi+1−bi|
lattice paths with corresponding sequence equal to B. This shows that the formula is
correct.
The recursive formula can be proved using Equation (4.2), but we provide a combi-
natorial proof. To do so we verify whether the lattice path has gone through the upper
right vertex of Cn or not. If it did, by definition there are T (S(a1, . . . , an−1), 1, 1) ways
of getting to that vertex and then the path to the end is completely defined. If it did
not, then in square Cn the path has to go through the vertex with label 0, which can be
done in S((a1, . . . , an−1 − 1), 1, 1) ways. This has to be multiplied by the an − 1 ways to
complete the path avoiding the upper right vertex of Cn. This completes the argument.
Notice that when a1 = a2 = . . . = an = 2 we are summing only 1’s over all the
sequences of F (n + 1). It is a folklore result that the number of such sequences is the
Fibonacci number Fn+3, and thus Proposition 4.2 can be regarded as a lattice path gen-
eralization of this. Indeed, the fact that the number of spanning trees of fans is counted
by Fibonacci numbers has been verified several times, see e.g. [37].
As a helpful remark that will be used later on, the formulas in Propositions 4.1 and
ro---
~ 
I I 
D 
4.3. THE MERINO-WELSH CONJECTURE FOR LATTICE PATH MATROIDS 65
4.2 are also valid if an is equal to 1. To verify this we have two cases. If n = 1 then indeed
we have
T (S(1), 1, 1) = 2 and T (S(1), 0, 2) · T (S(1), 2, 0) = 4.
If n > 1, then the snake is the same as snake S(a1, . . . , an−1). The formula in Equation
(4.1) remains unchanged because it gets an extra factor equal to 22− 1 = 1 and Equation
(4.2) remains unchanged because the extra terms in the sum are equal to 0.
4.3 The Merino-Welsh conjecture for lattice path ma-
troids
We will now prove that the strongest version of Conjecture 4.2 is true for lattice path
matroids. Notice that equality may hold. An easy example is the trivial snake. Since the
Tutte polynomial opens direct sums as products, it is immediate to see that a direct sum
of trivial snakes also yields equality.
More specifically, in this section we prove Theorem 4.1 which is an improvement of
the desired inequality by a constant factor except for the trivial cases mentioned above.
We provide an inductive proof. The strategy is as follows:
• We prove the theorem for connected snakes.
• We show that any connected LPM M either is a connected snake, or it has an
element e such that both M \ e and M/e are connected LPM with fewer elements.
• We state a straightforward lemma for proving the inequality for M from the veracity
of the inequality for M \ e and M/e.
• We extend the result to disconnected but LC LPM.
Before starting with the first step in the strategy, let us make a remark. In Section
4.2 we have shown that snakes are series parallel graphic matroids. Therefore, Conjecture
4.2.3 can be proven for snakes using the result in [58]. However, for the whole strategy to
work we will need to first prove the sharper inequality for snakes. Thus we will need the
precise results on the Tutte polynomial provided by Proposition 4.1 and Proposition 4.2.
Proposition 4.3. If M is a connected non-trivial snake, then
66 CHAPTER 4. SOME ALGEBRAIC RESULTS ON LATTICE PATH MATROIDS
TM(2, 0) · TM(0, 2) ≥ 4
3
· TM(1, 1)2.
Proof. We proceed by induction on n. If n = 1, then the snake is a unit strip. Call
its length a. Since the snake non-trivial we have a ≥ 2. Now, T (1, 1) is the number of
allowed lattice paths which is clearly a+ 1. By Equation 4.1, we have to prove that
4 · (2a − 1) ≥ 4
3
· (a+ 1)2
Since a ≥ 2, we have a2 ≥ a+ 2. Using the binomial formula we get
4 · ((1 + 1)a − 1) ≥ 4 ·
(
1 + a+
a(a− 1)
2
− 1
)
= 2a2 + 2a =
4
3
· a2 + 2
3
· a2 + 2a ≥ 4
3
· a2 + 2
3
· (a+ 2) + 2a
=
4
3
· (a2 + 2a+ 1) =
4
3
· (a+ 1)2.
We need another inductive base: the snakes S(2, a). Using Equations 4.1 and 4.2, we
need to prove that
4 · 3 · (2a − 1) ≥ 4
3
· (2a+ 1)2.
Recall that a ≥ 2. Using the binomial formula again we have
4 · 3 · (2a − 1) ≥ 12 ·
(
1 + a+
a(a− 1)
2
− 1
)
= 6a2 + 6a =
4
3
· (4a2 + 4a) +
2
3
(a2 + a) ≥ 4
3
· (4a2 + 4a+ 1)
=
4
3
· (2a+ 1)2.
This proves our induction bases. We now suppose that the conclusion is true for
1, 2, . . . , n − 1 and we consider the snake S(a1, . . . , an−1, b). Recall that b ≥ 2. Using
Equation 4.3, we have that:
4.3. THE MERINO-WELSH CONJECTURE FOR LATTICE PATH MATROIDS 67
T (S(a1, . . . , b), 1, 1) = T (S(a1, . . . , an−1), 1, 1)+
(b− 1) · T (S(a1, . . . , an−1 − 1), 1, 1).
Now we want to use the inductive hypothesis. We should be careful because an−1 − 1
may become 1. Nevertheless, if n ≥ 3 the remark after Proposition 4.2 takes care of this
detail. If n ≤ 2, then we fall in the second inductive case. Thus, we can always conclude
that T (S(a1, . . . , b), 1, 1) is less than or equal to
√
3
2
· 2 ·
n−1∏
i=1
(2ai − 1)1/2 +
√
3
2
· (b− 1) · 2 · (2an−1−1 − 1)1/2 ·
n−2∏
i=1
(2ai − 1)1/2
which can be factorized as
√
3
2
· 2 ·
(
n−2∏
i=1
(2ai − 1)1/2
)
·
(
(2an−1 − 1)1/2 + (b− 1) · (2an−1−1 − 1)1/2
)
.
Therefore, to get the two extra factors that we need it will be enough to prove that
for any an−1 ≥ 2 and b ≥ 2 we have
(2an−1 − 1)1/2 + (b− 1) · (2an−1−1 − 1)1/2 ≤ (2an−1 − 1)1/2 · (2b − 1)1/2
Dividing both sides by (2an−1 − 1)1/2 this becomes
1 +
b− 1√
2
·
(
1− 1
2an−1 − 1
)1/2
≤ (2b − 1)1/2.
We will prove that for b ≥ 2 the following stronger inequality holds
1 +
b− 1√
2
≤ (2b − 1)1/2.
By the binomial formula, 2b ≥ 1 + b+ b(b−1)
2
. Therefore
2b − 1 ≥ b2 + b
2
≥ b2
2
+
(√
2− 1
)
b+
3
2
−
√
2 =
(
1 +
b− 1√
2
)2
.
68 CHAPTER 4. SOME ALGEBRAIC RESULTS ON LATTICE PATH MATROIDS
This proves the desired inequality and thus the proposition follows by induction.
Proposition 4.4. Let M be a connected LPM. Then either
• M is a snake or
• M has an element e such that both M \ e and M/e are connected LPM different
from the trivial snake.
Proof. Suppose that M = M [P,Q] is a connected LPM that is not a snake. Consider the
interior lattice point of M that is highest and rightmost. Suppose that it is B = (b1, b2).
We claim that e = b1 + b2 + 1 is the required element of M . To prove this, it is enough
to show that for every element f 6= e of M there is:
• a base with both e and f
• a base with e without f
• a base with f without e
• a base without f and e
We will find these bases, but we need to introduce some notation. Figure 4.6 depicts
the situation. In this figure we have drawn the paths P and Q. We have also labeled X,
the first point in path P with x-coordinate equal to b1. Similarly, Y is the first point in
path Q with y-coordinate equal to b2. Furthermore, we define
A = B + (−1, 1) C = B + (1,−1) D = B + (1, 0) E = B + (0, 1) O = (0, 0)
From point B to the end we have a snake S because B was the top-right interior point.
By duality, we may assume this snake goes to the right. Notice that e can be found in
the figure exactly twice: as the segment from B to D and as the segment from C to E.
Consider an element f . We want to find bases that have any combination of elements e
and f .
We will first deal with the elements f < e. For this consider the path P ′ that on P
goes from O to X and then goes directly to B. Consider also the path Q′ that on Q goes
from O to Y and then goes directly to B. All the horizontal segments of P before X
are strictly below segment BY . Also, all the vertical segments of Q before Y are strictly
4.3. THE MERINO-WELSH CONJECTURE FOR LATTICE PATH MATROIDS 69
O
Q
P
X
C
e
e
D
B
Y
A
E
Figure 4.6: Lattice path matroid with interior point.
to the left of BX. Therefore the matroid M ′ = M [P ′, Q′] does not have any loops or
coloops. Let Kf and Lf be lattice paths in M ′ with and without f respectively. After
reaching B we can decide to continue each of these lattice paths using e or not. Therefore
we have found the desired bases.
The only case left is f > e. The snake S is LC, and therefore we now consider paths
Kf and Lf with respect to S. This time to extend Kf and Lf we may need to make some
adjustments. We know that f is in Kf . If Kf goes through D (resp. E) then e is (resp.
is not) in Kf . If we want a base of M which does this, we complete Kf with an arbitrary
path from O to B. If we want that e is not (resp. is) in the base, then we take Q (resp.
P ) until we get to D (resp. E) and then continue through Kf . This new path avoids
(resp. goes through) e and goes through f . The argument is analogous for Lf .
We also have to check that M \ e and M/e are not the trivial snake. This is easy,
because a matroid with an interior point has at least 4 elements, and thus M \ e and M/e
have at least 3 elements.
The following result is valid for matroids in general. A version without the 4
3
factor
~-
~ ---
r---
j--------------
D 
70 CHAPTER 4. SOME ALGEBRAIC RESULTS ON LATTICE PATH MATROIDS
has also appeared in [58] as Lemma 2.2. The following proof is slightly different, and we
include it for completeness.
Lemma 4.3. Let M be a loopless and coloopless matroid and let e be an element of its
ground set. Suppose that the inequality in Theorem 4.1 holds holds for M \e and for M/e.
Then the inequality also holds for M .
Proof. We define a, b, c, d, e, f as follows:
a = TM\e(2, 0), b = TM\e(0, 2), c = TM\e(1, 1)
d = TM/e(2, 0), e = TM/e(0, 2), f = TM/e(1, 1)
Since M is loopless and coloopless, we have that TM(x, y) = TM\e(x, y) + TM/e(x, y).
Therefore, we have to prove that
(a+ d)(b+ e) ≥ 4
3
· (c+ f)2
By hypothesis, we know that a · b ≥ 4
3
· c2 and that d · e ≥ 4
3
· f 2. Combining this and
the Cauchy-Schwartz inequality we conclude as follows:
(a+ d)(b+ e) ≥
(√
ab+
√
de
)2
≥ 4
3
· (c+ f)2.
We are ready to prove our main result.
Proof of Theorem 4.1. First we prove the theorem for connected LPMs. In this proof we
will only refer to LPMs different from the trivial snake. We proceed by induction on the
number of elements. If the matroid has three elements, then it is S(2), for which we know
the theorem is true.
Now suppose that the theorem is true for connected LPM of less than n elements.
Let M be a connected LPM with n elements. If M is a snake, then by Proposition 4.3
the inequality holds. Otherwise, by Proposition 4.4 we can find an element e such that
both M \ e and M/e are connected LPM. Each of these has less elements than M , and
thus by the inductive hypothesis the inequality holds for both of them. Therefore using
Lemma 4.3 we conclude that the inequality also holds for M . This completes the proof
for connected LPM.
4.3. THE MERINO-WELSH CONJECTURE FOR LATTICE PATH MATROIDS 71
We only are left with the case in which M is LC, but is not connected. In this case
we express M as the direct sum of connected LPMs M1, M2, . . ., Mn. By hypothesis at
least one of them, say M1, is not the trivial snake. For each i ∈ [n] let
ai = TMi
(2, 0), bi = TMi
(0, 2), ci = TMi
(1, 1).
We know that a1 · b1 ≥ 4
3
· c1 and that for each i in {2, 3, . . . , n} we have ai · bi ≥ c2i .
Using that the Tutte polynomial of a direct sum is the product of the Tutte polynomials
we get:
TM(2, 0) · TM(0, 2) =
n∏
i=1
ai ·
n∏
i=1
bi =
n∏
i=1
(ai · bi)
≥ 4
3
·
n∏
i=1
c2i =
4
3
·
(
∏
i=1
ci
)2
=
4
3
· TM(1, 1)2.
Therefore the inequality is true for every LC LPM that is not a direct sum of trivial
snakes.
Theorem 4.1 immediately yields the following corollary which confirms the multiplica-
tive Merino-Welsh conjecture for LPMs.
Corollary 4.2. Let M be an LC LPM. Then
TM(2, 0) · TM(0, 2) ≥ TM(1, 1)2.
and equality holds if and only if M is a direct sum of trivial snakes.
Chapter 5
Kneser transversals
In 2010, Arocha, Bracho, Montejano and Ramı́rez-Alfonśın posed the following two prob-
lems [7]. Let d, λ and k be positive integers.
• What is the minimum number of points in Rd so that no matter how we choose
them it is impossible to find a common (d− λ)- transversal plane to all the convex
hulls of k-sets of the set of points?
• What is the maximum number of points in Rd so that no matter how we choose
them it is possible to find a common (d − λ)- transversal plane to all the convex
hulls of k-sets of the set of points?
They completely solved the first problem. Concerning the second problem, they dis-
covered an interesting with two classic problems: determining the chromatic number of
Kneser hypergraphs and Rado’s central point theorem. They obtained upper and lower
bounds for the second problem and left some conjectures and problems open.
In this chapter we continue the work concerning the second problem. We introduce a
discrete variant that can be studied using the theory of oriented matroids. We provide
some bounds for this new problem and we solve it asymptotically when the points are the
vertices of a cyclic polytope.
This is a joint work with Jonathan Chappelon, Luis Montejano Peimbert, Luis Pedro
Montejano Cantoral and Jorge Luis Ramı́rez Alfonśın. The results have been presented
in the VIII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS
2015). An extended abstract of the presentation [18] is to be published by Electronic
Notes in Discrete Mathematics.
73
74 CHAPTER 5. KNESER TRANSVERSALS
5.1 Introduction
5.1.1 Background
In [7] the following function was introduced and studied. Let k, d, λ ≥ 1 be integers with
both d, k ≥ λ. Let
m(k, d, λ)
def
= The maximum positive integer n such that every set of n points (not
necessarily in general position) in Rd has the property that the convex
hulls of all k-sets have a common transversal (d− λ)-plane.
For this function, the following bounds were obtained
d− λ+ k +
⌈
k
λ
⌉
− 1 ≤ m(k, d, λ) < d+ 2(k − λ) + 1. (5.1)
An interesting feature of the value of m(k, d, λ) is its strong connection with the
chromatic number of Kneser hypergraphs [45, 47] as well as with Rado’s central Theorem
[60]. Indeed, for the former it is proved in [7, Theorem 1, Corollary 1] that
if m(k, d, λ) < n, then d− λ+ 1 < χ(KGλ+1(n, k)).
For the latter, recall that the well-known Rado’s central point theorem [60] states that
if X is a bounded measurable set in Rd then there exists a point x ∈ Rd such that
measure(P ∩X) ≥ measure(X/(d+ 1))
for each half-space P that contains x (see also [57] for the case d = 2).
In [17, Section 6], Bukh and Matousek consider the following generalization of a dis-
crete version of Rado’s central point theorem. Let n, d, λ ≥ 1 be integers with d ≥ λ and
let
τ(n, d, λ)
def
= The maximum positive integer τ such that for any collection X of n
points in Rd, there is a transversal (d− λ)-plane LX such that any
closed half-space H through LX contains at least τ points..
5.1. INTRODUCTION 75
By the hyperplane separation theorem we have that n− τ(n, d, λ) + 1 is equal to the
minimum positive integer k such that for any collection X of n points in Rd there is a
common transversal (d − λ)-plane to the convex hulls of all k-sets, which is essentially
m(k, d, λ).
The lower bound of equation (5.1) lead to the following result [7, Theorem 2].
Let X be a finite set of n points in Rd. Then there is a (d− λ)-plane L such that
(5.2)
any closed half-space H through L contains at least
⌊
n− d+ 2λ
λ+ 1
⌋
+ (d− λ) points.
As remarked in [69], Rado’s central point theorem can also be obtained by using the
well-known Tverberg’s generalization of Rado’s Theorem [68]. Tverberg-type results on
flat transversal are natural strengthenings of the central (flat) transversal theorem and
thus they are closely related to our work.
Additionally, [7, Conjecture 1] states that
m(k, d, λ) = d− λ+ k +
⌈
k
λ
⌉
− 1 (5.3)
and it was remarked [7, Corollary 3] that (5.2) is sharp if (5.3) holds. Therefore, any
improvement to the lower or upper bounds for m(d, λ, k) will give important insight on
the above interesting problem.
5.1.2 Complete Kneser transversals
The purpose of this paper is to introduce and study a discrete version of the function
m(k, d, λ).
Let k, d, λ ≥ 1 be integers with d ≥ λ. Let X ⊂ Rd be a finite set and let L be a
(d−λ)-plane transversal to the convex hull of all k-sets of X. We say that L is a complete
Kneser (d− λ)-transversal if it contains (d− λ) + 1 points of X. Let us define
76 CHAPTER 5. KNESER TRANSVERSALS
m∗(k, d, λ)
def
= The maximum positive integer n such that every set of n points (not
necessarily in general position) in Rd has the property that the convex
hulls of all k-sets have a complete Kneser (d− λ)-transversal..
This is a natural discrete version of the original function m. Indeed, consider a set of
points X in Rd. The existence of an arbitrary (d−λ)-plane transversal to the convex hull
of the k-sets of X is not an invariant of the order type. For example, if d = 2 and X is
the vertex set of a regular hexagon then the center is a 0-plane transversal to the convex
hull of the 4-sets. But by suitably perturbing these 6 points slightly we lose this property.
On the other hand, the existence of a complete Kneser (d − λ)-transversal to the
convex hull of the k-sets is an invariant of the order type (see Propositions 5.1 and 5.2).
This allow us to study m∗ using matroid theory. Since the function m∗ requires extra
conditions than m on the needed transversals, we clearly have
m∗(k, d, λ) ≤ m(k, d, λ).
It turns out that the function m∗ has two different behaviors. The arguments for the
case λ− 1 ≥
⌈
d
2
⌉
are usually simpler than those used when λ− 1 <
⌈
d
2
⌉
. For this reason,
we define
α(d, λ) =
λ− 1
⌈d
2
⌉
and we call α ≥ 1 the trivial range and α < 1 the non-trivial range.
5.1.3 Outline of chapter and results
This chapter is organized as follows. In Section 5.2 we provide tools from convex geometry
to detect complete Kneser transversals by using Radon partitions. We find the following
lower bound for m∗.
Theorem 5.1. In the non-trivial range, when α(d, λ) < 1, we have that
(d− λ+ 1) + k ≤ m∗(k, d, λ).
5.1. INTRODUCTION 77
In Section 5.3, after reviewing some basic notions on cyclic polytopes and alternat-
ing oriented matroids, we introduce the following function which is can be thought as
m∗(k, d, λ) for this particular family.
m∗(k, d, λ)
def
= The maximum number of vertices that the cyclic polytope in Rd can have,
so that it has a complete Kneser (d− λ)-transversal to the convex hulls of
its k-sets of vertices..
We clearly have
m∗(k, d, λ) ≤ ζ(k, d, λ).
In the trivial range we prove the following
Theorem 5.2. When α(d, λ) ≥ 1, we have that
m∗(k, d, λ) = ζ(k, d, λ) = d− λ+ k.
In particular, when α(d, λ) ≥ 1, the cyclic polytope of at least (d − λ + 1) + k points
does not have a complete Kneser (d− λ)-transversal to the convex hulls of its k-sets.
In order to obtain an upper bound for m∗(k, d, λ) when α(d, λ) < 1, we present explicit
upper and lower bounds for ζ(k, d, λ).
Theorem 5.3. In the non-trivial range, when α(d, λ) < 1,
z(k, d, λ) ≤ ζ(k, d, λ) ≤ Z(k, d, λ).
As a corollary we obtain that m∗(k, d, λ) ≤ Z(k, d, λ) in the non-trivial range. We end
Section 5.3 by showing that these bounds are asymptotically correct in terms of k.
Theorem 5.4. In the non trivial-range we have that
lim
k→∞
ζ(k, d, λ)
k
= 2− α(d, λ).
78 CHAPTER 5. KNESER TRANSVERSALS
We see that the latter easily yields
lim
d→∞
lim
k→∞
ζ(k, d, λ)
k
= 2,
that, together with a result of Bukh and Matousek [17], allow us to verify that if
α(d, λ) < 1 then m(k, d, 2) is not necessarily equal to m∗(k, d, 2).
Finally, in Section 5.4 we give exact values of m∗(k, d, λ). We show that
- (Theorem 5.5) if α(d, λ) < 1 and d
2
≤ k < 2
1−α(d,λ)
then
m∗(k, d, λ) = (d− λ+ 1) + k
- (Theorem 5.6)
m∗(k, d, 1) = d+ 2(k − 1)
implying that m∗(k, d, λ) = d − λ + k when α(d, λ) ≥ 1) (Corollary 5.3) and thus
obtaining that m∗(k, d, λ) < m(k, d, λ) when k > λ and α(d, λ) ≥ 1 (Corollary 5.4).
5.2 Kneser transversals from Radon partitions
The following proposition is a generalization of the well-known Carathéodory’s theorem
that states that if a point p lies in the convex hull of a set S in Rd, then there is a subset
S ′ of S consisting of at most d+1 points such that p lies in the convex hull of S. It is not
difficult to prove that the set S ′ has exactly d+1 points if the set S is in general position
in Rd.
Proposition 5.1. Let d and λ be positive integers with d ≥ λ and let S and T be two
disjoint sets of points in general position in Rd such that|S| ≥ λ+ 1 and |T | = d− λ+ 1.
Then the following two statements are equivalent:
• conv(S) ∩ aff(T ) 6= 0
• conv(S ′) ∩ aff(T ) 6= 0 for a subset S ′ ⊆ S such that |S ′| = λ+ 1.
Proof. The second statement clearly implies the first one. Now let p ∈ conv(S) ∩ aff(T )
and let U be the affine subspace through p that is perpendicular to aff(T ). Consider SU the
5.2. KNESER TRANSVERSALS FROM RADON PARTITIONS 79
projection of S to U . We have that p ∈ convSU and that U has dimension λ. Therefore,
by Carathéodory’s theorem, there is a (λ+1)-set of SU such that p lies in its convex hull.
This corresponds to a subset S ′ of S with λ+1 elements such that conv(S ′)∩ aff(T ) 6= 0,
as desired.
The following result will be very useful for the rest of the paper. We refer to the
Appendix for a review of Radon’s partition theorem.
Proposition 5.2. Let S and T be two disjoint and non-empty sets of points in general
position in Rd such that |S| + |T | = d + 2. Then conv(S) ∩ aff(T ) 6= ∅ if and only if all
the points of S are in the same set in the Radon partition of S ∪ T .
Proof. Let S ∪T = {v1, v2, . . . , vn+2} and let A∪B be the partition of {1, . . . , d+2} that
yields the Radon partition for S ∪ T . This means that there exist positive real numbers
α1, . . ., αd+2 such that
∑
i∈A
αi =
∑
i∈B
αi = 1
∑
i∈A
αivi =
∑
i∈B
αivi.
First suppose that all the elements from S get the same sign in the Radon partition
of S ∪ T . Without loss of generality, this means that if vi ∈ S, then i ∈ A. We may
therefore write:
∑
i∈A,vi∈S
αivi =
∑
i∈B
αivi −
∑
i∈A,vi∈T
αivi
Dividing by both sides of the equality by
∑
i∈A,vi∈S
αi, we get on the LHS a convex
linear combination of elements in S and on the RHS an affine linear combination of
elements in T . This shows that conv(S) ∩ aff(T ) 6= ∅.
Now suppose that conv(S)∩ aff(T ) 6= ∅. This means that there exists real numbers βi
such that
80 CHAPTER 5. KNESER TRANSVERSALS
βi ≥ 0 when vi ∈ S
∑
vi∈S
βivi =
∑
vi∈T
βivi
∑
i∈A
βi =
∑
i∈B
βi = 1.
We may rearrange the sum as
∑
vi∈S
βivi +
∑
vi∈T,βi<0
(−βi)vi =
∑
vi∈T,βi≥0
βivi
and dividing both sides of the equality by
∑
vi∈T,βi≥0 βi we get a convex linear combi-
nation on both sides. This induces a Radon partition of S ∪ T . Since the points are in
general position, this must be the same partition as the one induced by A∪B. Therefore
αi = βi and all the ai’s get the same sign.
As a consequence of this proposition we get the following lemma.
Lemma 5.1. Let X be any set of d+ 2 points in general position in Rd and let ⌊d+2
2
⌋ ≤
t ≤ d+ 1. Then X can be partitioned into two disjoint sets S and T such that
|T | = t and conv(S) ∩ aff(T ) 6= ∅.
Proof. By Radon’s Theorem the set X can be partitioned into two disjoint sets, A and B,
whose convex hulls intersect. We may suppose that |B| ≤ ⌊d+2
2
⌋ ≤ t since |A|+|B| = d+2.
If |B| = t, as conv(A) ∩ conv(B) 6= ∅, we have already finished the proof. If |B| < t, let
Y ⊆ A be such that |B| + |Y | = t. Let denote T = B ∪ Y and S = A \ Y , hence by
Proposition 5.2 we conclude that conv(S) ∩ aff(T ) 6= ∅.
5.2.1 A lower bound for m∗(k, d, λ) in the non-trivial range
First, we consider the case when the points are not in general position.
Lemma 5.2. Suppose α(d, λ) < 1 and let X be a collection of (d − λ + 1) + k points in
Rd such that no d+2 points of X are in general position in Rd. Then there is a complete
Kneser (d− λ)-transversal to the convex hulls of all k-sets of X.
5.2. KNESER TRANSVERSALS FROM RADON PARTITIONS 81
Proof. First of all note that 2λ < d+ 2 if and only is α(d, λ) = λ−1
⌈ d
2
⌉
< 1. We may assume
that k > λ, otherwise the theorem is trivial, because it is easy to see that m∗(k, d, k) =
d + 1. We shall prove the lemma by induction on d. If d = 1 (then λ ≤ 1), it is not
difficult to see that the lemma holds for any integer k > λ. Assume we have proven the
lemma for every integer d′ < d, and every integers λ′, k′ with k′ > λ′ and 2λ′ < d′ + 2.
Let X be a collection of (d− λ+ 1) + k points in Rd with k > λ and 2λ < d+ 2, and
no d + 2 points of X in general position in Rd. We will prove that there is a complete
Kneser (d − λ)-transversal to the convex hulls of all k-sets. First suppose that X is
contained in Rd−i for some i ≥ 1. Taking d′ = d − i and λ′ = λ − i, one can check that
|X| = d′−λ′+1+ k with k > λ′ and 2λ′ < d′+2. Then, by induction there is a complete
Kneser (d′ − λ′)- transversal to the convex hulls of all k-sets of X and lemma holds since
d′ − λ′ = d− λ.
Now suppose that X is not contained in Rd−i for every i ≥ 1. As X ⊆ Rd, there
exist d+ 1 points of X forming a simplex ∆ in Rd. Let F be the set of faces of ∆, since
|X| ≥ d + 2 and as no d + 2 points of X are in general position in Rd, then there exist
F ∈ F such that aff(F ) contains at least d+ 1 points of X. Let X ′ = X ∩ aff(F ), then it
follows that |X ′| = d − λ + k − j where 0 ≤ j ≤ k − λ − 1. Let d′ = d − 1, λ′ = λ − 1
and k′ = k − (j + 1), then |X ′| = d′ − λ′ + 1 + k′. As k′ > λ′ and 2λ′ < d′ + 2, it follows
by induction that there is a complete Kneser (d′ − λ′)-transversal T in Rd′ to the convex
hulls of all k′-sets of X ′. We claim that T is a complete Kneser (d − λ)-transversal in
Rd to the convex hulls of all k-sets of X. Clearly T contains d − λ + 1 points of X and
since k′ = k − (j + 1) it follows that T intersects the convex hulls of all (k − (j + 1))-sets
of X ′ = X ∩ aff(F ). Let K ⊆ X with k points, since |X ∩ (Rd \ aff(F ))| = j + 1 then
|K ∩ aff(F )| ≥ k − (j + 1), then T intersects the convex hull of K ∩ aff(F ) and therefore
T intersects the convex hull of K.
We are ready to prove the lower bound
m∗(k, d, λ) ≥ (d− λ+ 1) + k.
Proof of Theorem 5.1. Let X be a collection of (d− λ+ 1) + k points in Rd. If no d+ 2
points of X are in general position in Rd, then the theorem holds by Lemma 5.2. Now
suppose there exists Y ⊆ X with d+ 2 points in general position in Rd. Since 2λ < d+ 2
it follows that 2λ− (2d+2) < d+2− (2d+2) obtaining that d− λ+1 ≥ ⌈d+1
2
⌉ = ⌊d+2
2
⌋.
Then by Lemma 5.1, the set Y can be partitioned into two disjoint and non-empty sets
S and T such that
|T | = d− λ+ 1 and conv(S) ∩ aff(T ) 6= ∅.
82 CHAPTER 5. KNESER TRANSVERSALS
Let us see that aff(T ) is a complete Kneser (d− λ)-transversal to the convex hulls of
all k-sets of X. Let K ⊆ X with k points. If K∩T 6= ∅ then clearly aff(T )∩conv(K) 6= ∅.
If K ∩ T = ∅, then K = X \ T since |X| = (d − λ + 1) + k. Hence S ⊆ K obtaining
that conv(S) ⊆ conv(K). Finally, as aff(T ) intersects the convex hull of S, it follows that
aff(T ) intersects the convex hull of K.
5.3 Matroids and cyclic polytopes
The moment curve in Rd is defined parametrically as the map γ : R → Rd, t 7→
(t, t2, . . . , td). A cyclic polytope is the convex hull of some points on the moment curve. In
this section we study the function m∗ for cyclic polytopes. For basic notions of oriented
matroids we refer the reader to [12]. The oriented matroids associated to cyclic polytopes
on n vertices of dimension d are called alternating oriented matroids and they are denoted
by A(r, n) with r = d + 1. A well-known fact in oriented matroids is that the circuits
of oriented matroid theory arising from a configuration of points can be interpreted as
minimal Radon-partitions induced by the signs of the elements. For example, if we have
the set of points V = {v1, v2, v3, v4, v5, v6} in R3 and if C = {v1, v2, v4, v5, v6} is a signed
circuit with + + − − +, this means that the sets A = {v1, v2, v6} and B = {v4, v5} form
a Radon partition, that is, conv(A) ∩ conv(B) 6= ∅.
Let C be a circuit of A(r, n). A well-known fact [12, Section 9.4] is that
|C| = r + 1 and its elements are alternatively signed +−+− · · · (5.4)
Therefore, minimal Radon partitions of cyclic polytopes are well understood.
Let ζ(k, d, λ) be the maximum number of vertices that the cyclic polytope in Rd can
have, so that it has a complete Kneser (d − λ)-transversal to the convex hulls of all its
k-subsets of vertices.
We clearly have,
m∗(k, d, λ) ≤ ζ(k, d, λ).
We will give upper and lower bounds for ζ(k, d, λ). First we deal with some easy
special cases. If λ = 0, then any d − 0 transversal is the whole space, and then we can
have as many points as we want. Also, in the trivial range Theorem 5.2 states that the
precise value of ζ(k, d, λ) and m∗(k, d, λ) is d− λ+ k. We now prove this.
5.3. MATROIDS AND CYCLIC POLYTOPES 83
Proof of Theorem 5.2. Clearly d−λ+k ≤ m∗(k, d, λ) since every (d−λ+1)-set intersects
all the k-sets for any set of d − λ + k points in Rd. Let S be the cyclic polytope with
d − λ + 1 + k points in Rd. Let T ⊆ S be with d − λ + 1 points and consider any set
K ⊆ S \T with k points and any K ′ ⊆ K with λ+1 points. By (5.4) the Radon partition
of T ∪ K ′ can have at most
⌈
d+2
2
⌉
elements with the same sign. Since by hypothesis
|K ′| = λ + 1 >
⌈
d+2
2
⌉
, then K ′ has at least two elements with different signs and hence
by Proposition 5.2 we have conv(K ′) ∩ aff(T ) = ∅. Therefore conv(K) ∩ aff(T ) = ∅ by
Proposition 5.1.
Let us define β(λ, j) = j+λ−1
2
for each integer j such that j+λ is odd the number. Let
z(k, d, λ)
def
= (d− λ+ 1) + max
j∈{λ+1,...,d−λ+2}
j+λ is odd
(⌊
k − 1
β(λ, j)
⌋
· j + (k − 1)modβ(λ,j)
)
Z(k, d, λ)
def
= (d− λ+ 1) + ⌊(2− α(d, λ))(k − 1)⌋
The rest of this section is devoted to prove Theorem 5.3, that is, that ζ(k, d, λ) lies
above z(k, d, λ) and below Z(k, d, λ) in the non-trivial range.
5.3.1 Some combinatorial tools
In this section we will develop some counting combinatorial tools that will allow us to
prove Theorem 5.3. Let n be a positive integer. We denote by [n] the set {1, 2, . . . , n}, as
usual.
For a set S of integers x1 < x2 < . . . < xr we will denote by OD(S) the number of
odd integers in the set of differences
{x2 − x1, x3 − x2, . . . , xr − xr−1}.
In other words, a set S consists of OD(S) + 1 parity blocks. For example, the set
S = {1, 4, 5, 7, 8, 10, 12} satisfies OD(S) = 3 and its parity blocks are {1}, {4}, {5, 7} and
{8, 10, 12}. It is easy to verify that if S is a subset of T , then OD(S) ≤ OD(T ).
Fix a non-negative integer ℓ and a positive integer k. In order to prove the lower
bound for Theorem 5.3, we are interested in finding the largest value of n such that each
k-set of [n] contains a subset S such that OD(S) ≥ ℓ. Let A(k, ℓ) denote this maximum.
Proposition 5.3. For a non-negative integer ℓ and a positive integer k we have
84 CHAPTER 5. KNESER TRANSVERSALS
A(k, ℓ) =



∞ if ℓ = 0
2k − ℓ− 1 if k ≥ ℓ ≥ 1
k − 1 if ℓ ≥ k.
Proof. We will first establish the lemma for the cases ℓ = 1 and λ ≥ k. For any element
j of [n] we have OD({j}) = 0 therefore, if ℓ = 0 then n can be as large as we want.
Now suppose that ℓ ≥ k. If n ≤ k − 1, then there are no k-sets. If n ≥ k, then there
is at least one k-set K, but any subset S of K set satisfies OD(S) ≤ OD(K) ≤ k − 1.
We are left with the case k ≥ ℓ ≥ 1. Suppose that n ≤ 2k− ℓ+1 and consider a k-set
of [n] with ordered elements x1 < x2 < . . . < xk. If it does not have any subset S with
OD(S) ≥ ℓ, then at most ℓ − 1 of the numbers in {x2 − x1, x3 − x2, . . . , xk − xk−1} are
odd, and thus at least (k − 1)− (ℓ− 1) = k − ℓ of them are even giving
xk − x1 =
k−1∑
j=1
xj+1 − xj ≥ ℓ− 1 + 2(k − ℓ) = 2k − ℓ− 1.
This implies n ≥ xk ≥ 2k − ℓ− 1 + x1 ≥ 2k − ℓ, a contradiction.
Now, if n ≥ 2k − ℓ, then the set
K = {1, 2, 3, . . . , ℓ− 1} ∪ {ℓ, ℓ+ 2, ℓ+ 4, . . . , ℓ+ 2(k − ℓ)}
is a k-set of [n]. Notice that OD(K) = ℓ − 1 and therefore each subset S satisfies
OD(S) ≤ ℓ− 1.
We will develop further some counting tools needed for the proof of the upper bound
for Theorem 5.3. Let d and λ be two positive integers. We will construct a special family
of subsets of [d− λ+ 2] as follows.
First, we consider the case in which d is odd. We define
I(d, λ) := {1, 2, . . . , λ− 1} ∪ {λ, λ+ 2, λ+ 4, . . . , d− λ+ 1}.
The parity of d ensures that the last term is correct. Notice that this set has
5.3. MATROIDS AND CYCLIC POLYTOPES 85
(λ− 1) +
(d− λ+ 2)− (λ− 1)
2
=
d+ 1
2
elements.
Now, let σ be the cyclic permutation in [d−λ+2] defined as σ(i) = i+1 for i ∈ [d−λ+1]
and σ(d− λ+ 2) = 1. For each j ∈ [d− λ+ 2] we define the set
I(d, λ, j) := σj−1(I(d, λ)).
Finally, we define the sets I(d, λ, j) for even values of d. In this case we will only define
the sets up to j = d− λ+ 1 as follows:
I(d, λ, j) :=
{
I(d− 1, λ, j) ∪ {d− λ+ 2} if 1 is in I(d− 1, λ, j),
I(d− 1, λ, j) if not.
Notice that for fixed λ and d, we have defined a total of 2
⌈
d
2
⌉
− λ+ 1 sets regardless
of the parity of d. We now prove that the elements from [d− λ + 2] are well distributed
in these sets and that the sets have few parity blocks.
Proposition 5.4. Fix two positive integers d and λ. Suppose that d is odd. Define the
sets I(d, λ, j) as above. Then
1. Each number from [d− λ+ 2] appears in exactly
⌈
d
2
⌉
of the sets I(d, λ, j).
2. For each j we have
OD(I(d, λ, k)) ≤ λ− 1.
Proof. 1. If d is odd, this follows from the fact that σ is a permutation of order d−λ+2
and that I has d+1
2
=
⌈
d
2
⌉
elements.
If d is even, by the previous argument all the elements of [d − λ + 1] appear in
(d−1)+1
2
=
⌈
d
2
⌉
of the subsets. The claim also follows for the element d + λ + 2
because it appears in as many sets as 1.
2. We will prove that
OD(I(d, λ, j)) = λ− 1
86 CHAPTER 5. KNESER TRANSVERSALS
holds for even values of d. This will be enough because then I(d−1, λ, j) ⊆ I(d, λ, j),
and therefore OD(I(d− 1, λ, j)) ≤ OD(I(d, λ, j)) = λ− 1.
If j = 1, then the set is
I(d, λ, 1) := {1, 2, . . . , λ− 1} ∪ {λ, λ+ 2, λ+ 4, . . . , d− λ, d− λ+ 2}.
which has exactly λ − 1 parity changes. We will now proceed by induction and
compare I(d, λ, j) and I(d, λ, j + 1). All the parity changes in [d− λ] are shifted to
parity changes in the interval [2, . . . , d − λ + 1], therefore we can only increase or
decrease parity changes at the endpoints.
At the left endpoint a shift can only increase parity changes. This happens if and
only if after the shift we obtain 1 and 2, if and only if before the shift we had 1 and
d− λ+ 1. Therefore, before and after the change we have the element d− λ+ 2. If
the number to the left of d− λ+ 1 was d− λ, then we lose the parity change from
d − λ to d − λ + 1 If the number to the left of d − λ + 1 was d − λ − 1, then we
lose the parity change from d− λ+ 1 to d− λ+ 2. Either way, the total changes of
parity remain constant.
If obtain a parity change using the right endpoint it was because we had both d−λ
and d − λ + 1 but not d − λ + 2. But in this case the win is compensated by the
loss of the parity change from d− λ to d− λ+ 1.
Finally, if we lose a parity change at the right endpoint it is because we had the
elements d−λ+1 and d−λ+2, but this gets compensated by an additional parity
change at the left endpoint.
5.3.2 Upper bound of ζ(k, d, λ)
In this section we prove that ζ(k, d, λ) ≤ Z(k, d, λ). Let γ : R 7→ Rd be the moment
curve and let t1 < . . . < tn be some real positive numbers. Consider the cyclic polytope
S = {v1, v2, . . . , vn} where vi = γ(ti). We want to show that if there exists a complete
Kneser (d− λ)-transversal to all the convex hulls of S, then n ≤ Z(k, d, λ).
Consider some indices 1 ≤ i1 < i2 < . . . < id−λ+1 ≤ n. For each j ∈ [d− λ+ 1] define
wj as vij . Furthermore, define
5.3. MATROIDS AND CYCLIC POLYTOPES 87
A1 := {v1, . . . , vi1−1}
Aj := {vi|i ∈ {ij−1 + 1, . . . , ij − 1}} for j ∈ {2, 3, . . . , d− λ+ 1}
Ad−λ+2 := {vid−λ+1+1, . . . , vn}
A := {A1, A2, . . . , Ad−λ+2}
T := {w1, . . . , wd−λ+1}.
We can get a better intuition of what is going on by concatenating the A′s and the
w′s as follows:
S = A1 w1 A2 w2 A3 . . . Ad−λ+1 wd−λ+1 Ad−λ+2.
We want a tool to test whether aff(T ) could be a transversal to all the convex hulls of
the k-sets. The tool are precisely the parity changes introduced in Subsection 5.3.1. The
following proposition makes the key connection.
Proposition 5.5. Using the notation above, if aff(T ) is a transversal to all the convex
hulls of the k-sets then for every subset S of [d−λ+2] such that OD(S) ≤ λ− 1 we have
∑
α∈S
|Aα| ≤ k − 1.
Proof. Suppose that S is a subset of [d− λ+ 2] such that OD(S) ≤ λ− 1 and
∑
α∈S
|Aα| ≥ k.
Then we can choose a k-set K ⊆ ⋃
α∈S Aα. According to Proposition 5.1, checking
whether aff(T ) ∩ conv(K) 6= ∅ is the same as checking that aff(T ) ∩ conv(K ′) 6= ∅ for a
set K ′ ⊆ K such that |K ′| = d− (d− λ) + 1 = λ+ 1.
Suppose K ′ = {vj1 , . . . , vjλ+1
} for some indices j1 < . . . < jλ+1. Each element of K ′ is
in some element of A. For each r ∈ [λ+1], let ĵr be the index such that vjr ∈ Aĵr
. Notice
that
• ĵ1 ≤ ĵ2 ≤ . . . ≤ ˆjλ+1.
• ĵr ∈ S for every r.
88 CHAPTER 5. KNESER TRANSVERSALS
Since OD(S) ≤ λ − 1 then two of the indices ĵr must lie in the same parity block of
S. We may assume that they correspond to two vertices vjr and vjr+1
. Since ĵr and ˆjr+1
lie in the same parity interval there are an even number of vertices of T ∪K ′ between vjr
and vjr+1
. Therefore, according to (5.4) they get different signs in the Radon partition.
Using Proposition 5.2 we have that aff(T ) does not intersect conv(K ′). Thus aff(T )
does not intersect conv(K) and therefore it cannot be a transversal.
Combining this proposition with the combinatorial lemmas of Subection 5.3.1 we may
now prove the upper bound of ζ(k, d, λ), that is
ζ(k, d, λ) ≤ (d− λ+ 1) + ⌊(2− α(d, λ))(k − 1)⌋ .
Proof of the upper bound of Theorem 5.3. Suppose T is a transversal. By the second part
of Proposition 5.4, the sets I(d, λ, k) of Section 5.3.1 satisfy the hypothesis for S in
Proposition 5.5. Adding the corresponding inequalities for each of the 2
⌈
d
2
⌉
− λ+ 1 sets
we get:
∑
j
∑
α∈I(d,λ,j)
|Aα| ≤
(
2
⌈
d
2
⌉
− λ+ 1
)
(k − 1).
Using the first part of Proposition 5.4, we have that each |Aα| appears exactly
⌈
d
2
⌉
times in the left hand side sum. Therefore,
⌈
d
2
⌉
·
d−λ+2∑
α=1
|Aα| ≤
(
2
⌈
d
2
⌉
− λ+ 1
)
(k − 1).
Finally, dividing by
⌈
d
2
⌉
and adding the points from the transversal we get
|S| = (d− λ+ 1) +
d−λ+2∑
α=1
|Aα| ≤ (d− λ+ 1) +
(
2
⌈
d
2
⌉
− λ+ 1
⌈
d
2
⌉
)
(k − 1).
Since |S| is an integer, we can take the floor function on both sides to get the desired
result.
5.3. MATROIDS AND CYCLIC POLYTOPES 89
Therefore, we obtain as a corollary the following upper bound for m∗(k, d, λ).
Corollary 5.1. In the non-trivial range, when α(d, λ) < 1 we have that
m∗(k, d, λ) ≤ (d− λ+ 1) + ⌊(2− α(d, λ))(k − 1)⌋ = Z(k, d, λ).
5.3.3 Lower bound of ζ(k, d, λ)
Now we want to show that the cyclic polytope with z(k, d, λ) points always has a complete
Kneser (d − λ)-transversal to the convex hulls of all its k-sets. We will use the notation
from Section 5.3.2. Notice that to determine which points are the d − λ + 1 that will
generate the transversal, it is enough to say how many points are in each set Ai.
The idea for constructing the example and proposing a complete Kneser transversal
will be to fix the parameters k, d, λ and then distribute the points as evenly as possible in
the sets Ai. However, it might be the case that distributing the points using all the sets
Ai is not optimal. Sometimes we get a better example by evenly distributing the points
only in some of the first Ai’s. This is the role that j plays in the following formula:
z(k, d, λ) = (d− λ+ 1) + max
j∈{λ+1,...,d−λ+2}
j+λ is odd
(⌊
k − 1
β(λ, j)
⌋
· j + (k − 1)modβ(λ,j)
)
.
We give a brief explanation of the formula to make the proof clearer. The d − λ + 1
in the formula represents the points that generate the complete Kneser transversal. For
a fixed value of j, we will distribute
zj :=
⌊
k − 1
β(λ, j)
⌋
· j + (k − 1)modβ(λ,j).
points evenly in the sets A1, . . ., Aj and we will show that we indeed get a complete
Kneser transversal. It may seem strange that in the index of the max in the formula for
z(k, d, λ) we have the restrictions j ≥ λ + 1 and j + λ is odd. The first one is due to
Proposition 5.5 and the second one is just a refinement to improve optimality (as we will
see in the proof). We can also create examples when j + λ even, but it turns out that
they are not optimal. We work having in mind that we want to stretch the idea of even
distribution as much as possible.
So, let us fix a value of j. Remember that we had defined β(λ, j) = j+λ−1
2
when j + λ
is odd. We can extend this definition for both parities of j + λ by defining β(λ, j) as
⌈
j+λ−1
2
⌉
. We need the following auxiliary result.
90 CHAPTER 5. KNESER TRANSVERSALS
Proposition 5.6. The solution to the optimization problem in variables a, r
max aj + r
subject to the restrictions
1. a is a non-negative integer
2. r is in {0, 1, . . . , j − 1}
3. If r ≥ β(λ, j) then
β(λ, j)(a+ 1) ≤ k − 1
4. If r ≤ β(λ, j)− 1 then
(a+ 1)r + (β(λ, j)− r)a ≤ k − 1
is zj and is obtained when
a =
⌊
k − 1
β(λ, j)
⌋
, r = (k − 1)modβ(λ,j).
Proof. It is clear that to maximize the expression aj + r, first we have to maximize a
given our constraints, and then maximize r.
We will first get the maximum when r ≥ β(λ, j). In this case, we are subject to the
restriction (3):
β(λ, j)(a+ 1) ≤ k − 1.
The best value we can get for a is
⌊
k−1
β(λ,j)
⌋
−1. Since in this case we only have restriction
(2) for r, then we can get r = j − 1. Therefore, in this case the maximum for aj + r is
(⌊
k − 1
β(λ, j)
⌋
− 1
)
· j + (j − 1) =
⌊
k − 1
β(λ, j)
⌋
· j − 1.
In the case r ≤ β(λ, j)− 1, we have restriction (4), which can be simplified to
β(λ, j)a+ r ≤ k − 1.
5.3. MATROIDS AND CYCLIC POLYTOPES 91
Once again, we first optimize a. The greatest value it can take is
⌊
k−1
β(λ,j)
⌋
. Afterwards,
by restriction (4) the maximum value that r can take is (k − 1)modβ(λ,j). Now we just
check that this value of r lies in the case we are studying:
r = (k − 1)modβ(λ,j) ≤ β(λ, j)− 1.
Therefore, when r ≤ β(λ, j)− 1 the best value for aj + r is
⌊
k − 1
β(λ, j)
⌋
· j + (k − 1)modβ(λ,j).
This value is always greater than the optimum when r ≥ β(λ, j). Therefore, the
solution for the whole optimization problem is zj, it is attained in the case r ≤ β(λ, j)−1
and the values of a and r are
a =
⌊
k − 1
β(λ, j)
⌋
, r = (k − 1)modβ(λ,j).
The following proposition provides the connection between Proposition 5.6 and the
construction of examples with complete Kneser transversals.
Proposition 5.7. Let j be an integer in {λ+ 1, . . . , d− λ+ 2} and a and r integers that
satisfy the constraints from Proposition 5.6. The cyclic polytope in dimension d with
(d− λ+ 1) + aj + r
vertices has a complete Kneser (d− λ)-transversal to the convex hulls of all its k-sets.
Proof. We will use the notation from Section 5.3.2. As we have said before, we will just
split the aj + r points among A1, . . ., Aj. For this, we choose T = {w1, . . . , wd−λ+1} in
such a way that
|A1| = |A2| = . . . = |Ar| = a+ 1 |Ar+1| = |Ar+2| = . . . = |Aj| = a.
First, we indeed have that |A| = r(a+ 1)+ (j − r)a = ja+ r. We claim that aff(T ) is
indeed the desired transversal. Consider aK set of A. IfK has an element wi, then clearly
92 CHAPTER 5. KNESER TRANSVERSALS
aff(T ) ∩ conv(K) 6= ∅. If K ∩ T = ∅, the constraints from Proposition 5.6 guarantee K
cannot be contained in the union of β(λ, j) sets Ai. This means that if I is the smallest
family of indices such that
K ⊆
⋃
i∈I
Ai,
then |I| ≥ β(λ, j) + 1 =
⌈
j+λ−1
2
⌉
. But then
2|I| − λ− 1 ≥ (j + λ− 1)− λ− 1 = j,
and therefore we can use Proposition 5.3 to conclude that I contains a set with at
least λ odd changes, and therefore that it has at least λ+ 1 parity blocks. Then, we can
find a set J ⊆ I with λ+1 elements of alternating parity. For each j ∈ J choose a vertex
vj in K ∩ Aj. Call K
′ the set of all these vj’s.
If vj1 and vj2 are consecutive vertices in K ′, then there is an odd number of elements
from T ∪ K ′ in between them. This means that all the elements from K ′ get the same
sign in the Radon partition for T ∪K ′. Therefore, by Proposition 5.1 and Proposition 5.2
we have that aff(T )∩ conv(K) 6= ∅. We have proven that aff(T ) is the desired transversal.
We may now prove the lower bound of ζ(k, d, λ), that is
ζ(k, d, λ) ≥ (d− λ+ 1) + max
j∈{λ+1,...,d−λ+2}
j+λ is odd
(⌊
k − 1
β(λ, j)
⌋
· j + (k − 1)modβ(λ,j)
)
.
Proof of the lower bound of Theorem 5.3. We combine Proposition 5.7 and the optimal
value from Proposition 5.6 for every integer j in {λ + 1, . . . , d − λ + 2}. We can show a
corresponding complete Kneser (d− λ)-transversal for the cyclic polytope with (d− λ+
1) + aj vertices.
Notice that if j + λ is even, then we would already have an example with the same
number of points by using j − 1 instead of j. Therefore, we do not lose examples by
requiring that j + λ be odd. By definition of ζ we can take the maximum over all these
values of j and thus this yields the claimed bound.
5.3. MATROIDS AND CYCLIC POLYTOPES 93
Remark 5.1. The above proof is the best we can do by using a balanced distribution of
points in the sets Ai. Let us briefly explain this by sketching an argument. Suppose that
we distribute the points in the sets Ai1, Ai2, . . ., Aij , where i1 < . . . < ij. We have that
the set {i1, . . . , ij} has at most j parity blocks, not more than those in the set {1, 2, . . . , j}
used in Proposition 5.7. Therefore, when conisdering an optimization problem analogous
to the one in Proposition 5.6, it is considered a problem with stronger constraints which
translates to an example with fewer or the same number of points. Nevertheless, as far as
we know, there might be still better examples if we do not require an even distribution.
5.3.4 Asymptotics
The bounds found by Theorem 5.3 are asymptotically correct in terms of k. In this section
we provide the calculations to show that in the non-trivial range
lim
k→∞
ζ(k, d, λ)
k
= 2− α(d, λ).
Proof of Theorem 5.4. By Theorem 5.3 we have that
ζ(k, d, λ)
k
≤ Z(k, d, λ)
k
≤ (2− α(d, λ))(k − 1)
k
+
d− λ+ 1
k
,
hence
lim
k→∞
ζ(k, d, λ)
k
≤ 2− α(d, λ).
We will prove now that limk→∞
ζ(k,d,λ)
k
≥ 2− α(d, λ).
By the lower bound of Theorem 5.3 we have that
ζ(k, d, λ) ≥ z(k, d, λ) ≥
⌊
k − 1
β(λ, j)
⌋
· j + (k − 1)modβ(λ,j)
for every j ∈ {λ + 1, . . . , d − λ + 2} whenever d + λ is odd. Suppose d is odd. By
setting j = d− λ+ 2 we have
ζ(k, d, λ) ≥
⌊
k − 1
d+1
2
⌋
(d− λ+ 2) + (d− λ+ 1).
94 CHAPTER 5. KNESER TRANSVERSALS
Then
lim
k→∞
ζ(k, d, λ)
k
≥ 2
(
d− λ+ 2
d+ 1
)
= 2
(
1− λ− 1
d+ 1
)
=
(
2− λ− 1
d+1
2
)
.
Since d is odd, the rightmost expression is equals 2− α(d, λ), as desired.
Suppose now that d is even. Then (d−λ+1)+λ is odd and we may set j = d−λ+1
yielding that
ζ(k, d, λ) ≥
⌊
k − 1
d
2
⌋
(d− λ+ 1) + (d− λ+ 1).
Then limk→∞
ζ(k,d,λ)
k
≥ 2(d−λ+1
d
) = 2 − α(d, λ) and once again we obtain the correct
lower bound.
Corollary 5.2. limd→∞ limk→∞
ζ(k,d,λ)
k
= 2.
Remark 5.2. By [17, Corollay 5.1], it is easy to prove that
2− 1
d
≤ lim
k→∞
m(k, d, λ)
k
,
and therefore that for d ≥ 3,
lim
k→∞
m∗(k, d, 2)
k
≤ lim
k→∞
ζ(k, d, 2)
k
= 2− 2
d
< 2− 1
d
≤ lim
k→∞
m(k, d, 2)
k
.
So, for k large enough and d ≥ 3, m∗(k, d, 2) < m(k, d, 2).
Remark 5.3. In the non-trivial range, when k > λ+ 1 and k − 1 ≥
⌈
d
2
⌉
, we have
ζ(k, d, λ) = ⌊(2− α(d, λ))(k − 1)⌋+ (d− λ) + 1 < d+ 2(k − λ).
5.4 Some exact values of m∗
If we set additional constraints in k, d and λ then we can find the exact value ofm∗(k, d, λ).
Theorem 5.5. Suppose α(d, λ) < 1 and d
2
≤ k < 2
1−α(d,λ)
, then
m∗(k, d, λ) = (d− λ+ 1) + k.
5.4. SOME EXACT VALUES OF M∗ 95
Proof. By Theorems 5.1 and 5.3, we have that
(d− λ+ 1) + k ≤ m∗(k, d, λ) ≤ (d− λ+ 1) + ⌊(2− α(d, λ))(k − 1)⌋ ,
when α(d, λ) < 1 and k ≥ ⌈d
2
⌉ + 1. Then m∗(k, d, λ) = (d − λ + 1) + k whenever
k = ⌊((2−α(d, λ))(k− 1)⌋. Since for any real number x we have that ⌊x⌋ ≤ x < ⌊x⌋+1,
then it follows that m∗(k, d, λ) = (d− λ+ 1) + k if
k ≤ (2− α(d, λ))(k − 1) < k + 1.
By doing some calculations, we have the following equivalences
k
k − 1
≤ 2− α(d, λ) <
k + 1
k − 1
,
1 +
1
k − 1
≤ 2− α(d, λ) < 1 +
2
k − 1
,
1
k − 1
≤ 1− α(d, λ) <
2
k − 1
,
k − 1 ≥ 1
1− α(d, λ)
>
k − 1
2
,
concluding that m∗(k, d, λ) = (d− λ+1)+ k whenever 2
1−α(d,λ)
+1 > k ≥ 1
1−α(d,λ)
+1.
The inequality 2
1−α(d,λ)
+1 > k holds by hypothesis. On the other hand as α(d, λ) < 1
we have that λ ≤ ⌈d
2
⌉. Then the inequality k ≥ 1
1−α(d,λ)
+ 1 holds since by hypothesis we
have that k ≥ ⌈d
2
⌉+ 1. Therefore m∗(k, d, λ) = (d− λ+ 1) + k.
When λ = 1, we have obtained the exact value of m∗(k, d, 1).
Theorem 5.6. The value of m∗(k, d, 1) is d+ 2(k − 1).
Proof. The theorem is trivial for k = 1, in the other cases the upper bound is given by
Theorem 5.3. Let X be any set of d + 2(k − 1) points in Rd, in order to prove that
d + 2(k − 1) ≤ m∗(k, d, 1), we will show that there exists an hyperplane H with at
least d points of X and with at most k − 1 points of X in each of the two open half-
spaces determined by H. Let F be a face of conv(X) and let us consider S ⊂ X ∩ F
with cardinality d − 1, such that each point of S is a vertex of the d-polytope conv(X).
Consider the hyperplane aff(F ), clearly X is contained in one half-space of aff(F ). We
96 CHAPTER 5. KNESER TRANSVERSALS
may now rotate continously aff(F ) by fixing S to find an hyperplane H with at least d
points of X and with at most k− 1 points in each of the two open half-spaces determined
by H. Then H is a complete Kneser d-transversal to the convex hulls of all k-sets.
By Theorem 5.2 we immediately have the following.
Corollary 5.3. m∗(k, d, λ) = d− λ+ k when α(d, λ) ≥ 1.
We can now give a strict inequality between m∗ and m.
Corollary 5.4. m∗(k, d, λ) < m(k, d, λ) when k > λ and α(d, λ) ≥ 1.
Proof. Since d−λ+k+ ⌈ k
λ
⌉−1 ≤ m(k, d, λ) ([7, Corollary 1]) and m∗(k, d, λ) = d−λ+k
(Corollary 5.3), it follows that m∗(k, d, λ) < d− λ+ k + ⌈ k
λ
⌉ − 1 ≤ m(k, d, λ) if 1 < ⌈ k
λ
⌉.
The result holds since by hypothesis k > λ.
Remark 5.4. In the trivial range α(d, λ) ≥ 1, there exist configurations of d − λ + k +
⌈ k
λ
⌉ − 1 points in Rd with a (d − λ)-transversal to the convex hulls of all the k-sets and
without complete Kneser (d− λ)-transversals.
For infinitely values of d, λ and k, this configurations of points are the cyclic polytopes
(see Section 5.3). For instance, the cyclic polytope with 6 points in general position in
R4 has transversal lines to the convex hulls of all the 4-sets but does not have complete
Kneser transversal lines. This means m∗(4, 3, 4) = 5 and 6 ≤ m(4, 3, 4).
We end by mentioning that the smallest values of k, d and λ in which we do not
know the value of m∗(k, d, λ) are k = 3, d = 2 and λ = 5, in this case we know that
7 ≤ m∗(3, 2, 5) ≤ 8.
Chapter 6
Appendix: Definitions and basic
theory
6.1 Basic notation
For a positive integer n, we define [n] := {1, 2, . . . , n}. For a set X and a positive integer
k we define
(
X
k
)
as the family of sets of X with k elements (or k-sets). We use P(X) to
denote the set of all subsets of X.
6.2 Graphs, digraphs and hypergraphs
6.2.1 Definitions
We define a graph as a pair G = (V,E) such that E is a subset of
(
V
2
)
. We call V the
vertices and E the edges of the graph. Unless otherwise stated, we will assume that V is
finite.
If we are given a graph G, we will denote the set of vertices by V (G) and the set of
edges by E(G). We say that two vertices u and v are adjacent if {u, v} is an edge of the
graph.
In the following definitions G and H are graphs. We say that G and H are isomorphic
if there exists a bijective mapping f : V (G) → V (H) that preserves adjacency in both
directions. For convenience, we usually think of isomorphic graphs as the same graph.
We say that H is a subgraph of G if V (H) is a subset of V (G) and E(H) is a subset of
97
98 CHAPTER 6. APPENDIX: DEFINITIONS AND BASIC THEORY
E(G). If H is a subgraph of G and we also have that E(H) is exactly E(G) ∩
(
H
2
)
, then
we will say that H is an induced subgraph of G. We say that G is H-free if there is no
induced subgraph of G that is isomorphic to H.
A clique is a subset of vertices of a graph such that every two of them are adjacent.
The number of vertices in a largest clique of G is called the clique number of the graph
and it is denoted by ω(G). A set of vertices is independent if there is no edge any two
of them. The size of a largest independent set of G is called the independence number of
the graph and it is denoted α(G).
Let c be a positive integer. A c-coloring of V (G) is a function f : V (G) → [c]. The
coloring is proper if for any pair of adjacent vertices v1 and v2 we have that f(v1) 6= f(v2).
The chromatic number of a graph G is the minimum c for which a proper c-coloring of
V (G) exists. It is denoted by χ(G). We define c-colorings of E(G) analogously.
We say that G is bipartite if it admits a proper 2-coloring. If G is bipartite, we usually
write G = [X, Y ] to express that both X and Y are independent sets and V (G) = X ∪Y .
Similarly, for a positive integer k we say that G is k-partite if it admits a proper k-coloring
Throughout this dissertation we are interested in four families of graphs. Let k be a
positive integer.
• The graph on [k] such that each pair of vertices are adjacent is called the k-complete
graph. It is denoted by Kk.
• The k-path has vertex set [k] and for each i ∈ [k − 1] the pair {i, i+ 1} is an edge.
It is usually denoted by Pk.
• If k > 2, the k-cycle is the graph obtained by adding the edge {1, k} to the k-path.
It is usually denoted by Ck.
• The graph on [k + 1] such that the only edges are those of the form {i, k + 1} with
i ∈ [k] is called the k-star. We will denote it by Sλ.
We can avoid using the k and just call these graphs complete graphs, paths, cycles and
stars respectively.
Two vertices u and v of G are connected if we can find a path in G with endpoints u
and v. We say that G is connected if any two of its vertices are connected. We say that
G is 2-connected if even after removing any vertex we still get a connected graph.
We say G that is acyclic if it does not have cycles as subgraphs. We will say that G is
a tree if it is a acyclic and it is connected. We say that H is a spanning tree of G if H is
a subgraph of G, it is a tree and V (H) is V (G). The number of spanning trees of a graph
is denoted by τ(G), counting isomorphic copies with the corresponding multiplicities.
6.2. GRAPHS, DIGRAPHS AND HYPERGRAPHS 99
It is possible to extend the definition of graph to allow loops (edges from a vertex to
itself) or multiple edges (more than one edge for a pair of vertices). In such a theory we
call G loopless if it does not have any loops and simple if it is loopless and it does not
have multiple edges (i.e. it is a graph in the first definition).
We define a directed graph or digraph as a pair G = (V,A) such that A is a subset of
V × V . We call V the vertices and E the arrows of the digraph. We define subdigraphs
and digraph isomorphism analogously to the case of graphs. As in the case of graphs, we
may allow multiple arrows and loop arrows.
Let k be a positive integer. The directed k-path is the digraph constructed as follows.
The vertex set is k and for each i ∈ [k − 1] the pair (i, i + 1) is an arrow. If k > 2, the
directed k-cycle is the graph obtained by adding the arrow (k, 1) to the directed k−path.
We can avoid using the k and just call these digraphs directed paths and directed cycles
respectively.
One way to obtain directed graphs is to take a graph G and assign to each of its
edges a direction. This is called an orientation of the graph. An acyclic orientation of a
graph is an orientation such that there is no directed cycle as subgraph. A totally cyclic
orientation is an orientation such that each edge belongs to a directed cycle.
Another way to extend graph theory is to allow for edges with more than two vertices.
A hypergraph G consists of a vertex set V (G) and a an edge (or hyperedge) set E(G)
which is a subset of P(V (G)){∅}, where P(X) is the power set of V (G).
If there exists an integer k such that all the edges of G have cardinality k, then we
say that G is k-uniform. Many definitions for graphs extend naturally to hypergraphs,
for example, for positive integers n and k the complete hypergraph Kr
n has vertex set [n]
and edge set
(
[n]
r
)
.
6.2.2 Classical results
Intuitively, a graph with a fixed number of vertices and many edges should have a large
clique number. Turán’s theorem [66] is a result in extremal graph theory which makes
this idea precise.
Theorem 6.1 (Simple Turán’s theorem). Let G be a graph with n vertices and r a positive
integer. If G has more than
(
1− 1
r − 1
)
· n
2
2
edges, then ω(G) ≥ r.
Furthermore, Pál Turán characterized the optimal graphs, that is, the graphs with
100 CHAPTER 6. APPENDIX: DEFINITIONS AND BASIC THEORY
the greatest number of edges in a fixed vertex set that avoid a clique of fixed size. For
positive integers n and r, we split [n] in r− 1 sets V1, . . ., Vr−1 as evenly as possible, that
is, so that no two sets have size difference larger than 1. The Turán graph Tn,r has vertex
set [n] and two vertices u and v are adjacent if and only if they belong to different Vi’s.
Theorem 6.2 (Turán’s theorem). Let G be a graph with n vertices and r a positive
integer. If G has more than Tn,r, then ω(G) ≥ r. Furthermore, if ω(G) ≤ r − 1 and G
has |E(Tn,r)| edges, then G is (isomorphic to) Tn,r.
A matching in a graph is a set of disjoint edges. If we have a graph G and a subset
X of the vertices, we say that a matching covers X if each vertex of x is contained in an
edge of the matching. If we have a bipartite graph G = [X, Y ], Hall’s marriage theorem
[34] provides a criterion to determine when we can find a matching that covers X.
Theorem 6.3 (Hall’s theorem). Let G = [X, Y ] be a bipartite graph. There exists a
matching that covers X if and only if for each subset S of X there are at least |S| vertices
of Y adjacent to at least one vertex of S.
Another interesting result is Ramsey’s theorem [61]. To get an intuition of the theorem,
we can say that it is a broad generalization of the following statement: if G is a graph
with a large number of vertices, then it either has a large independent set, or a large
clique. Here we present a version in terms of hypergraphs.
Theorem 6.4 (Ramsey’s theorem). Let r, k and c1, c2, . . ., ck be positive integers. Then
there exists a positive integer R = R(c1, . . . , ck; r) such that for any n > R and any k-
coloring f of the edges of Kr
n, there exists an index i ∈ {1, . . . , k} and a subset S of [n]
with size ci such that f is constant in
(
S
r
)
.
In informal terms, no matter the size of the edges, or how many colors; if we color the
edges of a complete and large enough hypergraph, we will a get a large monochromatic
hypergraph.
6.3 Convex geometry
Let d be a positive integer and x and y two points in Rd. A point z lies between x and y
if there exists an real number t ∈ [0, 1] such that z = tx+ (1− t)y. The segment between
x and y is the set of points that lie between x and y. We say that a set X of Rd is convex
if it contains the segment between every two of its points.
For a set X of Rd the convex hull of X is the smallest convex set that contains X. It
is denoted by conv(X).
6.4. MATROIDS AND ORIENTED MATROIDS 101
We state some classical results related to convex geometry. For these results, d is a
positive integer.
Theorem 6.5 (Separation theorem). Let A and B be two disjoint non-empty closed
convex sets, one of which is compact. Then there exists a hyperplane such that A and B
are strictly contained in distinct sides of the hyperplane.
Theorem 6.6 (Helly’s theorem). Let F a finite family of at least d+1 convex sets of Rd.
If each d+ 1 convex sets of F have non-empty intersection, then the whole family F has
non-empty intersection.
Theorem 6.7 (Carathéodory’s theorem). Let S be a set of Rd. If 0 lies in conv(S), then
there is a subset S ′ of S consisting of at most d+ 1 points such that p lies in conv(S ′).
Theorem 6.8 (Radon’s theorem). Let S be a set of d+2 points of Rd in general position.
Then there exists a unique partition S = A ∪ B such that
conv(A) ∩ conv(B) 6= ∅.
Furthermore, the intersection is a single point that lies in the interior of both conv(A) and
conv(B)
We refer to the excellent material in [51] for proofs and additional comments.
6.4 Matroids and oriented matroids
This is a brief introduction to matroid and oriented matroid theory. We refer the reader
to the classical text [59] for proofs of the basic facts and a deeper discussion on matroids.
For oriented matroids, we recommend the text [12].
There are several ways to define what a matroid is. We will define matroids in terms
of its bases and then provide an equivalent definitions in terms of independent sets and
in terms of circuits.
A matroid is a structure M consisting of a ground set E and a collection subsets of
E, called its base set, B which satisfies:
1. B is non empty.
2. If A and B are in B and there is an element a ∈ A \B, then we can find an element
b ∈ B \ A such that A \ {a} ∪ {b} is in B.
102 CHAPTER 6. APPENDIX: DEFINITIONS AND BASIC THEORY
We call Property 2 the basis exchange axiom. Elements of B are called bases.
It is a standard fact in matroid theory that all the bases of a matroid have the same
cardinality. We call this number the rank of the matroid. If an element a of E belongs to
no base, we will call it a loop. If it belongs to every base, we call it a coloop. If a matroid
has no loops or coloops we will call it loopless-coloopless, but for brevity we will just call
it LC. If we have a matroid M with base set B then we can construct another matroid
M∗ called the dual of M with the same ground set but with base set
B∗ := {E \B : B ∈ B}.
The base graph GM of a matroid M has as vertex set the set B of bases of M and two
bases B,B′ ∈ B are adjacent if and only if the symmetric difference B∆B′ consists of two
elements or, equivalently, when B can be obtained from B′ by a single application of the
basis exchange axiom. The base polytope PM is the convex hull of the binary incidence
vectors of the set B of bases of M . By a well-known result of [32], the base graph GM is
isomorphic to the 1-skeleton of the base polytope of M .
If a base A also satisfies that M \ A is a base, then we call A a base-cobase. We will
say that M is a block matroid if it has at least one base-cobase. In this case, notice that
|E| = 2r, where r is the rank of M . For a block matroid M we define the base-cobases
graph G(M,M∗) as the subgraph of the base graph GM induced by the base-cobases of
M .
We can also study matroids using independent sets. If we have a matroid M on E
with base set B, we can consider the set of independent sets defined as
I := {I : I ⊂ B,B ∈ B}
which satisfies the following three properties:
1. ∅ ∈ I.
2. If A ∈ I and B ⊂ A, then B ∈ I.
3. If A and B are two elements in I and A has more elements than B, then there is
an element a ∈ A such that B ∪ {a} is in I.
These properties provide an alternative and equivalent set of axioms for matroid theory.
Property 3 is called the augmentation property. If we have two matroids M and N with
ground sets E and F respectively, we define the direct sum of M and N as the matroid
6.4. MATROIDS AND ORIENTED MATROIDS 103
whose ground set is the disjoint union of E and F , and whose independent sets are the
disjoint unions of an independent set of M with an independent set of N . If a matroid
cannot be expressed as the direct sum of two nonempty matroids is said to be connected.
If we have a matroid M and a subset S of its ground set E, then the independent sets
of M contained in E \ S yield a new matroid M \ S called the deletion of S. The dual
operation is the contraction of S and can be defined as the matroid M/s := (M∗ \ S)∗.
When S consists of one element s, we shorten the notations M \ {s} and M/{s} to M \ s
and M/s respectively.
A very useful algebraic invariant for matroids is the Tutte polynomial. For each matroid
M , this is a two variable polynomial defined as follows:
T (M ; x, y) =
∑
A⊂E
(x− 1)r(E)−r(A)(y − 1)|A|−r(A).
The Tutte polynomial contains important information about the matroid. For exam-
ple, T (M ; 1, 1) is the number of bases of M . In the case of graphic matroids, T (M ; 2, 0)
and T (M ; 0, 2) count the number of acyclic and totally cyclic orientations of the under-
lying graph. It is also well known [70] that the Tutte polynomial satisfies the following
recursive properties:
1. T (M ; x, y) = T (M \ s; x, y) + T (M/s; x, y) when s is neither a loop nor a coloop.
2. T (M ; x, y) = xT (M \ s; x, y) when s is a coloop.
3. T (M ; x, y) = yT (M/s; x, y) when s is a loop.
In order to introduce oriented matroids, we will give a final characterization of ma-
troids. If instead of looking at maximal independent sets we consider all the minimal
dependent sets then we get a collection of sets C called the circuits of the matroid which
satisfy:
1. ∅ /∈ C.
2. If A and B are in C and A ⊆ B, then A = B.
3. If A and B are in C, A 6= B and c ∈ A ∩ B, then there exists C ∈ C such that
C ⊆ (A ∪ B)− {e}.
The third property is called circuit elimination. As before, these properties provide
an alternative definition for matroids.
104 CHAPTER 6. APPENDIX: DEFINITIONS AND BASIC THEORY
There are many examples from geometry and graph theory that suggest that circuits
may hold more information if we add a + or − sign to each of its elements. This motivates
the following definition. A signed subset of a set E is a pair C = (C+, C−) of disjoint
subsets C+ and C− of E. We call C+ ∪ C− the underlying subset of C and we denote it
by C.
An oriented matroid is a structure M consisting of a ground set E and a collection of
signed subsets of E, called its signed circuits, C, which satisfies:
1. ∅ /∈ C.
2. C = −C.
3. If A and B are in C, and A ⊆ B, then A = ±B.
4. If A and B are in C, A 6= −B y e ∈ A+ ∩ B−, then there exists C ∈ C such that
C+ ⊆ (A+ ∪B+)− {e}
C− ⊆ (A− ∪ B−)− {e}.
The last property is called signed circuit elimination. If we have a set of points X on
on R and we partition its d + 2-sets based on the Radon partitions, then we obtain an
oriented matroid with ground set X.
6.5 Bézout’s theorem
The work in Chapter 1 requires a basic form of Bézout’s theorem, a result in algebraic
geometry.
An algebraic curve in the plane is the zero set of a non-zero two variable polynomialP (x, y)
in the ring R[x, y]. If P (x, y) factors, then the curve is the union of the zero sets of all
factors. Each of these zero sets is called a component of the original curve. In this case
we say that the algebraic curve is said to be reducible. Otherwise, we say it is irreducible.
Theorem 6.9 (Bézout’s inequality for plane curves). Let C and D be two plane curves
that come from polynomials of degree m and n respectively. Then the intersection of C
and D either contains an irreducible component of both curves, or is a finite set of at most
m · n elements.
For more general statements and proofs we refer to classical textbooks on algebraic
geometry like [35] or [43].
6.6. COMBINATORIAL TOPOLOGY 105
6.6 Combinatorial topology
Here we present some results used in Chapter 2.
A k-simplex is a k-dimensional polytope that is the convex hull of k + 1 affinely
independent points in Euclidean space. When we are interested in a k-simplex as a
topological space we will usually denote it by ∆k. A face of the simplex is the convex hull
of a subset of its vertices (and so it is also a simplex).
A simplicial complex is a topological space that can be constructed “gluing” simplices
correctly. More formally, it is a collection K of simplices such that
1. Any face of a simplex from K is also in K.
2. If σ1 and σ2 are in K, then its intersection is either empty, or it is a face of both σ1
and σ2.
We call each element of mcK a face. The 1-dimensional skeleton of a simplicial
complex K consists of all its vertices and edges. More generally, the k-dimensional skeleton
consists of all its simplices of dimension at most k.
If we divide ∆k into smaller k-dimensional simplices (which can be formally though as
a continuous function from a simplicial complex to ∆k that satisfies certain conditions)
then we get a triangulation of ∆k. Sperner’s lemma states that if we give a special
(k + 1)-coloring of the vertices, then we can find a colorful simplex of the triangulation.
Theorem 6.10 (Sperner’s lemma). Let T be a triangulation of ∆k with vertex set V =
{v1, v2 . . . , vk+1} and f a k + 1-coloring of the vertices of T . Suppose that
1. For each i ∈ [k + 1], f(vi) = i.
2. If v is a vertex of T that lies in the subface of ∆k generated by a subset S of V , the
v can only get a color in f(S).
Then there exists a simplex of T such that f is bijective on its vertices.
Bibliography
[1] Ron Aharoni. Ryser’s conjecture for tripartite 3-graphs. Combinatorica, 21(1):1–4,
2001.
[2] Ron Aharoni and Eli Berger. The intersection of a matroid and a simplicial complex.
Transactions of the American Mathematical Society, 358(11):4895–4917, 2006.
[3] Ron Aharoni, Eli Berger, and Roy Meshulam. Eigenvalues and homology of flag
complexes and vector representations of graphs. Geometric & Functional Analysis
GAFA, 15(3):555–566, 2005.
[4] Ron Aharoni, Eli Berger, and Ran Ziv. Independent systems of representatives in
weighted graphs. Combinatorica, 27(3):253–267, 2007.
[5] Ron Aharoni, Maria Chudnovsky, and Andrei Kotlov. Triangulated spheres and
colored cliques. Discrete and Computational Geometry, 28(2):223–229, 2002.
[6] Ron Aharoni and Penny Haxell. Hall’s theorem for hypergraphs. Journal of Graph
Theory, 35(2):83–88, 2000.
[7] Jorge L. Arocha, Javier Bracho, Luis Montejano, and JL Ramı́rez Alfonśın. Transver-
sals to the convex hulls of all k-sets of discrete subsets of Rn. Journal of Combinatorial
Theory, Series A, 118(1):197–207, 2011.
[8] Hoda Bidkhori. Lattice Path Matroid Polytopes. ArXiv e-prints, December 2012.
[9] Anders Bjorner. Topological methods. Handbook of combinatorics, 2:1819–1872,
1995.
[10] Anders Björner. Nerves, fibers and homotopy groups. Journal of Combinatorial
Theory, Series A, 102(1):88–93, 2003.
[11] Anders Björner, Bernhard Korte, and László Lovász. Homotopy properties of gree-
doids. Advances in Applied Mathematics, 6(4):447–494, 1985.
[12] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M
Ziegler. Oriented matroids, Encyclopedia of Mathematics, volume 46. Cambridge
University Press, 1999.
107
108 BIBLIOGRAPHY
[13] Joseph E. Bonin. Lattice path matroids: the excluded minors. J. Combin. Theory
Ser. B, 100(6):585–599, 2010.
[14] Joseph E. Bonin and Anna de Mier. Lattice path matroids: structural properties.
European J. Combin., 27(5):701–738, 2006.
[15] Joseph E. Bonin, Anna de Mier, and Marc Noy. Lattice path matroids: enumerative
aspects and Tutte polynomials. J. Combin. Theory Ser. A, 104(1):63–94, 2003.
[16] Joseph E. Bonin and Omer Giménez. Multi-path matroids. Combin. Probab. Com-
put., 16(2):193–217, 2007.
[17] Boris Bukh, Jǐŕı Matoušek, and Gabriel Nivasch. Stabbing simplices by points and
flats. Discrete and Computational Geometry, 43(2):321–338, 2010.
[18] Jonathan Chappelon, L. Mart́ınez-Sandoval, Luis Pedro Montejano, Luis Montejano,
and Ramı́rez-Alfonsíın Jorge Luis. Kneser transversals. Electronic Notes in Discrete
Mathematics, 2015 (to appear).
[19] Vanessa Chatelain and Jorge Luis Ramı́rez Alfonśın. Matroid base polytope decom-
position. Adv. in Appl. Math., 47(1):158–172, 2011.
[20] Laura E. Chávez-Lomeĺı, Criel Merino, Steven D. Noble, and Marcelino Ramı́rez-
Ibáñez. Some inequalities for the Tutte polynomial. European Journal of Combina-
torics, 32(3):422 – 433, 2011.
[21] E. Cohen, P. Tetali, and D. Yeliussizov. Lattice Path Matroids: Negative Correlation
and Fast Mixing. ArXiv e-prints, May 2015.
[22] R. Conde and C. Merino. Comparing the number of acyclic and totally cyclic orien-
tations with that of spanning trees of a graph. Int. J. Math. Com., 2:79–89, 2009.
[23] Julian L. Coolidge. A treatise on algebraic plane curves. Clarendon Press, 1931.
[24] Emanuele Delucchi and Martin Dlugosch. Bergman Complexes of Lattice Path Ma-
troids. ArXiv e-prints, July 2012.
[25] B. Descartes. Solution to advanced problem no. 4526. Amer. Math. Monthly, 61:352,
1954.
[26] Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Combi-
natorial OptimizationEureka, You Shrink!, pages 11–26. Springer, 2003.
[27] Paul Erdős and George Szekeres. A combinatorial problem in geometry. Compositio
Math., 2:463–470, 1935.
[28] P. Erdős. Graph theory and probability. Canad. J. Math, 1:34–38, 1959.
BIBLIOGRAPHY 109
[29] Paul Erdős. Some problems on elementary geometry. Austral. Math. Soc. Gaz., 2:2–3,
1975.
[30] Paul Erdős. Some more problems on elementary geometry. Austral. Math. Soc. Gaz.,
5(371):52–54, 1978.
[31] Paul Erdős. Problems and results in combinatorial geometry. Discrete geometry and
convexity, Annals of New York Acad. Sci., 440:1–11, 1985.
[32] I. M. Gelfand, R. M. Goresky, R. D. MacPherson, and V. V. Serganova. Combinato-
rial geometries, convex polyhedra, and Schubert cells. Adv. in Math., 63(3):301–316,
1987.
[33] András Gyárfás. Problems from the world surrounding perfect graphs. Applicationes
Mathematicae, 19(3-4):413–441, 1987.
[34] Philip Hall. On representatives of subsets. J. London Math. Soc, 10(1):26–30, 1935.
[35] Robin Hartshorne. Algebraic geometry, volume 52. Springer Science & Business
Media, 1977.
[36] Penny Haxell. On forming committees. The American Mathematical Monthly,
118(9):777–788, 2011.
[37] A.J.W. Hilton. Spanning trees and Fibonacci and Lucas numbers. Fibonacci Q.,
12:259–262, 1974.
[38] Andreas F. Holmsen, Leonardo Mart́ınez-Sandoval, and Luis Montejano. A geometric
Hall-type theorem. Proc. Amer. Math. Soc, June 2015.
[39] Matthew Kahle. Topology of random clique complexes. Discrete Mathematics,
309(6):1658–1671, 2009.
[40] Gil Kalai and Roy Meshulam. A topological colorful Helly theorem. Advances in
Mathematics, 191(2):305–311, 2005.
[41] Jovan Karamata. Sur une inégalité relative aux fonctions convexes. Publications de
l’Institut Mathématique, 1(1):145–147, 1932.
[42] M Katchalski and A Liu. A problem of geometry in. Proceedings of the American
Mathematical Society, 75(2):284–288, 1979.
[43] Frances Clare Kirwan. Complex algebraic curves, volume 23. Cambridge University
Press, 1992.
[44] K. Knauer, L. Mart́ınez-Sandoval, and J. L. Ramı́rez Alfonśın. A Tutte polynomial
inequality for lattice path matroids. ArXiv e-prints, October 2015.
110 BIBLIOGRAPHY
[45] M Kneser. Aufgabe 300. , Jahresbericht der Deutschen Math. Ver., 58(2):27, 1955.
[46] John Leech. The problem of the thirteen spheres. The Mathematical Gazette, pages
22–23, 1956.
[47] László Lovász. Kneser’s conjecture, chromatic number, and homotopy. Journal of
Combinatorial Theory, Series A, 25(3):319–324, 1978.
[48] Leonardo Martinez and Luis Montejano. Geometric variants of Hall’s theorem
through Sperner’s lemma. Electronic Notes in Discrete Mathematics, 44:127–132,
2013.
[49] Leonardo Mart́ınez and Edgardo Roldán-Pensado. Points defining triangles with
distinct circumradii. Acta Mathematica Hungarica, 145(1):136–141, 2015.
[50] Leonardo Mart́ınez-Sandoval and Luis Montejano. Fractional Turan’s theorem and
bounds for the chromatic number. Electronic Notes in Discrete Mathematics, 2015
(to appear).
[51] Jǐŕı Matoušek. Lectures on discrete geometry, volume 212. Springer New York, 2002.
[52] C. Merino and D.J.A. Welsh. Forests, colorings and acyclic orientations of the square
lattice. Annals of Combinatorics, 3(2-4):417–429, 1999.
[53] Roy Meshulam. The clique complex and hypergraph matching. Combinatorica,
21(1):89–94, 2001.
[54] Roy Meshulam. Domination numbers and homology. Journal of Combinatorial The-
ory, Series A, 102(2):321–330, 2003.
[55] Oleg Rustumovich Musin. The problem of the twenty-five spheres. Russian Mathe-
matical Surveys, 58(4):794–795, 2003.
[56] Jan Mycielski. Sur le coloriage des graphs. In Colloquium Mathematicae, volume 2,
pages 161–162, 1955.
[57] Bernhard Hermann Neumann. On an invariant of plane regions and mass distribu-
tions. Journal of the London Mathematical Society, 1(4):226–237, 1945.
[58] Steven D. Noble and Gordon F. Royle. The Merino-Welsh conjecture holds for series-
parallel graphs. Eur. J. Comb., 38:24–35, 2014.
[59] J.G. Oxley. Matroid Theory. Oxford graduate texts in mathematics. Oxford Univer-
sity Press, 2006.
[60] Richard Rado. A theorem on general measure. Journal of the London Mathematical
Society, 1(4):291–300, 1946.
BIBLIOGRAPHY 111
[61] Frank P. Ramsey. On a problem in formal logic. Proc. London Math. Soc. (3),
30:264–286, 1930.
[62] Kurt Schütte and Bartel Leendert van der Waerden. Das problem der dreizehn
kugeln. Mathematische Annalen, 125(1):325–334, 1952.
[63] Jay Schweig. On the h-vector of a lattice path matroid. Electron. J. Combin.,
17(1):Note 3, 6, 2010.
[64] Jay Schweig. Toric ideals of lattice path matroids and polymatroids. J. Pure Appl.
Algebra, 215(11):2660–2665, 2011.
[65] Carsten Thomassen. Spanning trees and orientations of graphs. Journal of Combi-
natorics, 1(2):101–111, 2010.
[66] Paul Turán. On an extremal problem in graph theory. Mat. Fiz. Lapok, 48(436-
452):137, 1941.
[67] Morton Turner and Jacob Turner. Computing the Tutte Polynomial of Lattice Path
Matroids Using Determinantal Circuits. ArXiv e-prints, December 2013.
[68] Helge Tverberg. A generalization of Radons theorem. J. London Math. Soc,
41(1):123–128, 1966.
[69] Helge Tverberg and Sinǐsa Vrećica. On generalizations of Radon’s theorem and the
ham sandwich theorem. European journal of combinatorics, 14(3):259–264, 1993.
[70] Dominic Welsh. The Tutte polynomial. Random Structures & Algorithms, 15(3-
4):210–228, 1999.
[71] Alexander Aleksandrovich Zykov. On some properties of linear complexes. Matem-
aticheskii sbornik, 66(2):163–188, 1949.