%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[submission]{FPSAC2026}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

% Loading all packages and macros

\usepackage{mathtools, % add-on for amsmath
            hyperref, % used for urls and autoref
            graphicx,
}

\usepackage{nicematrix} % for matrices with indexed rows and cols
%\NiceMatrixOptions{cell-space-limits = 1.5pt} % spacing for math in tables

\usepackage{tikz}
\usetikzlibrary{arrows, positioning, math, quotes}

% Making compact section autorefs
\makeatletter
\renewcommand{\sectionautorefname}{\S\@gobble}
\renewcommand{\subsectionautorefname}{\S\@gobble}
\renewcommand{\subsubsectionautorefname}{\S\@gobble}
\makeatother

% Defining theorem environments
\usepackage{amsthm}
\usepackage{thmtools}
\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}

\theoremstyle{definition}
\newtheorem{dfn}[thm]{Definition}
\newtheorem{exam}[thm]{Example}

\theoremstyle{remark}
\newtheorem*{rmk}{Remark}

\newenvironment{pf}[1][\proofname]{\proof}{\endproof}

% Custom macros
\usepackage{bbm}
\newcommand{\bbone}{\mathbbm{1}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cM}{\mathcal{M}}

\newcommand{\paren}[1]{\left( #1 \right)}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}

\renewcommand{\phi}{\varphi}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\Cay}{Cay}
\DeclareMathOperator{\Tr}{Tr}


%% define your title in the usual way
\title[Graphical Designs find Combinatorial Structures]{Extended Abstract for ``Graphical Designs find Combinatorial Structures''}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author{Zawad Chowdhury\thanks{Corresponding author; contact at \href{mailto:zawadx@uw.edu}{zawadx@uw.edu}.}\addressmark{1}, Stefan Steinerberger\addressmark{1}, \and Rekha Thomas\addressmark{1}}

\address{\addressmark{1}Department of Mathematics, University of Washington}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\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\H{o}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.
}

%% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Spectral Graph Theory, Combinatorial Designs, Orthogonal Arrays.}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{ref.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\articlenumber{31}
\begin{document}

\maketitle


\section{Introduction}
\subsection{Graphical Designs}
Let $G=(V,E)$ be a finite, connected, undirected and unweighted graph on $n$ vertices. 
Any such graph has an associated \emph{Graph Laplacian} $L=D-A$, where $D \in \mathbb{R}^{n \times n}$ is the diagonal degree matrix with $D_{ii} = \deg(v_i)$, 
and $A \in \mathbb{R}^{n \times n}$ is the adjacency matrix with $A_{ij} = 1$ if $(i, j) \in E$ and $0$ otherwise.
The matrix $L \in \mathbb{R}^{n \times n}$ is symmetric and positive semidefinite, with eigenvalues $0 = \lambda_1 < \lambda_2 \leq \lambda_3 \leq \dots \leq \lambda_n$, 
and associated eigenvectors $\phi_1, \dots, \phi_n \in \mathbb{R}^n$. This spectral information captures the underlying geometry of the graph $G$, and a collection of $n$ independent eigenvectors form a `canonical' basis for functions $f:V \rightarrow \mathbb{R}$. 
These facts form the core of Spectral Graph Theory \cite{chung1997spectral, grigoryan2018intro, nica2018intro}. 

\begin{figure}[!h]
    \begin{minipage}{0.48\textwidth}
        \centering
        \begin{tikzpicture}[scale=0.6]
            \node at (-6, 0) {}; % pushes figure to the right
            \tikzstyle{every node}=[circle, fill=black, inner sep=2pt]
            \foreach \y[count=\a] in {10,9,4}
                {\pgfmathtruncatemacro{\kn}{120*\a-90}
                    \node at (\kn:3) (b\a){} ;}
                \foreach \y[count=\a] in {8,7,2}
                {\pgfmathtruncatemacro{\kn}{120*\a-90}
                    \node at (\kn:1.8) (d\a) {};}
                \foreach \y[count=\a] in {1,5,6}
                {\pgfmathtruncatemacro{\jn}{120*\a-30}
                    \node at (\jn:1.6) (a\a) {};}
                \foreach \y[count=\a] in {3,11,12}
                {\pgfmathtruncatemacro{\jn}{120*\a-30}
                    \node at (\jn:3) (c\a) {};}
            \draw[dashed] (a1)--(a2)--(a3)--(a1);
            \draw[thick] (d1)--(d2)--(d3)--(d1);
            \foreach \a in {1,2,3}
                {\draw[dashed] (a\a)--(c\a);
                \draw[thick] (d\a)--(b\a);}
                \draw[thick] (c1)--(b1)--(c3)--(b3)--(c2)--(b2)--(c1);
                \draw[thick] (c1)--(d1)--(c3)--(d3)--(c2)--(d2)--(c1);
                \draw[dashed] (b1)--(a1)--(b2)--(a2)--(b3)--(a3)--(b1);
        \end{tikzpicture}
    \end{minipage}
        \begin{minipage}{.48\textwidth}
        \centering
        \begin{tikzpicture}[scale=0.6]
            \tikzstyle{every node}=[circle, fill=white, draw=black, inner sep=2pt]

            % graph vertices
            \foreach \a in {1,2,...,9}{
                \node (o\a) at (\a*360/9: 3) {};
            }
            \node (i1) at (0, 1) {};
            \node (i2) at (-0.8, -0.4) {};
            \node (i3) at (0.8, -0.4) {};

            % design vertices
            \foreach \a in {1,5,9}{
                \node[fill=black] at (o\a) {};
            }
            \node[fill=black] at (i2) {};

            % graph edges
            \foreach \a[evaluate={\b=int(\a + 1)}] in {1,2,...,8}{
                \draw (o\a) -- (o\b);
            }
            \draw (o9) -- (o1);
            \foreach \a[evaluate={\c=int(\a + 2)}] in {1,4,7}{
                \draw (o\a) -- (o\c);
            }
            \draw (i1) -- (i2) -- (i3) -- (i1);
            \foreach \a[evaluate={\d=int(3*\a - 1)}] in {1,2,3}{
                \draw (i\a) -- (o\d);
            }
        \end{tikzpicture}
    \end{minipage}
    \caption{Left: the icosahedron, a spherical 5-design of $\mathbb{S}^2$, is automatically recovered by the spectral geometry. Right: a graphical design with four vertices averaging 11 of 12 eigenvectors in the truncated tetrahedral graph.}
\end{figure}

Motivated by \emph{spherical designs} \cite{goethals1977sphericaldesigns,sobolev1962cubature}, one may define \cite{steinerberger2020designs}  a \textbf{graphical design} $\cD \subseteq V$ to be a subset which, for a certain collection of eigenvectors $\Phi \subseteq \set{\phi_1, \dots, \phi_n}$, satisfies
\begin{equation} \label{eq:designs-average}
    \frac{1}{|\mathcal{D}|}\sum_{v \in \mathcal{D}} \phi(v) =  \frac{1}{|V|} \sum_{v \in V} \phi(v) \qquad \forall~\phi \in \Phi.
\end{equation}
We say $\cD$ \textbf{averages} an eigenvector $\phi$ if it satisfies \autoref{eq:designs-average} for $\phi$, and call all subsets averaging a fixed collection of eigenvectors $\Phi$ the \textbf{$\Phi$-designs} of $G$.

There is a natural question of which subset $\Phi$ one should choose. 
In this paper we show several particular choices of $\Phi$ for which the graphical designs of well-known graphs correspond to well-known combinatorial structures.
This connection brings a new point of view to the study of these objects. 
 
\subsection{Outline of Results}

Graphical designs are defined purely analytically by the graph Laplacian. But they also recognize the combinatorics within structured graphs, which we showcase in three different settings. Proofs and further results are provided in our main paper \cite{chowdhury2025combstruc}.
\begin{enumerate}
    \item Graphical designs of the hypercube graph on $\set{0,1}^n$, and more generally in Hamming graphs (\autoref{sec:hamming-section}), are naturally related to \emph{orthogonal arrays}. As a special byproduct, we show that in the second simplest case for hypercube graphs, the smallest graphical designs correspond to \emph{Hadamard matrices}. Smaller Hamming cubes are graphical designs when the order of eigenspaces is reversed.
    \item Graphical designs of the Johnson graph (\autoref{sec:johnson-section}) correspond to  \emph{combinatorial block designs}. Moreover, reversing the order of eigenspaces, we recover extremal configurations from the \emph{Erd\H{o}s--Ko--Rado Theorem}.
    \item Moving to the symmetric group $S_n$ (\autoref{sec:S_n-section}), we show that \emph{t-wise uniform sets of permutations} are graphical designs. Reversing the order of the eigenspaces leads to graphical designs that are given by \emph{symmetric subgroups}.
\end{enumerate}

The original paper on graphical designs \cite{steinerberger2020designs} made the point that designs, whenever they exist, should capture the underlying geometry of the graph. We show this for several well-known graphs, connecting their designs to the underlying combinatorial structures.
Our results also generalize the work of Golubev \cite{golubev2020extremal}, whose results on the extremal designs of the Kneser graph and the derangement graph are special cases of \autoref{thm:erdos-ko-rado-designs} and \autoref{thm:symm-subgrp-designs} respectively.
Babecki \cite{babecki2021codes} and Zhu \cite{zhu2023bch} established connections between graphical designs and coding theory, which we extend by showing orthogonal arrays are graphical designs (\autoref{thm:orth-array-designs}).
Babecki and Thomas \cite{babecki2023galeduality} showed positively weighted graphical designs are in bijection with the faces of a generalized eigenpolytope, which we apply to several new settings.
Finally our result equating the Hadamard conjecture with an existence problem of designs (\autoref{thm:hadamard-matrix-designs}) establishes their mathematical complexity, complementing computational complexity results \cite{babecki2024universality}.

If $\Phi_0 = \set{\bbone}, \Phi_1, \dots, \Phi_k$ are the eigenspaces of our graph with corresponding eigenvalues $0 = \lambda_0 < \lambda_1 < \dots < \lambda_k$, then our most common choices for $\Phi$ are:
\begin{enumerate}
    \item \textbf{Laplacian order}, where $\Phi = \Phi_{[t]} = \set{\Phi_1, \Phi_2, \dots, \Phi_t}$. 
    \item \textbf{Reverse Laplacian order}, where 
    $\Phi = \Phi_{[k]\setminus [t]} = \set{\Phi_k, \Phi_{k-1}, \dots, \Phi_{t+1}}$. 
\end{enumerate}

We describe graphical designs in these orders in \S2-3. In \S4, we abandon the Laplacian orders and instead use an ordering coming from the representation theory of $S_n$. 
Note that $\Phi$ never includes $\Phi_0$ as it is averaged by all subsets.

\section{Designs of the Hamming Graph} \label{sec:hamming-section}

\subsection{Hypercube Graphs, Orthogonal Arrays and Hadamard Matrices} \label{sec:hypercube-designs}

The \textbf{hypercube graph} $H(n, 2)$ is the graph with vertex set $(\ZZ/2\ZZ)^n$ and an edge between vertices that differ in one coordinate.
The graph induces a metric on the group: the Hamming distance $|x-y|$ between $x, y \in (\ZZ/2\ZZ)^n$ is the number of coordinates they differ in. 
The Hamming weight $|x|$ is the Hamming distance from $x$ to $0$.

\begin{figure}[!h]
    \begin{minipage}{0.48\textwidth}
        \centering
        \begin{tikzpicture}[scale=1.1]
            \node at (-2, 0) {}; % pushes figure to the right
            \tikzstyle{every node}=[circle, fill=white, draw=black, inner sep=2pt]
            \foreach \x in {0, 1} {\foreach \y in {0, 1} {\foreach \z in {0, 1} {\foreach \w in {0, 1} {
                \node (v\x\y\z\w) at (-0.2*\x + 1*\y + 1.4*\z + 1*\w, 1.4*\x + 1*\y + 0.2*\z - 1*\w) {};
            }}}}
            \foreach \xyzw in {0000, 1110, 0111, 1001} {
                \node[fill=black] at (v\xyzw) {};
            }
            \foreach \x in {0, 1} {\foreach \y in {0, 1} {\foreach \z in {0, 1} {
                \draw (v\x\y\z0) -- (v\x\y\z1);
                \draw (v\x\y0\z) -- (v\x\y1\z);
                \draw (v\x0\y\z) -- (v\x1\y\z);
                \draw (v0\x\y\z) -- (v1\x\y\z);    
            }}}
        \end{tikzpicture}    
    \end{minipage}
    \begin{minipage}{0.48\textwidth}
        \centering
        \begin{tikzpicture}[scale=1.1]
            \tikzstyle{every node}=[circle, fill=white, draw=black, inner sep=2pt]
            \foreach \x in {0, 1} {\foreach \y in {0, 1} {\foreach \z in {0, 1} {\foreach \w in {0, 1} {
                \node (v\x\y\z\w) at (-0.2*\x + 1*\y + 1.4*\z + 1*\w, 1.4*\x + 1*\y + 0.2*\z - 1*\w) {};
            }}}}
            \foreach \w in {0, 1} {
                \foreach \xyz in {000, 111} {
                    \node[fill=black] at (v\xyz\w) {};
                }
            }
            \foreach \x in {0, 1} {\foreach \y in {0, 1} {\foreach \z in {0, 1} {
                \draw (v\x\y\z0) -- (v\x\y\z1);
                \draw (v\x\y0\z) -- (v\x\y1\z);
                \draw (v\x0\y\z) -- (v\x1\y\z);
                \draw (v0\x\y\z) -- (v1\x\y\z);
            }}}    
        \end{tikzpicture}    
    \end{minipage}
    \caption{The hypercube graph $H(4, 2)$ with some graphical designs. Left: averaging the first nontrivial eigenspace. Right: averaging all but the middle eigenspace.}
    \label{fig:q4-designs-example}
\end{figure}

Each element $y \in (\ZZ/2\ZZ)^n$ gives us an eigenvector of the $H(n, 2)$ graph Laplacian:
the function $\chi_y: (\ZZ/2\ZZ)^n \to \RR$ defined by $\chi_y(x) := (-1)^{y \cdot x}.$
$\chi_y$ has eigenvalue $2|y|$, and the set of $\chi_y$ is an orthogonal basis of eigenvectors of the Laplacian.
Thus the Laplacian of $H(n, 2)$ has $n+1$ eigenspaces $\Phi_t = \set{y : |y|= t}$, one for each Hamming weight $t = 0, \dots, n$. The eigenspace $\Phi_t$ has eigenvalue $2t$ and multiplicity $\binom{n}{t}$.


\begin{exam} \label{exam:cube-design-example}
    Consider the cube graph $H(3, 2)$. The matrix below, whose columns and rows are indexed by $x, y \in (\ZZ/2\ZZ)^3$ respectively, has $\chi_y(x)$ in position $(y,x)$.
    
    \[U = \begin{pNiceMatrix}[first-row, last-col]
        000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 & \\
        1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 000\\
        \hline
        1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 & 001\\
        1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 & 010\\
        1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 & 100\\
        \hline 
        1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 & 011\\
        1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 & 101\\
        1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 & 110\\
        \hline
        1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 & 111
    \end{pNiceMatrix}\]
    The rows of this matrix are the eigenvectors $\chi_y$ of $H(3, 2)$. We have grouped them in horizontal strips by eigenvalue.
    $\Phi_{[1]}$ is the first block of size three, $\set{\chi_{001}, \chi_{010}, \chi_{100}}$. The sets $\cD_1 = \set{000, 111}$ and $\cD_2 = \set{000, 011, 101, 110}$ both average this eigenspace. 
    However, if we set $\Phi = \Phi_{[2]}$ which includes both blocks of size three, then $\cD_1$ is no longer a $\Phi$-design as it does not average the second block. But $\cD_2$ is a $\Phi_{[2]}$-design; for all six eigenvectors, the average over $\cD_2$ is the same as the average over all vertices.
\end{exam}
\begin{figure}[ht]
    \begin{minipage}{0.48\textwidth}
        \centering
        \begin{tikzpicture}[scale=2.2]
            \tikzstyle{every node}=[circle, fill=white, draw=black, inner sep=2pt]
            \foreach \x in {0, 1} {
                \foreach \y in {0, 1} {
                    \foreach \z[evaluate={\l=\y\x\z}] in {0, 1} {
                        \node (v\x\y\z) at (\x, \y, -\z) [label=above left:\l]{};
                    }
                }
            }
            \foreach \xyz in {000, 111} {
                \node[fill=black] at (v\xyz) {};
            }
            \foreach \x in {0, 1} {
                \foreach \y in {0, 1} {
                    \draw (v\x\y0) -- (v\x\y1);
                    \draw (v\x0\y) -- (v\x1\y);
                    \draw (v0\x\y) -- (v1\x\y);
                }
            }
        \end{tikzpicture}
    \end{minipage}
    \begin{minipage}{0.48\textwidth}
        \centering
        \begin{tikzpicture}[scale=2.2]
            \tikzstyle{every node}=[circle, fill=white, draw=black, inner sep=2pt]
            \foreach \x in {0, 1} {
                \foreach \y in {0, 1} {
                    \foreach \z[evaluate={\l=\y\x\z}] in {0, 1} {
                        \node (v\x\y\z) at (\x, \y, -\z) [label=above left:\l]{};
                    }
                }
            }
            \foreach \xyz in {000, 110, 011, 101} {
                \node[fill=black] at (v\xyz) {};
            }
            \foreach \x in {0, 1} {
                \foreach \y in {0, 1} {
                    \draw (v\x\y0) -- (v\x\y1);
                    \draw (v\x0\y) -- (v\x1\y);
                    \draw (v0\x\y) -- (v1\x\y);
                }
            }
        \end{tikzpicture}
    \end{minipage}
    \caption{The $\Phi_{[1]}$-design $\cD_1$ (left) and the $\Phi_{[2]}$-design $\cD_2$ (right) of $H(3,2)$.}
    \label{fig:q3-designs-example}
\end{figure}
The bit strings in the design $\cD_2 = \set{000, 011, 101, 110}$ have a curious pattern. Projecting to any two coordinates, $\cD_2$ looks like the set $\set{00, 01, 10, 11}$. In other words, $\cD_2$ has a uniform distribution in all pairs of coordinates. 
Such sets are called \emph{orthogonal arrays}.
\begin{dfn}
    An \textbf{orthogonal array} with parameters $(t, n, q)$ is a set of $q$-ary strings of length $n$ (in other words, a subset of $(\ZZ/q\ZZ)^n$) such that any subset of $t$ coordinates contains every length $t$ string (i.e. every element of $(\ZZ/q\ZZ)^t$) equally many times. Such an orthogonal array has \textbf{$q$ levels, $n$ constraints and strength $t$}.
\end{dfn}
In our example above, $\cD_2$ is an orthogonal array with parameters $(2, 3, 2)$. In fact, $\cD_1$ is also an orthogonal array, but with strength 1 instead of 2. This pattern holds in general, and is the main result of this section. We state the result first in the specific case of hypercube graphs; the proof is provided for the general case of \autoref{thm:orth-array-designs}.

\begin{thm}[Orthogonal Arrays are Designs I] \label{thm:hamming-orthogonalarrays-binary}
    A subset $\cD \subseteq (\ZZ/2\ZZ)^n$ is a $\Phi_{[t]}$-design if and only if $\cD$ is an orthogonal array with parameters $(t, n, 2)$.
\end{thm}

A natural followup question is whether one can construct the smallest $\Phi_{[t]}$-designs for a given $t$. When $t=1$, the smallest designs have size two and are given by antipodal vertices in $H(n, 2)$. When $t=2$, the situation immediately becomes much more complex: the smallest designs correspond to \emph{Hadamard matrices}. 
A matrix in $\{+1, -1\}^{n\times n}$ is called a \textbf{Hadamard matrix} if its rows are pairwise orthogonal. It is well known that an $n \times n$ Hadamard matrix can exist only when $n=1,2$ or is divisible by 4. Proving that such a matrix exists for all $n$ divisible by 4 is the \emph{Hadamard Conjecture}, which has been open for almost a century. The first construction of a Hadamard matrix of order 428 was in 2004 \cite{kharaghani2004hadamard}, and it is still unknown whether there is a Hadamard matrix of order 668 \cite{dokovic2014hadamard}. 

We show that the existence of $\Phi_{[2]}$-designs of $H(n,2)$ with the smallest possible size is equivalent to the Hadamard conjecture. This shows that graphical designs are conceptually hard to find: proving or disproving their existence in this optimal case is at least as difficult as the Hadamard conjecture.

\begin{thm}[name=Hadamard Matrices are Smallest $\Phi_{[2]}$-Designs, label=thm:hadamard-matrix-designs, restate=thmhadamarddesigns]
    The size of a $\Phi_{[2]}$-design of $H(n, 2)$ is greater than $n$ and divisible by $4$. When $n = 4\ell-1$, a $\Phi_{[2]}$-design with size $4 \ell$ exists if and only if there is a $4\ell \times 4\ell$ Hadamard matrix. 
\end{thm}

The story of orthogonal arrays and graphical designs generalizes if we replace binary with $q$-ary, passing from $H(n,2)$ to the general Hamming graph.
The \textbf{Hamming graph} $H(n, q)$ is the graph with vertex set $(\ZZ/q\ZZ)^n$, with an edge between vertices that differ in one coordinate.
The eigenvectors of the graph Laplacian of $H(n,q)$ are given by the functions $\chi_y: x \mapsto \omega^{y \cdot x}$ for each $y \in (\ZZ/q\ZZ)^n$, where $\omega$ is a primitive $q$-th root of unity.
$\chi_y$ has eigenvalue $q|y|$, forming $n+1$ eigenspaces.
$\Phi_{[t]}$-designs in Laplacian order correspond to orthogonal arrays, generalizing \autoref{thm:hamming-orthogonalarrays-binary} to general $q$. This is equivalent to a result of Delsarte \cite[Theorem 4.4]{delsarte1973thesis}, but we provide an original proof.

\begin{thm}[name=Orthogonal Arrays are Designs II, label=thm:orth-array-designs, restate=thmortharraydesigns]
    A subset $\cD \subset (\ZZ/q\ZZ)^n$ is a $\Phi_{[t]}$-design if and only if $\cD$ is an orthogonal array with parameters $(t, n, q)$.
\end{thm}

\begin{figure}[!h]
    \centering
    \begin{minipage}{0.48\textwidth}
        \centering
        \begin{tikzpicture}[scale=1.5]
            \node at (-1, 0) {};
            \tikzstyle{every node}=[circle, fill=white, draw=black, inner sep=2pt]
            \foreach \x in {0, 1, 2} {
                \foreach \y[evaluate={\l=(\x, \y)}] in {0, 1, 2} {
                    \node (v\x\y) at (\x, \y) [label=above left:\l]{};
                }
            }
            \foreach \x in {0, 1, 2} {
                \draw (v\x0) -- (v\x1);
                \draw (v\x1) -- (v\x2);
                \draw (v\x0) to [bend right=30] (v\x2);
            }
            \foreach \y in {0, 1, 2} {
                \draw (v0\y) -- (v1\y);
                \draw (v1\y) -- (v2\y);
                \draw (v0\y) to [bend right=30] (v2\y);
            }

        \end{tikzpicture}
    \end{minipage}
    \begin{minipage}{0.48\textwidth}
        \centering
        \begin{tikzpicture}[scale=1.5]
            \tikzstyle{every node}=[circle, fill=white, draw=black, inner sep=2pt]
            \foreach \x in {0, 1, 2} {
                \foreach \y[evaluate={\l=(\x, \y)}] in {0, 1, 2} {
                    \node (v\x\y) at (\x, \y) [label=above left:\l]{};
                }
            }
            
            \tikzmath{\e = 0.2;}
            \draw[color=red, thick] (0 - \e, 2 - \e) -- (0 + \e, 2 + \e);
            \draw[color=red, thick] (1 - \e, 0 - \e) -- (2 + \e, 1 + \e);
            \draw[color=teal, thick] (0 - \e, 0 - \e) -- (2 + \e, 2 + \e);
            \draw[color=cyan, thick] (0 - \e, 1 - \e) -- (1 + \e, 2 + \e);
            \draw[color=cyan, thick] (2 - \e, 0 - \e) -- (2 + \e, 0 + \e);
        \end{tikzpicture}
    \end{minipage}
    \caption{Left: the Hamming Graph $H(2, 3)$. Right: Hyperplanes along one direction in $(\ZZ/3\ZZ)^2$; each color is one hyperplane.}
    \label{fig:hamming-hyperplanes}
\end{figure}

A set $\cD \subset (\ZZ/q\ZZ)^t$ is an orthogonal array whenever certain functions are constant. Whenever $\cD$ is a design, these functions have constant average over all ``hyperplanes'' in $(\ZZ/q\ZZ)^t$ (\autoref{fig:hamming-hyperplanes}). We investigate the \emph{Radon transform} on finite groups in our proof \cite[\S 6.1.2]{chowdhury2025combstruc} to show that these two formulations are equivalent.

\subsection{Smaller Hamming Cubes are Reverse Order Designs} \label{sec:reverse-order-designs-hamming}

The Hamming graph has a recursive structure: fixing some coordinate values induces a smaller Hamming graph. These subcubes are philosophically opposite to orthogonal arrays; instead of being well distributed amongst all choices of coordinates, they are fixed with respect to a specific choice of coordinates. Quite remarkably, these subsets also serve as graphical designs, averaging eigenvectors in reverse Laplacian order.

\begin{thm}[label=thm:hamming-reverse-designs, restate=thmhammingreversedesigns, name=Hamming Subcubes are Reverse Order Designs]
    Let $\cD$ be a subset of $(\ZZ/q\ZZ)^n$ sharing values in $t$ coordinates, so that the induced subgraph on $\cD$ is isomorphic to the smaller Hamming graph $H(n-t, q)$. Then $\cD$ is a $\Phi_{[n]\setminus [t]}$-design i.e. it averages the first $n-t$ eigenspaces in reverse Laplacian order.
\end{thm}
 
\begin{figure}[!h]
    \begin{minipage}{0.48\textwidth}
        \centering
        \begin{tikzpicture}[scale=2.2]
            \node at (-1, 0) {};
            \tikzstyle{every node}=[circle, fill=white, draw=black, inner sep=2pt]
            \foreach \x in {0, 1} {
                \foreach \y in {0, 1} {
                    \foreach \z in {0, 1} {
                        \node (v\x\y\z) at (\x, \y, -\z) {};
                    }
                }
            }
            \foreach \x in {0, 1} {
                \foreach \y in {0, 1} {
                    \node[fill=black] at (v\x\y0) {};
                }
            }
            \foreach \x in {0, 1} {
                \foreach \y in {0, 1} {
                    \draw (v\x\y0) -- (v\x\y1);
                    \draw (v\x0\y) -- (v\x1\y);
                    \draw (v0\x\y) -- (v1\x\y);
                }
            }
        \end{tikzpicture}
    \end{minipage}
    \begin{minipage}{0.48\textwidth}
        \centering
        \begin{tikzpicture}[scale=1.1]
            \tikzstyle{every node}=[circle, fill=white, draw=black, inner sep=2pt]
            \foreach \x in {0, 1} {\foreach \y in {0, 1} {\foreach \z in {0, 1} {\foreach \w in {0, 1} {
                \node (v\x\y\z\w) at (-0.2*\x + 1*\y + 1.4*\z + 1*\w, 1.4*\x + 1*\y + 0.2*\z - 1*\w) {};
            }}}}
            \foreach \x in {0, 1} {
                \foreach \z in {0, 1} {
                    \node[fill=black] at (v\x0\z0) {};
                }
            }
            \foreach \x in {0, 1} {\foreach \y in {0, 1} {\foreach \z in {0, 1} {
                \draw (v\x\y\z0) -- (v\x\y\z1);
                \draw (v\x\y0\z) -- (v\x\y1\z);
                \draw (v\x0\y\z) -- (v\x1\y\z);
                \draw (v0\x\y\z) -- (v1\x\y\z);    
            }}}
        \end{tikzpicture}    
    \end{minipage}
    \caption{Smaller Hamming cubes are reverse order designs. Left: a $\Phi_{\{2, 3\}}$-design of $H(3, 2)$. Right: a $\Phi_{\{3, 4\}}$-design of $H(4, 2)$.}
    \label{fig:reverse-order-designs}
\end{figure}

\autoref{thm:hamming-reverse-designs} is known in the literature \cite[Theorem 8]{brouwer2003widthdualwidth}, but we provide a new proof using the theory of \emph{eigenpolytopes} \cite[\S 6.1.5]{chowdhury2025combstruc}.
The $t = 1$ case was shown by Golubev for $H(n,2)$ \cite[Theorem 3.3]{golubev2020extremal}. The story is actually quite rich in that case: all designs are the union of Hamming subcubes. This fact is not necessarily true for $t > 1$.
\begin{prop}[label=prop:hamming-reverse-eigenpolytope, restate=prophammingreverseeigenpolytope]
    For $i \in [n], a \in \ZZ/q\ZZ$, let $\cD_{i, a}$ be the subset of $(\ZZ/q\ZZ)^n$ consisting of $q$-ary strings $x$ with $x_i = a$. The $qn$ subsets $\cD_{i, a}$ are the minimal designs of $H(n,q)$, averaging $\Phi_{[n]\setminus [1]}$. All other designs are unions of these designs.
\end{prop}

\section{Designs of the Johnson graph} \label{sec:johnson-section}

\subsection{Combinatorial Block Designs} \label{sec:comb-designs}

Let $\binom{[n]}{k}$ denote the set of $k$-element subsets of $[n]$.
The \textbf{Johnson graph}, $J(n,k)$ is the graph with vertex set $\binom{[n]}{k}$ and edges between pairs of $k$-element subsets that share $k-1$ elements.
The graph $J(n,k)$ is regular of degree $k(n-k)$. 
The octahedral graph (\autoref{fig:J(4,2)}) is the Johnson graph $J(4,2)$, while the complement of the Petersen graph is $J(5,2)$. 

\begin{figure}[!h]
    \centering
    \begin{tikzpicture}[scale=0.6]
        \tikzstyle{every node}=[circle, fill=white, draw=black, inner sep=2pt]

        \node (A) at (90:2) [label=above:1100]{};
        \node (B) at (30:2) [label=above right:1010]{};
        \node (C) at (-30:2) [label=below right:1001]{};
        \node (D) at (-90:2) [label=below:0011]{};
        \node (E) at (-150:2) [label=below left:0101]{};
        \node (F) at (150:2) [label=above left:0110]{};

        \draw (A) -- (B);
        \draw (A) -- (C);
        \draw (A) -- (F);
        \draw (A) -- (E);
        \draw (B) -- (C);
        \draw (F) -- (B);
        \draw (E) -- (F);
        \draw (C) -- (E);
        \draw (D) -- (B);
        \draw (D) -- (C);
        \draw (D) -- (E);
        \draw (D) -- (F);
    \end{tikzpicture}
    \caption{The Johnson Graph $J(4, 2)$}
    \label{fig:J(4,2)}
\end{figure}

The Laplacian of $J(n, k)$ has $k+1$ distinct eigenvalues $\lambda_t$ for $t = 0, \dots, k$ \cite[Theorem 6.3.2]{godsil-meagher}. We choose an orthonormal basis $\Phi_t$ for each eigenspace. Then, similar to \autoref{sec:hamming-section}, Laplacian order designs average $\Phi_{[t]}$ and reverse Laplacian order designs average $\Phi_{[k]\setminus [t]}$.

A subset $\cD$ of $\binom{[n]}{k}$ is called a $t$-design with parameters $(n, k, \lambda)$ if every $t$-element subset of $[n]$ is contained in $\lambda$ of the $k$-element subsets in $\cD$. 
They are also known as \textbf{combinatorial block designs}, since the elements of $\cD$ are \emph{blocks} of elements in $[n]$. A $t$-design with $\lambda=1$ is a \textbf{Steiner system}. 
\begin{thm}[label=thm:comb-designs-are-graphical-designs, restate=thmcombdesigns, name=$t$-designs are Graphical Designs] 
    A subset $\cD$ of $\binom{[n]}{k}$ is a $t$-design if and only if it is a $\Phi_{[t]}$-design of the Johnson graph $J(n,k)$.
\end{thm}

The proof translates a theorem of Delsarte \cite[Theorem 4.7]{delsarte1973thesis} in the context of \emph{association schemes}. Our main paper \cite[\S 3.3]{chowdhury2025combstruc} discusses this connection more broadly. 

\subsection{Erd\H{o}s--Ko--Rado Extremizers are Reverse Order Designs}
\label{sec:reverse-order-designs-johnson} 

Every $t$-element subset of $[n]$ appears equally often in a $t$-design. If instead we pick one $t$-element subset $T$ to be special, and consider all subsets containing $T$, then we get designs in reverse Laplacian order. This is analogous to the story in \autoref{sec:reverse-order-designs-hamming}.

\begin{thm}[label=thm:erdos-ko-rado-designs, restate=thmerdoskoradodesigns, name=Erd\H{o}s--Ko--Rado Extremizers are Reverse Order Designs]
    Given a fixed $t$-element subset $T$ of $[n]$, let $\cD_T \subset \binom{[n]}{k}$ be the set of $k$-element subsets of $[n]$ containing $T$. Then $\cD_T$ averages all $\Phi_\ell$ with $\ell > t$ i.e. $\cD$ is a $\Phi_{[k]\setminus[t]}$-design.
\end{thm}

\autoref{thm:erdos-ko-rado-designs}, like \autoref{thm:hamming-reverse-designs}, is a special case of \cite[Theorem 8]{brouwer2003widthdualwidth}. But in these specific cases we provide a new proof using the connection between graphical designs and convex geometry.

The generalized Erd\H{o}s--Ko--Rado theorem \cite{wilson1984erdoskorado} states that, for large enough $n$, all families $\cF \subset \binom{[n]}{k}$ such that any two sets in $\cF$ intersect in at least $t$ elements satisfy $|\cF| \le \binom{n-t}{k-t}$. The designs $\cD_T$ in \autoref{thm:erdos-ko-rado-designs} are the extremal constructions which meet this upper bound. That is, the $\cD_T$ are the largest families in $\binom{[n]}{k}$ with pairwise intersections of size at least $t$, when $n$ is sufficiently large.
When $t=1$, these designs are called \textbf{stars}, and they are the largest constructions for the classical Erd\H{o}s--Ko--Rado theorem \cite{erdos1961intersection}. We can show that the stars are not just $\Phi_{[n]\setminus[1]}$-designs, but the minimal designs from which all other designs are constructed.

\begin{prop}[label=prop:johnson-reverse-eigenpolytope, restate=propjohnsonreverseeigenpolytope]
    Let $\cD_i$ be the subset of $\binom{[n]}{k}$ comprised of all $k$-element subsets containing the element $i \in [n]$. The minimal designs of $J(n, k)$ averaging $\Phi_{[k]\setminus [1]}$ are the $\cD_i$ or their complements; all other designs are unions of these designs.
\end{prop}

\section{Designs of the Symmetric Group} \label{sec:S_n-section}

\subsection{$t$-wise Uniform Sets and the Fall of Laplacian Order} \label{sec:t-wise-designs}

There are certain graphs on $S_n$, called \emph{normal Cayley graphs}, whose eigenvectors and eigenvalues are tied to the representation theory of $S_n$. In general, for a group $\Gamma$ and connection set $X \subset \Gamma$, the \textbf{Cayley graph} $\Cay(\Gamma, X)$ is the graph with vertex set $\Gamma$ and edge set $\set{(g, gx): g \in \Gamma, x \in X}$. To ensure that the graph is undirected and without loops, $X$ must not contain the identity and be closed under inverses. When $X$ is also closed under conjugation, we say $\Cay(\Gamma, X)$ is \textbf{normal}. The transposition graph and the derangement graph are examples of normal Cayley graphs on $S_n$ (\autoref{fig:s3-normal-cayley}).

\begin{figure}[!h]
    \begin{minipage}{0.48\textwidth}
        \centering
        \begin{tikzpicture}[scale=1.2]
            \node at (-1, 0) {};
            \tikzstyle{every node}=[circle, fill=white, draw=black, inner sep=2pt]

            \node (132) at (150:1) [label=above left:(132)]{};
            \node (e) at (90:1) [label=above:e]{};
            \node (123) at (30:1) [label=above right:(123)]{};
            \node (13) at (-30:1) [label=below right:(13)]{};
            \node (12) at (-90:1) [label=below:(12)]{};
            \node (23) at (-150:1) [label=below left:(23)]{};

            \foreach \x in {e, 123, 132} {\foreach \y in {12, 13, 23} {
                \draw (\x) -- (\y);
            }}
        \end{tikzpicture}
    \end{minipage}    
    \begin{minipage}{0.48\textwidth}
        \centering
        \begin{tikzpicture}[scale=1.2]
            \tikzstyle{every node}=[circle, fill=white, draw=black, inner sep=2pt]

            \node (132) at (150:1) [label=above left:(132)]{};
            \node (e) at (90:1) [label=above:e]{};
            \node (123) at (30:1) [label=above right:(123)]{};
            \node (13) at (-30:1) [label=below right:(13)]{};
            \node (12) at (-90:1) [label=below:(12)]{};
            \node (23) at (-150:1) [label=below left:(23)]{};

            \draw (e) -- (123) -- (132) -- (e);
            \draw (12) -- (13) -- (23) -- (12);
        \end{tikzpicture}
    \end{minipage}
    \caption{Normal cayley graphs on $S_3$: the transposition graph (left) and the derangement graph (right).}
    \label{fig:s3-normal-cayley}
\end{figure}

A classical result shows that the eigenvectors of normal Cayley graphs are produced by entries of irreducible orthogonal representations of the group; see \cite[Theorem 10]{ellis2011intersecting} for a proof. In the case of $S_n$, the irreducible representations are indexed by the partitions $p \vdash n$. Call the corresponding representation $\rho_p$, with degree $d_p$. Let $\rho_p^{ij}$ be the function sending a permutation $\pi$ to the $(i,j)$-th entry of its representation $\rho_p(\pi)$. Then $\rho_p^{ij}$ is an eigenvector of all normal Cayley graphs on $S_n$. 
There are $n! = |S_n|$ such eigenvectors $\rho_p^{ij}$, and they form an orthogonal basis of $\RR^{n!}$. 

For any partition $p \vdash n$, let $\Phi_p = \set{\rho_p^{ij} : i,j \in [d_p]}$ be all $d_p^2$ eigenvectors coming from the representation $\rho_p$. For a fixed normal Cayley graph, all eigenvectors in $\Phi_p$ have the same eigenvalue, and so the sets $\Phi_p$ refine a basis of Laplacian eigenspaces. It is natural to expect, following \autoref{thm:orth-array-designs} and \autoref{thm:comb-designs-are-graphical-designs}, that we will find an interesting combinatorial structure as graphical designs averaging all $\Phi_p$ with low Laplacian eigenvalues. We shall soon see (\autoref{thm:t-wise-uniform-designs}) that this does not work.

A well-studied collection of combinatorial structures associated to $S_n$ are \emph{$t$-wise uniform sets of permutations}; these, like orthogonal arrays and combinatorial block designs, are uniformly distributed among all possibilities at specific coordinates.
\begin{dfn}
    A \textbf{$t$-wise uniform set of permutations} (or \textbf{$t$-uniform set} in short) is a subset $\cD \subset S_n$ with a uniform action on any $t$-tuple of elements. In other words, for all choices of distinct $i_1, \dots, i_t \in [n]$ and distinct $j_1, \dots, j_t \in [n]$ we have (for $k=1, \dots, t$),
    \[\frac{\abs{\set{\sigma \in \cD : \sigma(i_k) = j_k}}}{|\cD|} = \frac{\abs{\set{\sigma \in S_n : \sigma(i_k) = j_k}}}{|S_n|} = \frac{(n-t)!}{n!}.\]
    The probability that $\sigma(i_k) = j_k$ 
    % for all $1 \le k \le t$ 
    is the same whether $\sigma$ is chosen uniformly from $S_n$ or $\cD$. 
    % Sometimes in short we say $\cD$ is \textbf{$t$-uniform}. 
\end{dfn}

For $S_4$ we have three different $t$ for which a set can be $t$-uniform, as $3$-uniform sets are automatically $4$-uniform. On the other hand, $S_4$ has four non-constant eigenspaces $\Phi_p$, namely $\Phi_{(3,1)}$, $\Phi_{(2,2)}$, $\Phi_{(2,1,1)}$, and $\Phi_{(1,1,1,1)}$ (we exclude the eigenspace $\Phi_{(4)}$ of constant functions). Looking at which eigenspaces the different $t$-uniform sets average, we have
\begin{center}
    \begin{tabular}{ll}
        $1$-uniform sets average & $\Phi_{(3,1)};$ \\
        $2$-uniform sets average & $\Phi_{(3,1)}, \Phi_{(2,2)}, \Phi_{(2,1,1)};$ \\
        $3$-uniform sets average & $\Phi_{(3,1)}, \Phi_{(2,2)}, \Phi_{(2,1,1)}, \Phi_{(1,1,1,1)}.$
    \end{tabular}
\end{center}
No normal Cayley graph on $S_4$ has Laplacian eigenspaces that split like this. Looking at the partitions, we spot a different pattern: the new eigenspaces added at each step have the same first part. This pattern works in general.

\begin{thm}[label=thm:t-wise-uniform-designs, restate=twiseuniformdesigns, name=$t$-uniform Sets are Designs]
    A set $\cD \subset S_n$ is $t$-uniform if and only if it is a design averaging all $\Phi_p$ for partitions $p \vdash n$ with first part $p_1 \ge n-t$. 
\end{thm}

\autoref{thm:t-wise-uniform-designs} immediately follows from results by Kuperberg, Lovett and Peled \cite[Section 3.4.2]{kuperberg2017combstructures}; it is also the special case $\lambda = (n-t, 1^t)$ of \cite[Theorem 4]{martin2006transitivity}. Our proof \cite[\S 6.3.1]{chowdhury2025combstruc} describes the details to reinterpret their results in the language of graphical designs. The breakdown of Laplacian order poses an interesting question: what are the Laplacian order designs, if not $t$-wise uniform sets? Do they represent a different combinatorial structure? 
\begin{exam}
    Let us describe the graphical designs not covered by \autoref{thm:t-wise-uniform-designs}, in the case of $S_4$. In the $S_4$ transposition graph, each $\Phi_p$ has a different eigenvalue. Therefore a design $\cD \subset S_4$ averaging $\Phi_{(3, 1)}$ and $\Phi_{(2,2)}$ is a design in Laplacian order, but not necessarily a design in the first part order specified in \autoref{thm:t-wise-uniform-designs}. 
    $\cD$ is 1-uniform as it averages $\Phi_{(3,1)}$, but not necessarily 2-uniform as it does not always average $\Phi_{(2,1,1)}$. The smallest such $\cD$ are of size 12, and up to graph automorphism are either
    \begin{align*}
        &\set{e, (14), (24), (34), (123), (1243), (1423), (1234), (132), (1324), (1342), (1432)},\\
        &\set{e, (1243), (14)(23), (1342), (12), (143), (1324), (234), (13), (243), (1234), (142)}
    \end{align*}
    or $A_4$ (which is also 2-uniform and thus a stronger design). If one can find a special property that distinguishes these $\Phi_{(3,1)} \cup 
    \Phi_{(2,2)}$ designs from other 1-uniform sets in $S_4$, that would be combinatorial information found by the Laplacian order that is not found by the first part order.
\end{exam}

\subsection{Symmetric Subgroups are Reverse Order Designs} \label{sec:reverse-order-designs-symmetric}

The $t$-wise uniform sets of permutations came from averaging eigenvectors in first part order. We might naturally expect that reversing the first part order will yield opposite combinatorial structures, which fix certain positions $\pi(i_k) = j_k$ instead of uniformly distributing every position. If this fixing is done for $n-t$ positions, then the corresponding subsets look like a coset of $S_t$ (under both left and right translation). 

\begin{thm}[label=thm:symm-subgrp-designs, restate=thmsymmsubgrpdesigns, name=Symmetric Subgroups are Reverse Order Designs]
    Suppose $S \subset S_n$ is a subgroup isomorphic to $S_t$ for $t < n$. Then all of its cosets $\cD = \sigma S \sigma'$ are designs of $S_n$ averaging the eigenspaces $\Phi_p$ with $p_1 < n-t$ i.e. in reverse first part order. 
\end{thm}

The generalized \emph{Deza--Frankl conjecture}, proved by Ellis, Friedgut and Pilpel \cite{ellis2011intersecting}, states that if $n$ is sufficiently large compared to $n-t$ and $\cD \subset S_n$ has the property that any two permutations in $\cD$ agree on at least $n-t$ points in $[n]$, then $|\cD| \le t!$. The equality in the bound is achieved precisely by the coset constructions in \autoref{thm:symm-subgrp-designs}. 
The Deza--Frankl conjecture is the $S_n$-analog of the Erd\H{o}s--Ko--Rado theorem, and so \autoref{thm:symm-subgrp-designs} is analogous to \autoref{thm:erdos-ko-rado-designs}.
It is also equivalent to the special case $\lambda = (n-t, 1^t)$ of \cite[Lemma 3]{martin2006transitivity}; however, we provide a novel proof using eigenpolytopes.

Similar to \autoref{prop:hamming-reverse-eigenpolytope} and \autoref{prop:johnson-reverse-eigenpolytope}, we can fully describe the extremal case of \autoref{thm:symm-subgrp-designs}, considering $t=1$ and designs averaging all $\Phi_p$ except $\Phi_{(n-1,1)}$. The proofs of those results relied on describing the eigenpolytope of this single omitted eigenspace, and using the Gale duality bijection \cite{babecki2023galeduality}. In the current case, we show that the $\Phi_{(n-1, 1)}$-eigenpolytope is the well-known \textbf{Birkhoff polytope}, the convex hull of the permutation matrices in $\RR^{n\times n}$ \cite[Example 0.12]{ziegler1995polytopes}. This is a 0/1-polytope which projects down to the permutahedron, the polytope most commonly associated to $S_n$.

\begin{prop}[label=prop:birkhoff-eigenpolytope, restate=propbirkhoffeigenpolytope]
    The minimal designs averaging the eigenspaces $\Phi_p$ with $p_1 < n-1$, are the subsets of $S_n$ which are cosets of $S_{n-1}$. All other such designs are unions of these cosets. 
\end{prop}

\autoref{prop:birkhoff-eigenpolytope} does not hold if $n-1$ is replaced by $n-t$ for $t>1$. The counterexamples provided by Filmus \cite[\S3]{filmus2017comment} are designs which average all eigenspaces $\Phi_p$ with $p_1 < n-t$ but are not cosets of $S_t$. 


\acknowledgements{The authors gratefully acknowledge helpful conversations with William Monty McGovern, Thomas Rothvoss, Isaiah Siegl and Varun Shah.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}