Perfect Matchings

# 1. Definition

A perfect matching(a.k.a. 1-factor) on a ground set $\mathcal{S}$ is a set partition $\mathcal{P}$ of $\mathcal{S}$ into parts of length exactly 2.

# 2. Examples

Let $\mathcal{S} = \{1, 2, 3, 4, 5, 6, 7, 8\}$.

• $\{ \{1, 2\}, \{3, 4\}, \{5, 6\}, \{7, 8\} \}$

• $\{ \{1, 3\}, \{2, 4\}, \{5, 6\}, \{7, 8\} \}$

• $\{ \{1, 7\}, \{2, 4\}, \{3, 5\}, \{6, 8\} \}$

• $\{ \{1, 5\}, \{2, 6\}, \{3, 8\}, \{4, 7\} \}$

The nine perfect matchings of the cubical graph are illustrated above, notice that every vertex is covered.

# 3. Properties

• The size of $\mathcal{S}$ is necessarily even.

• The number of perfect matchings of a fixed set $\mathcal{S}$ with $|\mathcal{S}| = 2n$ is equal to $(2n-1)!! = 1 \cdot 3 \cdot 5 \cdot \cdots \cdot (2n - 1)$.

# 4. Remarks

• A near-perfect matching is one where exactly one vertex is unmatched.

• Perfect matchings can also be seen as fixed point free involutions on $\mathcal{S}$.

• Perfect matchings have a matrix known as the Weingarten matrix which are used to compute polynomial integrals over the orthogonal group $O_N$ [CM].

• Perfect matchings correspond to Kekulé structures in chemistry and give important information about the chemical structure of compounds. Applications include estimation of resonance energy, estimation of π-electron energy, and estimation of bond lengths.
• Hall's marriage theorem provides a characterization of bipartite graphs which have a perfect matching.

• Tutte's theorem provides a characterization for arbitrary graphs which have a perfect matching.

• An Aztec diamond of order n consists of all squares of a square lattice whose centers (x,y) satisfy |x| + |y| ≤ n. The number of perfect matchings of a Aztec diamond of order n is 2^n(n+1)/2.

# 5. Statistics

We have the following 15 statistics in the database:

The number of nestings of a perfect matching.
The number of crossings of a perfect matching.
The number of crossings plus two-nestings of a perfect matching.
The number of vertices of the unicellular map given by a perfect matching.
The number of short pairs.
The number of alignments in a perfect matching.
The size of the largest partition in the oscillating tableau corresponding to the....
The sum of the partition sizes in the oscillating tableau corresponding to a perf....
The number of pairs with odd minimum in a perfect matching.
The Grundy value for the game of removing nestings in a perfect matching.
The size of the orbit under rotation of a perfect matching.
The indicator function of whether a given perfect matching is an L & P matching.
The number of flips required to make a perfect matching noncrossing.
The number of nesting-similar perfect matchings of a perfect matching.
The number of crossing-similar perfect matchings of a perfect matching.

# 6. Maps

We have the following 4 maps in the database:

to permutation
to set partition
reverse
Kasraoui-Zeng

# 7. References

[CM]   Benoit Collins and Sho Matsumoto, On some properties of orthogonal Weingarten functions, arXiv:0903.5143.

# 8. Sage examples

PerfectMatchings (last edited 2015-12-16 23:02:50 by JordanThielen)