Approximate counting and entropy of perfect matchings

The explanation

Six people need to pair off for a dance. If anyone may dance with anyone, there are 15 ways. The first person has 5 choices of partner, the next unpaired person has 3, and the last two have 1. With 20 people the count is 654,729,075. With 100 people it is about 2.7 × 10^78. Each complete pairing is called a perfect matching. It pairs every point of a network, using only allowed pairs.

Real networks allow only some pairs, and then no simple formula exists. Finding one perfect matching is easy. Jack Edmonds gave a fast method for that in 1965. Counting them all exactly is another matter. In 1979, Leslie Valiant showed that exact counting is #P-complete, even for bipartite networks. Bipartite means the points form two sides and every allowed pair crosses between them. The label #P-complete means as hard as a broad class of counting problems with no known fast method.

So researchers aimed for good estimates instead. An FPRAS (fully polynomial randomized approximation scheme) is a method that flips coins. You pick an error, such as 1 percent, and a failure chance, such as one in a million. The method must land within that error, except with at most that failure chance. Its running time may grow only like a fixed power of the input size and of 1 over the error. The failure chance costs even less: only its logarithm enters.

In 1989, Mark Jerrum and Alistair Sinclair gave an FPRAS for counting all matchings, of every size. Their method for perfect matchings needed a promise. Near-perfect matchings, which leave two points unpaired, could not outnumber perfect ones too badly. In 2004, Jerrum, Sinclair and Eric Vigoda removed that promise for bipartite networks. General networks stayed open. Jerrum and Sinclair had raised that question explicitly in 1989.

The one obstacle was that the bipartite method does not stretch. These methods take a long random walk through possible matchings, then read off statistics. In 2018, Daniel Štefankovič, Vigoda and John Wilmes built networks that defeat every walk of the 2004 type. On them, the walk either almost never visits a perfect matching or takes exponentially long to spread out. The new paper walks through a different space. It keeps several perfect matchings at once, on a larger network with colored linksSource 1. A move swaps a closed loop of links between two of them. The count starts from the network where every pair is allowed, which is easy to countSource 2. Then the missing links are weakened step by step, and the changes are multiplied together.

The first paper proves that this gives an FPRAS for every finite network without repeated links or weightsSource 3,Source 4. If no perfect matching exists, it returns zero every time. The time bound holds on every run, even unlucky onesSource 5. It is a guarantee about growth, not a practical program. The paper says its constants favour clear estimates over speedSource 6.

The companion paper studies spread. Take four people, with all 6 pairs allowed. There are 3 perfect matchings. Ask each pair to appear with probability 1/3. Only one random choice fits: each matching with chance 1/3. Its entropy, a measure of how spread out a random choice is, equals ln 3, about 1.10. The paper compares this with two sums built from the pair probabilities alone. Here they are F ≈ 2.20 and B ≈ 1.62. With m = 2 pairs, its theorem says F − (2 − 2/m)·B ≤ entropy ≤ F. That reads 0.58 ≤ 1.10 ≤ 2.20. Turned back into counts, the bounds say between about 1.78 and 9 matchings. The true count is 3.

The upper bound was already known, from Shearer's entropy inequalitySource 7. The lower bound is the new partSource 8. For bipartite networks, work of Schrijver and Gurvits implies the stronger F − B. The paper shows this fails in general, with an eight-point exampleSource 9. In 2018, Nima Anari, Shayan Oveis Gharan and Cynthia Vinzant asked a related question for their counting framework. Does their entropy objective exceed the log of the count by only a linear amount? The paper claims yes: the excess is at most 3m − 2. The bound holds at every feasible set of probabilities, including edge cases where some are 0 or 1Source 10. It also proves a fast method that never flips coins. That method is only accurate within a factor of 512^n for n pointsSource 11. It also claims a sharp count about the shape of the set of feasible probabilities.

How sure is this? A computer proof checker called Lean has checked formal versions of the main statements. These are the FPRAS, the entropy bounds, and the 512^n method. Each is matched against a fixed reference statement by a tool called Comparator. The paper's sharp shape count is outside that check. No specialist review of either paper has been published.

What it doesn't show. This does not give a practical program: the running time is a polynomial guarantee with large constants.