A Framework for the Greedy Algorithm

A. Vince Department of Mathematics University of Florida Gainesville, FL 32611, USA

                 vince@math.ufl.edu

Abstract

The classical setting for the greedy algorithm is the theory of matroids. Given a set system M the greedy algorithm correctly solves the associated optimization problem for all weight functions if and only if M is a matroid. There are, however, set systems M that are not matroids, for which the greedy algorithm nevertheless correctly solves the optimization problem - but not for every weight function. This is the case, for example, for the symmetric matroids of Bouchet [?], symplectic matroids of Borovik, Gelfand and White [?] and, more generally, the Coxeter matroids of Gelfand and Serganova [?, ?]. Our intention is to put the greedy algorithm into a simple framework that includes such examples, as well as ordinary matroids. For any pair (P, P) consisting of a finite set P together with a set P of partial orderings of P, we define the concepts of greedy set and admissible function. On greedy sets, the greedy algorithm correctly solves the naturally associated optimization problem for all admissible functions. Indeed, when P consists of linear orders, the greedy sets are characterized by this property. A geometric condition sufficient for a set to be greedy is given in terms of roots and the greedy polytope.

Résumé

Le cadre classique pour l’algorithme “greedy” est la théorie des matroïdes. Etant donné un système d’ensembles M, l’algorithme “greedy” résoud correctement le problème d’optimisation associé pour toute fonction de poids si et seulement si M est un matroïde. Il existe cependant des systèmes d’ensembles M qui ne sont pas des matroïdes et pour lesquels l’algorithme “greedy” résoud le problème d’optimisation, mais pas pour toutes les fonctions de poids. Par exemple, c’est le cas pour les matroïdes symétriques de Bouchet [?], les matroïdes symplectiques de Borovik, Gelfand et White [?], et plus généralement les matroïdes de Coxeter de Gelfand et Serganova [?, ?]. Notre but est de placer l’algorithme “greedy” dans un cadre plus simple qui comprend tous ces exemples, en plus des matroïdes standards. Pour toute paire (P, P) d’un ensemble fini P et d’un ensemble P d’ordres partiels sur P, nous définissons le concept d’ensemble “greedy” et de fonctions admissibles. Sur les ensembles “greedy”, d’algorithme “greedy” resoud correctement le problème d’optimisation naturellement associé pour toute fonction admissibles. En effet, si P est l’ensemble des ordres linéaires, alors les ensembles “greedy” sont caractérisés par cette propriété. Une condition géométrique suffisante pour que l’ensemble soit “greedy” est donnée en termes de racines et de polytopes “greedy”.

1 Introduction

Perhaps the best known algorithm in combinatorial optimization is the greedy algorithm. The classical MAXIMAL (MINIMAL) SPANNNING TREE problem, for example, is solved by the greedy algorithm: Given a finite graph G with weights on the edges, find a spanning tree of G with maximum (minimum) total weight. At each step in the greedy algorithm that solves this problem, there is set of edges T comprising the partial tree; an edge e of maximum weight among the edges not in T (the greedy choice) is added to T so long as T + e contains no cycle.

A natural context in which to place the greedy algorithm is that of a matroid. Consider a pair (P, I) consisting of a finite set P together with a nonempty collection I of subsets of P, called independent sets, closed under inclusion. There is a natural combinatorial optimization problem associated with this pair. Given a weight function f : P → ℝ, extend the weight to subsets A ⊆ P by defining f(A) = ∑_{a∈A} f(a).

\underline{OPTIMIZATION PROBLEM.} Given a weight function f : P → ℝ, find an independent set with the greatest weight.

The greedy algorithm for this optimization problem is simply:

GREEDY ALGORITHM

I = ∅ while P ≠ ∅ do

remove from P an element a of largest weight.

if I ∪ {a} is independent then

I = I ∪ {a} end

end

It is well known that the following statements are equivalent for the pair M = (P, I). Here B denotes the set of bases of M, a basis being a maximum independent set.

1. M is a matroid.

2. The greedy algorithm correctly solves the combinatorial optimization problem associated with M for any positive weight function f : P → ℝ.

3. Every basis has the same cardinality and, for every linear ordering ⪯ on P, there exists a B ∈ B such that for any A ∈ B, if we write B = (b_{1}, b_{2}, …, b_{k}) and A = (a_{1}, a_{2}, …, a_{k}) with the elements of B and A both in increasing order, then a_{i} ⪯ b_{i} for all i. This ordering on k-element subsets of X is called the Gale order.

In the spanning tree problem, the set P consists of the set of edges of G and the independent sets are the acyclic subsets of edges. Many well known optimization problems, including the spanning tree problem, can be put into the framework of matroids. Texts by Lawler [?] and by Papadimitriou and Steiglitz [?] contain numerous examples.

Matroids are characterized by the property that the greedy algorithm correctly solves the optimization problem for any weight function. There are, however, non-matroids, for which the greedy algorithm correctly solves the optimization problem - but not for every weight function. This is the case for the symmetric matroids [?], the sympletric matroids [?] and, more generally, the Coxeter matroids of Gelfand and Serganova [?, ?]. It is our intenton in this paper to put the greedy algorithm into a simple framework that includes such examples.

The basic notion is that of a pair (P, P) consisting of a finite set P together with a set P of partial orderings of P. In Section 2 the concepts of greedy set and admissible function are defined and examples are given. When P = {1, 2, …, n} and P is the set of all linear orderings of P, the greedy sets are exactly the bases of matroids. Many of the pairs (P, P) of interest are obtained by letting a group act on the poset P. This group case is introduced in Section 3. In Section 4 we prove that, for greedy sets, the greedy algorithm correctly solves the naturally associated optimization problem for all admissible functions. Indeed, when P contains only linear orders, the greedy sets are characterized by this property. In fact, it is proved in Section 4 that there is essentially no loss of generality in assuming that P contains only linear orders. The results of Section 4 naturally lead to the problem of effectively characterizing greedy sets. A geometric approach via roots and the greedy polytope is considered in Section 5. It is proved that if every edge of the polytope of a collection L is parallel to a root, then L is a greedy set.

2 Greedy sets

Consider a pair (P, P) consisting of a finite set P and a set P of partial orderings of P. A subset M ⊆ P will be called a greedy set for the pair (P, P) if M has a unique maximum for every ordering in P.

Let P_{k} denote the collection of k-element subsets of P. Each partial order on P induces a partial order on P_{k}, namely the Gale order. If A, B ∈ P_{k}, then A ⪯ B in the Gale order if there are orderings A = (a_{1}, a_{2}, …, a_{k}) and B = (b_{1}, b_{2}, …, b_{k}) of the two sets such that a_{i} ⪯ b_{i} for all i. If ⪯ is an ordering in P, then the same notation A ⪯ B will be used for sets A, B ∈ P_{k} related in the Gale order. The set of Gale orderings induced on P_{k} by the orderings in P will be denoted P_{k}. A greedy set for the pair (P_{k}, P_{k}) will be referred to as a rank k greedy set for (P, P).

A weight function f : P → ℝ is called compatible with a partial order ⪯ on P if f(a) < f(b) whenever a ≺ b. (The notation a ≺ b means a ⪯ b but a ≠ b.) A weight function f is said to be admissible for (P, P) if f is compatible with some partial order in P. An admissible weight function f for (P, P) can be extended to an admissible weight function f : P_{k} → ℝ for (P_{k}, P_{k}) by defining

f(A) = ∑_{a∈A} f(a).

That this function is indeed admissible is the statement of the corollary below. The first proposition below is obvious from the definitions of greedy set and admissible weight function.

Proposition 2.1 If M ⊆ P is a greedy set for (P, P) and f is an admissible weight function, then f attains a unique maximum on M. □

Proposition 2.2 Let P be a partially ordered set and P_{k} the set of all k-element subsets of P with the Gale order. For any A, B ∈ P_{k} we have B ⪯ A if and only if f(B) ≤ f(A) for every weight function f compatible with the order on P.

Proof: Assume that B ⪯ A. Then there are orderings A = (a_{1}, a_{2}, …, a_{k}) and B = (b_{1}, b_{2}, …, b_{k}) such that b_{i} ⪯ a_{i}, and hence f(b_{i}) ≤ f(a_{i}), for 1 ≤ i ≤ k. Therefore f(B) = ∑_{b∈B} f(b) ≤ ∑_{a∈A} f(a) = f(A).

Conversely assume that it is not the case that B ⪯ A. We will construct a function f that is compatible with the order on P but f(B) > f(A). For each element a ∈ A, let B_{a} = {x ∈ B | x⪯a}. Now B ⪯ A in the Gale order if and only if there is a set of distinct representatives of the sets B_{a}, a ∈ A. Hence there is not such set of representatives, and, by Philip Hall’s theorem on distinct representatives, there must be a set A′ ⊆ A such that |g(A′)| < |A′|, where g(A) = ∪{B_{a} | a ∈ A′}. Now define f(x) = 0 for x ∈ A′∪g(A′) and f(x) = 1 for x ∈ B ∖ g(A′). For this function f(B) = ∑_{b∈B} f(x) = |B ∖ g(A′)| > |A ∖ A′| ≥ ∑_{a∈A} f(x) = f(A). It is easy to see that this function f can be extended and perturbed slightly to be compatible with the order on P and to retain the property that f(B) > f(A). □

Remark. By the same reasoning as in the proof above, it is also true that, for any A, B ∈ P_{k}, we have B ≺ A if and only if f(B) < f(A) for every weight function f compatible with the order on P.

Corollary 2.3 If f : P → ℝ is admissible for (P, P), then f : P_{k} → ℝ is admissible for (P_{k}, P_{k}). □

Example 2.4 Matroids. Let P = [n] = {1, 2, …, n} and let P be the set of all linear orderings of P. Then clearly every weight function f : P → ℝ is admissible. By definition, a rank k greedy set M is a collection of k-element subsets of P such that, for every linear ordering of [n], there is a unique maximum in M in the induced Gale ordering on P_{k}. But this is exactly the third characterization of matroid given in the introduction. In other words, M is a rank k greedy set for (P, P) if and only if M is the set of bases of a rank k matroid.

Example 2.5 Symplectic matroids. Let [n]^{∗} = {1^{∗}, …, n^{∗}} and let P = [n] ∪ [n]^{∗}. By convention i^{∗∗} = i. Let P be the set of all linear orderings ≤ of P with the property that i ≤ j if and only if j^{∗} ≤ i^{∗} for any i, j ∈ P. Equivalently, the pair i and i^{∗} appear symmetrically in the order. For example, with n = 3 one such order is 2 < 1^{∗} < 3 < 3^{∗} < 1 < 2^{∗}. Consequently the admissible weight functions include all weights f : P → ℝ such that f(i^{∗}) = −f(i) for each i ∈ [n]. A symmetric matroid of Bouchet [?] is exactly a rank n greedy set L for the pair (P, P) with the additional property that A ∩ A^{∗} = ∅ for each A ∈ L. More generally, the rank k greedy sets, 0 ≤ k ≤ n, satisfying this same property are exactly the symplectic matroids of Borovik, Gelfand and White [?]. The significance of the added assumption will be discussed in the next section.

3 The Group Case

Let P be a partially ordered set and G a transitive group of permutations of P. If ⪯ denotes the order on P and π ∈ G, let ⪯_{π} denote the order defined by a ⪯_{π} b if π^{−1}a ⪯ π^{−1}b. For rank k subsets, the corresponding Gale order will likewise be denoted A ⪯_{π} B. This shifted order will be called the π-order. Let P = P(G) be the set of all π-orders on P for π ∈ G. For example, if P = [n] with the order 1 < 2 < ⋯ < n, then P is the set of all orders π(1) < π(2) < ⋯ < π(n) where π ∈ G. The pair (P, P(G)) is referred to as the group case.

Although G acts transitively on P, the induced action of G on P_{k} may not be transitive. There will therefore be situations where attention will be restricted to a single orbit Q_{k} of G acting on P_{k}. The rank k greedy sets of (P, P(G)) will then be restricted to being contained in a set Q_{k} on which G acts transitively.

Example 3.1 Matroids. If P = [n] with the linear order 1 ≺ 2 ≺ ⋯ ≺ n, and S_{n} is the symmetric group consisting of all permutations of [n], then the greedy sets for (P, P(S_{n})) are exactly the ordinary matroids of Example ??.

Example 3.2 Symplectic matroids. Let P = [n] ∪ [n]^{∗} with the linear order 1 ≺ 2 ≺ ⋯ ≺ n ≺ n^{∗} ≺ ⋯ ≺ 2^{∗} ≺ 1^{∗}, and let G = B_{n} be the permutation group whose generators are all transpositions of the form (i i^{∗}) and all involutions of the form (i j)(i^{∗} j^{∗}). The group B_{n} is called the symplectic group. Note that the set of all kelement sets A with the property that A ∩ A^{∗} = ∅ comprises a single orbit of G acting on P_{k}; call this orbit Q_{k}. Then the greedy sets L ⊆ Q_{k}) for (P, P(G)) are exactly the symplectic matroids of Example ?? above.

Example 3.3 Cyclic case. Let P = [n] be a poset with the order 1 ≺ 2 ≺ ⋯ ≺ n, and let G be the cycle group acting on [n] and generated by the cycle (1 2 ⋯ n). For example, 3 ≺ 4 ≺ 1 ≺ 2 is a cyclic ordering for n = 4. A collection L of k-element subsets of P is a greedy set if and only if L = {A_{1}, A_{2}, …, A_{m}} where A_{i} = {a_{i1}, …, a_{ik}} and a_{11}⪯a_{21}⪯ ⋯ ⪯a_{m1}⪯a_{12}⪯a_{22}⪯ ⋯ α_{m2}⪯ ⋯ ⪯a_{1k}⪯a_{2k}⪯ ⋯ ⪯α_{mk}. This characterization is easily proved by induction.

Example 3.4 Bipartite case. Let P = [n] ∪ [n]^{∗} and let P consist of any linear order such that either all the unstarred elements preceed the starred elements or all the starred elements preceed the unstarred elements. This is the group case where, if [n] and [n]^{∗} are considered as vertex sets of the two parts of a complete bipartite graph K_{n,n}, then the group is the automorphism group of K_{n,n}.

4 The Greedy Algorithm

Naturally associated to the pair (P, P) is the following optimization problem.

\underline{OPTIMIZATION PROBLEM} Given an admissible weight function f : P → ℝ and a set L ⊆ P_{k}, find an element of L that maximizes the induced weight function f : P_{k} → ℝ.

Given L ⊆ P_{k}, call a subset I ⊆ P independent with respect to L if I is a subset of some element of L. The greedy algorithm, given explicitely in the introduction, applied to this optimization problem, merely chooses the largest weight element at each stage subject to the condition that the resulting set is independent with respect to L.

Theorem 4.1 Let (P, P) be a pair consisting of a collection P of orderings of the finite set P. If L ⊆ P_{k} is a rank k greedy set, then the greedy algorithm correctly solves the optimization problem for every admissible weight function f : P → ℝ.

Proof: Assume that L is a greedy set and that f is compatible with some order, say ⪯, in P. Since L is a greedy set, it contains a unique set A that is maximum with respect to the Gale order. We claim that the greedy algorithm selects this set A. Suppose, instead that B is chosen where B ⪯ A. Order the sets A = (a_{1}, a_{2}, …, a_{k}) and B = (b_{1}, b_{2}, …, b_{k}) so that the elements of B appear in the order selected by the greedy algorithm and b_{i} ⪯ a_{i} for 1 ≤ i ≤ k. Assume that a_{i} = b_{i} for 1 ≤ i < j, but a_{j} ≠ b_{j}. Then b_{j} ≺ a_{j} implies, by the compatibility of f, that f(b_{j}) < f(a_{j}). But this contradicts the fact that, at this stage, the greedy algorithm chose b_{j}. □

In the case that P contains only linear orderings of P, the greedy sets are actually characterized by the property that the greedy algorithm correctly solves the optimization problem for every admissible weight function. The assumption that P contains only linear orderings of P is a reasonable one in light of Theorem ?? below.

Theorem 4.2 Let P be a set of linear orderings of P and L ⊆ P_{k}. Then the greedy algorithm correctly solves the optimization problem for every admissible weight function if and only if L is a greedy set.

Proof: In one direction, this result is a corollary of Theorem ??. To prove it in the other direction, assume that L is not a greedy set. Then there exists an order on P, say ⪯, for which L does not attain a unique maximum. Since ⪯ is a linear ordering of P, order the elements in each set in L in decreasing order. Let A denote the lexicographically maximum element of L, and let B ≠ A be a set in L that is a maximum with respect to Gale order. According to Proposition ?? there exists a weight function compatible with ⪯ such that f(B) > f(A). On the other hand, the greedy algorithm chooses A. □

It is desirable to choose P so that there are many admissible weight functions and many rank k greedy sets. Then the greedy algorithm will correctly solve a large collection of optimization problems. Unfortunately, these two objectives - many admissible functions and many greedy sets - are often contradictory. If (P, P) and (P, Q) have the same collection of admissible functions, but, for each k, each rank k greedy set for (P, P) is a rank k greedy set for (P, Q), then clearly it is preferable, for algorithmic purposes, to use (P, Q) rather than (P, P).

Theorem 4.3 For any pair (P, P) there is a pair (P, Q) such that

1. Q contains only linear orders;

2. (P, P) and (P, Q) have the same admissible functions; and

3. for each k, each rank k greedy set for (P, P) is already a rank k greedy set for (P, Q).

Proof: Let Q be the collection of all linear extensions of the orders in P. Clearly condition (1) is satisfied. Concerning condition (2) assume that weight function f is admissible for (P, Q). Then f is compatible with some linear ordering ≤ in Q and hence is also compatibale with any ordering in P having ≤ as a linear extension. Therefore f is admissible for (P, P). Conversely assume that f is admissible for (P, P). Then f is compatible with some ordering ⪯ in P. Assume that the elements of {x_{1}, x_{2}, …, x_{n}} of P are indexed such that f(x_{1}) ≤ f(x_{2}) ≤ ⋯ ≤ f(x_{n}). Then, by definition, the linear order x_{1} < x_{2} < ⋯ < x_{n} is a linear extension of ⪯ and f is compatible with this linear order. Therefore f is admissible for (P, Q).

Concerning condition (3) assume that M is a rank k greedy set for (P, P). To show that M must also be a greedy set for (P, Q), let ≤ be any linear order in Q. Then ≤ is a linear extension of some order ⪯ in P. Since M is greedy for (P, P), there is a unique maximum set A = (a_{1}, …, a_{k}) in M such that, for any B = (b_{1}, …, b_{k}), we have b_{i} ⪯ a_{i} for all i for some ordering of the elementsof A and B. Because ≤ is a linear extension of ⪯, it is also true that b_{i} ≤ a_{i} for all i. Therefore A is also the unique maximum with respect to the Gale order relative to ≤. So M is a greedy set for (P, Q). □

The following examples are chosen to be simple and to demonstrate the theory for non-matroid greedy sets.

Example 4.4 Symplectic matroids. This is a continuation of Example ?? of Section 2. Consider the case n = 3. It is not hard to check that the set

M = {12^{∗}, 13, 2^{∗}3^{∗}, 1^{∗}3^{∗}}

is a rank 2 greedy set. Take the particular function f : [3] ∪ [3]^{∗} → ℝ defined by f(1) = 1; f(2) = 2; f(3) = 3; f(3^{∗}) = 4; f(2^{∗}) = 5; f(1^{∗}) = 6. This is an admissible function because it is compatible with the ordering 1 ≺ 2 ≺ 3 ≺ 3^{∗} ≺ 2^{∗} ≺ 1^{∗}. The greedy algorithm applied to M chooses the set 1^{∗}3^{∗} whose total weight is 10, greater than that of any other set in M.

On the other hand, for the function f(1) = 4; f(2) = 2; f(3) = 3; f(3^{∗}) = 1; f(2^{∗}) = 5; f(1^{∗}) = 6, which is not admissible, the greedy algorithm again chooses the set 1^{∗}3^{∗} whose total weight is 7, but the total weight of 12^{∗} is 9. The greedy algorithm fails in this case. Note that the collection M is not an ordinary matroid on the set [3] ∪ [3]^{∗}.

Example 4.5 Cyclic case. This is a continuation of Example ?? of Section 3. Consider the case n = 4, and take the admissible weigh function f(1) = 3; f(2) = 4; f(3) = 1; f(4) = 2. The set

M = {13, 24}

is a greedy set for (P, P). The greedy algorithm chooses 13 whose weight is 6, greater than the other element of M. On the other hand, for the weight function f(1) = 1; f(2) = 3; f(3) = 5; f(4) = 4, which is not admissible, the greedy algorithm fails for M.

Example 4.6 Bipartite case. This is a continuation of Example ?? of Section 3. Consider the case n = 2; clearly

M = {12, 1^{∗}2^{∗}}

is a greedy set. An admissible function is one for which either f(i) < f(j) for every unstarred i and starred j or f(i) < f(j) for every starred i and unstarred j. As a simple example, let f(1) = 1; f(2) = 2; f(1^{∗}) = 3; f(2^{∗}) = 4. Then f is admissible, and the greedy algorithm chooses 1^{∗}2^{∗} which has total weight 7 compared to the total weight 3 of 12. On the other hand the function f(1) = 3; f(2) = 4; f(1^{∗}) = 1; f(2^{∗}) = 5, is not admissible. The greedy algorithm chooses 1^{∗}2^{∗} which has total weight 6, although 12 has greater total weight 7.

5 Roots and Polytopes

In light of Theorems ?? and ??, it is important to have an efficient method to determine whether a collection L ⊆ P_{k} is a greedy set. If (P, P) is such that |P | = n and P consists of N linear orderings of P, then N may well be exponential as a function of n. If L is a collection of k-element subsets of P, then it will take no less than exponential time to check, using the definition, whether L is a greedy set. An alternative procedure is sought that is polynomial in n and the cardinality of L. In the matroid case, any one of many cryptomorphic definitions of matroid can be used to do this; that is one of the nice properties of matroids. For ordinary and symplectic matroids, the associated matroid polytope [?] furnishes an efficient procedure to determine whether a set is greedy. For the general case, we have the geometric approach of Theorem ?? and the remarks that follow it.

Because of Theorem ??, it will be assumed throughout this section that P = [n] and P contains only linear orders. Each linear order ≺ in P can be denoted by the permutation π for which π(1) ≺ π(2) ≺ … ≺ π(n). Given the pair (P, P), we will associate a polytope Δ(L) to each subset L ⊆ P_{k} as follows. Let ϵ_{1}, …, ϵ_{n} be the canonical orthonormal basis for n-dimensional Euclidean space ℝ^{n}. For any k-element subset A of P, set

δ_{A} = ∑_{i∈A} ϵ_{i}.  (1)

Let Δ(L) be the convex hull of the points {δ_{A} | A ∈ L}. Notice that Δ(L) lies in the (n-1)-dimensional hyperplane in ℝ^{n} with equation ∑_{i=1}^{n} x_{i} = k.

A vector v = (x_{1}, x_{2}, …, x_{n}) ∈ ℝ^{n} will be called π-admissible for (P, P) if 0 < x_{π1} < x_{π2} < … < x_{πn}. A vector that is π-admissible for some π ∈ P will simply be called admissible.

Theorem 5.1 A subset L ⊆ P_{k} is a rank k greedy set for (P, P) if and only if, for each admissible vector v, the linear function f_{v}(x) = ⟨x, v⟩ attains a maximum on Δ(L) at a unique vertex.

Proof: If v = (x_{1}, …, x_{n}), then

f_{v}(δ_{A}) = ∑_{i∈A} x_{i}.

Notice that, for A, B ∈ P_{k} and π ∈ P, we have, by Proposition ?? and the remark following it, that A ≺ B in the π-Gale order if and only if f(A) < f(B) for all positive weight functions f compatible with ≺_{π}. This is equivalent to ∑_{i∈A} f(i) < ∑_{i∈B} f(i) for all positive weight function such that 0 < f(π1) < f(π2) < ⋯ < f(πn). But this, in turn, is the same as f_{v}(δ_{A}) = ∑_{i∈A} x_{i} = ∑_{i∈B} x_{i} = f_{v}(δ_{B}) for all π-admissible vectors v. Thus the linear function f_{v}(x) = ⟨x, v⟩ attains a maximum on Δ(L) at a unique vertex for each admissible vector v if and only if there is a unique π-Gale maximum in L for each π ∈ P. But the latter condition is the definition of greedy set. □

Define a root of (P, P) as a vector r = ±(x_{1}, x_{2}, …, x_{n}) that satisfies the following properties.

1. x_{i} = 0, 1 or −1 for all i,

2. ∑_{i=1}^{n} x_{i} = 0, and

3. ∑_{i=1}^{m} x_{πi} ≥ 0 for every π ∈ P and for each m = 1, …, n.

In particular, note that ϵ_{i} −ϵ_{j} is a root of any pair (P, P) for all i ≠ j. Our definition of root of (P, P) is meant as a generalization of the root system of a Coxeter group. In the group case, we refer to a root of (P, P(G)) as a root of G. The group acts on the set of roots, as well as on the set of admissible vectors. The roots in the following examples are easy to compute.

Example 5.2 For either the symmetric group S_{n} or the alternating group A_{n} acting on [n], the roots are R = {ϵ_{i} − ϵ_{j} | i ≠ j}.

Example 5.3 For the cyclic group Z_{n} of Example ?? acting on [n], the roots are {± ∑_{j=1}^{2m}(−1)^{j}ϵ_{i_{j}}}, where i_{1} < i_{1} < ⋯ < i_{2m}. In other words, +1 and −1 alternate in the vector r. For example, with n = 5, the vector (1, 0, −1, 1, −1) is a root while (1, −1, 0, −1, 1) is not.

Example 5.4 For the symplectic group B_{n} of Example ?? acting on [n] ∪ [n]^{∗} the roots are R∪{ϵ_{i}+ϵ_{j} −ϵ_{i^{∗}} +ϵ_{j^{∗}} | i ≠ j, j^{∗}}. For example, for n = 3, the vector (1, −1, 0, 0, 1, −1) is a root.

Example 5.5 For the bipartite group of Example ?? acting on [n] ∪ [n]^{∗}, let ϵ = ϵ_{1} + ⋯ + ϵ_{n} and ϵ^{∗} = ϵ_{1^{∗}} + ⋯ + ϵ_{n^{∗}}. The roots are R ∪ {ϵ, ϵ^{∗}}.

Lemma 5.6 Let r be a vector satisfying conditions (1) and (2) in the definition of root. Then r is a root if and only if r^{⊥} contains no admissible vector.

Proof: Assume that r = (y_{1}, …, y_{n}) is orthogonal to some admissible vector v = (x_{1}, …, x_{n}). Since v is admissible, there is a π ∈ P such that 0 < x_{π1} < x_{π2} < … < x_{πn}. We have ∑_{i=1}^{n} x_{πi}y_{πi} = ∑_{i=1}^{n} x_{i}y_{i} = 0. Let A = {i | y_{πi} = +1} and B = {i | y_{πi} = −1}. Then ∑_{i∈A} x_{πi} = ∑_{i∈B} x_{πi}. Assume, by way of contradiction, that r is a root. Condition (3) in the definition of root implies (without loss of generality) that there is a bijection ϕ from A onto B so that ϕ(i) > i. But this implies that ∑_{i∈A} x_{πi} < ∑_{i∈B} x_{πi}, a contradiction.

Conversely, assume that r = (y_{1}, …, y_{n}) is not a root. We use the same notation A and B as above. Without loss of generality we can ignore the 0 entries in r and assume that A∪B = [n] and that 1 ∈ A. Define a bijection ϕ from A to B recursively as follows. Let ϕ(1) be the least element of B. Having defined ϕ(i) for i < j, define ϕ(j) as the least element of B not already in the image of ϕ. Let C = {i ∈ A | ϕ(i) > i} ∪ {ϕ(i) ∈ B | ϕ(i) > i} and D = {i ∈ A | ϕ(i) < i} ∪ {ϕ(i) ∈ B | ϕ(i) < i}. Since r is not a root, C and D are nonempty. An admissible vector v = (x_{1}, …, x_{n}) can now be chosen so that ∑_{i∈C} x_{i}y_{i} and ∑_{i∈D} x_{i}y_{i} take arbitrary positive and negative values, respectively. In particular, an admissible vector v can be chosen so that ⟨r, v⟩ = ∑_{i∈C∪D} x_{i}y_{i} = 0. □

Theorem 5.7 Let P be a collection of linear orderings of a finite set P and let L ⊆ P_{k}. If every edge of Δ(L) is parallel to a root, then L is a greedy set for (P, P).

Proof: Assume that L is not a greedy set. By Theorem ?? there exists an admissible vector v = (x_{1}, …, x_{n}) such that the linear function f_{v} achieves its maximum on at least two vertices of Δ(L). Since Δ(L) is convex, f_{v} achieves its maximum on some edge e of Δ(L). Therefore ⟨e, v⟩ = 0. By Lemma ??, e is not parallel to a root. □

Unfortunately the converse of Theorem ?? is, in general, false. There exist greedy sets L for which the polytope Δ(L) has non-root edges. As an example, consider the cyclic group Z_{5} acting on the poset [5] = {1, 2, 3, 4, 5}. This is the group case n = 5 in Example ??. If

L = {12, 23, 34, 15, 35},

then L is a greedy set: The (Gale) maximum is 35 for the order 12345; 15 for the order 23451; 12 for the order 34512; 23 for the order 45123; and 34 for the order 51234. It is easy to check that the segment joining δ_{12} and δ_{34} is an edge e of Δ(L) but that e = (1, 1, −1, −1, 0) is not a root because condition (3) in the definition fails.

Recall from Section 3 that in the group case it is natural to require that L be contained in a single orbit Q_{k} ⊆ P_{k} under the action of G. This is, however, not the case in the above example; L is not contained in a single orbit of P_{2} under the action of Z_{5}. This motivates the following question.

Question 5.8 Let G is a permutation group acting on P, and let Q_{k} be an orbit of G acting on P_{k}. Is it true that L ⊆ Q_{k} is a rank k greedy set for (P, P(G)) if and only if every edge of Δ(L) is parallel to a root of G?

In certain cases the question can be answered in the affirmative. An edge of a polytope Δ in ℝ^{n} will be called supporting if it is contained in a supporting hyperplane of Δ that is orthogonal to an admissible vector. According to Lemma ??, an edge not parallel to a root must be orthogonal to some admisssible vector; so it is possible for such an edge to be supporting. On the other hand, an edge that is parallel to a root cannot be supporting. A set L ⊆ P_{k} is called supporting if each edge of Δ(L) is either supporting or parallel to a root.

Theorem 5.9 Let P be a collection of linear orderings of a finite set P. Assume that L ⊆ P_{k} is supporting. Then L is a greedy set for (P, P) if and only if every edge of Δ(L) is parallel to a root.

Proof: In one direction the statement follows directly from Theorem ??. Conversely, assume that some edge e of Δ(L) is not parallel to a root. Because L is supporting, there is an admissible vector v such that e is contained in a supporting hyperplane of Δ(L) that is orthogonal to v. This implies that the linear function f_{v}(x) = ⟨x, v⟩ attains a maximum at both endpoints of the edge e. By Theorem ??, L is not a greedy set. □

Let G be a permutation group acting on P, and let Q_{k} be an orbit under the induced action of G on P_{k}. Sometimes it is the case that any L ⊆ Q_{k} is supporting. This is so, for example, if each vector determined by a point on the boundary of Δ(Q_{k}) is either admissible or orthogonal to a root. It can be shown that this is the case for ordinary and symplectic matroids. In general, it is not the case that any L ⊆ Q_{k} is supporting. Again consider the cyclic group Z_{5} acting on [5]. If

L = {12, 23, 34, 51},

then L is a greedy set, but the edge e = (1, 1, −1, −1, 0) joining δ_{12} and δ_{34} in Δ(L) is not a root and is not supporting. For e to be supporting, there would have to exist an admissible vector v = (x_{1}, …, x_{n}) such that x_{1} + x_{2} = x_{3} + x_{4}. This would imply that either x_{2} < x_{3} < x_{4} < x_{5} < x_{1} or x_{4} < x_{5} < x_{1} < x_{2} < x_{3}. In the first case, the vertex δ_{51} lies outside the hyperplane containing e; in the second case the vertex δ_{23} lies outside the hyperplane containing e. So there does not exist a supporting hyperplane of Δ(L) containing e.

References

[1] A. Borovik, I. Gelfand and N. White, Symplectic matroids, preprint.

[2] A. Bouchet, Greedy algorithm and symmetric matroids, Mathemataical Programming 38 (1987), 147–159.

[3] D. Gale, Optimal assignments in an ordered set: an application of matroid theory, J. Combinatorial Theory 4 (1968), 1073-1082.

[4] I. M. Gelfand and V. V. Serganova, On a general definition of a matroid and a greedoid, Soviet Math. Dokl., 35 (1987), 6-10.

[5] I. M. Gelfand and V. V. Serganova, Combinatorial geometries and torus strata on homogeneous compact manifolds, Russian Math. Surveys 42 (198)7 133-168.

[6] E. Lawler, Combinatorial Optimization, Networks and Matroids, Holt, Rinehart and Winston, New York (1976).

[7] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization - Algorithms and Complexity, Prentice-Hall, Inc. Holt, Englewood Cliffs, New Jersey (1982).

[8] V. V. Serganova, A. Vince and A. Zelevinsky, A geometric characterization of Coxeter matroids, Annals of Combinatorics, to appear.

[9] V. V. Serganova, A. Vince and A. Zelevinsky, The greedy algorithm and Coxeter matroids, preprint.