Ham sandwiches, staircases and counting polynomials

Abstract

This 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.

In meiner Dissertation behandle ich vier weitgehend unabhängige Themen. Zählfunktionen als Hilbert-Funktionen. Steingrímsson hat gezeigt, dass das verschobene chromatische Polynom eines Graphen die Hilbert-Funktion eines relativen Stanley-Reisner-Ideals ist. Dall und ich zeigen, dass sowohl die modularen als auch die ganzzahligen Varianten des Fluss- und des Tension- Polynoms eines Graphen Hilbert-Funktionen sind und dass sich auch das chromatische Polynom ohne Verschiebung als Hilbert-Funktion realisieren lässt. Wir zeigen dies, indem wir beweisen, dass die Ehrhart-Funktion eines relativen polytopalen Komplexes mit komprimierten Seiten eine Hilbert funktion in Steingrímssons Sinne ist. Wir geben sowohl einen kombinatorischen als auch einen geometrischen Beweis an. Reziprozitätssätze. Sätze, die die Werte von Zählpolynomen an negativen ganzen Zahlen kombinatorisch interpretieren, werden kombinatorische Reziprozitätssätze genannt. Sanyal und ich geben einen Reziprozitätssatz für das modulare Flusspolynom an, das einzige der fünf oben genannten Polynome, für das noch kein solcher Satz bekannt war. Das Tutte- Polynom ist die wichtigste polynomiale Invariante eines Graphen. Wir verbinden die Reziprozitätssätze für das modulare Fluss- und Tension-Polynom mit einer Konvolutionsformel von Kook, Reiner und Stanton, um zu ein einer kombinatorischen Interpretation der Werte des Tutte-Polynoms an jeder ganzzahligen Stelle der Ebene zu kommen. Treppen in der Ebene. Von Heymann und ich definieren eine Treppe als die Menge aller Gitterpunkte in der Ebene unterhalb einer Geraden mit rationaler Steigung, die Manhattan-Abstand höchstens 1 zur Geraden haben. Diese Mengen sind eng verwandt mit den aus der Zahlentheorie bekannten Sturm- und Beatty-Folgen rationaler Zahlen. Wir beweisen drei Charakterisierungen dieser Folgen aus einem geometrischen Blickwinkel. Zwei dieser Charakterisierungen sind neu. Die wichtigste ist rekursiv und steht in enger Beziehung mit dem Euklidischen Algorithmus. Diese geometrischen Überlegungen haben mehrere Anwendungen. Erstens führen sie zu einem neuen Beweis von Barvinoks Satz in Dimension 2. Zweitens ergeben sie eine Rekursionsformel für Dedekind-Carlitz-Polynome. Drittens erlauben sie es uns Scarfs Beweis des Satzes von White zu vereinfachen. Ungleiches Teilen von Ham Sandwiches. Der berühmte Ham Sandwich Satz besagt, dass es für n stetige Wahrscheinlichkeitsmaße im n-dimensionalen Raum immer eine Hyperebene gibt, die alle Maße gleichzeitig in gleiche Hälften teilt. Was, wenn wir eine Teilung in einem anderen Teilungsverhältnis suchen? Ich gebe ein hinreichendes Kriterium für die Existenz einer solchen ungleichen Teilung an. Dieses Kriterium kann auch angewandt werden, wenn sich die Träger der Maße überlappen. Für den Beweis verwende ich einen neuen Ansatz, basierend auf dem Satz von Poincaré und Miranda.