Possible database queries for perfect matchings: search your data / browse all statistics / browse all maps
1. Definition & Example
A perfect matching of the set $\{1,2,3,\ldots,2n\}$ is a partition into blocks of size 2.
The three perfect matchings of $\{1,2,3,4\}$ |
||
[(1,2),(3,4)] |
[(1,3),(2,4)] |
[(1,4),(2,3)] |
There are $(2n-1)!! = 1 \cdot 3 \cdot 5 \cdot \cdots \cdot (2n - 1)$ such perfect matchings, see OEIS:A001147.
2. Additional information
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.
3. References
4. Sage examples
5. Technical information for database usage
- A perfect matching is uniquely represented as a sorted list of increasing pairs.
- Perfect matchings are graded by the size.
- The database contains all perfect matchings of size at most 10.