Complete Kneser transversals

DOI10.1016/J.AAM.2016.07.004MaRDI QIDQ335860zbMATH OpenOpenAlexFDO

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

Publication date 2 November 2016

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

oriented matroidstransversalscyclic polytopeKneser hypergraphs

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Oriented matroids in discrete geometry (52C40) Coloring of graphs and hypergraphs (05C15) Helly-type theorems and geometric transversal theory (52A35) Polytopes and polyhedra (52B99)

Abstract: Let $k,d,lambdageqslant1$ be integers with $dgeqslantlambda$. Let $m(k,d,lambda)$ be the maximum positive integer $n$ such that every set 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. 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^{\ast }$ of $m$ by considering the existence of complete Kneser transversals. We study the relation between them and give a number of lower and upper bounds of $m^{\ast }$ as well as the exact value in some cases. The main ingredient for the proofs are Radon's partition theorem as well as oriented matroids tools. By studying the alternating oriented matroid we obtain the asymptotic behavior of the function $m^{\ast }$ for the family of cyclic polytopes.

Recommendations

• Transversals to the convex hulls of all k-sets of discrete subsets of R^n
• Codimension two and three Kneser transversals
• Kneser transversals
• Oriented matroids and hyperplane transversals
• Transversal numbers for hypergraphs arising in geometry

Cites work

• A Theorem on General Measure
• Kneser's conjecture, chromatic number, and homotopy
• On An Invariant of Plane Regions and Mass Distributions
• Oriented Matroids
• Stabbing simplices by points and flats
• Transversals to the convex hulls of all k-sets of discrete subsets of R^n

Cited in

(4)

• Codimension two and three Kneser transversals
• Kneser transversals
• Tverberg’s theorem is 50 years old: A survey
• Transversals to the convex hulls of all k-sets of discrete subsets of R^n

This page was built for publication: Complete Kneser transversals

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