# Structure and Complexity of Graphical Designs for Weighted Graphs through
Eigenpolytopes

Catherine Babecki and David Shiroma  Department of Mathematics, University of
Washington, Seattle, WA 98195<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We extend the theory of graphical designs, which are quadrature rules for
graphs, to positively weighted graphs. Through Gale duality for polytopes, we
show that there is a bijection between graphical designs and the faces of
eigenpolytopes associated to the graph. This bijection proves the existence of
graphical designs with positive quadrature weights, and upper bounds the size
of a graphical design. We further show that any combinatorial polytope appears
as the eigenpolytope of a positively weighted graph. Through this
universality, we establish two complexity results for graphical designs: it is
strongly NP-complete to determine if there is a graphical design smaller than
the mentioned upper bound, and it is #P-complete to count the number of
minimal graphical designs.

###### Key words and phrases:

Graphical Designs, Graph Laplacian, Gale Duality, Polytopes, Quadrature Rules,
Eigenpolytopes, Complexity, Graph Sampling.

###### 2020 Mathematics Subject Classification:

05C50, 68R10, 52B12, 52B35, 90C60

Research partially supported by the Walker Family Endowed Professorship in
Mathematics at the University of Washington.
Corresponding Author: Catherine Babecki

##  1\. Introduction

A graphical design is a quadrature rule for a graph $G=([n],E,w)$ on $n$
vertices with edge set $E$ and positive edge weights
$w:E\to{\mathbb{R}}_{>0}$. Classical numerical quadrature allows one to
compute or approximate definite integrals of certain classes of functions on
${\mathbb{R}}^{n}$ by sampling at finitely many points. Analogously, a
graphical design is a rule to compute the average of certain classes of
functions $\varphi:[n]\to{\mathbb{R}}$ over the vertex set $[n]$ by sampling
$\varphi$ on a subset $S\subset[n]$. We identify a function
$\varphi:[n]\to{\mathbb{R}}$ with a vector $\varphi\in{\mathbb{R}}^{n}$. The
classes of functions we seek to average will come from eigenvectors of the
combinatorial graph Laplacian, which form a basis for the space of all
functions on $G$. _Gale duality_ [Gal56] provides a bijection between
graphical designs and faces of the generalized _eigenpolytopes_ [God78] of a
graph. If the graph is regular, the framework we establish is precisely the
one shown in [BT22]. For more details on the connection between graphical
designs and eigenpolytopes through Gale duality, we refer the reader to
[BT22].

We outline the main results of this paper.

  * •

We establish the bijection provided by Gale duality between graphical designs
and faces of eigenpolytopes. We note that this bijection holds when the
combinatorial Laplacian is replaced by any symmetric operator with the all-
ones vector as an eigenvector. This bijection upper bounds the size of minimal
graphical designs.

  * •

Eigenpolytopes of positively weighted graphs are universal in the sense that
any combinatorial polytope appears as an eigenpolytope of a positively
weighted graph. We prove this universality by showing that the Laplacian
eigenbases from positively weighted graphs are sufficiently general. Moreover,
the algorithm to construct a positively weighted graph which has an
eigenpolytope of a given combinatorial type is polynomial time.

  * •

Using this polynomial time algorithm, we show it is strongly NP-complete to
determine if there is a graphical design smaller than the upper bound provided
by Gale duality. Similarly, it is #P-complete to count the number of minimal
graphical designs. We provide a linear program which finds one not necessarily
minimal graphical design in polynomial time.

Much of modern data is modeled through graphs, such as online communities,
power grids, and transit networks, where edge weights play a crucial role in
representing the strength of connections. As the scale of our data grows, so
too must the power of our data processing techniques. Graph signal processing
is a relatively new field which seeks to extend traditional signal processing
techniques to functions on graphs; see [Ort+18] or [Ort22] for an
introduction. Graphical designs provide a method for graph sampling, a major
problem studied in graph signal processing.

Graphical designs were defined relatively recently. In [Ste20], Steinerberger
first proposed seeking subsets $S\subset[n]$ which average eigenvectors of the
normalized Laplacian operator. This construction extended spherical
$t$-designs ([DGS77]), a type of quadrature rule on the sphere, to the
discrete domain of graphs. The main result of this paper showed that “good”
graphical designs are either large or have exponentially growing
neighborhoods. Previous work on graphical designs has mostly focused on
unweighted regular graphs, where the eigenvectors of a graph are not dependent
on the choice of operator. Golubev in [Gol20] connected graphical designs in
regular graphs to extremal combinatorics, including maximum stable sets and
the Cheeger constant of a graph. The first author in [Bab21] clarified the
original definition in the case of eigenspaces with multiplicity, connected
graphical designs in the edge graphs of hypercubes to linear error correcting
codes, and distinguished graphical designs for regular graphs in the frequency
order (introduced in [Ste20]) from a handful of related concepts. Thomas and
the first author in [BT22] used Gale duality to connect graphical designs on
regular graphs to eigenpolytopes, and used this connection to compute or bound
graphical designs for several families of regular graphs. Steinerberger and
Thomas in [ST22] showed convergence rates for random walks on regular graphs
which start at graphical designs. We also note the work of Steinerberger and
Linderman in [LS20], which considered the numerics of graphical designs on
positively weighted graphs arising from the eigenvectors of a lazy random walk
matrix.

We organize the paper as follows. Section 2 establishes definitions and
notation for graphical designs on positively weighted graphs. Section 3
briefly recounts the theory of Gale duality for polytopes and uses this
machinery to connect graphical designs to eigenpolytopes of the graph, our
main structural result. This correspondence provides a proof of existence and
an upper bound on the size of a graphical design. Section 4 illustrates this
design-polytope correspondence on two examples. In Section 5, we provide a
polynomial time algorithm to construct a positively weighted graph with $n$
vertices which has an eigenpolytope combinatorially equivalent to a given
polytope with $n$ vertices. To do this, we first show that given any
orthonormal basis of ${\mathbb{R}}^{n}$ which includes $\mathbbm{1}/\sqrt{n}$
as a vector and any partition of this basis where $\\{\mathbbm{1}/\sqrt{n}\\}$
is a part, there is a connected, positively weighted graph for which each part
of the partition spans an eigenspace of the Laplacian of this graph. Using
this universality of eigenpolytopes, we establish in Section 6 that it is
strongly NP-complete to determine if there is a design smaller than the upper
bound established in Section 3, and that it is #P-complete to count the number
of minimal graphical designs in a graph.

Acknowledgments. We thank Shayan Oveis-Gharan, Stefan Steinerberger, and Rekha
Thomas for their feedback and guidance.

##  2\. Graphical Designs on Weighted Graphs

Let $G=([n],E,w)$ be a connected graph with vertex set
$[n]:=\\{1,2,\ldots,n\\}$, edge set $E$, and positive edge weights
$w:E\to{\mathbb{R}}_{>0}$. Let $A\in{\mathbb{R}}^{n\times n}$ be the weighted
adjacency matrix of $G$, with $A_{ij}=w(ij)$ if $ij\in E$ and 0 otherwise, and
$D$ be the weighted (diagonal) degree matrix of $G$, with $D_{ii}=\deg
i=\sum_{ij\in E}w(ij)$. The combinatorial Laplacian of $G$ is the symmetric
matrix $L=D-A$. Since $L$ is positive semidefinite, it has non-negative
eigenvalues and an orthogonal set of eigenvectors
$\varphi_{1},\ldots,\varphi_{n}$ that form a basis of ${\mathbb{R}}^{n}$.
Hence any function $f:[n]\to{\mathbb{R}}$ is a linear combination of
$\varphi_{1},\ldots,\varphi_{n}$, and we will use these eigenvectors to define
the classes of functions that a graphical design on $G$ seeks to average
exactly.

Letting $\mathbbm{1}$ denote the all-ones vector in ${\mathbb{R}}^{n}$, we
always have that $L\mathbbm{1}=0$, since the $i$-th row of $A$ sums to
$\deg(i)=\sum_{ij\in E}w(ij)$. Therefore, $\mathbbm{1}$ is an eigenvector of
$L$ with eigenvalue $0$. Moreover, since $G$ is connected, the eigenspace of 0
is spanned by $\mathbbm{1}$; we denote this eigenspace by $\Lambda_{1}.$ It is
convenient to not normalize the eigenvectors $\varphi_{i}$ so that we may take
$\varphi_{1}=\mathbbm{1}$ as the basis vector for $\Lambda_{1}$. We abuse
terminology and refer to the eigenspaces and eigenvalues of $L$ as the
eigenspaces and eigenvalues of the graph $G$. The following running example
will be used to illustrate the definitions and results of this section and the
next.

######  Example 2.1.

Consider the weighted graph in Figure 1, where the weight on an edge $ij$ is
given by $w(ij)=1/\deg(i)+1/\deg(j)$.

123456789 Figure 1. A weighted graph on 9 vertices. Thicker edges indicate
greater edge weights.

Its Laplacian $L$ is

$\begin{bmatrix}23/15&0&0&-1/2&0&-1/2&-8/15&0&0\\\
0&23/15&0&-1/2&-1/2&0&0&-8/15&0\\\ 0&0&23/15&0&-1/2&-1/2&0&0&-8/15\\\
-1/2&-1/2&0&12/5&-1/3&-1/3&-11/30&-11/30&0\\\
0&-1/2&-1/2&-1/3&12/5&-1/3&0&-11/30&-11/30\\\
-1/2&0&-1/2&-1/3&-1/3&12/5&-11/30&0&-11/30\\\
-8/15&0&0&-11/30&0&-11/30&31/15&-2/5&-2/5\\\
0&-8/15&0&-11/30&-11/30&0&-2/5&31/15&-2/5\\\
0&0&-8/15&0&-11/30&-11/30&-2/5&-2/5&31/15\end{bmatrix}.$

Table 1 shows the six distinct eigenvalues of $L$ in the left column, each
followed on the right by a basis of orthogonal eigenvectors for that
eigenspace. We note that $\lambda_{2},\lambda_{4},\lambda_{6}$ are the roots
of $450x^{3}-3030x^{2}+6321x-3844$ and $\lambda_{3},\lambda_{5}$ are the roots
of $75x^{2}-340x+373$. We show decimal approximations for conciseness.

$\scriptsize{\begin{array}[]{c|ccccccccc |}\lambda_{1}=0&1&1&1&1&1&1&1&1&1\\\
\hline\cr\lambda_{2}=1.069&-.6262&.5616&.0646&-.0264&.256&-.2291&-.3059&.2744&.0316\\\
&-.2870&-.3988&.6858&-.2798&.1171&.1627&-.1402&-.1948&.3350\\\
\hline\cr\lambda_{3}=1.861&.3193&.3193&.3193&.1406&.1406&.1406&-.4600&-.4600&-.4600\\\
\hline\cr\lambda_{4}=2.661&.3248&-.4014&.0766&.0507&.2150&-.2658&-.4852&.5996&-.1144\\\
&.2760&.1433&-.4193&-.2776&.1827&.0949&-.4123&-.2141&.6263\\\
\hline\cr\lambda_{5}=2.672&.3468&.3458&.3468&-.4499&-.4499&-.4499&.1032&.1032&.1032\\\
\hline\cr\lambda_{6}=3.003&.0724&-.0995&.0271&.1880&.5015&-.6894&.2707&-.3721&.1015\\\
&.0731&.0261&-.0992&-.6876&.5066&.1810&.2734&.0977&-.3711\end{array}}$
Table 1. The spectral information of the graph shown in Figure 1.

######  Definition 2.2.

A subset $S\subseteq[n]$ _averages the eigenspace_ $\Lambda$ of $G$ if there
are vertex weights $(a_{s}\neq 0:s\in S)$ such that for every eigenvector
$\varphi$ in a basis of $\Lambda$,

(1) $\sum_{s\in S}a_{s}\varphi(s)=\frac{1}{n}\sum_{v\in[n]}\varphi(v).$

We can now define graphical designs for a weighted graph $G=([n],E,w)$.

######  Definition 2.3 ($k$-graphical designs).

Suppose $G=([n],E,w)$ has $m$ distinct eigenspaces ordered
$\Lambda_{1}<\ldots<\Lambda_{m}.$

  1. (1)

A _weighted $k$-graphical design_ of $G$ is a subset $S\subseteq[n]$ and real
weights $(a_{s}\neq 0:s\in S)$ such that $S$ averages the eigenspaces
$\Lambda_{1},\ldots,\Lambda_{k}$.

  2. (2)

If in addition, $a_{s}>0$ for all $s\in S$, we call $S$ a _positively weighted
$k$-graphical design_ of $G$, and

  3. (3)

If $a_{s}=1/|S|$ for all $s\in S$, then $S$ is a _combinatorial $k$-graphical
design_.

We will often abbreviate $k$-graphical designs as $k$-designs. We note that
there are two kinds of weights at play in our setup: the edge weights $w$
which come with the graph, and the vertex weights $a_{s}$ which define the
graphical design. Further, there are 3 types of vertex weights, as in
Definition 2.3: arbitrary, positive, and combinatorial. We will only consider
positively weighted or combinatorial designs.

We establish some notation which allows us to simplify the definition of a
graphical design. The support of a vector $a\in{\mathbb{R}}^{n}$ is
$\operatorname{supp}(a):=\\{i\in[n]\,:\,a_{i}\neq 0\\}$. A graphical design
$S$ with weights $a_{s}$ may be identified with the vector
$a\in{\mathbb{R}}^{n}$ where $S=\operatorname{supp}(a)$. Let
$U\in{\mathbb{R}}^{n\times n}$ denote a matrix whose rows are an orthogonal
eigenbasis from $G$, let $\boldsymbol{k}=\\{2,\ldots,k\\}$, and let
$U_{\boldsymbol{k}}\in{\mathbb{R}}^{(\sum_{i=2}^{k}\dim\Lambda_{k})\times n}$
denote the submatrix of $U$ consisting of the eigenvectors which are bases for
the eigenspaces indexed by $\boldsymbol{k}$. For a subset $S\subseteq[n]$,
define its indicator vector $\mathbbm{1}_{S}$ by $\mathbbm{1}_{S}(i)=1$ if
$i\in S$ and 0 otherwise. In this paper, we will not be concerned about the
scaling of design weights as explained in the proof of the following lemma.

######  Lemma 2.4.

A set $S\subseteq[n]$ with weights $a_{s},\ s\in S$ is a positively weighted
$k$-graphical design of $G=([n],E,w)$ if and only if $U_{\boldsymbol{k}}a=0$,
$a\geq 0$, and $\operatorname{supp}(a)=S$. If further $a=\mathbbm{1}_{S}$,
then $S$ is a combinatorial $k$-graphical design.

###### Proof.

Recall that $\Lambda_{1}=\operatorname{span}\\{\mathbbm{1}\\}$. The global
average of any eigenvector in $\Lambda_{2},\ldots,\Lambda_{k}$ is 0 since
$\frac{1}{n}U_{\boldsymbol{k}}\mathbbm{1}=0$ by the orthogonality of
eigenspaces. Thus if $S=\operatorname{supp}(a)$, the condition
$U_{\boldsymbol{k}}a=0$ is equivalent to saying $S$ averages
$\Lambda_{2},\ldots,\Lambda_{k}$ with weights $a_{s}$. For any weight vector
$a$ with $\mathbbm{1}^{\top}a\neq 0$, a scaling of $a$ averages
$\Lambda_{1}=\operatorname{span}\\{\mathbbm{1}\\}$:

$\left(\frac{a}{\mathbbm{1}^{\top}a}\right)^{\top}\mathbbm{1}=1=\frac{1}{n}\mathbbm{1}^{\top}\mathbbm{1}.$

Moreover, such a scaling does not impact whether a subset $S$ averages any of
$\Lambda_{2},\ldots,\Lambda_{k}$. Thus we only care about weight vectors up to
scaling. Since $a\geq 0$ implies that $a$ is not orthogonal to $\mathbbm{1},$
it follows that $S\subseteq[n]$ with weights $a_{s},\ s\in S$ is a positively
weighted $k$-design of $G=([n],E,w)$ if and only if $U_{\boldsymbol{k}}a=0$,
$a\geq 0$, and $\operatorname{supp}(a)=S$. If additionally
$a=\mathbbm{1}_{S}$, then $S$ is a combinatorial $k$-design. ∎

######  Example 2.5.

Consider the graph from Example 2.1 shown in Figure 1 with eigenspaces ordered
as labeled: $\Lambda_{1}<\Lambda_{2}<\ldots<\Lambda_{6}$. Choosing vertex
weights

$a_{1}=a_{3}=.0342,\,a_{2}=.1111,\,a_{6}=.5328,\,a_{8}=.2876,$

we see that $S=\\{1,2,3,6,8\\}$ averages the basis vectors given for the first
four eigenspaces of this graph. Thus these vertices with these weights form a
positively weighted $4$-graphical design. Using Lemma 2.4, we can also see
that the corresponding vector $a=(.0342,.1111,.0342,0,0,.5328,0,.2876,0)$ lies
in the kernel of $U_{\boldsymbol{4}}$, where we recall that
$\boldsymbol{4}=\\{2,3,4\\}$ and $U_{\boldsymbol{4}}$ consists of the rows of
Table 1 corresponding to $\\{\lambda_{2},\lambda_{3},\lambda_{4}\\}.$ We
depict this design in Figure 2. In this ordering of eigenspaces, there are no
combinatorial 4-designs.

123456789 Figure 2. A positively weighted 4-graphical design on a positively
weighted graph. A more saturated color on a vertex indicates a larger vertex
weight in the design.

##  3\. Eigenpolytopes and Graphical Designs

We now use Gale duality to construct polytopes whose faces are in bijection
with $k$-designs, extending the results in [BT22] for unweighted regular
graphs to positively weighted graphs without regularity assumptions. We begin
with a brief introduction to Gale duality, due to [Gal56]; see [Zie95, Grü03]
for more details.

A _vector configuration_
$\mathcal{U}=\\{u_{1},\ldots,u_{n}\\}\subset{\mathbb{R}}^{d}$ is a collection
of vectors, with possible repetitions. We denote the matrix
$\begin{bmatrix}u_{1}&u_{2}&\cdots&u_{n}\end{bmatrix}\in{\mathbb{R}}^{d\times
n}$ by $U$. A dependence on $\mathcal{U}$ is a vector $a\in{\mathbb{R}}^{n}$
such that $Ua=0$. A support-minimal dependence on $\mathcal{U}$ is called a
_circuit_ of $\mathcal{U}$.

######  Theorem 3.1 (Gale Duality).

Suppose

$\mathcal{U}=\\{u_{1},\ldots,u_{n}\\}\subset{\mathbb{R}}^{d}\textup{ and
}\mathcal{U}^{*}=\\{u^{*}_{1},\ldots,u^{*}_{n}\\}\subset{\mathbb{R}}^{n-d}$

are vector configurations satisfying the following properties.

  1. (1)

$U$ and $U^{*}$ are full rank matrices.

  2. (2)

$U(U^{*})^{\top}=0$

  3. (3)

$\mathbbm{1}$ is the first row of $U^{*}$.

Then, for any $I\subseteq[n]$,
$\operatorname{conv}\\{u_{i}^{\ast}:i\in[n]\setminus I\\}$ is a face of
$P^{*}=\operatorname{conv}(\mathcal{U}^{\ast})$ if and only if $0$ is in the
relative interior of $\operatorname{conv}\\{u_{i}:i\in I\\}$.

For an index set $I\subseteq[n]$, $0$ is in the relative interior of
$\operatorname{conv}\\{u_{i}:i\in I\\}$ if and only if there exists $c\geq 0$
with $\operatorname{supp}(c)=I$ and $Uc=0$. Equivalently $c$ is a positive
dependence of $\mathcal{U}$ with $\operatorname{supp}(c)=I$. Therefore we have
the following consequence.

######  Corollary 3.2.

Let $\mathcal{U}$ and $\mathcal{U}^{*}$ be as in Theorem 3.1. For any
$I\subseteq[n]$, $\operatorname{conv}\\{u_{i}^{\ast}:i\in[n]\setminus I\\}$ is
a face (facet) of $P^{\ast}=\operatorname{conv}(\mathcal{U}^{\ast})$ if and
only if $I$ is the support of a positive dependence (circuit) of
$\mathcal{U}$.

We now have the tools to connect $k$-graphical designs to polytopes arising
from the eigenspaces of $G$. For any index set
$\boldsymbol{\lambda}\subseteq[m]$, let $U_{\boldsymbol{\lambda}}$ denote the
submatrix of $U$ containing the rows of $U$ corresponding to the eigenspaces
indexed by $\boldsymbol{\lambda}$. Let
$\mathcal{U}_{\boldsymbol{\lambda}}\subset{\mathbb{R}}^{\sum_{i\in\boldsymbol{\lambda}}\dim(\Lambda_{i})}$
denote the vector configuration given by the columns of
$U_{\boldsymbol{\lambda}}$, and let
$P_{\boldsymbol{\lambda}}=\operatorname{conv}(\mathcal{U}_{\boldsymbol{\lambda}})$.

######  Definition 3.3.

Let $G=([n],E,w)$ have $m$ Laplacian eigenspaces, and let
$\boldsymbol{\lambda}\subset[m]$ index a set of Laplacian eigenvalues of $G$.
The polytope
$P_{\boldsymbol{\lambda}}=\operatorname{conv}(\mathcal{U}_{\boldsymbol{\lambda}})$
is a Laplacian eigenpolytope of $G$ associated to $\boldsymbol{\lambda}$.

The polytopes $P_{\boldsymbol{\lambda}}$ are generalizations of eigenpolytopes
as first defined by Godsil in [God78] for single eigenspaces of the adjacency
matrix $A$. Padrol and Pfeifle in [PP10] considered Laplacian eigenpolytopes,
which are eigenpolytopes arising from single eigenspaces of $L=D-A$. Our
eigenpolytopes $P_{\boldsymbol{\lambda}}$ are more general in the sense that
they correspond to multiple eigenvalues of $L$ and allow for weighted graphs.
Though the definition depends on a choice of eigenbasis, eigenpolytopes of a
graph are well defined up to combinatorial type, which is sufficient for our
purposes. Recall that we have defined the particular index set
$\boldsymbol{k}=\\{2,\ldots,k\\}$. Let
$\overline{\boldsymbol{k}}=\\{1,k+1,\ldots,m\\}$ be the complement of
$\boldsymbol{k}$ in $[m]$.

######  Theorem 3.4.

Let $G=([n],E,w)$ be a connected weighted graph with $m$ eigenspaces ordered
$\Lambda_{1}<\ldots<\Lambda_{m}$. A set $S\subseteq[n]$ is a (minimal)
positively weighted $k$-graphical design of $G$ if and only if $[n]\setminus
S$ indexes the elements of $\mathcal{U}_{\overline{\boldsymbol{k}}}$ which lie
on a face (facet) of the polytope $P_{\overline{\boldsymbol{k}}}$.

###### Proof.

Lemma 2.4 states that the positively weighted $k$-graphical designs of $G$ are
positive dependences on the matrix $U_{\boldsymbol{k}}$. The matrices
$U_{\boldsymbol{k}}$ and $U_{\overline{\boldsymbol{k}}}$ satisfy the
hypothesis of Corollary 3.2: they are full rank, the first row of
$U_{\overline{\boldsymbol{k}}}$ is $\mathbbm{1}$, and by the orthogonality of
eigenspaces, $U_{\boldsymbol{k}}U_{\overline{\boldsymbol{k}}}^{\top}=0.$
Therefore the faces (facets) of $P_{\overline{\boldsymbol{k}}}$ are dual to
the dependences (circuits) of $\mathcal{U}_{\boldsymbol{k}}$ in the sense of
Gale duality: $S$ indexes the elements of
$\mathcal{U}_{\overline{\boldsymbol{k}}}$ lying on a face (facet) of
$P_{\overline{\boldsymbol{k}}}$ if and only if $[n]\setminus S$ indexes the
support of a (minimal) dependence on $\mathcal{U}_{\boldsymbol{k}}$. ∎

######  Example 3.5.

Consider again the positively weighted $4$-graphical design shown in Example
2.5 defined by the vector $a=(.0342,.1111,.0342,0,0,.5328,0,.2876,0)$. Since
$U_{\boldsymbol{4}}a=0$, this design is indeed a positive dependence on the
matrix $U_{\boldsymbol{4}}$ shown in Figure 3. This dependence is also support
minimal, that is, it is a circuit. Figure 3 shows the eigenpolytope
$P_{\overline{\boldsymbol{4}}}$ and the facet corresponding to this design.

$\begin{bmatrix}{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}-.6262}&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}.5616}&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}.0646}&-.0264&.2560&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}-.2291}&-.3059&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color<EMAIL_ADDRESS>{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}-.2870}&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}-.3988}&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}.6858}&-.2798&.1171&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}.1627}&-.1402&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color<EMAIL_ADDRESS>{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}.3193}&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}.3193}&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}.3193}&.1406&.1406&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}.1406}&-.4600&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color<EMAIL_ADDRESS>{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}.3248}&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}-.4014}&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}.0766}&.0507&.2150&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}-.2658}&-.4852&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color<EMAIL_ADDRESS>{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}.2760}&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}.1433}&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}-.4193}&-.2776&.1827&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}.0949}&-.4123&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color<EMAIL_ADDRESS>\end{bmatrix}$

123456789

Figure 3. The matrix $U_{\boldsymbol{4}}$ and its Gale dual eigenpolytope
$P_{\overline{\boldsymbol{4}}}$. The cyan facet of
$P_{\overline{\boldsymbol{4}}}$ indexed by $F=\\{4,5,7,9\\}$ corresponds to
the circuit of $U_{\boldsymbol{4}}$ with support $\\{1,2,3,6,8\\}=[9]\setminus
F$ shown in cyan in the matrix $U_{\boldsymbol{4}}$ above. The support of the
corresponding design on the graph is shown in cyan in Figure 2.

######  Remark 3.6.

The theory established in this section remains true if $D-A$ is replaced by
any symmetric operator which has
$\Lambda_{1}=\operatorname{span}\\{\mathbbm{1}\\}$ as an eigenspace; for
instance, the symmetric normalized adjacency matrix $D^{-1/2}AD^{-1/2}$. See
[Chu97] for more on various graph operators.

######  Remark 3.7.

One could also define graphical designs for positively weighted graphs using
the eigenvectors of $AD^{-1}$, however, the framework provided by Gale duality
and eigenpolytopes does not immediately apply. If the graph is not regular,
the eigenspaces of $AD^{-1}$ need not be orthogonal, hence the matrices
$U_{\boldsymbol{k}}$ and $U_{\overline{\boldsymbol{k}}}$ need not satisfy the
conditions of Theorem 3.1. This can be worked around with some care if one
considers the dual configurations given by $U_{\boldsymbol{k}}$ and
$U_{\overline{\boldsymbol{k}}}D^{-1}$. There are many details to this, which
we do not elaborate on here.

######  Example 3.8.

We depict two more eigenpolytopes of our running example (Example 2.1) with
distinguished facets and show the supports of the corresponding positively
weighted graphical designs in Figures 4 and 5.

Figure 4. The eigenpolytope $P_{\\{1,2\\}}$ and the design corresponding to
the facet $\\{2,3\\}$, averaging all but $\Lambda_{2}$. Figure 5. The
eigenpolytope $P_{\\{1,3,4\\}}$ and the design corresponding to the facet
$\\{7,8,9\\}$ averaging $\Lambda_{1},\Lambda_{2},\Lambda_{5},\Lambda_{6}$. The
vertices $4,5$ and $6$ lie in the interior of $P_{\\{1,3,4\\}}$, which we note
is an octohedron.

We show in Section 6 that the eigenpolytopes of positively weighted graphs are
completely general – that is, for an $n$-vertex polytope $P$, there is a
positively weighted graph $G=([n],E,w)$ for which an eigenpolytope of $G$ is
combinatorially equivalent to $P$.

Theorem 3.4 provides an upper bound to the size of a $k$-graphical design,
similar to [BT22, Theorem 3.14]. Further, no proper subset can average all
eigenspaces of a positively weighted graph – this follows by the same argument
as in [BT22, Lemma 2.5]. If a graph has $m$ eigenspaces, the only $m$-design
is given by the weight vector $\mathbbm{1}$. Hence we never search for
$m$-designs.

######  Theorem 3.9.

Let $G=([n],E,w)$ be a connected weighted graph with eigenspaces
$\Lambda_{1}<\cdots<\Lambda_{m}$, let $\dim\Lambda_{i}=d_{i}$, and let
$s_{k}:=\sum_{i=1}^{k}d_{i}$. Then for every $k\in[m-1]$ there is a positively
weighted $k$-design with at most $s_{k}$ vertices.

###### Proof.

The Laplacian eigenpolytope $P_{\overline{\boldsymbol{k}}}$ has dimension
$\sum_{i=k+1}^{m}d_{i}=n-s_{k}$. Any facet of $P_{\overline{\boldsymbol{k}}}$
has at least $n-s_{k}$ distinct vertices. By the correspondence established in
Theorem 3.4, any minimal positively weighted $k$-design has at most $s_{k}$
vertices. ∎

We note that this bound may be tight. The example of an unweighted regular
graph and an eigenspace ordering for which this bound is tight for every $k$
given in [BT22, Example 3.16] is also valid here.

######  Example 3.10.

We return to our running example for the last time. In the ordering specified
in Example 2.5, Theorem 3.9 states that a minimal positively weighted 4-design
has at most $9-(1+2)=6$ vertices. The eigenpolytope
$P_{\overline{\boldsymbol{4}}}$ shown in Figure 3 has two triangular facets
and six quadrilateral facets. The quadrilateral facets correspond to minimal
designs with $5$ vertices, which is smaller than the facet bound of Theorem
3.9. We recall that a polytope is _simplicial_ if all of its facets are
simplices. The eigenpolytopes shown in Figures 4 and 5 are both simplicial,
implying this bound is tight for the graphical designs corresponding to those
eigenpolytopes.

##  4\. Examples

We illustrate the power of Theorem 3.4 on two examples, and use them to
comment on connections with graph sampling and clustering.

######  Example 4.1.

Consider the unweighted graph (i.e. a weighted graph with $w=\mathbbm{1}$) and
its Laplacian shown in Figure 6.

123456 $\displaystyle L=\begin{bmatrix}1&0&0&-1&0&0\\\ 0&3&0&-1&-1&-1\\\
0&0&3&-1&-1&-1\\\ -1&-1&-1&5&-1&-1\\\ 0&-1&-1&-1&3&0\\\
0&-1&-1&-1&0&3\end{bmatrix}$ Figure 6. An unweighted graph on 6 vertices and
its Laplacian.

Here is its spectrum and an orthogonal basis of eigenvectors.

$\begin{array}[]{c|cccccc|}\lambda_{1}=0&1&1&1&1&1&1\\\
\hline\cr\lambda_{2}=1&4&-1&-1&0&-1&-1\\\
\hline\cr\lambda_{3}=3&0&1&-1&0&0&0\\\ &0&0&0&0&1&-1\\\
\hline\cr\lambda_{4}=5&0&1&1&0&-1&-1\\\ \hline\cr\lambda_{5}=6&1&1&1&-5&1&1\\\
\end{array}$

We first consider the eigenpolytope $P_{\\{1,3\\}}$ shown in Figure 7. The
elements of $\mathcal{U}_{\\{1,3\\}}$ indexed by $1$ and $4$ lie in the
interior of this eigenpolytope. Therefore, if $\Lambda_{3}$ is ordered last,
every $4$-graphical design must contain the vertices $1$ and $4$ since they
are in the complement of every facet index set. This indicates that $1$ and
$4$ are ‘important’ graph vertices to sample from. Indeed, it would make sense
to sample at $4$, which is connected to every other vertex, and $1$, which is
the only vertex of degree 1 and hence less dependent on the information at
other vertices. We can also examine the circuits on the dual configuration
$\mathcal{U}_{\\{2,4,5\\}}$ for an explanation. To average $\Lambda_{5}$, we
must pick out $-5$ from $U_{\\{5\\}}$ – indexed by 4 – since it is the only
negative entry for that eigenvector. Similarly, to average $\Lambda_{2}$, we
must pick out $4$ from $U_{\\{2\\}}$ – indexed by 1 – since it is the only
positive entry.

We also note the symmetry in the graphical designs shown in Figure 7. In some
sense the vertices $\\{2,3\\}$ and $\\{5,6\\}$ play the same role – any choice
of one vertex from each set along with 1 and 4 provides a minimal graphical
design.

1,42356 123456123456123456123456 Figure 7. The eigenpolytope $P_{\\{1,3\\}}$
and the supports of the minimal designs corresponding to each facet, which
average all but $\Lambda_{3}$.

We depict a selection of other eigenpolytopes and the supports of the
corresponding positively weighted graphical designs in Figures 8, 9, and 10.
We see likewise in Figures 8 and 9 that $4$ lies in the interior of the
eigenpolytopes $P_{\\{1,2\\}}$ and $P_{\\{1,2,3\\}}$, hence must be in the
support of each of the corresponding graphical designs.

In Figure 10, we see that $4$ does not lie in the interior of
$P_{\\{1,4,5\\}}$. The single vertex $4$ is the support of a minimal design,
and any design consisting of a single vertex is combinatorial. The complement
of a combinatorial design is also a combinatorial design ([BT22, Lemma 2.4]),
hence $4$ and $\\{1,2,3,5,6\\}$ must lie on disjoint faces. Hence no vertex is
in the interior of this polytope.

Figure 8. The eigenpolytope $P_{\\{1,2\\}}$ and the graphical design
corresponding to the facet $\\{2,3,5,6\\}$ which averages all but
$\Lambda_{2}$. Figure 9. The eigenpolytope $P_{\\{1,2,3\\}}$ and the design
corresponding to the facet $\\{2,3,5,6\\}$ which averages
$\Lambda_{1},\Lambda_{4},\Lambda_{5}$. Figure 10. The eigenpolytope
$P_{\\{1,4,5\\}}$ and the design corresponding to the facet $\\{1,2,3,5,6\\}$
which averages $\Lambda_{1},\Lambda_{2},\Lambda_{3}$.

We state the observations made in the previous example generally.

######  Remark 4.2.

Fix an ordering $\Lambda_{1},\ldots,\Lambda_{m}$ of a graph $G=([n],E,w)$. The
$i$-th element of $\mathcal{U}_{\overline{\boldsymbol{k}}}$ lies in the
interior of the eigenpolytope $P_{\overline{\boldsymbol{k}}}$ if and only if
$i$ is in the support of every $k$-graphical design.

######  Remark 4.3.

Fix an ordering $\Lambda_{1},\ldots,\Lambda_{m}$ of a graph $G=([n],E,w)$. If
$S\subset[n]$ is a combinatorial $k$-design, then $S$ and $[n]\setminus S$
partition $P_{\overline{\boldsymbol{k}}}$ into two disjoint faces. Therefore,
if $G$ has a combinatorial $k$-design, no vertices lie in the interior of
$P_{\overline{\boldsymbol{k}}}$. We speculate that the symmetry needed for a
combinatorial design to exist precludes the possibility that a graph vertex is
‘so important’ that it lies in every design.

######  Example 4.4.

Consider the barbell graph on $2n$ vertices, which consists of two copies of
$K_{n}$ joined by a single edge. We denote this graph by $B_{n}$ and exhibit
$B_{3}$ in Figure 11. We label one clique of the barbell with $[n]$, where the
vertex $n$ is connected to $n+1$ in the other clique. We examine what happens
to the graphical designs and eigenpolytopes of $B_{n}$ as the weight $w$ on
the single connecting edge is allowed to vary. The Laplacian of $B_{n}$ is

$\left(\begin{array}[]{@{}c|c@{}}\begin{matrix}n-1&-1&\ldots&-1\\\
-1&n-1&\ldots&-1\\\ \vdots&&&\vdots\\\
-1&\ldots&-1&n-1+w\end{matrix}&\begin{matrix}0&&&\ldots&&&&0\\\
\vdots&&&&&&&\vdots\\\ 0&&&\ldots&&&&0\\\ -w&0&&\ldots&&&&0\end{matrix}\\\
\hline\cr\begin{matrix}0&&&\ldots&&&0&-w\\\ 0&&&\ldots&&&&0\\\
\vdots&&&&&&&\vdots&\\\
0&&&\ldots&&&&0\end{matrix}&\begin{matrix}n-1+w&-1&\ldots&-1\\\
-1&n-1&\ldots&-1\\\ \vdots&&&\vdots\\\
-1&\ldots&-1&n-1\end{matrix}\end{array}\right).$

123456$1$$1$$1$$w$$1$$1$$1$ Figure 11. The barbell graph $B_{3}$ with equal
edge weights on the maximum cliques and a variable weight $w$ on the
connecting edge.

The graph $B_{n}$ has the following spectral information.

  * •

$\Lambda_{1}=\operatorname{span}\\{\mathbbm{1}\\}$ has eigenvalue 0.

  * •

$\Lambda_{2}=\operatorname{span}\\{[\mathbbm{1}_{n-1},\alpha,-\alpha,-\mathbbm{1}_{n-1}]\\}$
has eigenvalue $1-\alpha$, where

$\alpha=\frac{-(2w+n-2)+\sqrt{(2w+n-2)^{2}+4(n-1)}}{2}$

  * •

$\Lambda_{3}=\operatorname{span}\\{\\{e_{i}-e_{i+1},e_{n+1+i}-e_{n+2+i}\\}_{i=1}^{n-2},[\mathbbm{1}_{n-1},1-n,1-n,\mathbbm{1}_{n-1}]\\}$
has eigenvalue $n$ and multiplicity $2n-3$.

  * •

$\Lambda_{4}=\operatorname{span}\\{[\mathbbm{1}_{n-1},\beta,-\beta,-\mathbbm{1}_{n-1}]\\}$
has eigenvalue $1-\beta$, where

$\beta=\frac{-(2w+n-2)-\sqrt{(2w+n-2)^{2}+4(n-1)}}{2}$

We note that $\dim\Lambda_{1}=\dim\Lambda_{2}=\dim\Lambda_{4}=1$. As $w\to 0$,
$\alpha\to 1$ and $\beta\to 1-n$. Thus $\Lambda_{2}$ collapses into the
eigenspace $\Lambda_{1}$ with eigenvalue 0, and $\Lambda_{4}$ collapses into
$\Lambda_{3}$ with eigenvalue $n$. This agrees with the spectrum of
$K_{n}\sqcup K_{n}$. As $w\to\infty$, $\alpha\to 0$ and $\beta\to-\infty$.
Since $\alpha$ and $\beta$ are both strictly decreasing in $w$, the
eigenvalues satisfy $\lambda_{2}=1-\alpha\in(0,1)$ and $\lambda_{3}=1-\beta>n$
for $w>0$. We examine all the graphical designs and eigenpolytopes of this
graph systematically for $w>0$.

  * •

The eigenpolytope $P_{\\{1,2\\}}$ is the line segment $[-1,1]$, where the
facet $\\{-1\\}$ is indexed by $[2n]\setminus[n+1]$ and the facet $\\{1\\}$ is
indexed by $[n-1]$. Hence there are two positively weighted $3$-graphical
designs with $\Lambda_{2}$ ordered last, one supported on $[n+1]$ and the
other supported on $[2n]\setminus[n-1]$. For $B_{3}$, this means the two
minimal positively weighted designs have support $\\{1,2,3,4\\}$ and
$\\{3,4,5,6\\}$.

  * •

Similarly, the eigenpolytope $P_{\\{1,4\\}}$ is the line segment
$[\beta,-\beta]$, where the facet $\\{\beta\\}$ is indexed by $n-1$ and the
facet $\\{-\beta\\}$ is indexed by $n$. Hence there are two positively
weighted $3$-graphical designs with $\Lambda_{4}$ ordered last, one supported
on $[2n]\setminus\\{n\\}$ and the other supported on $[2n]\setminus\\{n+1\\}$.
For $B_{3}$, this means the two minimal positively weighted designs have
support $\\{1,2,3,5,6\\}$ and $\\{1,2,4,5,6\\}$.

  * •

$P_{\\{1,3\\}}$ is a $(2n-3)$-dimensional polytope with $2n$ vertices. There
are exponentially many combinatorial types of $d$-dimensional polytopes with
$d+3$ vertices ([Llo70, Fus06]), so it may be difficult to classify
$P_{\\{1,3\\}}$ through its vertex description. However, the positive circuits
of

$U_{\\{2,4\\}}=\begin{bmatrix}\mathbbm{1}_{n-1}&\alpha&-\alpha&-\mathbbm{1}_{n-1}\\\
\mathbbm{1}_{n-1}&\beta&-\beta&-\mathbbm{1}_{n-1}\end{bmatrix}$

are easier to identify. From the depiction of $\mathcal{U}_{\\{2,4\\}}$ in
Figure 12, it is quick to read off that the minimal positive circuits are
given by $e_{n}+e_{n+1}$ and $e_{i}+e_{j}$, for any $i\in[n-1]$ and
$j\in[2n]\setminus[n+1].$ These minimal positive circuits are the positively
weighted $3$-graphical designs with $\Lambda_{3}$ ordered last. By Gale
duality, we see that $P_{\\{1,3\\}}$ has $(n-1)^{2}+1$ facets, each containing
$2n-2$ graph vertices. For $B_{3}$, this means the support of a minimal
positively weighted designs is one of $\\{3,4\\}$ or $\\{i,j\\}$ for any
$i\in\\{1,2\\}$, $j\in\\{5,6\\}$.

$[n-1]$$[2n]\setminus[n+1]$$\\{n\\}$$\\{n+1\\}$ Figure 12. The vector
configuration $\mathcal{U}_{\\{2,4\\}}$ labelled by the graph vertices that
provide each vector.

  * •

The eigenpolytopes $P_{\\{1,2,3\\}}$ and $P_{\\{1,3,4\\}}$ are each
$(2n-2)$-dimensional polytopes with $2n$ vertices. Every $d$-dimensional
polytope with $d+2$ vertices is an $r$-fold pyramid with a $(d-r)$-dimensional
simplicial base; see [Grü03, Section 6.1] for more on the classification of
$d$-polytopes with $d+2$ vertices. Like with $P_{\\{1,3\\}}$, we can classify
these polytopes by looking at their dual vector configurations, which are one-
dimensional. The first $n$ columns of
$U_{\\{2\\}}=[\mathbbm{1}_{n-1},\alpha,-\alpha,-\mathbbm{1}_{n-1}]$ are
positive, and the last $n$ columns are negative. Thus any positive circuit has
support $\\{i,j\\}$ where $i\in[n]$ and $j\in[2n]\setminus[n]$. For $B_{3}$,
this means the support of the design is $\\{i,j\\}$ where $i\in\\{1,2,3\\}$
and $j\in\\{4,5,6\\}$. Generally, $P_{\\{1,3,4\\}}$ is simplicial.

We likewise see from
$U_{\\{4\\}}=[\mathbbm{1}_{n-1},\beta,-\beta,-\mathbbm{1}_{n-1}]$ that
$P_{\\{1,2,3\\}}$ is simplicial and its facets are of the form
$F=\operatorname{conv}([2n]\setminus\\{i,j\\}:i\in\\{1,\ldots,n-1,n+1\\},j\in\\{n,n+2,\ldots
2n\\})$. For $B_{3}$, this means the support of the design is $\\{i,j\\}$
where $i\in\\{1,2,4\\}$ and $j\in\\{3,5,6\\}$.

  * •

The eigenpolytope $P_{\\{1,2,4\\}}$ is a parallelogram with vertices $(1,1)$
and $(-1,-1)$ corresponding to the first and last $n-1$ graph vertices
respectively, and vertices $(\alpha,\beta)$ and $(-\alpha,-\beta)$
corresponding to $n$ and $n+1$ respectively as graph vertices. By the
bijection established in Theorem 3.4, it follows that a minimal positively
weighted $2$-graphical design in the ordering
$\Lambda_{1}<\Lambda_{3}<\Lambda_{2}<\Lambda_{4}$ has one of the following
supports: $[n],[n-1]\cup\\{n+1\\},[2n]\setminus[n],\\{n-1,n+1,\ldots 2n\\}.$

We can also see this by examining the eigenspace $\Lambda_{3}$ directly. For
$n>3$, let $a\in{\mathbb{R}}^{2n}$ average $\Lambda_{3}$. If $i\in[n-1]$ is in
the support of $a$, it must be that $a_{1}=a_{2}=\ldots=a_{n-1}$ since $a$
averages the vectors $\\{e_{i}-e_{i+1}\\}_{i=1}^{n-2}$. Thus
$i+1\in\operatorname{supp}(a)$ as well. Since $a$ also averages
$[\mathbbm{1}_{n-1},1-n,1-n,\mathbbm{1}_{n-1}]$, either $n$ or $n+1$ are in
the support of $a$. By symmetry, we then see the minimal positive vectors
averaging this eigenspace are
$[\mathbbm{1}_{n},0_{n}],[\mathbbm{1}_{n-1},0,1,0_{n-1}],[0_{n},\mathbbm{1}_{n}][0_{n-1},1,0,\mathbbm{1}_{n-1}]$.
Thus these minimal positively weighted designs are also combinatorial. This
implies for $B_{3}$ that the support of a minimal positively weighted designs
is one of $\\{1,2,3\\}$, $\\{1,2,4\\}$, $\\{3,5,6\\}$, or $\\{4,5,6\\}$.

######  Remark 4.5.

The eigenpolytope $P_{\\{1,3,4\\}}$ and the corresponding 2-graphical designs
detect clustering in the barbell graph. That is, the graphical designs which
average $\Lambda_{2}$ will consist of one vertex in each clique of the barbell
graph, regardless of the weight $w$. More generally, if $G=([n],E,w)$ has $k$
clusters, a design which averages the $k$ Laplacian eigenvectors with
eigenvalues nearest 0 will consist of one vertex from each cluster. We plan to
expand on this in future work.

##  5\. Constructing Graphs From Polytopes

In Section 3, we saw that a weighted graph gives rise to a class of polytopes
via its spectral information, namely its eigenpolytopes. In this section, we
show that any combinatorial polytope can appear as an eigenpolytope of a
positively weighted graph. In the next section, we use this universality of
eigenpolytopes to establish complexity results for the graphical design
problem.

We first show that any orthonormal basis for ${\mathbb{R}}^{n}$ which includes
$\mathbbm{1}/\sqrt{n}$ as a basis vector, and any partition of this basis,
gives rise to a positively weighted graph $G=([n],E,w)$ where each part of the
partition spans a distinct Laplacian eigenspace of $G$. We overload the
notation $\operatorname{Diag}$; for a vector $v\in{\mathbb{R}}^{n}$,
$\operatorname{Diag}(v)\in{\mathbb{R}}^{n\times n}$ is the diagonal matrix
with $\operatorname{Diag}(v)_{ii}=v_{i}$, and for a matrix
$M\in{\mathbb{R}}^{n\times n}$,
$\operatorname{Diag}(M)\in{\mathbb{R}}^{n\times n}$ is the diagonal matrix
which forgets the off-diagonal entries of $M$.

######  Lemma 5.1.

Let
$\mathcal{B}=\\{\varphi_{1}=\mathbbm{1}/\sqrt{n},\varphi_{2},\ldots,\varphi_{n}\\}$
be an orthonormal basis of ${\mathbb{R}}^{n}$, partitioned as
$\mathcal{B}=\pi_{1}\sqcup\ldots\sqcup\pi_{m}$ with at least 2 parts such that
$\pi_{1}=\\{\mathbbm{1}/\sqrt{n}\\}$. There is a connected, positively
weighted graph $G=([n],E,w)$ with $m$ Laplacian eigenspaces
$\Lambda_{1},\ldots,\Lambda_{m}$ such that $\pi_{i}$ spans $\Lambda_{i}$. The
graph $G$ can be constructed in $\mathcal{O}(n^{3})$ time.

###### Proof.

Let $B\in{\mathbb{R}}^{n\times n}$ have $i$-th row $\varphi_{i}$. We seek a
matrix $M=\operatorname{Diag}(0,\lambda_{2},\ldots,\lambda_{n})$ with
$\lambda_{i}>0$ and $\lambda_{i}=\lambda_{j}$ if and only if $\varphi_{i}$ and
$\varphi_{j}$ lie in the same part of the partition so that $L=B^{\top}MB$ is
the Laplacian of a positively weighted graph.

Assuming such an $M$ exists, $A=\operatorname{Diag}(B^{\top}MB)-B^{\top}MB$ is
then the adjacency matrix of the desired graph $G$, which has Laplacian
eigenspaces $\Lambda_{1},\ldots\Lambda_{m}$ where $\Lambda_{i}$ is spanned by
$\pi_{i}$. We first check several properties of this construction.

  1. (1)

$L$ is positive semi-definite: We see that $L=(M^{1/2}B)^{\top}(M^{1/2}B)$.

  2. (2)

$D=\operatorname{Diag}(B^{\top}MB)$ is the degree matrix of $G$: Since
$B^{\top}MB\mathbbm{1}=0$, $D$ satisfies
$D_{ii}=(B^{\top}MB)_{ii}=-\sum_{j\neq i}(B^{\top}MB)_{ij}=\sum_{j\neq
i}A_{ij}=\deg(i)$.

  3. (3)

$G$ is connected: By construction, the multiplicity of 0 as a Laplacian
eigenvalue is 1.

  4. (4)

The matrix multiplication to compute $B^{\top}MB$ can be done in time
$\mathcal{O}(n^{3})$, from which $A$ is derived.

It remains to show that we can find an $M$ with the given properties so that
$A\geq 0$. For the rest of this proof, let $\mathbbm{1}\in{\mathbb{R}}^{n-1}$.
We will prove that such an $M$ exists by showing that
$M=\operatorname{Diag}(0,\mathbbm{1})$ lies in the interior of the constraints
imposed by $A\geq 0$, and can be perturbed to satisfy all the needed
conditions. We note that $M=\operatorname{Diag}(0,\mathbbm{1})$ corresponds to
an equally weighted complete graph and solves the problem when $m=2$. Since
$\lambda_{1}=0$,

$L=B^{\top}MB=\sum_{j=1}^{n}\lambda_{j}\varphi_{j}\varphi_{j}^{\top}=\sum_{j=2}^{n}\lambda_{j}\varphi_{j}\varphi_{j}^{\top}.$

Since we require positive edge weights, we need that for $i\neq j$,

$(A)_{ij}=-(L)_{ij}=-\sum_{k=2}^{n}\varphi_{k}(i)\varphi_{k}(j)\lambda_{k}\geq
0.$

This gives us a system of $n(n-1)/2$ linear inequalities constraining the
choice of $\lambda_{2},\ldots,\lambda_{n}$. Represent this system as
$C\lambda\geq 0$, where
$\lambda=(\lambda_{2},\ldots,\lambda_{n})\in{\mathbb{R}}^{n-1}$ and
$C\in{\mathbb{R}}^{n(n-1)/2\times(n-1)}$. We note that
$K=\\{\lambda\in{\mathbb{R}}^{n-1}:C\lambda\geq 0\\}$ is a polyhedral cone.
Let
$c=(-\varphi_{2}(i)\varphi_{2}(j),\ldots,-\varphi_{n}(i)\varphi_{n}(j))^{\top}$
be some row of $C$. Since $\mathcal{B}$ is orthonormal, the columns of $B$ are
orthogonal. Therefore,

$\displaystyle 0$
$\displaystyle=\left(\frac{1}{\sqrt{n}},\varphi_{2}(i),\cdots,\varphi_{n}(i)\right)\left(\frac{1}{\sqrt{n}},\varphi_{2}(j),\cdots,\varphi_{n}(j)\right)^{\top}$
$\displaystyle=\frac{1}{n}+\sum_{k=2}^{n}\varphi_{k}(i)\varphi_{k}(j)=\frac{1}{n}-c^{\top}\mathbbm{1}.$

Hence $c^{\top}\mathbbm{1}=\frac{1}{n}>0$. Since $c$ was an arbitrary row of
$C$, we see that $C\mathbbm{1}>0$, implying that the ray spanned by
$\mathbbm{1}$ lies in the interior of $K$.

$c^{\top}\lambda\geq 0$$c$$\mathbbm{1}$$d_{c}$$\theta_{c}$$\theta_{c}$ Figure
13. Computing the distance from $\mathbbm{1}$ to $\partial K$

Thus there is an $\varepsilon$-neighborhood of $\mathbbm{1}$ contained in $K$.
Let $\theta_{c}$ be the angle between $\mathbbm{1}$ and $c$. Observe from
Figure 13 that the distance between $\mathbbm{1}$ and the hyperplane
$c^{\top}\lambda\geq 0$ is

$d_{c}=\|\mathbbm{1}\|\cos\theta_{c}=\|\mathbbm{1}\|\cdot\frac{c^{\top}\mathbbm{1}}{\|c\|\|\mathbbm{1}\|}=\frac{1}{n\|c\|}>0.$

Then such $\varepsilon$ can be computed in $\mathcal{O}(n^{2})$ time as the
minimum over all possible $d_{c}$’s, multiplied by some constant $\alpha<1$
(e.g. $\alpha=0.99$). For $k=2,\ldots,n$, if $\varphi_{j}\in\pi_{k}$, define
$\lambda_{j}\coloneqq 1+\delta_{j}$, where
$\delta_{j}=\frac{\sqrt{k}\varepsilon}{n}$. Note that
$\sum_{k=2}^{m}|\pi_{k}|=|\mathcal{B}|-1=n-1$. Then,

$\displaystyle\left\|\lambda-\mathbbm{1}\right\|=\frac{\varepsilon}{n}\left(\sum_{k=2}^{m}k|\pi_{k}|\right)^{\frac{1}{2}}\leq\frac{\varepsilon}{n}\left(n\sum_{k=2}^{m}|\pi_{k}|\right)^{\frac{1}{2}}=\frac{\varepsilon}{n}\left(n(n-1)\right)^{\frac{1}{2}}<\varepsilon.$

By construction, $\lambda>0$ since it is in the $\varepsilon$-neighborhood of
$\mathbbm{1}$, and $\lambda$ satisfies the requirements imposed by the given
partition of $\mathcal{B}$. Thus we have found the desired matrix
$M=\operatorname{Diag}(0,\lambda_{2},\ldots,\lambda_{n})$. ∎

######  Example 5.2.

Consider the orthonormal basis of ${\mathbb{R}}^{4}$

$\left\\{\varphi_{1}=\frac{1}{2}\begin{pmatrix}1\\\ 1\\\ 1\\\
1\end{pmatrix},\varphi_{2}=\frac{1}{\sqrt{2}}\begin{pmatrix}1\\\ -1\\\ 0\\\
0\end{pmatrix},\varphi_{3}=\frac{1}{\sqrt{6}}\begin{pmatrix}1\\\ 1\\\ -2\\\
0\end{pmatrix},\varphi_{4}=\frac{1}{2\sqrt{3}}\begin{pmatrix}1\\\ 1\\\ 1\\\
-3\end{pmatrix}\right\\}$

and the partition
$\mathcal{B}=\\{\varphi_{1}\\}\sqcup\\{\varphi_{2}\\}\sqcup\\{\varphi_{3},\varphi_{4}\\}$.
Following the algorithm of Lemma 5.1, we obtain the constraint matrix

$C=\begin{bmatrix}1/2&-1/6&-1/12\\\ 0&1/3&-1/12\\\ 0&0&1/4\\\ 0&1/3&-1/12\\\
0&0&1/4\\\ 0&0&1/4\end{bmatrix}.$

Then we seek $\varepsilon$ less than

$\min_{\text{row $c$ of
$C$}}\frac{1}{4\|c\|}=\min\left\\{\frac{3}{\sqrt{41}},\frac{3}{\sqrt{17}},1,\frac{3}{\sqrt{17}},1,1\right\\}=\frac{3}{\sqrt{41}}.$

We choose $\varepsilon=1/3$. This yields
$(\lambda_{2},\lambda_{3},\lambda_{4})=(1+\frac{\sqrt{2}}{12},1+\frac{\sqrt{3}}{12},1+\frac{\sqrt{3}}{12})$
as a feasible choice of nonzero eigenvalues. We check that

$\displaystyle
B^{\top}\operatorname{Diag}(0,\lambda_{2},\lambda_{3},\lambda_{4})B$
$\displaystyle=\frac{1}{144}\begin{pmatrix}108+6\sqrt{2}+3\sqrt{3}&-36-6\sqrt{2}+3\sqrt{3}&-36-3\sqrt{3}&-36-3\sqrt{3}\\\
-36-6\sqrt{2}+3\sqrt{3}&108+6\sqrt{2}+3\sqrt{3}&-36-3\sqrt{3}&-36-3\sqrt{3}\\\
-36-3\sqrt{3}&-36-3\sqrt{3}&108+9\sqrt{3}&-36-3\sqrt{3}\\\
-36-3\sqrt{3}&-36-3\sqrt{3}&-36-3\sqrt{3}&108+9\sqrt{3}\end{pmatrix}$
$\displaystyle\approx\begin{pmatrix}0.84501&-0.272841&-0.286084&-0.286084\\\
-0.272841&0.84501&-0.286084&-0.286084\\\
-0.286084&-0.286084&0.858253&-0.286084\\\
-0.286084&-0.286084&-0.286084&0.858253\end{pmatrix}$

gives the Laplacian of a connected, positively weighted graph, shown in Figure
14. Generally, the graph from this construction will be a complete graph with
nearly equal edge weights, as its Laplacian is a small perturbation the
Laplacian of $K_{n}$.

Figure 14. A positively weighted graph with the eigenspaces given in Example
5.2. The dashed edge has weight $(36+6\sqrt{2}-3\sqrt{3})/144$, and the solid
edges have weight $(36+3\sqrt{3})/144$.

We use Lemma 5.1 to show that given a polytope $P$, we can construct a
positively weighted graph in polynomial time which has an eigenpolytope that
is combinatorially equivalent to $P$.

######  Lemma 5.3.

Let $P$ be a $d$-dimensional polytope given as the convex hull of $n$
vertices. We can create a connected, positively weighted graph $G=([n],E,w)$
which has a Laplacian eigenpolytope that is combinatorially equivalent to $P$
in $\mathcal{O}(n^{3})$ time.

###### Proof.

Let $V=\\{v_{1},\ldots,v_{n}\\}\subset{\mathbb{R}}^{d}$ and
$P=\operatorname{conv}(V)$. We may translate $P$ so that its centroid lies at
the origin by mapping $v_{i}\mapsto v_{i}-\frac{1}{n}\sum_{i=1}^{n}v_{i}$.
This preserves the combinatorial structure of $P,$ and

$\sum_{i=1}^{n}\left(v_{i}-\frac{1}{n}\sum_{i=1}^{n}v_{i}\right)=\sum_{i=1}^{n}v_{i}-n\frac{1}{n}\sum_{i=1}^{n}v_{i}=0.$

Thus, we may assume without loss of generality that $\sum_{i=1}^{n}v_{i}=0$,
or equivalently, that the rows of the matrix $[v_{1}\ldots v_{n}]$ are
orthogonal to $\mathbbm{1}.$ Let
$V^{*}=\\{v^{*}_{1},\ldots,v^{*}_{n}\\}\subset{\mathbb{R}}^{n-d-1}$ be a Gale
dual vector configuration to the polytope $P$. To find $V^{*}$, we find a
basis for the kernel of the matrix

$\begin{bmatrix}1&\ldots&1\\\ v_{1}&\ldots&v_{n}\end{bmatrix}.$

Using singular value decomposition, this takes $\mathcal{O}(n^{3})$ time. Let

${U}=\begin{bmatrix}1&\ldots&1\\\ v_{1}&\ldots&v_{n}\\\
v^{*}_{1}&\ldots&v^{*}_{n}\end{bmatrix}.$

We will think of the rows of $U$ as the Laplacian eigenvectors of the graph we
will construct. Since $P$ is $d$-dimensional, the matrix $U$ is full rank.
Perform Gram-Schmidt (an $\mathcal{O}(n^{3})$ algorithm) on the rows of $U$ to
obtain an orthonormal matrix

$\tilde{U}=\begin{bmatrix}1/\sqrt{n}&\ldots&1/\sqrt{n}\\\
u_{1}&\ldots&u_{n}\\\ u^{*}_{1}&\ldots&u^{*}_{n}\end{bmatrix}.$

Since Gram-Schmidt preserves span in a sequential manner,
$\operatorname{rowspan}[u_{1},\ldots,u_{n}]=\operatorname{rowspan}[v_{1},\ldots,v_{n}]$.
Moreover, the matrices $[u_{1},\ldots,u_{n}]$ and $[v_{1},\ldots,v_{n}]$
differ only by a change of basis, so the polytope
$\operatorname{conv}\\{u_{1},\ldots,u_{n}\\}$ is the same combinatorial type
as $P=\operatorname{conv}\\{v_{1},\ldots,v_{n}\\}$. By Lemma 5.1, we can
construct a connected positively weighted graph $G=([n],E,w)$ which has the
following 3 eigenspaces in $\mathcal{O}(n^{3})$ time:
$\Lambda_{1}=\operatorname{span}(\mathbbm{1}),\Lambda_{2}=\operatorname{rowspan}([u_{1},\ldots,u_{n}]),\Lambda_{3}=\operatorname{rowspan}([u^{*}_{1},\ldots,u^{*}_{n}]).$
Thus by definition, $P$ is combinatorially equivalent to the Laplacian
eigenpolytope of $G$ for the eigenspace $\Lambda_{2}$. ∎

######  Corollary 5.4.

Every combinatorial polytope with $n$ vertices appears as the eigenpolytope of
a positively weighted graph on $n$ vertices.

######  Example 5.5.

We illustrate Lemma 5.3 by embedding the 16-cell, also known as the
4-dimensional cross polytope, as the eigenpolytope of a connected positively
weighted graph. A centered, orthonormal embedding of the 16-cell’s vertices is

$V=\frac{1}{\sqrt{2}}\begin{bmatrix}1&0&0&0&-1&0&0&0\\\ 0&1&0&0&0&-1&0&0\\\
0&0&1&0&0&0&-1&0\\\ 0&0&0&1&0&0&0&-1\end{bmatrix}.$

We next compute an orthonormal basis for the kernel of
$[\mathbbm{1},V^{\top}]^{\top}$:

$V^{*}=\begin{bmatrix}-1/2&1/2&0&0&-1/2&1/2&0&0\\\
-\frac{1}{\sqrt{12}}&-\frac{1}{\sqrt{12}}&\frac{1}{\sqrt{3}}&0&-\frac{1}{\sqrt{12}}&-\frac{1}{\sqrt{12}}&\frac{1}{\sqrt{3}}&0\\\
-\frac{1}{\sqrt{24}}&-\frac{1}{\sqrt{24}}&-\frac{1}{\sqrt{24}}&\frac{3}{\sqrt{8}}&-\frac{1}{\sqrt{24}}&-\frac{1}{\sqrt{24}}&-\frac{1}{\sqrt{24}}&\frac{3}{\sqrt{8}}\end{bmatrix}.$

We set the eigenspace partition
$\Lambda_{1}=\operatorname{span}\\{\mathbbm{1}\\},\Lambda_{2}=\operatorname{rowspan}V,\Lambda_{3}=\operatorname{rowspan}V^{*}$.
Following the procedure in Lemma 5.1, we compute the following cone of
eigenvalues for which the resulting graph will be positively weighted.

$K=\left\\{(\lambda_{2},\lambda_{3}):\begin{bmatrix}0&1/8\\\
1/2&-3/8\end{bmatrix}\begin{bmatrix}\lambda_{2}\\\
\lambda_{3}\end{bmatrix}\geq 0\right\\}$

Thus we seek
$\varepsilon<\min\left\\{1/(4\|(0,-1/8)\|),1/(4\|(-1/2,3/8)\|)\right\\}=\frac{25}{16}$.
Picking $\varepsilon=1$, the resulting eigenvalues are
$\lambda_{2}=1+\sqrt{2}/8$ and $\lambda_{3}=1+\sqrt{3}/8$. Then
$[\mathbbm{1}/\sqrt{8},V^{\top},(V^{*})^{\top}]\operatorname{Diag}(0,\lambda_{2},\lambda_{2},\lambda_{2},\lambda_{2},\lambda_{3},\lambda_{3},\lambda_{3})[\mathbbm{1}/\sqrt{8},V^{\top},(V^{*})^{\top}]^{\top}$
is the Laplacian of the desired graph. We depict the resulting weighted graph
in Figure 15.

Figure 15. A positively weighted graph which has the 16-cell as an
eigenpolytope. The solid edges have weight .1521, the dashed edges have weight
.1322.

The embedding of a polytope into a positively weighted graph given by this
construction always uses eigenvalues from the interior of the cone $K$. Thus
the resulting graph will always be a positively weighted complete graph. To
find a non-complete graph with the given eigenpolytope, one needs to find
eigenvalues lying in the boundary of the cone $K$. We will use this idea to
show that the edge graph of the 16-cell has the 16-cell as an eigenpolytope, a
result due to [God98, Theorem 4.3]. The edge-graph of the 16-cell, depicted in
Figure 16, has Laplacian eigenvalues $0^{1},6^{4},8^{3}$, where the exponents
represent multiplicity. We see that

$\begin{bmatrix}0&1/8\\\ 1/2&-3/8\end{bmatrix}\begin{bmatrix}6\\\
8\end{bmatrix}=\begin{bmatrix}1\\\ 0\end{bmatrix},$

hence these eigenvalues do indeed lie on the boundary of $K$. The matrix
$\Lambda=\operatorname{Diag}(0,6,6,6,6,8,8,8)$ also satisfies the requirement
of the eigenspace partitioning. Thus the Laplacian
$L=[\mathbbm{1}/\sqrt{8},V^{\top},(V^{*})^{\top}]\Lambda[\mathbbm{1}/\sqrt{8},V^{\top},(V^{*})^{\top}]^{\top}$
defines a valid positively weighted graph for which the 16-cell is an
eigenpolytope. Working out the computations shows that $L$ is indeed the
Laplacian of the graph of the 16-cell.

Figure 16. The graph of the 16-cell, for which the 16-cell is an
eigenpolytope.

We expect that eigenpolytopes of unweighted graphs are special, that is, that
not every combinatorial polytope may be embedded as the eigenpolytope of an
unweighted graph. However, the computations to show that such an embedding
does not exist quickly grow complicated, and every polytope with 6 or fewer
vertices, or in dimension 2, appears as an eigenpolytope of an unweighted
graph. Hence we pose the following as an open problem.

######  Open Problem 5.6.

Does every combinatorial polytope appear as an eigenpolytope of some
unweighted graph?

##  6\. Complexity Results

We use the results of Section 5 to show the hardness of two algorithmic
problems in computing graphical designs. We first recall some basics of
polytopes; we refer the reader to [Grü03] or [Zie95] for more. We assume $0$
is in the interior of every polytope. A polytope $P$ can either be expressed
as the convex hull of finitely many points, known as a
$\mathcal{V}$-description, or as the bounded intersection of finitely many
half-spaces, known as an $\mathcal{H}$-description. Because $0$ is in the
interior of $P=\operatorname{conv}(\\{v_{1},\ldots v_{n}\\})$,
$P^{*}=\cap_{i=1}^{n}\\{x:v_{i}^{\top}x\leq 1\\}$ is also a polytope, known as
the _dual polytope_ to $P$. We note that $(P^{*})^{*}=P$. A $d$-dimensional
polytope is _simple_ if every vertex is adjacent to exactly $d$ edges, or
equivalently, exactly $d$ facets. We recall that a polytope is _simplicial_ if
each of its facets is a simplex. Simplicial polytopes and simple polytopes are
dual in this sense: if $P=\operatorname{conv}(\\{v_{1},\ldots v_{n}\\})$ is
simple (resp. simplicial), then $P^{*}=\cap_{i=1}^{n}\\{x:v_{i}^{\top}x\leq
1\\}$ is simplicial (resp. simple).

It was established independently in [CKM82] and [Dye83] that it is NP-complete
to determine whether an $\mathcal{H}$-polytope is simple. The improvement to
strong NP-completeness is due to [FLM97].

######  Lemma 6.1 ([CKM82, Dye83, FLM97]).

The following decision problem is strongly NP-complete.

Instance: A polytope $P$ given in $\mathcal{H}$-description.

Question: Is $P$ nondegenerate (simple)?

Passing to the dual polytope provides an immediate corollary.

######  Corollary 6.2.

The following decision problem is strongly NP-complete.

Instance: A polytope $P$ given in $\mathcal{V}$-description.

Question: Is $P$ simplicial?

We now use this corollary to show that it is strongly NP-complete to determine
whether a graph has a positively weighted $k$-design of size smaller than the
facet bound shown in Theorem 3.9.

######  Theorem 6.3.

The following decision problem is strongly NP-complete.

Instance: A connected, positively weighted graph $G=([n],E,w)$ with $m$
Laplacian eigenspaces
$\Lambda_{1}=\operatorname{span}\\{\mathbbm{1}\\}<\Lambda_{2}<\ldots<\Lambda_{m}$,
and $k\in\\{2,\ldots,m-1\\}$.

Question: Is there a positively weighted $k$-graphical design consisting of
fewer than $\sum_{i=1}^{k}\dim(\Lambda_{i})$ vertices?

###### Proof.

We first show that this problem is in NP. Given a weight vector $a\geq 0$ with
$\operatorname{supp}(a)=S\subset[n]$, it is polynomial time in $n$ to check
whether $a$ defines a $k$-graphical design and further whether
$|S|<\sum_{i=1}^{k}\dim(\Lambda_{i}).$ We recall that $a\geq 0$ is a
$k$-graphical design if and only if $U_{\boldsymbol{k}}a=0,$ and as noted
previously, matrix multiplication can be done in polynomial time.

To show strong NP-completeness, we will show that the decision problem in
Corollary 6.2 is a sub-problem of the decision problem in the theorem
statement. Let
$P=\operatorname{conv}(\\{v_{1},\ldots,v_{n}\\})\subset{\mathbb{R}}^{d}$ be a
polytope given in $\mathcal{V}$ description with $d\leq n-2$. We note that if
$d=n-1$, then the polytope $P$ must be a simplex and hence simplicial. By
Lemma 5.3, there is a polynomial time algorithm to create a graph
$G=([n],E,w)$ with eigenspaces
$\Lambda_{1}=\operatorname{span}(\mathbbm{1}),\Lambda_{2},\Lambda_{3}$ for
which $P$ is combinatorially equivalent to $P_{\\{1,3\\}}$. Consider the
eigenspace ordering $\Lambda_{1}<\Lambda_{2}<\Lambda_{3}$. By Theorem 3.4, the
facets of $P$ are in bijection with the minimal positively weighted
$2$-graphical designs. A facet of $P$ is a simplex if and only if it contains
exactly $d$ vertices. The polytope $P$ is then simplicial if and only if every
minimal positively weighted $2$-graphical design has exactly
$n-d=\dim(\Lambda_{1})+\dim(\Lambda_{2})$ vertices. Thus if we could determine
whether a graph $G=([n],E,w)$ has a $2$-graphical design of size smaller than
the bound in Theorem 3.9, we could determine whether an arbitrary polytope $P$
was simplicial. ∎

Using a similar argument, we can show that it is #P-complete to count the
number of positively weighted $k$-designs of a graph. It was shown
independently in [Dye83] and [Lin86] that it is #P-complete to count the
number of facets of a polytope given by its vertices.

######  Lemma 6.4 ([Dye83, Lin86]).

The following counting problem is #P-complete.

Input: A polytope $P$ given in $\mathcal{V}$-description.

Output: Number of facets of $P.$

We again use Lemma 5.3 to hide the facet-counting polytope problem in the
problem of counting graphical designs.

######  Theorem 6.5.

The following counting problem is #P-complete.

Input: A connected, weighted graph $G=([n],E,w)$ with $m$ eigenspaces
$\Lambda_{1}=\operatorname{span}\\{\mathbbm{1}\\}<\Lambda_{2},\ldots<\Lambda_{m}$,
and an integer $k\in\\{2,\ldots,m-1\\}$.

Output: The number of minimal positively weighted $k$-graphical designs of
$G$.

###### Proof.

We will show that the counting problem in Lemma 6.4 is a sub-problem of this
counting problem. Let
$P=\operatorname{conv}(\\{v_{1},\ldots,v_{n}\\})\subset{\mathbb{R}}^{d}$ be a
polytope given in $\mathcal{V}$-description with $d\leq n-2$. We note that if
$d=n-1$, then the polytope $P$ must be a simplex and hence has $n$ facets. By
Lemma 5.3, there is a polynomial time algorithm to create a graph
$G=([n],E,w)$ with eigenspaces
$\Lambda_{1}=\operatorname{span}(\mathbbm{1}),\Lambda_{2},\Lambda_{3}$ for
which $P$ is combinatorially equivalent to $P_{\\{1,3\\}}$. Consider the
eigenspace ordering $\Lambda_{1}<\Lambda_{2}<\Lambda_{3}$. By Theorem 3.4, the
facets of $P$ are in bijection with the minimal positively weighted
$2$-graphical designs. Thus any enumeration of the minimal positively weighted
$2$-graphical designs of $G$ would count the facets of $P$, hence this
counting problem must be #P-complete. ∎

Many algorithmic polytope questions are open when the dimension is not fixed.
In particular, the complexity of listing all facets of a polytope given a
vertex description is unknown, though it is widely believed to be a difficult
problem. Any complexity result for the facet enumeration problem would provide
a complexity result for the problem of listing all minimal $k$-graphical
design, using the same framework as in the proofs of Theorems 6.3 and 6.5.

######  Remark 6.6.

We note that it is polynomial time to find a not necessarily minimal
$k$-graphical design. A solution to the linear program

(2) $\min\left\|x\right\|_{1}\qquad\text{ s.t.
}U_{\boldsymbol{k}}x=0,\mathbbm{1}^{\top}x=1,x\geq 0$

provides a positively weighted $k$-graphical design. Linear programming is
polynomial time by [Kha79, Kar84]. The 1-norm is often used as a proxy for
sparseness, but we have no guarantee that a solution to this linear program
will be minimal or even somewhat sparse. Minimizing any cost vector over this
feasible set would provide a (not necessarily minimal) positively weighted
k-graphical design.

######  Example 6.7.

Figure 17 shows the graph of pairwise word similarities of the 1000 most
common English words. Using the Word2vec NLP scheme established in [Mik+13],
each unique word from a given corpus is associated with a high-dimensional
vector. The similarity of two words is calculated as the cosine of the angle
of their vectors, with values closer to 1 corresponding to greater similarity.
The vectors used for this example were taken from the dataset available at
https://code.google.com/archive/p/word2vec/. We use the similarity scores as
edge weights, shifted by 1 to ensure positive weights. Using the linear
programming relaxation shown in Remark 6.6, we compute a positively weighted
100-graphical design consisting of 100 vertices. In this example, we order the
eigenspaces by _frequency_ as introduced by Steinerberger in [Ste20].

Figure 17. The red vertices are the support of a positively weighted
100-design on the similarity graph of the 1000 most common English words.

## References

  * [Bab21] C. Babecki  “Cubes, codes, and graphical designs” 81  In _J Fourier Anal Appl._ 27, 2021
  * [BT22] C. Babecki and R.. Thomas  “Graphical designs and gale duality” Accepted  In _Mathematical Programming_ , 2022  arXiv:2204.01873 [math.CO]
  * [Chu97] F… Chung  “Spectral Graph Theory”  Providence, R.I. :: Published for the Conference Board of the mathematical sciences by the American Mathematical Society,, 1997
  * [CKM82] R. Chandrasekaran, S.. Kabadi and K.. Murthy  “Some NP-complete problems in linear programming”  In _Operations Research Letters_ 1.3, 1982, pp. 101–104
  * [DGS77] Ph. Delsarte, J.. Goethal and J.. Seidel  “Spherical codes and designs”  In _Geometriae Dedicata._ 6.3 Kluwer Academic Publishers, 1977, pp. 363–388
  * [Dye83] M.. Dyer  “The complexity of vertex enumeration methods”  In _Mathematics of Operations Research_ 8.3 INFORMS, 1983, pp. 381–402
  * [FLM97] K. Fukuda, T.. Liebling and F. Margot  “Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron”  In _Computational Geometry_ 8.1, 1997, pp. 1–12
  * [Fus06] É. Fusy  “Counting d-polytopes with $d+3$ Vertices”  In _Electron. J. Comb._ 13, 2006
  * [Gal56] D. Gale  “Neighboring vertices on a convex polyhedron”  In _Linear Inequalities and Related System_ , Annals of Mathematics Studies, no. 38  Princeton University Press, Princeton, N.J., 1956, pp. 255–263
  * [God78] C.. Godsil  “Graphs, groups and polytopes”  In _Combinatorial Mathematics (Proc. Internat. Conf. Combinatorial Theory, Australian Nat. Univ., Canberra, 1977)_ 686, Lecture Notes in Math.  Springer, Berlin, 1978, pp. 157–164
  * [God98] C.. Godsil  “Eigenpolytopes of distance regular graphs”  In _Canad. J. Math._ 50.4, 1998, pp. 739–755
  * [Gol20] K. Golubev  “Graphical designs and extremal combinatorics”  In _Linear Algebra and its Applications._ 604, 2020
  * [Grü03] B. Grünbaum  “Convex Polytopes” 221, Graduate Texts in Mathematics  Springer-Verlag, New York, 2003
  * [Kar84] N. Karmarkar  “A new polynomial-time algorithm for linear programming”  In _Combinatorica_ 4.4, 1984, pp. 373–395
  * [Kha79] L. Khachiyan  “A polynomial algorithm for linear programming”  In _Doklady Akademii Nauk SSSR_ 224.5, 1979, pp. 1093–1096
  * [Lin86] N. Linial  “Hard enumeration problems in geometry and combinatorics”  In _SIAM Journal on Algebraic and Discrete Methods_ 7, 1986, pp. 331–335
  * [Llo70] K. Lloyd  “The number of $d$-polytopes with $(d+3)$ vertices”  In _Mathematika._ 17, 1970, pp. 120–132
  * [LS20] G.. Linderman and S. Steinerberger  “Numerical integration on graphs: where to sample and how to weigh”  In _Mathematics of Computation._ 89.324 National Academy of Sciences-National Research Council,, 2020, pp. 1933–1952
  * [Mik+13] T. Mikolov, K. Chen, G.. Corrado and J. Dean  “Efficient estimation of word representations in vector space”, 2013  URL: http://arxiv.org/abs/1301.3781
  * [Ort+18] A. Ortega et al.  “Graph signal processing: overview, challenges, and applications”  In _Proceedings of the IEEE._ 106.5, 2018, pp. 808–828
  * [Ort22] A. Ortega  “Introduction to Graph Signal Processing”  Cambridge University Press, 2022
  * [PP10] A. Padrol Sureda and J. Pfeifle  “Graph operations and Laplacian eigenpolytopes”  In _VII Jornadas de Matemática Discreta y Algorítmica_ , 2010, pp. 505–516
  * [ST22] S. Steinerberger and R.R. Thomas  “Random Walks, Equidistribution and Graphical Designs”, 2022  arXiv:2206.05346
  * [Ste20] S. Steinerberger  “Generalized designs on graphs: sampling, spectra, symmetries”  In _Journal of Graph Theory._ 93.2, 2020, pp. 253–267
  * [Zie95] G.. Ziegler  “Lectures on Polytopes” 152, Graduate Texts in Mathematics  Springer-Verlag, New York, 1995