E-Book Content
AN INTRODUCTION TO TRANSVERSAL MATROIDS JOSEPH E. BONIN
October 27, 2010
C ONTENTS 1. Prefatory Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Several Perspectives on Transversal Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1. Set systems, transversals, partial transversals, and Hall’s theorem . . . . . . . . 2.2. Transversal matroids via matrix encodings of set systems . . . . . . . . . . . . . . . . 2.3. Properties of transversal matroids that follow easily from the matrix view . 2.4. Background for the geometric perspective: cyclic flats . . . . . . . . . . . . . . . . . . 2.5. The geometric perspective on transversal matroids . . . . . . . . . . . . . . . . . . . . . . 3. Characterizations of Transversal Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1. Fundamental transversal matroids and the Mason-Ingleton theorem . . . . . . . 3.2. Sets in presentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Multiplicities of complements of cyclic flats in presentations . . . . . . . . . . . . 3.4. Completion of the proof of the Mason-Ingleton theorem . . . . . . . . . . . . . . . . . 3.5. Several further results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4. Lattice Path Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1. Sets of lattice paths and related set systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2. Lattice path matroids; interpreting paths as bases . . . . . . . . . . . . . . . . . . . . . . . 4.3. Duality, direct sums, connectivity, spanning circuits, and minors . . . . . . . . . 5. Tutte Polynomials of Lattice Path Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1. A brief introduction to Tutte polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. Tutte polynomials as generating functions for basis activities . . . . . . . . . . . . 5.3. Basis activities in lattice path matroids; computing Tutte polynomials . . . . 6. Further comments and open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7. Supplement: Hall’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 2 2 3 5 6 7 9 9 11 12 14 15 16 16 17 18 21 21 22 23 25 26 26
1. P REFATORY R EMARKS When first introduced in the mid 1960’s, transversal matroids unified many results in transversal theory, simplified their proofs, and provided a larger context for such results, thereby firmly establishing the importance of this class of matroids. Such links with other specialties fueled much interest in matroid theory within the wider research community. This expository paper develops several ways to view transversal matroids, a selection of basic results about them, and several characterizations of these matroids, as well as some results about lattice path matroids, which form a class of transversal matroids with many 1
2
[n]
An Introduction to Transversal Matroids
J. Bonin
very attractive properties. Thus, readers will gain a substantial but selective introduction to the theory of transversal matroids, including some recent developments, as well as some exposure to several related topics from other parts of matroid theory. We assume that readers have already been exposed to the basic concepts of matroid theory (e.g., minors, duals, direct sums, and matrix representations over fields). All sets considered are finite. We use [n] to denote the set {1, 2, . . . , n}. 2.