"Combinatorics of half-space systems"

Half-space systems (HSS's) is a way of speaking about linear-inequality systems which suggests a geometric flavour, fun-theorems as well as practical, and beautiful generalizations to (piecewise-linear) topology.

1st Example: An ancient theorem, conjectured by Sylvester and eventually first proved by Gallai, says that For any finite set P of points in the plane which do not all lie on one straight line, there is a straight line which contains exactly two points of P. Though the S-G theorem does not appear to have anything to do with half-spaces, God's proof of it does, and when his proof is seen, the theorem is immediately seen to generalize to "topological HSS's" of the plane.

2nd Example: Ofcourse any finite set S of d-1 dimensional euclidean planes (hyperplanes), in d dimensional euclidean space E, slices E into certain d dimensional regions (polyhedra).

A theorem of Paul Camion says that If the intersection of all of S is empty, and there is no parallelism among any of the various intersections of subsets of S, then at least one of these d dimensional regions is a simplex. (I'll say this better in the talk.)

Camion's theorem is clearly about (linear, i.e., euclidean) HSS's, and immediately suggests generalization to topological HSS's. The complete generalization is is not yet proved, though it is proved with natural additional topological hypotheses which hold for the linear case, but surprisingly do not hold for all topological HSS's. (I hope that I make you curious about what a topological HSS is. If not, come anyway, because the talk is mainly about linear HSS's, which ofcourse everyone is interested in.)

3rd Example: Farkas' Lemma is an importent theorem of linear programming. We see that a restatement of it is the Helly Theorem: For any finite set R of half-spaces in d dimensional euclidean space E, either there a point in the intersection of all of R, or there is a subset R' of R, having cardinality at most d+1, such that the intersection of R' is empty. This Helly Theorem generalizes to topological HSS's. We give a simple geometric proof which provides a promising algorithm for linear programming.

Date et lieu : jeudi 4 septembre 1997 a 14h15
Salle C310 (salle du laboratoire LEIBNIZ)
Entree C, 3eme etage, 46, avenue Felix Viallet, Grenobe

E-mail: jedmonds@math.uwaterloo.ca