Non-interval greedoids and the transposition property

AbstractIn previous papers we have mainly studied greedoids with the interval property. This paper exhibits 11 classes of greedoids whose members do not necessarily have the interval property. These non-interval greedoids are related to some fundamental algorithms and procedural principles like Gaussian elimination, blossom trees, series-parallel decomposition, ear decomposition, retracting and dismantling. We introduce some weaker exchange properties. One of them can be shown to be equivalent to the greedoid exchange property. Another one leads to the definition of transposition greedoids. Besides all interval greedoids, some non-interval greedoids share the transposition property