Discrete CATS Seminar
Department of Mathematics
University of Kentucky

Spring 2021

February 1 Discrete Math Faculty (University of Kentucky)
Title: Open House

Abstract: The research group open house for the discrete math group will be held during the first meeting of the discrete math seminar.

February 8 Thomas McConville (Kennesaw State University)
Title: Determinantal Formulas with Major Indices

Abstract: Krattenthaler and Thibon discovered a beautiful formula for the determinant of the matrix indexed by permutations whose entries are q^maj( u*v^{-1} ), where "maj" is the major index. Previous proofs of this identity have applied the theory of nonsymmetric functions or the representation theory of the Tits algebra to determine the eigenvalues of the matrix. I will present a new, more elementary proof of the determinantal formula. Then I will explain how we used this method to prove several conjectures by Krattenthaler for variations of the major index over signed permutations and colored permutations. This is based on joint work with Donald Robertson and Clifford Smyth.

February 15 Ruriko Yoshida (Naval Postgraduate School)
Title: Tropical Support Vector Machines

Abstract: Support Vector Machines (SVMs) are one of the most popular supervised learning models to classify using a hyperplane in an Euclidean space. Similar to SVMs, tropical SVMs classify data points using a tropical hyperplane under the tropical metric with the max-plus algebra. In this talk, first we show generalization error bounds of tropical SVMs over the tropical projective space. While the generalization error bounds attained via VC dimensions in a distribution-free manner still depend on the dimension, we also show theoretically by extreme value statistics that the tropical SVMs for classifying data points from two Gaussian distributions as well as empirical data sets of different neuron types are fairly robust against the curse of dimensionality. Extreme value statistics also underlie the anomalous scaling behaviors of the tropical distance between random vectors with additional noise dimensions. This is joint work with M. Takamori, H. Matsumoto and K. Miura.

February 22 Amzi Jeffs (University of Washington)
Title: The Geometry and Combinatorics of Convex Union Representable Complexes

Abstract: The study of convex neural codes seeks to classify the intersection and covering patterns of convex sets in Euclidean space. A specific instance of this is to classify "convex union representable" (CUR) complexes: the simplicial complexes that arise as the nerve of a collection of convex sets whose union is convex. In 2018 Chen, Frick, and Shiu showed that CUR complexes are always collapsible, and asked if the converse holds: is every collapsible complex also CUR? We will provide a negative answer to this question, and more generally describe the combinatorial consequences arising from the geometric representations of CUR complexes. This talk is based on joint work with Isabella Novik.

March 1 Emily Barnard (DePaul University)
Title: Pairwise Completability for 2-Simple Minded Collections

Abstract: Let Lambda be a basic, finite dimensional algebra over an arbitrary field, and let mod(Lambda) be the category of finitely generated right modules over Lambda. A 2-term simple minded collection is a special set of modules that generate the bounded derived category for mod(Lambda). In this talk we describe how 2-term simple minded collections are related to finite semidistributive lattices, and we show how to model 2-term simple minded collections for the preprojective algebra of type A.

March 8 Fu Liu (UC Davis)
Title: Permuto-associahedra as deformations of nested permutohedra

Abstract: A classic problem connecting algebraic and geometric combinatorics is the realization problem: given a poset (with a reasonable structure), determine whether there exists a polytope whose face lattice is the poset. In the 1990s, Kapranov defined a poset, called the permuto-associhedron, as a hybrid between the face poset of the permutohedron and the associahedron, and he asked whether this poset is realizable. Shortly after his question was posed, Reiner and Ziegler provided a realization. In this talk, I will discuss a different construction we obtained as a deformations of nested permutohedra. This is joint work with Federico Castillo.

March 15 Katharina Jochemko (KTH Royal Institute of Technology)
Title:Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity

Abstract: Generalized permutahedra form a combinatorially rich class of polytopes that appear naturally in various areas of mathematics. They include many interesting and significant classes of polytopes such as matroid polytopes. We study functions on generalized permutahedra that behave linearly with respect to dilation and taking Minkowski sums. We present classification results and discuss how these can be applied to prove positivity of the linear coefficient of the Ehrhart polynomial of generalized permutahedra. This is joint work with Mohan Ravichandran.

March 22 John Machacek (Hampden-Sydney College)
Title: Shelling the m=1 Amplituhedron

Abstract: The amplituhedron is a topological space related to the totally nonnegative Grassmannian that was inspired by high energy physics. In this talk we will apply combinatorics and poset topology to analyze a special case known as the m=1 amplituhedron. There is a poset of sign vectors which is the closure poset of the m=1 amplituhedron, and we show this poset has an EL shelling. This implies the m=1 amplituhedron is a ball. We also show this poset is strongly Sperner.

March 29 Michael Joseph (Dalton State College)
Title: The Lalanne--Kreweras Involution, Rowmotion, and Birational Liftings

Abstract: Our work ties together a few different actions studied in combinatorics. First, The Lalanne--Kreweras involution (LK) on Dyck paths yields a bijective proof of the symmetry of two statistics: the number of valleys and the major index. Panyushev studied an equivalent involution can be considered on the set of antichains of the type A root poset. Second, we will discuss the action of rowmotion on the set of antichains of a poset. This action, which sends an antichain A to the minimal elements of the complement of the order ideal generated by A, has received significant attention recently in dynamical algebraic combinatorics due to various phenomena (e.g. periodicity, cyclic sieving, homomesy) on certain "nice" posets including root posets. The LK involution and rowmotion are connected in that they generate a dihedral action on the set of antichains of the type A root poset. Furthermore, the periodicity of rowmotion on the type A root poset lifts to a generalization called "birational rowmotion" first studied by David Einstein and James Propp. This motivated us to search for a birational lifting of the LK involution, where we discovered that the key properties of the LK involution are also satisfied in this generalization. This is joint work with Sam Hopkins.

April 5 Avery St. Dizier (University of Illinois at Urbana Champaign)
Title: Log-Concavity of Littlewood-Richardson Coefficients

Abstract: Schur polynomials and Littlewood-Richardson numbers are classical objects arising in symmetric function theory, representation theory, and the cohomology of the Grassmannian. I will give a quick introduction to them, and then describe a new log-concavity property of the Littlewood-Richardson numbers. I will then explain the mechanism behind the log-concavity, Brändén and Huh's theory of Lorentzian polynomials.

April 12 Darleen Perez-Lavin (University of Kentucky)
Title: Recurrence Relations of Linear Tilings

Abstract: Let U ⊆ ℕ and let T be a linear tiling of a 1 x n board using 1 x i polyomino tiles where u is in U. We define T_U(n) to be the set of linear tilings of length n using tile sizes in U. Classically, when U = { 1, 2} these tilings are known as the Lucanomial tilings and they follow the Lucas sequence. Now, let U and V be distinct subsets of the natural numbers. In this talk, we will provide some general results and supportive examples of a large family of linear recurrence relations between the sequences T_U(n) and T_V(n) for fixed sets U and V. This is joint work with Christopher O'Neill and Pamela E. Harris.

April 19 Hudson Lafayette (Virginia Commonwealth University)
Title: Coloring (P5, gem)-free Graphs with Δ-1 Colors

Abstract: The Borodin--Kostochka Conjecture states that for a graph G, if Δ(G) ≥ 9 and ω(G) ≤ Δ(G)-1, then χ(G) ≤ Δ(G)-1. This conjecture is a strengthening of Brooks' Theorem and while known for certain graph classes it remains open for general graphs. In this talk we prove the Borodin--Kostochka Conjecture for (P5,gem)-free graphs, i.e. graphs with no induced P5 and no induced K1 v P4.

April 26 Anastasia Chavez (UC Davis)
Title:Characterizing Quotients of Positroids

Abstract: We characterize quotients of specific families of positroids. Positroids are a special class of representable matroids introduced by Postnikov in the study of the nonnegative part of the Grassmannian. Postnikov defined several combinatorial objects that index positroids. In this talk, we make use of one of these objects called a decorated permutation to combinatorially characterize when certain positroids form quotients. Furthermore, we conjecture a general rule for quotients among arbitrary positroids on the same ground set. This is joint work with Carolina Benedetti and Daniel Tamayo.

May 3 William Gustafson (University of Kentucky)
Title: Lattice minors and Eulerian posets

Abstract: We define a notion of deletion and contraction for lattices. The result of a sequence of deletions and contractions is called a minor of the original lattice. The name minors is justified by the fact that the minors of the lattice of flats of a graph correspond to the simple minors of the graph when the vertices are labeled (and the edges unlabeled). For each finite lattice we define a poset of minors and show it is Eulerian and a PL sphere. We also obtain some inequalities for the cd-indices of these posets of minors.


Fall 2020

August 31 Andrés R. Vindas Meléndez (University of Kentucky)
Title: Decompositions of Ehrhart h*-polynomials for rational polytopes

Abstract: The Ehrhart quasipolynomial of a rational polytope P encodes the number of integer lattice points in dilates of P, and the h* -polynomial of P is the numerator of the accompanying generating function. We provide two decomposition formulas for the h*-polynomial of a rational polytope. The first decomposition generalizes a theorem of Betke and McMullen for lattice polytopes. We use our rational Betke--McMullen formula to provide a novel proof of Stanley's Monotonicity Theorem for the h*-polynomial of a rational polytope. The second decomposition generalizes a result of Stapledon, which we use to provide rational extensions of the Stanley and Hibi inequalities satisfied by the coefficients of the h*-polynomial for lattice polytopes. Lastly, we apply our results to rational polytopes containing the origin whose duals are lattice polytopes. This is joint work with Matthias Beck (San Francisco State Univ. & FU Berlin) and Ben Braun (Univ. of Kentucky).

September 7 Noah Speeter (University of Kentucky)
Title: Chip firings and the Scramble Number

Abstract: Chip firing can be described as a game we play by placing poker chips on the vertices of a graph. The scramble number is a new graph invariant that helps inform us as to how many chips we need to "win" that game. We will explore the properties of the scramble number as well as techniques used to compute it. This is joint work with Dave Jensen.

September 14 Mario Sanchez (UC Berkeley)
Title: The Universal Valuation of Coxeter Matroids

Abstract: Valuations on a family of polytopes are functions which behave nicely with respect to subdivisions in this family. One important question is the determine the structure of the set of all valuations on a certain family. This can be done by constructing a "universal valuation" which is a valuation that can be specialized to any other valuation on this family. Coxeter matroids are a generalization of matroids to an arbitrary root system. As with usual matroids, we can interpret Coxeter matroids as polytopes. In this talk, we will construct a universal valuation for the family of Coxeter matroid polytopes.

September 21 Emine Yildirim (Queens University)
Title: The Coxeter Transformation and Rowmotion for Cominuscule Posets

Abstract: There is a combinatorial action, called the Rowmotion, defined on cominuscule posets. It is well-known that this action has order 'h' on the order ideal poset of a cominuscule poset where h is the Coxeter number of the corresponding root system. Also, we will talk about the action of the Coxeter transformation on the order ideals of cominuscule posets. We prove that the Coxeter transformation is periodic of order 'h+1' (up to a sign) in most cases. We will demonstrate combinatorial similarities of the orbits of these two actions.

September 28 Gábor Hetyei (University of North Carolina - Charlotte)
Title: Rational Links Represented by Reduced Alternating Diagrams

Abstract: In knot theory, a rational link may be represented by any of the (infinitely) many link diagrams corresponding to various continued fraction expansions of the same rational number. The continued fraction expansion of the rational number in which all signs are the same is called a nonalternating form and the diagram corresponding to it is a reduced alternating link diagram, which is minimum in terms of the number of crossings in the diagram. Famous formulas exist in the literature for the braid index of a rational link by Murasugi and for its HOMFLY polynomial by Lickorish and Millet, but these rely on a special continued fraction expansion of the rational number in which all partial denominators are even (called all-even form}). In this talk we present an algorithmic way to transform a continued fraction given in nonalternating form into the all-even form. Using this method we derive formulas for the braid index and the HOMFLY polynomial of a rational link in terms of its reduced alternating form, or equivalently the nonalternating form of the corresponding rational number. This is joint work with Yuanan Diao and Claus Ernst. The talk will define and explain all terms, with a general audience in mind.

October 5 Véronique Bazier-Matte (University of Connecticut)
Title: Quasi-cluster algebras and triangulations of the Möbius strip

Abstract: In this talk, we will first define triangulations of marked surfaces, then use it to define quasi-cluster algebras (the equivalent of cluster algebras for non-orientable surfaces). We will list a few properties of these algebras, then we will count the number of triangulations of the Möbius strip, the only surface with a finite number of triangulations.

October 12 Greg Muller (University of Oklahoma)
Title: Linear recurrences indexed by Z

Abstract: We consider a system of equations in variables indexed by the integers, in which each variable is equal to a linear combination of the previous variables. We will show a number of general results about these systems, including an analog of Gaussian elimination, a parametrization of solutions, and (time-permitting) a characterization of systems whose solutions are periodic.

October 19 Ayomikun Adeniran (Pomona College)
Title: Increasing and Invariant Parking Sequences

Abstract: The notion of parking sequences is a new generalization of parking functions introduced by Ehrenborg and Happ. In the parking process defining the classical parking functions, instead of each car only taking one parking space, the cars are allowed to have different sizes and each takes up a number of adjacent parking spaces after a trailer that was parked at the start of the street. A preference sequence in which all the cars are able to park is called a parking sequence. In this talk, we will look at increasing parking sequences and their connections to lattice paths. We will also discuss two notions of invariance in parking sequences and present various characterizations and enumerative results. This is joint work with Catherine Yan.

October 26 Liam Solus (KTH Royal Institute of Technology)
Title: Some Recent Applications of Real-rooted Polynomials

Abstract: In enumerative, geometric, algebraic and topological combinatorics the inequalities that hold amongst the coefficients of a combinatorial generating polynomial are frequently studied. Typical questions ask whether or not the coefficient sequence is unimodal, log-concave, alternatingly increasing and/or gamma-nonnegative. We will discuss some recent results that rely on the real zeros of polynomials to give answers to questions of this type. The main applications will pertain to polytopal cell complexes and lattice polytopes. Aside from giving answers, we will also pose some new problems motivated by these results.

November 2 Sara Billey (University of Washington)
Title: Limit Laws for q-Hook Formulas

Abstract: Various asymptotic aspects of the Hook Length Formula for standard Young tableaux have been studied recently in combinatorics and probability. In this talk, we study the limiting distributions that come from random variables associated to Stanley's q-hook-content formula for semistandard tableaux and q-hook length formulas of Björner--Wachs related to linear extensions of labeled forests. We show that, while these limiting distributions are "generically" asymptotically normal, there are uncountably many non-normal limit laws. More precisely, we introduce and completely describe the compact closure of the moduli space of distributions of these statistics in several regimes. The additional limit distributions involve generalized uniform sum distributions which are topologically parameterized by certain decreasing sequence spaces with bounded 2-norm. The closure of the moduli space of these distributions in the Lévy metric gives rise to the moduli space of DUSTPAN distributions. As an application, we completely classify the limiting distributions of the size statistic on plane partitions fitting in a box. This talk is based on joint work with Joshua Swanson at UCSD.

November 9 Richard Ehrenborg (University of Kentucky)
Title: Three Combinatorial Applications

Abstract: This is not one seminar talk. This is three small seminars. First, we prove a geometric result of Dirichlet using combinatorics. Second, as an application of posets we obtain Sylvester's two coin result. Finally, we present a counting proof when 2 is a quadratic residue in a finite field. The third topic is joint work with Frits Beukers and Karthik Chandrasekhar.

November 16 Carolina Benedetti (Universidad de los Andes)
Title: Quotients of Lattice Path Matroids

Abstract: Matroids are a combinatorial object that generalize the notion of linear independence. One way to characterize matroids is via polytopes, as shown in the work of Gelfand, Goresky, MacPherson, Serganova. In this talk we will focus on a particular class of matroids called Lattice Path Matroids (LPMs). We will show when a collection M_1,...,M_k of LPMs are a flag matroid, using their combinatorics. Part of our work will show that the polytope associated to such a flag can be thought as an interval in the Bruhat order, and thus provides a partial understanding of flags of LPMs from a polytopal point of view. We will not assume previous knowledge on matroids nor quotients. This is joint work with Kolja Knauer.