Events - August 2023

Title: Chasing Positive Bodies

Abstract: We study the problem of chasing positive bodies in \ell_1: given a sequence of bodies K_t\subset R^n revealed online, where each K_t is defined by a mixed packing-covering linear program, the goal is to (approximately) maintain a point x_t \in K_t such that \sum_t \|x_t - x_{t-1}\|_1 is minimized. This captures the fully-dynamic low-recourse variant of any problem that can be expressed as a mixed packing-covering linear program and thus also the fractional version of many central problems in dynamic algorithms such as set cover, load balancing, hyperedge orientation, minimum spanning tree, and matching.

Title: From the Upper Bound Conjecture to Gorenstein linkage

Abstract: In 1957, Motzkin conjectured that the maximum number of faces possible for a polytope on n vertices in d-space is achieved by the convex hull of n points on the moment curve in d-space.  This conjecture, called the Upper Bound Conjecture, was proved by McMullen in 1970 and generalized by Stanley in 1975.  On the road to Stanley's proof, a correspondence between squarefree monomial ideals and simplicial complexes was born.  That correspondence is called the Stanley--Reisner correspondence.  It has come to occupy a central place in combinatorial algebraic geometry. 

Title: Rigidity of Simplicial Complexes

Abstract: A simplicial k-cycle is an abstract simplicial k-complex in which every (k-1)-face belongs to an even number of k-faces. A simplicial k-circuit is a minimal simplicial k-cycle (in the sense that none of its proper subcomplexes are simplicial k-cycles).