Complete Kneser transversals

DOI10.1016/J.AAM.2016.07.004zbMATH Open1352.52017arXiv1511.01315OpenAlexW3102125445MaRDI QIDQ335860FDOQ335860

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)

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.

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

Recommendations

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

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)

Cites Work

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

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 \(\mathbb 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)