Title (eng)
Arithmetic matroids and an application to number theory
Parallel title (deu)
Arithmetische Matroide und eine Anwendung in der Zahlentheorie
Author
Marcus Schönfelder
Advisor
Christian Krattenthaler
Assessor
Christian Krattenthaler
Abstract (deu)
Ein Matroid ist eine kombinatorische Struktur, die das Konzept von linearer Abhängigkeit auf ganz verschiedene endliche Mengen verallgemeinert. Klassischerweise werden Matroide über endlichen Mengen von Vektoren oder über Graphen betrachtet. Wir erhalten dadurch eine Theorie, die die strukturellen Grundkonzepte der Linearen Algebra mit denen der Graphentheorie verbindet. Von besonderem Interesse ist hierbei das Tutte-Polynom T (x, y) als strukturelle Invariante eines jeden Matroids. Dieses Polynom kodiert allerlei nützliche kombinatorische Information der zu Grunde liegenden mathematischen Struktur. So finden sich etwa die Anzahlen aller Möglichkeiten, einen Graphen mit einer gegebenen Anzahl an Farben einzufärben, in seinem Tutte-Polynom versteckt. Allerdings berücksichtigen gewöhnliche Matroid-Strukturen wirklich nur Sachverhalte die aus der Unabhängigkeit der Teilmengen resultieren. Die italienischen Mathematiker Luca Moci und Michele D’Adderio konfrontieren dieses Problem mit der von ihnen entwickelten Theorie der arithmetischen Matroide. Arithmetische Matroide sind nun Matroide, welche zusätzlich mit einer sogenannten Vielfachheitsfunktion ausgestattet sind. Diese kann nun je nach Wahl ganz beliebige kombinatorische Daten beinhalten, welche schließlich auch in die Definition des arithmetischen Tutte-Polynoms M (x, y) einfließen. Dieses erweiterte Tutte-Polynom kann nun allerlei weitere Daten der zu Grunde liegenden mathematischen Struktur in sich tragen. Beispielsweise werden wir sehen, dass wir einen arithmetischen Matroid über einem Zonotop im R^n definieren können, dessen arithmetisches Tutte-Polynom zum Ehrhart-Polynom des Zonotops spezialisiert werden kann. Diese Arbeit umfasst vier Teile, in denen wir die wichtigsten Aspekte der Theorie arithmetischer Matroide und ihrer arithmetischen Tutte-Polynome zusammenfassen. Im ersten Teil wiederholen wir die Grundbegriffe der klassischen Matroidtheorie. Anschließend betrachten wir im zweiten Teil die Definition eines arithmetischen Matroids. Wir sehen uns einige grundlegende Beispiele an und formulieren Konzepte wie Darstellbarkeit und Dualität nun für den arithmetischen Fall. Der dritte und größte Teil ist dem arithmetischen Tutte-Polynom gewidmet. Wir sehen einige Verallgemeinerungen von Formeln, die aus der klassischen Matroidtheorie bekannt sind. Anschließend schauen wir uns Anwendungen und Interpretationen des arithmetischen Tutte-Polynoms in konkreten Fällen an. Zu guter Letzt konstruieren wir eine neue Klasse an quasi-arithmetischen Matroiden über Objekten der Zahlentheorie. Diese werden wir schließlich Radikalmatroide taufen, da ihre Vielfachheitsfunktionen durch die Radikalfunktion gegeben sind. Wir erforschen ihren Zusammenhang mit den arithmetischen Matroiden und geben eine vollständige Charakterisierung aller darstellbaren Radikalmatroide an.
Abstract (eng)
Matroids are combinatorial structures that abstract the notion of linear independence on finite sets. In their most famous examples they closely connect finite dimensional linear algebra with graph theory. In applications they are mostly regarded together with their most important invariant: the Tutte polynomial T (x, y). This bivariate polynomial is encoding a huge amount of combinatorial data of the underlying matroid (for example the number of spanning trees and possible colourings of a graph). Now arithmetic matroids form a true combinatorial generalisation of the notion of ordinary matroids. While classical matroids are only concerned with the dependency relations of the underlying structure, an arithmetic matroid is also equipped with a certain multiplicity function that contains additional combinatorial information. These multiplicities are also used to construct the so-called arithmetic Tutte polynomial M (x, y). This advanced version of the Tutte polynomial may now encode various useful new data of the underlying structure, depending on the choice of the multiplicities. For example, if we consider a zonotope in R^n whose corners lie in a lattice Λ ⊆ R^n, then we will see that we can associate an arithmetic matroid to the zonotope whose arithmetic Tutte polynomial specialises to the Ehrhart polynomial of the zonotope. This theory was mainly developed by the insights of Luca Moci in his pioneering paper A tutte polynomial for toric arrangements [Moc11] from 2011. The abstract concept of an arithmetic matroid was then firstly defined by Moci and D’Adderio [MD12] in 2012. In this thesis we summarize the essential aspects of the theory of arithmetic matroids and arithmetic Tutte polynomials. In the first part we start with an introduction to standard matroid theory to establish the basic concepts and terminology. Afterwards in the second part, we discuss the different axiomatisations as well as the most important structural properties of arithmetic matroids. We will see the main examples and talk about how to adapt the concepts of representability, duality, direct sums, deletion and contraction of matroids to the arithmetic situation such that their essential qualities are preserved. The third part of this thesis is committed to the arithmetic Tutte polynomial, for which we list generalisations of many of the identities known from the standard matroid case. Eventually we talk about possible specialisations of the arithmetic Tutte polynomials in the concrete cases of arithmetic matroids over lattice points and labeled graphs. The fourth and final part of the thesis is dedicated to the construction of a class or quasi-arithmetic matroids inside the realms of number theory. We will call them radical matroids since they will have radicals as multiplicities. We aim for analysing cases where radical matroids are also arithmetic matroids and will give a full characterisation of the representable radical matroids.
Keywords (deu)
MatroidArithmetischer MatroidTutte-PolynomArithmetisches Tutte-PolynomRadikalmatroid
Keywords (eng)
Matroidarithmetic matroidTutte polynomialarithmetic Tutte polynomialmultiplicity matroidradical matroid
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:2075437
rdau:P60550 (deu)
ix, 102 Seiten : Illustrationen
Number of pages
113
Association (deu)
Title (eng)
Arithmetic matroids and an application to number theory
Parallel title (deu)
Arithmetische Matroide und eine Anwendung in der Zahlentheorie
Author
Marcus Schönfelder
Abstract (deu)
Ein Matroid ist eine kombinatorische Struktur, die das Konzept von linearer Abhängigkeit auf ganz verschiedene endliche Mengen verallgemeinert. Klassischerweise werden Matroide über endlichen Mengen von Vektoren oder über Graphen betrachtet. Wir erhalten dadurch eine Theorie, die die strukturellen Grundkonzepte der Linearen Algebra mit denen der Graphentheorie verbindet. Von besonderem Interesse ist hierbei das Tutte-Polynom T (x, y) als strukturelle Invariante eines jeden Matroids. Dieses Polynom kodiert allerlei nützliche kombinatorische Information der zu Grunde liegenden mathematischen Struktur. So finden sich etwa die Anzahlen aller Möglichkeiten, einen Graphen mit einer gegebenen Anzahl an Farben einzufärben, in seinem Tutte-Polynom versteckt. Allerdings berücksichtigen gewöhnliche Matroid-Strukturen wirklich nur Sachverhalte die aus der Unabhängigkeit der Teilmengen resultieren. Die italienischen Mathematiker Luca Moci und Michele D’Adderio konfrontieren dieses Problem mit der von ihnen entwickelten Theorie der arithmetischen Matroide. Arithmetische Matroide sind nun Matroide, welche zusätzlich mit einer sogenannten Vielfachheitsfunktion ausgestattet sind. Diese kann nun je nach Wahl ganz beliebige kombinatorische Daten beinhalten, welche schließlich auch in die Definition des arithmetischen Tutte-Polynoms M (x, y) einfließen. Dieses erweiterte Tutte-Polynom kann nun allerlei weitere Daten der zu Grunde liegenden mathematischen Struktur in sich tragen. Beispielsweise werden wir sehen, dass wir einen arithmetischen Matroid über einem Zonotop im R^n definieren können, dessen arithmetisches Tutte-Polynom zum Ehrhart-Polynom des Zonotops spezialisiert werden kann. Diese Arbeit umfasst vier Teile, in denen wir die wichtigsten Aspekte der Theorie arithmetischer Matroide und ihrer arithmetischen Tutte-Polynome zusammenfassen. Im ersten Teil wiederholen wir die Grundbegriffe der klassischen Matroidtheorie. Anschließend betrachten wir im zweiten Teil die Definition eines arithmetischen Matroids. Wir sehen uns einige grundlegende Beispiele an und formulieren Konzepte wie Darstellbarkeit und Dualität nun für den arithmetischen Fall. Der dritte und größte Teil ist dem arithmetischen Tutte-Polynom gewidmet. Wir sehen einige Verallgemeinerungen von Formeln, die aus der klassischen Matroidtheorie bekannt sind. Anschließend schauen wir uns Anwendungen und Interpretationen des arithmetischen Tutte-Polynoms in konkreten Fällen an. Zu guter Letzt konstruieren wir eine neue Klasse an quasi-arithmetischen Matroiden über Objekten der Zahlentheorie. Diese werden wir schließlich Radikalmatroide taufen, da ihre Vielfachheitsfunktionen durch die Radikalfunktion gegeben sind. Wir erforschen ihren Zusammenhang mit den arithmetischen Matroiden und geben eine vollständige Charakterisierung aller darstellbaren Radikalmatroide an.
Abstract (eng)
Matroids are combinatorial structures that abstract the notion of linear independence on finite sets. In their most famous examples they closely connect finite dimensional linear algebra with graph theory. In applications they are mostly regarded together with their most important invariant: the Tutte polynomial T (x, y). This bivariate polynomial is encoding a huge amount of combinatorial data of the underlying matroid (for example the number of spanning trees and possible colourings of a graph). Now arithmetic matroids form a true combinatorial generalisation of the notion of ordinary matroids. While classical matroids are only concerned with the dependency relations of the underlying structure, an arithmetic matroid is also equipped with a certain multiplicity function that contains additional combinatorial information. These multiplicities are also used to construct the so-called arithmetic Tutte polynomial M (x, y). This advanced version of the Tutte polynomial may now encode various useful new data of the underlying structure, depending on the choice of the multiplicities. For example, if we consider a zonotope in R^n whose corners lie in a lattice Λ ⊆ R^n, then we will see that we can associate an arithmetic matroid to the zonotope whose arithmetic Tutte polynomial specialises to the Ehrhart polynomial of the zonotope. This theory was mainly developed by the insights of Luca Moci in his pioneering paper A tutte polynomial for toric arrangements [Moc11] from 2011. The abstract concept of an arithmetic matroid was then firstly defined by Moci and D’Adderio [MD12] in 2012. In this thesis we summarize the essential aspects of the theory of arithmetic matroids and arithmetic Tutte polynomials. In the first part we start with an introduction to standard matroid theory to establish the basic concepts and terminology. Afterwards in the second part, we discuss the different axiomatisations as well as the most important structural properties of arithmetic matroids. We will see the main examples and talk about how to adapt the concepts of representability, duality, direct sums, deletion and contraction of matroids to the arithmetic situation such that their essential qualities are preserved. The third part of this thesis is committed to the arithmetic Tutte polynomial, for which we list generalisations of many of the identities known from the standard matroid case. Eventually we talk about possible specialisations of the arithmetic Tutte polynomials in the concrete cases of arithmetic matroids over lattice points and labeled graphs. The fourth and final part of the thesis is dedicated to the construction of a class or quasi-arithmetic matroids inside the realms of number theory. We will call them radical matroids since they will have radicals as multiplicities. We aim for analysing cases where radical matroids are also arithmetic matroids and will give a full characterisation of the representable radical matroids.
Keywords (deu)
MatroidArithmetischer MatroidTutte-PolynomArithmetisches Tutte-PolynomRadikalmatroid
Keywords (eng)
Matroidarithmetic matroidTutte polynomialarithmetic Tutte polynomialmultiplicity matroidradical matroid
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:2082866
Number of pages
113
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0