ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS THEORY OF MATROIDS Edited by NEIL WHITE ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS Volume 26 Theory of Matroids ENCYCLOPEDIA OF MATHEMATICS and Its Applications GIAN-CARLO ROTA, Editor Massachusetts Institute of Technology Editorial Board Janos D. Aczel, Waterloo Donald E. Knuth, Stanford George E. Andrews, Penn State Joshua Lederberg, Rockefeller Richard Askey, Madison Andrb Lichnerowicz, College de France Michael F. Atiyah, Oxford M. J. Lighthill, London Donald Babbitt, U.C.L.A. Chia-Chiao Lin, M.I.T. Lipman Bers, Columbia Jacques-Louis Lions, Paris Garrett Birkhoff, Harvard G. G. Lorentz, Austin Raoul Bott, Harvard Roger Lyndon, Ann Arbor James K. Brooks, Gainesville Robert J. McEliece, Caltech Felix E. Browder, Chicago Henry McKean, Courant A. P. Calderon, Buenos Aires Marvin Marcus, Santa Barbara Peter A. Carruthers, Los Alamos N. Metropolis, Los Alamos S. Chandrasekhar, Chicago Frederick Mosteller, Harvard S. S. Chem, Berkeley Jan Mycielski, Boulder Hermann Chernoff, M.I.T. L. Nachbin, Rio de Janeiro and Rochester P. M. Cohn, Bedford College, London Steven A. Orszag, M.I.T. H. S. MacDonald Coxeter, Toronto Alexander Ostrowski, Basel George B. Dantzig, Stanford Roger Penrose, Oxford Nelson Dunford, Sarasota, Florida Carlo Pucci, Florence F. J. Dyson, Inst. for Advanced Study Fred S. Roberts, Rutgers Harold M. Edwards, Courant Abdus Salam, Trieste Harvey Friedman, Ohio State M. P. Schutzenberger, Paris Giovanni Gallavotti, Rome Jacob T. Schwartz, Courant Andrew M. Gleason, Harvard Irving Segal, M.I.T. James Glimm, Courant Oved Shisha, Univ. of Rhode Island M. Gordon, Essex I. M. Singer, Berkeley Elias P. Gyftopoulos, M.I.T. Olga Taussky, Caltech Peter Henrici, ETH, Zurich Ren6 Thom, Bures-sur-Yvette Nathan Jacobson, Yale John Todd, Caltech Mark Kac, U.S.C. John W. Tukey, Princeton Shizuo Kakutani, Yale Veeravalli S. Varadarajan, U.C.L.A. Samuel Karlin, Stanford Antoni Zygmund, Chicago J. F. C. Kingman, Oxford For other books in this series see page 317 THEORY OF MATROIDS Edited by Neil White University of Florida 1 The eight of the Unite sUy of Camheldge to pint and sell all mnenee of hooky was geamed by Henry V111 in 1534. 1 The Unteerstty has printed and pahlited rondnaoatly j since 1384. CAMBRIDGE UNIVERSITY PRESS Cambridge London New York New Rochelle Melbourne Sydney CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, Sao Paulo, Delhi Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK Published in the United States of America by Cambridge University Press, New York www.cambridge.org Information on this title: www.cambridge.org/9780521309370 © Cambridge University Press 1986 This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 1986 This digitally printed version 2008 A catalogue record for this publication is available from the British Library Library of Congress Cataloguing in Publication data Main entry under title: Theory of matroids. (Encyclopedia of mathematics and its applications; v. 26) Bibliography: p. 1. Matroids. I. White, Neil. II. Series. QA166.6.T44 1986 511'.6 85-6682 ISBN 978-0-521-30937-0 hardback ISBN 978-0-521-09202-9 paperback Contents List of Contributors page ix Series Editor's Statement xi Foreword by Gian-Carlo Rota xiii Preface xv Chapter 1 Examples and Basic Concepts 1 Henry Crapo 1.1 Examples from Linear Algebra and Projective Geometry 1 1.2 Further Algebraic Examples 12 1.3 Combinatorial Examples 16 1.4 Structure and Related Geometries 25 Exercises 27 Chapter 2 Axiom Systems 29 Giorgio Nicoletti and Neil White 2.1 Basis Axioms 30 2.2 Other Families of Subsets 32 2.3 Closure and Rank 38 2.4 Combinatorial Geometries and Infinite Matroids 42 V Contents Exercises 43 References 44 Chapter 3 Lattices 45 Ulrich Faigle 3.1 Posets and Lattices 46 3.2 Modularity 49 3.3 Semimodular Lattices of Finite Length 51 3.4 Geometric Lattices 53 3.5 Decomposition of Geometric Lattices 56 3.6 Projective Geometry and Modular Geometric Lattices 58 Exercises 60 References 61 Chapter 4 Basis-Exchange Properties 62 Joseph P. S. Kung 4.1 Bracket Identities and Basis-Exchange Properties 62 4.2 The Exchange Graph 64 4.3 Multiple and Alternating Exchanges 66 Historical Notes 69 Exercises 69 References 73 Chapter 5 Orthogonality 76 Henry Crapo 5.1 Introduction 76 5.2 Orthogonal Geometries 77 5.3 Vector Geometries and Function-Space Geometries 81 5.4 Orthogonality of Vector Geometries 85 5.5 Orthogonality of Simplicial Geometries 87 5.6 Orthogonality of Planar Graphic Geometries 90 5.7 Research Problem: Orthogonality between Other Pairs of Simplicial Geometries 91 5.8 The Orthogonal of a Structure Geometry 94 References 96 Chapter 6 Graphs and Series-Parallel Networks 97 James Oxley 6.1 Polygon Matroids, Bond Matroids, and Planar Graphs 98 6.2 Connectivity for Graphs and Matroids 107 6.3 Whitney's 2-Isomorphism Theorem 110 6.4 Series-Parallel Networks 116 Contents Vii Exercises 120 References 125 Chapter 7 Constructions 127 Thomas Brylawski 7.1 Introduction 127 7.2 Isthmuses and Loops 128 7.3 Deletions, Submatroids, and Extensions 130 7.4 Contractions, Minors, and Lifts 138 7.5 Truncations, Lifts, and Matroid Bracing 162 7.6 Direct Sum and Its Generalizations 173 7.7 Lower Truncations 193 7.8 Index of Constructions 201 Exercises 209 References 222 Chapter 8 Strong Maps 224 Joseph P. S. Kung 8.1 Minors and Strong Maps 224 8.2 The Factorization Theorem 230 8.3 Elementary Quotient Maps 237 8.4 Further Topics 240 Historical Notes 242 Exercises 243 References 252 Chapter 9 Weak Maps 254 Joseph P. S. Kung and Hien Q. Nguyen 9.1 The Weak Order 254 9.2 Weak Cuts 256 9.3 Rank-preserving Weak Maps 260 9.4 Simple Weak Maps of Binary Matroids 262 Historical Notes 267 Exercises 268 References 270 Chapter 10 Semimodular Functions 272 Hien Q. Nguyen 10.1 General Properties of Semimodular Functions 273 10.2 Expansions and Dilworth's Embedding 275 10.3 Reductions 282 10.4 Applications of Expansions and Reductions 289 Historical Notes 296 References 297 viii Contents Appendix of Matroid Cryptomorphisms 298 Thomas Brylawski Axiomatizations for the Matroid M(E) 300 Cryptomorphisms 304 Prototypical Examples 305 Special Cryptomorphisms Characterizing Binary Matroids 310 Index 313 Contributors Thomas Brylawski Department of Mathematics University of North Carolina Chapel Hill, NC 27514 Henry Crapo Institut National de Recherche en Informatique et en Automatique, B. P. 105 78153 le Chesnay Cedex, France Ulrich Faigle Institut fur Okonometrie and Operations Research, Universitat Bonn Nassestrasse 2, D-5300 Bonn 1 Federal Republic of Germany Joseph P. S. Kung Department of Mathematics North Texas State University Denton, TX 76203 Hien Q. Nguyen Department of Mathematics University of Montana Missoula, MT 59812 Giorgio Nicoletti Istituto di Geometria Universita Bologna Piazza di Porta S. Donato Bologna, Italy ix