Title: P-partitions Revisited

Abstract: We will be discussing the paper P-partitions Revisited, which attempts, for a given poset P, to connect algebraic invariants of the ring of P-partitions to the structure of P itself, i.e., gives a partial answer to the question: What poset properties survive the process of "algebrizing", and in what form?  We will introduce the relevant objects (Linear extensions, P-partition rings, Hilbert Series), and give sketches of their constructions and the relationships between them. 

Discrete CATS Seminar

Monday, October 31, 2016

2PM, POT 745

Speaker: Federico Ardila, San Francisco State University

Title: The algebraic and combinatorial structure of generalized permutahedra

Abstract: Generalized permutahedra are a beautiful family of polytopes which are known to have a rich combinatorial structure. We explore the Hopf algebraic structure of this family, and use it to unify old results, prove new results, and answer open questions about families of interest such as graphs, matroids, posets, trees, set partitions, hypergraphs, and simplicial complexes. As a corollary, we obtain a new polyhedral approach for computing the multiplicative and compositional inverses of a power series.  The talk is based on joint work with Marcelo Aguiar, and will assume no previous knowledge of Hopf algebras or generalized permutahedra.

Title: Properties of s-lecture hall polytopes

Abstract: Arising from the well-studied s-lecture hall partitions, we will discuss the s-lecture hall polytopes. In recent work, T. Hibi, A. Tsuchiya, and I were able to characterize algebraic and geometric properties for  s-lecture lecture hall polytopes, such as the Fano, reflexive, and Gorenstein properties as well as the integer decomposition property (IDP), for certain classes of s-sequences. We also make several conjectures. At the end of the talk, we will briefly discuss related polytopes, namely the partition polytope and the Gelfand–Tsetlin polytope, and recent work of P. Alexandersson which suggests that our conjectures may not be true.
 

Title: Excedance Algebra and box polynomials

Abstract: In this talk we will introduce the excedance algebra and a related sequence of polynomials known as the box polynomials. We will prove recurrence relations for the polynomials and characterize their roots. We will end the talk by showing the box polynomials can also be defined in terms of delta operators.
 

Title:  Independence Complexes, Matching Trees, and Discrete Morse Theory

Abstract:  An independent set in a combinatorial graph is a subset of vertices that are pairwise non-adjacent.  Since set independence is preserved under deletion of elements, we can construct a simplicial complex from the independent sets of a graph of interest.  In this talk, we will survey some of the tools from discrete Morse theory that are useful for analyzing these so-called independence complexes.  We will also discuss some recent results pertaining to the independence complex of small grid graphs including, but not limited to, a particular algorithm giving cell-counting recursions that connect back to some interesting combinatorial sequences.

Title: Ehrhart polynomials with negative coefficients

Abstract: The Ehrhart polynomials of integral convex polytopes count integer points under dilations of the polytopes. In this talk, I will discuss the possible sign patterns of the coefficients of Ehrhart polynomials of integral convex polytopes. While the leading terms, the second leading terms and the constant of Ehrhart polynomials are always positive, the other terms aren't necessarily positive.  In fact, some examples of Ehrhart polynomials with negative coefficients were known before. For arbitrary dimension, I will describe a construction of Ehrhart polynomials with negative coefficients. 

Title: Polyhedral Problems in Combinatorial Convex Geometry

Abstract: Polyhedra play a special role in combinatorial convex geometry in the sense that they are both convex sets and combinatorial objects.  As such, a polyhedron can act as either the convex set of interest or the combinatorial object describing properties of another convex set.  We will examine two instances of polyhedra in combinatorial convex geometry, one exhibiting each of these two roles.  The first instance arises in the context of Ehrhart theory, and the polyhedra are the central objects of study.  We will examine the Ehrhart h*-polynomials of a family of lattice polytopes called the r-stable (n,k)-hypersimplices, providing some combinatorial interpretations of their coefficients as well as some results on unimodality of these polynomials.  The second instance arises in algebraic statistics, and the polyhedra act as a conduit through which we study a nonpolyhedral problem.  For a graph G, we study the extremal ranks of the closure of the cone of concentration matrices of G via the facet-normals of the cut polytope of G.  Along the way, we will discover that real-rooted polynomials are lurking in the background of all of these problems.  

Kristen will discuss some old and new combinatorial games in this presentation for her qualifying exam.

Title:  Deletion-Induced Triangulations

Abstract:   Let $d > 0$ be  a fixed integer and let $\A \subseteq \mathbb{R}^d$ be a collection of $n \geq d+2$ points which we lift into $\mathbb{R}^{d+1}$. Further let $k$ be an integer satisfying $0 \leq k \leq n-(d+2)$ and assign to each $k$-subset of the points of $\A$ a (regular) triangulation obtained by deleting the specified $k$-subset and projecting down the lower hull of the convex hull of the resulting lifting. Next, for each triangulation we form the characteristic vector outlined by Gelfand, Kapranov, and Zelevinsky by assigning to each vertex the sum of the volumes of all adjacent simplices. We then form a vector for the lifting, which we call the compound GKZ-vector, by summing all the characteristic vectors. Lastly, we construct a polytope $\Sigma_k(\A) \subseteq \mathbb{R}^{| \A |}$ by taking the convex hull of all obtainable compound GKZ-vectors by various liftings of $\A$, and note that $\Sigma_0(\A)$ is the well-studied secondary polytope corresponding to $\A$. We will see that by varying $k$, we obtain a family of polytopes with interesting properties relating to Minkowski sums, Gale transforms, and Lawrence constructions, with the member of the family with maximal $k$ corresponding to a zonotope studied by Billera, Fillamen, and Sturmfels. We will also discuss the case $k=d=1$, in which we can outline a combinatorial description of the vertices allowing us to better understand the graph of the polytope and to obtain formulas for the numbers of vertices and edges present.