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 **20 statistics** in the database:

# 6. Maps

We have the following **4 maps** in the database:

# 7. References

*On some properties of orthogonal Weingarten functions*, arXiv:0903.5143.

# 8. Sage examples