Codimension two and three Kneser transversals

DOI10.1137/16M1101854MaRDI QIDQ4568090zbMATH OpenOpenAlexFDO

Authors Jonathan Chappelon, L. Martínez-Sandoval, Luis Pedro Montejano, L. Montejano, Jorge Luis Ramírez Alfonsín

Publication date 15 June 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.00421

zbMATH Keywords

cyclic polytopeinstabilityKneser transversaloriented matroidsstability

Mathematics Subject Classification ID

Helly-type theorems and geometric transversal theory (52A35) Computational aspects related to convexity (52B55) Oriented matroids in discrete geometry (52C40) Software, source code, etc. for problems pertaining to computer science (68-04)

Abstract: Let $k,d,lambdageqslant1$ be integers with $dgeqslantlambda$ and let $X$ be a finite set of points in $mathbb{R}^d$. A $(d-lambda)$-plane $L$ transversal to the convex hulls 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+2(k-lambda)$ points in $mathbb{R}^d$ with $k-lambdageqslant2$ and $lambda=2,3$. We then present a description of Kneser transversals $L$ of collections of $d+2(k-lambda)$ points in $mathbb{R}^d$ with $k-lambdageqslant2$ 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 $2(k-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 $m(k,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$ admit 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$.

Recommendations

• Complete Kneser transversals
• Transversals to the convex hulls of all k-sets of discrete subsets of R^n
• Kneser transversals
• The Katchalski-Lewis transversal problem in \(\mathbb R^{n}\)
• New bounds on the Katchalski-Lewis transversal problem

Cites work

• A Theorem on General Measure
• Complete Kneser transversals
• Generation of oriented matroids --- a graph theoretical approach
• Kneser's conjecture, chromatic number, and homotopy
• Oriented Matroids
• Stabbing simplices by points and flats
• Transversals to the convex hulls of all k-sets of discrete subsets of R^n
• Upper bounds for centerlines

Cited in

(4)

• Kneser transversals
• Complete Kneser transversals
• Normal extensions of KTB of codimension 3
• Transversals to the convex hulls of all k-sets of discrete subsets of R^n

This page was built for publication: Codimension two and three Kneser transversals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4568090)