Georgia Institute of Technology College of Sciences

One can associate regular cell complexes to various objects from discrete and combinatorial geometry such as real and complex hyperplane arrangements, oriented matroids and CAT(0) cube complexes. The faces of these cell complexes have a natural algebraic structure. In a seminal paper from 1998, Bidigare, Hanlon and Rockmore exploited this algebraic structure to model a number of interesting Markov chains including the riffle shuffle and the top-to-random shuffle, as well as the Tsetlin library. Using the representation theory of the associated algebras, they gave a complete description of the spectrum of the transition matrix of the Markov chain. Diaconis and Brown proved further results on mixing times and diagonalizability for these Markov chains. Bidigare also noticed in his thesis a natural connection between Solomon's descent algebra for a finite Coxeter group and the algebra associated to its Coxeter arrangement. Given, the nice interplay between the geometry, the combinatorics and the algebra that appeared in these two contexts, it is natural to study the representation theory of these algebras from the point of view of the representation theory of finite dimensional algebras. Building on earlier work of Brown's student, Saliola, for the case of real central hyperplane arrangements, we provide a quiver presentation for the algebras associated to hyperplane arrangements, oriented matroids and CAT(0) cube complexes and prove that these algebras are Koszul duals of incidence algebras of associated posets. Key to obtaining these results is a description of the minimal projective resolutions of the simple modules in terms of the cellular chain complexes of the corresponding cell complexes.This is joint work with Stuart Margolis (Bar-Ilan) and Franco Saliola (University of Quebec at Montreal)

An expander polynomial in F_p, the finite field with p elements, is a polynomial f(x_1,...,x_n) such that there exists an absolute c>0 with the property that for every set A in F_p (of cardinality not particularly close to p) the cardinality of f(A,...,A) = {f(a_1,...,a_n) : a in A} is at least |A|^{1+c}. Given an expander polynomial, a very interesting question is to determine a threshold T so that |A|> T implies that |f(A,...,A)| contains, say, half the elements of F_p and so is about as large as it can be. For a large number of "natural appearing" expander polynomials like f(x,y,z) = xy+z and f(x,y,z) = x(y+z), the best known threshold is T= p^{2/3}. What is interesting is that there are several proofs of this threshold of very different “depth” and complexity. We will discuss why for the expander polynomial f(x,y,z,w) = (x-y)(z-w), where f(A,A,A,A) consists of the product of differences of elements of A, one may take T = p^{5/8}. We will also discuss the more complicated setting where A is a subset of a not necessarily prime order finite field.

Motivated by real-time logistics, I will present a deterministic online algorithm for the Online Minimum Metric Bipartite Matching Problem. In this problem, we are given a set S of server locations and a set R of request locations.The requests arrive one at a time and when it arrives, we must immediately and irrevocably match it to a ``free" server. The cost of matching a server to request is given by the distance between the two locations (which we assume satisfies triangle inequality). The objective of this problem is to come up with a matching of servers to requests which is competitive with respect to the minimum-cost matching of S and R.In this talk, I will show that this new deterministic algorithm performs optimally across different adversaries and metric spaces. In particular, I will show that this algorithm simultaneously achieves optimal performances in two well-known online models -- the adversarial and the random arrival models. Furthermore, the same algorithm also has an exponentially improved performance for the line metric resolving a long standing open question.

A graph is ``strongly regular'' (SRG) if it is $k$-regular, and every pair of adjacent (resp. nonadjacent) vertices has exactly $\lambda$ (resp. $\mu$) common neighbors. Paradoxically, the high degree of regularity in SRGs inhibits their symmetry. Although the line-graphs of the complete graph and complete bipartite graph give examples of SRGs with $\exp(\Omega(\sqrt{n}))$ automorphisms, where $n$ is the number of vertices, all other SRGs have much fewer---the best bound is currently $\exp(\tilde{O}(n^{9/37}))$ (Chen--Sun--Teng, 2013), and Babai conjectures that in fact all primitive SRGs besides the two exceptional line-graph families have only quasipolynomially-many automorphisms. In joint work with Babai, Chen, Sun, and Teng, we make progress toward this conjecture by giving a quasipolynomial bound on the number of automorphisms for valencies $k > n^{5/6}$. Our proof relies on bounds on the vertex expansion of SRGs to show that a polylogarithmic number of randomly chosen vertices form a base for the automorphism group with high probability.