This post was originally written on Codeforces; relevant discussion can be found here.

Disclaimer: This is not an introduction to greedy algorithms. Rather, it is only a way to formalize and internalize certain patterns that crop up while solving problems that can be solved using a greedy algorithm.

Note for beginners: If you’re uncomfortable with proving the correctness of greedy algorithms, I would refer you to this tutorial that describes two common ways of proving correctness — “greedy stays ahead” and “exchange arguments”. For examples of such arguments, I would recommend trying to prove the correctness of standard greedy algorithms (such as choosing events to maximize number of non-overlapping events, Kruskal’s algorithm, binary representation of an integer) using these methods, and using your favourite search engine to look up more examples.

Have you ever wondered why greedy algorithms sometimes magically seem to work? Or find them unintuitive in a mathematical sense? This post is meant to be an introduction to a mathematical structure called a greedoid (developed in the 1980s, but with certain errors that were corrected as recently as 2021), that captures some intuition behind greedy algorithms and provides a fresh perspective on them.

The idea behind this post is to abstract out commonly occurring patterns into a single structure, which can be focused upon and studied extensively. This helps by making it easy to recognize such arguments in many situations, especially when you’re not explicitly looking for them. Note that this post is in no way a comprehensive collection of all results about greedoids; for a more comprehensive treatment, I would refer you to the references as well as your favourite search engine. If there is something unclear in this post, please let me know in the comments.

For readers familiar with matroidsAs you might notice when we define a greedoid, a greedoid is a generalization of a matroid. The reason why greedoids are useful is that sometimes the whole power of matroids is not necessary, and the definition of a matroid might be too restrictive. A greedoid keeps a lot of the intuition for a greedy algorithm intact, while also having useful results. If you're familiar with anti-matroids, you will realize that they are also greedoids.

To get an idea as to how wide a variety of concepts it is connected to is, greedoids come up in BFS, Dijkstra’s algorithm, Prim’s algorithm, Kruskal’s algorithm, Blossom’s algorithm, ear decomposition of graphs, posets, machine scheduling, convex hulls, linear algebra and so on, some of which we shall discuss in this post.

Note that we will mainly focus on intuition and results, and not focus on proofs of these properties, because they tend to become quite involved, and there is probably not enough space to discuss these otherwise. However, we will give sketches of proofs of properties that are quite important in developing an intuition for greedoids.

Table of contents

  1. Motivation and definition
    • Unordered version of conditions on optimality
    • Weaker conditions on optimality of the greedy algorithm
  2. Some examples
    • Interval greedoids
    • Matroids
    • Antimatroids
    • Other greedoids
  3. Constructing more greedoids
    • From matroids
    • From antimatroids
    • From greedoids
  4. Some random facts about greedoids
  5. References and further reading

Motivation and definition

We will take an approach in an order that is different from most treatments of greedoids (which throw a definition at you), and try to build up to the structure that a greedoid provides us.

How does a usual greedy algorithm look like? Initially, we have made no decisions. Then we perform a sequence of steps. After each step, we have a string of decisions that we have taken (for instance, picking some element and adding it to a set). We also want a set of final choices (so we can’t extend beyond those choices).

To make this concept precise, we define the following:

  1. A ground set is any set. We usually interpret this as a set of incremental decisions that can be made.
  2. A language is any set of finite sequences (or words) of elements coming from the ground set. We interpret a language as a set of possible sequences of decisions we can take in the greedy algorithm.
  3. A simple language is any language where the sequences don’t have repeated elements. This definition is motivated from the fact that we don’t take a decision more than once.
  4. A hereditary language is any language \(L\) on a ground set \(S\) satisfying the following two conditions:
    • \(\emptyset \in L\)
    • For any \(s \in L\), every prefix of \(s\) is also in \(L\). This definition is motivated from the fact that we want to capture a sense of time/causality in our sequence of decisions. That is, if we have a sequence of decisions, we must have arrived at it from the just-smaller prefix of decisions.
  5. A basic word in \(L\) is any \(s \in L\) such that there is no element \(e\) in \(S\) such that \(s\) extended by that element (denoted by \(s \cdot e\) or \(se\)) is in \(L\). This is motivated from the fact that we want to have some ending states at the end of the greedy algorithm.

We can now rephrase the optimization problems that a large set of greedy algorithms try to solve in the following terms:

  • Consider a simple hereditary language \(L\) on the ground set \(S\), and a function \(w : L \to \mathbb{R}\). Now maximize \(w(s)\) where \(s\) is a basic word of \(L\).

A (certain quite general type of) greedy algorithm looks something like this:

  • Initially there are no decisions taken.
  • At step \(i\), when the decisions \(x_1, \dots, x_{i - 1}\) have already been taken, pick an \(x_i \in S\) such that \(x_1 x_2 \cdots x_i \in L\), and this choice of \(x_i\) maximizes \(w(x_1 x_2 \cdots x_i)\) over all valid choices of \(x_i\). If there is no such \(x_i\), terminate the algorithm.

Of course, taking arbitrary \(w\) doesn’t make any sense, so we limit \(w\) to the following kinds of functions (we shall relax these conditions later, so that we can reason about a larger variety of problems):

  1. If at a certain point, a decision \(x\) is optimal, then it will also be optimal at a later stage. That is, if \(x\) is chosen when the prefix was \(s\), then for a prefix \(st\), we have \(w(stxu) \ge w(styu)\) for all valid \(y, u\) (\(u\) can be empty, \(y\) is a decision).
  2. It is optimal to pick \(x\) sooner than later. That is, if \(x\) is chosen when the prefix was \(s\), then we must have \(w(sxtyu) \ge w(sytxu)\) for all valid \(y, t, u\) (\(t, u\) can be empty, \(y\) is a decision).

To this end, we define greedoids as follows:

A greedoid is a simple hereditary language \(L\) on a ground set \(S\) that satisfies an “exchange” property of the following form:

  • If \(s, t \in L\) satisfy \(|s| > |t|\), then there is a decision in \(s\) that we can append to \(t\), so that the resulting word is also in \(L\).

This extra condition is crucial for us to be able to prove the optimality of greedy solutions using an exchange argument (the usual exchange argument that people apply when proving the correctness of greedy algorithms).

One notable result is that by this extra condition, all basic words in \(L\) have the same length. This might seem like a major downgrade from the kind of generality we were going for, but it still handles a lot of cases and gives us nice properties to work with.

For people familiar with matroids

Similar to the rank function for matroids, we can define a rank function for greedoids, which is also subcardinal, monotone and locally semimodular.

It turns out that greedoids have the following equivalent definitions which will be useful later on (we omit the proofs, since they are quite easy):

  1. Let a set variant of the greedoid be defined as follows: a pair \((S, F)\) of a ground set \(S\) and a family of its subsets \(F\), such that \(\emptyset \in F\) and for any \(A, B \in F\) with \(|A| > |B|\), there exists an \(s \in A \setminus B\) such that \(B \cup \{s\} \in F\). Then the original definition of a greedoid and this definition of a set variant are equivalent, in the sense that for any such \(F\), there is exactly one simple hereditary language \(L\) such that the set of set of decisions in a word for each word in \(L\) is precisely \(F\). (That is, when we replace sequences in \(L\) with an unordered version, the resulting set of unordered sets is \(F\)).
  2. We can replace the second condition in the definition of the set variant by the condition that all maximal sets have the same cardinality. Maximal sets are defined as sets such that the set formed after adding another element to them is not in \(F\).

There is also a set analogue for simple hereditary languages: \(\emptyset \in F\) and for each \(X \in F\), we have an element \(x \in X\) such that \(X \setminus \{x\} \in F\). The intuition remains the same. Note that again, we don’t need this to hold for all \(x \in X\), but at least one \(x \in X\).

But why do we care about greedoids at all? The answer lies in the following informally-stated two-part theorem:

Theorem 1:

  1. If \(L\) is a greedoid on \(S\), and \(w\) satisfies the conditions mentioned earlier, then the greedy algorithm gives the correct answer.
  2. If the greedy algorithm gives the correct answer for all \(w\) satisfying the conditions mentioned earlier, and if \(L\) has the same length for all its basic words, then \(L\) is a greedoid on \(S\).
Brief proof sketch

For the first part, prove the following claims in order:

  1. If the set of decisions of \(s \in L\) and \(t \in L\) are the same, and \(sa \in L\), then \(ta \in L\).
  2. If for two sequences of decisions \(s, t\) and a decision \(a \in S\), we have \(st, sa \in L\), then we can pick a subsequence of \(t\) starting with the first decision, shift it forward by \(1\) (dropping the last character), and putting \(a\) in the place of the original first decision of \(t\) to get \(t’\), such that \(st’\) will be in \(L\).
  3. Continuing with the first claim, we can replace an arbitrary decision in \(t\) with \(a\), and shift an arbitrary subsequence of \(t\) starting after the position of replacement to get \(t’\), and \(st’\) will be in \(L\).
  4. Consider an optimal sequence of decisions that maximizes the length of the common prefix with our greedy solution. Use the previous claims to use the transformations to get to a larger common prefix length if the optimal sequence of decisions doesn’t coincide with the greedy sequence.

For the second part, define generalized bottleneck functions as follows: for every element \(s\) of \(S\), construct a non-increasing sequence of values \(f(s, i)\). Then \(w(x_1x_2\cdots x_i) = \min_{j} f(x_j, j)\) is a generalized bottleneck function. Show that \(w\) satisfies the required conditions, and try to construct a \(w\) that can help you show that the extra condition in the definition of a greedoid is satisfied.

Note that the definition of greedoid doesn’t depend on \(w\) in any way, so it can be studied as a combinatorial structure in its own right — this leads to quite non-trivial results at times. However, when we think of them in the greedy sense, we almost always have an associated \(w\).

In a lot of cases, \(w\) has a much simpler (and restrictive) structure, for instance, having a positive and additive weight function (which is defined on each element). In that case, the following algorithm works for matroids (special cases of greedoids): sort elements in descending order of their weight, and pick an element iff adding it to the set of current choices is still in the matroid.

Unordered version of conditions on optimality

Usually, \(w\) is not defined on a sequence of steps, but on the set of choices you have made. However, in the general case, the “natural” relaxation from the ordered version to the unordered version of greedoids fails (both in being equivalent and in giving the optimal answer). In fact, this error was present in the original publications (since 1981) and was corrected fairly recently in 2021. For a more detailed discussion (and the proofs of the following few theorems), please refer to \([1]\), which we shall closely follow.

We shall start out with some special cases:

Theorem 2: Consider a greedoid \(F\) (unordered) on a ground set \(S\). Suppose \(c\) is a utility function from \(S\) to \(\mathbb{R}\), so that the weight of a set of decisions is additive over its elements. Then the greedy algorithm gives an optimal solution iff the following is true:

  • If \(A, A \cup \{x\} \in F\) and \(B\) is an unordered basic word (i.e., maximal set) in \(F\) such that \(A \subseteq B\) and \(x \in S \setminus B\), then there is a \(y \in B \setminus A\) such that \(A \cup \{y\} \in F\) and \(B \cup \{x\} \setminus \{y\}\) is also a maximal set.

The following theorem generalizes the sufficiency:

Theorem 3: Consider a greedoid \(F\) (unordered) on a ground set \(S\) and \(w : 2^S \to \mathbb{R}\). The greedy algorithm gives an optimal solution if (and not iff) the following is true:

  • If for some \(A, A \cup \{x\} \in F\) and \(B\) being an unordered basic word (i.e., maximal set) in \(F\) such that \(A \subseteq B\) and \(x \in S \setminus B\), it holds that \(w(A \cup \{x\}) \ge w(A \cup \{u\})\) for all valid \(u\), then there is a \(y \in B \setminus A\) such that \(A \cup \{y\} \in F\) and \(B \cup \{x\} \setminus \{y\}\) is also a maximal set and \(w(B \cup \{x\} \setminus \{y\}) \ge w(B)\).

This theorem can be used to show optimality of Prim’s algorithm on its corresponding greedoid.

This theorem can also be derived from theorem 6 that we shall mention later on.

Remember that we mentioned that the original claim in the 1981 paper about greedoids was false? It turns out that the claim is true about a certain type of greedoids, called local forest greedoids. Since it is not so relevant to our discussion, we’re going to spoiler it to avoid impairing the readability of what follows.

Local forest greedoids and some optimality theorems

A local forest greedoid is a greedoid that satisfies the following three additional conditions:

  1. (Local union property): If \(A, B \in F\), with \(A \cup B\) being a subset of an element in \(F\), then \(A \cup B \in F\).
  2. (Local intersection property): If \(A, B \in F\), with \(A \cup B\) being a subset of an element in \(F\), then \(A \cap B \in F\).
  3. (Local forest property): If \(A, A \cup \{x\}, A \cup \{y\}, A \cup \{x, y\}, A \cup \{x, y, z\}\) are all in \(F\), then at least one of \(A \cup \{x, z\}\) and \(A \cup \{y, z\}\) is in \(F\).

One property of this structure is that for every element \(x \in S\), we can associate a path to it by taking the unique set in \(F\) that contains \(x\), none of whose subsets in \(F\) also contain \(x\). This uniqueness comes from the local forest property.

Now we are ready to state a couple of theorems:

Theorem 4: Let \(S\) be a local forest greedoid on the ground set \(S\), and \(f\) be a real function of the paths of \(S\) corresponding to this greedoid, which satisfies the following constraints:

  1. For paths \(A \subseteq B\), \(f(A) \ge f(B)\).
  2. For paths \(A, B, A \cup C, B \cup C\), \(f(A) \ge f(B)\) implies \(f(A \cup C) \ge f(B \cup C)\).

Then for the function \(w\) defined as the sum of \(f\) over paths of all elements in the argument, greedy gives an optimal solution.

As a corollary, we have the following:

Theorem 5: For an additive non-positive utility function defined on the ground set of a local forest greedoid, the greedy algorithm gives an optimal solution.

Weaker conditions on optimality of the greedy algorithm

As we had mentioned earlier, the constraints on \(w\) while motivating the definition of a greedoid (ordered) are quite stringent, and they might not hold in a lot of cases. Here, we work upon reducing the set of constraints (which will also have implications on theorem 3 earlier).

Theorem 6: Let \(L\) be a greedoid on a ground set \(S\), and \(w\) be an objective function that satisfies the following condition:

  • If \(ax \in L\) such that \(w(ax) \ge w(ay)\) for every valid \(y\) and \(c = azb\) is a basic word, then there exists a basic word \(d = axe\) such that \(w(d) \ge w( c)\).

Then the greedy algorithm gives an optimal solution.

The proof is quite easy, and goes by way of contradiction. There is a special case of the above theorem (that needs some care to prove), which is applicable in a lot of cases. It turns out that it corresponds to the last part of the proof sketch of Theorem 1, so maybe it’s not such a bad idea to read it again.

Some examples

The main point of adding examples at this point is to showcase the kinds of greedoids that exist in the wild and some of their properties, so that it becomes easy to recognize these structures. I have added the examples in spoiler tags, just to make navigation easier. Some of these examples will make more sense after reading the section on how to construct greedoids.

While going through these examples, I encourage you to find some examples of cost functions that correspond to greedy optimality, so that you can recognize them in the future. Discussing them in the comments can be a great idea too. For a slightly larger set of examples, please refer to Wikipedia and the references.

When appropriate, we will also point out greedy algorithms that are associated with these structures.

Interval greedoids

These are greedoids that satisfy the local union property (as introduced in the section of local forest greedoids). Equivalently, they are also defined as greedoids where for every \(A \subseteq B \subseteq C\) with \(A, B, C \in F\), if \(A \cup \{x\}, C \cup \{x\} \in F\) for some \(x \not \in C\), then \(B \cup \{x\} \in F\).

Some examples are:

  1. All local forest greedoids.
  2. Matroids (to be introduced later).
  3. Anti-matroids (to be introduced later).
Directed branching greedoid

A greedoid where the ground set is the edges of a directed graph, and the elements of the greedoids are arborescences that are subgraphs of the original graph, and are rooted at a certain root \(r\). This is also a local forest greedoid. Using the theorem on local forest greedoids, we can show that Dijkstra and BFS are just special cases of the greedy algorithm on this greedoid. Similarly, the widest path problem (maximimize the capacity of the minimum capacity edge on a path) can also be done using modified Dijkstra, with a proof along the lines of similar ideas.

A generalization of this is the hypergraph branching greedoid. For more, please refer \([4]\).

Undirected branching greedoid

Similar to the directed version but here the graph is undirected. The correctness of Prim’s algorithm is just an application of Theorem 2 on this greedoid.

Some generalizations of this are matroid branching greedoids, polymatroid greedoids and polymatroid branching greedoids, the last two of which are defined with an underlying polymatroid (which is a matroid). For more, please refer \([4]\).

Clique elimination greedoid

This is related to the perfect elimination antimatroid, but is slightly different.

We do the following procedure on a chordal graph:

  • At each step, pick a simplicial vertex and remove the (unique) maximal clique that contains it.

This sequence of vertices forms a greedoid.

A natural generalization is to the hypergraph elimination greedoid, and the directed branching greedoid is also a special case of the hypergraph elimination greedoid.

Matroids

Matroids are greedoids that satisfy a stronger property than the interval property for interval greedoids, by removing the lower bounds. More precisely, a matroid is a greedoid that satisfies the following property:

  • For every \(B \subseteq C\) with \(B, C \in F\), if \(C \cup \{x\} \in F\) for some \(x \not \in C\), then \(B \cup \{x\} \in F\).

Equivalently, they are greedoids where in the unordered version, for each \(X \in F\), and for all (not at least one) \(x \in X\) we have \(X \setminus \{x\} \in F\). In other words, they are downwards closed. In such a context, elements of \(F\) are also called independent sets.

Intuitively, they try to capture some concept of independence. In fact, matroids came up from linear algebra and graph theory, and greedoids were a generalization of them when people realized that matroids are too restrictive, and downwards-closedness is not really important in the context of greedy algorithms. The examples will make this notion clearer.

Note that for matroids, it is sufficient to define a basis (the set of maximal sets in \(F\)), and downwards closedness handles the rest for us.

Matroids have a much vaster theory compared to greedoids, due to being studied for quite a long time and being more popular in the research community. Since this is a post only on greedy algorithms, we will refrain from diving into matroid theory in too much detail. Interested readers can go through the references for more.

Some examples of matroids are as follows.

Free matroid

The greedoid where \(F\) is the power set of \(S\) is trivially a matroid. In other words, it is the matroid with a single maximal set — \(S\).

Uniform matroid

The matroid with the basis as all sets of some fixed size \(k\). This is a matroid that is formed by truncations of the free matroid. Truncations will be explained in the section on constructing more greedoids.

Graphic matroid

When the ground set is an undirected graph, and \(S\) is the set of all spanning forests of the graph, this matroid is called a graphic matroid.

Note that the correctness of Kruskal’s algorithm follows from this matroid.

Transversal matroid

When the ground set is the vertex set of a bipartite graph, and \(S\) is the set of endpoints of all possible matchings, this matroid is called a transversal matroid. Note that uniform matroids are a special case of transversal matroids (just consider a complete bipartite graph with \(k\) vertices on the left and \(n\) vertices on the right).

Gammoid

In a graph (directed or undirected), if there are two special sets of vertices \(U, V\), then the set of all subsets \(W\) of \(U\) where there are exactly \(|W|\) vertex-disjoint paths from \(V\) to \(W\) defines a matroid on \(U\). The transversal matroid is a special case of a gammoid. (This kind of a matroid also has a relation with flows and Menger’s theorem). A strict gammoid is one where \(U\) is the vertex set of the graph, and it is the dual of a transversal matroid. Duals of matroids will be explained in the section on constructing more greedoids.

Algebraic matroid

This is a matroid that appears in algebraic contexts when considering field extensions. Consider a field extension \(U \subseteq V\). We construct a matroid on \(V\) as the ground set, with the independent sets being the subsets of \(V\) that are algebraically independent over \(U\). That is, the elements of independent sets don’t satisfy a non-trivial polynomial equation with coefficients in \(U\).

Vector matroid

This matroid comes from linear algebra. Consider any set of points in a vector space as the ground set. Then the sets of linearly independent points in this set form a matroid called the vector matroid.

Column matroid

Consider a matrix \(M\). Then with the ground set as the set of columns of \(M\), the independent sets are the sets of columns that are independent as sets of vectors. This is almost the same as a vector matroid, but here we consider columns with different indices as different, even if they are the same as vectors.

Antimatroids

Antimatroids are greedoids that satisfy a stronger property than the interval property for interval greedoids, by removing the upper bounds. More precisely, an antimatroid is a greedoid that satisfies the following property:

  • For every \(A \subseteq B\) with \(A, B \in F\), if \(A \cup \{x\} \in F\) for some \(x \not \in B\), then \(B \cup \{x\} \in F\).

Unlike matroids, this does not necessarily imply upward closure, but it does imply closure under unions (which is another way to define antimatroids).

Another definition of antimatroids that is in terms of languages (and gives some intuition about their structure) calls a simple hereditary language over a ground set an antimatroid iff the following two conditions hold:

  1. Every element of the ground set must appear in a word in the language.
  2. The exchange property holds for any two words \(a, b\) such that \(a\) has an element not in \(b\), rather than only restricting it to \(|a| > |b|\).

Using this, we note that the basic words are all permutations of the ground set.

Another piece of intuition (derived from the above definition) that helps with antimatroids is the fact that when we try constructing sets in an antimatroid, we keep adding elements to a set, and once we can add an element, we can add it any time after that.

It also makes sense to talk about antimatroids in the context of convex geometries. To understand the intuition behind this, we take the example of a special case of what is called a shelling antimatroid. Let’s consider a finite set of \(n\) points in the 2D plane. At each step, remove a point from the convex hull of the remaining points. The set of points at any point in this process clearly forms an antimatroid by the above intuition. In fact, if instead of 2D, we embed the ground set in a space with a high enough dimension, we can get an antimatroid isomorphic to the given matroid!

What is so special about convexity here? Turns out we can use some sort of “anti-exchange” rule to define convex geometries in the following manner. It will roughly correspond to this fact: if a point \(z\) is in the convex hull of a set \(X\) and a point \(y\), then \(y\) is outside the convex hull of \(X\) and \(z\).

Let’s consider a set system closed under intersection, which has both the ground set and empty set in it. Any subset of the ground set (doesn’t matter whether it is in the system or not) has a smallest superset in such a set system (and it is the smallest set from the system that contains the subset). Let’s call this mapping from the subset to its corresponding smallest superset in the system \(\tau\). Then we have the following properties:

  1. \(\tau(\emptyset) = \emptyset\)
  2. \(A \subseteq \tau(A)\)
  3. \(A \subseteq B \implies \tau(A) \subseteq \tau(B)\)
  4. \(\tau(\tau(A)) = \tau(A)\)

Now for such a set system, it is called a convex geometry if the following “anti-exchange” property holds:

  • If some distinct \(y, z \not \in \tau(X)\), but \(z \in \tau(X \cup \{y\})\), then \(y \not \in \tau(X \cup \{z\})\).

Intuitively, consider \(\tau\) as a convex hull operator. Then the anti-exchange property simply means that if \(z\) is in the convex hull of \(X\) and \(y\), then \(y\) is outside the convex hull of \(X\) and \(z\).

Now it turns out that the complements of all sets in an antimatroid form a convex geometry! This is not too hard to prove.

We shall now give some examples of antimatroids.

Chain antimatroid

This is just the antimatroid that is formed when we take all prefixes of a word.

Poset antimatroid

The downwards closed (under the partial order) subsets of elements in a poset form an antimatroid. In simpler words, if you have a DAG and you pick an arbitrary subset of vertices, construct a set consisting of all vertices from which at least one vertex in the subset is reachable. Now these kinds of constructed sets form an antimatroid. Note that the chain antimatroid is a special case of a poset antimatroid, when the order is total (or equivalently, when the DAG is a line). Intuitively, it is related to the shelling antimatroid when you try to “shell” the poset from the bottom.

The machine scheduling problem is related to this greedoid. Indeed, let \(D = (V, A)\) be a DAG whose vertices represent jobs to be scheduled on a single machine (with no interruptions) and edges of \(D\) represent precedence constraints to be respected by the schedule. Furthermore, a processing time \(a(v) \in \mathbb{N}\) is also given for every job \(v \in V\). Finally, a monotone non-decreasing cost function \(c_v : \{0, \dots, N\} \to \mathbb{R}\) is also given for every job \(v \in V\), where \(N = \sum_{v \in V} a(v)\) such that \(c_v(t)\) represents the cost incurred by job \(v\) if it is completed at time \(t\). The problem is to find a schedule (that is, a topological ordering of the jobs with respect to \(D\)) such that the maximum of the costs incurred is minimized. Lawler (1973) gave a simple greedy algorithm for this problem: it builds up the schedule in a reverse order always choosing out of the currently possible jobs one with the lowest cost at the current completion time.

Note that in the poset antimatroid, we shelled a poset from the bottom. When we do so from both ends (that is, sets are the union of a downwards closed and an upwards closed set), it also forms an antimatroid (called the double poset shelling antimatroid).

Shelling antimatroid

A shelling sequence of a finite set \(U\) of points in the Euclidean plane or a higher-dimensional Euclidean space is formed by repeatedly removing vertices of the convex hull. The feasible sets of the antimatroid formed by these sequences are the intersections of \(U\) with the complement of a convex set. Every antimatroid is isomorphic to a shelling antimatroid of points in a sufficiently high-dimensional space, as mentioned earlier.

A special case is the tree-shelling antimatroid, where we form the feasible sets by pruning leaves one by one. This is also a perfect elimination antimatroid.

Another special case is the edge tree-shelling antimatroid, where we form the feasible sets by pruning terminal edges (instead of leaves) one by one. Again, this is also a perfect elimination antimatroid.

Also see \([4]\) for more kinds of shelling antimatroids.

Perfect elimination antimatroid

This arises when we consider chordal graphs and their perfect elimination orderings. Prefixes of all possible perfect elimination orderings formed an antimatroid.

Point-line search antimatroid

An antimatroid where the ground set is the union of vertex and edge sets of an undirected graph, and feasible sets are sets \(A\) that satisfy the following property:

  • If \((u,v) \in A \cap E(G)\) then either \(u \in A \cap V(G)\) or \(v \in A \cap V(G)\).
Cover antimatroid

Let \(G\) be an undirected graph with vertex set \(V\) and edge set \(E\), and let \(x\) be a new vertex not in \(V\). We can define an antimatroid on ground set \(V \cup \{x\}\) with the feasible sets as the union of the power set of \(V\) and the set of all sets \(X \cup \{x\}\) such that all edges have at least one endpoint in \(X\).

Point search antimatroid

Root a directed graph at a vertex \(r\). Then with the ground set as the set of vertices \(\ne r\), we can define an antimatroid consisting of sets of vertices that can be reached while searching along the graph (i.e., \(\emptyset\) is in the antimatroid, and if \(X\) is in the antimatroid, then \(X \cup \{y\}\) is in the antimatroid for \(y \not \in X\) iff \((x, y)\) is an edge and \(x \in X\)).

Line search antimatroid

The same thing as the previous antimatroid, but rather than searching for a vertex, we search for an edge. That is, the ground set becomes the set of all edges, and we add an edge \((v, w)\) to a feasible set iff \((u, v)\) is in the feasible set.

Undirected point/line search antimatroid

The definitions are similar the previous two, only the underlying graph becomes undirected. Note that undirected line search can also be generalized to matroids instead of graphs.

Capacitated point search antimatroid

In this variant, we assign a capacity \(c\) to every vertex in a rooted directed graph, which denotes the maximum length we can cover after we have reached this vertex (initially, the maximum length is infinite, and we take some kind of prefix minimums (more specifically, max length that can be travelled = min(previous max — 1, current capacity)) of the capacities). Then the sets that are formed as follows form an antimatroid:

  1. Take a vertex set, and find at least one path from the root to each vertex in this set.
  2. Add vertices from this set of paths to the vertex set. Return the set so formed.
Transitivity antimatroid and shelling of an acyclic matroid

Refer \([4]\).

Chip-firing antimatroid

This antimatroid stems from a combinatorially important game (in fact, it has so many deep implications on combinatorics, that it is an important research topic that is very active). A brief description of a chip firing game is as follows:

  • Initially there is a directed graph (without loops or parallel edges), and some chips on each of its vertices.
  • At the \(i\)-th step, a vertex \(v\) can be fired if there are at least \(deg(v)\) chips on it. One such vertex is chosen and fired. This operation consists of transferring one chip each from \(v\) to its neighbours.

Note that \(v\) firing \(i\) times is equivalent to having fired \(i - 1\) times and having accumulated at least \(i \cdot deg(v)\) chips, and thus \(v\) is always available for firing after this condition is satisfied (until it is fired). So the pairs \((v, i)\) form an antimatroid. A consequence of the antimatroid property of these systems is that, for a given initial state, the number of times each vertex fires and the eventual stable state of the system do not depend on the firing order.

Universal antimatroid

This antimatroid is special, in the sense that all antimatroids can be represented in this form. For why this is true, refer \([4]\).

Let \(G\) be a bipartite graph where some edges have been marked special. A vertex in the left partition is called extreme iff it is not adjacent to any special edge. Now consider the following procedure:

  • Pick an extreme vertex, add it to the sequence, and remove it and its neighbourhood from the graph. Some more vertices might become extreme.

Sequences of this kind form an antimatroid on the vertices in the left partition.

Other greedoids

Now that we got a few special types of greedoids out of the way, we shall look at some more greedoids.

Perfect elimination greedoids on bipartite graphs

This is motivated by chordal graph perfect elimination antimatroid. An edge \((u, v)\) in a bipartite graph \(G\) is called bisimplicial if the neighbourhoods of \(u\) and \(v\) form a complete bipartite subgraph of \(G\). The process which keeps removing bisimplicial edges (along with their endpoints) forms sequences that form a greedoid.

Retract, monoid retract and dismantling greedoids

These greedoids are formed when we perform certain kinds of operations on a graph/monoid. Please refer to \([4]\) for a detailed description.

Bipartite matching greedoid

This is slightly different from the transversal matroid, but is nevertheless related to it. Consider an ordering of the right half of a bipartite matching. To construct feasible sets of the greedoid, we pick a prefix of this order, and find all sets of vertices on the left which have a perfect matching with this prefix.

Linking greedoid

This is similar to the bipartite matching greedoid, but we use gammoids instead of transversal matroids here.

Gaussian elimination greedoid

Consider what happens when we perform column-wise Gaussian elimination on a matrix of full row rank. In the \(i\)-th row, we pick an unpicked column with the element at it not \(0\), and try to make everything else in that row \(0\) by subtracting an appropriate multiple of that column.

The set of chosen columns forms a greedoid.

A specialization of this to graphs is called the graphical gaussian elimination greedoid.

A generalization of this and the previous two examples comes from strong matroid systems, which can be read about in \([4]\).

Twisted and dual-twisted matroids (which are not matroids)

These are greedoids that arise from the following kinds of operations:

  1. Take a matroid and fix a feasible set of the matroid. Take the xor of this feasible set with all other elements of the matroid. This forms a twisted matroid. The naming is a bit unfortunate because it is a greedoid and not a matroid.
  2. Take a twisted matroid and add sets from the power set of the ground set which contain maximal sets (bases) of the twisted matroid. This is called a dual-twisted matroid.
Ear decomposition greedoid (undirected and directed)

Consider the ear decomposition \((e_0, P_1, \dots, P_k)\) of a 2-edge-connected undirected graph into a specified edge \(e_0\) and paths \(P_i\). This gives rise to a greedoid where the feasible sets are subsets \(X\) of edges not containing \(e_0\) such that

  1. \(X \cup \{e_0\}\) is connected.
  2. Every block of \(X \cup \{e_0\}\) not containing \(e_0\) has a single edge.

The basic words of this greedoid correspond to valid ear decompositions of the graph.

For the directed case, we need the graph to be strongly connected. The feasible sets are constructed as follows:

  1. Choose a strongly connected subgraph which will function as a root.
  2. Pick a set of vertices, and choose arborescences rooted at them, which must not intersect with the rooted subgraph, apart from possibly the root of the arborescence.
Blossom greedoid

This is related to Blossom’s maximum matching algorithm on general graphs.

Let \(G = (V, E)\) be a graph and \(M\) a matching. We define a greedoid on \(E \setminus M\) so that a feasible sequence of edges corresponds to an edge labeling in the matching algorithm.

Edmonds matching algorithm has the following setup:

A graph is matching-critical if deleting any of its nodes results in a graph that has a perfect matching. Such a graph has an odd number of nodes. A blossom forest \(B\) (with respect to \(M\)) is a subgraph of \(G\) that has a set \(A\) of nodes (inner nodes) with the following properties.

  • Every connected component of \(G \setminus A\) is matching-critical and almost perfectly matched up by \(M\)
  • Every node of \(A\) is a cut-point, has degree two and is adjacent to exactly one edge of \(M \cap G\).

The connected components of \(G \setminus A\) are called the pseudonodes or blossoms of the blossom forest, and if we contract every pseudonode we get a forest. Every connected component of \(B\) contains exactly one node that is not covered by \(M\).

The Edmonds algorithm consists of building up a blossom forest one edge at a time (not counting the edges in \(M\)). If it finds an edge connecting two pseudonodes in different components of the blossom forest, then it is easy to construct a larger matching and the algorithm starts again. If it finds an edge connecting a pseudonode to a node \(v\) outside the blossom forest, then it adds this edge and the edge of \(M\) incident with \(v\) to the blossom forest. If it finds an edge that connects two pseudonodes in the same connected component or two nodes in the same pseudo node, then it adds this to the blossom forest. Finally, if none of these steps can be carried out, the algorithm stops and concludes that the matching \(M\) is maximum. If \(M\) is a maximum matching, the edge set of the blossom forests restricted to \(E(G) \setminus M\) with respect to \(M\) forms a greedoid. To prove this, we use the fact that every maximum matching forest has the same set \(A\) of inner nodes and the same pseudonodes. Hence they all have the same number of edges, i.e. all bases have the same cardinality. Since this also holds for all subgraphs containing \(M\), by properties of polymatroid greedoids, we have a greedoid. A run of the last phase of the Edmonds algorithm corresponds to a basic word of this greedoid.

Constructing more greedoids

Note that some constructions from polymatroids/matroids etc. were already mentioned in the section on examples, so we will focus on the ones that were not.

From matroids

Truncation

When we take matroids and remove sets with rank > some threshold, we again get a matroid.

Duality

When we take the dual of a matroid (set the new basis elements to be complements of the original basis elements, and get a downward closure), the resulting structure is also a matroid.

Restriction

We can restrict a matroid by throwing away all feasible sets which have anything outside a fixed subset \(S\) of the ground set. This leads to another matroid.

Contraction

Contracting \(S\) in a matroid \(M\) is equivalent to taking the dual matroid of \(M\), deleting \(S\) (or in the restriction sense, restricting it to the complement of \(S\)), then taking the dual again.

The reason why these two operations are important is that when we apply a sequence of operations that are either restrictions or contractions, we get to a matroid minor, a concept similar to a graph minor (deletion corresponds to edge deletion and contraction corresponds to edge contraction).

Sums and unions

Taking the direct sum and union of two matroids (possibly on different ground sets) also leads to matroids. In these operations, you take the sum/union of both the ground sets and the sum/union of the each element in the Cartesian product of the sets of their independent sets.

From antimatroids

Join of antimatroids on the same ground set

For antimatroids on the same ground set, we construct feasible sets by taking the union of every possible pair of feasible sets. This is another antimatroid.

Intersection of matroid and antimatroid

Refer to the construction in \([5]\). Polymatroid greedoids naturally arise from these operations, though the class of generated greedoids is more generic than just these (and such greedoids are called trimmed greedoids).

From greedoids

Truncation

Removing all feasible sets of size \(> k\) from a greedoid also forms a greedoid.

Restriction

Defined identically to matroid restriction.

Contraction

For a feasible set \(X\), the contraction of the greedoid is constructed with ground set \(S \setminus X\) and feasible sets being those sets in \(2^{S \setminus X}\) such that adding elements of \(X\) to them gives feasible sets in the original greedoid. This is a greedoid.

Greedoid minors are defined similarly to matroid minors.

Some random facts about greedoids

This is a collection of interesting facts about greedoids that just don’t seem to fit in the above sections, but are important enough not to be ignored. Of course, with every important construction or idea, there are a lot of facts that lead to a combinatorial explosion of the kinds of facts we can derive about anything, so what we discussed above is way too incomplete to be a comprehensive introduction. It’ll hopefully evolve over time too, so I’m open to suggestions regarding this section.

  • You can construct Tutte polynomials for greedoids, just like you can for matroids.
  • We can characterize greedoids into matroids, antimatroids, and none of these in terms of having certain kinds of greedoid minors.
  • Antimatroids are very closely related to lattices, and in general we can reason about greedoids by their associated poset flats too.

References and further reading

  1. Dávid Szeszlér (2021), Sufficient conditions for the optimality of the greedy algorithm in greedoids.
  2. Bernhard Korte, Laszlo Lovasz, Rainer Schrader (1991), Greedoids
  3. Matroid intersection in simple words
  4. Goecke, Korte, Lovasz (1986), Examples and algorithmic properties of greedoids
  5. Bernhard Korte, Laszlo Lovasz (1988), Intersection of matroids and antimatroids
  6. Brenda L Dietrich (1987), Matroids and antimatroids — a survey

Lastly, since this is a huge post, some mistakes might have crept in. If you find any, please let me know!