From clutters to matroids

From clutters to matroids Jaume Mart´ı-Farr´e ∗ Departament de Matem`atica Aplicada IV Universitat Polit`ecnica de Catalunya, BarcelonaTech Barcelona, Spain [email protected] Submitted: Nov 20, 2013; Accepted: Dec 23, 2013; Published: Jan 12, 2014 Mathematics Subject Classifications: 05B35, 05C65 Abstract This paper deals with the question of completing a monotone increasing family of subsets Γ of a finite set Ω to obtain the dependent sets of a matroid. Specifically, we provide several natural processes for transforming the clutter Λ of the inclusionminimal subsets of the family Γ into the set of circuits C(M) of a matroid Mwith ground set Ω. In addition, by combining these processes, we prove that all the minimal matroidal completions of the family can be obtained. Keywords: clutter, hypergraph, matroid, circuits. 1 Introduction Amonotone increasing family of subsets Γ of a finite set Ω is a collection of subsets of Ω such that any superset of a set in the family Γ must be in Γ. All the inclusion-minimal elements of Γ determine a clutter Λ, that is, a collection of subsets of Ω none of which is a proper subset of another. Clutters are also known as antichains,Sperner systems or simple hypergraphs. A wide variety of examples of monotone increasing families exist, among them the collection of the linearly dependent subsets of vectors in a vector space. A matroid Mis a combinatorial object that provides an axiomatic abstraction of linear dependence on a finite set Ω. The minimal dependent sets of a matroid Mare called circuits. Therefore, the family of circuits of a matroid Mis a clutter. ∗Supported by the Ministerio de Educaci´on y Ciencia (Spain) and the European Regional Development Fund under project MTM2011-28800-C02-01, and by the Catalan Research Council under project 2009SGR1387. the electronic journal of combinatorics 21(1) (2014), #P1.11 1 We say that a clutter is matroidal if it corresponds to the family of circuits of a matroid. Matroidal clutters, as well as “almost matroidal” clutters, play a key role in several situations. For instance, in the context of secret-sharing schemes they become a crucial issue for providing general bounds on the optimal information rate of the scheme (see [4, 8]). In the framework of algebraic combinatorics and commutative algebra, other interesting examples can be found that deal with monomial ideals and arithmetic properties of the face ring of simplicial complexes (see [1, 9]). Since in general a clutter is far from being matroidal, it is of interest to know how it can be transformed into a matroidal one. This paper deals with the question of finding the matroidal completions of a clutter. The outline of the paper is as follows. In Section 2 we recall some definitions and basic facts about clutters and matroids. Several ways to obtain matroidal completions of clutters can be found in Section 3; namely, we present the uniform completions (Proposition 3), the I-completions (Proposition 5), and the T-completions (Proposition 8). In addition, by means of the clutter transformations involved in these processes, a necessary condition for a clutter to be a matroid port is obtained (Proposition 9). Finally, Section 4 is devoted to analyzing the minimal matroidal completions. We characterize the clutters with only one minimal element (Theorem 12), and we show how to obtain all the minimal matroidal completions of any clutter (Theorem 13). 2 Clutters and matroids In this section we present the definitions and basic facts concerning families of subsets, clutters and matroids that are used in the paper. (The reader is referred to [6, 10] for general references on matroid theory). Let Ω be a finite set. Observe that if Γ is a monotone increasing family of subsets of Ω, then the collection min(Γ) of its inclusion-minimal elements is a clutter; while if Λ is a clutter on Ω, then the family Λ+={A⊆Ω : A0⊆Afor some A0∈Λ}is a monotone increasing family of subsets. Clearly Γ = (min(Γ))+and Λ = min Λ+. So a monotone increasing family of subsets Γ is determined uniquely by the clutter min(Γ), while a clutter Λ is determined uniquely by the monotone increasing family Λ+. Despite the foregoing, we must take into account the following lemma concerning the relationship between the inclusion and the equality of two clutters Λ1and Λ2, and the inclusion and the equality of their associated monotone increasing families of subsets Λ+ 1 and Λ+ 2. Lemma 1. Let Λ1,Λ2be two clutters on a finite set Ω. Then: 1. Λ1= Λ2if and only if Λ+ 1= Λ+ 2. 2. If Λ1⊆Λ2then Λ+ 1⊆Λ+ 2. The converse is not true. 3. Λ+ 1⊆Λ+ 2if and only if Λ1⊆Λ+ 2. the electronic journal of combinatorics 21(1) (2014), #P1.11 2 Proof. The proofs of the statements are a straightforward consequence of the definition of Λ+and of the fact that Λ = min Λ+. So it is only necessary to present an example of clutters with Λ1*Λ2and Λ+ 1⊆Λ+ 2. For instance, on the finite set Ω = {1,2,3}, let us consider the clutters Λ1={{1,2},{2,3}} and Λ2={{1},{2,3}}. Then Λ1*Λ2, while Λ+ 1={{1,2},{2,3},{1,2,3}} ⊆ {{1},{1,2},{1,3},{2,3},{1,2,3}} = Λ+ 2. The previous lemma leads us to consider a binary relation ⩽defined on the set of clutters on Ω. Namely, if Λ1and Λ2are two clutters on Ω, then we say that Λ1⩽Λ2if and only if Λ+ 1⊆Λ+ 2. Therefore, Λ1⩽Λ2if and only if for all A1∈Λ1there exists A2∈Λ2 such that A2⊆A1. It is clear that the binary relation ⩽is reflexive and transitive. Besides, from statement (1) of the previous lemma, the relation ⩽is antisymmetric. Therefore, the binary relation ⩽is a partial order on the set of clutters of Ω. We will use this partial order throughout the paper. There are many interesting families of clutters that can be considered. However, because of their applications, we are interested in clutters that provide matroids. Matroids are combinatorial objects that can be axiomatized in terms of their independent sets, bases, circuits, rank function, flats, or hyperplanes. Here we present the definition in terms of circuits. A matroid Mis an ordered pair M= (Ω,C) consisting of a finite set Ω, called the ground set of the matroid, and a family Cof nonempty subsets of Ω which satisfy the following three conditions: 1. ∅ 6∈ C; 2. if C1, C2∈ C and C1⊆C2, then C1=C2; and 3. if C1and C2are distinct members of Cand x∈C1∩C2, then there is a member C3 of Csuch that C3⊆(C1∪C2)\ {x}. The members of the clutter Care the circuits of the matroid M. We shall often write C(M) instead of C. The dependent sets of the matroid are the supersets of the circuits, that is, the dependent sets of Mare the members of C(M)+. Therefore, the set of dependent sets of the matroid is a monotone increasing family of subsets whose inclusion-minimal elements are its circuits. A clutter Λ is said to be a matroidal clutter if it is the set of circuits of a matroid, that is, if there exists a matroid M0such that C(M0) = Λ. Since the set of circuits of a matroid is a clutter on the ground set of the matroid, we can consider the partial order induced by ⩽on the set of matroids with ground set Ω. Thereby, if M1and M2are two matroids with ground set Ω, then we say that M1⩽M2 if and only if C(M1)⩽C(M2) where C(Mi) is the clutter of the circuits of Mi. So, M1⩽M2if and only if every circuit of M1contains a circuit of M2. In matroid theory this is equivalent to saying that the identity map on Ω is a weak map from the matroid M1to the matroid M2(see [6, Proposition 7.3.11]). the electronic journal of combinatorics 21(1) (2014), #P1.11 3 3 Matroidal completions of a clutter The set of circuits of a matroid is a clutter, but there are clutters on a finite set Ω that are not the set of circuits of a matroid with ground set Ω. So, a natural question that arises at this point is to determine how to complete a clutter Λ to obtain a matroid; that is to say, to transform the clutter Λ into a matroidal clutter. In order to look for matroidal completions, it is important to take into account the dependent sets of the matroid instead of the circuits. This is due to the fact that, as the following example shows, there exist clutters Λ such that Λ *C(M) for any matroid M. Example 2. Let n⩾4. On the finite set Ω = {1,2,3, . . . , n}, we consider the clutter Λ = {{1,2},{1,3},{2,3, . . . , n}}. Observe that {1,2}∪{1,3}\{1}={2,3} {2,3, . . . , n}. Hence it follows that Λ *C(M) for any matroid M. The above example leads us to the following definition. Let Λ be a clutter on a finite set Ω, and let Mbe a matroid with ground set Ω. We say that the matroid Mis a matroidal completion of the clutter Λ if Λ ⊆ C(M)+. In other words, Mis a matroidal completion of Λ if and only if every subset A∈Λ is a dependent set in M. From Lemma 1 we get that Mis a matroidal completion of Λ if and only if Λ ⩽C(M). We will write Λ⩽Minstead of Λ ⩽C(M). The set of all the matroidal completions of a clutter Λ is denoted by Mat(Λ), that is Mat(Λ) = {M : Λ ⩽M}. Observe that if ∅ ∈ Λ then Mat(Λ) = ∅. So, from now on, throughout the paper we assume that ∅ 6∈ Λ if Λ is a clutter. As is shown in the next subsection, this assumption guarantees that Mat(Λ) 6=∅ for all clutters. The aim of this section is to provide three methods in order to obtain matroidal completions of Λ; that is, to obtain matroids Min Mat(Λ). By combining these methods, the minimal matroidal completions will be studied in Section 4. 3.1 Uniform completion The following proposition states that the family of uniform matroids provides matroidal completions of clutters. Recall that if Ω is a finite set of size |Ω|=ωand if m⩽ωis a non-negative integer, then the uniform matroid of rank mon Ω is the matroid Um,ω with ground set Ω and set of circuits C(Um,ω) = {C⊆Ω : |C|=m+ 1}if m < ω and C(Um,ω) = ∅if m=ω. Proposition 3. Let Λbe a clutter on a finite set Ωof size |Ω|=ω. Then, Um,ω ∈Mat(Λ) if and only if m⩽s−1where s= min{|A|:A∈Λ}. Proof. The dependent sets of the uniform matroid Um,ω are those subsets X⊆Ω with |X|⩾m+ 1. Therefore, Λ ⊆ C(Um,ω)+if and only if |A|⩾m+ 1 for all A∈Λ; that is, if and only if s⩾m+ 1. It is clear that Um1,ω ⩽Um2,ω if and only if m1⩾m2. Hence, the uniform matroids in Mat(Λ) form a chain Us−1,ω ⩽· · · ⩽U1,ω ⩽U0,ω whose minimal element is Us−1,ω. We will say that Us−1,ω is the uniform completion of Λ and it is denoted by U(Λ). the electronic journal of combinatorics 21(1) (2014), #P1.11 4 The following example shows that, in general, there are matroids in Mat(Λ) that are not uniform matroids. Moreover, from the example, it follows that in general the uniform completion U(Λ) is not a minimal matroidal completion of Λ. Example 4. On the finite set Ω = {1,2,3,4,5}, we consider the clutter Λ = {{1,2}, {1,3},{2,3,4},{2,3,5}}. We have that Λ ⊆ C(M)+where Mis the matroid with set of circuits C(M) = {{1,2},{1,3},{2,3},{1,4,5},{2,4,5},{3,4,5}}. So Mis a matroidal completion of Λ which is not a uniform matroid. Observe that the uniform matroids in Mat(Λ) are U1,4and U0,4, and here MU(Λ) = U1,4⩽U0,4. 3.2 Completion with intersections: I-transformations In this subsection we prove that it is possible to transform a clutter Λ into a matroidal clutter by adding intersections of suitable subsets of Λ. To present our result we need to introduce some previous definitions. Let Λ be a clutter on a finite set Ω. For a subset X⊆Ω, we denote by IΛ(X) the intersection of the subsets Ain Λ contained in X, (this intersection is the one involved in the characterization of the set of circuits in connected matroids, see [6, Theorem 4.3.2]). We say that a clutter Λ0is an I-transformation of the clutter Λ if Λ0= min Λ∪{A1∩A2} where A1, A2∈Λ are two different subsets with IΛ(A1∪A2)6=∅. Proposition 5. Let Λbe a clutter on a finite set Ω. If Λis not matroidal then there exists a chain of clutters Λ=Λ0Λ1· · · Λrsuch that the clutter Λiis an I-intersection of Λi−1for i⩾1and the clutter Λris a matroidal clutter. Proof. First of all notice that if A1, A2∈Λ are different then, IΛ(A1∪A2) = ∅if and only if for all x∈A1∩A2there exists A3∈Λ with A3⊆(A1∪A2)\ {x}. Therefore we get that a clutter Λ is a matroidal clutter if and only if IΛ(A1∪A2) = ∅for any two different A1, A2∈Λ. The proof of the proposition follows from this equivalence. Indeed, if Λ is not a matroidal clutter, then we get that there exist two different subsets A1, A2∈Λ with IΛ(A1∪A2)6=∅. So we can consider the clutter Λ1= min Λ∪ {A1∩A2}, which is an I-intersection of Λ. Clearly Λ Λ1because A1and A2are different. We now proceed in the same way with the clutter Λ1, and so on. Therefore, by means of I-transformations we can transform a clutter Λ into a matroidal clutter. The matroids obtained in this way will be called I-matroidal completions of Λ. Next we present some examples to show that it no general result exists concerning the comparison between two different I-matroidal completions of a clutter. Example 6. On the finite set Ω = {1,2,3,4,5}, we consider the clutters Λ1, Λ2and Λ3where Λ1={{1,2,3},{1,2,4},{3,4,5}}, Λ2={{1,2,3},{1,2,4},{1,5},{2,5}} and Λ3={{1,2,3},{1,2,4},{4,5}}. It is clear that Λ1has only one I-matroidal completion, the matroid M1with set of circuits C(M1) = {{1,2},{3,4,5}}. The two I-matroidal completions of the clutter Λ2are the matroids M2,1and M2,2with set the electronic journal of combinatorics 21(1) (2014), #P1.11 5 of circuits C(M2,1) = {{1,2},{1,5},{2,5}} and C(M2,2) = {{1,2},{5}}. The two I-matroidal completions of Λ3are the matroids M3,1and M3,2with set of circuits C(M3,1) = {{1,2},{4,5}} and C(M3,2) = {{1,2,3},{4}}. Therefore the I-matroidal completions of Λ2form a chain M2,1⩽M2,2, while the I-matroidal completions of Λ3 are not comparable, that is, M3,1M3,2and M3,2M3,1. 3.3 Completion with unions: T-transformations The aim of this subsection is to present some natural ways to obtain matroidal completions of a clutter Λ, that is, to obtain matroids in Mat(Λ). Unlike in the previous subsection, here we proceed in a recursive way by adding, in each step of the process, some slight modifications of the union of two distinct elements of the clutter. Our result is stated in Proposition 8, and by using these matroidal completions a necessary condition for matroid ports is presented in Proposition 9. Let us start by defining the two elementary transformations involved in the recursive process. Let Λ be a clutter on a finite set Ω. We define the elementary transformations T(1)(Λ) and T(2)(Λ) of Λ as the clutters: • T (1)(Λ) = min Λ∪(A1∪A2)\{x}where A1, A2∈Λ are different and x∈A1∩A2; that is, in the first elementary transformation T(1)(Λ), we consider the minimal elements of the family obtained by adding to Λ those subsets that arise from the circuit condition. • T (2)(Λ) = min Λ∪(A1∪A2)\IΛ(A1∪A2), where A1, A2∈Λ are different}; that is, in the second elementary transformation T(2)(Λ), we add to Λ the subsets obtained from the union after removing the intersections IΛ(X) defined in the previous subsection. Since T(1)(Λ) and T(2)(Λ) are clutters, we can apply the elementary transformations again. Hence, for (i1, i2)∈ {1,2}×{1,2}we can consider the clutter T(i2)(T(i1)(Λ)). At this point we proceed in a recursive way. Let r⩾2 be a non-negative integer and let (i1, . . . , ir)∈ {1,2}rbe an r-tuple. Then we define the clutter T(i1,...,ir)(Λ) by the recursion formula T(i1,...,ir)(Λ) = T(ir)(T(i1,...,ir−1)(Λ)); that is, T(i1,...,ir)(Λ) is the irelementary transformation of T(i1,...,ir−1)(Λ). In this way we obtain the following tree diagram of T-transformations of the clutter Λ, where we write (i1, . . . , ir) instead of T(i1,...,ir)(Λ): the electronic journal of combinatorics 21(1) (2014), #P1.11 6 Λ ttiiiiiiiiiiiiiiiiiiiiiiii ** U U U U U U U U U U U U U U U U U U U U U U U U (1) ||z z z z z z z z "" D D D D D D D D(2) ||z z z z z z z z "" D D D D D D D D (1,1) ||z z z z z z z z  (1,2) "" D D D D D D D D(2,1) ||z z z z z z z z  (2,2) "" D D D D D D D D We will say that a clutter Λ0is a T-transformation of Λ if it is obtained from Λ in this way, that is, if Λ0=T(i1,...,ir)(Λ) for some r-tuple (i1, . . . , ir). The next lemma points out the relationship between two T-transformations, that is, between two clutters of the above diagram. The first statement of the lemma deals with the relationship between clutters in each branch of the diagram, whereas the last two statements deal with the comparison of clutters in a same row of the diagram, that is, the 2rpossible clutters T(i1,...,ir)(Λ). Lemma 7. Let Λbe a clutter on a finite set Ω. Let I= (i1, i2, i3, . . . , is, is+1, . . . )be a sequence with i`∈ {1,2}, and let (j1, . . . , jr),(k1, . . . , kr)∈ {1,2}rbe two r-tuples. Then, the following statements hold: 1. Λ⩽T(i1)(Λ) ⩽T(i1,i2)(Λ) ⩽· · · ⩽T(i1,...,is)(Λ) ⩽T(i1,...,is,is+1)(Λ) ⩽· · · , and there exists r⩾1such that T(i1,...,ir)(Λ) = T(i1,...,ir,ir+1)(Λ). 2. If (j1, . . . , jr−1)=(k1, . . . , kr−1)and jr⩽kr, then T(j1,...,jr)(Λ) ⩽T(k1,...,kr)(Λ). In general this inequality is not an equality. 3. If (j1, . . . , jr−1)6= (k1, . . . , kr−1)then, in general, there is no relationship between the clutters T(j1,...,jr)(Λ) and T(k1,...,kr)(Λ). Proof. From the definitions of the two elementary transformations it follows that if Λ0 is a clutter on Ω then Λ0⩽T(1)(Λ0) and Λ0⩽T(2)(Λ0). Therefore, we have that the iteration of the elementary transformations provides a monotone increasing sequence of clutters Λ ⩽T(i1)(Λ) ⩽T(i1,i2)(Λ) ⩽· · · ⩽T(i1,...,is)(Λ) ⩽T(i1,...,is,is+1)(Λ) ⩽· · · . The proof of statement (1) is concluded by noticing that there are only a finite number of clutters in a finite set. Next let us prove statement (2). It is necessary to prove the inequality T(i1,...,ir−1,1)(Λ)⩽ T(i1,...,ir−1,2)(Λ) and, in addition, we must also show that in general this inequality is not an equality. Clearly, to do this it is enough to prove that if Λ0is a clutter on the finite set Ω then T(1)(Λ0)⩽T(2)(Λ0) and, in addition, we must show that there are clutters Λ0 of Ω with T(1)(Λ0)6=T(2)(Λ0). the electronic journal of combinatorics 21(1) (2014), #P1.11 7 First let us show that T(1)(Λ0)⩽T(2)(Λ0); that is, we must demonstrate that if X∈ T (1)(Λ0), then there exists X0∈ T (2)(Λ0) such that X0⊆X. So let X∈ T (1)(Λ0) = min Λ0∪(A1∪A2)\{x}, where A1, A2∈Λ0are different and x∈A1∩A2. If X=A∈ Λ0, then from the definition of T(2)(Λ0), it follows that there exists X0∈ T (2)(Λ0) with X0⊆X, as we wanted to prove. Therefore, we may assume now that X= (A1∪A2)\{x} where A1and A2are two distinct members of Λ0and where x∈A1∩A2. At this point we distinguish two cases. First suppose that x∈IΛ0(A1∪A2). In such a case we have that (A1∪A2)\IΛ0(A1∪A2)⊆(A1∪A2)\ {x}and from the definition of T(2)(Λ0) we get that there exists X0∈ T (2)(Λ0) with X0⊆(A1∪A2)\IΛ0(A1∪A2). Hence, if x∈IΛ0(A1∪A2), then there exists X0∈ T (2)(Λ0) with X0⊆X. Now assume that x6∈ IΛ0(A1∪A2). Then from the definition of IΛ0(A1∪A2) we get that there exists A3∈Λ0with A3⊆(A1∪A2)\ {x}. Since A3∈Λ0, there exists X0∈ T (2)(Λ0) with X0⊆A3. Therefore, if x6∈ IΛ0(A1∪A2), then there exists X0∈ T (2)(Λ0) with X0⊆X. Thus, in both cases we conclude that there exists X0∈ T (2)(Λ0) such that X0⊆X, that is, T(1)(Λ0)⩽T(2)(Λ0), as we wanted to prove. To finish the proof of statement (2) we must show that there are clutters Λ0with T(1)(Λ0)6=T(2)(Λ0). Let us consider the clutter Λ0={{1,2,3},{1,2,4, . . . , n}} of the finite set Ω = {1,2,3,4, . . . , n}where n⩾4. Then we have that T(1)(Λ0) = {{1,2,3},{1,2,4, . . . , n},{1,3,4, . . . , n},{2,3,4, . . . , n}}, whereas T(2)(Λ0) = {{1,2,3}, {1,2,4, . . . , n},{3,4, . . . , n}}. So in this case we have that T(1)(Λ0)T(2)(Λ0). This completes the proof of statement (2). To finish, let us prove statement (3); namely, we are going to show that in general neither the lexicographic order nor the reverse lexicographic order between r-tuples is preserved by applying T-transformations and, moreover, we prove that there exist clutters Λ for which the T-transformations T(i1,...,ir)(Λ) and T(j1,...,jr)(Λ) are not comparable. On the finite set Ω = {1,2,3,4,5}, we consider the clutters Λ1={{1,2,3},{2,3,4},{4,5}}, Λ2={{1,2,3},{1,4,5},{3,5}} and Λ3={{1,2,3},{2,3,4},{3,4,5}}. For the clutter Λ1 we have that T(1,2)(Λ1) = {{1,5},{4,5},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{2,3,5}} and that T(2,1)(Λ1) = {{1,4},{1,5},{4,5},{1,2,3},{2,3,4},{2,3,5}}, and therefore we have the inequality T(1,2)(Λ1)⩽T(2,1)(Λ1). However, since the transformations (1,2) and (2,1) of the clutter Λ2are T(1,2)(Λ2) = {{2,4},{3,5},{1,2,3},{1,2,5},{1,3,4},{1,4,5}} and T(2,1)(Λ2) = {{3,5},{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,4,5},{2,3,4},{2,4,5}}, then T(2,1)(Λ2)⩽T(1,2)(Λ2). On the other hand, the Ttransformations (1,2) and (2,1) of the clutter Λ3are T(1,2)(Λ3) = {{1,5},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{2,3,5},{2,4,5}, {3,4,5}} and T(2,1)(Λ3) = {{1,4},{2,5},{1,2,3},{1,3,5},{2,3,4},{3,4,5}}, and so we have that T(1,2)(Λ3)T(2,1)(Λ3) and that T(2,1)(Λ3)T(1,2)(Λ3). This completes the proof of the lemma. Now let us consider the “stable” value T(I) ∗(Λ) of the monotone increasing sequence of clutters Λ ⩽T(i1)(Λ) ⩽· · · ⩽T(i1,...,ir)(Λ) ⩽T(i1,...,ir,ir+1)(Λ) ⩽· · · obtained from Λ by using the sequence I= (i1, i2, . . . , ir, ir+1, . . . ) where i`∈ {1,2}; that is, if the electronic journal of combinatorics 21(1) (2014), #P1.11 8 r0= min{r:T(i1,...,ir)(Λ) = T(i1,...,irir+1)(Λ)}, then: T(I) ∗(Λ) = Λ if T(i1)(Λ) = Λ, T(I) ∗(Λ) = T(i1,...,ir0)(Λ) if T(i1)(Λ) 6= Λ. The main result of this subsection is the following proposition, which states that for any sequence Ithe clutter T(I) ∗(Λ) defines a matroid. Proposition 8. Let Λbe a clutter on a finite set Ω. Let I= (i1, i2, i3, . . . )be a sequence where i`∈ {1,2}. Then, the clutter T(I) ∗(Λ) is a matroidal clutter with Λ⩽T(I) ∗(Λ). Furthermore, if r0= min{r:T(i1,...,ir)(Λ) = T(i1,...,ir,ir+1)(Λ)}, then for s⩽r0−1the clutter T(i1,...,is)(Λ) is not matroidal. Proof. From Lemma 7 we get that Λ ⩽T(i1,...,i`)(Λ) for any `-tuple (i1, . . . , i`). Therefore, Λ⩽T(I) ∗(Λ). Recall that by definition T(i1,...,i`)(Λ) = T(i`)(T(i1,...,i`−1)(Λ)). Therefore, to prove the proposition it is enough to demonstrate that if Λ0is a clutter on Ω, then Λ0=T(1)(Λ0) if and only if Λ0is a matroidal clutter, and that Λ0=T(2)(Λ0) if and only if Λ0is a matroidal clutter. In other words, we must prove that Λ0=T(2)(Λ0) if and only if Λ0=T(1)(Λ0), if and only if Λ0is a matroidal clutter. First let us show that if Λ0=T(2)(Λ0) then Λ0=T(1)(Λ0). By applying statements (1) and (2) of Lemma 7 we get that Λ0⩽T(1)(Λ0) and that T(1)(Λ0)⩽T(2)(Λ0). Hence, if Λ0=T(2)(Λ0), then Λ0⩽T(1)(Λ0)⩽T(2)(Λ0) = Λ0and so Λ0=T(1)(Λ0). Now let us show that if Λ0=T(1)(Λ0) then Λ0is a matroidal clutter; that is, we must demonstrate that Λ0satisfies the conditions of the set of circuits of a matroid. So let A1, A2∈Λ0be different and let x∈A1∩A2. Since Λ0=T(1)(Λ0), there exists A3∈Λ0 such that A3⊆(A1∪A2)\ {x}. Therefore, the circuit conditions are fulfilled. Finally it is necessary to demonstrate that if Λ0is a matroidal clutter then Λ0= T(2)(Λ0). Recall that in the proof of Proposition 5 it was stated that a clutter Λ is a matroidal clutter if and only if IΛ(A1∪A2) = ∅for any two different A1, A2∈Λ. Therefore, if the clutter Λ0is a matroidal clutter, then IΛ0(A1∪A2) = ∅if A1, A2∈Λ0 are different, and so T(2)(Λ0) = Λ0. This completes the proof of the proposition. In some way, the stable value of the above proposition indicates how far Λ is from being a matroid. For instance, from the above proposition it follows that a clutter Λ is the set of circuits of a matroid with ground set Ω if and only if there exists a sequence I such that T(I) ∗(Λ) = Λ. A matroid is said to be connected if for every pair of distinct elements of the ground set, there is a circuit containing both. A clutter Λ of a finite set Ω is said to be a matroid port if it corresponds to the set of circuits of a connected matroid containing a fixed point, that is, if there exists a connected matroid Nwith ground set Ω ∪ {ω0}, where ω06∈ Ω, such that Λ = {C\ {ω0}:ω0∈C∈ C(N)}. In such a case it is said that the clutter Λ is the port of the connected matroid Nat the point w0. Matroid ports were introduced by Lehman [2] to solve the Shannon switching game. There are several characterizations of these combinatorial objects which range from exthe electronic journal of combinatorics 21(1) (2014), #P1.11 9