Matching Theory

László Lovász and Michael D. Plummer
Publisher:
American Mathematical Society
Publication Date:
2009
Number of Pages:
547
Format:
Hardcover
Series:
AMS/Chelsea Publishing 367
Price:
79.00
ISBN:
978-0-8218-4759-6
Category:
Monograph
BLL Rating:

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Miklós Bóna
, on
12/28/2009
]

This is a corrected reprint of the 1986 first edition of a classic book, with an 18-page Appendix describing progress in the area during the last 23 years.

A matching in a graph is a set of pairwise vertex-disjoint edges. This is the go-to book on everything known about matchings. This reviewer believes that the only way to do it justice is to give a somewhat detailed description of the contents, and then, at the end, to discuss possible uses.

Chapter I is on matchings in bipartite graphs, the situation occurring when five job openings are filled with five different candidates. The size of a maximum matching in a bipartite graph is equal to the size of the smallest vertex set S so that each edge has at least one endpoint in S. The authors prove this, and other classic theorems, and discuss the Hungarian algorithm, which finds the maximum matching of a bipartite graph in polynomial time.

The first half of Chapter 2 does not mention matchings at all; it discusses directed graphs in which each edge has a capacity, which can be thought of a the amount of water that can pass through that edge in a given time, hence the name “flow theory”. The main result proved here is the famous “Max-Flow Min-Cut” theorem, which we do not state here, but which the reader can easily review on pages 43–45. The second half of the chapter then shows how spectacularly this theorem implies the main theorems of Chapter 1.

In Chapter 3, we leave bipartite graphs and cover Tutte’s theorem showing that a graph G has a perfect matching if and only if its set of vertices V(G) has no subset S so that removing S from V(G), the remaining graph has more than |S| components of odd size. This theorem, originally proved in 1947, implies most of the earlier theorems as a special case. This is, however, not the strongest result in the chapter. That title goes to the Gallai-Edmonds structure theorem. That result has five parts, all related to a decomposition of any graph in a way that is very relevant to large matchings in the graph. It implies Tutte’s theorem as well.

Chapter 4 returns to bipartite graphs, but now with the goal of counting their perfect matchings, that is, matchings that cover each vertex of the graph. If in a bipartite graph each edge is contained in a perfect matching, then it that graph is called elementary. These are the important graphs for our purposes, since if an edge in a graph does not occur in any perfect matchings, then its removal will not change the number of those matchings. This motivates a complete characterization of elementary bipartite graphs.

Chapter 5 deals with the much more complicated topic of general graphs with perfect matchings. In their structural analysis, several other classes of special graphs are needed. They describe a complex procedure, called the Brick Decomposition Procedure, illustrated on page 144, to decompose general graphs with perfect matchings into simpler graphs. It involves ten different classes of graphs, which are defined in Chapters 3, 4, and 5.

It is here that the second half of the book starts. Up to this point, the discussion is all about matching theory pure and simple. From now on, other parts of graph theory, and other parts of combinatorics, will come into the picture.

Chapter 6 is about applications of matching theory to other parts of graph theory. One such topic is that of Hamiltonian cycles, that is, cycles that contain all vertices of a graph, and another one is the Chinese Postman problem. In the latter, we need to find a walk in a graph that uses each edge of the graph at least once, and consists of as few edges as possible.

In Chapter 7, the direction of applications is reversed. Instead of applying matching theory to other fields, the authors apply Linear Programming to Matching Theory. In particular, they show how the famous Duality Theorem from Linear Programming can be used to prove minimax theorems in matching theory. The matching polytope of a graph is defined as the convex hull of all incidence vectors of matchings of the graph. The perfect matching polytope is defined analogously. These polytopes are then studied from many angles. It is proved, for instance, that the dimension of the perfect matching polytope of an elementary bipartite graph is q – p + 1, where q is the number of edges, and p is the number of vertices.

Chapter 8 is the one that this reviewer (an enumerative combinatorialist) found the most enjoyable. The title is Determinants and Matching, and the results are typically upper bounds, lower bounds, and some exact formulae for the number of perfect matchings in various graphs. For bipartite graphs, it is easy to define a matrix, the so-called biadjacency matrix A, so that the permanent of A is equal to the number of perfect matchings of the graph. This leads to bounds from both sides, especially if the graph is regular. There is a section on probabilistic counting techniques. The chapter is replete with interesting theorems and conjectures, but here is the favorite of this reviewer: Let G be a k-connected graph that contains at least one perfect matching. Then G contains at least k!! = k(k–2)(k–4)… perfect matchings.

Chapter 9 discusses algorithms that find maximum matchings in non-bipartite graphs. These are much more complicated than the Hungarian algorithm that works in bipartite graphs and is covered in Chapter 1. The classic algorithms are often based on a step that shrinks an odd cycle to a single vertex. It is relatively easy to prove that maximum matchings are in a sense preserved by this operation. An enhanced version of the algorithm can find the maximum weight matching in a graph in which each edge has a weight associated to it. The chapter ends by exhibiting methods whose main idea is something other than shrinking an odd cycle.

Chapter 10 generalizes matching theory as follows. Let us assign an integer f(v) to each vertex v of the graph G. Is there a subgraph H of G that has the same vertex set as G so that each vertex v has degree f(v) in H? This is the f-factor problem. Note that the existence of a perfect matching is the special case when f(v) = 1 for all vertices v. A structure theory of f-factors then follows.

Perhaps Chapter 11 will be the least read since it is the most specialized. It is about a generalization of bipartite matchings into matroid theory. This is the only Chapter of the book whose main objects are (primarily) not graphs.

Chapter 12 is on the vertex packing number of a graph. This is the maximum number of vertices in an empty induced subgraph of a graph. It is often called the maximum number of independent vertices, and as such, is a dual notion to the maximum number of independent edges, which in turn is the size of a maximum matching in a graph. In general, the problem of deciding whether a graph has an independent set of a given size is NP-complete, so one cannot expect a theorem as strong as Tutte’s theorem for matchings discussed in Chapter 3. Still, many interesting structural theorems are proved, especially about critical graphs, that is, those whose vertex packing number goes up if any of their edges is removed.

As we mentioned, the book ends with an 18-page Appendix discussing progress in the field since 1986, with theorems, but no proofs, and with many references.

There is no question about the fact that the book is excellent reference material. Facts can be found in it rather easily, and there is a balance of old and new results.

Teaching a course from the book is also possible, with a few caveats. First, there is certainly enough material here for at least two semesters, so if you teach a one-semester course, be ready to make a lot of choices. At least three courses are possible: “Matching Theory,” “Applications of Matching Theory,” and a well-balanced mixture of the two. Second, while there are exercises in the book, they are not quite evenly distributed, and none come with solutions. So assigning homework will be a challenge. Third, some of the material is just plain difficult, so class preparation will have to be intensive. Still, if you are ready to commit the time to handle these issues, you will enjoy the power, beauty, and applicability of the theory explained by Lóvasz and Plummer.

Miklós Bóna is Professor of Mathematics at the University of Florida

• Matchings in bipartite graphs
• Flow theory
• Size and structure of maximum matchings
• Bipartite graphs with perfect matchings
• General graphs with perfect matchings
• Some graph-theoretical problems related to matchings
• Matching and linear programming
• Determinants and matchings
• Matching algorithms
• The $f$-factor problem
• Matroid matching
• Vertex packing and covering
• Appendix: Developments in matching theory since this book was first published
• References
• Index of terms
• Index of symbols
• Errata