tailieunhanh - Báo cáo khoa học:Transversal and cotransversal matroids via their representations

This note gives a new proof of the theorem, due to Ingleton and Pi [3], that the duals of transversal matroids are precisely the strict gammoids. Section 1 denes the relevant objects. Section 2 presents explicit representations of the families of transversal matroids and strict gammoids. Section 3 uses these representations to prove the duality of these two families. | Transversal and cotransversal matroids via their representations. Federico Ardila Submitted May 23 2006 Accepted Feb 27 2007 Published Mar 5 2007 Mathematics Subject Classification 05B35 05C38 05A99 Abstract. It is known that the duals of transversal matroids are precisely the strict gammoids. We show that by representing these two families of matroids geometrically one obtains a simple proof of their duality. 0 This note gives a new proof of the theorem due to Ingleton and Piff 3 that the duals of transversal matroids are precisely the strict gammoids. Section 1 defines the relevant objects. Section 2 presents explicit representations of the families of transversal matroids and strict gammoids. Section 3 uses these representations to prove the duality of these two families. 1 Matroids and duality. A matroid M E B is a finite set E together with a non-empty collection B of subsets of E called the bases of M which satisfy the following axiom If B1 B2 are bases and e is in B1 B2 there exists f in B2 B1 such that B1 e u f is a basis. If M E B is a matroid then B fE B I B 2 Bg is also the collection of bases of a matroid M E B called the dual of M. Representable matroids. Matroids can be thought of as providing a combinatorial abstraction of linear independence. If V is a set of vectors in a vector space and B is the federico@. Dept. of Mathematics San Francisco State University San Francisco CA USA. Supported by NSF grant DMS-9983797. THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 N6 1 collection of maximal linearly independent subsets of V then M V B is a matroid. Such a matroid is called representable and V is called a representation of M. Transversal matroids. Let A1 . Ar be subsets of n 1 . ng. A transversal or system of distinct representatives of A1 . Ar is an r-subset of n whose elements can be labelled e1 . er in such a way that ei is in Ai for each i. The transversals of A1 . Ar are the bases of a matroid on n . Such a matroid is called a .