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\}$.

PerfectMatching_1000.png

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

3. Properties

4. Remarks

5. Statistics

We have the following 22 statistics on Perfect matchings 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.
The propagating number of a perfect matching.
The number of terminal right-hand endpoints when the vertices are written in orde....
The number of closers smaller than the largest opener in a perfect matching.
The largest opener of a perfect matching.
The decomposition number of a perfect matching.
The number of topologically connected components of a perfect matching.
The number of matchings in the dihedral orbit of a perfect matching.

6. Maps

We have the following 8 maps in the database:

to permutation
to set partition
link pattern
reverse
Kasraoui-Zeng
rotation
inverse rotation
to noncrossing matching

7. References

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

8. Sage examples


CategoryCombinatorialCollection