BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Complete Kneser Transversal. Ramirez Alfonsin, Jorge


Let $k,d,\lambda\ge 1$ be integers with $d\ge \lambda $. Let $m(k,d,\lambda)$ be the maximum positive integer $n$ such that every set $X$ of $n$ points (not necessarily in general position) in $\mathbb{R}^{d}$ has the property that the convex hulls of all $k$-sets have a common transversal $(d-\lambda)$-plane (called \emph{Kneser Transversal}). It turns out that $m(k, d,\lambda)$ is strongly connected with other interesting problems, for instance, the chromatic number of Kneser hypergraphs and a discrete version of Rado's centerpoint theorem. In the same spirit, we introduce a natural discrete version $m^*$ of $m$ by considering the existence of \emph{complete Kneser transversals} (in which we ask, in addition, that the transversal $(d-\lambda)$-plane contains $(d-\lambda)+1$ points of $X$). In this Talk, we present results concerning the relation between $m$ and $m^*$ and give a number of lower and upper bounds of $m^*$ as well as the exact value in some cases. After introducing the notions of \emph{stability} and \emph{instability} for (complete) Kneser transversals we give a stability result that leads to a nice geometric properties for the existence of (complete) Kneser transversals. We end by presenting some computational results (closely related to the stability and unstability notions). (This is a joint work with J. Chappelon, L. Martinez, L. Montejano and L.P. Montejano)

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International