c Birkh¨auser Verlag, Basel, 2007

Annals of Combinatorics 11 (2007) 79-100

Annals of Combinatorics

0218-0006/07/010079-22 DOI 10.1007/s00026-007-0307-0

A Characterization of Mixed Branching Greedoids Steven J. Tedford Department of Mathematical Sciences, Franklin and Marshall College, Lancaster, PA 17604-3003, USA [email protected] Received July 12, 2005 AMS Subject Classification: 05B99, 05C99 Abstract. Branching greedoids have been defined and characterized for both directed and undirected rooted graphs. Such greedoids can be extended to rooted mixed graphs – graphs with both directed and undirected edges. These greedoids are characterized by a list of forbidden minors. If Ω is a rooted mixed graph, its mixed branching greedoid has the edges of Ω as its ground set and the collection of arborescences as its feasible sets. The set of mixed branching greedoids is exactly the set of local forest greedoids without / {a}, {b}, {c}, {a, b}, {a, c}, {b, c}}) ({a, b, c}, {0, as a minor. Keywords: greedoid, forbidden minor, rooted mixed graph

1. Introduction and Definitions A greedoid G can be defined by a ground set E and a collection F of subsets of E called the feasible sets of G. A mixed branching greedoid is defined on a rooted mixed graph Ωr , where the ground set is the set of edges and the feasible sets are the edge sets of rooted arborescences. We show that a mixed branching greedoid can be characterized by a list of forbidden minors. We build up to this result by introducing preliminary facts relating to the structure of these greedoids and then determine how to place a direction on certain elements of the greedoid. The main result, Theorem 2.3, will be stated in Section 2. In the rest of this section, we will give some definitions and basic results on greedoids. Suppose that A, B1 , and B2 are sets, and i, r are non-negative integers with r ≥ 1. We use the following notation: Z≥0 denotes the set of nonnegative integers, [r] denotes the set {1, 2, . . . , r}; Mi (A) denotes the set of i element submultisets of A; |A| denotes the cardinality of A; and 2A denotes the power set of A. A mixed graph Ω is a 5-tuple (V, E, ι, D, h), where V is the set of vertices, E is the / ι : E → M2 (V ) is the attachment map, D ⊆ E is the set of set of edges with E ∩V = 0, directed edges, and h : D → V is the head map with h(d) ∈ ι(d) for all d ∈ D. 79

80

S.J. Tedford

Let e ∈ E be an edge with ι(e) = {v1 , v2 }. If v1 = v2 then e is called a loop of Ω, / then every edge is otherwise e is a link of Ω. v1 is said to be adjacent to v2 . If D = 0, undirected, i.e., Ω is a graph. If D = E, then every edge is directed, i.e., Ω is a directed graph (digraph). A mixed graph is rooted if there is a distinguished vertex which is called the root. Ωr will denote a mixed graph Ω with root r. We now extend standard graph theory and digraph terminology to mixed graphs. Let Ω be a mixed graph. A path in Ω from v0 to vn is a sequence (v0 , e1 , . . . , vn−1 , en , vn ) with n ≥ 1, ι(ei ) = {vi−1 , vi }, and vi 6= v j for i 6= j. Such a path has length n. A directed path in Ω from v0 to vn is a path in Ω with h(ei ) = vi for all ei ∈ D. A connected mixed graph Ω is a tree if for all vertices vi , v j ∈ Ω, the path from vi to v j is unique. If a tree Ω is rooted with root r, we say Ωr is a rooted tree. A rooted mixed graph Ωr is a rooted arborescence if Ω is a tree and for any vertex v 6= r, the path in Ω from r to v is a directed path. Since arborescences are rooted by definition, we will write arborescence to mean rooted arborescence. We now review the necessary definitions from greedoid theory, most of which come from [4, Chapters 4 and 5]. A greedoid G consists of a finite set E, called the ground set of G, and a nonempty collection, F (G), of subsets of E, called the feasible sets of G, which satisfy the following properties: (1) 0/ 6= X ∈ F (G) implies that there exists x ∈ X with X \ x ∈ F (G). (2) X, Y ∈ F (G) with |X| > |Y | implies that there exists x ∈ X \Y with Y ∪ x ∈ F (G). If no confusion will arise, we use F instead of F (G). Given a feasible set X = {x1 , . . . , xm }, an ordering, x1 , x2 , . . . , xm , of X is a feasible ordering if Xi = {x1 , . . . , xi } ∈ F for all i ∈ [m]. Let G be a greedoid with ground set E and feasible sets F . If e ∈ E is not contained in any feasible set, then e is a loop of G. We also refer to such elements as g-loops. Greedoids that contain no loops are called normal. Given an element e ∈ E, a minimal feasible set, P, containing e, is called an e-path. Given an e-path P, we assume that P = {p1 , . . . , pn } and that p1 , . . . , pn is a feasible ordering of P. A maximal feasible set of a greedoid G is called a basis of G. Any e ∈ E which is contained in every basis of G is called a coloop of G. The rank function of a greedoid G, denoted rG , is a function from 2E into Z≥0 defined by rG (X) = max{|F| : F ∈ F , F ⊆ X}. We let r(G) denote the rank of a greedoid G, r(G) = rG (E). The nullity of a set X ⊆ E is defined by nulG (X) = |X| − rG (X). The closure operator of G, denoted σG , is a function σG : 2E → 2E defined by σG (X) = {e ∈ E : r(X ∪ e) = r(X)}. The kernel closure, λG : 2E → 2E , of G is defined by: λG (X) = {e ∈ E : There exists F ∈ F with e ∈ F and r(X ∪ F) = r(X)}. We will drop the subscript when no confusion will arise. See [4] for more information about these definitions. Two other important collections of subsets of E(G) besides the feasible sets are the rank-feasible sets of G and the partial alphabets of G. A set X ⊆ E is rank feasible if

A Characterization of Mixed Branching Greedoids

81

r(X) = βG (X), where βG (X) = max{|X ∩ B| : B is a basis of G} . A set A ⊆ E is a partial alphabet of G if A can be written as a union of feasible sets. We will denote the collections of rank-feasible sets and partial alphabets of G by R (G) and A (G), respectively. Given a greedoid G, we can delete or contract subsets of E to obtain new greedoids. For any A ⊆ E, we can delete A to obtain a new greedoid G \ A. G \ A is defined by G \ A = (E \ A, F (G \ A)), where F (G \ A) = {F ⊆ E \ A : F ∈ F }. Given a set A ∈ A and Y , a basis of A, we contract A to obtain G/A, which is defined by: G/A = (E \ A, F (G/A)), where F (G/A) = {F ⊆ E \ A : F ∪Y ∈ F (G)}. See [4, Section V.4] for more details about both contractions and deletions. A greedoid H is a minor of G if there exist A ∈ A and B ⊆ E so that H = (G/A) \ B. Two elements a and b are parallel if {a} ∈ F , {b} ∈ F , and {a, b} ∈ / F . (This is not the definition of parallel elements given in [4, Section VII.5].) We generalize this to elements which are parallel in a minor of G. If B ⊆ E and a, b ∈ / B, then a and b are parallel in G \ B if and only if a and b are parallel in G. We say that (A, a, b) is a parallelism if A ∈ A , a, b ∈ / σ(A) and b ∈ λ(A ∪ a). This is equivalent to saying that a and b are parallel in G/A. (Note: Parallelisms were called d-triples in [6] and [7].) Since, when we contract a partial alphabet A, we actually contract only a basis of A and the choice of basis does not matter, we can assume that A ∈ F . Thus, without loss of generality, if (A, a, b) is a parallelism, we can assume that A ∈ F . It is difficult to obtain results which apply to all greedoids. However, by considering additional properties, it becomes possible to obtain results. We now define four such properties: the interval property [4, Section V.5], the local poset property [4, Section VII.2], the local forest property [4, Section VII.4], and the transposition property [4, Section X.1]. After each definition, we state the relationships that exist between the properties. A greedoid G has the interval property if, for any A, B, C ∈ F with A ⊆ B ⊆ C and element a ∈ E \C, A ∪ a ∈ F and C ∪ a ∈ F imply B ∪ a ∈ F . Properties equivalent to the interval property include: Proposition 1.1. ([4, Corollary V.5.8]) Given a greedoid G, the following are equivalent: (1) G has the interval property ; (2) A (G) ⊆ R (G); (3) A, B, C ∈ F and A ∪ B ⊆ C imply A ∪ B ∈ F . A greedoid G has the local poset property if, for any sets A, B, C ∈ F with A, B ⊆ C, we have A ∪ B ∈ F and A ∩ B ∈ F . Proposition 1.1 implies immediately that every local poset greedoid is an interval greedoid. In addition, combining [4, Chapter VII, Lemma 3.2] and [4, Chapter VII, Lemma 4.1], we obtain Proposition 1.2. If G has the interval property, then the following are equivalent:

82

S.J. Tedford

(1) G has the local poset property; (2) G does not contain the following greedoid as a minor: / {a}, {b}, {a, b}, {a, c}, {b, c}, {a, b, c}}) ; ({a, b, c}, {0, (3) Each A ∈ F contains exactly one e-path for each e ∈ A. A greedoid G has the local forest property if G has the local poset property and, for any set A ⊆ E and elements a, b, c ∈ E \ A, with the following feasible sets, A, A ∪ a, A ∪ b, A ∪ {a, b}, A ∪ {a, b, c}, we have either A ∪ {a, c} ∈ F or A ∪ {b, c} ∈ F . It is immediate that the local forest property implies the local poset property. Combining [4, Equation VII.4.2], [4, Theorem VII.4.4], and [4, Lemma VII.4.5], we obtain Proposition 1.3. If G has the local poset property, then the following are equivalent: (1) G has the local forest property; (2) G does not have the following greedoid as a minor:  
/ {a}, {b}, {a, b}, {a, b, c} ; a, b, c}, 0, (3) every path in G has a unique feasible ordering; (4) for all A, B ∈ R , σ(A) ∩ σ(B) ⊆ σ(A ∪ B). A greedoid G has the transposition property, if, for all sets A ⊆ E and elements x, y ∈ E \ A with A ∪ x ∈ F , A ∪ y ∈ F , and A ∪ {x, y} ∈ / F , A ∪ x and A ∪ y are twins. Two sets X, Y ⊆ E are twins if, for every B ⊆ E \ (X ∪ Y ), X ∪ B ∈ F if and only if Y ∪ B ∈ F . We have Lemma 1.4. ([4, Corollary X.1.2]) The interval property implies the transposition property. With all of these properties, if G has property P, then we say that G is a P greedoid, i.e., if G has the interval property, then G is an interval greedoid. 2. The Main Result We consider a specific class of greedoids defined on rooted mixed graphs. These greedoids generalize both undirected branching greedoids ([4, Section IV.2.9], [6]) and directed branching greedoids ([4, Section IV.2.10], [7]). Let Ω r be a rooted mixed graph. The mixed branching greedoid of Ωr , G(Ωr ), has ground set E, and feasible sets F ⊆ E where F is the edge set of an arborescence in Ωr . If Ω is either directed or undirected, this definition is exactly that for directed branching and undirected branching greedoids. It was shown in [8] that G(Ωr ) is a greedoid. The proof of the following proposition, which summarizes the properties of mixed branching greedoids, is straightforward.

A Characterization of Mixed Branching Greedoids

83

Proposition 2.1. Suppose Ωr is a rooted mixed graph. The greedoid G(Ωr ) is an interval greedoid, a local poset greedoid, and a local forest greedoid. Finally, we note that the class of mixed branching greedoids is closed under minors. The proof is left to the reader. Proposition 2.2. Any minor of a mixed branching greedoid is a mixed branching greedoid. These propositions have given a list of sufficient properties for a mixed branching greedoid. We now proceed to show that these properties are also necessary. Theorem 2.3. A greedoid G is a mixed branching greedoid if and only if G is an interval greedoid without any of the following minors: / {x}, {y}, {x, y}, {x, z}, {y, z}, {x, y, z}}) , ({x, y, z}, {0,

(2.1)

/ {x}, {y}, {x, y}, {x, y, z}}) , ({x, y, z}, {0,

(2.2)

/ {x}, {y}, {z}, {x, y}, {x, z}, {y, z}}) . ({x, y, z}, {0,

(2.3)

Using results from the previous section, this is equivalent to saying that mixed branching greedoids are local forest greedoids without / {x}, {y}, {z}, {x, y}, {x, z}, {y, z}}) ({x, y, z}, {0, as a minor. It will simplify notation if we denote the collection of interval greedoids without minors (2.1), (2.2), and (2.3) by M. In order to prove necessity, we use an algorithm that builds a rooted mixed graph from a greedoid G ∈ M. In order to show that this mixed graph is well-defined, and to show that the mixed branching greedoid of this graph is the greedoid we started with, we need a collection of preliminary results, the topic of the next section, and will also need to discuss the roles of directed and undirected edges in a mixed branching greedoid. 3. Preliminary Results We have collected various results relating to greedoid in this section. These results have been roughly organized by general topic. We begin with general results, then discuss reducing nullity in paths, and finally, paths and parallelisms. 3.1. General Results Combining Proposition 1.1 and [4, Theorem V.3.2], we obtain the following lemma. Lemma 3.1. Let G be an interval greedoid. Let A ∈ A (G) and B ⊆ E. If A ⊆ B, then nul(A) ≤ nul(B). The forbidden minor (2.3) separates greedoids in M from general local forest greedoids. This forbidden minor can be generalized to feasible sets, as the next lemma shows.

84

S.J. Tedford

Lemma 3.2. Let A, B, and C be feasible sets in an interval greedoid G without minor (2.3). A ∪ B ∪C is feasible if and only if A ∪ B, A ∪C, and B ∪C are feasible. Proof. Suppose A ∪ B ∪C ∈ F . Since G is an interval greedoid, Proposition 1.1 implies that A ∪ B, A ∪C, and B ∪C ∈ F . Conversely, assume that A∪B ∈ F , A∪C ∈ F , B∪C ∈ F , and that |A| = n, |B| = m, and |C| = l. Fixa feasible ordering for A, B, and C. Recall that Ai = {a1 , . . . , ai } ∈ F for i ∈ [n], B j = b1 , . . . , b j ∈ F for j ∈ [m], and Ck = {c1 , . . . , ck } ∈ F for k ∈ [l]. Let / We will show that A ∪ B ∪C ∈ F by induction on i + j + k. A0 = B0 = C0 = 0. The hypotheses and the interval property imply that if i = 0, j = 0, or k = 0, then Ai ∪ B j ∪Ck ∈ F . Let i ∈ [n], j ∈ [m], and k ∈ [l]. Assume that Ai 0 ∪ B j 0 ∪Ck0 ∈ F , for all i 0 ∈ [n], j 0 ∈ [m], and k0 ∈ [l] with i 0 + j 0 + k0 < i + j + k. Let S = Ai−1 ∪ B j−1 ∪Ck−1 . The induction hypotheses imply that the following sets are all feasible: S, S ∪ ai , S ∪ b j , S ∪ ck , S ∪ {ai , b j }, S ∪ {ai , ck }, S ∪ {b j , ck }. Since G does not have (2.3) as a minor, S ∪ {ai , b j , ck } = Ai ∪ B j ∪Ck ∈ F . Therefore, by induction, A ∪ B ∪C ∈ F . We also need to consider the behavior of σG relative to contractions of feasible elements. Lemma 3.3. Let G be an interval greedoid. Given X ⊆ E and a feasible x ∈ σ(X), σG (X) = σG/x (X \ x) ∪ x. Proof. Consider rG/x (X \ x). By definition, rG/x (X \ x) = max{|F| : F ⊆ X \ x and F ∈ F (G/x)} , which is equivalent to max{|F| : F ⊆ X, x ∈ F, and F ∈ F (G)} − 1. Since, given any feasible set F ⊆ X, augmentation from {x} gives another feasible set H ⊆ X with x ∈ H and |H| = |F|, we have that rG/x (X \ x) = rG (X) − 1. Using this, we obtain  σG/x (X \ x) ∪ x = e ∈ E \ x : rG/x ((X \ x) ∪ e) = rG/x (X \ x) ∪ x = {e ∈ E \ x : rG (X ∪ e) − 1 = rG (X) − 1} ∪ x = {e ∈ E : rG (X ∪ e) = rG (X)} = σG (X). This lemma implies that, in particular, if P ⊆ X is an a-path for some a ∈ X, then σG (X) = σG/P1 (X \ P1) ∪ P1 = σG/P2 (X \ P2) ∪ P2 ··· = σG/P (X \ P) ∪ P.

A Characterization of Mixed Branching Greedoids

85

Lemma 3.4. Let X ∈ A (G) and f ∈ / σ(X) with { f } ∈ F . If a ∈ σG/ f (X) and a ∈ / σG (X), then either {a} ∈ F (G/ f ) or a is a loop in G/ f . Prior to proving this lemma, we need another result. Lemma 3.5. Let G ∈ M. Let a, b ∈ E and Z ⊆ E with (Z, a, b) a parallelism. Let P ⊆ Z ∪ a be an a-path and Q a b-path. If P 6= Q \ b, then P ∪ Q ∈ /F. Proof. We prove this lemma by contradiction. Suppose G ∈ M is a greedoid with a, b ∈ E(G), a set Z ⊆ E(G) with (Z, a, b) a parallelism, an a-path P ⊆ Z ∪ a, a bpath Q with P 6= Q \ b and P ∪ Q ∈ F . Suppose further that G is such a greedoid with minimum rank. Let p1 ∈ F be the initial element of P. Since {p1 } ∈ F and P ∪ Q ∈ F , Q ∪ p1 ∈ F . Notice that (Z \ p1 , a, b) is a parallelism in G/p1 and P \ p1 is an a-path in G/p1 . There are two possible cases. Suppose that p1 ∈ Q. This implies that Q \ p1 is a b-path in G/p1 . Since P 6= Q \ b, P\ p1 6= Q\{p1, b}, so by the assumptions P\ p1 ∪Q\ p1 ∈ / F (G/p1 ). Thus P∪Q ∈ /F. This implies that p1 ∈ / Q, implying that Q ∪ p1 ∈ F . Thus Q is a b-path in G/p1 . Since P \ p1 ∈ / F and Q\ ∈ F , P \ p1 6= Q \ b thus P \ p1 ∪ Q ∈ / F (G/p1 ). Therefore (P \ p1 ∪ Q) ∪ p1 = P ∪ Q ∈ / F (G). This contradicts the assumptions, thus no such greedoid exists. Proof of Lemma 3.4. Assume a is not a loop in G/ f . Since X ∈ A , we can assume, without loss of generality, that X ∈ F . Thus X ∪ a ∈ F , X ∪ f ∈ F , and X ∪ {a, f } ∈ /F. This implies that (X, a, f ) is a parallelism. Lemma 3.5 implies that, for any a-path Q, if Q \ a 6= { f }, then Q ∪ f ∈ / F . Since {a, f } ∈ / F implies that, by definition, a is a loop in G/ f , Q = {a, f } ∈ F . Therefore, {a} ∈ F (G/ f ). 3.2. Reduction of Nullity In order to simplify our arguments, we want to assume that the union of two paths has the minimum nullity possible. The following four results allow us to make this assumption. Lemma 3.6. Let G be an interval greedoid. Let P and Q be distinct paths with feasible orderings p1 , . . . , pn and q1 , . . . , qm with P ∪ Q ∈ / F . Define s, s 0 ∈ [n] and t, t 0 ∈ [m] by: s = max {i | Pi−1 ∪ Q ∈ F }, t = max{i | P ∪ Qi−1 ∈ F }, s 0 = max{i | Pi−1 ∪ Qt ∈ F }, t 0 = max{i | Ps ∪ Qi−1 ∈ F }. Then the following hold. (1) s = s 0 if and only if t = t 0 . ˜ ˜ (2) If s 0 < n or t 0 <
m then there exist a pn -path
P ⊆ P ∪ Q, and a q
m -path Q ⊆ P ∪ Q, with nul P˜ ∪ Q˜ < nul (P ∪ Q), nul P ∪ P˜ ≤ 1, and nul Q ∪ Q˜ ≤ 1.

86

S.J. Tedford

Proof. (1) From the definitions of s, s 0 , t, and t 0 , we have s ≤ s 0 and t ≤ t 0 . Suppose s = s 0 and t < t 0 . Now Qt−1 ∪ Ps−1 ⊆ Qt ∪ Ps−1 ⊆ Qt 0 −1 ∪ Ps−1 , and by the definition of s, each union is feasible. By the definition of t, Qt−1 ∪ Ps ∈ F and by the definition of t 0 , Qt 0 −1 ∪ Ps ∈ F . By the interval property of G, Qt ∪ Ps ∈ F . Yet Qt ∪ Ps = Qt ∪ Ps 0 , which cannot be feasible by the definition of s 0 . This is a contradiction, thus t = t 0 . A symmetrical argument shows that t = t 0 implies s = s 0 . (2) Without loss of generality, assume that s 0 < n. Since Ps 0 −1 ∪ Qt−1 , Ps 0 ∪ Qt−1 , and Ps 0 −1 ∪ Qt are all feasible, Ps 0 ∪ Qt is not feasible, and G is an interval greedoid, Lemma 1.4 implies that Ps 0 ∪ Qt−1 and Ps 0 −1 ∪ Qt are twins. Now P ∪ Qt−1 ∈ F implies P\ ps 0 ∪ Qt ∈ F . Let P˜ be the pn -path contained in P\ ps 0 ∪ Qt ∈ F and Q˜ = Q. Lemma 3.1 implies that
nul P˜ ∪ Q˜ ≤ nul(P \ ps 0 ∪ Q) ≤ nul(P ∪ Q). (3.1) Since (Ps 0 −1 ∪ Qt−1 , ps 0 , qt ) is a parallelism, ps 0 ∈ λ (Ps 0 −1 ∪ Qt ) ⊆ λ(P ∪ Q), which implies that r(P ∪ Q) = r(P \
ps 0 ∪ Q). Thus nul(P \ ps 0 ∪ Q) <
nul(P ∪ Q), which, with (3.1), implies that nul P˜ ∪ Q˜ < nul(P ∪ Q). Also, nul Q˜ ∪ Q = 0 < nul(P ∪ Q)
and since P ∪ P˜ ⊆ P ∪ Qt , Lemma 3.1 implies, by the definition of t, that nul P ∪ P˜ ≤ nul(P ∪ Qt ) = 1. Lemma 3.7. Let e ∈ E and let P and Q be distinct e-paths. Let s, s 0 , t, and t 0 be defined as in Lemma 3.6. Assume that |P| = n and |Q| = m. If s 0 = n and t 0 = m, then nul(P ∪ Q) = 1. Proof. Since there are two distinct e-paths, n, m ≥ 2. Since P ∪ Q ∈ / F and P ∪ Q = Pn−1 ∪ Q, s < s 0 . Lemma 3.6 implies that t < t 0 . We induct on n. Suppose n = 2. Since s < s 0 , this implies that s = 1. Thus Ps ∪ Qt 0 −1 = Pn−1 ∪ Qm−1 ∈ F . Therefore nul(P ∪ Q) = 1. Assume that n > 2, and that for any greedoid G 0 and e0 ∈ E(G0 ), if S 0 and T 0 are distinct e0 -paths in G0 with |S 0 | < |P|, then nul(S 0 ∪T 0 ) = 1. Let p1 be the feasible element of P. Suppose p1 ∈ Q. Thus P \ p1 and Q \ p1 are e-paths in G/p1 . Also |P| > |P \ p1 |, so, by induction, nulG/p1 ((P \ p1) ∪ (Q \ p1)) = 1. This implies that nulG (P ∪ Q) = 1. Assume that p1 ∈ / Q. We first show that p1 ∈ / σ(Q). If p1 ∈ σ(Q), then s = 1 by definition. Thus Qm−1 ∪ p1 ∈ F . Since Q ∪ p1 ∈ / F , we have e ∈ σG (Qm−1 ∪ p1 ) = σG/p1 (Qm−1 ) ∪ p1 , by Lemma 3.3, implying that e ∈ σG/p1 (Qm−1 ). The facts that Qm−1 ∈ A , p1 ∈ / σ(Qm−1 ), e ∈ / σG (Qm−1 ), and e ∈ σG/p1 (Qm−1 ) all imply, with Lemma 3.4, that either {e} ∈ F (G/p1 ) or e is a loop in G/p1 . Since P \ p1 ∈ F (G/p1 ), e cannot be a loop in G/p1 . Also, since {p1 , e} ∈ / F , {e} ∈ / F (G/p1 ). Thus we have a contradiction, so p1 ∈ / σ(Q). Since Q ∪ p1 ∈ F , Q is an e-path in G/p1 . Also, P \ p1 is an e-path in G/p1 . Thus by induction, nulG/p1 ((P \ p1 ) ∪ Q) = 1. This implies that nulG (P ∪ Q) = 1. With the previous two lemmas, whenever we have two distinct e-paths, P and Q, we can assume that nul(P ∪ Q) = 1. If nul(P ∪ Q) > 1, then Lemma 3.7 implies that

A Characterization of Mixed Branching Greedoids

87

˜ Q˜ ⊆ P ∪ either s 0 < n or t 0
< m. Thus, Lemma 3.6 implies that there exist e-paths P, ˜ Q with nul P˜ ∪ Q < nul(P ∪ Q). Repeating this argument, we obtain the following proposition. ˜ Q˜ ⊆ Proposition 3.8. If P
and Q are distinct e-paths, then there exist distinct e-paths P, P ∪ Q with nul P˜ ∪ Q˜ = 1. With this result in mind, we now describe what nul(P ∪ Q) = 1 implies. Lemma 3.9. Let P and Q be e-paths with nul(P ∪ Q) = 1. Let |P| = n and |Q| = m. Let s, s 0 , t, and t 0 be defined as in Lemma 3.6. Then s = s 0 , t = t 0 , n − s = m − t, and for all i ∈ [n − s], ps+i = qt+i . Proof. As in the proof of 3.6, nul((P \ ps 0 ) ∪ Q) < nul(P ∪ Q) = 1, thus (P \ ps 0 ) ∪ Q ∈ F , and therefore P ∪ Q \ qt ∈ F . Similarly, (P \ ps ) ∪ Q ∈ F . This implies that P∪ (Q \ qt ) ∈ F and (P \ ps ) ∪ Q ∈ F . Ps 0 ∪ Qt−1 ∈ F is a basis of Ps 0 ∪ Qt . We contract Ps 0 ∪ Qt−1 . Thus (P \ Ps 0 ) ∪ (Q \ Qt ) ∈ F (G/(Ps 0 ∪ Qt )). Both P \ Ps 0 and Q \ Qt are epaths in G/ (Ps 0 ∪ Qt ), yet both are contained in (P \ Ps 0 ) ∪ (Q \ Qt ), which implies that P \ Ps 0 = Q \ Qt . A symmetrical argument gives P \ Ps = Q \ Qt 0 . Thus s = s 0 , t = t 0 , and n − s = m − t. Also, for any 1 ≤ i ≤ n − s, ps+i = qt+i . 3.3. Parallelisms and Paths Parallelisms play an important role in the structure of greedoids in M. As a result of this, we now consider results directly relating to parallelisms. In particular, we consider how parallelisms and paths can be combined. First we quote a result from Schmidt concerning the existence of parallelisms. Lemma 3.10. ([7, Lemma 3]) Let G be a normal interval greedoid, T, T ∪ e ∈ A , and e ∈ σ(T ). Then there exist Y ⊆ T with Y ∈ F and a ∈ (E \ σ(Y )) ∩ T with (Y, a, e) a parallelism. The behavior of parallelisms with respect to contractions is the subject of the following lemma. Lemma 3.11. Suppose { f } ∈ F , x, y ∈ E \ f , and B ∈ F (G/ f ). Then (B ∪ f , x, y) is a parallelism in G if and only if (B, x, y) is a parallelism in G/ f . Proof. By definition of contraction, B ∪ { f , x} ∈ F , B ∪ { f , y} ∈ F , and B ∪ { f , x, y} ∈ / F if and only if B ∪ x ∈ F (G/ f ), B ∪ y ∈ F (G/ f ), and B ∪ {x, y} ∈/ F (G/ f ). Thus

(B ∪ f , x, y) is a parallelism in G if and only if (B, x, y) is a parallelism in G/ f . We can also combine parallelisms together, as in the following lemma.

Lemma 3.12. Suppose that (A, a, b) and (A, b, c) are parallelisms. Then (A, a, c) is a parallelism. Proof. By definition, λ(A) 6= λ(A ∪ b). Also, λ(A ∪ a) = λ(A ∪ b) = λ(A ∪ c). Thus (A, a, c) is a parallelism.

88

S.J. Tedford

We have shown, when introducing parallelisms, that we can restrict the sets involved to feasible sets. We want to restrict the sets even further, by only looking at the paths involved. Thus we first state [6, Proposition 2.3]. Proposition 3.13. Let G be a local poset greedoid without greedoid (2.3) as a minor. Suppose that a, b ∈ E, (Y, a, b) is a parallelism, P ⊆ Y ∪ a is an a-path, and Q ⊆ Y ∪ b is a b-path. Then P ∪ Q ∈ /F. Using this, we have Lemma 3.14. Let G be a local poset greedoid without greedoid (2.3) as a minor. Suppose that (Y, a, b) is a parallelism. Let P ⊆ Y ∪ a be an a-path and Q ⊆ Y ∪ b be a b-path. Then (P \ a ∪ Q \ b, a, b) is a parallelism. Proof. Without loss of generality, we assume that Y ∈ F . Since P ∪ (Q \ b) ⊆ Y ∪ a, we have P ∪ (Q \ b) ∈ F . Similarly, (P \ a) ∪ Q ∈ F . Furthermore, P ∪ Q ∈ / F by Proposition 3.13. Thus (P \ a ∪ Q \ b, a, b) is a parallelism. We now consider the union of two parallelisms. Lemma 3.15. Let a, b, c ∈ E. Let P be an a-path, Q be a b-path, and R be a c-path. If b
6= c, (P \ a ∪ Q \ b, a, b) and (P \ a ∪ R \ c, a, c) are parallelisms, then Q\b∪R\c, b, c is a parallelism.
˜ ˜ ˜ Proof. If nul(P ∪ Q) > 1, then there exist an a-path P˜ and a b-path
Q with nul P ∪ Q = 1 and P˜ ∪ Q˜ ⊆ P ∪ Q. Thus by Lemma 3.14, P˜ \ a ∪ Q˜ \ b, a, b is a parallelism. Thus we can assume that P \ a ∪ Q \ b ∈ F . Similarly, we can assume that P \ a ∪ R \ c ∈ F . Suppose that p1 is the feasible element of P. Then, by Lemma 3.11, ((P \ a ∪ Q \ b) \ p1 , a, b) and ((P \ a ∪ R \ c) \ p1, a, c) are parallelisms in G/p1 . Repeating this argument, we find that (Q \ (P \ a), a, b) and (R \ (P \ a), a, c) are parallelisms in H = G/(P \ a). Let Q0 = Q \ (P \ a) and R 0 = R \ (P \ a). Also, R 0 , Q0 ∈ F (H). We now induct on |Q0 |. Suppose Q0 = {b}. This implies that {a}, {b} ∈ F (H). Thus, since {a, b} ∈ / F , a and b are twins in H. Since R 0 \ c ∈ F (H) and (R 0 \ c) ∪ a ∈ F (H), we have (R 0 \ c) ∪ b ∈ F (H). Similarly, R 0 ∪ a ∈/ F (H) implies that R 0 ∪ b ∈/ F (H). Thus (R 0 \ c, b, c) is a parallelism in H. Since Q0 = {b}, ((P \ a) ∪ (Q \ b) ∪ (R \ c), b, c) is a parallelism in G. ˜ c˜ ∈ E(G) ˜ ˜ with Q˜ a bFor the induction hypothesis, let G˜ be a greedoid and a, ˜ b,

˜ a, ˜ < |Q0 | and Q˜ \ b, path, R˜ a c-path, ˜ and a˜ feasible. If |Q| ˜ b˜ and R˜ \ c, ˜ a, ˜ c˜ are
˜ c˜ is a parallelism. ˜ then Q˜ \ b˜ ∪ R˜ \ c, parallelisms in G, ˜ b, Let q1 ∈ Q0 be feasible in H. By the definition of contraction, Q0 \ b ∪ a ∈ F , Q0 ∈ F and Q0 ∪ {a} ∈ / F if and only if Q0 \ {q1, b} ∪ a ∈ F (H/q1), Q0 \ q1 ∈ F (H/q1) and Q0 \ q1 ∪ {a} ∈ / F (H/q1 ). Therefore (Q0 \ {q1, b}, a, b) is a parallelism in H/q1 . Consider the cases: Case 1. Suppose q1 ∈ σH (R 0 \ c). This implies that σH (R 0 \ c) = σH ((R 0 \ c) ∪ q1 ) which implies that a, c ∈ / σH ((R 0 \ c) ∪ q1). Furthermore, c ∈ λH ((R 0 \ c) ∪ a) 0 ⊆ λH ((R \ c) ∪ {q1, a}). Thus ((R 0 \ c) ∪ q1, a, c) is a parallelism in H. Case 2. Suppose q1 ∈ / σH (R 0 \ c). Thus (R 0 \ c) ∪ q1 , {q1, a}, and (R 0 \ c) ∪ a ∈ F (H). 0 By Lemma 3.2, (R \ c) ∪ {q1, a} ∈ F (H). Furthermore, (R 0 \ c) ∪ a and R 0 are twins

A Characterization of Mixed Branching Greedoids

89

in H, thus R 0 ∪ q1 ∈ F (H). Now

1 ≤ nulH R 0 ∪ a ≤ nulH R 0 ∪ {q1 , a, } , so R 0 ∪ {q1, a} ∈ / F (H). Thus ((R 0 \ c) ∪ q1, a, c) is a parallelism in H. Therefore, in either case, (R 0 \ c, a, c) is a parallelism in H/q1 . By induction, this implies that ((Q0 \ {q1, b}) ∪ (R 0 \ c), b, c) is a parallelism in H/q1. This and Lemma 3.11 imply that (Q0 \ b ∪ R 0 \ c, b, c) is a parallelism in H = G/(P \ a). Thus (P \ a ∪ Q \ b∪R\c, b, c) is a parallelism in G. Finally, Lemma 3.14 implies that (Q\b∪R\c, b, c) is a parallelism in G. It will also be useful to modify the paths involved in a parallelism. The following results state how this is possible. Lemma 3.16. Let P and P 0 be a-paths with a ∈ / λ((P ∪ P 0 ) \ a). If Q is a b-path with (P \ a ∪ Q \ b, a, b) a parallelism, then a ∈ / σ((P ∪ P 0 ) \ a ∪ Q \ b). Proof. Let |P \ a| = n, |P 0 \ a| = m, and |Q \ b| = l. The paragraph after Lemma 3.3 implies that

a ∈ σG Pn ∪ P 0m ∪ Ql if and only if a ∈ σG/Ql Pn ∪ P 0m . Since (Pn ∪ Ql , a, b) is a parallelism, assume, without loss of generality, that Pn ∪ Ql ∈ F . Let i ∈ [l]. Since G is an interval greedoid, P ∪ Qi ∈ F . Therefore P \ Qi ∈ F (G/Qi ) and a ∈ P \ Qi . Thus a is not a loop in G/Qi . If {a} ∈ F (G/Qi ), then Qi ∪ a would contain an a-path. This contradicts the fact that P ∪ Qi ∈ F , thus {a} ∈ / F (G/Qi ). / σG/Qi−1 (Pn ∪ P 0m ). If qi ∈ σG/Qi−1 (Pn ∪ P 0m ), Either qi ∈ σG/Qi−1 (Pn ∪ P 0m ) or qi ∈ then Lemma 3.3 implies that

a ∈ σG/Qi−1 Pn ∪ P 0m if and only if a ∈ σG/Qi Pn ∪ P 0m . If qi ∈ / σG/Qi−1 (Pn ∪ P 0m ), then Lemma 3.4 implies that

either a ∈ / σG/Qi Pn ∪ P 0m or a ∈ σG/Qi−1 Pn ∪ P 0m . Thus, for all i ∈ [l],

if a ∈ σG/Qi Pn ∪ P 0m , then a ∈ σG/Qi−1 Pn ∪ P 0m . Since a ∈ / σG (Pn ∪ P 0m ), we have a ∈ / σG/Ql (Pn ∪ P 0m ). Thus a ∈ / σG (Pn ∪ P 0m ∪ Ql ). Using this result, we have Lemma 3.17. Let a ∈ E. Let P and P 0 be a-paths, with a ∈ / λ ((P ∪ P 0 ) \ a). If Q is a b-path with (P \ a ∪ Q \ b, a, b) a parallelism, then ((P ∪ P 0 ) \ a ∪ Q \ b, a, b) is a parallelism.

90

S.J. Tedford

Proof. We have a ∈ / σ((P ∪ P 0 ) \ a ∪ Q \ b) from Lemma 3.16. If we show that

λ P ∪ P 0 ∪ Q \ b = λ (P ∪ P 0 ) \ a ∪ Q , then b ∈ / σ ((P ∪ P 0 ) \ a ∪ Q \ b) and ((P ∪ P 0 ) \ a ∪ Q \ b, a, b) will be a parallelism. We have P ∪ P 0 ∪ Q \ b = P 0 \ a ∪ (P ∪ Q \ b)
⊆ λ P 0 \ a ∪ λ(P ∪ Q \ b)
= λ P 0 \ a ∪ λ(P \ a ∪ Q)

⊆ λ P0 ∪ P \ a ∪ Q . Thus λ (P ∪ P 0 ∪ Q \ b) ⊆ λ ((P ∪ P 0 ) \ a ∪ Q). Similarly, λ ((P ∪ P 0 ) \ a ∪ Q) ⊆ λ (P ∪ P 0 ∪Q \ b). Thus ((P ∪ P 0 ) \ a ∪ Q \ b, a, b) is a parallelism. This result, with Lemma 3.14 gives a useful corollary. Corollary 3.18. Let P and P 0 be a-paths with a ∈ / λ ((P ∪ P 0 ) \ a). If Q is a b-path with 0 (P \ a ∪ Q \ b, a, b) a parallelism, then (P \ a ∪ Q \ b, a, b) is a parallelism. We now look at a series of results further describing the behavior of e-paths involved in parallelisms. Lemma 3.19. Let G ∈ M be a normal greedoid. Suppose P and Q are e-paths with |P| = n and |Q| = m. If e ∈ λ (Pn−1 ∪ Qm−1 ), then (Pn−1 ∪ Qm−2 , e, qm−1 ) and (Pn−2 ∪ Qm−1 , pn−1 , e) are parallelisms. Proof. Since e ∈ λ(Pn−1 ∪ Qm−1 ), Lemma 3.10 implies that there is a Y ⊆ Pn−1 ∪ Qm−1 and an a ∈ Pn−1 ∪ Qm−1 with (Y, e, a) a parallelism. Let R ⊆ Y ∪ e be an e-path. Let S ⊆ Y ∪ a be an a-path. Then ((R \ e) ∪ (S \ a), e, a) is a parallelism by Proposition 3.13. Since no feasible subset of Pn−2 ∪Qm−2 ∪e contains e, R\e is either a pn−1 -path or a qm−1 -path. Assume R\e is a pn−1 -path. Corollary 3.18 implies that (Pn−1 ∪ (S \ a), e, a) is a parallelism. For some j ∈ [m], a = q j . Since e ∈ / λ (Pn−1 ∪ Qm−2 ), j = m − 1. Thus Corollary 3.18 implies that (Pn−1 ∪ Qm−2 , e, qm−1 ) is a parallelism. Symmetrically, (Pn−2 ∪ Qm−1 , pn−1 , e) is also a parallelism. Lemma 3.20. Suppose that P and Q are e-paths with nul(P ∪ Q) > 1. Let P˜ and Q˜ be
˜ \e . the e-paths given in Lemma 3.6. Then e ∈ λ((P∪Q)\e) if and only if e ∈ λ (P˜ ∪ Q)



˜ \ e . Since P˜ ∪ Q˜ \ e ⊆ (P ∪ Q) \ e, λ P˜ ∪ Q˜ \ e ⊆ Proof. Suppose e ∈ λ (P˜ ∪ Q) λ((P ∪ Q) \ e). Thus e ∈ λ((P ∪ Q) \ e). Conversely, assume e ∈ λ((P ∪ Q) \ e). Without loss of generality, assume s 0 < n. ˜ = k, and |Q| = m. Suppose s 0 = n − 1. Thus (Pn−2 ∪ Qt−1 , pn−1 , qt ) Let |P| = n, |P| is a parallelism. This implies that pn−1 ∈ λ (Pn−2 ∪ Qt ) ⊆ λ (Pn−2 ∪ Qm−1 ). Yet e ∈ λ (Pn−1 ∪ Qm−1 ) = λ(Pn−2 ∪ Qm−1 ). This contradicts the fact that P and Q are e-paths, thus s 0 < n − 1. Therefore, P˜k−1 is a pn−1 -path.
By Lemma 3.19, (Pn−1 ∪ Qm−2 , e, qm−1 ) is a
parallelism. Also, e ∈ / λ Pn−1 ∪ P˜k−1 . Thus
by Corollary
3.18,
P˜k−1 ∪ Qm−2 , e, qm−1 is a parallelism. Thus e ∈ λ P˜k−1 ∪ Qm−1 = λ P˜ ∪ Q˜ \ e .

A Characterization of Mixed Branching Greedoids

91

Lemma 3.21. Suppose P and Q are distinct e-paths. Let |P| = n and |Q| = m. Then e ∈ λ (Pn−1 ∪ Qm−1 ) if and only if pn−1 6= qm−1 and (Pn−2 ∪ Qm−2 , pn−1 , qm−1 ) is not a parallelism. Proof. Proposition 3.8 and Lemma 3.20 allow us to assume that nul(P ∪ Q) = 1. Let s, s 0 , t, t 0 be defined as in Lemma 3.6. Lemma 3.9 implies that s = s 0 , t = t 0 , n − s = m −t, and for all 1 ≤ i ≤ n − s, ps+i = qt+i . Also, by definition, (Ps−1 ∪ Qt−1 , ps , qt ) is a parallelism. If e ∈ λ (Pn−1 ∪ Qm−1 ), then Pn−1 ∪ Qm−1 ∈ F . Thus by the uniqueness of paths in feasible sets, Qm−1 is not a pn−1 -path. Thus pn−1 6= qm−1 . By Proposition 3.13, (Pn−2 ∪ Qm−2 , pn−1 , qm−1 ) is not a parallelism. Conversely, if e ∈ / λ(Pn−1 ∪ Qm−1 ), then Pn−1 ∪ Qm−1 ∈ / F . So s < n and t < m. Thus either s = n − 1 and t = m − 1, implying (Pn−2 ∪ Qm−2 , pn−1 , qm−1 ) is a parallelism, or s < n − 1 and t < m − 1, implying pn−1 = qm−1 . Finally, we show that there are at most 2 e-paths contained in A ∪ e for a feasible set A and an element e in the kernel closure of A. Lemma 3.22. Let G ∈ M and A ∈ F (G). If e ∈ λ(A), then there exist at most two e-paths in A ∪ e. Proof. Suppose P, Q, and R are distinct e-paths in A ∪ e with lengths n, m, and l, respectively. Thus Pn−1 ∪ Qm−1 ∈ F , Pn−1 ∪ Rl−1 ∈ F , and Qm−1 ∪ Rl−1 ∈ F , which implies that e ∈ λ (Pn−1 ∪ Qm−1 ) ∩ λ(Pn−1 ∪ Rl−1 ) ∩ λ(Qm−1 ∪ Rl−1 ). We will prove a contradiction. Lemma 3.2 implies that Pn−1 ∪ Qm−1 ∪ Rl−1 ∈ F . Since P∪Q∪R contains more than one e-path, the local poset property of G implies that P∪Q∪R ∈ / F . Let X ⊆ Qm−1 and Y ⊆ Rl−1 be such that P ∪ X ∪Y ∈ F and |X| + |Y | is maximal. We want to show that X = Qm−1 or Y = Rl−1 . We assume that X ⊂ Qm−1 and Y ⊂ Rl−1 and obtain a contradiction. Let x ∈ Qm−1 \ X and y ∈ Rl−1 \ Y be such that X ∪ x ∈ F and Y ∪ y ∈ F . Then Pn−1 , X ∪ x ∈, Y ∪ y ⊆ Pn−1 ∪ Qm−1 ∪ Rl−1 ∈ F , thus Pn−1 ∪ (X ∪ x) ∪ (Y ∪ y) ∈ F . Yet |P ∪ X ∪Y | < |Pn−1 ∪ (X ∪ x) ∪ (Y ∪ y)|, so P ∪ X ∪Y can be augmented from Pn−1 ∪ (X ∪ x) ∪ (Y ∪ y). The choice of X and Y makes this impossible; thus X = Qm−1 or Y = Rl−1 . Without loss of generality, assume Y = Rl−1 . Thus P ∪ X ∪ Y ∈ F , yet P ∪ R ⊆ P ∪ X ∪Y , and P ∪ R ∈ / F . Therefore we have a contradiction, so e∈ / λ(Pn−1 ∪ Qm−1 ) ∩ λ(Pn−1 ∪ Rl−1 ) ∩ λ(Qm−1 ∪ Rl−1 ), i.e., there are at most 2 distinct e-paths in A ∪ e. 4. Directed and Undirectable Elements In a mixed branching greedoid, the directed edges play different roles than the undirected edges. We need to be able to distinguish these elements for greedoids in M. In this section, we introduce the idea of undirectable and directed elements, which will be equivalent to undirected and directed edges. Let G = (E, F ) be a greedoid.

92

S.J. Tedford

Definition 4.1. An element e ∈ E is undirectable if there exist elements a, b ∈ E, which form the following minor: / {a}, {b}, {a, b}, {a, e}, {b, e}}) . ({a, b, e}, {0,

(4.1)

Let U(G) ⊆ E denote the set of undirectable elements of the greedoid G. Definition 4.2. An element e ∈ E is directed if there exist elements a, b ∈ E which form the following minor: / {a}, {b}, {a, b}, {a, e}}) . ({a, b, e}, {0,

(4.2)

Let D(G) ⊆ E be the set of directed edges of the greedoid G. Any elements that are not in U are considered directable. The only elements that are directable but not directed are the loops, the coloops, and the feasible elements of G. These edges have a direction which can be applied to them which does not change the greedoid G. We first show that no element can be both undirectable and directed. / Proposition 4.3. If G ∈ M, then U(G) ∩ D(G) = 0. / Furthermore, assume that, among all greeProof. Let G ∈ M with U(G) ∩ D(G) 6= 0. / |E(G)| is minimal. Let e ∈ U(G) ∩ D(G). This doids G0 ∈ M with U (G0 ) ∩ D (G0 ) 6= 0, implies that there exist S, T ∈ F and edges a, b, c, d ∈ E with S ∪ a, S ∪ b, S ∪ {a, b}, S ∪ {a, e}, S ∪ {b, e} ∈ F , T ∪ c, T ∪ d, T ∪ {c, d}, T ∪ {c, e} ∈ F , and

(4.3)

S ∪ e, S ∪ {a, b, e}, T ∪ e, T ∪ {d, e}, T ∪ {c, d, e} 6∈ F . We will prove a contradiction. / First, suppose that T = 0. Suppose that d ∈ σ(S). This implies that d ∈ λ(S). Thus there exists an f ∈ S such that S 0 = S \ f ∪ d ∈ F , and S and S 0 are twins. Since e ∈ D(G), e is a loop in G/d. Yet e is not a loop in G/S 0 . This is a contradiction. Thus d ∈ / σ(S), i.e., S ∪ d ∈ F . Augment S ∪ d from S ∪ {a, e} and S ∪ {b, e} to get S ∪ {a, d} ∈ F and S ∪ {b, d} ∈ F . Thus G has the following feasible sets: S, S ∪ a, S ∪ b, S ∪ d, S ∪ {a, b}, S ∪ {a, d}, S ∪ {b, d}. Since G has the forbidden minor (2.3), this implies that S ∪ {a, b, d} ∈ F . Augment S ∪ {a, e} and S ∪ {b, e} from S ∪ {a, b, d}. Recalling that S ∪ {a, b, e} ∈ / F , this implies that S ∪ {a, d, e} ∈ F and S ∪ {b, d, e} ∈ F . The transposition property, and the fact that S ∪ {a, d, e} ∈ F and S ∪ {c, d, e} ∈ / F , imply that S ∪ {a, c} ∈ F . Similarly, S ∪ {b, c} ∈ F . Augment S ∪ {a, c} and S ∪ {b, c} from S ∪ {a, d, e} and S ∪ {b, d, e} respectively. Now, S ∪ {a, c, e} ∈ / F and S ∪ {b, c, e} ∈ / F since each contains two e-paths, {c, e} and another which does not contain c. Thus S ∪ {a, c, d} ∈ F and S ∪ {b, c, d} ∈ F . This implies that G contains the following feasible sets: S ∪ d, S ∪ {a, d}, S ∪ {b, d}, S ∪ {c, d}, S ∪ {a, b, d}, S ∪ {a, c, d}, S ∪ {b, c, d}.

A Characterization of Mixed Branching Greedoids

93

Thus S ∪ {a, b, c, d} ∈ F . Finally, augment S ∪ {b, d, e} from S ∪ {a, b, c, d} to get either S ∪ {a, b, d, e} ∈ F or S ∪ {b, c, d, e} ∈ F . In either case, there are two distinct e-paths in a feasible set, forming a contradiction. / Let y be a feasible element of T . We now show that there Now, assume T 6= 0. exists an S 0 ⊆ S with the following collection of feasible and nonfeasible sets: S 0 ∪ {y, a}, S 0 ∪ {y, b}, S 0 ∪ {y, a, b}, S 0 ∪ {y, a, e}, S 0 ∪ {y, b, e}, ∈ F ; S 0 ∪ {y, e}, S 0 ∪ {y, a, b, e} ∈ /F.

(4.4)

There are three possibilities, y ∈ S, y ∈ σ(S) \ S, and y ∈ / σ(S). We consider each possibility separately. If y ∈ S, let S 0 = S \ y. Thus since (4.3) holds, and S = S 0 ∪ y, (4.4) holds for S 0 . If y ∈ σ(S) \ S, augment {y} repeatedly from S to get an x ∈ S with (S \ x) ∪ y ∈ F . Let S 0 = S \ x. Now the transposition property implies that S and S 0 ∪ y are twins. Thus since (4.3) holds for S, (4.4) holds for S 0 . If y ∈ / σ(S) let S 0 = S. Now e ∈ σ(S 0 ), e ∈ σ({y}), so e ∈ σ(S 0 ∪ y). Augment 0 S ∪ y from S 0 ∪ {a, e} and S 0 ∪ {b, e} to get S 0 ∪ {y, a} ∈ F and S 0 ∪ {y, b} ∈ F . This implies that S 0 ∪ {y, a, b} ∈ F . Augment S 0 ∪ {a, e} and S 0 ∪ {b, e} from S 0 ∪ {y, a, b} to get S 0 ∪ {y, a, e} ∈ F and S 0 ∪ {y, b, e} ∈ F . Now e ∈ σ (S ∪ {a, b}) ∩ σ(S ∪ y) ⊆ σ (S ∪ {a, b, y}). Thus (4.4) holds for S 0 . Let T 0 = T \ y. In all cases, these facts about S 0 and T 0 imply that e ∈ U(G/y) ∩ D(G/y), which contradicts the assumption that |E(G)| is minimal. Therefore U(G) ∩ / D(G) = 0. Now that we know that U and D are disjoint, it will be useful to consider other equivalent definitions to U. Lemma 4.4. For a greedoid G ∈ M and e ∈ E the following are equivalent. (1) e ∈ U(G); (2) There exist distinct e-paths P and Q such that (P ∪ Q) \ e ∈ F ; (3) There exist a Y ∈ A and a, b ∈ / Y with e ∈ σ(Y ) and with (Y ∪ a, b, e) and (Y ∪ b, a, e) parallelisms. Proof. (1)⇒(2): Suppose e ∈ U. This implies that there exist S ⊆ E and elements a, b ∈ E such that S, S ∪ a, S ∪ b, S ∪ {a, b}, S ∪ {a, e}, S ∪ {b, e} ∈ F and S ∪ e, S ∪ {a, b, e} ∈ /F. Let P ⊆ S ∪ {a, e} and Q ⊆ S ∪ {b, e} be e-paths. Since e ∈ σ(S) \ λ(S), a ∈ P and b ∈ Q; thus P 6= Q. (P \ e) ∪ (Q \ e) ⊆ S ∪ {a, b} ∈ F , therefore (P ∪ Q) \ e ∈ F . Thus there exist two e-paths satisfying condition (2).

94

S.J. Tedford

(2)⇒(3): Let P = p1 · · · pn and Q = q1 · · · qm be e-paths with (P ∪ Q) \ e ∈ F . We need to find a set Y ⊆ A and edges a, b ∈ / Y with e ∈ σ(Y ) and with (Y ∪ a, b, e) and (Y ∪ b, a, e) parallelisms. Let Y = Pn−2 ∪ Qm−2 . Since G is an interval greedoid, Y ∈ F . Since both P and Q are e-paths, e ∈ σ(Pn−2 ) ∩ σ(Qm−2 ) ⊆ σ (Pn−2 ∪ Qm−2 ). Let a = pn−1 and b = qm−1 . Since G is an interval greedoid, Pn−1 ∪ Qm−2 , Pn−2 ∪ Qm−1 , and Pn−1 ∪ Qm−1 are feasible sets. Thus, pn−1 ∈ / σ(Pn−2 ∪ Qm−1 ) and qm−1 ∈ / σ(Pn−1 ∪ Qm−2 ). Furthermore, P ∪ Qm−2 and Pn−2 ∪ Q are feasible, so e ∈ / σ(Pn−1 ∪ Qm−2 ) and e ∈ / σ(Pn−2 ∪ Qm−1 ). P ∪ Qm−2 ∈ F and Pn−2 ∪ Q ∈ F also imply that λ (Pn−1 ∪ Qm−2 ) 6= λ (P ∪ Qm−2 ) ,

(4.5)

λ (Pn−2 ∪ Qm−1 ) 6= λ (Pn−2 ∪ Q) .

(4.6)

λ (P ∪ Qm−2 ) = λ (Pn−1 ∪ Qm−1 ) = λ (Pn−2 ∪ Qm−1 ) .

(4.7)

and It remains to show that

Since nul(P ∪ Q) = 1, nul(Pn−2 ∪ Q) = 0, and nul(P ∪ Qm−2 ) = 0, we have qm−1 ∈ λ(P ∪ Qm−2 ) and pn−1 ∈ λ(Pn−2 ∪ Q). Thus λ(P ∪ Qm−2 ) = λ(P ∪ Qm−1 ) = λ(P ∪ Q) and

λ(Pn−2 ∪ Q) = λ(Pn−1 ∪ Q) = λ(P ∪ Q).

Now Pn−1 ∪ Qm−1 ∈ F , Pn−2 ∪ Qm−2 ∈ F , and pn−1 6= qm−1 (G has unique paths in feasible sets and P 6= Q.), so r(Pn−1 ∪ Qm−1 ) = |Pn−2 ∪ Qm−2 | + 2. Thus r(P ∪ Q) ≥ |Pn−2 ∪ Qm−2 | + 2. Yet, r(P ∪ Q) < |P ∪ Q| = |Pn−2 ∪ Qm−2 | + 3. This implies that r(P ∪ Q) = r(Pn−1 ∪ Qm−1 ). Thus e ∈ λ (Pn−1 ∪ Qm−1 ). Therefore λ (Pn−1 ∪ Qm−1 ) = λ(P ∪ Q), which implies that (4.7) holds. Inequality (4.5) and equation (4.7) together imply that (Pn−1 ∪ Qm−2 , qm−1 , e) is a parallelism. Inequality (4.6) and equation (4.7) together imply that (Pn−2 ∪ Qm−1 , pn−1 , e) is a parallelism. Therefore, Statement (2) implies Statement (3). (3)⇒(1): Assume that for some Y ∈ A and a, b ∈ / Y , (Y ∪ a, b, e) and (Y ∪ b, a, e) are parallelisms. Without loss of generality, we can assume that Y ∈ F . This implies that Y ∪ a, Y ∪ b, Y ∪ {a, b}, Y ∪ {a, e}, Y ∪ {b, e} ∈ F . Yet Y ∪ e ∈ / F and e ∈ σ(Y ∪ {a, b}), so Y ∪ {a, b, e} ∈ / F . Thus e ∈ U. The second property in the above list can immediately be strengthened to the following. Corollary 4.5. If there exist e-paths P = p1 · · · pn and Q = q1 · · · qm in a greedoid G ∈ M, with pn−1 6= qm−1 and (Pn−2 ∪ Qm−2 , pn−1 , qm−1 ) not a parallelism, then e ∈ U. Proof. Since P and Q are e-paths, pn−1 6= qm−1 , and (Pn−2 ∪ Qm−2 , pn−1 , qm−1 ) is not a parallelism, Lemma 3.21 implies that e ∈ λ (Pn−1 ∪ Qm−1 ). Thus with Proposition 3.8 and Lemma 3.20 we can assume that nul(P ∪ Q) = 1. Since p n−1 6= qm−1 and (Pn−2 ∪ Qm−2 , pn−1 , qm−1 ) is not a parallelism, this implies that nul(P ∪ Q \ e) = 0. Thus, by Lemma 4.4, e ∈ U.

A Characterization of Mixed Branching Greedoids

95

Finally, being undirectable is equivalent to a property involving closures, as the following proposition shows. Proposition 4.6. Let G ∈ M and let e ∈ E be an element with {e} ∈ / F . Then e ∈ U if and only if there exist X, Y ∈ A with e ∈ σ(X ∪Y ) and e ∈ / σ(X) ∪ σ(Y ). Proof. Suppose e ∈ U. There exist e-paths P and P 0 with (P ∪ P 0 ) \ e ∈ F . Let X = P\ e and Y = P 0 \ e. Thus e ∈ / σ(X) and e ∈ / σ(Y ), yet e ∈ σ(X ∪Y ), proving the sufficiency. Assume there exist X, Y ∈ A with e ∈ σ(X ∪Y ) and e ∈ / σ(X) ∪ σ(Y ). Since X, Y ∈ A , we can pick any basis of each, so without loss of generality, assume that X and Y are feasible. We induct on |E|. Suppose |E| = 3. Let E = {x, y, e}. Then X = {x} and Y = {y}. Our assumptions imply that {x}, {y}, {x, e}, {y, e} ∈ F . We also have that {e}, {x, y, e} ∈ / F . If {x, y} ∈ / F then σ({x}) = σ({x, y}). Yet e ∈/ σ({x}) and e ∈ σ({x, y}), so {x, y} ∈ F . Thus e ∈ U. Suppose |E| > 3 and for any greedoid G 0 ∈ M with |E(G 0 )| < |E(G)| the proposition holds. Since {e} ∈ / F , |X| ≥ 1. Let Q ∪ e ⊆ Y ∪ e be an e-path. Suppose that for all feasible x ∈ X, e ∈ σ(Q ∪ x). For each x, the facts that e ∈ σ(Q ∪ x) and e ∈ / σ(Q) imply that x ∈ / σ(Q), or, equivalently, Q ∪ x ∈ F and Q ∪ {x, e} ∈ / F . Thus (Q, x, e) is / x 1 , x2 ) a parallelism. If there exist distinct feasible x1 , x2 ∈ X, then by Lemma 3.15, (0, is a parallelism. Yet {x1 , x2 } ⊆ X ∈ F , which forms a contradiction. Thus there exists a unique feasible x ∈ X. Let P ∪ e ⊆ X ∪ e be an e-path. We know x ∈ P. Thus e ∈ λ(Q ∪ x) ⊆ λ(Q ∪ P). By Lemma 3.21 and Corollary 4.5 this implies e ∈ U. Assume there exists x ∈ X with {x} ∈ F and e ∈ / σ(Y ∪ x). Now e ∈ / σG (X), so e∈ / σG/x (X \ x). Also e ∈ / σG/x (Y ). Furthermore, e ∈ σG/x (X \ x ∪Y ). This implies by induction that e ∈ U(G/x). Since e ∈ U(G/x), there exist a set A ⊆ E \ x and a, b ∈ E \ x with A ∪ a, A ∪ b, A ∪ {a, b}, A ∪ {a, e}, A ∪ {b, e} ∈ F (G/x) and A ∪ e, A ∪ {a, b, e} ∈ / F (G/x). This implies that e ∈ U(G), by the fact that if A0 = A ∪ x, then A0 ∪ a, A0 ∪ b, A0 ∪ {a, b}, A0 ∪ {a, e}, A0 ∪ {b, e} ∈ F (G), and A0 ∪ e, A0 ∪ {a, b, e} ∈ / F (G). Thus e ∈ U(G). 5. Construction of a Mixed Graph In order to show that greedoids in M are mixed branching greedoids, we need to generate rooted mixed graphs from greedoids in M. That is the purpose of the algorithm introduced in this section. This algorithm uses a function called the feasible height function of a greedoid, which we define. Let G = (E, F ) be a greedoid. For each e ∈ E, let Pe be the set of e-paths in G. The feasible height function of G, hF : E → Z≥−1 , is defined by hF (e) = min {|P| : P ∈ Pe } − 1.

96

S.J. Tedford

We let hF (G) = max {hF (e) : e ∈ E}. If P is an e-path with |P| − 1 = hF (e), we say that P is a minimal e-path. The feasible height function partitions E as follows: E−1 = L, Ei = {e ∈ E : hF (e) = i}, for i = 0, . . . , h, where L is the set of loops of G. For i = 0, . . . , h, let E i = ∪ij=0 E j . We now define an equivalence relation on E. Suppose that a and b are elements
with feasible
height k. We say that a is related to b if a = b, a, b ∈ σ E k−1 , or if E k−1 , a, b is a parallelism. Lemma 5.1. This relationship is an equivalence relation on E. Proof. Suppose that a, b, c ∈ E all have height
k. It is clear that a is related to a. Suppose a is
related to b. If a and
b are in σ E k−1 , then b is related to a. Suppose
that a∈ / σ E k−1 . Thus E k−1 , a, b is a parallelism, which implies that E k−1 , b, a is a parallelism. Thus b is related to a.
Suppose that a is related to b and

b is related to c. If a ∈ σ E k−1 , then b
∈ σ E k−1 , implying / σ E k−1 .
that c ∈ σ E k−1
. Thus a is related to c. Assume that a ∈ Thus E k−1
, a, b and E k−1 , b, c are parallelisms. By Lemma 3.12, this implies that E k−1 , a, c is a parallelism. Thus a is related to c. Therefore this relation is an equivalence relation. For any e ∈ E, let hei be the equivalence class containing e. We now give an algorithm for constructing mixed graphs from a G ∈ M. Let U ⊆ E be the set of undirectable elements and D ⊆ E be the set of directable elements except for the set L of g-loops. Let ni = |Ei | and let Ei = {e1 , e2 , . . . , eni } be ordered (arbitrarily). For each 0 ≤ k ≤ hF (G) and 1 ≤ j ≤ nk we let ek, j be the j-th element in the set Ek . We will associate two vertices with each element of E, ι1 (e) and ι2 (e). If e ∈ D, then h(e) = ι2 (e). Algorithm. (0) (1) (2) (3) (4) (4a) (4b) (5) (6) (7)

/ Let V = {v0 }, t = 1, and T = 0. For k = 0 to hF (G), do. For j = 1 to nk , do.
Let P ⊆ E¯k−1 be a path such that P ∪ ek, j is
a minimal ek, j -path. Set ι1 ek, j = / then τ(P) = v0 . τ(P). Notice that if P = 0, If ek, j ∈ λ (E¯k−1 ), then go to step

(4b),  otherwise go to step (4a).
/ then let f ∈ ek, j ∩
T be the first in the ordering. Set ι2 ek, j = If ek, j ∩ T 6= 0, ι2 ( f ). Otherwise, V ← V ∪ vt , ι2 ek, j = vt , and t ← t + 1. ¯ There exists an α < k, an eα, iα ∈ Eα and a Q ⊆ E
α−1 with Q∪eα a minimal eα -path such that ek, j
∈ σ(P ∪ Q ∪
eα ). Define ι e
2 k, j = τ (Q ∪ eα ).

Define  ι ek, j = ι1 ek, j , ι2 ek, j . If ek, j ∈ D, define h ek, j = ι2 ek, j . T ← T ∪ ek, j . Next j. Next k.

A Characterization of Mixed Branching Greedoids

97

(8) For each e ∈ E−1 , define ι(e) = {v0 , v0 }. Output: A rooted mixed graph Ωv0 = (V, E, ι, D, h). Two mixed graphs Ω = (V, E, ι, D, h) and Ω0 = (V 0 , E 0 , ι0 , D0 , h0 ) are isomorphic if there exists a map φ = (φv , φe ) : (V, E) → (V 0 , E 0 ) satisfying (1) φ is a bijection, and φe (D) = D0 , (2) φv (ι(e)) = ι0 (φe (e)), for all e ∈ E, (3) φv (h(d)) = h0 (φe (d)), for all d ∈ D. If Ωr and Ω0r 0 are isomorphic mixed graphs and the isomorphism φ maps r to r 0 , then they are isomorphic rooted mixed graphs, and φ is called a rooted mixed graph isomorphism. It is clear, from the definitions and steps in the algorithm that each step is well defined. We next show that the choices involved in the algorithm do not affect the resulting mixed graph. Lemma 5.2. Let G ∈ M. Suppose that Ω is the output of the algorithm applied to G. Ω is well defined, i.e., Ω is independent of the choices made during the running of the algorithm. Proof. There are exactly two steps in which a choice is possible, step (4b) and step (3). We need to show that these choices do not matter. Suppose G ∈ M. Let Ω(G) be an output of the algorithm applied to G with a specific ordering on its elements. Suppose that e ∈ E with hF (e) = k. Ω(G) will be independent of the choices made if we show the following: (1) Suppose that e ∈ / σ (E¯ k−1 ). For any minimal e-paths P ∪ e, and P 0 ∪ e, τ(P) = τ (P 0 ). (2) Suppose that e ∈ σ (E¯k−1 ). For any minimal e-paths P ∪ e, and P 0 ∪ e, and any minimal paths Q ∪ f ⊆ E¯k−1 and Q0 ∪ f 0 ⊆ E¯k−1 with e ∈ σ(P ∪ Q ∪ f ) and e ∈ σ(P 0 ∪ Q0 ∪ f 0 ), then {τ(P), τ(Q ∪ f )} = {τ(P 0 ), τ(Q0 ∪ f 0 )}. We consider each case separately. / Thus τ(P) = v0 = τ(P 0 ). Assume Case 1. We use induction. If k = 0, then P = P 0 = 0. 0 that k > 0. Assume that P is an a-path and P is an a0 -path. Since e ∈ / σ (E¯k−1 ), we 0 know that e ∈ / σ(P ∪ P ). This implies, from Lemma 3.21, that either a = a0 or (P \ 0 0 a ∪ P \ a , a, a0 ) is a parallelism. If a = a0 , since P ∪ e and P 0 ∪ e are both e-paths, τ(P) = τ(P 0 ). Since e ∈ Ek , we know that a, a0 ∈ Ek−1 and that a, a0 ∈ / σ (E¯k−2 ). Thus 0 0 a is related to a . From step (4a), we know that ι2 (a) = ι2 (a ). By induction, we can assume that τ(P) = ι2 (a) = ι2 (a0 ) = τ(P 0 ). Case 2. Suppose that e ∈ / σ(P ∪ P 0 ). We induct on k. Suppose k = 1. This implies that P = {p} and P 0 = {P 0 }. Since e ∈ / σ(P ∪ P 0 ), 0 0 we have that p and P are parallel. Thus, ι2 (p) = ι2 (P ) from the previous case. Also, / We have that ({p}, e, f ) and ({P 0 }, e, f 0 ) are parallelisms. Since e ∈ Q = Q0 = 0. / λ({p} ∪ {P 0 }), Corollary 3.18 implies that ({p}, e, f 0 ) is also a parallelism. From / f , f 0 ) is a parallelism, i.e., f is parallel to f 0 . Thus, Lemma 3.15, this implies that (0, 0 from case 1, ι2 ( f ) = ι2 ( f ).

98

S.J. Tedford

We now assume that k > 1. We assume that P is an a-path and P 0 is an a0 -path. Since both P ∪ e and P 0 ∪ e are e-paths, Lemma 3.21 implies that either a = a0 , or (P\a∪P 0 \a0 , a, a0 ) is a parallelism. Since both a, a0 ∈ Ek−1 and a, a0 ∈ / E¯k−2 , we know, from Case 1, that τ(P) = τ(P 0 ). Since (P ∪ Q, e, f ) and (P 0 ∪ Q0 , e, f 0 ) are parallelisms and e ∈ / λ(P ∪ P 0 ), Corollary 3.18 implies that (P 0 ∪ Q, e, f ) is a parallelism. This fact and Lemma 3.15 imply that either f = f 0 or (Q ∪ Q0 , f , f 0 ) is a parallelism. If f = f 0 , then τ(Q ∪ f ) = τ(Q0 ∪ f 0 ). Assume that f 6= f 0 . If hF ( f ) = hF ( f 0 ), then, from Case 1, τ(Q) = τ(Q0 ). Assume, without loss of generality, that hF ( f ) < hF ( f 0 ) = l. This implies that f 0 ∈ σ(E¯l−1 ). Thus, by induction and the fact that Q0 is a minimal f 0 -path, τ(Q ∪ f ) = ι2 ( f 0 ) = τ(Q0 ∪ f 0 ). Thus {τ(P), τ(Q ∪ f )} = {τ(P 0 ), τ(Q0 ∪ f 0 )}. Suppose that e ∈ σ(P ∪ P 0 ). This implies that e ∈ U. Thus we have 4 e-paths: P ∪ e, P 0 ∪ e, Q ∪ f ∪ e, Q0 ∪ f 0 ∪ e. Since they are all minimal e-paths, this implies that hF ( f ) = hF ( f 0 ) = hF (a) = hF (a0 ) = k − 1. From Proposition 3.8, we can assume that the nul(X ∪Y ∪ e) = 1 for all X, Y ∈ {P, P 0 , Q ∪ f , Q0 ∪ f 0 }. Assuming that e ∈ σ(X ∪ Y ) for all X, Y implies that X ∪ Y ∈ F . By Lemma 3.2, this implies that P ∪ Q ∪ f ∪ P 0 ∈ F . Yet Lemma 3.22 contradicts this fact. Thus, since e ∈ σ(P ∪ P 0 ) and e ∈ σ(P ∪ Q ∪ f ), e ∈ / σ(P 0 ∪ Q ∪ f ). Similarly, 0 0 e∈ / σ(P ∪ Q ∪ f ). Thus, from the argument in Case 1, we have that τ(P 0 ) = τ(Q ∪ f ) and τ(P) = τ(Q0 ∪ f 0 ). Thus {τ(P), τ(Q ∪ f )} = {τ(P 0 ), τ(Q0 ∪ f 0 )}. This implies that the mixed graph obtained as output from the algorithm is independent of the choices made during the algorithm. Since hei is an equivalence class, from the algorithm we have, for all e ∈ E with hF (e) = k and e ∈ / σ(E¯k−1 ) and all f ∈ hei, ι2 ( f ) = ι2 (e). This implies the following: Lemma 5.3. The mixed graph obtained as the output from the algorithm is independent of the ordering placed on the elements of G. Finally, we consider what occurs to the output when we contract an element. In order to do this, we need the following definition. Suppose that Ω and Ω0 are mixed graphs with sets of g-loops L and L0 . We say that Ωr and Ω0r0 are feasibly isomorphic if there exists a map φ : (V, E) → (V 0 , E 0 ) which, when restricted to Ω \ L, is a rooted mixed graph isomorphism, and φ v , when restricted to L, is a bijection. We denote this by Ω ∼ =F Ω0 . Lemma 5.4. Suppose G ∈ M, and Ω(G) is the resulting mixed graph. Suppose e ∈ F . Then Ω(G/e) ∼ =F Ω(G)/e. Proof. Since Ω(G) is independent of the ordering on the elements, we assume that e = e1, 1 . Thus, since e is not a loop of G, the vertices of e in Ω(G) are v0 and v1 . Thus, the vertex set of Ω(G)/e is v 00 , v 02 , v 03 , . . . , v 0r . We assume that E \ e has the same ordering when we obtain Ω(G/e). The vertex set of Ω(G/e) is {v 0 , v1 , . . . , vr−1 }. We define a map φ by letting φe ( f ) = f for all f ∈ E \ e, and φv (vi ) = v 0i+1 for 1 ≤ i ≤ r − 1 and φv (v0 ) = v 00 .

A Characterization of Mixed Branching Greedoids

99

Suppose f is a g-loop in G/e. This implies that either f is a loop in G, or {e, f } is not a subset of any feasible set of G. For any minimal f -path P in G, e ∈ σ(P). Thus we can assume that ι2 ( f ) = ι2 (e) = v1 . Thus when we contract e from Ω(G), either f will be a loop, or ι2 ( f ) = v0 . So f is a loop in Ω(G)/e. This argument can be reversed to show that the g-loops in Ω(G/e) are the g-loops in Ω(G)/e. Assume that f is not a loop in G/e. This implies that {e, f } ⊆ F ∈ F . We induct on hF ( f ). Assume that hF ( f ) = 0. This implies that e and f are not parallel. Thus, ι2 ( f ) = vi 6= v1 . Since hF /e ( f ) = 0, when G/e is run through the algorithm, ι02 ( f ) = v 0i−1 . Suppose hF ( f ) > 0. We let ι1 ( f ) = vi and ι2 ( f ) = v j . Since ι1 ( f ) was determined by an element with a lower feasible height, we have by induction that ι 01 ( f ) = v 0i−1 . Similarly, since ι2 ( f ) can be considered to be determined by f , we have that ι 02 ( f ) = v 0j−1 . Thus the map φ is a feasible isomorphism. We can now show that the feasible sets of Ω(G) are exactly the feasible sets of G. Theorem 5.5. If G ∈ M and Ω(G) is the mixed graph resulting from the algorithm, then F (Ω(G)) = F (G). Proof. We induct on r(G). Suppose that r(G) = 1. This implies that for all e ∈ E either e is a loop, or e is parallel to any other elements that are not loops. Since h F (e) = 0 for all non loops e, each edge will be connected to the vertices v0 and v1 . Thus the feasible sets of G will be exactly the feasible sets of Ω(G). Suppose r(G) > 1. Let F ⊆ E. Let e be a feasible element of F. By definition, F ∈ F (G) if and only if F \ e ∈ F (G/e). Since r(G/e) = r(G) − 1, F \ e ∈ F (G/e) if and only if F \ e ∈ F (Ω(G/e)) by induction. From Lemma 5.4. F \ e ∈ F (Ω(G/e)) if and only if F \ e ∈ F (Ω(G)/e). Finally, from the definition, F \ e ∈ F (Ω(G)/e) if and only if F ∈ F (Ω(G)). Thus F (G) = F (Ω(G)). 6. The Characterization of Mixed Branching Greedoids We are now in a position to prove Theorem 2.3. Theorem 2.3. A greedoid G is a mixed branching greedoid if and only if G is an interval greedoid without any of the following minors: 
/ {x}, {y}, {x, y}, {x, z}, {y, z}, {x, y, z} , {x, y, z}, 0, 
/ {x}, {y}, {x, y}, {x, y, z} , {x, y, z}, 0, 
/ {x}, {y}, {z}, {x, y}, {x, z}, {y, z} . {x, y, z}, 0,

(2.1) (2.2) (2.3)

Proof. Suppose G is a mixed branching greedoid of a rooted mixed graph (Ω, r). Since G is a local poset greedoid, we know from Proposition 1.2 that G does not contain minor (2.1). Furthermore, G is a local forest greedoid, so by Proposition 1.3 G does not contain the minor (2.2). Finally (2.3) is not a mixed branching greedoid, so, by Proposition 2.2, it must also be a forbidden minor. Suppose G is an interval greedoid without minors (2.1), (2.2), and (2.3). Theorem 5.5 implies that G is the mixed branching greedoid of the mixed graph Ω v0 obtained as output from the algorithm introduced in the last section.

100

S.J. Tedford

Schmidt’s characterizations of the undirected branching greedoid and the directed branching greedoid follow immediately from Theorem 2.3. Corollary 6.1. ([7, Theorem 1]) A greedoid G is a directed branching greedoid if and only if G is a local forest greedoid with the additional property that σ(X) ∩ σ(Y ) ⊆ σ(X ∪Y ) ⊆ σ(X) ∪ σ(Y ) for all X and Y ∈ A . Proof. The above statement is equivalent to saying that a directed branching greedoid is a mixed branching greedoid with the property that for all X, Y ∈ A , σ(X ∪ Y ) ⊆ / σ(X) ∪ σ(Y ). Proposition 4.6 implies that this property is equivalent to U(G) = 0, which implies that G is a mixed branching greedoid of a rooted directed graph. Corollary 6.2. ([6, Theorem 1.5]) A greedoid G is an undirected branching greedoid if and only if it is a local poset greedoid without the following minors: 
/ {x}, {y}, {x, y}, {x, z}, {y, z}, {x, y, z} , {x, y, z}, 0, 
/ {x}, {y}, {x, y}, {x, y, z} , {x, y, z}, 0, 
/ {x}, {y}, {x, y}, {x, z} , {x, y, z}, 0, 
/ {x}, {y}, {x}, {x, y}, {x, z}, {y, z} . {x, y, z}, 0, Proof. Saying a local poset greedoid G does not have these minors is equivalent to saying that G ∈ M and G does not have 
/ {x}, {y}, {x, y}, {x, z} {x, y, z}, 0, as a minor. The lack of this extra minor implies that G has no directed edges, thus every edge can be considered undirected. Therefore, G is a mixed branching greedoid of an undirected graph. References 1. H. Crapo, Selectors: a theory of formal languages, semimodular lattices and shelling processes, Adv. Math. 54 (1984) 233–277. 2. B. Korte and L. Lov´asz, Structural properties of greedoids, Combinatorica 3 (1983) 359– 374. 3. B. Korte and L. Lov´asz, Shelling structures, convexity and a happy end, In: Graph Theory and Combinatorics, B. Bollob´as Ed., Academic Press, London, (1984) pp. 221–243. 4. B. Korte, L. Lov´asz, and R. Schrader, Greedoids, Springer-Verlag, New York, 1991. 5. W. Schmidt, Strukturelle Aspekte in der kombinatorischen Optimierung: Greedoide auf Graphen, Ph.D. Thesis, Universit¨at Bonn, 1985. 6. W. Schmidt, A characterization of undirected branching greedoids, J. Combin. Theory Ser. B 45 (1988) 160–184. 7. W. Schmidt, Greedoids and searches in directed graphs, Discrete Math. 93 (1991) 75–88. 8. S.J. Tedford, A characteristic polynomial for rooted mixed graphs, Discrete Math. 304 (2005) 121–127.