The Polyhedral Structure of Graphical Designs
Presenter
March 27, 2023
Abstract
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 has 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. This talk is based on work with Rekha Thomas, Stefan Steinerberger and David Shiroma.