The intersection of a matroid and an oriented matroid

Abstract

We prove the following "matroid intersection" theorem: Let M be a matroid with rank function rho and let O be an oriented matroid of rank r, both defined on the same ground set V and satisfying rho(V) > r. If every subset S subset of V with rho(V \ S) < r contains a positive circuit of O, then there is a positive circuit of O which is independent in M.

This contains Imre Barany's colorful Caratheodory theorem as a special case. The proof uses topological methods and combines the Folkman-Lawrence representation theorem with a generalization of Kalai and Meshulam's topological colorful Helly theorem. (C) 2015 Elsevier Inc. All rights reserved.