U N I V E R S I T Y   OF   K E N T U C K Y
D I S C R E T E   C A T S   S E M I N A R 

Feb 17

Richard Ehrenborg

University of Kentucky

The graph polytope of a cycle

We present one of my favorite polytopes: the subset in the first orthant such that the sum of two cyclically adjacent coordinates is less than or equal to 1.  We will discuss its volume, its Ehrhart polynomial, the volume again and its face polynomial.

March 3

DOUBLE HEADER!

2:00 - 2:20 pm:

Jim Propp

U Mass Lowell

The further advantures of Stanley's transfer map

Abstract:

In 1986 Stanley showed that the natural bijection between antichains and order ideals of a poset P gives rise to a well-behaved continuous piecewise-linear map from the order polytope of P to a new polytope he called the chain polytope of P.  I’ll describe several directions in which this map has been generalized and also discuss the role these newer maps have played in dynamical algebraic combinatorics.

Talk 

2:20 - 2:53 pm:

Sara Billey

University of Washington 

Brewing Fubini-Bruhat partial orders with ASMs

Abstract:

Fubini words (also known as Cayley permutations, packed words, and surjective words) are generalized permutations, allowing for repeated letters, and they are in one-to-one correspondence with ordered set partitions.  Brendan Pawlowski and Brendon Rhoades extended permutation matrices to pattern matrices for Fubini words.  Under a lower triangular action, these pattern matrices produce cells in projective space, specifically (Pk−1)n.  The containment of the cell closures in the Zariski topology gives rise to a poset which generalizes the Bruhat order for permutations. Unlike Bruhat order, containment is not equivalent to intersection of a cell with the closure of another cell. This allows for a refinement of the poset. 

It is additionally possible to define a weaker order, giving rise to a subposet containing all the elements. We call these orders, in order of decreasing strength, the espresso, medium roast, and decaf Fubini-Bruhat orders. The espresso and medium roast orders are not ranked in general. The decaf order is ranked by codimension of the corresponding cells. In fact, the decaf order has rank generating function given by a well-known q-analog of the Stirling numbers of the second kind.

In this paper, we give increasingly smaller sets of equations describing the cell closures, which lead to several different combinatorial descriptions for the relations in all three orders. Studying these partial orders and their associated rank functions has lead to generalizations of Fulton’s essential set and alternating sign matrices.

This talk is based on joint work with Stark Ryan and Matjaz Konvalinka.

Talk 

March 10

Einar Steingrímsson

University of Strathclyde

Permutation statistics, patterns and moment sequences

Which combinatorial sequences correspond to moments of probability measures on the real line?  We present two large classes of such sequences, where for one of the classes we prove these to be moment sequences, and conjecture it for the other class.

This is joint work with Natasha Blitvić and Slim Kammoun.

Talk 

March 24

Memories of Adriano Garsia

We will show mathematical highlights of mathematical work of Adriano Garsia from a recent memorial ceremony.

Talk

March 31

No meeting

April 14

Ford McElroy

University of Kentucky

PhD Defense (in CP 111:  Note location)

Two Network Flow Problems: Volume Inequalities for Flow Polytopes of Full Directed Acyclic Graphs; Optimal Additions to the Low-Stress Bike Network in Lexington, Kentucky

We address two distinct problems related by their foundation in network flow.

The first problem concerns volumes of flow polytopes of directed acyclic graphs. Given a finite directed acyclic graph, the space of non-negative unit flows is a lattice polytope called the flow polytope of the graph. We consider the volumes of flow polytopes for directed acyclic graphs on n+1 vertices with a fixed out-degree sequence (3,2,...,2,0). We prove that there is an interchange operation on the edge set of these graphs that induces a partial order on the graphs isomorphic to a Boolean algebra. Further, we prove that as we move up through this partial order, the volumes of the corresponding flow polytopes weakly decrease. 

The second problem develops a discrete optimization model for Lexington, Kentucky's bicycle network. Riding bikes is a crucial piece of a larger transportation sustainability puzzle. In cities with car-prioritizing infrastructure, like Lexington, choosing bike routes that feel safe can involve considerable detours. Fortunately, many cities have begun retrofitting car-centric infrastructure with more bike-friendly features. The optimization model we produce gives a potential answer to the question ``What are the best roads on which to build bike-friendly infrastructure to minimize the amount of safety-detouring?''

April 21

Pablo Castilla

University of Kentucky

Masters Exam

The Volume Metric for Cutting Planes from Gomory’s Group Relaxation

Cutting-plane methods are an approach to solving integer and mixed-integer linear programs by introducing additional linear constraints. In 2018, Basu, Conforti, Di Summa, and Zambelli discussed cutoff volume as the metric for evaluating the strength of a cut and proved that the well-studied Gomory Mixed-Integer (GMI) cut maximizes this metric. In this talk, we first present background on cutting planes, cut-generating functions, and Gomory’s master group, a fundamental mathematical object in integer programming. Then, we describe cutoff volume as a metric for evaluating the strength of a cut and extend the volume metric to the infinite-dimensional case. Finally, we present the proof that the GMI cut maximizes the volume metric and is the unique maximizer in the finite group setting.