Graphical Designs and Gale Duality

Catherine Babecki, Rekha R. Thomas

Published 2022-04-04Version 1

A graphical design is a subset of graph vertices such that the weighted averages of certain graph eigenvectors over the design agree with their global averages. We use Gale duality to show that positively weighted graphical designs in regular graphs are in bijection with the faces of a generalized eigenpolytope of the graph. This connection can be used to organize, compute and optimize designs. We illustrate the power of this tool on three families of Cayley graphs -- cocktail party graphs, cycles, and graphs of hypercubes -- by computing or bounding the smallest designs that average all but the last eigenspace in frequency order. We also prove that unless NP = coNP, there cannot be an efficient description of all minimal designs that average a fixed number of eigenspaces in a graph.