Transversal numbers over subsets of linear spaces

Abstract: Let

M

be a subset of

m a t h b b 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 (m a t h b b R^{n}) = n + 1

and, by the theorem due to Doignon, Bell and Scarf,

h (m a t h b b Z^{d}) = 2^{d} .

We give a common extension of these equalities showing that

h (m a t h b b R^{n} i m e s m a t h b b Z^{d}) = (n + 1) 2^{d} .

We show that the fractional Helly number of the space

M s u b s e t e q m a t h b b R^{d}

(with the convexity structure induced by

m a t h b b 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.

Recommendations

Cites Work

Cited In (18)

This page was built for publication: Transversal numbers over subsets of linear spaces