Title: Matrix tree theorems
Other Titles: Matrix-Baum Theoreme
Language: input.forms.value-pairs.iso-languages.en
Authors: Holzer, Fabian 
Qualification level: Diploma
Advisor: Gittenberger, Bernhard 
Issue Date: 2022
Citation: 
Holzer, F. (2022). Matrix tree theorems [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2022.99062
Number of Pages: 100
Qualification level: Diploma
Abstract: 
Das Ziel dieser Masterarbeit ist es, einen tieferen Einblick in verschiedene Aspekte des Matrix-Baum-Theorems zu vermitteln. Es wird eine Einführung in G. R. Kirchhoffs Matrix-Baum-Theorem geboten, wofür verschiedene Beweise präsentiert werden: der heute kanonische Beweis via die Cauchy-Binet Formel, G. R. Kirchhoffs ursprünglicher Zugang aus 1847, ein weiterer via das Inklusion-Exklusion Prinzip, ein sehr ähnlicher Beweis mit einer sogenannten Vorzeichen-umkehrenden Involution, um Subgraphen mit Zyklen zu entfernen, eine weitere Methode via Löschen und Zusammenziehen von Kanten, und ein probabilistischer Beweis mit Irrfahrten. Das Kapitel schließt mit Erwähnungen weiterer ähnlicher Sätze, unter anderem dem Matrix-Baum-Theorem auf Kanten, dem Matrix-Baum-Theorem mit der vorzeichenlosen Laplace’schen Matrix, und dem Markov-Ketten-Baum-Satz. Die zuvor vorgestellten Methoden werden dann benutzt, um das Matrix-Baum-Theorem auf Semiringen und für Hypergraphen zu beweisen. Um diese Verallgemeinerungen zu beschreiben, werden die symmetrische Erweiterung, Bideterminanten, arboreale Hypergraphen, Hyperbäume und die Pfaff’sche Determinante definiert.

The goal of this thesis is to provide a deeper insight into the inner workings of the matrix tree theorem. For this it introduces G. R. Kirchhoff’s matrix tree theorem and shows different approaches to prove it: the nowadays canonical proof via the Cauchy–Binet formula, G. R. Kirchhoff’s original approach used in 1847, one employing the inclusion–exclusion principle, a similar one applying a sign-reversing involution to remove subgraphs containing cycles, another using deletion–contraction via induction, and a probabilistic proof via random walks. The chapter closes with mentions of similar theorems, including the matrix tree theorem on edges, the matrix tree theorem using the signless Laplacian, and the Markov chain tree theorem. The previously presented methods are then applied to prove the matrix tree theorem on semirings and for hypergraphs. To formulate these generalisations, the symmetric extension of semirings, bideterminants, arboreal hypergraphs, hypertrees, and the Pfaffian are defined.
Keywords: matrix tree theorem; hypergraphs; semirings; spanning trees
URI: https://doi.org/10.34726/hss.2022.99062
http://hdl.handle.net/20.500.12708/20424
DOI: 10.34726/hss.2022.99062
Library ID: AC16556012
Organisation: E104 - Institut für Diskrete Mathematik und Geometrie 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:



Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.

Page view(s)

8
checked on Jun 25, 2022

Download(s)

2
checked on Jun 25, 2022

Google ScholarTM

Check