University of Kentucky Discrete CATS Seminar
U N I V E R S I T Y   O F   K E N T U C K Y


2018 -- 2019

Fall 2018

Unless otherwise noted, seminar meets at 2:00 pm Mondays in 745 POT.

Sept 10 Richard Ehrenborg
University of Kentucky
Uniform flag triangulations of the Legendre polytope (or how I spent my summer holiday)

The Legendre polytope, also known as the full root polytope of type A, is the convex hull of all pairwise differences of the basis vectors. We describe all flag triangulations of this polytope that are uniform, that is, the edges are described in terms of the relative order of the indices of the four basis vectors involved. We obtain three classes of triangulations: the lex class, the revlex class and the Simion class. We also do a refined enumeration of faces of these triangulations that keeps track of the number of forward and backward arrows, and surprisingly the enumeration result only depends on which class the triangulation belongs to.

Joint work with Gabor Hetyei and Margaret Readdy.

Sept 17 Margaret Readdy
University of Kentucky
Combinatorial identities related to the calculation of the cohomology of Siegel modular varieties

In the computation of the intersection cohomology of Shimura varieties, or of the L2 cohomology of equal rank locally symmetric spaces, combinatorial identities involving averaged discrete series characters of real reductive groups play a large technical role. These identities can become very complicated and are not always well-understood. We propose a geometric approach to these identities in the case of Siegel modular varieties using the combinatorial properties of the Coxeter complex of the symmetric group

Joint work with Richard Ehrenborg and Sophie Morel.

Oct 1 Ben Braun
University of Kentucky
Graph constructions and chromatic numbers
We will survey various graph constructions related to proper k-colorability. Possible topics for discussion include constructions of k-chromatic graphs due to Hajos, Ore, and Urquhart, constructions of graphs with high girth and high chromatic number due to Alon, Kostochka, Reiniger, West, and Zhu, and constructions of k-critical graphs with minimal possible number of edges due to Kostochka and Yancey.

Oct 8 Matthias Köppe
UC Davis
Normalized antics: Polyhedral computation in an irrational age
Classic polyhedra such as the dodecahedron have irrational coordinates. How do we compute with them if we need exact answers? In this hands-on lecture using the SageMath system, intended to be accessible to advanced undergraduate students, I explain how to compute with polyhedral representations and with real embedded algebraic number fields. I then report on an ongoing project with W. Bruns, V. Delecroix, and S. Gutsche to obtain an efficient implementation in Normaliz, integrated with SageMath, involving the existing software libraries ANTIC, arb, and FLINT.

Oct 15

Alex Chandler
NC State
Thin posets and homology theories
Inspired by Bar-Natan's description of Khovanov homology, we discuss thin posets and their capacity to support homology and cohomology theories which categorify rank-statistic generating functions. Additionally, we present two main applications. The first, a categorification of certain generalized Vandermonde determinants gotten from the Bruhat order on the symmetric group by applying a special TQFT to smoothings of torus link diagrams. The second is a broken circuit model for chromatic homology, categorifying Whitney's broken circuit theorem for the chromatic polynomial of graphs.

Oct 22 No meeting Robert Lang Origami workshop 2-5 pm

Oct 29 Ricky Liu
NC State
P-partition generating functions of naturally labeled posets
The P-partition generating function of a (naturally labeled) poset P is a quasisymmetric function enumerating order-preserving maps from P to the positive integers. We give several necessary and sufficient conditions for when two posets can have the same P-partition generating function. We also show that the P-partition generating function of a connected poset is an irreducible element of the ring of quasisymmetric functions. The proofs utilize the Hopf algebra structure of posets and quasisymmetric functions. This is joint work with Michael Weselcouch.

Nov 5 No meeting Hayden-Howard Lecture 4 pm

Nov 12 Yuan Zhou
U Kentucky
Integer optimization, cutting planes, and approximation theory
Cutting planes are the workhorses of numerical integer optimization. In my talk, I review the principles of the leading approach to solving integer linear optimization problems. I then introduce my research on the theory of general-purpose cutting planes. I end the talk with a recent result regarding the approximation theory of so-called cut-generating functions in a particular model, Gomory and Johnson's infinite group problem. Our approximation theorem has nice "injective" properties, which have implication on the relation between so-called finite group relaxations and the infinite group problem.

Nov 19 Fernando Shao
U Kentucky
Maximizing the number of solutions to a linear equation
When two numbers are added in base 10, what's the chance that a carry occurs? Questions like this motivates the study of maximizing/minimizing the number of solutions to a linear equation, such as x+y=z, with the variables lying in a set of given size N. Some of these questions are easy (i.e. challenge problems for high school students), but some others are hard (i.e. open). I will discuss problems from both categories. Based on joint work with P. Diaconis and K. Soundararajan.

Nov 26 Tefjol Pllaha
U Kentucky
Laplacian Simplices II: A Coding Theoretic Approach
This talk will be about Laplacian simplices, that is, simplices whose vertices are rows of the Laplacian matrix of a simple connected graph. We will focus on graphs and graph operations that yield reflexive Laplacian simplices. We spot such graphs by showing that the h*-vector of the simplex is symmetric. We use the same approach as Batyrev and Hofscheier by considering the fundamental parallelepiped lattice points as a finite abelian group. This is joint work with Marie Meyer.

Dec 3 Matias von Bell
U Kentucky
The ASMCRY(n) Polytope: An Interesting Face of the Alternating Sign Matrix Polytope
This talk showcases some of the work done by Karola Meszaros, Alejandro Morales, and Jessica Strikerin their 2015 paper titled ``On Flow Polytopes, Order Polytopes, and Certain Faces of the Alternating Sign Matrix Polytope". The alternating sign matrix polytope is the convex hull of alternating sign matrices. We will focus on one of its faces known as the Alternating Sign Matrix Chan-Robbins-Yuen polytope (ASMCRY(n)). It is part of a larger family: The ASM-CRY family of polytopes. After a discussion of flow- and order polytopes, we'll prove that the polytopes in the ASM-CRY family are both flow- and order polytopes. Then using Stanley's results for order polytopes, we show that ASMCRY(n) has Catalan many vertices, and its volume is the number of Standard Young Tableaux of staircase shape.

This is Matias von Bell's Masters Exam.

Dec 6 Susanna Lang
U Kentucky
Rational Catalan Numbers and Associahedra
Classical Catalan numbers are known to count over 200 combinatorial objects, including Dyck paths, noncrossing partitions, and vertices of the classical associahedra. In this talk we discuss a generalization of the classical Catalan numbers and their connection with a class of simplicial complexes known as rational associahedra. We show rational associahedra have many nice properties, in particular they are shellable. This talk follows the paper "Rational Associahedra and Noncrossing Partitions" by Armstrong, Rhoades, and Williams.

This is Susanna Lang's Masters exam.

Spring 2019

Jan 24 Discrete Math Job Candidate

Jan 29 Discrete Math Job Candidate

Feb 1 Discrete Math Job Candidate

Feb 25 McCabe Olsen
Ohio State
Signed Birkhoff polytopes and the orthant-lattice preservation property
Given a d-dimensional lattice polytope P, we say that P has the orthant-lattice preservation property (OLP) if the subpolytope obtained by restriction to any orthant is a lattice polytope. While this property feels somewhat contrived, it can actually be quite useful in verification of discrete geometric properties of P. In this talk, we will discuss a number of results for the existence of triangulation and the integer decomposition property for reflexive OLP polytopes. One such polytope which fits into the program is a type-B analogue of the Birkhoff polytope and its dual polytope, the investigation of which led to interest in this property. This is based on joint work with Florian Kohl (Aalto University).
Mar 7 Gabor Hetyei
UNC Charlotte
Alternation acyclic tournaments and the homogeneous Linial arrangement
We define a tournament to be alternation acyclic if it does not contain a cycle in which descents and ascents alternate. We show that these label the regions in a homogenized generalization of the Linial arrangement. Using a result by Athanasiadis, we show that these are counted by the median Genocchi numbers. By establishing a bijection with objects defined by Dumont, we show that alternation acyclic tournaments in which at least one ascent begins at each vertex, except for the largest one, are counted by the Genocchi numbers of the first kind. As an unexpected consequence, we obtain a simple model for the normalized median Genocchi numbers.
Mar 8 Galen Dorpalen-Barry
U Minnesota
Whitney Numbers for Cones
An arrangement of hyperplanes dissects space into connected components called chambers. A nonempty intersection of halfspaces from the arrangement will be called a cone. The number of chambers of the arrangement lying within the cone is counted by a theorem of Zaslavsky, as a sum of certain nonnegative integers that we will call the cone's "Whitney numbers of the 1st kind". For cones inside the reflection arrangement of type A (the braid arrangement), cones correspond to posets, chambers in the cone correspond to linear extensions of the poset, and these Whitney numbers refine the number of linear extensions. We present some basic facts about these Whitney numbers, and interpret them for two families of posets.

Seminar Archive

Richard Ehrenborg is the organizer of the Discrete CATS Seminar in Spring 2019. If you wish to be added to the seminar list or give a talk, please e-mail him at richard.ehrenborg (at)

We would like to thank Richard Ehrenborg (Simons Foundation Collaboration Grant 2016--2021), Margaret Readdy (Simons Foundation Collaboration Grant 2016--2021) and Martha Yip (Simons Foundation Collaboration Grant 2016--2021) who generously continue to support our speakers with their grants. The Discrete CATS seminar is partially supported by the University of Kentucky Department of Mathematics.

Last updated March 4, 2019.