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 8 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....

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


CategoryCombinatorialCollection

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