$C(1-\frac{4}{n}\cdot\min(l,n-l))$, where $C=\Theta(1)$ is a normalizing
factor, and $g(l)\equiv\frac{8C^{2}}{n^{2}}$), and

$\sigma_{k}(G)=\sum_{l=0}^{k-1}\left(1-\cos\left(\frac{2\pi
l}{n}\right)\right)=\Theta\left(\frac{k^{3}}{n^{2}}\right),$

one can verify that in this case the hard direction of Theorem 6.4 is tight.

We prove 6.2 and 6.3 in the following two subsections.

###  6.1 Rounding $k$-Step Approximation

We prove 6.2 in this subsection. First, we do some preprocessing on the
solution $(f,g)$ as in Section 3. Then, as in [KLLOT13], the main step is to
use a modified probability distribution on the thresholds based on the
$k$-step approximation $y$ to analyze the threshold rounding algorithm.

Given a feasible solution $(f,g)$ to the $\gamma^{(1)}(G)$ program with
objective value $\gamma_{f}$, we use 3.12 and 3.13 to obtain a solution $f$
and $\overrightarrow{E}$ to the directed program
$\overrightarrow{\gamma}^{(1)}(G)$ in 3.11 with objective value at most
$2\gamma_{f}$. Then we apply the truncation step in 3.17 on $f$ and
$\overrightarrow{E}$ to obtain a solution $x$ and $\overrightarrow{E}$ with
$x\geq 0$ and $\pi(\operatorname{supp}(x))\leq 1/2$ and

$\sum_{v\in V}\pi(v)\max_{u:uv\in\overrightarrow{E}}(x(u)-x(v))^{2}\leq
8\gamma_{f}\quad{\rm and}\quad\sum_{v\in V}\pi(v)x(v)^{2}=1.$

Let $y_{f}$ be the $k$-step approximation of $f$ in the assumption of 6.2.
Note that the way we construct $x$ from $f$ consists of shifting, truncating,
and scaling by a factor of at most $2$. So, applying the same transformations
to $y_{f}$ will still give us a $k$-step function $y$ with $\left\lVert
x-y\right\rVert_{\pi}\leq 2\left\lVert f-y_{f}\right\rVert_{\pi}$. Henceforth,
we work with $x$ and its $k$-step approximation $y$.

The main step is to prove that applying the threshold rounding algorithm on
$x$ will find a set $S\subseteq V$ with small directed vertex expansion
$\overrightarrow{\psi}(S)$ as defined in 3.18. For the analysis, we take the
$k$-step approximation $y$ into consideration and give higher weight to a
threshold $t$ if $t$ is far away from the function values in $y$.

The following weighting scheme is from [KLLOT13]. Let $x_{\max}:=\max_{v\in
V}x(v)$. Suppose the $k$-step function $y$ takes values $0\leq y_{1}\leq
y_{2}\leq\cdots\leq y_{k}$. For $t\in[0,x_{\max}]$, define
$\rho(t):=\min_{1\leq i\leq k}|t-y_{i}|$. In words, $\rho(t)$ is the distance
from $t$ to the closest value of the $k$-step function $y$. We sample
$t\in[0,x_{\max}]$ with probability proportional to $\rho(t)$. That is, for
$0\leq a<b\leq x_{\max}$,

$\Pr\big{[}t\in[a,b]\big{]}=\frac{1}{Z}\int_{a}^{b}\rho(t)\,dt,$

where $Z:=\int_{0}^{x_{\max}}\rho(t)dt$ is the normalizing factor.

We use the distribution described above to analyze the threshold rounding
algorithm. Let $S_{t}:=\\{v\in V\mid x(v)>t\\}$ be a threshold set. By a
standard averaging argument,

$\min_{t\in[0,x_{\max}]}\overrightarrow{\psi}(S_{t})\leq\frac{\mathbb{E}_{t}[\pi(\overrightarrow{\partial}S_{t})]}{\mathbb{E}_{t}[\pi(S_{t})]}$

The denominator is

$\displaystyle\mathbb{E}_{t}[\pi(S_{t})]~{}=~{}\frac{1}{Z}\cdot\sum_{v\in
V}\pi(v)\cdot\int_{0}^{x(v)}\rho(t)\,dt~{}\gtrsim~{}\frac{1}{kZ}\sum_{v\in
V}\pi(v)x(v)^{2}=\frac{1}{kZ},$

where the inequality can be seen as follows: For any $v\in V$, let
$k^{\prime}\leq k$ be the largest index so that $0\leq y_{1}\leq\dots\leq
y_{k^{\prime}}\leq x(v)$ and let $z_{0}:=0$, $z_{i}:=y_{i}$ for $1\leq i\leq
k^{\prime}$ and $z_{k^{\prime}+1}:=x(v)$, then

$\displaystyle\int_{0}^{x(v)}\rho(t)\,dt=\sum_{i=0}^{k^{\prime}}\int_{z_{i}}^{z_{i+1}}\rho(t)\,dt\geq\frac{1}{4}\sum_{i=0}^{k^{\prime}}(z_{i+1}-z_{i})^{2}\geq\frac{1}{4(k^{\prime}+1)}\bigg{(}\sum_{i=0}^{k^{\prime}}(z_{i+1}-z_{i})\bigg{)}^{2}\gtrsim\frac{1}{k}x(v)^{2},$

where the first inequality is by simple calculus and the second inequality is
by Cauchy-Schwarz.

The numerator is

$\displaystyle\mathbb{E}_{t}\Big{[}\pi\big{(}\overrightarrow{\partial}S_{t}\big{)}\Big{]}$
$\displaystyle=$ $\displaystyle\sum_{v}\pi(v)\cdot\Pr_{t}[\text{ there exists
an edge }uv\in\overrightarrow{E}\text{ with }uv\in\delta(S_{t})]$
$\displaystyle=$ $\displaystyle\sum_{v}\pi(v)\cdot\max_{u:u\to
v}\Pr_{t}\big{[}uv\in\delta(S_{t})\big{]}$ $\displaystyle=$
$\displaystyle\sum_{v}\pi(v)\cdot\max_{u:u\to
v}\frac{1}{Z}\cdot\bigg{|}\int_{x(v)}^{x(u)}\rho(t)\,dt\bigg{|}$
$\displaystyle\leq$ $\displaystyle\frac{1}{Z}\sum_{v}\pi(v)\cdot\max_{u:u\to
v}\bigg{|}\int_{x(v)}^{x(u)}\Big{(}\rho\big{(}x(v)\big{)}+\big{|}t-x(v)\big{|}\Big{)}\,dt\bigg{|}$
$\displaystyle=$ $\displaystyle\frac{1}{Z}\sum_{v}\pi(v)\cdot\max_{u:u\to
v}\bigg{[}\big{|}x(u)-x(v)\big{|}\cdot\rho\big{(}x(v)\big{)}+\frac{1}{2}\big{(}x(u)-x(v)\big{)}^{2}\bigg{]}$
$\displaystyle\leq$
$\displaystyle\frac{1}{Z}\cdot\Big{(}4\gamma_{f}+\sum_{v}\pi(v)\cdot\rho\big{(}x(v)\big{)}\cdot\max_{u:u\to
v}\big{|}x(u)-x(v)\big{|}\Big{)}$ $\displaystyle\leq$
$\displaystyle\frac{1}{Z}\cdot\bigg{(}4\gamma_{f}+\sqrt{\Big{(}\sum_{v}\pi(v)\cdot\rho\big{(}x(v)\big{)}^{2}\Big{)}\cdot\Big{(}\sum_{v}\pi(v)\max_{u:u\to
v}\big{(}x(u)-x(v)\big{)}^{2}\Big{)}}\bigg{)}$ $\displaystyle\leq$
$\displaystyle\frac{1}{Z}\cdot\Big{(}4\gamma_{f}+\sqrt{\left\lVert
x-y\right\rVert_{\pi}^{2}\cdot 8\gamma_{f}}\Big{)}$ $\displaystyle\lesssim$
$\displaystyle\frac{1}{Z}\cdot\big{(}\gamma_{f}+\left\lVert
x-y\right\rVert_{\pi}\cdot\sqrt{\gamma_{f}}\big{)},$

where the first inequality is because $\rho(t)$ is a $1$-Lipschitz function,
the third inequality is by Cauchy-Schwarz, and the fourth inequality is
because $\rho(x(v))\leq|x(v)-y(v)|$ by the definition of $\rho$.

Combining the bounds on the denominator and the numerator,

$\min_{t\in[0,x_{\max}]}\overrightarrow{\psi}(S_{t})~{}\leq~{}\frac{\mathbb{E}_{t}\big{[}\pi\big{(}\overrightarrow{\partial}S_{t}\big{)}\big{]}}{\mathbb{E}_{t}\big{[}\pi(S_{t})\big{]}}~{}\lesssim~{}k\gamma_{f}+k\left\lVert
x-y\right\rVert_{\pi}\cdot\sqrt{\gamma_{f}}~{}\lesssim~{}k\gamma_{f}+k\left\lVert
f-y_{f}\right\rVert_{\pi}\cdot\sqrt{\gamma_{f}}.$

Since $\pi(\operatorname{supp}(x))\leq\frac{1}{2}$, the output set $S$ has
$\pi(S)\leq\frac{1}{2}$. Finally, we apply the postprocessing step in 3.20 to
obtain a set $S^{\prime}\subseteq S$ with $\psi(S^{\prime})\leq
2\overrightarrow{\psi}(S)$. We conclude that

$\psi(G)~{}\leq~{}\psi(S^{\prime})~{}\lesssim~{}\min_{t}\overrightarrow{\psi}(S_{t})~{}\lesssim~{}\gamma_{f}+k\left\lVert
f-y_{f}\right\rVert_{\pi}\cdot\sqrt{\gamma_{f}}.$

###  6.2 Constructing $k$-Step Approximation

We prove 6.3 in this subsection. The high level plan is similar to that in
[KLLOT13]. Given a feasible solution $(f,g)$ to the $\gamma^{(1)}(G)$ program,
we aim to construct a good $k$-step approximation $y$ of $f$ using a simple
procedure. If we fail to do so, then we show that $f$ can be used to construct
a good $k$-dimensional solution
$\bar{f}=(\bar{f}_{1},\bar{f}_{2},\ldots,\bar{f}_{k})$ to the
$\sigma_{k}^{*}(G)$ program, contradicting the value of $\sigma_{k}^{*}(G)$ is
large. Therefore, the simple process must succeed to find a good $k$-step
approximation $y$ of $f$.

Suppose our $k$-step function $y$ takes values $y_{1}\leq y_{2}\leq\cdots\leq
y_{k}$. For convenience $y_{0}:=-\infty$. We use these values to define $k$
disjoint subsets $S_{1},\ldots,S_{k}\subseteq V$ where $S_{i}:=\\{v\in V\mid
y_{i-1}<f(v)\leq y_{i}\\}$, and define functions
$\bar{f}_{1},\ldots,\bar{f}_{k}$ supported on $S_{1},\ldots,S_{k}$
respectively where

$\bar{f}_{i}(v):=\begin{cases}\min\big{\\{}|y_{i}-f(v)|,|f(v)-y_{i-1}|\big{\\}},&\text{
if }f(v)\in(y_{i-1},y_{i})\\\ 0&\text{ otherwise.}\end{cases}$

The role of $\bar{f}_{i}$ is to measure how well the two threshold values
$y_{i-1}$ and $y_{i}$ approximate the values of the vertices in $S_{i}$ in
$f$. We would like to choose $y_{1}\leq y_{2}\leq\cdots\leq y_{k}$ so that
each $\left\lVert\bar{f}_{i}\right\rVert_{\pi}^{2}$ is small and
$S_{1}\cup\cdots\cup S_{k}=V$. As we will show, this would imply that there
exists a $k$-step function $y$ with threshold values $y_{1}\leq
y_{2}\leq\cdots\leq y_{k}$ so that $\left\lVert
f-y\right\rVert_{\pi}=\sum_{i=1}^{k}\left\lVert\bar{f}_{i}\right\rVert^{2}_{\pi}$
is small, and thus $y$ is a good $k$-step approximation to $f$.

Consider the following simple procedure to choose the threshold values
$y_{1}\leq y_{2}\leq\ldots\leq y_{k}$ of the $k$-step function. Let $\mu$ be a
parameter to be determined later. We would like to guarantee that
$\left\lVert\bar{f}_{i}\right\rVert_{\pi}^{2}\leq\mu$ for $1\leq i\leq k$ and
$S_{1}\cup S_{2}\cup\cdots\cup S_{k}=V$ such that all vertices are covered by
these functions $\bar{f}_{1},\ldots,\bar{f}_{k}$. We choose $y_{i}$
successively as follows: given $y_{0},\ldots,y_{i-1}$, set $y_{i}$ to be the
smallest number such that $\left\lVert\bar{f}_{i}\right\rVert_{\pi}^{2}=\mu$.
If the smallest $y_{i}$ does not exist, then we set
$y_{i}=\ldots=y_{k}:=\max_{v\in V}f(v)$ and call the procedure a “success”.
Otherwise, if we set all $y_{1}\leq y_{2}\leq\ldots\leq y_{k}$ and $S_{1}\cup
S_{2}\cup\cdots S_{k}\subset V$ such that not all vertices are covered by
$\bar{f}_{1},\ldots,\bar{f}_{k}$, then we call the procedure a “failure”.

Now we set

$\mu=\frac{2\gamma_{f}}{\sigma_{k}^{*}(G)}.$

When the procedure succeeds, then
$\left\lVert\bar{f}_{i}\right\rVert_{\pi}^{2}\leq\mu$ for $1\leq i\leq k$ and
$S_{1}\cup S_{2}\cup\cdots\cup S_{k}=V$. We would like to show that the there
exists a $k$-step function $y$ with threshold values $y_{1}\leq
y_{2}\leq\ldots\leq y_{k}$ such that $\left\lVert
y-f\right\rVert_{\pi}^{2}\leq k\mu$. Define $y:V\to\mathbb{R}$ to be

$y(v):=\operatorname{argmin}_{\alpha\in\\{y_{1},\dots,y_{k}\\}}|\alpha-f(v)|,$

such that each vertex $v$ is assigned to its closest threshold value. Then

$\left\lVert f-y\right\rVert_{\pi}^{2}=\sum_{v\in
V}\pi(v)\cdot\big{|}f(v)-y(v)\big{|}^{2}=\sum_{i=1}^{k}\sum_{v\in
S_{i}}\pi(v)\bar{f}_{i}(v)^{2}=\sum_{i=1}^{k}\left\lVert\bar{f}_{i}\right\rVert_{\pi}^{2}\leq
k\mu\lesssim\frac{k\gamma_{f}}{\sigma_{k}^{*}(G)},$

where the second equality uses that $S_{1}\cup S_{2}\cup\cdots\cup S_{k}=V$
and the first inequality uses that each
$\left\lVert\bar{f}_{i}\right\rVert_{\pi}^{2}\leq\mu$. Thus $y$ is a $k$-step
function that satisfies the statement of the proposition.

To complete the proof, we would like to show that the procedure always
succeeds. When the procedure fails, then there exist
$y_{1}<y_{2}<\cdots<y_{k}$ such that
$\left\lVert\bar{f}_{i}\right\rVert_{\pi}^{2}=\mu$ for $1\leq i\leq k$. We
will construct from $\bar{f}_{1},\ldots,\bar{f}_{k}$ a solution
$(\bar{f},\bar{g})$ to the $\sigma_{k}^{*}(G)$ program with objective value
less than $\sigma_{k}^{*}(G)$, thus arriving at a contradiction. Define
$\bar{f}:V\rightarrow\mathbb{R}^{n}$ and $\bar{g}:V\rightarrow\mathbb{R}$ as
follows:

$\bar{f}(v):=\Big{(}\frac{\bar{f}_{1}(v)}{\sqrt{\mu}},\dots,\frac{\bar{f}_{k}(v)}{\sqrt{\mu}},0,\dots,0\Big{)}^{T}\quad{\rm
and}\quad\bar{g}(v):=\frac{1}{\mu}g(v).$

We will check that $(\bar{f},\bar{g})$ is a feasible solution to the
$\sigma_{k}^{*}(G)$ program in 5.2. For the sub-isotropy condition, note that
each $\bar{f}(v)$ has at most one nonzero entry, and

$\displaystyle\sum_{v\in V}\pi(v)\bar{f}(v)\bar{f}(v)^{T}$ $\displaystyle=$
$\displaystyle\operatorname{diag}\Big{(}\frac{1}{\mu}\sum_{v\in
S_{1}}\pi(u)\bar{f}_{1}(u)^{2},\frac{1}{\mu}\sum_{v\in
S_{2}}\pi(v)\bar{f}_{2}(u)^{2},\dots,\frac{1}{\mu}\sum_{v\in
S_{k}}\pi(v)\bar{f}_{k}(v)^{2},0,\dots,0\Big{)}$ $\displaystyle=$
$\displaystyle\frac{1}{\mu}\operatorname{diag}\Big{(}\left\lVert\bar{f}_{1}\right\rVert_{\pi}^{2},\left\lVert\bar{f}_{2}\right\rVert_{\pi}^{2},\dots,\left\lVert\bar{f}_{k}\right\rVert_{\pi}^{2},0,\dots,0\Big{)}~{}=~{}\operatorname{diag}(1,1,\dots,1,0,\dots,0)~{}\preccurlyeq~{}I_{n}.$

The mass constraint is satisfied as

$\sum_{v\in
V}\pi(v)\left\lVert\bar{f}(v)\right\rVert^{2}=\operatorname{tr}\bigg{(}\sum_{u\in
V}\pi(u)\bar{f}(u)\bar{f}(u)^{T}\bigg{)}=\operatorname{tr}\Big{(}\operatorname{diag}\big{(}1,1,\dots,1,0,\dots,0\big{)}\Big{)}=k.$

For the constraint on each edge $uv\in E$,

$\left\lVert\bar{f}(u)-\bar{f}(v)\right\rVert^{2}=\frac{1}{\mu}\sum_{i=1}^{k}\big{(}\bar{f}_{i}(u)-\bar{f}_{i}(v)\big{)}^{2}\leq\frac{1}{\mu}\big{(}f(u)-f(v)\big{)}^{2}\leq\frac{1}{\mu}\big{(}g(u)+g(v)\big{)}=\bar{g}(u)+\bar{g}(v),$

where for the first inequality we consider two cases: (i) suppose $u\in S_{i}$
and $v\in S_{j}$ for $i=j$, then
$\sum_{l=1}^{k}\big{(}\bar{f}_{l}(u)-\bar{f}_{l}(v)\big{)}^{2}=\big{(}\bar{f}_{i}(u)-\bar{f}_{i}(v)\big{)}^{2}\leq\big{(}f(u)-f(v)\big{)}^{2}$,
and (ii) suppose $u\in S_{i}$ and $v\in S_{j}$ for $i\neq j$, then
$\sum_{l=1}^{k}\big{(}\bar{f}_{l}(u)-\bar{f}_{l}(v)\big{)}^{2}=\big{(}\bar{f}_{i}(u)-\bar{f}_{i}(v)\big{)}^{2}+\big{(}\bar{f}_{j}(u)-\bar{f}_{j}(v)\big{)}^{2}\leq\big{(}f(u)-f(v)\big{)}^{2}$
since
$\big{|}\bar{f}_{i}(u)-\bar{f}_{i}(v)\big{|}+\big{|}\bar{f}_{j}(u)-\bar{f}_{j}(v)\big{|}\leq\big{|}f(u)-f(v)\big{|}$.

Therefore, $(\bar{f},\bar{g})$ is a feasible solution to the
$\sigma_{k}^{*}(G)$ program, and its objective value is

$\sum_{v\in V}\pi(v)\bar{g}(v)=\frac{1}{\mu}\sum_{v\in
V}\pi(v)g(v)=\frac{1}{\mu}\cdot\gamma_{f}=\frac{\sigma_{k}^{*}(G)}{2}<\sigma_{k}^{*}(G),$

a contradiction to the definition of $\sigma_{k}^{*}(G)$.

To conclude, the procedure must succeed and return a $k$-step function $y$
with $\left\lVert f-y\right\rVert_{\pi}^{2}\lesssim
k\gamma_{f}/\sigma_{k}^{*}(G)$.

##  7 Vertex Expansion of $0/1$-Polytopes

The goal of this section is to present a construction of $0/1$-polytopes with
poor vertex expansion as described in Theorem 1.12, which has implications
about sampling from the uniform distribution as described in Section 1.1.5.

A $0/1$-polytope is defined by a subset of vertices in the boolean hypercube
$\\{0,1\\}^{n}$. Our examples are based on the following simple probabilistic
construction.

######  Definition 7.1 (Probabilistic Construction).

Let $n$ be an even number and $k<n/2$. For a binary string
$x\in\\{0,1\\}^{n}$, denote its $1$-norm by $|x|:=\sum_{i=1}^{n}|x_{i}|$. The
set of vertices of our constructed polytope is the union of three subsets:

  1. 1.

A left part $L:=\\{x\in\\{0,1\\}^{n}\mid|x|=k\\}$ consists of all binary
strings with $k$ ones.

  2. 2.

A right part $R:=\\{x\in\\{0,1\\}^{n}\mid|x|=n-k\\}$ consists of all binary
strings with $n-k$ ones.

  3. 3.

A middle part $M\subset\\{x\in\\{0,1\\}^{n}\mid|x|=n/2\\}$ consists of
$\Theta(4^{k}n^{2})$ number of uniformly random binary strings with $n/2$
ones.

The graph $G_{Q}=(V,E)$ of a polytope $Q$ is defined as the $1$-skeleton of
the polytope $Q$. Our plan is to prove that for a random polytope $Q$
constructed in 7.1, the middle part $M$ “blocks” all the edges between $L$ and
$R$ in $G_{Q}$ with constant probability. This would imply that $\partial
L\subseteq M$ and $\partial R\subseteq M$, and thus $\psi(L),\psi(R)\lesssim
4^{k}n^{2}/n^{k}$ are very small.

The organization of this section is as follows. First, in Section 7.1, we
provide a sufficient condition for two binary strings $x,y$ to have no edge in
$G_{Q}$, using geometric arguments. Then, in Section 7.2, we outline the main
probabilistic argument to prove Theorem 1.12, by using a union bound over the
set of linear threshold functions. Finally, we show 1.13 in Section 7.3. We
defer all the proofs in Section 7.1 and Section 7.2 to Appendix D.

As mentioned in 1.14 in the introduction, Gillmann [Gil07] has constructed
similar examples of 0/1-polytopes with poor vertex expansion. Following the
same simple argument as in Section 7.3, one obtains analogous lower bounds on
the fastest mixing time of these polytopes. We remark that the construction in
[Gil07] is similar to our construction, but the proofs are different and so we
present our proofs even though the results follow from [Gil07].

###  7.1 A Sufficient Condition for Edge Blocking

Let $Q$ be a $0/1$-polytope and $G_{Q}=(V,E)$ be its graph/$1$-skeleton. For
two binary strings $x,y\in\\{0,1\\}^{n}$, if $xy$ is an edge in $G_{Q}$, then
there is a separating hyperplane $l$ with $l(x),l(y)\geq 0$ while $l(z)<0$ for
all other binary strings $z$ in the $0/1$-polytope $Q$.

In the construction of $Q$ in 7.1, if $x\in L$ and $y\in R$ then
$\frac{1}{2}(x+y)$ has $1$-norm equal to $n/2$. If $xy$ is an edge in $G_{Q}$,
then there is a separating hyperplane $l$ with
$l\big{(}\frac{1}{2}(x+y)\big{)}\geq 0$ while $l(z)<0$ for all other binary
strings $z$ in the middle part $M$. So, if we could establish that
$\frac{1}{2}(x+y)$ is in the convex hull ${\rm conv}(M)$ of $M$ for all $x\in
L$ and $y\in R$, then there are no edges between $L$ and $R$ in the graph
$G_{Q}$. This is the sufficient condition that we will formalize.

In the analysis, we use the following definitions to group the pairs of
vertices $x\in L$, $y\in R$ based on their common patterns.

######  Definition 7.2 (Patterns).

For $n\in\mathbb{N}$, a pattern is an element $p\in\\{0,1,\lor\\}^{n}$, where
$0$, $1$, and $\lor$ are regarded as symbols.

The support of a pattern $p\in\\{0,1,\lor\\}^{n}$ is defined as
$\operatorname{supp}(p):=\\{i\in[n]\mid p_{i}\neq\lor\\}$. We also define
$\operatorname{supp}_{0}(p):=\\{i\in[n]\mid p_{i}=0\\}$ and
$\operatorname{supp}_{1}(p):=\\{i\in[n]\mid p_{i}=1\\}$.

Given two binary strings $x,y\in\\{0,1\\}^{n}$, their common pattern
$p^{(x,y)}\in\\{0,1,\lor\\}^{n}$ is defined as

$p^{(x,y)}_{i}=\begin{cases}0,&\text{ if }x_{i}=y_{i}=0\\\ 1,&\text{ if
}x_{i}=y_{i}=1\\\ \lor,&\text{ if }x_{i}\neq y_{i}.\end{cases}$

Given a pattern $p\in\\{0,1,\lor\\}^{n}$ and a binary string
$x\in\\{0,1\\}^{n}$, $x$ is said to match $p$ if and only if $p_{i}\neq\lor$
implies $p_{i}=x_{i}$.

For each pattern $p$, we consider a potential separating hyperplane of the
following specific form, which will be convenient for the probabilistic
analysis

######  Definition 7.3 (Consistent Affine Function).

Let $p\in\\{0,1,\lor\\}^{n}$ be a pattern. An affine function
$l:(u_{1},u_{2},\dots,u_{n})\in\mathbb{R}^{n}\mapsto\beta+\sum_{i}\alpha_{i}u_{i}$
is called $p$-consistent if

$\alpha_{i}=0{\rm~{}for~{}}i\in\operatorname{supp}(p)\qquad{\rm
and}\qquad\beta+\frac{1}{2}\sum_{i:i\notin\operatorname{supp}(p)}\alpha_{i}=0.$

If $p$ is the common pattern of $x$ and $y$, then $l$ being $p$-consistent
implies $l\big{(}\frac{1}{2}(x+y)\big{)}=0$.

We formulate the sufficient condition described above for the middle part $M$
blocking the edge $xy$ for $x\in L$ and $y\in R$ using the definitions that we
have developed. The proof is deferred to Appendix D.

######  Lemma 7.4 (Blocking One Edge).

Let $Q=L\cup M\cup R$ be a $0/1$-polytope from 7.1. Let $x\in L$, $y\in R$ and
$p=p^{(x,y)}\in\\{0,1,\lor\\}^{n}$ be the common pattern of $x$ and $y$. If
for any $p$-consistent affine function $l$ there exists a point $z\in M$
matching the pattern $p$ and satisfying $l(z)\geq 0$, then there is no edge
connecting $x$ and $y$ in the graph of $Q$.

The following is a sufficient condition for the middle part $M$ blocking all
the edges between $L$ and $R$, by considering all possible common patterns of
an $x\in L$ and a $y\in R$.

######  Lemma 7.5 (Blocking All Edges).

Let $Q=L\cup M\cup R$ be a $0/1$-polytope from 7.1. Suppose for every pattern
$p\in\\{0,1,\lor\\}^{n}$ with
$|\operatorname{supp}_{0}(p)|=|\operatorname{supp}_{1}(p)|\leq k$ and for any
$p$-consistent affine function $l:\mathbb{R}^{n}\to\mathbb{R}$, there is $z\in
M$ matching the pattern $p$ with $l(z)\geq 0$. Then there are no edges between
$L$ and $R$ in the graph of $Q$.

###  7.2 Probabilistic Analysis

Our plan is to use the sufficient condition in 7.5 to prove that a random $M$
with not many points can block all the edges between $L$ and $R$. To this end,
we prepare with two simple lemmas about the probability that $z\in M$
satisfying $l(z)\geq 0$ and matching a particular pattern $p$ with
$|\operatorname{supp}_{0}(p)|=|\operatorname{supp}_{1}(p)|\leq k$.

The geometric intuition of the first lemma is simple: when we restrict a
$p$-consistent affine function $l$ on the coordinates in
$[n]\setminus\operatorname{supp}(p)$, then $l$ is an “unbiased” hyperplane
that goes through the point $\frac{1}{2}\cdot\vec{1}$ on
$[n]\setminus\operatorname{supp}(p)$ (because of the second condition in 7.3),
and thus a random vertex in $M$ matching the pattern $p$ lies on the non-
negative side of $l$ with probability at least $1/2$.

######  Lemma 7.6.

Let $Q=L\cup M\cup R$ be a $0/1$-polytope from 7.1. Let $p$ be the common
pattern of $x\in L$ and $y\in R$, and $l$ be a $p$-consistent affine function.
Let $Z$ be the uniform distribution on
$\\{z\in\\{0,1\\}^{n}:|z|=\frac{n}{2}\\}$. Then,

$\Pr_{z\sim Z}\big{[}\,l(z)\geq 0\mid z\text{ matches pattern
}p\,\big{]}\geq\frac{1}{2}.$

The second lemma gives a lower bound on the probability that a random point
$z\sim Z$ matches a pattern $p$ with
$|\operatorname{supp}_{0}(p)|=|\operatorname{supp}_{1}(p)|\leq k$.

######  Lemma 7.7.

Let $p\in\\{0,1,\lor\\}^{n}$ be a pattern with
$|supp_{0}(p)|=|supp_{1}(p)|=s\leq k$, and let $Z$ be the uniform distribution
on $\\{z\in\\{0,1\\}^{n}:|z|=n/2\\}$. Then

$\Pr_{z\sim Z}[z\text{ matches pattern }p]\gtrsim 4^{-s}.$

With the above two lemmas, we can show that for any pattern $p$ with
$|\operatorname{supp}_{0}(p)|=|\operatorname{supp}_{1}(p)|=s\leq k$ and any
$p$-consistent affine function $l$, the probability that a random point in
$\\{z\in\\{0,1\\}^{n}:|z|=n/2\\}$ matches the pattern $p$ and satisfies
$l(z)\geq 0$ with probability not too small. So, by adding enough number of
random points in the middle part $M$, such a point $z$ exists in $M$ with high
probability for a fixed $p$ and $l$. Then, we would like to use a union bound
over $p$ and $l$ to prove that there will be no edges between $L$ and $R$ in
the graph of the polytope with constant probability.

One technical issue of this approach is that there are infinitely many affine
functions $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$. Note, however, that we only
care about the values of $l$ on the hypercube vertices. This reduces the
number of different functions to $2^{2^{n}}$. Indeed, we only care about
whether $l(z)\geq 0$ for $z\in\\{0,1\\}^{n}$ for 7.5. Therefore, we only need
to apply a union bound over the set of linear threshold functions over the
boolean hypercube, which further reduces the number of different such
functions to $2^{n^{2}}$.

######  Proposition 7.8 ([Cov65]).

The number of linear threshold functions on $\\{0,1\\}^{n}$ is at most
$2^{n^{2}}$. A linear threshold function on $\\{0,1\\}^{n}$ is a function of
the form $\tau:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, where

$\tau(u_{1},\dots,u_{n})=\begin{cases}1,&\text{ if
}\beta+\sum_{i}\alpha_{i}u_{i}\geq 0;\\\ 0,&\text{ if
}\beta+\sum_{i}\alpha_{i}u_{i}<0,\end{cases}$

for some $\alpha_{1},\dots,\alpha_{n},\beta\in\mathbb{R}$.

The complete proof of Theorem 1.12 can be found in Appendix D.

###  7.3 Mixing Time

1.13 follows from Theorem 1.12 and the easy direction of Cheeger’s inequality
for vertex expansion in Theorem 1.3.

Proof of 1.13.  Let $Q=L\cup M\cup R$ be a $0/1$-polytope from 7.1. The number
of vertices of $Q$ is $|L|+|M|+|R|\lesssim{n\choose k}\leq(en/k)^{k}$. By
Theorem 1.12, the vertex expansion of the graph $G_{Q}$ is
$\psi(G_{Q})\lesssim(4k)^{k}/n^{k-2}$. Therefore, by the easy direction in
Theorem 1.3, the mixing time of any reversible chain
$P\in\mathbb{R}^{|V|\times|V|}$ on $G_{Q}$ with stationary distribution
$\pi=\frac{1}{|V|}\vec{1}$ is at least

$\displaystyle\tau^{*}(G)\gtrsim\frac{1}{\psi(G_{Q})}\gtrsim\frac{n^{k-2}}{(4k)^{k}}\gtrsim\left(\frac{en}{k}\right)^{k-2}\gtrsim|V|^{1-\frac{2}{k}},$

where the second last inequality is by the assumption that $k$ is a constant
and so only the exponent of $n$ matters, and the last inequality is by
$|V|\leq(en/k)^{k}$ explained above. ∎

The implication of 1.13 has been discussed in Section 1.1.5 and we won’t
repeat here.

##  8 Tight Example to Cheeger’s Inequality for Vertex Expansion

The goal of this section is to construct a family of tight examples to Theorem
1.4 when $\pi=\vec{1}/|V|$. The graphs constructed will have non-constant
maximum degree $d$ and satisfy

$\frac{\psi(G)^{2}}{\log d}\asymp\lambda_{2}^{*}(G).$

These examples are suggested to us by Shayan Oveis Gharan.

The graphs are realized as proximity graphs on $\mathbb{S}^{k-1}$. We employ
the following notations: $\mu$ denotes the normalized Lebesgue measure on
$\mathbb{S}^{k-1}$. $\Delta(\cdot,\cdot)$ denotes the geodesic distance on
$\mathbb{S}^{k-1}$. For $\theta\in\mathbb{S}^{k-1}$ and $r>0$, $B(\theta,r)$
denotes the set of points of distance less than $r$ from $\theta$. $Cap(r)$
denotes a generic spherical cap on $\mathbb{S}^{k-1}$ of radius $r$. For
$S\subseteq\mathbb{S}^{k-1}$, we use $S_{r}$ or $S+Cap(r)$ to denote the set
of points of distance less than $r$ from $S$.

######  Definition 8.1 (Spherical Proximity Graph).

Given $k$, a $(\gamma,\delta)$-spherical proximity graph in $k$ dimensions is
a graph $G_{k}=(V,E)$ that can be constructed as follows:

  1. 1.

Partition $\mathbb{S}^{k-1}$ into $n$ cells: $S_{1},S_{2},\dots,S_{n}$, such
that each cell has diameter at most $\gamma$ and measure between
${\epsilon}:=\mu(Cap(\gamma/4))$ and $2{\epsilon}$. Take a point $x_{i}\in
S_{i}$ for each $i\in[n]$.

  2. 2.

Set $V=\\{x_{i}\\}_{i\in[n]}$ and $E=\\{(x_{i},x_{j})\in V\times
V:\Delta(x_{i},x_{j})<\delta\\}$.

We shall show that, for suitable choices of $\gamma$ and $\delta$, the
resulting graph will be a vertex expander with $\lambda_{2}^{*}=O(1/\log d)$.

######  Theorem 8.2 (Tight Example of Theorem 1.4).

Given any $k\in\mathbb{N}$, if we set
$\gamma=c_{1}/\sqrt{k},\delta=c_{2}/\sqrt{k}$ for constants $0<c_{1}<c_{2}$,
then for any $(\gamma,\delta)$-spherical proximity graph $G_{k}$:

  * •

the maximum degree $d$ of $G_{k}$ is $2^{O(k)}$;

  * •

$\psi(G_{k})=\Theta(1)$; and

  * •

$\lambda_{2}^{*}(G_{k})=O(1/\log d)$.

The rest of the section is organized as follows. First, we show that the
construction of the spherical proximity graph is indeed possible. Then, we
prove the degree and expansion bounds, by relating them to volume ratios on
the sphere. Finally, we prove the bound on reweighted eigenvalue, using the
spherical embedding of the graph. All the proofs in this section are deferred
to Appendix E.

###  8.1 The Graph Construction

The following proposition is modified from [GM12, Lemma 8.3.22] and shows that
we can always construct a spherical proximity graph.

######  Proposition 8.3 (Constructing Spherical Proximity Graph).

For every $k$ and $\gamma>0$, there exists $n$ such that $\mathbb{S}^{k-1}$
can be partitioned into cells $S_{1},\dots,S_{n}$ with
${\mathrm{diam}}(S_{i})\leq\gamma$ and $\mu(S_{i})\in[{\epsilon},2{\epsilon}]$
for all $i\in[n]$, where ${\epsilon}:=\mu(Cap(\gamma/4))$. Therefore,
$n=\Theta(\mu(Cap(\gamma/4))^{-1})$.

###  8.2 Degree and Expansion Bounds

Now, we establish bounds on the maximum degree and vertex expansion of
$G_{k}$. We do so by connecting the quantities with the continuous notion of
volume.

Recall our choice of parameters $\gamma=c_{1}/\sqrt{k}$ and
$\delta=c_{2}/\sqrt{k}$, where $0<c_{1}<c_{2}$ are constants.

######  Lemma 8.4 (Degree, Expansion, and Volume).

Let $G=(V,E)$ be the graph constructed above.

  * •

The maximum degree of $G$ is at most

$\frac{\mu(Cap(\delta+\gamma))}{\mu(Cap(\gamma/4))}.$

  * •

For any $T\subseteq V$ with $|T|\leq|V|/2$, if we let $S_{T}:=\cup_{i\in
T}S_{i}$, then

$\psi(T)\geq\frac{\mu(S_{T}+Cap(\delta-\gamma))-\mu(S_{T})}{2\mu(S_{T})}.$

After relating the graph degree and vertex expansion to volumes of portions of
sphere, we shall now use results from high-dimensional geometry to obtain
bounds on the maximum degree and vertex expansion.

######  Proposition 8.5 (Degree Bound).

For constants $0<c_{1}<c_{2}$, it holds that

$\frac{\mu(Cap(\delta+\gamma))}{\mu(Cap(\gamma/4))}\leq 2^{O(k)}.$

######  Proposition 8.6 (Small-Volume Expansion of the Sphere).

For constants $0<c_{1}<c_{2}$ with $c_{2}-c_{1}$ sufficiently large, it holds
that for all $T\subseteq V$ with $|T|\leq|V|/2$,

$\frac{\mu(S_{T}+Cap(\delta-\gamma))-\mu(S_{T})}{\mu(S_{T})}\geq\Omega(1).$

Combining 8.4, 8.5, and 8.6 gives the first two parts of Theorem 8.2.

###  8.3 Reweighted eigenvalue bound

Finally, we bound $\lambda_{2}^{*}(G)$. On a high level, if a graph can be
embedded in a unit sphere via $i\mapsto v_{i}$, such that the centre of mass
is the origin and that each edge $ij$ satisfies $\left\lVert
v_{i}-v_{j}\right\rVert\leq\delta$, then the embedding certifies that
$\lambda_{2}^{*}(G)\leq\delta^{2}$. This is basically the proof. The details
can be found in Appendix E.

######  Proposition 8.7 (Reweighted Eigenvalue Bound).

For constants $0<c_{1}<c_{2}$, it holds that

$\lambda_{2}^{*}(G_{n})\lesssim\frac{1}{k}\lesssim\frac{1}{\log d}.$

8.7 gives the last part of Theorem 8.2. Thus, the proof of Theorem 8.2 is
complete.

##  9 Concluding Remarks

We present a new spectral theory which relates (i) reweighted eignevalues,
(ii) vertex expansion and (iii) fastest mixing time. This is analogous to the
classical spectral theory which relates (i) eigenvalues, (ii) edge conductance
and (iii) mixing time. This spectral approach for vertex expansion has the
advantage that most existing results and proofs for edge conductances and
eigenvalues have a close analog for vertex expansion and reweighted
eigenvalues with almost tight bounds. We do not intend to be exhaustive in
this paper, and we fully expect that other results relating eigenvalues and
edge conductances also have an analog for vertex expansion using reweighted
eigenvalues.

To conclude, we believe that our work provides an interesting spectral theory
for vertex expansion, as the formulations have the natural interpretation as
reweighted eigenvalues and also have close connections to other important
problems such as fastest mixing time and the reweighting conjectures in
approximation algorithms. We also believe that this approach can be extended
further for hypergraph edge expansion.

### Acknowledgements

We thank Shayan Oveis Gharan for suggesting the tight example for Theorem 1.4
in Section 8, Robert Wang for suggesting the connection to the $0/1$-polytope
expansion conjecture, and Sam Olesker-Taylor for providing insightful comments
that improved the presentation of the paper.

##  Appendix A Deferred Proofs for Weighted Vertex Expansion

Proof of 3.16.  First we consider the case that there is an optimizer
$S\subseteq V$ to $\psi(G)$, with $0<\pi(S)\leq 1/2$ and $\pi(\partial
S)/\pi(S)=\psi(G)$. For $a,b\in\mathbb{R}$ to be chosen below, we define a
solution $f,g$ to $\gamma^{(1)}(G)$ in 3.2 as follows:

$f(v):=\begin{cases}a,&\text{if }v\in S;\\\ b,&\text{if }v\not\in
S,\end{cases}\qquad g(v):=\begin{cases}(a-b)^{2},&\text{if }v\in\partial S;\\\
0,&\text{otherwise}.\end{cases}$

Then the constraints $g(u)+g(v)\geq(f(u)-f(v))^{2}$ for $uv\in E$ are
satisfied by construction. Note that we can always choose $a,b\neq 0$ that
satisfy the two equations $\pi(S)\cdot a+(1-\pi(S))\cdot b=0$ and $\pi(S)\cdot
a^{2}+(1-\pi(S))\cdot b^{2}=1$ simultaneously. This choice ensures that the
two constraints $\sum_{v\in V}\pi(v)f(v)=0$ and $\sum_{v\in
V}\pi(v)f(v)^{2}=1$ are satisfied, and so $f,g$ as defined is a feasible
solution to $\gamma^{(1)}(G)$. The objective value is

$\sum_{v\in V}\pi(v)g(v)=\pi(\partial
S)\cdot(a-b)^{2}=\psi(G)\cdot\pi(S)\cdot(a-b)^{2}\leq
2\psi(G)\cdot\pi(S)\cdot(a^{2}+b^{2})\leq 2\psi(G),$

where the last inequality uses that $\pi(S)\leq 1/2$ and so
$\pi(S)\cdot(a^{2}+b^{2})\leq\pi(S)\cdot a^{2}+(1-\pi(S))\cdot b^{2}=1$. This
proves $\gamma^{(1)}(G)\leq 2\psi(G)$ in this case.

The other case is when $\psi(G)=1$. We will show that $\gamma^{(1)}(G)\leq 2$
and this would imply that $\gamma^{(1)}(G)\leq 2\psi(G)$. Let $v$ be a vertex
with $0<\pi(v)\leq 1/2$, which must exist as long as the graph has at least
two vertices. We define a solution $f,g$ to $\gamma^{(1)}(G)$ as above with
$S=\\{v\\}$. Following the same arguments, $f,g$ is a feasible solution to
$\gamma^{(1)}(G)$ with objective value

$\sum_{v\in V}\pi(v)g(v)=\pi(v)(a-b)^{2}\leq
2\pi(v)\big{(}a^{2}+b^{2}\big{)}\leq
2\big{(}\pi(v)a^{2}+(1-\pi(v))b^{2}\big{)}=2.$

This proves $\gamma^{(1)}\leq 2\psi(G)$ in the other case when $\psi(G)=1$. ∎

Proof of 3.17.  First we shift $y$ so that both $\pi(\\{v\in V:y(v)>0\\})$ and
$\pi(\\{v\in V:y(v)<0\\}|)$ are at most $1/2$, which is always possible thanks
to the constraint $\sum_{v\in V}\pi(v)y(v)=0$. By shifting, the objective
value of the solution does not change. Let $y^{+}$ and $y^{-}$ be the
solutions with $y^{+}(v):=\max\\{y(v),0\\}$ and $y^{-}(v):=\min\\{y(v),0\\}$
for $v\in V$. Note that the objective values for $y^{+}$ and $y^{-}$ are at
most that for $y$, as $|y^{+}(u)-y^{+}(v)|\leq|y(u)-y(v)|$ and
$|y^{-}(u)-y^{-}(v)|\leq|y(u)-y(v)|$. By A.1, either $\sum_{v\in
V}\pi(v)y^{+}(v)^{2}$ or $\sum_{v\in V}\pi(v)y^{-}(v)^{2}$ is at least $1/4$.

We define $x$ to be $y^{+}$ if $\sum_{v\in V}\pi(v)y^{+}(v)^{2}\geq\sum_{v\in
V}\pi(v)y^{-}(v)^{2}$, or otherwise we define $x$ to be $-y^{-}$. Then $x\geq
0$ and $\pi(\operatorname{supp}(x))\leq 1/2$. The numerator is at most the
objective value of $y$ which is $\overrightarrow{\gamma}^{(1)}(G)$, and the
denominator is at least $1/4$ by A.1 and so the lemma follows. ∎

######  Lemma A.1.

Given a finite set $X$, a vector $f:X\rightarrow\mathbb{R}$, a distribution
$\pi$ on $X$. Let

$\operatorname{Var}_{\pi}(f):=\sum_{i\in X}\pi(i)f(i)^{2}-\bigg{(}\sum_{i\in
X}\pi(i)f(i)\bigg{)}^{2}$

be the $\pi$-variance of $f$. Let $f^{+}:=\max(f,0)$ and $f^{-}:=\max(-f,0)$
be the positive and negative parts of $f$ respectively (so that
$f=f^{+}-f^{-}$). Then,

$2\big{(}\operatorname{Var}_{\pi}(f^{+})+\operatorname{Var}_{\pi}(f^{-})\big{)}\geq\operatorname{Var}_{\pi}(f).$

###### Proof.

Let $S^{+}\subseteq X:=\\{i\in X:f(i)\geq 0\\}$ and $S^{-}\subseteq X:=\\{i\in
X:f(i)<0\\}$. Suppose $\pi(S^{+}),\pi(S^{-})>0$; otherwise either $f^{+}=f$ or
$f^{-}=f$, and there is nothing to prove. Then

$\displaystyle\operatorname{Var}_{\pi}(f^{+})$ $\displaystyle=$
$\displaystyle\sum_{i\in S^{+}}\pi(i)f(i)^{2}-\bigg{(}\sum_{i\in
S^{+}}\pi(i)f(i)\bigg{)}^{2}$ $\displaystyle=$
$\displaystyle\pi(S^{+})\sum_{i\in
S^{+}}\frac{\pi(i)}{\pi(S^{+})}f(i)^{2}-\pi(S^{+})^{2}\bigg{(}\sum_{i\in
S^{+}}\frac{\pi(i)}{\pi(S^{+})}f(i)\bigg{)}^{2}$ $\displaystyle=$
$\displaystyle\pi(S^{+})\pi(S^{-})\sum_{i\in
S^{+}}\frac{\pi(i)}{\pi(S^{+})}f(i)^{2}+\pi(S^{+})^{2}\bigg{[}\sum_{i\in
S^{+}}\frac{\pi(i)}{\pi(S^{+})}f(i)^{2}-\bigg{(}\sum_{i\in
S^{+}}\frac{\pi(i)}{\pi(S^{+})}f(i)\bigg{)}^{2}\bigg{]}$

Similarly,

$\displaystyle\operatorname{Var}_{\pi}(f^{-})$ $\displaystyle=$
$\displaystyle\pi(S^{-})\pi(S^{+})\sum_{i\in
S^{-}}\frac{\pi(i)}{\pi(S^{-})}f(i)^{2}+\pi(S^{-})^{2}\bigg{[}\sum_{i\in
S^{-}}\frac{\pi(i)}{\pi(S^{-})}f(i)^{2}-\bigg{(}\sum_{i\in
S^{-}}\frac{\pi(i)}{\pi(S^{-})}f(i)\bigg{)}^{2}\bigg{]}$

Therefore,

$\displaystyle\operatorname{Var}_{\pi}(f)$ $\displaystyle=$
$\displaystyle\sum_{i\in X}\pi(i)f(i)^{2}-\left(\sum_{i\in
X}\pi(i)f(i)\right)^{2}$ $\displaystyle=$ $\displaystyle\pi(S^{+})\sum_{i\in
S^{+}}\frac{\pi(i)}{\pi(S^{+})}f(i)^{2}+\pi(S^{-})\sum_{i\in
S^{-}}\frac{\pi(i)}{\pi(S^{-})}f(i)^{2}$
$\displaystyle\quad-\bigg{(}\pi(S^{+})\sum_{i\in
S^{+}}\frac{\pi(i)}{\pi(S^{+})}f(i)+\pi(S^{-})\sum_{i\in
S^{-}}\frac{\pi(i)}{\pi(S^{-})}f(i)\bigg{)}^{2}$ $\displaystyle=$
$\displaystyle\operatorname{Var}_{\pi}(f^{+})+\operatorname{Var}_{\pi}(f^{-})-2\pi(S^{+})\pi(S^{-})\bigg{(}\sum_{i\in
S^{+}}\frac{\pi(i)}{\pi(S^{+})}f(i)\bigg{)}\bigg{(}\sum_{i\in
S^{-}}\frac{\pi(i)}{\pi(S^{-})}f(i)\bigg{)}$ $\displaystyle\leq$
$\displaystyle\operatorname{Var}_{\pi}(f^{+})+\operatorname{Var}_{\pi}(f^{-})+\pi(S^{+})\pi(S^{-})\bigg{[}\bigg{(}\sum_{i\in
S^{+}}\frac{\pi(i)}{\pi(S^{+})}f(i)\bigg{)}^{2}+\bigg{(}\sum_{i\in
S^{-}}\frac{\pi(i)}{\pi(S^{-})}f(i)\bigg{)}^{2}\bigg{]}$ $\displaystyle\leq$
$\displaystyle\operatorname{Var}_{\pi}(f^{+})+\operatorname{Var}_{\pi}(f^{-})+\pi(S^{+})\pi(S^{-})\bigg{[}\bigg{(}\sum_{i\in
S^{+}}\frac{\pi(i)}{\pi(S^{+})}f(i)^{2}\bigg{)}+\bigg{(}\sum_{i\in
S^{-}}\frac{\pi(i)}{\pi(S^{-})}f(i)^{2}\bigg{)}\bigg{]}$ $\displaystyle\leq$
$\displaystyle
2\big{(}\operatorname{Var}_{\pi}(f^{+})+\operatorname{Var}_{\pi}(f^{-})\big{)},$

∎

Proof of Theorem 3.15.  The easy direction $\gamma^{(1)}(G)\lesssim\psi(G)$ is
proved in 3.16. For the hard direction, given a solution $y$ and
$\overrightarrow{E}$ to $\overrightarrow{\gamma}^{(1)}(G)$, we apply the
truncation step in 3.17 to obtain $x\geq 0$ with
$\pi(\operatorname{supp}(x))\leq 1/2$ and $\big{(}\sum_{v\in
V}\pi(v)\max_{u:u\to v}(x(u)-x(v))^{2}\big{)}/\big{(}\sum_{v\in
V}\pi(v)x(v)^{2}\big{)}\leq 4\overrightarrow{\gamma}^{(1)}(G).$ Then, we apply
the threshold rounding step in 3.19 on $x$ to obtain a set $S$ with
$S\subseteq\operatorname{supp}(x)$ and
$\overrightarrow{\psi}(S)\lesssim\sqrt{\overrightarrow{\gamma}^{(1)}(G)}$. If
$\overrightarrow{\psi}(S)\geq 1/2$, then it implies that
$\overrightarrow{\gamma}^{(1)}(G)=\Omega(1)$, and so the inequality
$\psi(G)^{2}\lesssim\overrightarrow{\gamma}^{(1)}(G)$ holds trivially as
$\psi(G)\leq 1$ by definition. Otherwise, if $\overrightarrow{\psi}(S)<1/2$,
we apply the postprocessing step in 3.20 on $S$ to obtain $S^{\prime}\subseteq
S$ with $\psi(S^{\prime})\leq 2\overrightarrow{\psi}(S)$. Therefore,
$S^{\prime}$ is a set with
$\pi(S^{\prime})\leq\pi(S)\leq\pi(\operatorname{supp}(x))\leq 1/2$ and
$\psi(S^{\prime})\leq
2\overrightarrow{\psi}(S)\lesssim\sqrt{\overrightarrow{\gamma}^{(1)}(G)}$.
Thus we conclude the hard direction that
$\psi(G)\leq\psi(S^{\prime})\lesssim\sqrt{\overrightarrow{\gamma}^{(1)}(G)}\lesssim\sqrt{\gamma^{(1)}(G)}$.
∎

##  Appendix B Deferred Proofs for Bipartite Vertex Expansion

Proof of 4.8.  First we consider the case that there is an optimizer
$S\subseteq V$ to $\psi_{B}(G)$, with bipartition $S=(S_{1},S_{2})$ and
$\pi(\partial S)/\pi(S)=\psi_{B}(G)$. Define $f:V\rightarrow\mathbb{R}$ and
$g:V\rightarrow\mathbb{R}$ as follows:

  * •

$f(u)=1$ if $u\in S_{1}$, and $f(u)=-1$ if $u\in S_{2}$, and $f(u)=0$ if
$u\not\in S$;

  * •

$g(u)=1$ if $u\in\partial S$, and $g(u)=0$ otherwise.

For each edge $uv\in E$, we claim that $g(u)+g(v)\geq(f(u)+f(v))^{2}$. Note
that $u$ and $v$ cannot both belong to $S_{1}$ or both belong to $S_{2}$. One
can check that the constraint is satisfied in all the remaining cases: (1)
$u\in S_{1}$ and $v\in S_{2}$ (or vice versa), (2) $u\in S$ and $v\not\in S$
(or vice versa), and (3) $u,v\not\in S$. So, $(f,g)$ is a feasible solution to
the $\nu^{(1)}(G)$ program, and the objective value is

$\frac{\sum_{v\in V}\pi(v)g(v)}{\sum_{v\in
V}\pi(v)f(v)^{2}}=\frac{\sum_{v\in\partial S}\pi(v)}{\sum_{v\in S_{1}\cup
S_{2}}\pi(v)}=\frac{\pi(\partial S)}{\pi(S)}=\psi_{B}(S).$

This implies that $\nu^{(1)}(G)\leq 2\psi_{B}(S)$ in this case. The other case
is when $\psi_{B}(G)=1$. Choosing the feasible solution $f\equiv 1$ and
$g\equiv 2$ to the $\nu^{(1)}(G)$ program shows that $\nu^{(1)}(G)\leq 2$.
This implies that $\nu^{(1)}(G)\leq 2\psi_{B}(G)$ in the other case. ∎

Proof of Theorem 4.4.  The easy direction $\nu^{(1)}(G)\lesssim\psi_{B}(G)$ is
proved in 4.8. For the hard direction, given a solution $x$ and
$\overrightarrow{E}$ to $\overrightarrow{\nu}^{(1)}(G)$, we apply the
threshold rounding step in 4.10 on $x$ to obtain two disjoint sets
$S_{1},S_{2}\subseteq V$ with
$\overrightarrow{\psi}(S_{1},S_{2})\lesssim\sqrt{\overrightarrow{\nu}^{(1)}(G)}$.
If $\overrightarrow{\psi}(S_{1},S_{2})\geq 1/2$, then it implies that
$\overrightarrow{\nu}^{(1)}(G)=\Omega(1)$, and so the inequality
$\psi_{B}(G)^{2}\lesssim\overrightarrow{\nu}^{(1)}(G)$ holds trivially as
$\psi_{B}(G)\leq 1$ by definition. Otherwise, if
$\overrightarrow{\psi}(S_{1},S_{2})<1/2$, we apply the postprocessing step in
4.11 on $(S_{1},S_{2})$ to obtain $(S_{1}^{\prime},S_{2}^{\prime})$ so that
$S_{1}^{\prime}\cup S_{2}^{\prime}$ is an induced bipartite graph in $G$ and
$\psi(S_{1}^{\prime}\cup S_{2}^{\prime})\leq
2\overrightarrow{\psi}(S_{1},S_{2})$. Thus we conclude the hard direction that
$\psi_{B}(G)\leq\psi_{B}(S_{1}^{\prime}\cup S_{2}^{\prime})\leq
2\overrightarrow{\psi}(S_{1},S_{2})\lesssim\sqrt{\overrightarrow{\nu}^{(1)}(G)}$.
∎

##  Appendix C Deferred Proofs for Multiway Vertex Expansion

Proof of 5.9.  By the Laurent-Massart bound of $\chi$-squared distribution
(c.f. Lemma 1 of [LM00]), for any $\delta>0$ and $i\leq d$,

$\Pr\big{[}Y_{i}-1\geq 2\sqrt{\delta/m}+2(\delta/m)\big{]}\leq e^{-\delta}.$

Since

$1+2\sqrt{\delta/m}+2(\delta/m)\leq 4+4(\delta/m)$

it follows that

$\Pr[Y_{i}\geq 4+4(\delta/m)]\leq e^{-\delta}.$

Recall that $Y=\max_{i\leq d}Y_{i}$. Taking union bound over the $Y_{i}$’s,

$\Pr[Y\geq 4+4(\delta/m)]\leq d\cdot e^{-\delta}.$

With this probability tail bound, the expectation of $Y$ can be bounded as
follows:

$\displaystyle\mathbb{E}[Y]$ $\displaystyle=$
$\displaystyle\int_{0}^{\infty}\Pr[Y\geq
t]\,dt~{}\leq~{}4+\int_{0}^{\infty}\Pr[Y\geq
4+t]\,dt~{}\leq~{}4+\int_{0}^{\infty}\min\big{\\{}1,d\cdot
e^{-mt/4}\big{\\}}\,dt\quad$ $\displaystyle=$ $\displaystyle 4+\frac{4\log
d}{m}+\int_{\frac{4\log d}{m}}^{\infty}d\cdot
e^{-mt/4}\,dt~{}=~{}4+\frac{4\log d}{m}-\frac{4d}{m}\cdot
e^{-mt/4}\Big{|}_{\frac{4\log d}{m}}^{\infty}~{}=~{}4+\frac{4\log
d}{m}+\frac{4}{m}.$

∎

Proof of 5.19.  If $\psi_{k}(G)\geq 1$, then the lemma holds trivially as
$\lambda_{k}^{*}(G)\leq 2$. Henceforth, we assume $\psi_{k}(G)<1$, and there
are nonempty disjoint subsets $S_{1},\dots,S_{k}\subseteq V$ with $\max_{1\leq
i\leq k}\psi(S_{i})=\psi_{k}(G)$.

Using the notation in 5.2, the $\lambda_{k}^{*}$ program in 1.9 can be written
as

$\displaystyle\lambda_{k}^{*}(G)~{}:=~{}\max_{Q\geq
0}\min_{f_{1},\dots,f_{k}:V\rightarrow\mathbb{R}}\max_{1\leq i\leq k}$
$\displaystyle~{}~{}~{}f_{i}^{T}(\Pi-Q)f_{i}$ subject to
$\displaystyle~{}~{}~{}\sum_{v}\pi(v)f_{i}(v)^{2}=1$ $\displaystyle\forall
1\leq i\leq k$ $\displaystyle~{}~{}~{}\sum_{v}\pi(v)f_{i}(v)f_{j}(v)=0$
$\displaystyle\forall 1\leq i\neq j\leq k$ $\displaystyle~{}~{}~{}Q(u,v)=0$
$\displaystyle\forall uv\notin E$ $\displaystyle~{}~{}~{}\sum_{v\in
V}Q(u,v)=\pi(u)$ $\displaystyle\forall u\in V$
$\displaystyle~{}~{}~{}Q(u,v)=Q(v,u)$ $\displaystyle\forall uv\in E.$

Each $f_{i}^{T}(\Pi-Q)f_{i}$ can be written as

$\sum_{uv\in E}Q(u,v)\big{(}f_{i}(u)-f_{i}(v)\big{)}^{2}=\sum_{uv\in
E}\pi(u)P(u,v)\big{(}f_{i}(u)-f_{i}(v)\big{)}^{2}.$

We set

$f_{i}(u):=\begin{cases}\frac{1}{\sqrt{\pi(S_{i})}},&\text{ if $u\in S_{i}$
}\\\ 0,&\text{ otherwise.}\end{cases}$

We can check that the constraints on $f_{i}$ are satisfied. Moreover, for any
$P$ satisfying the constraints,

$\displaystyle\sum_{uv\in E}\pi(u)P(u,v)\big{(}f_{i}(u)-f_{i}(v)\big{)}^{2}$
$\displaystyle=$ $\displaystyle\sum_{v\in
S_{i},u\in\partial(S_{i})}\pi(u)P(u,v)\frac{1}{\pi(S_{i})}$
$\displaystyle\leq$ $\displaystyle\frac{1}{\pi(S_{i})}\sum_{v\in
V,u\in\partial(S_{i})}\pi(u)P(u,v)~{}=~{}\frac{\pi(\partial(S_{i}))}{\pi(S_{i})}~{}=~{}\psi(S_{i}).$

So, $\max_{1\leq i\leq k}f_{i}^{T}(\Pi-\Pi P)f_{i}\leq\max_{1\leq i\leq
k}\psi(S_{i})$. Taking maximum over $P$ gives
$\lambda_{k}^{*}(G)\leq\psi_{k}(G)$. ∎

##  Appendix D Deferred Proofs for 0/1-Polytopes with Poor Vertex Expansion

Proof of 7.4.  The plan is to prove that the stated conditions imply
$\frac{1}{2}(x+y)\in{\rm conv}(M)$, which would then immediately imply that
there is no edge connecting $x$ and $y$ in $Q$. We will prove the
contrapositive: if $\frac{1}{2}(x+y)\notin{\rm conv}(M)$, then there is a
$p$-consistent affine function $l$ such that $l(z)<0$ for all $z\in M$
matching the pattern $p$.

Denote $w:=\frac{1}{2}(x+y)$. As $w\notin{\rm conv}(M)$, by 2.6, there is an
affine function
$l^{\prime}:(u_{1},\dots,u_{n})\mapsto\beta^{\prime}+\sum_{i}\alpha_{i}^{\prime}u_{i}$
such that $l^{\prime}(w)=0$ and $l^{\prime}(z)<0$ for all $z\in M$. We would
like to modify $l^{\prime}$ to obtain an affine function
$l:(u_{1},\dots,u_{n})\mapsto\beta+\sum_{i}\alpha_{i}u_{i}$ such that (i)
$l(w)=0$, (ii) $\alpha_{i}=0$ for $i\in\operatorname{supp}(p)$, and (iii)
$l(z)<0$ for all $z\in M$ matching the pattern $p$.

Note that, by the definition of common pattern, for
$i\in\operatorname{supp}(p)$, either $x_{i}=y_{i}=1$ or $x_{i}=y_{i}=0$, and
so $w_{i}\in\\{0,1\\}$. Also, for any $z\in\\{0,1\\}^{n}$ that matches the
pattern $p$, we must have $z_{i}=w_{i}$ for $i\in\operatorname{supp}(p)$. So,
for any such $z$,

$\displaystyle
l^{\prime}(z)=\beta^{\prime}+\sum_{i=1}^{n}\alpha^{\prime}_{i}z_{i}=\bigg{(}\beta^{\prime}+\sum_{i\in\operatorname{supp}(p)}\alpha^{\prime}_{i}z_{i}\bigg{)}+\sum_{i\not\in\operatorname{supp}(p)}\alpha^{\prime}_{i}z_{i}=\bigg{(}\beta^{\prime}+\sum_{i\in\operatorname{supp}(p)}\alpha^{\prime}_{i}w_{i}\bigg{)}+\sum_{i\not\in\operatorname{supp}(p)}\alpha^{\prime}_{i}z_{i}.$

Hence, if we set
$\beta:=\beta^{\prime}+\sum_{i\in\operatorname{supp}(p)}\alpha_{i}^{\prime}w_{i}$,
and $\alpha_{i}=\alpha^{\prime}_{i}$ for $i\notin\operatorname{supp}(p)$ and
$\alpha_{i}=0$ for $i\in\operatorname{supp}(p)$, then the affine function
$l:(u_{1},u_{2},\dots,u_{n})\in\mathbb{R}^{n}\mapsto\beta+\sum_{i}\alpha_{i}u_{i}$
satisfies $l(z)=l^{\prime}(z)$ for any $z$ that matches the pattern $p$.
Therefore, $l$ is an affine function that satisfies the three properties that
(i) $l(w)=l^{\prime}(w)=0$, (ii) $\alpha_{i}=0$ for
$i\in\operatorname{supp}(p)$, and (iii) $l(z)=l^{\prime}(z)<0$ for $z\in M$
matching the pattern $p$. ∎

Proof of 7.5.  Note that for $x\in L$ and $y\in R$ in our construction in 7.1,
their common pattern $p$ satisfies
$|\operatorname{supp}_{0}(p)|=|\operatorname{supp}_{1}(p)|\leq k$. The lemma
follows by applying 7.4 on all possible such patterns. ∎

Proof of 7.6.  Let $z\in\\{0,1\\}^{n}$ be such that $|z|=\frac{n}{2}$ and $z$
matching the pattern $p$. Let $z^{\tau}\in\\{0,1\\}^{n}$ be its “opposite
point” formed by toggling the coordinates of $z_{i}$ for
$i\not\in\operatorname{supp}(p)$ and leaving other coordinates unchanged. Note
that the lemma follows from the following two facts: (i)
$|z^{\tau}|=\frac{n}{2}$ and $z^{\tau}$ matches the pattern $p$, and (ii)
$l(z)+l(z^{\tau})=0$.

For the first fact, $z^{\tau}$ matches the pattern $p$ because
$z^{\tau}_{i}=z_{i}$ for $i\in\operatorname{supp}(p)$. And
$|z^{\tau}|=\frac{n}{2}$ because $|z|=\frac{n}{2}$ and there are the same
number of zeroes and ones in $p$, the latter being a consequence of
$|x|+|y|=k+(n-k)=n$.

For the second fact, as $l$ is $p$-consistent,

$\displaystyle
l(z)+l(z^{\tau})=\bigg{(}\beta+\sum_{i\not\in\operatorname{supp}(p)}\alpha_{i}z_{i}\bigg{)}+\bigg{(}\beta+\sum_{i\not\in\operatorname{supp}(p)}\alpha_{i}z_{i}^{\tau}\bigg{)}=2\bigg{(}\beta+\frac{1}{2}\sum_{i\not\in\operatorname{supp}(p)}\alpha_{i}\bigg{)}=0,$

where the last equality is from the second condition in 7.3. ∎

Proof of 7.7.  The number of points $z\in\\{0,1\\}^{n}$ with $|z|=\frac{n}{2}$
is ${n\choose n/2}$, whereas the number of such points that matches pattern
$p$ is ${n-2s\choose n/2-s}$. Therefore,

$\displaystyle\Pr_{z\sim Z}[z\text{ matches pattern }p]~{}=~{}{n-2s\choose
n/2-s}\Big{/}{n\choose
n/2}~{}\gtrsim~{}\bigg{(}\sqrt{\frac{2}{\pi(n-2s)}}\cdot
2^{n-2s}\bigg{)}\Big{/}\bigg{(}\sqrt{\frac{2}{\pi n}}\cdot
2^{n}\bigg{)}~{}\geq~{}4^{-s},$

where we used Stirling’s approximation $n!\approx_{n}\sqrt{2\pi n}(n/e)^{n}$.
∎

Proof of Theorem 1.12.  Let $Q$ be a $0/1$-polytope from 7.1. We would like to
apply 7.5 to prove the theorem.

Let $Z$ be the uniform distribution on $\\{z\in\\{0,1\\}^{n}:|z|=n/2\\}$.
Combining 7.6 and 7.7, it follows that for any pattern $p$ with
$|\operatorname{supp}_{0}(p)|=|\operatorname{supp}_{1}(p)|=s\leq k$ and any
$p$-consistent affine function $l$,

$\displaystyle\Pr_{z\sim Z}\left[\,l(z)\geq 0\text{ and }z\text{ matches
pattern }p\,\right]\geq c\cdot 4^{-s}$

for some universal constant $c>0$. Therefore, if we take independent samples
$z_{1},\dots,z_{m}\sim Z$ and set $M:=\\{z_{1},\dots,z_{m}\\}$ where $m$ is a
value to be determined later, then for any pattern $p$ with
$|\operatorname{supp}_{0}(p)|=|\operatorname{supp}_{1}(p)|=s\leq k$ and any
$p$-consistent affine function $l$,

$\displaystyle\Pr[\nexists z\in M\text{ with }l(z)\geq 0\text{ and }z\text{
matching pattern }p]~{}\leq~{}(1-c\cdot 4^{-s})^{m}~{}\leq~{}(1-c\cdot
4^{-k})^{m}.$

To apply a union bound, we upper bound the numbers of different such $p$ and
$l$. The number of patterns $p$ with
$|\operatorname{supp}_{0}(p)|=|\operatorname{supp}_{1}(p)|=s\leq k$ is

$\sum_{s=0}^{k}{n\choose 2s}\cdot{2s\choose s}\leq(k+1)\cdot n^{2k}.$

The number of $p$-consistent affine functions $l$ with different sign patterns
on the boolean hypercube $\\{0,1\\}^{n}$ is upper bounded by the number of
affine threshold functions on $\\{0,1\\}^{n}$, which is at most $2^{n^{2}}$ by
7.8. Combining the two estimates and the above probability bound, the failure
probability is

$\Pr[\exists p~{}\exists l\text{ s.t. }\nexists z\in M\text{ with }l(z)\geq
0\text{ and }z\text{ matching pattern }p]\leq(1-c\cdot
4^{-k})^{m}\cdot(k+1)\cdot n^{2k}\cdot 2^{n^{2}}.$

Setting

$m~{}=~{}\frac{4^{k}}{c}\cdot(1+\log(k+1)+2k\log n+n^{2}\log
2)~{}\lesssim~{}4^{k}n^{2},$

the failure probability is at most

$\displaystyle(1-c\cdot 4^{-k})^{m}\cdot(k+1)\cdot n^{2k}\cdot 2^{n^{2}}$
$\displaystyle\leq$ $\displaystyle\exp(-c\cdot 4^{-k}\cdot
m)\cdot\exp(\log(k+1)+2k\log n+n^{2}\log 2)$ $\displaystyle\leq$
$\displaystyle\exp(-(1+\log(k+1)+2k\log n+n^{2}\log
2))\cdot\exp(\log(k+1)+2k\log n+n^{2}\log 2)$ $\displaystyle=$ $\displaystyle
e^{-1}.$

Therefore, by 7.5, we conclude that there exists
$M\subseteq\\{z\in\\{0,1\\}^{n}:|z|=n/2\\}$ with $|M|\lesssim 4^{k}n^{2}$ such
that there are no edges between $L$ and $R$ in the graph of $Q$.

Finally, as $|L|={n\choose k}\geq(n/k)^{k}$ and $\partial L\subseteq M$, it
follows that

$\psi(L)\leq\frac{|M|}{|L|}\lesssim\frac{4^{k}n^{2}}{(n/k)^{k}}=\frac{(4k)^{k}}{n^{k-2}}.$

∎

##  Appendix E Deferred Proofs for Spherical Proximity Graph

Proof of 8.3.  The construction largely follows that of [GM12, Lemma 8.3.22].
Given $n$ and $\gamma>0$, we iteratively choose points
$y_{1},y_{2},\dots,y_{m}\in\mathbb{S}^{k-1}$, such that each new point
$y_{i+1}$ has distance at least $\gamma/2$ from $y_{1},\dots,y_{i}$. We stop
when it is no longer possible to choose a point that is $(\gamma/2)$-far from
all existing points.

We now let $S_{1}^{\prime},S_{2}^{\prime},\dots,S_{m}^{\prime}$ be the cells
of the Voronoi diagram of $y_{1},y_{2},\dots,y_{m}$. That is, for any
$x\in\mathbb{S}^{k-1}$, $x\in S_{i}^{\prime}$ iff
$\Delta(x,y_{i})=\min_{j\in[m]}\Delta(x,y_{j})$. Note that cell
$S_{i}^{\prime}$ contains $B(y_{i},\gamma/4)$ and is contained in
$B(y_{i},\gamma/2)$. Therefore, the measure of each $S_{i}^{\prime}$ is at
least ${\epsilon}=\mu(Cap(\gamma/4))$ and the diamater of each
$S_{i}^{\prime}$ is at most $\gamma$. By further subdividing the cells
(evenly) until each cell has measure $\leq 2{\epsilon}$, we obtain
$S_{1},S_{2},\dots,S_{n}$, such that the measure of each $S_{i}$ is between
${\epsilon}$ and $2{\epsilon}$, and ${\rm diam}(S_{i})\leq\gamma$ for each
$i\in[n]$. We can choose the points $x_{i}\in S_{i}$ arbitrarily. ∎

Proof of 8.4.  First, we prove the bound on the maximum degree. For any vertex
$i\in V$, its degree is equal to the number of points $x_{j}$ that are
$\delta$-close to $x_{i}$. We can count the number of such points using volume
estimation. If a point $x_{j}$ is within distance $\delta$ from $x_{i}$, then
the entire cell $S_{j}$ is within distance $\delta+\gamma$ from $x_{i}$. This
contributes at least ${\epsilon}=\mu(Cap(\gamma/4))$ total measure to
$B(x_{i},\delta+\gamma)$. The total measure of these cells is at most
$\mu(B(x_{i},\delta+\gamma))$, so

$|\partial(i)|\cdot\mu(Cap(\gamma/4))\leq\mu(B(x_{i},\delta+\gamma)).$

Rearranging gives the desired upper bound on $|\partial(i)|$, and thus on the
maximum degree.

Next, we prove the bound on the vertex expansion. Given any $T\subseteq V$, we
wish to lower bound $|\partial(T)|$. For $j\in V$, if the cell $S_{j}$ is
completely contained in $S_{T}+Cap(\delta)$, then $x_{j}\in T\cup\partial(T)$.
If we take the union of all such cells, then the set will contain
$S_{T}+Cap(\delta-\gamma)$:

$\cup\\{S_{j}:S_{j}\subseteq S_{T}+Cap(\delta)\\}\supseteq
S_{T}+Cap(\delta-\gamma).$

This is because, for any point $u\in S_{T}+Cap(\delta-\gamma)$, the cell that
it is in will be contained in

$\\{u\\}+Cap(\gamma)\subseteq
S_{T}+Cap(\delta-\gamma)+Cap(\gamma)=S_{T}+Cap(\delta).$

It follows that

$\cup\\{S_{j}:j\not\in T\text{ and }S_{j}\subseteq
S_{T}+Cap(\delta)\\}\supseteq(S_{T}+Cap(\delta-\gamma))\setminus S_{T}.$

Combining previous observations, and since each cell has measure at most
$2{\epsilon}$,

$\displaystyle|\partial(T)|=|(T\cup\partial(T))\setminus T|$
$\displaystyle\geq$ $\displaystyle|\\{S_{j}:j\not\in T\text{ and
}S_{j}\subseteq S_{T}+Cap(\delta)\\}|$ $\displaystyle\geq$
$\displaystyle\frac{\mu(S_{T}+Cap(\delta-\gamma))-\mu(S_{T})}{2{\epsilon}}.$

We are done after substituting this and $|T|\leq\mu(S_{T})/{\epsilon}$ into
$\psi(T)=|\partial(T)|/|T|$. ∎

Proof of 8.5.  We will use the following formula for spherical cap volume:

$\mu(Cap(x))=\frac{\int_{0}^{x}\sin^{k-2}\theta\,d\theta}{\int_{0}^{\pi}\sin^{k-2}\theta\,d\theta}.$

This comes from the formula for unnormalized spherical cap volume [Li11]:

$\mu_{0}(Cap(x))=\frac{2\pi^{(k-1)/2}}{\Gamma((k-1)/2)}\cdot\int_{0}^{x}\sin^{k-2}\theta\,d\theta.$

We shall use the approximation

$\sin^{k}\theta\approx_{k}\left(\theta-\frac{\theta^{3}}{3!}\right)^{k}$

for $0\leq\theta\leq O(1/\sqrt{k})$. The third-degree approximation is
sufficient because
$(\theta-\theta^{3}/3!+O(\theta^{5}))^{k}\approx_{k}(\theta-\theta^{3}/3!)^{k}$
for $\theta$ in this range.

Then, for $x=O(1/\sqrt{k})$,

$\displaystyle\int_{0}^{x}\sin^{k}\theta\,d\theta$ $\displaystyle\approx_{k}$
$\displaystyle\int_{0}^{x}\left(\theta-\frac{\theta^{3}}{3!}\right)^{k}\,d\theta$
$\displaystyle\approx_{k}$
$\displaystyle\int_{0}^{x}\left(\theta-\frac{\theta^{3}}{3!}\right)^{k}\cdot(1-\theta^{2}/2)\,d\theta\quad(\because(1-\theta^{2}/2)\text{
is close to }1)$ $\displaystyle\overset{y:=\theta-\theta^{3}/6}{=}$
$\displaystyle\int_{0}^{x-x^{3}/6}y^{k}\,dy\quad(\because
y(\theta):=\theta-\theta^{3}/6\text{ is increasing for $\theta\in[0,x]$})$
$\displaystyle=$ $\displaystyle\frac{(x-x^{3}/6)^{k+1}}{k+1}.$

Therefore,

$\displaystyle\frac{\mu(Cap(\delta+\gamma))}{\mu(Cap(\gamma/4))}$
$\displaystyle=$
$\displaystyle\frac{\int_{0}^{\delta+\gamma}\sin^{k-2}\theta\,d\theta}{\int_{0}^{\gamma/4}\sin^{k-2}\theta\,d\theta}$
$\displaystyle\approx_{k}$
$\displaystyle\left(\frac{\delta+\gamma}{\gamma/4}\right)^{k-1}\cdot\left(\frac{1-(\delta+\gamma)^{2}/6}{1-(\gamma/4)^{2}/6}\right)^{k-1}$
$\displaystyle=$
$\displaystyle\left(\frac{4(c_{1}+c_{2})}{c_{1}}\right)^{k-1}\cdot\left(\frac{1-(c_{1}+c_{2})/6k}{1-c_{1}/96k}\right)^{k-1}$
$\displaystyle\lesssim$
$\displaystyle\left(\frac{4(c_{1}+c_{2})}{c_{1}}\right)^{k}$
$\displaystyle\leq$ $\displaystyle 2^{O(k)}.$

∎

Proof of 8.6.  By isoperimetric results on the sphere, the worst case is when
the set $S_{T}$ is a spherical cap. Therefore, it suffices to prove that, for
any $\tau\in(0,\pi/2]$,

$\mu(Cap(\tau+(\delta-\gamma)))\geq(1+\Omega(1))\cdot\mu(Cap(\tau)).$

Let $c:=c_{2}-c_{1}>0$. This is equivalent to

$\int_{0}^{\tau+c/\sqrt{k}}\sin^{k-2}\theta\,d\theta\geq(1+\Omega(1))\int_{0}^{\tau}\sin^{k-2}\theta\,d\theta.$

For technical reasons, we first deal with the case where $\tau$ is close to
$\pi/2$. For $\tau\geq\pi/2-c/\sqrt{k}$, the result follows from well-known
upper bounds on spherical cap volume. For example, we may use the upper bound
in [Tko12]:

$\mu(Cap(\pi/2-\theta))\leq e^{-k\sin^{2}\theta/2},\qquad\theta\in[0,\pi/2)$

and the fact that $\sin\theta\approx_{k}\theta$ for $\theta=O(1/\sqrt{k})$.
Then, if $c$ is such that
$\exp\left[-k\sin^{2}\left(\frac{c}{2\sqrt{k}}\right)/2\right]\leq 1/3$,

$\frac{\mu(Cap(\tau+c/\sqrt{k}))}{\mu(Cap(\tau))}\geq\min\left(\frac{\mu(Cap(\pi/2))}{\mu(Cap(\pi/2-c/2\sqrt{k}))},\frac{\mu(Cap(\pi/2+c/2\sqrt{k}))}{\mu(Cap(\pi/2))}\right)\geq\frac{4}{3}.$

Therefore, we may assume that $\tau<\pi/2-c/\sqrt{k}$.

We will actually prove the following relation: for all
$x\in[0,\pi/2-c/\sqrt{k}]$,

$\int_{x}^{x+c/\sqrt{k}}\sin^{k-2}\theta\,d\theta\geq(1+\Omega(1))\int_{x-c/\sqrt{k}}^{x}\sin^{k-2}\theta\,d\theta.$

If this relation is proven to be true, then by writing

$\int_{0}^{\tau+c/\sqrt{k}}\sin^{k-2}\theta\,d\theta=\left(\int_{\tau}^{\tau+c/\sqrt{k}}+\int_{\tau-c/\sqrt{k}}^{\tau}+\cdots+\int_{0}^{\tau-
tc/\sqrt{k}}\right)\sin^{k-2}\theta\,d\theta,\quad(t:=\left\lfloor\frac{\tau\sqrt{k}}{c}\right\rfloor),$

and applying the above relation to each term on RHS, we obtain the desired
result.

In order to prove the relation, we show that, for all
$x\in[0,\pi/2-c/\sqrt{k}]$,

$\sin^{k-2}(x+c/\sqrt{k})\geq(1+\Omega(1))\cdot\sin^{k-2}x.$

that is, we wish to show that the function

$f(x):=\frac{\sin^{k-2}(x+c/\sqrt{k})}{\sin^{k-2}(x)}$

is at least $1+\Omega(1)$ for $x\in[0,\pi/2-c/\sqrt{k}]$.

Check that, for $k\geq 3$, $f(x)$ is decreasing by differentiating
$\sin(x+c/\sqrt{k})/\sin(x)$. It remains to compute

$\displaystyle f(\pi/2-c/\sqrt{k})$ $\displaystyle=$
$\displaystyle\frac{\sin^{k-2}(\pi/2)}{\sin^{k-2}(\pi/2-c/\sqrt{k})}$
$\displaystyle=$ $\displaystyle[\cos(c/\sqrt{k})]^{-(k-2)}$ $\displaystyle=$
$\displaystyle\left(1-\frac{c^{2}}{2k}\right)^{-(k-2)}+o(1)\qquad(\text{by
Taylor expansion})$ $\displaystyle=$ $\displaystyle\exp(c^{2}/2)+o_{k}(1).$

Therefore, for sufficiently large $k$, $f(x)\geq 1+\Omega(1)$, where the
constant depends on $c$. ∎

Proof of 8.7.  We wish to construct test vectors $\\{v_{i}\\}_{i\in[n]}$, such
that $\sum_{i\in[n]}v_{i}=\vec{0}$ and

$\frac{\sum_{(i,j)\in E}P(i,j)\left\lVert
v_{i}-v_{j}\right\rVert^{2}}{\sum_{i\in[n]}\left\lVert v_{i}\right\rVert^{2}}$

is small for any doubly stochastic reweighting $P$ of the graph $G_{n}$.

We claim that setting $v_{i}:=x_{i}-z$ works, where
$z:=\frac{1}{n}\sum_{j\in[n]}x_{j}$. By construction,
$\sum_{i\in[n]}v_{i}=\vec{0}$. We next show that

$\sum_{i\in[n]}\left\lVert v_{i}\right\rVert^{2}\geq\Omega(n).$

Since $\sum_{i\in[n]}v_{i}=\vec{0}$, note that

$\sum_{i\in[n]}\left\lVert
v_{i}\right\rVert^{2}=\frac{1}{2n}\sum_{i,j\in[n]}\left\lVert
v_{i}-v_{j}\right\rVert^{2}=\frac{1}{2n}\sum_{i,j\in[n]}\left\lVert
x_{i}-x_{j}\right\rVert^{2}.$

It then suffices to show that

$\sum_{j\in[n]}\left\lVert x_{i}-x_{j}\right\rVert^{2}\geq\Omega(n)$

for all $i\in[n]$. This follows from the fact that at least $\frac{n}{3}$ of
the points $x_{j}$ are of geodesic distance at least
$\frac{\pi}{2}-\gamma\geq\Omega(1)$ from $x_{i}$, and so are of Euclidean
distance $\Omega(1)$ from $x_{i}$.

Therefore, for any doubly stochastic reweighting $P$,

$\displaystyle\lambda_{2}(P)\leq\frac{\sum_{(i,j)\in E}P(i,j)\left\lVert
v_{i}-v_{j}\right\rVert^{2}}{\sum_{i\in V}\left\lVert
v_{i}\right\rVert^{2}}\leq\frac{\sum_{i\in[n]}\sum_{j:(i,j)\in
E}P(i,j)\cdot\delta^{2}}{\Omega(n)}=O(\delta^{2}).$

Note that, in the second inequality, we used the fact that straight-line
distance in $\mathbb{R}^{k}$ is less than or equal to geodesic distance in
$\mathbb{S}^{k-1}$.

We conclude that $\lambda_{2}^{*}(G)\lesssim\delta^{2}\lesssim 1/k$. Combining
with the degree bound in Proposition 8.5,

$\lambda_{2}^{*}(G)\lesssim\frac{1}{k}\lesssim\frac{1}{\log d}.$

∎

## References

  * [Alo86] Noga Alon. Eigenvalues and expanders. Combinatorica, 6, 83–96, 1986.
  * [AM85] Noga Alon, Vitali Milman. $\lambda_{1}$, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B, 38(1), 73–88, 1985.
  * [ALOV19] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant. Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. In Proceedings of the 51th Annual Symposium on Theory of Computing (STOC), 1–12, 2019.
  * [ABS10] Sanjeev Arora, Boaz Barak, David Steurer. Subexponential algorithms for unique games and related problems. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 563–572, 2010.
  * [AG11] Sanjeev Arora, Rong Ge. New tools for graph coloring. In Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), 1–12, 2011.
  * [ARV09] Sanjeev Arora, Satish Rao, Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM, 56(2):1–37, 2009.
  * [Blu94] Avrim Blum. New approximation algorithms for graph coloring. Journal of the ACM, 41:470–516, 1994.
  * [BHT00] S. Bobkov, C. Houdré, Prasad Tetali. $\lambda_{\infty}$, vertex isoperimetry and concentration. Combinatorica 20(2):153–172, 2000.
  * [BDPX09] Stephen Boyd, Persi Diaconis, Pablo Parrilo, Lin Xiao. Fastest mixing time on graphs with symmetries. SIAM Journal on Optimization, 20(2):792–819, 2009.
  * [BDSX06] Stephen Boyd, Persi Diaconis, J. Sun, Lin Xiao. Fastest mixing Markov chain on a path. American Mathematical Monthly, 113(1):70–74, 2006.
  * [BDX04] Stephen Boyd, Persi Diaconis, Lin Xiao.  Fastest mixing markov chain on a graph.  SIAM review, 46(4):667–689, 2004.
  * [CLTZ18] T.-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, Chenzi Zhang. Spectral properties of hypergraph Laplacian and approximation algorithms. Journal of the ACM, 65(3):1–48, 2018.
  * [CTWZ17] T.-H. Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu, Chenzi Zhang. Diffusion operator and spectral analysis for directed hypergraph Laplacian. CoRR abs/1711.01560, 2017.
  * [Che70] Jeff Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. Problems in Analysis, Princeton University Press, 195–199, 1970.
  * [CA15] O. Cihan, M. Akar. Fastest mixing reversible Markov chains on graphs with degree proportional stationary distributions. Transactions on Automatic Control, 60(1):227–232, 2015.
  * [Cov65] Thomas M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers, 3:326–334, 1965.
  * [FLT20] Majid Farhadi, Anand Louis, Prasad Tetali. On the complexity of $\lambda_{\infty}$, vertex expansion, and spread constant of trees. In arXiv:2003.05582, 2020.
  * [FM92] Tomás Feder, Milena Mihail. Balanced matroids. In Proceedings of the 24th Annual Symposium on Theory of Computing (STOC), 26–38, 1992.
  * [FHL08] Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM Journal on Computing, 38(2):629–657, 2008.
  * [FK13] J.A. Fill, Jeff Kahn. Comparision inequalities and fastest mixing Markov chains. Annals of Applied Probability, 23(5):1778–1816, 2013.
  * [GM12] Bernd Gärtner and Jiri Matousek. Approximation algorithms and semidefinite programming. Springer, 2012.
  * [Gil07] Rafael Gillmann. 0/1-polytopes: typical and extremal properties. Ph.D. thesis, Technische Universität Berlin, 2007.
  * [GKL03] Anupam Gupta, Robert Krauthgamer, James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS), 534–543, 2003.
  * [JPV22] Vishesh Jain, Huy Tuan Pham, and Thuy-Duong Vuong. Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain. In arXiv:2203.03858, 2022.
  * [Kai04] Volker Kaibel. On the expansion of graphs of $0/1$-polytopes. The Sharpest Cut. MPS-SAIM series on optimization 4, 199–216, 2004.
  * [KR03] Volker Kaibel, Anja Remshagen. On the graph-density of random $0/1$-polytopes. In Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 318–328, 2003.
  * [KLLOT13] Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan. Improved Cheeger’s inequality: Analysis of spectral partitioning algorithms through higher order spectral gap. In Proceedings of the 45th Annual Symposium on Theory of Computing (STOC), 11–20, 2013.
  * [LM00] Beatrice Laurent, Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, 1302–1338, 2000.
  * [LOT12] James R. Lee, Shayan Oveis Gharan, Luca Trevisan. Multi-way spectral partitioning and higher-order Cheeger inequalities. In Proceedings of the 44th Annual Symposium on Theory of Computing (STOC), 1117–1130, 2012.
  * [LP17] David Levin and Yuval Peres. Markov chains and mixing times. American Mathematical Society, Volume 107, 2017.
  * [Li11] Shengqiao Li. Concise formulas for the area and volume of a hyperspherical cap. Asian Journal of Mathematics and Statistics, Volume 4, No. 1, 66–70, 2011.
  * [Lou15] Anand Louis. Hypergraph Markov operators, eigenvalues and approximation algorthms. In Proceedings of the 47th Annual Symposium on Theory of Computing (STOC), 713–722, 2015.
  * [LRTV12] Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala. Many sparse cuts via higher eigenvalues. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), 1131–1140, 2012.
  * [LRV13] Anand Louis, Prasad Raghavendra, Santosh Vempala. The complexity of approximating vertex expansion. In Proceedings of the 54th IEEE Annual Symposium on Foundations of Computer Secience (FOCS), 360–369, 2013.
  * [OZ22] Sam Olesker-Taylor, Luca Zanetti. Geometric bounds on the fastest mixing Markov chain. In the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022).
  * [RS10] Prasad Raghavendra, David Steurer. Graph expansion and the unique games conjecture. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), 755–764, 2010.
  * [Roc05] Sébastien Roch. Bounding fastest mixing. Electron. Commun. Probab. 10:282–296, 2005.
  * [Sim95] Stephen Simons. Minimax theorems and their proofs. Minimax and applications, 1–23, 1995.
  * [Ste10] David Steurer. On the complexity of unique games and graph expansion. Ph.D. thesis, Princeton University, 2010.
  * [Tan84] R.M. Tanner. Explicit construction of concentrators from generalized $N$-gons. SIAM J. Algebraic Discrete Methods 5: 287–294, 1984.
  * [Tko12] Tomasz Tkocz. An upper bound for spherical caps. The American Mathematical Monthly, Volume 119, No. 7, 606–607, 2012.
  * [Tre09] Luca Trevisan. Max cut and the smallest eigenvalue. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), 263–272, 2009.