Lopsided sets and orthant-intersection by convex sets

James F. Lawrence

Vol. 104 (1983), No. 1, 155–173

DOI: 10.2140/pjm.1983.104.155

Abstract

Given a subset L of the 2^d closed orthants in d-dimensional Euclidean space, is there a convex set K which intersects those closed orthants in L, while missing those not in L? A strong combinatorial condition on L, which is necessary for the existence of such a convex set, is exhibited. This condition is studied and its close connections with the theory of oriented matroids are examined. The sets L satisfying this condition—the “lopsided” sets—have a rich combinatorial structure which can be exploited in the study of convex sets and systems of linear inequalities.

Mathematical Subject Classification 2000

Primary: 52A20

Secondary: 05B30

Milestones

Received: 19 September 1981

Published: 1 January 1983