FoCM 2014 conference

Workshop A4 - Graph Theory and Combinatorics

December 11, 18:00 ~ 18:30 - Room B11

Transversals to the convex hulls of $k$-sets

Luis Montejano

National University of Mexico, Juriquyilla, Mexico   -

What is the maximum positive integer $n$ such that every set of $n$ points in $\mathbb{R}^{d}$ has the property that the convex hulls of all $k$-sets have a transversal $(d-\lambda )$-plane? In this paper, we investigate this and closely related questions. We define a special Kneser hypergraph and by using some topological results and the well-known $\lambda$-Helly property, we relate our question with the chromatic number of the Kneser hypergraph, and we establish a connection $(\lambda=1)$ with so called Kneser's conjecture, first proved by Lovász. This problem is all connected with Gale embeddings, the discrete version of Rado’s Problem, and with cyclic polytopes.

Joint work with J. L. Arocha, J. Bracho, J. Chaperon, Leo Martínez, J. Ramirez-Alfonsin and L. P. Montejano.

View abstract PDF