Hafnian
Appearance
In mathematics, the hafnian of an adjacency matrix of a graph is the number of perfect matchings in the graph. It was so named by Eduardo R. Caianiello "to mark the fruitful period of stay in Copenhagen (Hafnia in Latin)."[1]
The hafnian of a 2n × 2n symmetric matrix is computed as
where is the symmetric group on [2n].[2]
Equivalently,
where is the set of all 1-factors (perfect matchings) on the complete graph , namely the set of all ways to partition the set into subsets of size .[3][4]
References
- ^ F. Guerra, in Imagination and Rigor: Essays on Eduardo R. Caianiello's Scientific Heritage, edited by Settimo Termini, Springer Science & Business Media, 2006, page 98
- ^ Rudelson, Mark, Alex Samorodnitsky, and Ofer Zeitouni. "Random Gaussian matrices and Hafnian estimators." arXiv preprint arXiv:1409.3905 (2014). http://arxiv.org/abs/1409.3905
- ^ Alexander Barvinok. Combinatorics and Complexity of Partition Functions. p. 93.
- ^ "Weighted counting of integer points in a subspace". p. 7. arXiv:1706.05423.
{{cite arXiv}}
: Unknown parameter|authors=
ignored (help)