Search

In geometric, algebraic, and topological combinatorics, properties such as symmetry, unimodality, and real-rootedness of combinatorial generating polynomials are frequently studied. In this thesis, we present three projects exploring various properties of polynomials arising from Ehrhart theory, the study of counting integer points in lattice polytopes. Many of the open questions on real-rootedness and unimodality of polynomials pertain to the enumeration of faces of cell complexes. When proving that a polynomial is real-rooted, we often rely on the theory of interlacing polynomials and their recursive nature. We relate the theory of interlacing polynomials to the shellability of cell complexes. We first derive a sufficient condition for stability of the $h$-polynomial of a subdivision of a shellable complex. To apply it, we generalize the notion of reciprocal domains for convex embeddings of polytopes to abstract polytopes and use this generalization to define the family of stable shellings of a polytopal complex. We characterize the stable shellings of cubical and simplicial complexes, and apply this theory to answer a question of Brenti and Welker on barycentric subdivisions for the well-known cubical polytopes. We also give a positive solution to a problem of Mohammadi and Welker on edgewise subdivisions of cell complexes. We end by relating the family of stable line shellings to the combinatorics of hyperplane arrangements. The Ehrhart polynomial $\text{ehr}_P(t)$ of a lattice polytope $P$ counts the number of integer points in the $n$-th dilate of $P$. The $f^*$-vector of $P$, introduced by Felix Breuer in 2012, is the vector of coefficients of $\text{ehr}_P(n)$ with respect to the binomial coefficient basis $ \left\{\binom{n-1}{0},\binom{n-1}{1},...,\binom{n-1}{d}\right\}$, where $d = \text{dim} P$. Similarly to $h/h^*$-vectors, the $f^*$-vector of $P$ coincides with the $f$-vector of its unimodular triangulations (if they exist). We present several inequalities that hold among the coefficients of $f^*$-vectors of polytopes. These inequalities resemble striking similarities with existing inequalities for the coefficients of $f$-vectors of simplicial polytopes; e.g., the first half of the $f^*$-coefficients increases and the last quarter decreases. Even though $f^*$-vectors of polytopes are not always unimodal, there are several families of polytopes that carry the unimodality property. We also show that for any polytope with a given Ehrhart $h^*$-vector, there is a polytope with the same $h^*$-vector whose $f^*$-vector is unimodal. Posets can be viewed as subsets of the type-A root system that satisfy certain properties. Geometric objects arising from posets, such as order cones, order polytopes, and chain polytopes, have been widely studied, though many open questions concerning them remain open, such as the unimodality of their $h^*$-vectors. In 1993, Vic Reiner introduced signed posets, which are subsets of the type-B root system that satisfy the same properties. We introduce the analogue of order and chain polytopes in this setting, focusing on the Ehrhart theory of these objects. We are able to determine when these signed order polytopes have symmetric $h^*$-vectors, and end with a discussion of open questions regarding signed chain polytopes.

Discrete geometry is a field of mathematics which encompasses the study of polyhedra, or intersections of closed half-spaces in some vector space. Algebraic combinatorics employs algebraic methods to learn about combinatorial objects. This thesis lies at the intersection of these two fields and traverses back and forth between them. We use algebra to prove results about polyhedra, and use polyhedral geometry to classify functions that are of interest in algebraic combinatorics. It is divided into four chapters: an introduction, and three sections of original results which each use different algebraic techniques.In the first chapter, we provide some background on polyhedra and establish the main actors of this thesis, generalized permutahedra. Along the way we introduce orbit polytopes and matroids as examples, and we also show how the combinatorics of generalized permutahedra can be extended to arbitrary finite reflection groups to obtain generalized Coxeter permutahedra and Coxeter matroids. We further give some background on combinatorial Hopf monoids, Ehrhart theory, and valuations that hints at the various approaches explored in this thesis.In the second chapter, we introduce the Hopf monoid of orbit polytopes, which is generated by the generalized permutahedra that are invariant under the action of the symmetric group. We show that modulo normal equivalence, these polytopes are in bijection with integer compositions. We interpret their Hopf structure through this lens, and we show that applying the first Fock functor to this Hopf monoid gives a Hopf algebra of compositions. We describe the character group of the Hopf monoid of orbit polytopes in terms of noncommutative symmetric functions, and we give a combinatorial interpretation of the basic character and its polynomial invariant.In Chapter 3, we explore equivariant Ehrhart theory, a generalization of Ehrhart theory introduced by Stapledon that counts the lattice points in a polytope up to the action of some symmetry group. We describe the equivariant Ehrhart theory of the permutahedron, and we explore the relationship between the properties of its equivariant Ehrhart series and the permutahedral toric variety. Answering a question of Stapledon, we describe the equivariant Ehrhart theory of the permutahedron, and we prove his Effectiveness Conjecture in this special case.In the last chapter, we give the universal valuative invariant of Coxeter matroids. In the process, we also describe the universal valuation of generalized Coxeter permutahedra. This chapter builds off of prior work of Derksen and Fink, but many of their techniques do not apply to the Coxeter setting, requiring new methods to extend their results. We borrow tools from the theory of 0-Hecke algebras to establish properties of Coxeter Schubert matroids.

The balanced minimum evolution (BME) polytope is a structure representative of a problem in biology, in particular in the study of phylogenetic trees. In this scope, the polytope is used to answer the question of how a set of species are related to one another. In this paper we explore generalized instances of the BME polytope for networks. For one of these generalized BME polytopes we focus on the discovery of new facets and their corresponding equations, while for the other we give the facets of the polytope and discuss the relationship that they have to another well known polytope outside of the field of biology. Furthermore, we also provide the dimension reducing equalities that were discovered which hold for every BME polytope and then prove their existence.

This dissertation explores hidden structure within scattering amplitudes in quantum field theory, both at tree-level and at loop-level, and introduces some novel methods for making this hidden structure manifest. In Chapter 1 we give a brief introduction to the field of scattering amplitudes. In Chapter 2, we examine two-loop amplitudes in half-maximal supergravity (SUGRA) and discuss different ways of manifesting the underlying and surprising UV-finiteness. In particular, we apply state of the art techniques for performing integration by parts (IBP) reduction on families of multiloop integrals and introduce a new way of exposing UV-cancellations by performing IBP reduction directly on vacuum diagrams in a way that does not mix up UV and IR divergences. In Chapter 3 we continue to explore IBP reduction, now from a different perspective. Here we focus on planar Feynman diagrams and use the properties of dual conformal transformations to identify a family of IBP vectors that do not double propagators, and are therefore compatible with the highly successful unitarity method of computing loop amplitudes. A natural extension of these ideas is to try to apply similar methods to nonplanar diagrams, and doing so leads to some very preliminary steps towards uncovering a nonplanar analog of dual conformal symmetry, which is believed to exist from other considerations. Initial steps along this direction are discussed at the end of this chapter. In Chapter 4 we continue on from Chapter 3 in uncovering a nonplanar analog of dual conformal symmetry. Here we show that through three loops in N = 4 super-Yang–Mills (sYM) theory at four points and through two loops at five points, a representation of the amplitudes exist such that every relevant nonplanar diagram enjoys this hidden nonplanar symmetry. In Chapter 5 we leave the world of loop amplitudes and consider one of the simplest classes of scattering amplitudes—tree amplitudes in planar N = 4 sYM. A novel geometric perspective on this class of amplitudes is afforded by the amplituhedron picture. We introduce a new formalism for computing these amplitudes in the NMHV helicity sector, and a new and purely combinatorial description of the underlying polytopes. Our formalism makes the equivalence of different triangulations of the underlying space manifest by introducing a new set of objects that can be used to express the amplitude uniquely. In Chapter 6 we discuss ongoing work. In the first section, we discuss some progress that has been made in extending the formalism introduced in Chapter 5 to different MHV sectors. This would provide new insight on the geometric underpinning of these amplitudes, which is currently not understood. Finally, in the last section of this chapter we describe an algorithm for finding complete sets of numerical solutions to the scattering equations, and doing so faster than other implementations currently available.

Abstract: We address several related problems from convex geometry and geometric tomography, which separate along two main themes. The content of this thesis is based on five papers, either published or submitted. The first theme concerns the origin-symmetry and unique determination of convex bodies. A convex body K is a compact and convex subset in n-dimensional Euclidean space with non-empty interior. We say K is origin-symmetric if it is equal to its reflection through the origin, that is K=-K. Makai, Martini, and Odor have shown that a convex body is necessarily origin-symmetric if every hyperplane section through the origin has maximal (n-1)-dimensional volume amongst all parallel sections. We prove a stability version of their result. Recently, Meyer and Reisner associated with every convex body K a new set, which they call the convex intersection body of K. It follows from previously known results that two origin-symmetric convex bodies coincide whenever their convex intersection bodies coincide. Removing the assumption of origin-symmetry, we show that Meyer and Reisner's convex intersection body does not uniquely determine a convex body up to congruency. A convex polytope P is a convex body which is the convex hull of finitely many points. We show that P must be origin-symmetric if every hyperplane section through the origin has maximal (n-2)-dimensional surface area amongst all parallel sections. This gives partial confirmation to a conjecture made by Makai, Martini, and Odor. Our second theme concerns extensions of Grunbaum's inequality, which gives a sharp lower bound for the volume of each half of a convex body that is split by a hyperplane through its centroid. In particular, we generalize this inequality to the orthogonal projections of a convex body onto subspaces, and the intersections of a convex body with subspaces through its centroid.

In this dissertation we first introduce an extension of the notion of parking functions to cars of different sizes. We prove a product formula for the number of such sequences and provide a refinement using a multi-parameter extension of the Abel--Rothe polynomial. Next, we study the incidence Hopf algebra on the noncrossing partition lattice. We demonstrate a bijection between the terms in the canceled chain decomposition of its antipode and noncrossing hypertrees. Thirdly, we analyze the sum of the th powers of the descent set statistic on permutations and how many small prime factors occur in these numbers. These results depend upon the base expansion of both the dimension and the power of these statistics. Finally, we inspect the ƒ-vector of the descent polytope DPv, proving a maximization result using an analogue of the boustrophedon transform.

Ability to design reliable and high quality products has always been an area of active interest to industries. With increasing commercial pressures, there is renewed interest to identify high performing designs that are both cost effective and reliable. Individual analysis of designs using such high fidelity solvers often consumes several thousand of CPU hours and use of such analysis within the course of optimization is still prohibitive even with todays massive computing power. Development of efficient optimization optimization algorithms and decision support tools to deal with such classes of problems is the primary focus of this dissertation. Two forms of computationally expensive analysis have been considered in this work. In the first, the underlying analysis is assumed to be black box in nature and the output/response is used as an objective or a constraint in the optimization formulation. For the second, the underlying analysis is assumed to be of iterative in nature. For the first, a flexible multiple surrogate assisted optimization algorithm is introduced that is capable of solving unconstrained and constrained multi/many objective optimization problems (where the term many-objective refers to optimization problems involving more than four objectives). As for the second i.e. multifidelity optimization, two novel optimization approaches have been introduced. Since a design optimization problem often involves one or more objectives in conflict, the solution is typically a large trade-off set. A decision support tool is introduced in this work which relies on the principles of expected marginal utility to select a handful of solutions of interest from a potentially large trade-off set of solutions. In addition to the above, two novel and computationally efficient methods have also been introduced to help identification of potential regions of interest for further exploration, given only a handful of trade-off solutions. All the above algorithmic developments have been rigorously tested and compared with state of the art approaches using a range of mathematical and engineering benchmarks to highlight the benefits of the developments and their utility in solving practical problems. The dissertation also summarizes some of the potential future developments that can overcome aforementioned and existing challenges.

A classical question in formal logic is "how much mathematics do we need to know in order to prove a given theorem?" Of particular interest is Harvey Friedman's grand conjecture: that every known mathematical theorem involving only finitary mathematical objects can be proven from Elementary Function Arithmetic (EFA)—a fragment of Peano Arithmetic. If Friedman's conjecture is correct, this would imply that Fermat's Last Theorem is derivable from the axioms of EFA. The vast task of proving Fermat's Last Theorem from the axioms of EFA seems to require certain theorems on convex polytopes and an important corollary: Minkowski's Linear Forms Theorem. I show that certain theorems of convex geometry—e.g. representation of polytopes both in vertex form and as the intersection of half-spaces, monotonicity of volume, the existence of a separating plane between disjoint polytopes, and Minkowski's Linear Forms Theorem—can be both interpreted and derived in EFA, assuming the well-definedness of volume of a convex polytope along with one other technical lemma.

While there is extensive literature on approximation of convex bodies by inscribed or circumscribed polytopes, much less is known in the case of generally positioned polytopes. In this thesis we give upper and lower bounds for the approximation of the Euclidean unit ball by arbitrarily positioned polytopes with a fixed number of vertices or facets in the surface area deviation. The main results of this paper are joint work with Dr. Carsten Schuett and Dr. Elisabeth Werner.In the introduction, we collect some definitions and background material from analysis and convex geometry that will be used throughout the paper. The main results of this dissertation are stated in Chapter 1. In Chapter 2, we collect several results related to our main results. Our focus there will be on results related to best and random approximation with respect to the volume, surface area, and mean width deviations. In Chapter 3 we state several auxiliary lemmas needed for the proofs of our main results. The proofs of our main results are given in Chapters 4 and 5.

We describe combinatorial techniques for studying log Calabi-Yau surfaces. These can be viewed as generalizing the techniques for studying toric varieties in terms of their character and cocharacter lattices. These lattices are replaced by certain integral linear manifolds described in [GHK11], and monomials on toric varieties are replaced with the canonical theta functions defined in [GHK11] using ideas from mirror symmetry. We classify deformation classes of log Calabi-Yau surfaces in terms of the geometry of these integral linear manifolds. We then describe the tropicalizations of theta functions and use them to generalize the dual pairing between the character and cocharacter lattices. We use this to describe generalizations of dual cones, Newton and polar polytopes, Minkowski sums, and finite Fourier series expansions. We hope that these techniques will generalize to higher rank cluster varieties.

Associahedra can be realized by taking the convex hull of coordinates derived from binary trees. Similarly, permutahedra can be found using leveled trees. In this paper we will introduce a new type of painted tree, (T ◦ Y)n where n is the number of interior nodes. We create these painted trees by composing binary trees on leveled trees. We define a coordinate system on these trees and take the convex hull of these points. We explore the resulting polytope and prove, using a bijection to tubings, that for n ≤ 4 the poset of the painted face trees with n+1 leaves is isomorphic to the face poset of an n-dimensional polytope, specifically KF1,n, the graph-associahedron for a fan graph, F1,n.

A long-standing problem in cobordism theory has been to find convenient manifolds to represent cobordism classes. For example, in the late 1950's, Hirzebruch asked which complex cobordism classes can be represented by smooth connected algebraic varieties. This question is still open. Progress can be made on this and related problems by studying certain convenient connected algebraic varieties, namely smooth projective toric varieties. The primary focus of this dissertation is to determine which complex cobordism classes can be represented by smooth projective toric varieties. A complete answer is given up to dimension six, and a partial answer is described in dimension eight. In addition, the role of smooth projective toric varieties in the polynomial ring structure of complex cobordism is examined. More specifically, smooth projective toric varieties are constructed as polynomial ring generators in most dimensions, and evidence is presented suggesting that a smooth projective toric variety can be chosen as a polynomial generator in every dimension. Finally, toric varieties with an additional fiber bundle structure are used to study some manifolds in oriented cobordism. In particular, manifolds with certain fiber bundle structures are shown to all be cobordant to zero in the oriented cobordism ring.

The associahedron has been generalized to a great variety of combinatorial structures. In each example the convex polytope is found whose face poset is the same as a certain poset structure on the combinatorial structures. Here we find polytopes whose face poset models the containment order of certain order ideals of the face poset of a cell complex. This is progress in a program which asks which posets in general have their ideals modeled by convex polytopes.

When does a topological polyhedral complex (embedded in Rd) admit a geometric realization (a rectilinear embedding in Rd)? What are the constraints on the possible realizations? Two classic results concerning such questions are Fary's theorem, which states that every planar graph can be drawn in the plane such that each edge is a straight line segment, and Tutte's theorem, which provides necessary and sufficient conditions for embedding a planar graph such that all faces are convex. The present work is motivated largely by the question of whether these types of results generalize to higher dimensions.We begin by constructing an irrational polytopal complex consisting of 1278 convex 3-polytopes in R3. The methods of this construction may also be used to produce small topological complexes with no geometric realization, as well as geometric complexes which encode arbitrary point and line configurations. This allows us to prove universality theorems for 3-dimensional polytopal complexes and arrangements. We also investigate geometric realizations of plane triangulations, and describe an explicit algorithm that embeds a plane triangulation with n vertices in a 4n3 x 8n5 integer grid, in such a way that at each step of the algorithm, the resulting region of the plane is convex. This embedding, by nature of its sequential convexity, may be lifted vertically to a 3-polytope. This process gives a new proof of Steinitz's Theorem for triangulations, and provides a new upper bound on the size of the integer grid necessary to embed the vertices of simplicial 3-polytopes. For certain classes of triangulations, this grid size is subexponential.

The integer points of a high-dimensional polytope P are generally difficult to count or sample uniformly. We consider a class of low-complexity random models for these points which arise from an entropy maximization problem. From these models, by way of "anti-concentration" results for sums of independent random variables, we derive general, efficiently computable upper bounds on the number of integer points of P. We make a detailed study of contingency tables with bounded entries, which are the integer points of a transportation polytope truncated by a cuboid. We provide efficiently computable estimates for the logarithm of the number of m by n tables with specified row and column sums r_1, ..., r_m, c_1, ..., c_n and bounds on the entries. These estimates are asymptotic as m and n go to infinity simultaneously, given that no r_i (resp., c_j) is allowed to exceed a fixed multiple of the average row sum (resp., column sum). As an application, we consider a random, uniformly selected table with entries in {0, 1, ..., kappa} having a given sum. Responding to questions raised by Diaconis and Efron in the context of statistical significance testing, we show that the occurrence of row sums r_1, ..., r_m is positively correlated with the occurrence of column sums c_1, ..., c_n when kappa > 1 and r_1, ..., r_m, c_1, ..., c_n are sufficiently extreme. We give evidence that the opposite is true for near-average values of r_1, ..., r_m, c_1, ..., c_n.

We study generalized permutohedra and some of the geometric properties they exhibit. We decompose matroid polytopes (and several related polytopes) into signed Minkowski sums of simplices and compute their volumes. We define the associahedron and multiplihedron in terms of trees and show them to be generalized permutohedra. We also generalize the multiplihedron to a broader class of generalized permutohedra, and describe their face lattices, vertices, and volumes. A family of interesting polynomials that we call composition polynomials arises from the study of multiplihedra, and we analyze several of their surprising properties. Finally, we look at generalized permutohedra of different root systems and study the Minkowski sums of faces of the crosspolytope.

We investigate the mean and median values of the support functions (called the mean or median radius) for a wide class of permutation and other polytopes. In particular, we calculate or estimate the asymptotic mean radius for the Birkhoff Polytope, Asymmetric Traveling Salesman Polytope, Symmetric Matching Polytope, and the Symmetric Traveling Salesman Polytope, as the number of vertices (in the corresponding graphs) n approaches $\infty.$ We also link the notion of mean value of the support function over a sphere with that of vertex counting, proving a nontrivial lower bound for the mean value as a function of the number of vertices. We also relate two concepts of averaging and show examples of each.