On the Combinatorics of Valuations

Abstract

This thesis deals with structural results for translation invariant valuations on polytopes and certain related enumeration problems together with geometric approaches to them. The starting point of the first part are two theorems by Richard Stanley. The first one is his famous Nonnegativity Theorem stating that the Ehrhart h*-vector of every lattice polytope has nonnegative integer entries. He further proved that the entries satisfy a monotonicity property. In Chapter 2 we consider the h*-vector for arbitrary translation invariant valuations. Our main theorem states that monotonicity and nonnegativity of the h*-vector are, in fact, equivalent properties and we give a simple characterization. In Chapter 3 we consider the h*-vector of zonotopes and show that the entries of their h*-vector form a unimodal sequence for all translation invariant valuations that satisfy the nonnegativity condition. The second part deals with certain enumeration problems for order preserving maps. Given a finite poset P, a suitable subposet A of P, and an order preserving map f from A to the integers we consider the problem of enumerating order preserving extensions of f to P. In Chapter 4 we show that their number is given by a piecewise multivariate polynomial. We apply our results to counting extensions of graph colorings and generalize a theorem by Herzberg and Murty. We further apply our results to counting monotone triangles, which are closely related to alternating sign matrices, and give a short geometric proof of a reciprocity theorem by Fischer and Riegler. In Chapter 5 we consider counting order preserving maps from P to the n-chain up to symmetry. We show that their number is given by a polynomial in n, thus, giving an order theoretic generalization of Pólya’s enumeration theorem. We further prove a reciprocity theorem and apply our results to counting graph colorings up to symmetry.

Die vorliegende Arbeit beschäftigt sich mit der Struktur translationsinvarianter Bewertungen auf Polytopen und damit im Zusammenhang stehenden Abzählproblemen mit geometrischen Lösungsansätzen. Den Ausgangspunkt des ersten Kapitels bilden zwei Resultate von Richard Stanley: Zum einen sein bahnbrechendes Nonnegativity Theorem, welches aussagt, dass der Ehrhart h*-Vektor jedes Gitterpolytops nur nichtnegative ganze Zahlen enthält. Zum anderen zeigte er, dass dieser Vektor eine Monotonieeigenschaft besitzt. In Kapitel 2 untersuchen wir allgemein translationsinvariante Bewertungen auf diese Eigenschaften hin. Unser Hauptresultat ist, dass Nichtnegativität und Monotonie äquivalent sind, und wir geben eine einfache Charakterisierung an. In Kapitel 3 zeigen wir, dass der h*-Vektor eines Zonotops unimodal ist, falls die entsprechende translations-invariante Bewertung die Monotoniebedingung erfüllt. Der zweite Teil der Arbeit behandelt Abzählprobleme für ordnungserhaltenden Abbildungen. Für gegebene partielle Ordnungen A und P derart, dass A in P enthalten ist, und eine ordnungserhaltende Abbildung f von A nach [n] zeigen wir in Kapitel 4, dass die Anzahl der Fortsetzungen von f nach P durch ein stückweise multivariates Polynom gegeben ist. Angewandt auf das Zählen von Fortsetzungen von Graphenfärbungen verallgemeinert dies einen Satz von Herzberg und Murty. Zudem enumerieren wir Monotone Triangles, welche in engem Zusammenhang mit Alternating Sign Matrices stehen, und können einen kurzen geometrischen Beweis einer Reziprozität von Fischer und Riegler angeben. In Kapitel 5 zählen wir ordnungserhaltende Abbildungen von P nach [n] bis auf Symmetry. Wir zeigen, dass die Zählfunktion ein Polynom in n ist und beweisen eine ordnungstheoretische Verallgemeinerung von Pólya’s Enumeration Theorem. Zudem zeigen wir eine Reziprozität und wenden unsere Resultate darauf an Graphenfärbungen bis auf Symmetrie zu zählen.