How many ways a regular graph pairs off

A dance has six women and six men, and each person knows exactly three people of the other side. Hall’s theorem says everyone can be paired with an acquaintance at once: in a regular graph no group of $k$ people on one side can know fewer than $k$ on the other, because the group sends out $3k$ edges and each person on the other side can absorb at most three. So a perfect matching exists. The question this essay asks is the quantitative one. How many perfect matchings must there be, and how many can there be?

Both questions have exact answers for the growth rate, by two theorems published twenty-five years apart, and both answers can be watched at work on small cases. The lower bound turns out to describe what a typical graph does, and the upper bound what a very special graph does — which is the reverse of what a first guess would suggest about where extremes come from.

Counting matchings as a permanent #

Write the graph as a square table of 0s and 1s, a row for each point on top and a column for each point below, with a 1 where they are joined. A $d$-regular bipartite graph is a table in which every row and every column contains exactly $d$ ones. A perfect matching is a choice of $n$ ones, one in each row and each column, and the number of perfect matchings is the permanent of the table — the sum over all permutations of the products of entries, which is the determinant with all its minus signs made plus.

The permanent has no shortcut like Gaussian elimination, and computing it is believed to be hard in general. For tables up to about twenty rows Herbert Ryser’s formula of 1963 is practical: it adds up, over all $2^n$ subsets of columns, a product of row sums restricted to the subset, with alternating signs. Running through the subsets in Gray-code order, so that each step adds or removes one column, makes each term cheap. Every count in this essay is computed that way.

Two edges at every point #

The case $d = 2$ is completely transparent and shows why there is something to prove.

With two edges at every point, the graph splits into cycles that alternate between top and bottom, and a cycle has exactly two perfect matchings: every other edge, starting from either. So the number of matchings is 2 raised to the number of cycles. It can be as small as 2, when the whole graph is one long cycle, and as large as $2^{n/2}$, when every cycle has length four. That smallest value does not grow with $n$ at all, so for degree two there is no interesting lower bound: a huge 2-regular graph can still have just two ways to pair everyone off. The largest is reached by a union of copies of the complete graph on two and two.

The same picture has a reading in terms of permutations. A 2-regular table is the sum of two permutation tables, one for each perfect matching in a cycle taken alternately, and its cycles are the cycles of the permutation that carries one matching into the other. So counting matchings of 2-regular graphs is counting the cycles of a permutation, and a random 2-regular graph, whose permutation is random, has about $\ln n$ cycles and so typically about $n^{\ln 2}$ perfect matchings — polynomially many, not exponentially.

From degree three upwards things change, and the number of matchings is forced to grow exponentially.

Every cubic graph on six and six #

For six points a side and three edges each, every possible graph can be listed: they are the 0–1 tables of order 6 with every row and column summing to 3, and a search that builds such tables row by row, rejecting any row that would overfill a column or leave one unfillable, finds 297,200 of them. That count, a classical one, is checked in the computation.

The permanent of each takes only four values: 17, 18, 20 and 36. There are 21,600 tables with 17, 216,000 with 18, 59,400 with 20, and 200 with 36. The two hundred at the top are all the same graph up to relabelling — two disjoint copies of the complete graph on three and three, each matched in $3! = 6$ ways, so $6 \times 6 = 36$ in all. The other graphs are connected or nearly so, and they cluster at the bottom. The least, 17, is far above anything a crude argument would suggest, and above the general lower bound for this size, which is about 5.6.

The top value is the only disconnected one. A cubic bipartite graph that falls into pieces must have at least three points a side in each piece, so on six and six the only possibility is two complete graphs on three and three; every other table is a connected graph, and every connected cubic graph on six and six has 17, 18 or 20 perfect matchings. The gap between 20 and 36 is the price of connection. It is the same effect that the search for a matching meets in the other direction: in a connected graph the choices interfere with one another, and interference cuts the count.

Brégman’s ceiling #

The upper end has a clean answer. Lev Brégman proved in 1973, settling a conjecture of Henryk Minc, that a 0–1 table with $r_i$ ones in row $i$ has permanent at most

$$\prod_i (r_i!)^{1/r_i},$$

so a $d$-regular bipartite graph on $n$ points a side has at most $(d!)^{n/d}$ perfect matchings. When $d$ divides $n$, disjoint copies of the complete graph on $d$ and $d$ achieve it exactly: each copy has $d!$ matchings and there are $n/d$ copies. That is the graph on the right of the hero. The bound appeared earlier on this shelf as the ceiling on how many Latin squares there can be, whose rows extend one at a time through perfect matchings of regular graphs.

The intuition for why splitting into complete pieces is best is that a perfect matching is a sequence of choices — row 1 picks a column, row 2 picks among what remains, and so on — and the number of options each row has left is largest when rows that share columns share all their columns. In a block, once one row has chosen, the others in its block lose exactly one option each and nothing else. Jaikumar Radhakrishnan gave a proof in 1997 that makes this precise with entropy, averaging over random orders in which the rows choose.

Schrijver’s floor #

The lower end is much harder. A first bound comes from the van der Waerden conjecture, proved by Georgii Egorychev and Dmitry Falikman in 1981: a doubly stochastic table, with non-negative entries and every row and column adding to 1, has permanent at least $n!/n^n$. Dividing a $d$-regular table by $d$ makes it doubly stochastic, so the number of matchings is at least $n!\,d^n/n^n$, which by Stirling’s formula grows like $(d/e)^n$.

That is the right order for large $d$ but not for small. For $d = 3$ it gives growth rate $3/e \approx 1.10$ per vertex, while the truth is larger. Alexander Schrijver proved in 1998 the sharp bound

$$\text{matchings} \ge \left(\frac{(d-1)^{d-1}}{d^{d-2}}\right)^n,$$

which for $d = 3$ is $(4/3)^n$, and he showed that the base cannot be improved for any $d$: there are $d$-regular graphs whose number of perfect matchings grows no faster. For $d = 2$ the bound is $1^n$, which is right, as the long cycle showed.

The cubic case came first: Marc Voorhoeve proved in 1979 that a cubic bipartite graph on $n$ points a side has at least $6\,(4/3)^{n-3}$ perfect matchings, and Schrijver’s general proof, two decades later, was long and intricate. Leonid Gurvits found a short proof of both Schrijver’s bound and the van der Waerden theorem in 2006, by studying the polynomial $\prod_i \sum_j a_{ij} x_j$, whose coefficient of $x_1 x_2 \cdots x_n$ is the permanent. That polynomial has no zeros with all variables in the upper half-plane, a property related to the real-rootedness of matching polynomials, and Gurvits showed that each time one variable is differentiated away and set to zero, a quantity he called the capacity falls by at most a fixed factor. The factors multiply to Schrijver’s base.

Random graphs sit near the floor #

The graphs that show Schrijver’s bound cannot be improved are random ones. A typical regular graph, with no special structure, has close to the fewest matchings possible.

Each random graph was made by starting from a regular pattern and swapping the ends of pairs of edges many times, which keeps every degree at three while scrambling the structure. The growth rates per vertex start near the upper line at four points a side, where there is little room for anything else, and fall as the graphs grow: about 0.48 at six, 0.45 at eight, 0.40 at sixteen. Schrijver’s rate is $\ln(4/3) = 0.2877$ and Brégman’s is $\ln 6/3 = 0.5973$. The random graphs are drifting towards the lower line, slowly, and at sixteen points a side they are still about 0.11 above it per vertex.

The slow approach has a reason. The expected number of perfect matchings of a random regular bipartite graph equals Schrijver’s base to the power $n$ multiplied by factors that grow more slowly than any exponential, and at small sizes those factors are large enough to lift the rate per vertex well above the base; spread over more and more vertices, their effect dies away. So the floor is the right growth rate for a typical graph, but small graphs show it only roughly. The dashed van der Waerden curve, by contrast, starts high and sinks well below the random graphs: it is a correct bound but a weak one at degree three.

Both bounds as the degree grows #

With 12 points a side and degrees from 2 to 8, the random graphs again sit just above the lower line at every degree. Both bounds grow like $\ln d - 1$ as $d$ increases, the same rate as $n!\,(d/n)^n$, and the gap between them closes. Dense regular graphs have nearly as many perfect matchings as any graph of their degree could, and at $d = n$, the complete graph, the count is exactly $n!$, where every bound agrees.

The ratio of the two bounds, for fixed $d$, is an exponential factor $c_d^{\,n}$ with $c_d$ tending to 1 as $d$ grows: at $d = 3$ it is $6^{1/3}/(4/3) \approx 1.36$ per vertex, at $d = 8$ about $1.20$. So for sparse graphs the structure of the graph changes the count by an exponential factor, and for dense ones by a factor that is still exponential but much milder.

So the theory has a clear shape. For sparse regular graphs the number of perfect matchings can vary by an exponential factor, from Schrijver’s floor to Brégman’s ceiling, and the ceiling is reached only by disconnected graphs while the floor describes typical connected ones. For dense regular graphs the range collapses.

The same graphs as tables #

As tables, the graph with the most matchings is two blocks of ones on the diagonal. The graph with the fewest spreads its ones so that the rows overlap in many different columns, and a choice in one row constrains many others. Dividing either table by 3 gives a doubly stochastic table, and the van der Waerden theorem says that among all doubly stochastic tables the uniform one, every entry $1/n$, has the smallest permanent. That sounds as though it should favour spreading out, and the 0–1 tables seem to agree: the spread-out graph has fewer matchings. But a 0–1 table with three ones per row cannot be uniform; it can only approximate uniformity, and the more evenly it spreads, the closer it comes to the minimum.

For planar graphs there is a shortcut that the permanent otherwise lacks. Kasteleyn showed that signing the entries of the table suitably turns the permanent into a determinant, which counts the matchings exactly and in polynomial time; that is how the Aztec diamond’s tilings were counted. Cubic bipartite graphs are not planar in general, and for those no sign trick exists, which is part of why the bounds of this essay are the main tool for understanding their matchings.

Special maximum, random minimum #

The surprise is where the extremes come from. In many counting problems the extreme cases are special constructions and the typical case lies in the middle. Here the maximum is special — a disjoint union of complete pieces, which is about as unlike a random graph as a regular graph can be — and the minimum is not. A random cubic graph, one that a reader drawing edges blindfold would produce, has close to the fewest perfect matchings that any cubic graph can have. The van der Waerden theorem’s message, that the most spread-out mixture has the smallest permanent, is the continuous form of the same fact.

The other surprise is how few values occur. Among nearly three hundred thousand cubic graphs on six and six, the number of perfect matchings takes just four values. Six points a side is small enough that only a few shapes of graph exist up to relabelling, and the permanent sees only the shape.

A census that stops at six a side #

The census is exhaustive only at six points a side; at seven the tables are vastly more numerous, and the minimum there was not computed. The random graphs are a dozen per size, made by edge switching, which mixes well but not perfectly in the number of steps used; and the sizes run only to sixteen, far too small to show the growth rate settling. The claim that random graphs approach Schrijver’s rate is a theorem quoted from the literature, which the figures are consistent with but do not prove.

The figures also say nothing about non-regular graphs, where the bounds take different forms, nor about how hard it is to find the graph with the fewest matchings at a given size; Schrijver’s theorem gives the growth rate of the minimum, not the minimum itself.

Permanents by Ryser, the bounds quoted #

Computed here: permanents by Ryser’s formula, checked on small cases including the complete graph on four and four with $4! = 24$; every 0–1 table of order 6 with line sums 3, of which there are 297,200, and the permanent of each, giving counts 17, 18, 20 and 36 with multiplicities 21,600, 216,000, 59,400 and 200; unions of cycles with $2^{\text{cycles}}$ matchings; random regular graphs by edge switching, each checked to lie between the two bounds.

Quoted: Brégman’s theorem of 1973 and Minc’s conjecture; Radhakrishnan’s entropy proof; the van der Waerden theorem of Egorychev and Falikman; Schrijver’s theorem of 1998 and the sharpness of its base; the behaviour of random regular graphs.

Still open: the exact minimum #

Schrijver’s bound pins down the growth rate of the least number of perfect matchings, but not the least number itself. For a given $n$ and $d$, which $d$-regular bipartite graphs have the fewest perfect matchings, and how many do they have? For $d = 3$ the answer is known only for small $n$, from computer searches like the one above, and no family of graphs is known to achieve the minimum for every $n$. The analogous questions for general graphs, where the matchings are counted by a Pfaffian or a hafnian instead of a permanent, are less settled still. And the hardness of the permanent means there is no quick way to compute the count even for one large graph: approximating it within a constant factor is possible by a random walk, a celebrated result of Mark Jerrum, Alistair Sinclair and Eric Vigoda in 2001, but computing it exactly is believed impossible in reasonable time.

A ceiling for blocks, a floor for the rest #

A $d$-regular bipartite graph on $n$ points a side has between $((d-1)^{d-1}/d^{d-2})^n$ and $(d!)^{n/d}$ perfect matchings. The ceiling is reached by disjoint complete pieces; the floor is the growth rate of a typical random graph. Every cubic graph on six and six — 297,200 of them — has 17, 18, 20 or 36, and random cubic graphs up to sixteen a side sit between the bounds, drifting slowly down towards the floor.