# 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 22 statistics in the database:

St000041
Perfect matchings ⟶ ℤ
The number of nestings of a perfect matching.
St000042
Perfect matchings ⟶ ℤ
The number of crossings of a perfect matching.
St000043
Perfect matchings ⟶ ℤ
The number of crossings plus two-nestings of a perfect matching.
St000044
Perfect matchings ⟶ ℤ
The number of vertices of the unicellular map given by a perfect matching.
St000164
Perfect matchings ⟶ ℤ
The number of short pairs.
St000719
Perfect matchings ⟶ ℤ
The number of alignments in a perfect matching.
St000720
Perfect matchings ⟶ ℤ
The size of the largest partition in the oscillating tableau corresponding to the....
St000721
Perfect matchings ⟶ ℤ
The sum of the partition sizes in the oscillating tableau corresponding to a perf....
St000746
Perfect matchings ⟶ ℤ
The number of pairs with odd minimum in a perfect matching.
St000754
Perfect matchings ⟶ ℤ
The Grundy value for the game of removing nestings in a perfect matching.
St000780
Perfect matchings ⟶ ℤ
The size of the orbit under rotation of a perfect matching.
St000782
Perfect matchings ⟶ ℤ
The indicator function of whether a given perfect matching is an L & P matching.
St000787
Perfect matchings ⟶ ℤ
The number of flips required to make a perfect matching noncrossing.
St000788
Perfect matchings ⟶ ℤ
The number of nesting-similar perfect matchings of a perfect matching.
St000789
Perfect matchings ⟶ ℤ
The number of crossing-similar perfect matchings of a perfect matching.
St000819
Perfect matchings ⟶ ℤ
The propagating number of a perfect matching.
St000838
Perfect matchings ⟶ ℤ
The number of terminal right-hand endpoints when the vertices are written in orde....
St000840
Perfect matchings ⟶ ℤ
The number of closers smaller than the largest opener in a perfect matching.
St000841
Perfect matchings ⟶ ℤ
The largest opener of a perfect matching.
St000843
Perfect matchings ⟶ ℤ
The decomposition number of a perfect matching.
St000924
Perfect matchings ⟶ ℤ
The number of topologically connected components of a perfect matching.
St000945
Perfect matchings ⟶ ℤ
The number of matchings in the dihedral orbit of a perfect matching.

# 6. Maps

We have the following 8 maps in the database:

Mp00058
Perfect matchings ⟶ Permutations
to permutation
Mp00092
Perfect matchings ⟶ Set partitions
to set partition
Mp00098
Alternating sign matrices ⟶ Perfect matchings
Mp00113
Perfect matchings ⟶ Perfect matchings
reverse
Mp00116
Perfect matchings ⟶ Perfect matchings
Kasraoui-Zeng
Mp00144
Perfect matchings ⟶ Perfect matchings
rotation
Mp00145
Perfect matchings ⟶ Perfect matchings
inverse rotation
Mp00146
Dyck paths ⟶ Perfect matchings
to noncrossing matching

# 7. References

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