Graphical Designs and Gale Duality

Graphical designs are an extension of classical quadrature rules to the domain of graphs. That is, 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.