Detailansicht
Matchings of the alternating sign triangle graph
Veronika Schreitter
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Mathematik
Betreuer*in
Ilse Fischer
DOI
10.25365/thesis.81168
URN
urn:nbn:at:at-ubw:1-27255.98838.869332-6
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Ayyer, Behrend und Fischer führten 2020 einen Graphen ein, dessen Matchings (die fast perfekt sind) mit alternierenden Vorzeichendreiecken (ASTs) auf dieselbe Weise in Verbindung stehen wie perfekte Matchings des Azteken-Graphen mit alternierenden Vorzeichenmatrizen (ASMs). Sie zeigten, dass es gleich viele ASTs wie ASMs gibt, und dass dasselbe für die zugehörigen Matchings gilt. Hier arbeiten wir hin auf eine elementare Abzählung der Matchings, die mit ASTs in Verbindung stehen, vor allem indem wir bekannte Methoden verallgemeinern. Insbesondere geben wir eine Verallgemeinerung von Ciucus Theorem über perfekte Matchings von zellulären Graphen an, wir finden einen gemeinsamen Rahmen für verschiedene bekannte Bijektionen zwischen Matchings und Pfadfamilien, wir verallgemeinern die planare Version des Lindström-Gessel-Viennot Lemmas, wir verknüpfen Operationen auf gerichteten Graphen mit Operationen auf Matrizen, die deren Pfadanzahlen beinhalten, wir behandeln umfassend Anzahlen von Schröder-Pfaden (die auch über der x-Achse starten und enden dürfen), und wir drücken Summen von Minoren als Pfaffsche Formen einzelner Matrizen aus (Okada folgend, aber mit einer Abwandlung ähnlich wie Ishikawa und Wakayama). Als Ergebnis wird die gesuchte Anzahl als Determinante relativ einfacher Matrizen ausgedrückt.
Abstract
(Englisch)
In 2020, Ayyer, Behrend, and Fischer introduced a graph whose matchings (which are nearly perfect) are related to alternating sign triangles (ASTs) in the same way that perfect matchings of the Aztec graph are related to alternating sign matrices (ASMs). They showed that ASTs and ASMs are equinumerous, and that the same holds for the associated matchings. Here, we work towards an elementary enumeration of the matchings related to ASTs, mainly by generalizing known techniques. In particular, we give a generalization of Ciucu's theorem about perfect matchings of cellular graphs, we find a common framework for various known bijections between matchings and path families, we generalize the planar version of the Lindström-Gessel-Viennot lemma, we relate operations on directed graphs to operations on matrices containing their path numbers, we broadly treat numbers of Schröder paths (allowed to start and end also above the x-axis), and we express sums of minors as Pfaffians of single matrices (following Okada, but giving a twist to it similar to Ishikawa and Wakayama). As a result, the sought-after number is expressed as the determinant of relatively simple matrices.
Schlagwörter
Schlagwörter
(Deutsch)
Alternierendes Vorzeichendreieck (AST) AST-Graph Alternierende Vorzeichenmatrix (ASM) Azteken-Diamant Azteken-Graph Q-partielles Matching Ciucus zelluläre Graphen Bijektion Matching Pfadfamilien MaPaf-Bijektion Rhombus-Pflasterung Lindström-Gessel-Viennot Lemma (LGV Lemma) Schröder-Pfad Schröder-Zahl Schröder-Matrix Linearität der Pfaffschen Form Summenformel für Minoren
Schlagwörter
(Englisch)
Alternating Sign Triangle (AST) AST-graph Alternating Sign Matrix (ASM) Aztec Diamond Aztec Graph Q-partial Matching Ciucu's Cellular Graphs Bijection Matching Path Family MaPaf-bijection Rhombus Tiling Lindström-Gessel-Viennot Lemma (LGV Lemma) Schröder Path Schröder Number Schröder Matrix Linearity of the Pfaffian Minor Summation Formula
Autor*innen
Veronika Schreitter
Haupttitel (Englisch)
Matchings of the alternating sign triangle graph
Publikationsjahr
2026
Umfangsangabe
iv, 127 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Ilse Fischer
Klassifikationen
31 Mathematik > 31.12 Kombinatorik. Graphentheorie ,
31 Mathematik > 31.25 Lineare Algebra. multilineare Algebra
AC Nummer
AC17891778
Utheses ID
80231
Studienkennzahl
UA | 066 | 821 | |