Detailansicht
Counting integral points in polytopes
Liselotte Tschepen
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Betreuer*in
Ilse Fischer
DOI
10.25365/thesis.7116
URN
urn:nbn:at:at-ubw:1-29447.15457.782770-1
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Probleme, die sich durch das Zählen von ganzzahligen Punkten in Polytopen lösen lassen, treten in
den unterschiedlichsten mathematischen Gebieten auf. Es ist das Anliegen der vorliegenden Arbeit, einige Methoden darzustellen, mit denen diesen Abzählproblemen begegnet werden kann.
Die ersten Untersuchungen, die sich dezidiert mit dem Abzählen von ganzzahligen Punkten in Polytopen auseinandersetzen, finden sich in Arbeiten von Eug\`{e}ne Ehrhart aus den 1960er Jahren. Ehrhart betrachtete Streckungen von rationalen Polytopen um einen positiven ganzzahligen Faktor. Dabei entdeckte er, dass die Anzahl der ganzzahligen Punkte in diesen Streckungen durch ein Quasi-Polynom im Streckungsfaktor berechnet werden kann. Während wir uns im ersten Kapitel mit einer kurzen Einführung in die Polytoptheorie begnügen, die als Grundlage für die weiteren Betrachtungen dienen soll, wenden wir uns im Anschluss eingehend der Ehrhart-Theorie zu und liefern eine Darstellung ihrer wichtigsten Resultate.
Unter einem allgemeineren Blickwinkel kann man die Anzahl der ganzzahligen Punkte in Polytopen betrachten, die durch unabhängige Parallelverschiebung der Randflächen eines Polytops entstehen. Mit Hilfe der Theorie von "vector partition functions" lassen sich die Resultate der Ehrhart-Theorie für diese Polytope verallgemeinern.
Vor dem Hintergrund der Arbeit von Wolfgang Dahmen und Charles A. Micchelli \cite{DM} die im Zuge ihrer Untersuchungen von "box splines" auf "vector partition functions" gestoßen sind, führen wir im dritten Kapitel einen elementaren Beweis für eine Verallgemeinerung von Ehrharts Satz. Während der Ansatz von Dahmen und Micchelli auf den Eigenschaften von splines beruht, fußt unser Beweis auf geometrischen Betrachtungen und macht sich die Eigenschaften von Polytopen zunutze.
Mit diesen Mitteln können wir schließlich eine stärkere Version des Satzes aus \cite{DM} beweisen. Diese Variante wurde bereits von Andr\'{a}s Szenes und Mich\`{e}le Vergne in \cite{vergne} mit Hilfe von Methoden der Komplexen Analysis gezeigt.
Abstract
(Englisch)
Problems that may be approached by counting integral points in polytopes occur in many mathematical fields. It is the objective of the present thesis to provide methods that enable us to face these problems.
The first attempts that explicitly dealt with the issue of counting integral points in polytopes were made by Eug\`{e}ne Ehrhart in the 1960s. Ehrhart concerned himself with integral dilations of rational polytopes. In doing so, he discovered that the number of integral points in these dilated polytopes may be computed by a quasi--polynomial in the dilation factor. While we content ourselves with a short introduction to the theory of polytopes in the first chapter we will subsequently engage in a more detailed study on Ehrhart Theory that will provide us with a description of its most important results.
From a more general point of view, it is convenient to examine the number of integral points in polytopes that result from independent parallel motions of the bounding hyperplanes of a given rational polytope. By means of the theory of vector partition functions, it is possible to generalize the results of Ehrhart Theory in order to apply them to this type of problem.
Based on an article of Wolfgang Dahmen and Charles A. Micchelli \cite{DM} who came across vector partition functions in the course of their investigation on box splines, we will establish a proof of a generalization of Ehrhart's Theorem in chapter three. While the approach of Dahmen and Micchelli relies on properties of splines, our proof is based on geometrical considerations and makes use of properties of polytopes.
Eventually, we may, in this wise, provide a proof of a more general version of the theorem given in \cite{DM}. This result has already been achieved by Andr\'{a}s Szenes and Mich\`{e}le Vergne
in \cite{vergne} by means of complex analysis.
Schlagwörter
Schlagwörter
(Englisch)
integral points in polytopes Ehrhart quasi--polynomial vector partition functions
Schlagwörter
(Deutsch)
Ganzzahlige Punkte in Polytopen Ehrhart Quasi-polynome Vector Partitions Funktionen
Autor*innen
Liselotte Tschepen
Haupttitel (Englisch)
Counting integral points in polytopes
Paralleltitel (Deutsch)
Das Zählen von Gitterpunkten in Polytopen
Publikationsjahr
2009
Umfangsangabe
9, 132 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Ilse Fischer
Klassifikation
31 Mathematik > 31.12 Kombinatorik, Graphentheorie
AC Nummer
AC07855383
Utheses ID
6439
Studienkennzahl
UA | 405 | | |