Ordered matroids and regular independence systems

Research output: Contribution to journalArticle

1 Citation (Scopus)

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

Keywords

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

Cite this