𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bideterminants, arborescences and extension of the Matrix-Tree theorem to semirings

✍ Scribed by M. Minoux

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
394 KB
Volume
171
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The Matrix-Tree Theorem is a well-known combinatorial result relating the value of the minors of a certain square matrix to the sum of the weights of the arborescences (= rooted directed trees) in the associated graph. We prove an extension of this result to algebraic structures much more general than the field of real numbers, namely commutative semirings. In such structures, the first law (addition) is not assumed to be invertible, therefore the combinatorial proof given here significantly differs from earlier proofs for the standard case. In particular, it requires the use of the concept of bideterminant of a matrix, an extension of the classical concept of determinant.

πŸ“œ SIMILAR VOLUMES

A generalization of the all minors tree
A generalization of the all minors tree theorem to semirings
✍ M. Minoux πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 616 KB

The 'All Minors Matrix Tree Theorem' (Chen, Applied Graph Theory, Graphs and Electrical Networks, North-Holland, Amsterdam, 1976; Chaiken, SIAM J. Algebraic Discrete Math. 3 (3) (1982) 319-329) is an extension of the well-known 'Matrix Tree Theorem' (Tutte, Proc. Cambridge Philos. Sot. 44 (1948) 463

Two bijective proofs for the arborescent
Two bijective proofs for the arborescent form of the Good–Lagrange formula and some applications to colored rooted trees and cacti
✍ Michel Bousquet; Cedric Chauve; Gilbert Labelle; Pierre Leroux πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 598 KB

Goulden and Kulkarni (J. Combin. Theory Ser. A 80 (2) (1997) 295) give a bijective proof of an arborescent form of the Good-Lagrange multivariable inversion formula. This formula was ΓΏrst stated explicitly by Bender and Richmond (Electron. J. Combin. 5 (1) (1998) 4pp) but is implicit in . In this pa

Extension of the quantum virial and Hell
Extension of the quantum virial and Hellmann–Feynman theorems to the quantum statistical averages
✍ DuΕ‘an Popov πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 155 KB

In the present article, we extended the quantum virial and Hellmann᎐Feynman theorems to the quantum statistical averages, that is, to the thermal states. We obtained some new formulas which make possible expressing the thermodynamical observables of the system as functions of the moments of coordina