Polytopes; valuations; nonnegativity; lattice point enumeration; unimodality; order preserving maps; combinatorial reciprocity;
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.
PDF-Datei von FUDISS_thesis_000000098742
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.