Oriented Matroids and Hyperplane Transversals

✍ Scribed by Laura Anderson; Rephael Wenger

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 401 KB
• Volume: 119
• Category: Article
• ISSN: 0001-8708
• DOI: 10.1006/aima.1996.0028

✦ Synopsis

We prove that a finite family A of compact connected sets in R d has a hyperplane transversal if and only if for some k, 0<k<d, there exists an acyclic oriented matroid of rank k+1 on A such that every k+2 sets in A have an oriented k-transversal which meets the sets consistently with that oriented matroid. 1996 Academic Press, Inc.

Let A be a finite family of compact convex sets in R d . A k-transversal for A is an affine subspace of dimension k which intersects every member of A. A hyperplane transversal for A is a hyperplane which intersects every member of A. Under what conditions does the family A have a hyperplane transversal ?

Hadwiger in 1957 gave the first such conditions for line transversals in the plane [3]. He noted that a directed line transversal intersects pairwise disjoint sets in a specific order. He used this ordering to give conditions for the existence of line transversals.

Theorem 1 (Hadwiger's Transversal Theorem [3]). A finite family A of pairwise disjoint compact convex sets in the plane has a line transversal if and only if there is a linear ordering of A such that every three convex sets have a directed line transversal meeting them consistently with that ordering.