tailieunhanh - Báo cáo toán học: "Characterizations of Transversal and Fundamental Transversal Matroids"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Characterizations of Transversal and Fundamental Transversal Matroids. | Characterizations of Transversal and Fundamental Transversal Matroids Joseph E. Bonin Department of Mathematics The George Washington University Washington . 20052 USA j bonin@ Joseph P S. Kung Department of Mathematics University of North Texas Denton TX 76203 USA kung@ Anna de Mier Departament de Matematica Aplicada II Universitat Politecnica de Catalunya Jordi Girona 1-3 08034 Barcelona Spain Submitted Sep 17 2010 Accepted Apr 29 2011 Published May 8 2011 Mathematics Subject Classification 05B35 Abstract A result of Mason as refined by Ingleton characterizes transversal matroids as the matroids that satisfy a set of inequalities that relate the ranks of intersections and unions of nonempty sets of cyclic flats. We prove counterparts for fundamental transversal matroids of this and other characterizations of transversal matroids. In particular we show that fundamental transversal matroids are precisely the matroids that yield equality in Mason s inequalities and we deduce a characterization of fundamental transversal matroids due to Brylawski from this simpler characterization. 1 Introduction Transversal matroids can be thought of in several ways. By definition a matroid is transversal if its independent sets are the partial transversals of some set system. A result of Brylawski gives a geometric perspective a matroid is transversal if and only if it has an affine representation on a simplex in which each union of circuits spans a face of the simplex. Partially supported by Projects MTM2008-03020 and Gen. Cat. DGR 2009SGR1040. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P106 1 Unions of circuits in a matroid are called cyclic sets. Thus a set X in a matroid M is cyclic if and only if the restriction M X has no coloops. Let Z M be the set of all cyclic flats of M. Under inclusion Z M is a lattice for X Y G Z M their join in Z M is their join cl X u Y in the lattice of flats their meet in Z M is the union of the circuits in