✦ LIBER ✦

A generalization of the all minors tree theorem to semirings

✍ Scribed by M. Minoux

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 616 KB
Volume: 199
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(98)00204-0

No coin nor oath required. For personal study only.

✦ Synopsis

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-482) which relates the values of the determinants of square submatrices of a given square matrix to the sum of the weights of some families of forests in the associated weighted graph. The 'All Minors Matrix Tree Theorem' is extended here to algebraic structures much more general than the field of real numbers, namely semirings. Since a semiring is no longer assumed to be a group with respect to the first law (addition), the combinatorial proof given here significantly differs from the one working on the field of real numbers. Even the statement of the result has to be changed since the standard concept of determinant of a matrix is not relevant any more and must be replaced by the concept of bideterminant.

The proof also significantly differs from the one used in a previous paper to derive the semiring extension of the Matrix Tree Theorem.

📜 SIMILAR VOLUMES

Bideterminants, arborescences and extens

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

✍ M. Minoux 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 394 KB

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 th

A simpler proof and a generalization of

A simpler proof and a generalization of the zero-trees theorem

✍ A Schrijver; P.D Seymour 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 290 KB

A Generalization of the Riesz Representa

A Generalization of the Riesz Representation Theorem to Infinite Dimensions

✍ Yuh-Jia Lee 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 393 KB

Let C p be the collection of real-valued functions f defined on E &p such that f is uniformly continuous on bounded subsets of Then C is a complete countably normed space equipped with the family [&}& , p : p=1, 2, 3, ...] of norms. In this paper it is shown that to every bounded linear functional

A Generalization of the Calderón-Vaillan

A Generalization of the Calderón-Vaillancourt Theorem to Lp and hp

✍ L. Päivärinta; E. Somersalo 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 432 KB

Generalization of Falk's theorem and the

Generalization of Falk's theorem and the i−δ relations for S = 1 on a Cayley tree

✍ B. Frank 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 181 KB

A generalization of the Keisler-Morley t

A generalization of the Keisler-Morley theorem to recursively saturated ordered structures

✍ Shahram Mohsenipour 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB

## Abstract We prove a model theoretic generalization of an extension of the Keisler‐Morley theorem for countable recursively saturated models of theories having a __κ__ ‐like model, where __κ__ is an inaccessible cardinal. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)