# A Characterization of Uniform Matroids

Authors: Brahim Chaourar
Journal: ISRN Algebra
 (2011)

---

## Abstract

This paper gives a characterization of uniform matroids by means of locked subsets. Locked subsets are 2-connected subsets, their complements are 2-connected in the dual, and the minimum rank of both is 2. Locked subsets give the nontrivial facets of the bases polytope.


---

## Body

## 1. Introduction

Sets and their characteristic vectors will not be distinguished. We refer to Oxley [1] for the terminology about matroids and to Schrijver [2] for the terminology about polyhedra.LetE be a finite set, and let M be a matroid defined on E. If M is 2-connected, then we will say that a proper subset L of E; that is, Ø≠L≠E, is locked if L is nonseparable or 2-connected in M,E∖L is nonseparable or 2-connected in M* and r(L)≥max{2,2+r(E)-∣E∖L|} or min{r(L),r*(E∖L)}≥2. Observe that L is locked in a matroid M if and only if M∣L and M/L are both connected and min{r(L),r*(E∖L)}≥2. Locked subsets give the nontrivial facets of the bases polytope. We will denote the class of these subsets by Λ(M) or Λ. If M is not 2-connected, then M=M1⊕M2⊕⋯⊕Mk where each Mj is 2-connected, j=1,2,…,k, and the class of locked subsets Λ(M) is the union of such classes in each 2-connected component involved in the direct sums. Locked subsets were introduced by Chaourar ([3–5]) to describe some facets of the cone and the polytope generated by the matroid bases. We will denote the 2-sum of two matroids M and N using the basepoint {e} by M⊕eN or M⊕2N if there is no confusion. Since 2-sums with U1,2 and U1,1 are, respectively, identity and deletion, then we will consider only proper 2-sums without U1,2 nor U1,1.LetM be the class of matroids obtained by means of 1-sums (or direct sums) and (proper) 2-sums of uniform matroids together with all minors of such matroids. Since (M⊕N)*=M*⊕N* and (M⊕2N)*=M*⊕2N* (see [1]), then M is closed under the taking of duals. It is also clear that M is closed under the taking of minors.IfM is not a 3-connected matroid, then, using a theorem of Oxley (see [1]), M can be constructed from 3-connected minors of it by a sequence of the operations of 1-sum and 2-sum.The purpose of this paper is to characterize uniform matroids by means of locked subsets. There are exactly five 3-connected matroids of rank 3 on a 6-element set. These matroids can be obtained fromM(K4) by relaxing zero, one, two, three, or four circuit-hyperplanes. The matroids are, respectively, M(K4), the rank-3 whirl W3,Q6,P6, and the uniform matroid U3,6 (see [1]).The remaining of the paper is organized as follows: in Section2, we will give a characterization of uniform matroids by means of locked subsets, two consequences are given in Section 3, and the conclusion is given is Section 4.


## 2. The Characterization

We will need to three lemmas in this section.Lemma 2.1.
|Λ(M*)|=|Λ(M)|.Proof.
Direct from the definition of a locked subset.Lemma 2.2.
LetN be a 3-connected minor of a 2-connected matroid M. If Λ(N)≠Ø, then Λ(M)≠Ø.Proof.
Using duality and Lemma2.1, it suffices to prove that, if Λ(M∖e)≠Ø, then Λ(M)≠Ø.
Suppose thatL is locked in M∖e. We establish that L∪{e}, when e∈closure(L), or L, when e∉closure(L), is locked in M. If L spans e in M, then M∣(L∪{e}) is connected because e is not a loop of M. As
(2.1)M/(L∪{e})=(M/L)/e=(M/L)∖e=(M∖e)/L
is connected, it follows that L∪{e} is locked in M. If L does not span e in M, then e is not a loop of M/L. Therefore, M/L is connected because (M/L)∖e=(M∖e)/L is connected (remember that L is locked in M∖e). Thus, L is locked in M.The following last lemma of this section was proved by Walton [6] and we give here a new proof based on locked subsets.Lemma 2.3.
LetM be a 3-connected matroid having no isomorphic minor to any of M(K4),W3,Q6, and P6. Then M is uniform.Proof.
Suppose by contradiction thatM is not uniform. It follows that there exists a subset F of M such that |F|=r(M) and F contains a circuit C. Without loss of generality, we can suppose that |C|=3 because, if it is not, we can contract some elements of C keeping C as a circuit and decreasing its cardinality. Now we delete all elements of F-C. Let N be the obtained matroid.
Case 1.
IfrN(E-C)=r(N), then let B be a base of N included into E-C. If |B|>3, then contract some elements of B keeping B as a base and C as a circuit with |B|=|C|=3. C is a locked subset of the matroid N∣(B∪C) because C is 2-connected, B is a cocircuit, and r(C)=r*(B)=2. Thus, N∣(B∪C) is one of the excluded minors, a contradiction.Case 2.
IfrN(E-C)<r(N), then N is a series extension of a uniform matroid. By induction on |E(M)|, the matroid U, obtained by contracting one element in the series closure S, is uniform. But S intersect C so there are two parallel elements e and f in U. Since r({e,f})=1, then r(U)=1, a contradiction.Here we give our main result.Theorem 2.4.
IfM is a 3-connected matroid, then the following assertions are equivalent:(i)
M is a uniform matroid,(ii)
Λ(M)=Ø.Proof.
(i)⇒(ii) Using the fact that there is a unique closed and 2-connected subset which is E.
(ii)⇒(i) Using Lemma 2.2, any minor N of M verifies Λ(N)=Ø. So M has no isomorphic minor to any of M(K4),W3,Q6, and P6, because any of these excluded minors has at least one locked subset (circuit of rank 3). By Lemma 2.3, M is uniform.Note that (i) implies (ii), in Theorem2.4, even if M is not 3-connected.


## 3. Some Consequences

We will give two corollaries of our characterization.The first one is a characterization by excluded minors and is almost a restatement of Lemma2.3, and Walton should be credited for this result:Corollary 3.1.
The following assertions are equivalent for a matroidM:(i)
M is a minor of 1-sums and 2-sums of uniform matroids,(ii)
M has no isomorphic to any of M(K4),W3,Q6 and P6.Proof.
(i)⇒(ii) By contradiction, suppose that M has one isomorphic to any of the excluded minors. Since all the excluded minors are 3-connected, then at least one of the 3-connected components used to construct M by means of 1-sums and 2-sums has one such excluded minor. Let N be this excluded minor. Since the number of locked subsets for any excluded minor is at least 1, then, using Lemmas 2.2 and 2.3 and Theorem 2.4, Λ(N)≠Ø and N is not uniform.
(ii)⇒(i) If M is 3-connected, then, by Lemma 2.3, M is uniform. If M is not 3-connected, then M can be construct using 3-connected matroids by means of 1-sum and 2-sum. It follows that no one of these matroids has an isomorphic to any of the excluded minors and, by Lemma 2.3, all these matroids are uniform.We will need the following result of Chaourar [5] to deduce the second corollary.Theorem 3.2.
IfM is a 2-connected matroid, then its bases’ polytope is given by the following constraints:
(3.1)x(E)=r(E),(3.2)x(S)≥|S|-1for any series closureSofM,(3.3)x(P)≤1for any parallel closurePofM,(3.4)x(H)≤r(H)for any locked subsetHofM.Corollary 3.3.
IfM is a 2-connected and uniform matroid, then its bases’ polytope is given by constraints (3.1)–(3.3).Proof.
Direct from Theorems2.4 and 3.2.


## 4. Conclusion

We have given a characterization of uniform matroids by means of locked subsets and two consequences of this characterization.



---

*Source: 208478-2011-12-01.xml*