Séminaire Lotharingien de Combinatoire, 95B.31 (2026), 12 pp.
Zawad Chowdhury, Stefan Steinerberger and Rekha Thomas
Graphical Designs find Combinatorial Structures (Extended Abstract)
Abstract.
Graphical designs are subsets of vertices of a graph that perfectly average a selected set of eigenvectors of the Graph Laplacian. We show that in highly-structured graphs, graphical designs can coincide with well-known combinatorial objects: orthogonal arrays in hypercube graphs, combinatorial block designs and extremizers of the Erdős-Ko-Rado theorem in Johnson graphs, and t$uniform sets and symmetric subgroups in normal Cayley graphs on the symmetric group. These connections allow tools from spectral graph theory to bear on these combinatorial objects.
Received: November 15, 2025.
Accepted: February 15, 2026.
Final version: April 1, 2026.
The following versions are available: