Transversal numbers over subsets of linear spaces

Details Transversal numbers over subsets of linear spaces Transversal numbers over subsets of linear spaces

2010-02-04

arxiv.org/abs/1002.0948v2

Mathematics

Optimization and Control

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Transversal numbers over subsets of linear spaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Transversal numbers over subsets of linear spaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transversal numbers over subsets of linear spaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-154754