Graphical designs: combinatorics and applications (Catherine Babecki, Caltech)

A graphical design is a quadrature rule for a graph inspired by classical numerical integration on the sphere. Broadly speaking, that means a graphical design is a relatively small subset of graph vertices chosen to capture the global behavior of functions from the vertex set to the real numbers. We first motivate and define graphical designs for graphs with positive edge weights. Through Gale duality, we exhibit a combinatorial bijection between graphical designs and the faces of certain polytopes associated to a graph, called eigenpolytopes. This polytope connection implies a variety of beautiful consequences, including a proof of existence, an upper bound on the cardinality of a graphical design, methods to compute, optimize, and organize graphical designs, the existence of random walks with improved convergence rates, and complexity results for associated computational problems.  We conclude with applications to the equitable facility location problem.