Ordered matroids and regular independence systems

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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 languageEnglish
Pages (from-to)255-261
Number of pages7
JournalDiscrete Mathematics
Issue number1-3
Publication statusPublished - 15 Jun 1996


  • matroids
  • regular 0/1 polytopes
  • 0/1 solutions of linear inequalities


Dive into the research topics of 'Ordered matroids and regular independence systems'. Together they form a unique fingerprint.

Cite this