View source for Independence Theory in Combinatorics

{{Short description|Textbook on the theory of matroids}}
{{italic title}}
'''''Independence Theory in Combinatorics: An Introductory Account with Applications to Graphs and Transversals''''' is an undergraduate-level mathematics textbook on the theory of [[Matroid|matroid]]s. It was written by Victor Bryant and [[Biography:Hazel Perfect|Hazel Perfect]], and published in 1980 by Chapman & Hall.

==Topics==
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.{{r|lloyd}} It has five chapters, the first of which provides basic definitions in [[Graph theory|graph theory]], [[Combinatorics|combinatorics]], and [[Linear algebra|linear algebra]], and the second of which defines and introduces [[Matroid|matroid]]s, called in this book "independence spaces".{{r|welsh}} As the name would suggest, these are defined primarily through their independent sets, but equivalences with definitions using circuits, [[Matroid rank|matroid rank]], and [[Submodular set function|submodular set function]] are also presented, as are sums, minors, truncations, and duals of matroids.{{r|dorfler}}

Chapter three concerns [[Graphic matroid|graphic matroid]]s, the matroids of [[Spanning tree|spanning tree]]s in graphs,{{r|welsh}} and the [[Greedy algorithm|greedy algorithm]] for [[Minimum spanning tree|minimum spanning tree]]s.{{r|dorfler}} Chapter four includes material on transversal matroids, which can be described in terms of [[Matching (graph theory)|matching]]s of [[Bipartite graph|bipartite graph]]s, 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 square]]s, and [[Gammoid|gammoid]]s.{{r|welsh|dorfler}} The final chapter concerns [[Matroid representation|matroid representation]]s using [[Linear independence|linear independence]] in [[Vector space|vector space]]s,{{r|welsh}} labeled as an appendix and presented with fewer proofs.{{r|lloyd|dorfler|ganley}}

Many exercises are included, of varied difficulty, with hints and solutions.{{r|lloyd|welsh|dorfler}}

==Audience and reception==
The level of the text is appropriate for courses for advanced undergraduates or master's students,{{r|lloyd}} with only basic linear algebra as a prerequisite,{{r|welsh|ganley|korte}} and covers its material at a more accessible and general level than other texts on matroid theory.{{r|dorfler|ganley|rado}} Although disagreeing with the book's choice to omit the related topic of [[Geometric lattice|geometric lattice]]s, reviewer [[Biography:Dominic Welsh|Dominic Welsh]] calls it "an ideal text for an undergraduate course on combinatorial theory".{{r|welsh}} Michael J. Ganley similarly calls it "a very good introduction to quite a difficult subject".{{r|ganley}}

However, reviewer W. Dörfler complains that the book has inadequate coverage of practical applications, and is missing a proper bibliography.{{r|dorfler}} Another complaint, by Bernhard Korte, is that the book's title is misleading: "independence spaces" often refers more generally to [[Abstract simplicial complex|abstract simplicial complex]]es, 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|combinatorial optimization]] and of connections to lattice theory.{{r|korte}}

==References==
{{reflist|refs=

<ref name=dorfler>{{citation|first=W.|last=Dörfler|title = Review of ''Independence Theory in Combinatorics''|work=zbMATH|zbl=0435.05017}}</ref>

<ref name=rado>{{citation
 | date = May 1981
 | doi = 10.1112/blms/13.3.252
 | issue = 3
 | journal = Bulletin of the London Mathematical Society
 | pages = 252–253
 | publisher = Wiley
 | title = Review of ''Independence Theory in Combinatorics''
 | volume = 13}}</ref>

<ref name=welsh>{{citation
 | date = October 1981
 | doi = 10.2307/3617158
 | issue = 433
 | journal = The Mathematical Gazette
 | jstor = 3617158
 | page = 228
 | title = Review of ''Independence Theory in Combinatorics''
 | volume = 65}}</ref>

<ref name=lloyd>{{citation|first=E. Keith|last=Lloyd|journal=[[Mathematical Reviews]]|year=1982|mr=0604173|title=Review of ''Independence Theory in Combinatorics''}}</ref>

<ref name=korte>{{citation
 | date = January 1982
 | doi = 10.1016/0377-2217(82)90025-x
 | issue = 1
 | journal = [[European Journal of Operational Research]]
 | pages = 100–101
 | title = Review of ''Independence Theory in Combinatorics''
 | volume = 9}}</ref>

<ref name=ganley>{{citation
 | last = Ganley | first = Michael J.
 | date = October 1982
 | doi = 10.1017/s0013091500016795 | doi-access = free
 | issue = 3
 | journal = Proceedings of the Edinburgh Mathematical Society
 | page = 282
 | title = Review of ''Independence Theory in Combinatorics''
 | volume = 25}}</ref>
 
}}

[[Category:Mathematics textbooks]]
[[Category:Matroid theory]]

{{Sourceattribution|Independence Theory in Combinatorics}}