Ordered matroids and regular independence systems

AbstractWe consider a class of matroids which we call ordered matroids. We show that these are the matroids of regular independence systems. (If E is a finite ordered set, a regular independence system on E is an independence system (E, F) with the following property: if A ∈ F and a ∈ A, then (A − {a}) ⌣ {e} ∈ F for all e ∈ E − A such that e ⩽ a.) We give a necessary and sufficient condition for a regular independence system to be a matroid. This condition is checkable with a linear number of calls to an independence oracle. With this condition we rediscover some known results relating regular 0/1 polytopes and matroids