Independence Theory in Combinatorics

Independence Theory in Combinatorics: An Introductory Account with Applications to Graphs and Transversals is an undergraduate-level mathematics textbook on the theory of matroids. It was written by Victor Bryant and Hazel Perfect, and published in 1980 by Chapman & Hall.

A major theme of Independence Theory in Combinatorics is the unifying nature of abstraction, and in particular the way that matroid theory can unify the concept of independence coming from different areas of mathematics.^[1] It has five chapters, the first of which provides basic definitions in graph theory, combinatorics, and linear algebra, and the second of which defines and introduces matroids, called in this book "independence spaces".^[2] As the name would suggest, these are defined primarily through their independent sets, but equivalences with definitions using circuits, matroid rank, and submodular set function are also presented, as are sums, minors, truncations, and duals of matroids.^[3]

Chapter three concerns graphic matroids, the matroids of spanning trees in graphs,^[2] and the greedy algorithm for minimum spanning trees.^[3] Chapter four includes material on transversal matroids, which can be described in terms of matchings of bipartite graphs, and includes additional material on matching theory and related topics including Hall's marriage theorem, Menger's theorem (an equivalence between minimum cuts and maximum sets disjoint paths in graphs), Latin squares, and gammoids.^[2][3] The final chapter concerns matroid representations using linear independence in vector spaces,^[2] labeled as an appendix and presented with fewer proofs.^[1][3][4]

Many exercises are included, of varied difficulty, with hints and solutions.^[1][2][3]

The level of the text is appropriate for courses for advanced undergraduates or master's students,^[1] with only basic linear algebra as a prerequisite,^[2][4][5] and covers its material at a more accessible and general level than other texts on matroid theory.^[3][4][6] Although disagreeing with the book's choice to omit the related topic of geometric lattices, reviewer Dominic Welsh calls it "an ideal text for an undergraduate course on combinatorial theory".^[2] Michael J. Ganley similarly calls it "a very good introduction to quite a difficult subject".^[4]

However, reviewer W. Dörfler complains that the book has inadequate coverage of practical applications, and is missing a proper bibliography.^[3] Another complaint, by Bernhard Korte, is that the book's title is misleading: "independence spaces" often refers more generally to abstract simplicial complexes, while the book concentrates much more specifically on matroids. Korte also echoes the other reviewers' complaints about the lack of coverage of applications in combinatorial optimization and of connections to lattice theory.^[5]