Dissertationen online der Freien Universität Berlin


Ham sandwiches, staircases and counting polynomials
Breuer, Felix

HaupttitelHam sandwiches, staircases and counting polynomials
TitelvarianteHam Sandwiches, Treppen und Zählpolynome
AutorBreuer, Felix
Geburtsort: Berlin
GutachterProf. Dr. Martin Aigner
weitere GutachterProf. Dr. Volkmar Welker
Freie Schlagwörterpartition of measures; alpha-splitting; ham sandwich theorem; Poincaré-Miranda theorem; central sphere; staircase; Beatty sequence; Sturmian sequence; chromatic polynomial; flow polynomial; tension polynomial; combinatorial reciprocity theorem; lattice polytope; inside-out polytope; compressed polytope; Ehrhart theory; Hilbert function; relative Stanley-Reisner ideal; relative polytopal complex
DDC510 Mathematik
ZusammenfassungThis thesis consists of four chapters that are largely independent.

Counting Functions as Hilbert Functions.
Steingrímsson showed that the chromatic polynomial of a graph, shifted by one, is the Hilbert function of a relative Stanley-Reisner ideal. Dall and myself show that the modluar flow and tension polynomials as well as the integer valued flow and tension polynomials are Hilbert functions, and that the chromatic polynomial can be realized as a Hilbert polynomial without shifting. We have shown this by proving that the Ehrhart function of a relative polytopal complex with compressed faces is a Hilbert function of Steingrímsson's type. It is interesting how this problem can be approached from both a combinatorial and a geometric point of view and accordingly we give two proofs of our main theorem, exploring both approaches.

Counting Functions and Reciprocity Theorems.
Results that give the values of counting polynomials at negative integers a combinatorial interpretation are called reciprocity theorems. Sanyal and myself give a reciprocity theorem for the modular flow polynomial, the only one of the five polynomials mentioned above for which a reciprocity result was still missing. The Tutte polynomial is arguably the most important polynomial invariant of a graph. Combining reciprocity theorems for the modular flow and tension polynomials with a convolution formula of Kook, Reiner and Stanton yields a unified framework in which the value of the Tutte polynomial at every integer point in the plane can be given a combinatorial interpretation.

Staircases in the Plane.
Von Heymann and myself define a staircase in the plane to be the set of lattice points in the plane below a rational line that have Manhattan distance less than 1 to the line. This set of lattice points is closely related to the Beatty and Sturmian sequences of rational numbers defined in number theory. We present three characterizations of these sequences from a geometric point of view. One of these characterizations is known, two are new. The most important one is recursive and closely related to the Euclidean Algorithm. These geometric observations have several applications. First, they lead to a new proof of Barvinok's Theorem in dimension 2. Second, they yield a recursion formula for Dedekind-Carlitz polynomials. Third, they allow us to simplify Scarf's proof of White's Theorem.

Uneven Splitting of Ham Sandwiches.
The famous Ham Sandwich Theorem states that for any n probability measures in n-space there exists a hyperplane that splits each of these measures in half, simultaneously. What if we want to split the measures in a different ratio? I give a sufficient criterion for the existence of an uneven splitting, that can even be applied if the supports of the measures overlap. For the proof I employ a novel approach based on the Poincaré-Miranda Theorem.
Dataobject from FUDISS_thesis_000000014580
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
Seitenzahl165 S.
Fachbereich/EinrichtungFB Mathematik und Informatik
Rechte Nutzungsbedingungen
Tag der Disputation17.11.2009
Erstellt am15.12.2009 - 12:21:14
Letzte Änderung19.02.2010 - 11:46:56
Statische URLhttp://www.diss.fu-berlin.de/diss/receive/FUDISS_thesis_000000014580