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.

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.

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.

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. 

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.

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.

Title: Boundary Algebras of Positroids

Abstract: Positroid varieties are subvarieties of the Grassmannian defined by requiring the vanishing and nonvanishing of certain maximal minors. Positroid varieties are known to have a cluster structure which is categorified by the Gorenstein-projective module category over the completed boundary algebra of the associated dimer model. I will talk about positroid combinatorics and describe the boundary algebras which arise from arbitrary connected positroids.

Abstract: Over 50 years ago, Victor Kac and Robert Moody introduced Kac-Moody algebras as a natural extension of the already classified semisimple Lie algebras. There are three types of Kac-Moody algebras: finite, affine, and indefinite. Both finite and affine have had all root multiplicities calculated. Some partial results have been obtained in the indefinite case, but the root multiplicities are not completely known. In this work, we realize the indefinite Kac-Moody algebras HE_7^(1)and HE_8^(1) as minimal graded Lie algebras whose local part is V\oplus gl(n;C)\oplus V' where V and V' are suitably chosen gl(n)-modules. This will allow us to use the combinatorial Kang's multiplicity formula to compute the root multiplicities to level 7 in the case of  HE_7^(1) and level 9 in the case of HE_8^(1). Additionally, we verify the counterexample to Frenkel's conjecture for HE_8^(1) found by Kac, Moody, and Wakimoto by computing the relevant root multiplicity and we provide a root whose multiplicity is a counterexample to Frenkel's conjecture for HE_7^(1) , showing that Frenkel's conjecture does not hold for HE_7^(1) .

This is a joint work with Kailash Misra.

Title: Equitable Facility Location

Abstract: Facility location is one of the most common applications of combinatorial optimization. Models that minimize the mean distance between a “customer” and their assigned facility behave well computationally and make sense from a modeling perspective in many contexts. However, if equity is a concern, the mean is not an ideal metric. Many equitable facility location models have been developed in the literature, but they tend not to scale well computationally because nonlinear optimization models with integer variables are very hard to solve. Historically applied to incomes, equally distributed equivalents (EDEs) provide more accurate measures of the experience of a population than the population mean by penalizing values on the “bad” end of the distribution; i.e., very low incomes pull the EDE below the mean.  We develop a computationally scalable facility location model that minimizes the Kolm-Pollak EDE, a metric that is applied in the Environmental Justice literature to compare exposure to environmental harms, such as air pollution, across demographic groups. We apply our methods to food deserts and election polling locations, demonstrating that optimizing over the Kolm-Pollak EDE, rather than the mean, can lead to big gains in equity while still resulting in near-optimal average distances.