DISCRETE CATS SEMINAR

Discrete CATS Seminar: Margaret Readdy

Speaker:  Margaret A. Readdy, University of Kentucky

Title:         The Pizza Theorem

 

Abstract:

The Pizza Theorem is a classical result in fair division: if one cuts a disk by an even number of equally-spaced lines through any point in the disk, where there are at least four lines, then the alternating sum of the areas of the slices equals zero.  We extend the Pizza Theorem to translates of convex bodies in n dimensions that contain the origin and are stable under a given Coxeter group.  We also give stronger results for the case of a ball in n dimensions. Using Herb’s theory of 2-structures, we derive a dissection proof and extensions to all intrinsic volumes.


 

This is joint work with Richard Ehrenborg and Sophie Morel.

Date:
Location:
745 POT

Discrete Seminar

Title: Branch-and-bound for D-Optimality with fast local search and variable-bound tightening
 

Abstract:  We develop a branch-and-bound algorithm for the D-optimality problem (D-opt), a central problem in statistical design theory, based on two bounds derived from convex relaxations, the "natural bound'' and the "Γ-bound''. We describe a procedure to fix variables based on convex duality. We demonstrate that the Γ-bound for the binary version of D-opt with a particular variable fixing is precisely the "complementary Γ-bound'' for the so-called "Data-Fusion problem''. Further, we present theoretical results showing some relations between different bounds. We propose local-search heuristics for D-opt and analyze different strategies to compute search directions and step sizes for each iteration of them. Finally, we present numerical experiments concerning a B&B algorithm based on our results. This is a joint work with Jon Lee and Gabriel Ponte.

Date:
-
Location:
POT 745
Event Series:

Discrete Seminar

Title: Combinatorics of Conway-Coxeter Friezes and SL_k-Tilings

Abstract:  In 1973, Conway and Coxeter published an article which introduced objects called friezes. In it they detailed several structural properties of these objects, including a bijection to triangulations of polygons. In more recent years, these Conway-Coxeter friezes and their higher-dimensional analogues known as SL_k-tilings have been studied due to their relation to cluster algebras.  Tilings are arrays of integers whose adjacent submatrices have determinant 1.  In the case of SL_2-tilings, there is a bijection to paths in the Farey Graph.  We prove that for higher k there is a bijection to certain sequences of k-vectors.

Date:
-
Location:
POT 745
Event Series:

Discrete Seminar

Title: Framing lattices and flow polytopes

Abstract: In this talk we introduce a vast new family of lattices which we call "framing lattices". They arise from directed acyclic graphs and encompass many combinatorially interesting lattices, including the Boolean lattice, the Tamari lattice, type A cambrian lattices, the weak order of the symmetric group, along with many of their recent generalizations. Framing lattices are also intimately tied to the geometry of triangulated flow polytopes. We will discuss this geometric connection along with known structural results regarding framing lattices. Many examples will be explored throughout the talk. This talk is based on joint work with Cesar Ceballos.

Date:
-
Location:
POT 745
Event Series:

Discrete Seminar

Title: Generalized Parking Function Polytopes
 
Abstract: A classical parking function of length n is a list of positive integers (a_1, a_2, ... , a_n) whose nondecreasing rearrangement b_1 \leq b_2 \leq ... \leq b_n satisfies b_i \leq i. The convex hull of all parking functions of length n is an n-dimensional polytope in R^n, which we refer to as the classical parking function polytope. Its geometric properties have been explored in (Amanbayeva and Wang 2022) in response to a question posed in (Stanley 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of x-parking functions, which we refer to as x-parking function polytopes. When x=(a,b, ... ,b), we make connections between these x-parking function polytopes, the Pitman-Stanley polytope, and  the partial permutahedra of (Heuer and Striker 2022). In particular, we establish a closed-form expression for the volume of x-parking function polytopes. This allows us to answer a conjecture of (Behrend et al. 2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary. If there is time, progress on an extension to general x will be presented. 
Date:
-
Location:
POT 745
Event Series:

Discrete Seminar

Title: Wilting Theory of Flow Polytopes

Abstract: Given a framed directed acyclic graph (DAG), we consider the DKK graph whose vertices are the maximal cliques of pairwise coherent routes and whose edges connect cliques which differ by only one route. Given a set of edges marked as “wilted,” we study the maximal cliques which avoid all wilted arrows. We define a class of framed DAGs whose DKK graphs may be realized as intervals in the DKK lattice of an amply framed DAG and we obtain interesting decompositions of the DKK graph of a general framed DAG. In particular, we may realize decompositions of the Tamari lattice into nu-Tamari intervals in this way.
Date:
-
Location:
POT 745
Event Series:

Discrete Seminar

Title: Protection Statistics in Rooted Trees

Abstract: For the first part of the talk, we will look at different classes of unlabeled simply generated rooted trees and study the asymptotic behavior of statistics which relate to the distance of vertices to the fringe: rank, height, and balance. I will focus on some general results on balanced trees using analytic techniques. Time permitting, I will also give a combinatorial proof of a recent result by Bona: the number of neighbors of leaves in increasing trees of size n is equal to the number of permutations of [n] with no fixed points. This talk is based on my doctoral thesis.

Date:
-
Location:
POT 745
Event Series:
Subscribe to DISCRETE CATS SEMINAR