pith. sign in

arxiv: 1002.0948 · v2 · pith:IZKEQLJEnew · submitted 2010-02-04 · 🧮 math.OC · math.MG

Transversal numbers over subsets of linear spaces

classification 🧮 math.OC math.MG
keywords mathbbnumberhellyinequalitieslineargiveinfeasiblespaces
0
0 comments X
read the original abstract

Let $M$ be a subset of $\mathbb{R}^k$. It is an important question in the theory of linear inequalities to estimate the minimal number $h=h(M)$ such that every system of linear inequalities which is infeasible over $M$ has a subsystem of at most $h$ inequalities which is already infeasible over $M.$ This number $h(M)$ is said to be the Helly number of $M.$ In view of Helly's theorem, $h(\mathbb{R}^n)=n+1$ and, by the theorem due to Doignon, Bell and Scarf, $h(\mathbb{Z}^d)=2^d.$ We give a common extension of these equalities showing that $h(\mathbb{R}^n \times \mathbb{Z}^d) = (n+1) 2^d.$ We show that the fractional Helly number of the space $M \subseteq \mathbb{R}^d$ (with the convexity structure induced by $\mathbb{R}^d$) is at most $d+1$ as long as $h(M)$ is finite. Finally we give estimates for the Radon number of mixed integer spaces.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.