Exchange systems (Q1823954)

A set system \(G(E)=(E,{\mathcal F})\) on a finite set E with \({\mathcal F}\subseteq 2^ E\) is called an exchange system if it satisfies the following two axioms. The first of them is the accessibility axiom that guarantees a saturated chain of feasible sets between any two comparable ones. The second one is the exchange axiom guaranteeing that the maximal feasible subsets of any subset of E form the basis family of some matroid. The aim of this paper is to give some fundamental results concerning these systems. In the second section the authors prove that exchange systems can be characterized as special greedoids, namely those all of whose single-element deletions are greedoids, or as the unique maximal class of greedoids closed under set-system union or, equivalently, under parallel connection. In the third section the authors show that some other matroid operations may be performed on exchange systems, as well. In addition to deletion, there are direct analogs of matroid restriction, series and parallel connection, lift, erection, and matroid union which work on the class of exchange systems. On the other hand, truncation does not work for a general exchange system but, however, a subclass of the class of exchange systems is described on which it does. In the fourth section the authors identify which of greedoids that previously have been described in the greedoid literature are exchange systems. And finally, the directions for further research concluding the first section should be taken into account, as well.