The intersection of matroids and antimatroids

AbstractAntimatroids are combinatorial structures abstracting some properties of convexity, and in a sense dual to matroids. Greedoids are common generalizations of matroids and antimatroids. We introduce a general operation to produce a greedoid from a matroid and an antimatroid on the same ground set. Greedoids arising by this operation are called trimmed matroids. Many known classes of greedoids are shown to be trimmed matroids. We derive two submodularity properties of trimmed matroids and a subclass of them called polymatroid greedoids. These are used to verify the properties of a rather elaborate counterexample, which shows that certain local properties do not characterize trimmed matroids and polymatroids greedoids (as was conjectured in an earlier paper)