Completion and decomposition of a clutter into representable matroids

COMPLETION AND DECOMPOSITION OF A CLUTTER INTO REPRESENTABLE MATROIDS JAUME MART´ I-FARR´ E AND ANNA DE MIER Abstract. This paper deals with the question of completing a monotone increasing family of subsets Γ of a finite set Ω to obtain the linearly dependent subsets of a family of vectors of a vector space. Specifically, we prove that such vectorial completions of the family of subsets Γ exist and, in addition, we show that the minimal vectorial completions of the family Γ provide a decomposition of the clutter Λ of the inclusion-minimal elements of Γ. The computation of such vectorial decomposition of clutters is also discussed in some cases. 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 Γ also belongs to Γ. 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. In this paper we focus our attention on those monotone increasing families of subsets that arise from linear algebra: the collection of the linearly dependent subsets of vectors in a vector space. We say that a clutter Λ is vectorial if its elements are the inclusion-minimal linearly dependent subsets of an indexed family of vectors of a vector space. Vectorial clutters are an important issue in matroid theory. 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 are called circuits. Therefore, the family of circuits of a matroid Mis a clutter. Vectorial clutters are exactly those corresponding to the set of circuits of representable matroids. In some cases it is convenient to use clutters that are either vectorial or are close to being vectorial. Examples of this situation can be found in the context of secret-sharing schemes [3, 5], or in the framework of algebraic combinatorics and commutative algebra [1, 6]. For instance, in the context of secret-sharing schemes, vectorial clutters become a 1 2 J. MART´ I-FARR´ E AND A. DE MIER crucial issue for providing general bounds on the optimal information rate of the scheme, while in the framework of algebraic combinatorics and commutative algebra, they are useful for controlling certain arithmetic properties of either monomial ideals or the face rings of simplicial complexes. In general, a clutter is far from being vectorial. Therefore it is of interest to determine how it can be transformed into a vectorial clutter. This paper deals with this issue. More specifically, we first define a partial order ⩽on the set of all clutters on Ω. Then a vectorial completion of a clutter Λ is a vectorial clutter Λ0such that Λ ⩽Λ0. We show that these completions exist and that Λ can be recovered from the minimal ones. We speak in this case of a decomposition of the clutter Λ. The structure of the paper is as follows. In Section 2 we recall some definitions and basic facts about clutters and present the problem of the vectorial completion of a clutter. Our main results are gathered in Section 3; namely, we present three theorems concerning vectorial completion and decomposition of clutters (Theorem 4, Theorem 5 and Theorem 6), and we apply them to obtain the decomposition of nonrepresentable matroids into representable matroids (Corollary 7). Finally, Section 4 is devoted to analyzing the computation of such decompositions: first, in Subsection 4.1 we study the vectorial completions and decompositions of clutters on a finite set of size at most seven (Proposition 9); next, in Subsection 4.2 we present the minimal binary completions of the excluded minor of binary matroids (Proposition 12); and we close in Subsection 4.3 by describing the minimal vectorial completions over fields of characteristic two of the non-Fano matroid (Proposition 14). 2. Vectorial clutters and vectorial completions In this section we present the definitions and basic facts concerning families of subsets, clutters and vectorial clutters that are used in the paper. Let Ω be a finite set. A family of subsets Γ of Ω is monotone increasing if any superset of a set in Γ must be in Γ; that is, if A∈Γ and A⊆A0⊆Ω, then A0∈Γ. A clutter of Ω is a collection of subsets Λ of Ω, none of which is a proper subset of another; that is, if A, A0∈Λ and A⊆A0then A=A0. 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 Λ+={A⊆Ω : A0⊆Afor some A0∈Λ}is a monotone increasing family of subsets. Clearly, Γ = COMPLETION AND DECOMPOSITION OF CLUTTERS 3 (min(Γ))+and Λ = min(Λ+). So a monotone increasing family of subsets Γ is uniquely determined by the clutter min(Γ), while a clutter Λ is uniquely determined by the monotone increasing family Λ+. Let Λ1,Λ2be two clutters on Ω. It is clear that if Λ1⊆Λ2then Λ+ 1⊆Λ+ 2. However, the converse is not true; that is, there exist clutters with Λ16⊆ Λ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 Λ16⊆ Λ2, while Λ+ 1={{1,2},{2,3},{1,2,3}} ⊆ {{1},{1,2},{1,3},{2,3},{1,2,3}} = Λ+ 2. This fact 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. The following lemma will be used several times throughout the paper. Lemma 1. Let Ωbe a finite set. The following statements hold: (1) If Λ1,Λ2are two clutters on Ωthen, Λ1⩽Λ2if and only if for all A1∈Λ1there exists A2∈Λ2such that A2⊆A1. (2) The binary relation ⩽is a partial order on the set of clutters of Ω. Proof The proofs of the statements are a straightforward consequence of the definition of Λ+and of the fact that Λ = min(Λ+).  There are many interesting families of clutters that can be considered. However, because of their applications, we are interested in those clutters that are vectorial. Let Ω = {x1, . . . , xn}be a finite set of nelements. A monotone increasing family Γ of subsets of Ω is said to be a vectorial family if there exists an indexed family of not necessarily distinct vectors v1, . . . , vnof a K-vector space such that {xi1, . . . , xir} ∈ Γ if, and only if, {vi1, . . . , vir}is a linearly dependent multiset of vectors. A clutter Λ on Ω is said to be a vectorial clutter if the monotone increasing family Λ+is a vectorial family. In such a case we say that the vectors v1, . . . , vnprovide a K-representation of Λ. In other words, a monotone increasing family of subsets Γ is vectorial if Γ is the family of the dependent sets of a representable matroid M with ground set Ω; whereas a clutter Λ is vectorial if the clutter Λ is the set of circuits of a representable matroid Mwith ground set Ω (definitions and basic facts about matroids are recalled in Subsection 3.3 as no matroid theory is needed until then). There are clutters on a finite set Ω that are not vectorial (in fact, there are matroids that are not representable matroids). So, a natural question that arises at this point is to determine how to complete a 4 J. MART´ I-FARR´ E AND A. DE MIER clutter Λ to obtain a vectorial clutter. In order to look for vectorial completions, it is important to take into account the binary relation ⩽rather than the inclusion ⊆. This is due to the fact that, as the following example shows, there exist clutters Λ such that Λ 6⊆ Λ0for any vectorial clutter Λ0. Example 2. Let us consider the clutter Λ = {{1,2},{1,3},{2,3,4}} on the finite set Ω = {1,2,3,4}. Observe that {1,2}∪{1,3}\ {1}= {2,3} {2,3,4}. Hence it follows that Λis not a vectorial clutter and, moreover, Λ6⊆ Λ0for any vectorial clutter Λ0. However, we have that Λ⩽Λ0, where Λ0is the vectorial clutter Λ0={{1},{2,3,4}} (a vectorial realization of Λ0is given by the set of vectors {v1, v2, v3, v4} where v1= (0,0),v2= (1,0),v3= (0,1) and v4= (1,1)). Futhermore, if Λ00 is the clutter on Ωdefined by Λ00 ={{1,2},{1,3},{2,3}}, then we have that Λ⩽Λ00 and that the clutter Λ00 is also a vectorial clutter (a vectorial realization of Λ00 is given by the set of vectors {w1, w2, w3, w4} where w1= (1,1),w2= (1,1),w3= (1,1) and w4= (0,1)). Notice that now the clutter Λcan be obtained from the vectorial clutters Λ0 and Λ00. Indeed, it is easy to check that the following equality holds Λ = min A0∪A00 where A0∈Λ0and A00 ∈Λ00. Therefore, the vectorial clutters Λ0and Λ00 in some way provide a decomposition of the non-vectorial clutter Λ. The above example leads us to the following definition. Let Λ be a clutter on a finite set Ω. A vectorial completion of the clutter Λ is a vectorial clutter Λ0on the finite set Ω such that Λ ⩽Λ0. The set of all the vectorial completions of a clutter Λ is denoted by Vect(Λ). Observe that if ∅ ∈ Λ, then Λ = {∅}, and thus Vect(Λ) = ∅. So, from now on we assume that ∅ 6∈ Λ if Λ is a clutter. As shown in the next section, this assumption guarantees that Vect(Λ) 6=∅for all clutters and, in addition, we demonstrate that, in the same way as in Example 2, suitable clutters in the non-empty set of the vectorial completions Vect(Λ) provide a decomposition of the clutter Λ. 3. Three results on vectorial completions and decompositions The aim of this section is to present three theoretical results concerning the “decomposition” of a clutter Λ into vectorial clutters Λ1,...,Λr. The general case is considered in Theorem 4, while Theorem 5 and Theorem 6 deal with those “decompositions” of Λ whose vectorial components Λ1,...,Λradmit vectorial realizations either over a fixed field K or over fields having a specific characteristic. The section concludes by applying these theorems to matroids (Corollary 7). COMPLETION AND DECOMPOSITION OF CLUTTERS 5 3.1. General case. Let Λ be a clutter on a finite set Ω. Our first result, Theorem 4, states that the set Vect (Λ) of its vectorial completions is a non-empty set and that its minimal elements provide a decomposition of Λ (in the sense that the elements Aof the clutter Λ can be obtained from the elements Aiof its minimal vectorial completions Λ1,...,Λr). To prove this we will use the following proposition which is a general result about the decomposition of the clutter Λ into clutters of a specific type. Let us denote by Clutt (Ω) the set whose elements are the clutters on the finite set Ω, and for a non-empty subset X⊆Ω, let ΛXbe the clutter on Ω defined by ΛX={{x}:x∈X}. Proposition 3. Let Λbe a clutter on a finite set Ω. Let Σ⊆Clutt (Ω) be a collection of clutters on Ωand let Σ(Λ) = {Λ0∈Σ : Λ ⩽Λ0}. Assume that ΛX∈Σfor all non-empty subsets Xof Ω. Then, Σ(Λ) 6=∅ and Λ = min A1∪· · ·∪ Ar:Ai∈Λi where Λ1,...,Λrare the minimal elements of the poset Σ(Λ) ,⩽. In particular, Λ∈Σif and only if r= 1. Proof Let n=|Ω|be the size of Ω and let Ω = {x1, . . . , xn}. On one hand, it is clear that Λ ⩽ΛΩ={{x1},...,{xn}}. On the other, from our assumption we get that ΛΩ∈Σ. Therefore, ΛΩ∈Σ(Λ), and so Σ(Λ) 6=∅. Since the set Ω is a finite set, then Σ(Λ) is finite. Without loss of generality, we may assume that Σ(Λ) = {Λ1,...,Λr,...,Λm}, where 1≤r≤mis such that Λ1,...,Λrare the minimal elements of the poset Σ(Λ) ,⩽. Let us denote by Λ0the clutter Λ0= min A1∪· · ·∪Ar: Ai∈Λi. It is necessary to demostrate the equality Λ = Λ0. Observe that by using this equality it is easy to prove that Λ ∈Σ if and only if r= 1. So, from now on we are going to prove the equality Λ = Λ0. In order to do this we use that the binary relation ⩽is a partial order (see Lemma 1). Namely, we are going to prove the equality Λ = Λ0by proving the two inequalities Λ ⩽Λ0and Λ0⩽Λ. Let 1 ≤i≤r. Since Λ ⩽Λi, for A∈Λ, there exist Ai∈Λisuch that Ai⊆A. Therefore, we obtain that A1∪ · · · ∪ Ar⊆A, and hence it follows that Λ ⩽min A1∪ · · · ∪ Ar:Ai∈Λi; that is, Λ ⩽Λ0. Therefore, to finish the proof of the proposition we must demonstrate that Λ0⩽Λ. In order to do this, let us consider the clutter Λ0 0on Ω defined by all the elements of Σ(Λ) = {Λ1,...,Λr,...,Λm}, that is, let Λ0 0be the clutter Λ0 0= min A1∪ · · · ∪ Am:Ai∈Λi. 6 J. MART´ I-FARR´ E AND A. DE MIER We claim that Λ0 0= Λ0. Let us prove our claim. It is clear that if {Λi1,...,Λis}⊆{Λ1,...,Λm}, then Λ0 0⩽min Ai1∪· · ·∪Ais:Aij∈ Λij. In particular, we obtain that Λ0 0⩽Λ0. Next we are going to prove that Λ0⩽Λ0 0. So let A1∪ · · · ∪ Ar∈Λ0. Since Λ1,...,Λrare the minimal elements of the poset Σ(Λ) ,⩽, for j > r there exists αj≤rsuch that Λαj⩽Λj. Therefore, there exists A0 j∈Λjsuch that A0 j⊆Aαj. So we have that A1∪· · ·∪Ar∪A0 r+1∪· · ·∪A0 m⊆A1∪· · ·∪Ar, and hence it follows that there exists C∈Λ0 0such that C⊆A1∪· · ·∪Ar. Therefore, by Lemma 1, Λ0⩽Λ0 0. This completes the proof of our claim. Let us consider the set of subsets {X1, . . . , Xt}={X⊆Ω : Λ ⩽ ΛX}, (observe that this set is non-empty and so t≥1 because Λ ⩽ ΛΩ). By assumption ΛX1,...,ΛXt∈Σ. So {ΛX1,...,ΛXt} ⊆ Σ(Λ) = {Λ1,...,Λm}, and hence it follows that Λ0= Λ0 0⩽min AX1∪ · · · ∪ AXt:AXj∈ΛXj. Now the proof of the proposition is completed by showing the inequality min AX1∪ · · · ∪ AXt:AXj∈ΛXj ⩽Λ; that is, we must demonstrate that if C∈min AX1∪ · · · ∪ AXt:AXj∈ΛXj then there exists A∈Λ such that A⊆C(see Lemma 1). So let C∈min AX1∪ · · · ∪ AXt:AXj∈ΛXj. Then C={xα1, . . . , xαt} where xαj∈Xjfor 1 ≤j≤t. Assume that A6⊆ Cfor all A∈Λ. Therefore, if A∈Λ, then A∩(Ω\C)6=∅, and so there exists x0∈Ω\C such that {x0} ⊆ A. Hence, by applying Lemma 1 it follows that Λ⩽ΛΩ\C. So Ω \C∈ {X⊆Ω : Λ ⩽ΛX}and thus Ω \C=Xi0 for a certain i0∈ {1, . . . , t}. This leads to a contradiction because xαi0∈C∩Xi0. Therefore, there exists A∈Λ such that A⊆C. This completes the proof of the proposition.  Theorem 4. Let Λbe a clutter on a finite set Ω. Then, Vect (Λ) 6=∅ and Λ = min A1∪ · · · ∪ Ar:Ai∈Λi where Λ1,...,Λrare the minimal elements of the poset Vect (Λ) ,⩽of the vectorial completions of Λ. In particular, the clutter Λhas a unique minimal vectorial completion if, and only if, the clutter Λis a vectorial clutter. Proof Observe that Vect (Λ) = Σ(Λ) where Σ ⊆Clutt (Ω) is the collection of the vectorial clutters on Ω. Therefore, from Proposition 3, we only must prove that ΛX∈Σ if ∅ X⊆Ω; that is, we only must demonstrate that the clutter ΛXis a vectorial clutter on the finite set Ω if Xis a non-empty subset of Ω. Let n=|Ω|and let Ω = {x1, . . . , xn}. Let ∅ X⊆Ω. Without loss of generality, we may assume that X={x1, . . . , xr}where 1≤r≤n. Let Kbe a field, and let Ebe a K-vector space having COMPLETION AND DECOMPOSITION OF CLUTTERS 7 dimension dim E≥n−r. Let us consider an indexed family of vectors v1, . . . , vn∈E, where vi= 0 if 1 ≤i≤rand where vr+1, . . . , vnare linearly independent. Then, it is easy to check that the vectors v1, . . . , vn provide a K-representation of ΛX. So, ΛXis a vectorial clutter on Ω.  3.2. Completion and decomposition with field restrictions. Observe that the previous theorem, Theorem 4, deals with vectorial completions and decompositions in the case where no field restrictions are assumed. The next theorems, Theorem 5 and Theorem 6, state that similar results occur if we consider only the case in which the vector spaces of the vectorial completions are either over a fixed field or over fields with a specific characteristic. Before stating these theorems, we introduce some notations. Let Kbe a field and let pbe a prime number. A vectorial clutter is said to be K-vectorial if admits a K-representation, and is said to be pvectorial if it has an L-representation for some field Lof characteristic p. For a clutter Λ, let us denote by Vect K(Λ) the set whose elements are the K-vectorial completions of Λ, and by Vect p(Λ) the set whose elements are the p-vectorial completions of Λ; that is, the elements of Vect K(Λ) are the K-vectorial clutters Λ0with Λ ⩽Λ0, while the elements of Vect p(Λ) are the p-vectorial clutters Λ0with Λ ⩽Λ0. Observe that Vect (Λ) = SKVect K(Λ) and that Vect (Λ) = SpVect p(Λ). The next theorems state that the sets Vect K(Λ) and Vect p(Λ) are non-empty sets and that their minimal elements provide a decomposition of the clutter Λ (in the sense that the elements of Λ can be obtained from these minimal vectorial completions). Theorem 5. Let Λbe a clutter on a finite set Ωand let Kbe a field. Then, Vect K(Λ) 6=∅and Λ = min A1∪ · · · ∪ Ar:Ai∈Λi where Λ1,...,Λrare the minimal elements of the poset Vect K(Λ) ,⩽. In particular, the clutter Λhas a unique minimal vectorial completion over Kif, and only if, the clutter Λis a K-vectorial clutter. Proof Essentially, the proof of this theorem works like the previous one. We must only take into account that, VectK(Λ) = Σ(Λ) where Σ⊆Clutt (Ω) is the collection of the K-vectorial clutters on Ω; and that, for a non-empty subset X⊆Ω, the clutter ΛXis a K-vectorial clutter.  Theorem 6. Let Λbe a clutter on a finite set Ωand let pbe a prime number. Then, Vect p(Λ) 6=∅and Λ = min A1∪· · ·∪Ar:Ai∈Λi where Λ1,...,Λrare the minimal elements of the poset Vect p(Λ) ,⩽. 8 J. MART´ I-FARR´ E AND A. DE MIER In particular, the clutter Λhas a unique minimal p-vectorial completion if, and only if, the clutter Λis a p-vectorial clutter. Proof As before, the proof of this theorem works like the one of Theorem 4. Now we only must bear in mind that, Vectp(Λ) = Σ(Λ) where Σ ⊆Clutt (Ω) is the collection of the p-vectorial clutters on Ω; and that, for a non-empty subset X⊆Ω, the clutter ΛXis a p-vectorial clutter.  3.3. Completion and decomposition of matroids into representable matroids. Matroids are combinatorial objects that can be axiomatized in terms of their independent sets, bases, circuits, rank function, flats, or hyperplanes (the reader is referred to [4, 7] for general references on matroid theory). Here we present the definition in terms of circuits. Amatroid Mis an ordered pair M= (Ω,C) consisting of a finite set Ω, called the ground set of the matroid, and a clutter Cof non-empty subsets of Ω which satisfies the weak circuit elimination property: if C1 and C2are distinct members of Cand x∈C1∩C2, then there is some member C3of 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)+. Sets that are not dependent are called independent. Observe that 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⩽M2if 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 [4, Proposition 7.3.11]); that is, M1⩽M2if M1is above M2in the weak order. A matrix Awith entries in a field Kgives rise to a matroid MAon its set of columns. The dependent sets of the matroid MAare those sets of columns of the matrix Athat are linearly dependent as sets of vectors. This matroid is called the column matroid of A, and the matrix Ais said to represent the matroid. A matroid Mis called representable over a field Kif if there exists some matrix Awith entries in the field Ksuch that M=MA. Therefore, a matroid Mis representable if and only if the clutter C(M) is vectorial. In addition, a matroid Mis COMPLETION AND DECOMPOSITION OF CLUTTERS 9 K-representable (resp. p-representable) if and only if the clutter C(M) is K-representable (resp. p-representable). In any case, for a given matroid M, we can now consider its vectorial completions; that is, those representable matroids M0with M⩽M0. We shall often write Vect (M), Vect K(M) and Vect p(M) instead of Vect (C(M)), Vect K(C(M)) and Vect p(C(M)). The following result states that all these three sets of representable matroidal completions of Mare non-empty, and that their minimal elements provide a decomposition of the matroid M. Corollary 7. Let Mbe a matroid with ground set Ω. Let Kbe a field and let pbe a prime number. Then: (1) Vect (M)6=∅and C(M) = min A1∪· · ·∪Ar:Ai∈ C(Mi) where M1,...,Mrare the minimal elements of Vect (M),⩽ . In particular, the matroid Mhas a unique minimal vectorial completion if, and only if, the matroid Mis representable. (2) Vect K(M)6=∅and C(M) = min A1∪ · · · ∪ Ar:Ai∈ C(Mi)where M1,...,Mrare the minimal elements of Vect K(M),⩽ . In particular, the matroid Mhas a unique minimal K- vectorial completion if, and only if, the matroid Mis K-representable. (3) Vect p(M)6=∅and C(M) = min A1∪ · · · ∪ Ar:Ai∈ C(Mi)where M1,...,Mrare the minimal elements of Vect p(M),⩽ . In particular, the matroid Mhas a unique minimal p-vectorial completion if, and only if, the matroid Mis p-representable. Proof The three statements of the corollary are specializations of the previous theorems.  Remark 8. In this paper we focus on vectorial completions and decompositions, but we could have considered completions and decompositions in some other families of clutters, as long as they include the clutters ΛX. Indeed, a proof analogous to that of Theorem 4 would give the desired completions and decompositions. For matroids, the ones whose clutter of circuits is of the form ΛXare the all whose circuits have size 1 or, in other words, the matroids that can be written as a direct sum of loops and coloops. Most of the familiar classes of matroids contain them, as graphic, cographic, regular, algebraic, transversal and cotransversal matroids. Therefore, similar results can be obtained concerning completions and decomposition of matroids into graphic, cographic, regular, algebraic, transversal and cotransversal matroids. 16 J. MART´ I-FARR´ E AND A. DE MIER M2,0,M2,2,M2,4,M2,6with ground set Ωand sets of circuits:          C(M1,1) = {{1}} ∪ {C∈ C(F− 7) : C⊆Ω\ {1}}, C(M1,3) = {{3}} ∪ {C∈ C(F− 7) : C⊆Ω\ {3}}, C(M1,5) = {{5}} ∪ {C∈ C(F− 7) : C⊆Ω\ {5}}, C(M1,7) = {{7}} ∪ {C∈ C(F− 7) : C⊆Ω\ {7}},                        C(M2,0) = {{1,3},{1,5},{1,7},{3,5},{3,7},{5,7}} ∪ ∪ {{1,2,4,6},{2,3,4,6},{2,4,5,6},{2,4,6,7}}, C(M2,2) = {{1,3},{5,7}} ∪ ∪ {A⊆Ω\ {2}such that |A|= 3 and {1,3},{5,7} 6⊆ A}, C(M2,4) = {{1,7},{3,5}} ∪ ∪ {A⊆Ω\ {4}such that |A|= 3 and {1,7},{3,5} 6⊆ A}, C(M2,6) = {{1,5},{3,7}} ∪ ∪ {A⊆Ω\ {6}such that |A|= 3 and {1,5},{3,7} 6⊆ A}. 1 4 7 6 3 2 5 1 3 2 4 6 5 7 M2,0 1 2 46 3 7 5 M2,2 M1,1 Figure 2. Geometric representations of the matroids M1,1,M2,0and M2,2. Here two elements lying on the same point form a 2-element circuit and an element inside a box is a 1-element circuit. Proof Let Σ = {F7,M1,1,M1,3,M1,5,M1,7,M2,0,M2,2,M2,4,M2,6} and take M ∈ Σ. On one hand, by using Lemma 1 it is not hard to check that F− 7⩽M. On the other, from [4, Proposition 6.4.8] and from the excluded minor characterizations [4, Proposition 6.5.4 and Proposition 6.5.6] we get that there exists a field Kof characteristic two such that Mis K-representable. So we conclude that if M ∈ Σ then F− 7⩽Mand Mis 2-representable, that is, Mis a 2-vectorial completion of the non-Fano matroid. From the above we have that Σ ⊆Vect2(F− 7). In addition, by using Lemma 1 it is a straightforward proof to check that M 6⩽M0if M,M0∈Σ are different. Hence we have that Σ ⊆Vect2(F− 7) and that two different matroids of Σ are not comparable. Therefore the COMPLETION AND DECOMPOSITION OF CLUTTERS 17 proof of the proposition will be completed by showing that if Nis a 2-vectorial completion of F− 7, then there exists a matroid M ∈ Σ such that M⩽N. So from now on, let Nbe a 2-representable matroid with ground set Ω and such that F− 7⩽N. We must demonstrate that M⩽Nfor some M ∈ Σ. In order to do this, we distinguish three cases according to the circuits of N. We systematically use Lemma 1 to compare matroids under the relation ⩽. Case 1: {2,4,6}∈C(N)+. We claim that, in such a case, F7⩽N. Indeed, if {2,4,6}is a dependent set of N, then there exists a circuit C0∈ C(N) such that C0⊆ {2,4,6}, and hence we get that F7⩽Nbecause C(F7)\ {{2,4,6}} ⊆ C(F− 7) and F− 7⩽N. So, if {2,4,6}∈C(N)+, then F7⩽N. Case 2: {2,4,6} 6∈ C(N)+and Nhas a 1-element circuit. In such a case we are going to prove that there exists i∈ {1,3,5,7} such that M1,i ⩽N. Let C0be a 1-element circuit of N. Since {2,4,6} 6∈ C(N)+, there exists i∈ {1,3,5,7}such that C0={i} ∈ C(N). Then for all C∈ C(M1,i), either C={i}, or there exists C0∈ C(N) such that C0⊆C, (because if i6∈ C∈ C(M1,i) then C∈ C(F− 7) and F− 7⩽N). Therefore, M1,i ⩽N, as we wanted to prove. Case 3: {2,4,6} 6∈ C(N)+and |C| ≥ 2for all C∈ C(N). This is the last case that we must consider. Now, the proof of the proposition will be completed by showing that, in this case, there exists j∈ {0,2,4,6}such that M2,j ⩽N. In order to prove this we will use some basic matroid theory facts that are recalled in the following. For a subset S⊆Ω, let the closure of Sin Nbe cl(S) = S∪ {x∈Ω : there is C∈ C(N) such that x∈C⊆S∪ {x}}. Then, the following statements hold: (a) If {a, b}and {a, c}are circuits of N, then {b, c}is also a circuit of N. (b) If {a, b}is a circuit of Nthen cl({a, c}) = cl({b, c}) for all c∈Ω. (c) If y∈cl(S), then cl(S∪ {y}) = cl(S). (d) If T⊆cl(S) and T∪ {x} ∈ C(N), then x∈cl(S). (e) Every subset of cl(S) with more than |S|elements is dependent. 18 J. MART´ I-FARR´ E AND A. DE MIER The first statement is an immediate application of the weak circuit elimination property. To prove the other four statements, let us interpret the closure operator when Nis the column matroid of the matrix A(which in fact is the only case that we need here). Recall that, in such a case, circuits correspond to minimal sets of linearly dependent columns, and thus the closure of a set Sconsists of the columns of Athat are in the linear span of the columns corresponding to S. Therefore, the properties (b)–(e) are clear from properties of linear dependence. This completes the proof of the five statements. Hereafter, we finalize the proof of the proposition. We are assuming that Nis a 2-vectorial completion of F− 7such that {2,4,6}is not a dependent set of Nand that no singleton is a circuit of N(that is, Nis loopless). In such a case we are going to prove that M2,j ⩽Nfor some j∈ {0,2,4,6}. We proceed by three steps. Step 1. There exists a circuit C∈ C(N) with |C|= 2. Proof. Let us assume that Nhas no circuit of size 2. We have then that every 3-element circuit of F− 7is also a circuit of Nbecause F− 7⩽N. At this point observe that if X⊆Ω is a subset with |X| ≥ 3, then either X⊆C0or C0⊆Xfor some C0∈ C(F− 7). Therefore, if C(F− 7)⊆ C(N) then C(F− 7) = C(N) and thus F− 7=Nwhich leads us to a contradiction because the matroid Nis 2-representable. Hence it follows that C(F− 7)6⊆ C(N) and so, since F− 7⩽N, some 4-element circuit of F− 7must properly contain a 3-element circuit C0of N. Up to symmetry, there are three possibilities for this circuit C0of N:{1,2,4}, {1,3,4}and {1,3,5}. In order to obtain a contradiction, we analyze each one of the different situations that may occur. First assume that C0={1,2,4} ∈ C(N). Consider L= cl({1,2}), which by property (c) equals cl({1,4}) (all closures are taken in N). Now the circuit {1,2,3}forces 3 to be in L(recall that every 3-element circuit of F− 7is also a circuit of N); similarly, the circuit {1,4,7} forces 7 to belong to L. But now the circuit {3,6,7}gives that 6 is in L. Thus {2,4,6} ⊆ L= cl({1,2}) and hence {2,4,6}is dependent by property (e), which is impossible as we are assuming that {2,4,6}is independent. Next assume that C0={1,3,4}∈C(N). In such a case we have that {1,2,3},{1,3,4} ∈ C(N) and so, from the weak circuit elimination property, it follows that {1,2,4} ∈ C(N). At this point, a contradiction is obtained by applying the previous case. Now assume that C0={1,3,5}. So we have {1,2,3},{1,3,5} ∈ C(N). Hence, from the weak circuit elimination property we get that COMPLETION AND DECOMPOSITION OF CLUTTERS 19 {1,2,5} ∈ C(N). Thereby {1,2,6} ∈ C(N) because {1,5,6} ∈ C(N). In this case a contradiction is obtained by applying the first case to C0 0={1,2,6}. This completes the proof of the first step. Step 2. There exists a circuit C∈ C(N) with |C|= 2 and C⊆ {1,3,5,7}. Proof. Assume that no two elements of {1,3,5,7}form a circuit of N. On one hand, {2,4,6}is not a dependent set of N. On the other, from the previous step Nhas some 2-element circuit. Therefore, by symmetry, we may assume that {1,2} ∈ C(N). We have that {1,4} is independent, as otherwise property (a) would imply that {2,4}is a circuit; similarly, we get that {2,7}is also independent. Consider L0= cl({1,4}); as {1,2}∈C(N), the element 2 belongs to L0. The circuit {1,4,7}of F− 7forces 7 to be in L0because F− 7⩽N. Since {2,5,7}∈C(F− 7) and F− 7⩽N, but {2,7} 6∈ C(N), there exists C∈ C(N) such that 5 ∈C⊆ {2,5,7}, and hence property (d) gives that 5∈L0because 2,7∈L0. Similarly, as {1,5,6}∈C(F− 7) and we are assuming that {1,5} 6∈ C(N), we deduce that 6 belongs to L0. But now {2,4,6} ⊆ L0= cl({1,4}) and thus it is dependent by property (e), which is not possible. Step 3. There exists j∈ {0,2,4,6}such that M2,j ⩽N. Proof. Recall that we are assuming that {2,4,6} 6∈ C(N)+and that Nis loopless. From the previous step, {1,3,5,7}contains a 2- element circuit. By symmetry, assume {1,3} ∈ C(N). If both {1,5} and {1,7}are also circuits, then by property (a) every 2-element subset of {1,3,5,7}is a circuit of Nand one easily checks M2,0⩽Nbecause F− 7⩽N. So let us assume that {1,3}∈C(N) but {1,5} 6∈ C(N), and thus by property (a) we get that {3,5} 6∈ C(N). Now consider L00 = cl({1,5}), that equals cl({3,5}) by property (b). As {1,5,6}and {3,4,5}are dependent in N, the elements 6 and 4 belong to L00. Observe that 26∈ L00 because if so the set {2,4,6}would be dependent in Nby property (e). Now observe that it cannot be that both {1,4}and {3,6}are circuits of N, since it that were the case, applying property (a) twice we would get that {4,6}∈C(N), contrary to {2,4,6}being independent in N. Assume by symmetry that {1,4} 6∈ C(N). Then, as {1,4,7} ∈ C(N)+, there is a circuit Cof Nsuch that 7 ∈C⊆ {1,4,7}. Therefore, since 1,4∈L00, the element 7 also belongs to L00 by property (d). Thus, 20 J. MART´ I-FARR´ E AND A. DE MIER L00 contains all elements except 2. Now consider the set {2,5,7} ∈ C(N)+; because 2 6∈ L00, it is forced that {5,7} ∈ C(N). So we have that {1,3}and {5,7}are circuits of Nand that L00 = cl({1,5})=Ω\ {2}. Hence we conclude that M2,2⩽N, as we wanted to prove. This step completes the proof of the third case, and so the proof of the proposition.  Remark 15. Since Vect2(F− 7),⩽has nine minimal elements, from Corollary 7 we conclude that the non-Fano matroid F− 7admits a 2- vectorial decomposition with nine components. However, as in the case of U2,4, it is possible to obtain a decompositon of F− 7by using only some of the minimal completions obtained in Proposition 14. Namely, if N1 and N2are two such minimal completions, then C(F− 7) = min C1∪C2:Ci∈ C(Ni) if and only if either N1or N2is the Fano matroid F7. Acknowledgments The first author was supported by the Ministerio de Educaci´on y Ciencia (Spain) and the European Regional Development Fund under project MTM2011-28800-C02-01. The second author was supported by the Ministerio de Educaci´on y Ciencia (Spain) under project MTM2011-24097. References [1] J. Herzog and T.Hibi. Monomial Ideals. Grad. Texts in Math. 260, Springer, London, 2010. [2] J. Mart´ı-Farr´e. From clutters to matroids. Electronic Journal of Combinatorics, 21(1)-P1.11 (14 pag.), 2014. [3] J. Mart´ı-Farr´e and C. Padr´o. On secret-sharing schemes, matroids and polymatroids. Journal of Mathematical Cryptology, 4:95–120, 2010. [4] J.G. Oxley. Matroid Theory. Oxford Graduate Text in Mathematics. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1992. [5] P.D. Seymour. On secret-sharing matroids. J. Combin. Theory Ser. B, 56:69– 73, 1992. [6] R.P. Stanley. Combinatorics and Commutative Algebra. Progress in Mathematics 41. Second Edition. Birkh¨auser, 1995. [7] D.J.A. Welsh. Matroid Theory. Academic Press, London, 1976. [8] R. Woodroofe. Chordal and sequentially Cohen-Macaulay clutters. Electronic Journal of Combinatorics, 18(1)-P1.208 (20 pag.), 2011. COMPLETION AND DECOMPOSITION OF CLUTTERS 21 (J. Mart´ı-Farr´e) Departament de Matem` atica Aplicada IV, Universitat Polit` ecnica de Catalunya, Barcelona, Spain E-mail address:[email protected] (A. de Mier) Departament de Matem` atica Aplicada II, Universitat Polit` ecnica de Catalunya, Barcelona, Spain E-mail address:[email protected]