Niklas Warren: Basic Theory and Illustrative Examples

Abstract: A greedoid is a combinatorial structure which arose from another combinatorial structure, the matroid. In this thesis, we go through some basic greedoid theory supplemented by various examples. After a short introduction to the concept, we look at a greedoid both in terms of a set system and in terms of a formal language. Later on, we explore various classes such as the Gaussian greedoids and the interval greedoids, among which, for example, matroids and antimatroids are included. In the final part, we examine the rank function and the closure operator of a greedoid more closely. Further, the operations known as truncation, restriction and contraction are presented and finally, the relationship between greedoids and optimization problems is briefly discussed​.