Matroids on partially ordered sets (Q1271880): Difference between revisions

The concept of a matroid is known to be a fundamental concept in combinatorics and it is also known to be ubiquitous in mathematics in general (e.g., stratification of Grassmanians, arrangements of hyperplanes, optimization). In the literature there exist attempts to generalize this concept. Those generalizations are mostly driven by a particular choice of the numerous aspects of matroids. For example ``greedoids'' [see \textit{B. Korte, L. Lovász}, and \textit{R. Schrader}, Greedoids (1991; Zbl 0733.05023)] were defined inspired by the fact that matroids allow a characterization by greedy algorithms. In this paper the authors are driven by the ``arrangement aspect'' of matroids. Every arrangement of hyperplanes in a vector space over a field gives rise to a matroid; the independent sets are the sets of hyperplanes whose intersection has codimension equal to the cardinality of the set. Now if one replaces hyperplanes by general linear subspaces the situation becomes much less structured. The concept of poset matroid introduced by the authors is proposed as a generalization capturing this situation. Various results valid for matroids are verified in the same or slightly modified form for poset matroids. A poset matroid is a set of filters -- the bases of the poset matroid -- on a partially ordered set. The axioms say that no two bases are contained in each other and for two bases and two arbitrary filters, one a lower bound for the first base and one an upper bound for the second, there is a base that is bounded by both. Arrangements of general linear subspaces are shown to give rise to poset matroids by choosing the poset as a disjoint union of chains. There is some overlap with the paper [Adv. Math. 102, No. 2, 230-239 (1993; Zbl 0793.05035)], where the same set of authors first introduced the notion of poset matroid.