# Codimension two and three Kneser Transversals

* Corresponding author 1 IMAG - Institut Montpelliérain Alexander Grothendieck 2 Instituto de Matematicas México

Abstract : Let $k,d,\lambda \geqslant 1$ be integers with $d\geqslant \lambda$ and let $X\subset\mathbb{R}^{d}$ be a finite set. A $d-\lambda$-plane $L$ transversal to the convex hull of all $k$-sets of $X$ is called Kneser transversal. If in addition $L$ contains $d-\lambda+1$ points of $X$, then $L$ is called complete Kneser transversal.In this paper, we present various results on the existence of complete Kneser transversals for $\lambda =2,3$. In order to do this, we introduce the notions of stability and instability for complete Kneser transversals. We first give a stability result for collections of $d+2k-\lambda$ points in $\mathbb{R}^d$ with $k-\lambda\geqslant 2$ and $\lambda =2,3$. We then present a description of Kneser transversals $L$ of collections of $d+2k-\lambda$ points in $\mathbb{R}^d$ with $k-\lambda\geqslant 2$ for $\lambda =2,3$. We show that either $L$ is a complete Kneser transversal or it contains $d-2\lambda-1$ points and the remaining $2k-1$ points of $X$ are matched in $k-1$ pairs in such a way that $L$ intersects the corresponding closed segments determined by them. The latter leads to new upper and lower bounds in the case when $\lambda =2$ and $3$ for $mk,d,\lambda$ defined as the maximum positive integer $n$ such that every set of $n$ points not necessarily in general position in $\mathbb{R}^{d}$ admitting a Kneser transversal.Finally, by using oriented matroid machinery, we present some computational results closely related to the stability and unstability notions. We determine the existence of complete Kneser transversals for each of the $246$ different order types of configurations of $7$ points in $\mathbb{R}^3$.

Keywords : transversals cyclic polytope oriented matroids

Author: Jonathan Chappelon - Leonardo Martínez-Sandoval - Luis Montejano - Luis Pedro Montejano - Jorge Luis Ramírez Alfonsín -

Source: https://hal.archives-ouvertes.fr/