Ordered matroids and regular independence systems (Q1918556): Difference between revisions

Submodular functions on an intersecting ring family obtained as a chain of subsets can define ordered matroids. Regular independence systems (where independence is maintained whenever an element \(e\) is substituted by some other element less than or equal to \(e\)) are proved to be matroids if and only if they are ordered matroids. Then a necessary and sufficient condition is given for a regular independent system to be a matroid. This condition can be checked by a linear number of calls of an independence oracle.