Abstract
We 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 is an element of F and a is an element of A, then (A - {a}) boolean OR {e} is an element of F for all e is an element of E - A such that e less than or equal to 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.
Original language | English |
---|---|
Pages (from-to) | 255-261 |
Number of pages | 7 |
Journal | Discrete Mathematics |
Volume | 154 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 15 Jun 1996 |
Keywords
- matroids
- regular 0/1 polytopes
- 0/1 solutions of linear inequalities