edit this page

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 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
link pattern
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.

8. Sage examples


CategoryCombinatorialCollection