# KUIELab-MDX-Net: A Two-Stream Neural Network for Music Demixing

Minseok Kim111co-first author Woosung Choi222co-first author Jaehwa Chung
Daewon Lee  Soonyoung Jung333corresponding author

††margin:  License
Authors of papers retain copyright and release the work under a Creative
Commons Attribution 4.0 International License
(http://creativecommons.org/licenses/by/4.0/https://doi.orgCC BY 4.0). In
partnership with

## Summary

Recently, many methods based on deep learning have been proposed for music
source separation. Some state-of-the-art methods have shown that stacking many
layers with many skip connections improve the SDR performance. Although such a
deep and complex architecture shows outstanding performance, it usually
requires numerous computing resources and time for training and evaluation.
This paper proposes a two-stream neural network for music demixing, called
KUIELab-MDX-Net, which shows a good balance of performance and required
resources. The proposed model has a time-frequency branch and a time-domain
branch, where each branch separates stems, respectively. It blends results
from two streams to generate the final estimation. KUIELab-MDX-Net took second
place on leaderboard A and third place on leaderboard B in the Music Demixing
Challenge at ISMIR 2021. This paper also summarizes experimental results on
another benchmark, MUSDB18. Our source code is available online
444https://github.com/kuielab/mdx-net.

## Introduction

Recently, many methods have been proposed for music source separation.
Notably, deep learning approaches Défossez et al. (2021) have become
mainstream because of their excellent performance. Some state-of-the-art
methods (Choi et al., 2020; Takahashi et al., 2018; Takahashi & Mitsufuji,
2021, 2017) have shown that stacking many layers with many skip connections
improve the SDR performance.

Although a deep and complex architecture shows outstanding performance, it
usually requires numerous computing resources and time for training and
evaluation. Such disadvantages make them not affordable in a restricted
environment where limited resources are provided. For example, some deep
models such as LaSAFT-Net (Choi et al., 2021) exceed the time limit of the
Music Demixing Challenge (MDX) at ISMIR 2021 (Mitsufuji et al., 2021) even if
they are the current state of the art on the MUSDB18 (Rafii et al., 2017b)
benchmark.

This paper presents a source separation model named KUIELab-MDX-Net. We
empirically found a good balance of performance and required resources to
design KUIElab-MDX-Net. For example, we replaced channel-wise concatenation
operations with simple element-wise multiplications for each skip connection
between encoder and decoder (i.e., for each U-connection in U-Net). In our
prior experiments, it reduced parameters with negligible performance
degradation.

Also, we removed the other skip connections, especially, skip connections used
in dense blocks (Choi et al., 2020; Takahashi et al., 2018; Takahashi &
Mitsufuji, 2021, 2017). We observed that stacked convolutional networks
without dense connections followed by Time-Distributed Fully connected layers
(TDF) (Choi et al., 2020) could perform comparably to dense blocks without
TDFs. TDF, proposed in (Choi et al., 2020), is a sequence of linear layers. It
is applied to a given input in the frequency domain to capture frequency-to-
frequency dependencies of the target source. Since a single TDF block has the
whole receptive field in terms of frequency, injecting TDF blocks into a
conventional U-Net (Ronneberger et al., 2015) improves the SDR performance on
singing voice separation even with a shallower structure.

By introducing such tricks, we found a computationally efficient and effective
model design. As a result, the proposed architecture has a time-frequency
branch and a time-domain branch, where each branch separates stems,
respectively. It blends results from two streams to generate the final
estimation. KUIELab-MDX-Net took second place on leaderboard A and third place
on leaderboard B in the Music Demixing Challenge at ISMIR 2021. This paper
also summarizes experimental results on another benchmark, MUSDB18.

## Background

### Frequency Transformation for Source Separation

Some source separation methods (Choi, 2021; Choi et al., 2020; Yin et al.,
2020) have adopted Frequency Transformation (FT) to capture frequency-to-
frequency dependencies of the target source. Both designed their FT blocks
with fully connected layers, also known as linear layers. For example, (Choi
et al., 2020) proposed Time-Distributed Fully connected layers (TDF) to
capture frequency patterns observed in spectrograms of a singing voice. A TDF
block is a sequence of two linear layers. It is applied to a given input in
the frequency domain. The first layer downsamples the features to
$\mathbb{R}^{\lceil F/bn\rceil}$, where we denote the number of frequency bins
in a given spectrogram feature by $F$ and the bottleneck factor that controls
the degree of downsampling by $bn$.

### TFC-TDF-U-Net v1

(Choi et al., 2020) proposed the original TFC-TDF-U-Net for singing voice
separation. We call this architecture TFC-TDF-U-Net v1 for the rest of this
paper. It adopted a Time-Frequency Convolutions followed by a TDF (TFC-TDF)
block as a fundamental building block. By replacing fully connected 2-D
convolutional building blocks, conventionally used in U-Net (Ronneberger et
al., 2015) with TFC-TDF blocks, it showed a promising performance on singing
voice separation tasks of the MUSDB18 (Rafii et al., 2017b) dataset. Also,
injecting TDF blocks can enhance separation quality for the other tasks of
MUSDB18, as shown in (Choi, 2021).

(Choi, 2021) presented how adding TDF blocks improves separation quality by
visualizing trained weight matrixes of single-layered TDF blocks (they
additionally trained U-Nets with single-layered TDF blocks for weight
visualization). As shown in Figure 1, each matrix is trained to analyze timbre
features uniquely observed in its instrument by capturing harmonic patterns
(i.e., $y=\frac{\alpha}{\beta}x$). It is also observable that the TDF blocks
still performs well on each scale.

Figure 1: Weight matrixes visualization of single-layered TDF blocks

We summarized TFC-TDF-U-Net v1’s performance reported in (Choi, 2021) in the
experiment section.

## Method: KUIELab-MDX-Net

Figure 2: The Overall Architecture of KUIELab-MDX-Net

Since the original TFC-TDF-U-Net v1 is computationally heavy to be evaluated
within the time limit of the MDX challenge, we could not submit this, although
its performance was promising on the MUSDB18 benchmark. To make an affordable
model for the MDX challenge, we empirically found a good balance of
performance and required resources.

As in Figure 2, KUIELab-MDX-Net consists of six networks, all trained
separately. Figure 2 depicts the overall flow at inference time: the four
U-Net-based separation models (TFC-TDF-U-Net v2) first estimate each source
independently, then the _Mixer_ model takes these estimated sources (+
mixture) and outputs enhanced estimated sources. Also, we extract sources with
another network based on a time-domain approach, as shown on the right side of
Figure 2. We used pretrained Demucs (Défossez et al., 2021) without fine-
tuning. Finally, it takes the weighted average for each estimated source, also
known as _blending_ (Uhlich et al., 2017).

### TFC-TDF-U-Net v2

Figure 3: The architecture of TFC-TDF-U-Net v2

The following changes were made to the original TFC-TDF-U-Net architecture: -
For “U” connections, we used multiplication instead of concatenation. - Other
than U connections, all skip connections were removed. - In TFC-TDF-U-Net v1,
the number of intermediate channels are not changed after down/upsampling
layers. For v2, they are increased when downsampling and decreased when
upsampling.

On top of these architectural changes, we also use a different loss function
(time-domain $l_{1}$ loss) as well as source-specific data preprocessing. As
shown in Figure 3, high frequencies above the target source’s expected
frequency range were cut off from the mixture spectrogram. This way, we can
increase _n_fft_ while using the same input spectrogram size (which we needed
to constrain for the separation time limit), and using a larger _n_fft_
usually leads to better SDR. It is also why we did not use a multi-target
model (a single model that is trained to estimate all four sources), where we
could not use source-specific frequency cutting.

### Mixer

Although training one separation model for each source can benefit from
source-specific preprocessing and model configurations, these models lack the
knowledge that they are separating using the same mixture. We thought an
additional network that _could_ exploit this knowledge (which we call the
Mixer) could further enhance the _independently_ estimated sources. For
example, estimated ‘vocals’ often have drum snare noises left. The Mixer can
learn to remove sounds from ‘vocals’ that are also present in the estimated
‘drums’ or vice versa.

We only tried very shallow models (such as a single convolution layer) for the
Mixer during the MDX Challenge due to the time limit. We look forward to
trying more complex models in the future since even a single $1\times 1$
convolution layer was enough to make some improvement on total SDR (Section
“Performance on the MUSDB18 Benchmark”).

## Experimental Results

This section describes the model configurations, STFT parameters, training
procedure, and evaluation results on the MUSDB18 benchmark. For training, we
used the MUSDB-HQ dataset with default 86/14 train and validation splits.

### Configurations and Training

We present a comparison between configurations of TFC-TDF-U-Net v1 and v2 as
follows. This applies to all models regardless of the target source (we did
not explore different model configurations for each source). In short, v2 is a
more shallow but wider model than v1.

| # blocks | # convs per block | $bn$ | # freq bins | # STFT frames | hop size |
---|---|---|---|---|---|---|---
v1 | 9 | 5 | 16 | 2048 | 128 | 1024 |
v2 | 11 | 3 | 8 | 2048 | 256 | 1024 |

The number of intermediate channels is increased/decreased after
down/upsampling layers with a linear factor of 32. Also, as mentioned in
Section “TFC-TDF-U-Net v2,” we used different _n_fft_ for each source: (6144,
4096, 16384, 8192) for (vocals, drums, bass, other).

All five models (four separation models + Mixer) were optimized with RMSProp
with no momentum. We used random chunking and mixing instruments from
different songs for data augmentation (Uhlich et al., 2017). We also used data
augmentation based on pitch shift and time stretch (Défossez et al., 2021).
The overall training procedure can be summarized into two steps:

  1. 1.

Train single-target separation models (TFC-TDF-U-Net v2) for each source.

  2. 2.

Train the Mixer while freezing the pretrained weights of the separation
models.

### Performance on the MUSDB18 Benchmark

We compare our models with current state-of-the-art models on the MUSDB18
benchmark using the SiSEC2018 version of the SDR metric (BSS Eval v4 framewise
multi-channel SDR). We report the median SDR over all 50 songs in the MUSDB18
test set. Only models for Leaderboard A were evaluated since our submissions
for Leaderboard B uses the MUSDB18 test set as part of the training data.

We summarize the MUSDB18 benchmark performance of KUIELab-MDX-Net. We compare
it to recent state-of-the-art models: TFC-TDF-U-Net v1 (Choi et al., 2020),
X-UMX (Sawata et al., 2021), Demucs (Défossez et al., 2021), D3Net (Takahashi
& Mitsufuji, 2021), ResUNetDecouple+ (Kong et al., 2021). We also include our
baselines to validate our architectural design. Even though our models were
downsized for the MDX Challenge, we can see that it gives superior performance
over the state-of-the-art models and achieves the best SDR for every
instrument except ‘bass.’ Also, it is notable that TFC-TDF-U-Net v2 with Mixer
(i.e., v2 + Mixer) outperforms the existing methods except for ‘vocals’ even
without blending with Demucs.

| vocals | drums | bass | other
---|---|---|---|---
TFC-TDF-U-Net v1 (Choi et al., 2020) | 7.98 | 6.11 | 5.94 | 5.02
X-UMX (Sawata et al., 2021) | 6.61 | 6.47 | 5.43 | 4.64
Demucs (Défossez et al., 2021) | 6.84 | 6.86 | 7.01 | 4.42
D3Net (Takahashi & Mitsufuji, 2021) | 7.24 | 7.01 | 5.25 | 4.53
ResUNetDecouple+ (Kong et al., 2021) | 8.98 | 6.62 | 6.04 | 5.29
TFC-TDF-U-Net v2 | 8.81 | 6.52 | 7.65 | 5.70
v2 + Mixer | 8.91 | 7.07 | 7.33 | 5.81
v2 + Demucs | 8.80 | 7.14 | 8.11 | 5.90
KUIELab-MDX-Net | 9.00 | 7.33 | 7.86 | 5.95

We also compare three winning models’ performance (Mitsufuji et al., 2021) on
the MUSDB18 benchmark as follows. It should be noted that we only reported
SDRs evaluated on MUSDB18 (Rafii et al., 2017a), not MUSDB-HQ (Rafii et al.,
2019).

| vocals | drums | bass | other
---|---|---|---|---
Hybrid Demucs (defossez) | 8.04 | 8.58 | 8.67 | 5.59
KUIELab-MDX-Net (kuielab) | 9.00 | 7.33 | 7.86 | 5.95
Danna-Sep (KazaneRyonoDanna) | 7.63 | 7.20 | 7.05 | 5.20

## Acknowledgements

This research was supported by Basic Science Research Program through the
National Research Foundation of Korea(NRF) funded by the Ministry of
Education(NRF-2021R1A6A3A03046770). This work was also supported by the
National Research Foundation of Korea(NRF) grant funded by the Korea
government(MSIT)(No. NRF-2020R1A2C1012624, NRF-2021R1A2C2011452).

## References

Choi, W. (2021). _Deep learning-based latent source analysis for source-aware
audio manipulation_ [PhD thesis]. Korea University.

Choi, W., Kim, M., Chung, J., & Jung, S. (2021). Lasaft: Latent source
attentive frequency transformation for conditioned source separation. _Proc.
IEEE International Conference on Acoustics, Speech and Signal Processing
(ICASSP)_ , 171–175. https://doi.org/10.1109/ICASSP39728.2021.9413896

Choi, W., Kim, M., Chung, J., Lee, D., & Jung, S. (2020). Investigating u-nets
with various intermediate blocks for spectrogram-based singing voice
separation. _Proc. International Society for Music Information Retrieval
Conference (ISMIR)_.

Défossez, A., Usunier, N., Bottou, L., & Bach, F. (2021). _Music source
separation in the waveform domain_. http://arxiv.org/abs/1911.13254

Kong, Q., Cao, Y., Liu, H., Choi, K., & Wang, Y. (2021). Decoupling magnitude
and phase estimation with deep ResUNet for music source separation. _CoRR_ ,
_abs/2109.05418_. https://arxiv.org/abs/2109.05418

Liu, J.-Y., & Yang, Y.-H. (2019). Dilated convolution with dilated GRU for
music source separation. _Proceedings of the Twenty-Eighth International Joint
Conference on Artificial Intelligence, IJCAI-19_ , 4718–4724.
https://doi.org/10.24963/ijcai.2019/655

Mitsufuji, Y., Fabbro, G., Uhlich, S., & Stöter, F.-R. (2021). Music demixing
challenge at ISMIR 2021. _arXiv Preprint arXiv:2108.13559_.

Rafii, Z., Liutkus, A., Stöter, F.-R., Mimilakis, S. I., & Bittner, R.
(2017a). _The MUSDB18 corpus for music separation_.
https://doi.org/10.5281/zenodo.1117372

Rafii, Z., Liutkus, A., Stöter, F.-R., Mimilakis, S. I., & Bittner, R. (2019).
_MUSDB18-HQ - an uncompressed version of MUSDB18_.
https://doi.org/10.5281/zenodo.3338373

Rafii, Z., Liutkus, A., Stöter, F.-R., Mimilakis, S. I., & Bittner, R.
(2017b). _MUSDB18-a corpus for music separation_.

Ronneberger, O., Fischer, P., & Brox, T. (2015). U-net: Convolutional networks
for biomedical image segmentation. _International Conference on Medical Image
Computing and Computer-Assisted Intervention_.

Sawata, R., Uhlich, S., Takahashi, S., & Mitsufuji, Y. (2021). All for one and
one for all: Improving music separation by bridging networks. _Proc. IEEE
International Conference on Acoustics, Speech and Signal Processing (ICASSP)_
, 51–55. https://doi.org/10.1109/ICASSP39728.2021.9414044

Takahashi, N., Goswami, N., & Mitsufuji, Y. (2018). Mmdenselstm: An efficient
combination of convolutional and recurrent neural networks for audio source
separation. _16th International Workshop on Acoustic Signal Enhancement,
IWAENC 2018, Tokyo, Japan, September 17-20, 2018_ , 106–110.
https://doi.org/10.1109/IWAENC.2018.8521383

Takahashi, N., & Mitsufuji, Y. (2021). Densely connected multi-dilated
convolutional networks for dense prediction tasks. _Proc. IEEE/CVF Conference
on Computer Vision and Pattern Recognition (CVPR)_ , 993–1002.

Takahashi, N., & Mitsufuji, Y. (2017). Multi-scale multi-band densenets for
audio source separation. _Workshop on Applications of Signal Processing to
Audio and Acoustics (WASPAA)_.

Uhlich, S., Porcu, M., Giron, F., Enenkl, M., Kemp, T., Takahashi, N., &
Mitsufuji, Y. (2017). Improving music source separation based on deep neural
networks through data augmentation and network blending. _Proc. IEEE
International Conference on Acoustics, Speech and Signal Processing (ICASSP)_
, 261–265. https://doi.org/10.1109/ICASSP.2017.7952158

Yin, D., Luo, C., Xiong, Z., & Zeng, W. (2020). PHASEN: A phase-and-harmonics-
aware speech enhancement network. _Proceedings of the AAAI Conference on
Artificial Intelligence_ , _34_ , 9458–9465.


& = 1 - \frac{1}{\numberOfCliques} \prod_{0 \le k \le \numberOfCliques - 2} \max \left\{ \frac{1}{12 \maxPartition^2}, 1 - \frac{(2+C)C}{\numberOfCliques - k - 1} \right\} .
\end{align*}

Let $k_0 = m - 2 (2+C)C - 1$ and observe that for $k \le k_0$ it holds that

\[
1 - \frac{(2+C)C}{\numberOfCliques - k - 1} \ge \frac{1}{2} > \frac{1}{12} \ge \frac{1}{12 \maxPartition^2} .
\]

Thus, we have

\begin{align*}
\frac{1}{\numberOfCliques} \prod_{0 \le k \le \numberOfCliques - 2} \max \left\{ \frac{1}{12 \maxPartition^2}, 1 - \frac{(2+C)C}{\numberOfCliques - k - 1} \right\}
& \ge \frac{1}{\numberOfCliques} \left( \prod_{0 \le k \le k_0} \left( 1 - \frac{(2+C)C}{\numberOfCliques - k - 1} \right) \right) \left( \prod_{k_0 < k \le \numberOfCliques - 2} \frac{1}{12 \maxPartition^2} \right) \\
& = \frac{1}{\numberOfCliques} \left( \frac{1}{12 \maxPartition^2} \right)^{m - 2 - k_0} \prod_{0 \le k \le k_0} \left( 1 - \frac{(2+C)C}{\numberOfCliques - k - 1} \right) \\
& = \frac{1}{\numberOfCliques} \left( \frac{1}{\sqrt{12} \maxPartition} \right)^{4 (2+C)C - 2} \prod_{0 \le k \le k_0} \left( 1 - \frac{(2+C)C}{\numberOfCliques - k - 1} \right) .
\end{align*}

Further, because $\ln(1 - x) \ge \frac{- x}{1 - x}$ for $x < 1$, we have

\begin{align*}
\ln \left(\prod_{0 \le k \le k_0} \left( 1 - \frac{(2+C)C}{\numberOfCliques - k - 1} \right) \right)
& = \sum_{0 \le k \le k_0} \ln \left( 1 - \frac{(2+C)C}{\numberOfCliques - k - 1} \right) \\
& \ge \sum_{0 \le k \le k_0} \frac{- (2+C)C / (\numberOfCliques - k - 1)}{1 - (2+C)C / (m - k - 1)} \\
& = - (2+C)C \sum_{0 \le k \le k_0} \frac{1}{\numberOfCliques - (2+C)C - k - 1} \\
& =  - (2+C)C \sum_{(2+C)C \le j \le \numberOfCliques - (2+C)C - 1} \frac{1}{j} \\
& \ge - (2+C)C \ln (\numberOfCliques) .
\end{align*}

We obtain

\begin{gather} \label{eq:main:twoStep}
\eigenvalueOf{\transitionMatrix[\twoStep]}[2]
\le 1 - \frac{1}{\numberOfCliques} \left( \frac{1}{\sqrt{12} \maxPartition} \right)^{4(2+C)C - 2} \eulerE^{- (2+C)C \ln(\numberOfCliques)}
= 1 - \left(\frac{1}{\numberOfCliques}\right)^{(2+C)C + 1} \left( \frac{1}{\sqrt{12} \maxPartition} \right)^{4(2+C)C - 2}.
\end{gather}

By combining <ref>, we get

\[
1 - \eigenvalueOf{\transitionMatrix[\blockDynamics]}[2] \ge \frac{1}{\bigO{\maxPartition^{4(2+C)C - 1} \numberOfCliques^{(2+C)C + 1}}}.
\]

As $C$ is assumed to be a constant, this implies the desired mixing time.

§ UNIVARIATE MODEL: MIXING UP TO UNIQUENESS

We consider the univariate hard-core model, often just referred to as hard-core model, in which all vertices $v \in \vertices$ have the same weight $\weight[v] = \weight$ for some $\weight \in \R_{>0}$.
We denote an instance of this model by $(\graph, \weight)$.

We define $\criticalWeight{\degree} = \frac{(\degree - 1)^{\degree - 1}}{(\degree - 2)^{\degree}}$ to be the critical weight of the hard-core model.
As we discussed in the introduction, $\criticalWeight{\degree}$ is the threshold for correlation decay on general graphs and a tight upper bound for rapid mixing of Glauber dynamics.

We show that the univariate model $(\graph, \weight)$ satisfies <Ref> for all $\weight \le \criticalWeight{\degree}$.
To do so, we use the following recently established result.

Let $(\graph, \weight)$ be an instance of the univariate hard-core model and assume that the maximum degree of $\graph$ is bounded by $\degree$.
If there is a constant $\delta > 0$ such that $\weight \le (1 - \delta) \criticalWeight{\degree}$, then there is a constant $C \in \bigO{\frac{1}{\delta}}$ such that for all $S \subseteq \vertices$ it holds that $\norm{\pairwiseInfluence{\subgraph{\graph}{S}}}[\infty] \le C$.

This implies the following result immediately.

Let $(\graph, \weight)$ be an instance of the univariate hard-core model and assume that the maximum degree of $\graph$ is bounded by $\degree$.
If there is a constant $\delta > 0$ such that $\weight \le (1 - \delta) \criticalWeight{\degree}$, then $(\graph, \weight)$ satisfies <Ref> for a constant $C \in \bigO{\frac{1}{\delta}}$.

By <Ref>, there is a $C \in \bigO{\frac{1}{\delta}}$ such that, for all $S \in \vertices$ and $r \in S$, it holds that

\[
\sum_{v \in S} \absolute{\pairwiseInfluence{\subgraph{\graph}{S}}[][r, v]} \le \norm{\pairwiseInfluence{\subgraph{\graph}{S}}}[\infty] \le C .
\]

Thus, <Ref> is satisfied for the same constant $C$ and $q(v) = 1$ for all $v \in \vertices$.

The following claim is a direct consequence of <Ref> and <Ref>.

Let $(\graph, \weight)$ be an instance of the univariate hard-core model and assume that the maximum degree of $\graph$ is bounded by $\degree$.
Let $\clique$ be a clique cover for $\graph$ of size $\numberOfCliques$, and let $\maxPartition = \max_{i \in [\numberOfCliques]} \{\partitionFunction[\subgraph{\graph}{\clique[i]}]\}$.
If there is a constant $\delta > 0$ such that $\weight \le (1-\delta) \criticalWeight{\degree}$, then the mixing time of the block dynamics $\blockDynamics[\graph, \weight, \clique]$, starting from $\emptyset \in \independentSets[\graph]$, is bounded by

\[
\mix{\blockDynamics}{\err}[\emptyset] \le \numberOfCliques^{\bigO{1/\delta^2}} \maxPartition^{\bigO{1/\delta^2}} \ln\left( \frac{1}{\err} \right) .
\qedhere
\]

§ MULTIVARIATE MODEL: COMPARISON TO

In this section, we relate <Ref> to a strict version of the , first introduced in <cit.>.

An instance of the multivariate hard-core model $(\graph, \weights)$ satisfies the for a function $\spmcFunction\colon \vertices \to \R_{>0}$ and a constant $\spmcConstant \in (0, 1)$ if and only if for all $v \in \vertices$ it holds that

\[
\sum_{w \in \neighbors{v}} \frac{\weight[w]}{1 + \weight[w]} \spmcFunction[w] \le (1 - \spmcConstant) \spmcFunction[v] .
\qedhere
\]

We show that the is sufficient to imply <Ref>.
This yields a mixing-time bound for block dynamics based on the and also bounds the eigenvalues of the pairwise influence matrix, which might be of independent interest.
To obtain our result, we translate the original instance $(\graph, \weights)$ to the self-avoiding-walk tree and apply a recursive proof on this tree.

§.§.§ Influence in self-avoiding-walk trees

For any instance of the multivariate hard-core model $(\graph , \weights)$ and any vertex $\sawRoot \in \vertices$, let $\sawTree[\graph, \sawRoot]$ denote the tree of self-avoiding walks as defined in <cit.>, which is constructed as follows.
Assume there is a total order of vertices in $v_1, \dots, v_{\numberOfVertices}$, where $\numberOfVertices = \size{\vertices}$.
A self-avoiding walk of length $l \ge 2$ is a simple path $v_{i_1}, v_{i_2}, \dots, v_{i_l}$ in $\graph$.
Further, a closed self-avoiding walk $v_{i_1}, \dots, v_{i_{l-1}}, v_{i_j}$ of length $l \ge 3$ consists of a self-avoiding walk $v_{i_1}, \dots, v_{i_{l-1}}$ of length $l-1$ and an appended vertex $v_{i_j}$ such that $j \in [l-2]$ and $(v_{i_{l-1}}, v_{i_j}) \in \edges$.
That is, the edge $(v_{i_{l-1}}, v_{i_j})$ closes a cycle $v_{i_j}, v_{i_{j+1}}, \dots, v_{i_{l-1}}$.
The graph $\sawTree[\graph, \sawRoot]$ consists of all closed self-avoiding walks with $v_{i_1} = \sawRoot$, and all self-avoiding walks with $v_{i_1} = \sawRoot$ and $v_{i_l}$ having degree $1$ in $\graph$.
Note that any vertex $v \in \vertices$ with $v \neq \sawRoot$ might have multiple copies in $\sawTree[\graph, \sawRoot]$.

For any root $\sawRoot \in \vertices$, the multivariate hard-core model $(\graph, \weights)$ is translated to a multivariate hard-core model on $\sawTree[\graph, \sawRoot]$ as follows.
Let $v_{i_1}, \dots, v_{i_l - 1}, v_{i_j}$ be a closed self-avoiding walk.
We fix $v_{i_j}$ always to be in the independent set (fix spin to $1$) if $i_{j+1} > i_{l-1}$, and we fix it always to be excluded from the independent (fix spin to $0$) otherwise.
We call such vertices fixed copies.
For each $v \in \vertices$, let $\sawCopies{v}[\sawTree[\graph, \sawRoot]]$ denote the set of all unfixed copies of $v$ in $\sawTree[\graph, \sawRoot]$.
We write $\sawCopies{v}$ if the tree $\sawTree[\graph, \sawRoot]$ is clear from the context.
In the multivariate hard-core model on $\sawTree[\graph, \sawRoot]$, each such copy $\sawCopy{v} \in \sawCopies{v}[\sawTree[\graph, \sawRoot]]$ has weight $\weight[\sawCopy{v}] = \weight[v]$.

This way of translating $(\graph, \weights)$ to the tree of self-avoiding walks for some root $\sawRoot \in \vertices$ was shown to have a variety of useful properties.
One of them is that pairwise influences are preserved in the following sense.

Let $(\graph, \weights)$ be an instance of the multivariate hard-core model.
For all $\sawRoot, v \in \vertices$ and $T = \sawTree[\graph, \sawRoot]$ it holds that

\[
\pairwiseInfluence{\graph}[][\sawRoot, v] = \sum_{\sawCopy{v} \in \sawCopies{v}[T]} \pairwiseInfluence{T}[][\sawRoot, \sawCopy{v}] .
\qedhere
\]

<Ref> states that it suffices to discuss the pairwise influence on the self-avoiding walk tree instead of the original graph.
This allows us to use the following multiplicative property for pairwise influence along paths in tree graphs.

Let $T=(\vertices, \edges)$ be a tree and $(T, \weights)$ be a multivariate hard-core model on $T$.
Further, let $v, w \in \vertices$ be a pair of distinct, non-adjacent vertices, and let $u \in \vertices$ with $u \neq v$ and $u \neq w$ be any vertex on the unique path between $v$ and $w$.

\[
\pairwiseInfluence{T}[][v, w] = \pairwiseInfluence{T}[][v, u] \pairwiseInfluence{T}[][u, w] .
\qedhere
\]

§.§.§ Bounding pairwise influence via the

We start by proving that the influence of the root on a certain layer in the self-avoiding-walk tree exhibits the following exponential decay in terms of depth. For a tree $T$ and integer $k$ let $\sawLayer{T}{k} \subseteq \sawCopy{V}$ denote the set of vertices in $T$ at layer $k \in \N$.

Let $(\graph, \weights)$ be a multivariate hard-core model, and let $\sawRoot \in \vertices$.
Furthermore, let $T = \sawTree[\sawRoot, \graph]$ and let $\sawCopy{V} = \bigcup_{v \in \vertices} \sawCopies{v}[T]$.
Assume that $(\graph, \weights)$ satisfies the for a function $\spmcFunction$ and a constant $\spmcConstant$, and define the function $\sawFunction\colon \sawCopy{V} \to \R_{>0}$ with $\sawFunction[\sawCopy{v}] = \spmcFunction[v]$ for all $\sawCopy{v} \in \sawCopies{v}[T]$ and $v \in \vertices$.
Then for all $k \in \N_{>0}$ it holds that

\[
\sum_{w \in \sawLayer{T}{k}} \absolute{\pairwiseInfluence{T}[][r, w]} \sawFunction[w] \le (1 - \spmcConstant)^k \spmcFunction[r] .
\qedhere
\]

Note that if $(\graph, \weights)$ satisfies the for a function $\spmcFunction$ and a constant $\spmcConstant$, then the corresponding multivariate hard-core instance on $T$ satisfies the for $\sawFunction$ and the same constant $\spmcConstant$.
Based on that, we prove our claim by induction on $k$.

Base case: $k = 1$.
Note that $\sawLayer{T}{1} = \neighbors{r}[T]$.
Further, we have for each $w \in \neighbors{r}[T]$ by definition

\[
\absolute{\pairwiseInfluence{T}[][r, w]} = \absolute{\gibbsPr{T}{\inSet{w}}[\inSet{r}] - \gibbsPr{T}{\inSet{w}}[\notInSet{r}]} \le \frac{\weight[w]}{1 + \weight[w]} .
\]

Thus, by the , we obtain

\[
\sum_{w \in \sawLayer{T}{1}} \absolute{\pairwiseInfluence{T}[][r, w]} \sawFunction[w]
\le \sum_{w \in \sawLayer{T}{1}} \frac{\weight[w]}{1 + \weight[w]} \sawFunction[w]
\le (1 - \spmcConstant) \sawFunction[r]
= (1 - \spmcConstant) \spmcFunction[r],
\]

which proves the case $k = 1$.

Induction step: $k > 1$.
Assume that the statement holds for $k - 1$.
For every $u \in \sawLayer{T}{k - 1}$, let $T_u$ denote the subtree rooted at $u$, and let $\sawLayer{T_u}{l}$ denote the vertices at layer $l \in \N$ in $T_u$.
Note that the sets $\sawLayer{T_u}{1}$ for $u \in \sawLayer{T}{k - 1}$ are a partition of $\sawLayer{T}{k}$.
By <Ref>, we get

\begin{align*}
\sum_{w \in \sawLayer{T}{k}} \absolute{\pairwiseInfluence{T}[][r, w]} \sawFunction[w]
&= \sum_{u \in \sawLayer{T}{k-1}} \sum_{w \in \sawLayer{T_u}{1}} \absolute{\pairwiseInfluence{T}[][r, w]} \sawFunction[w] \\
&= \sum_{u \in \sawLayer{T}{k-1}} \absolute{\pairwiseInfluence{T}[][r, u]} \sum_{w \in \sawLayer{T_u}{1}} \absolute{\pairwiseInfluence{T}[][u, w]} \sawFunction[w] .
\end{align*}

Further, for every $u \in \sawLayer{T}{k - 1}$ it holds that $\sawLayer{T_u}{1} \subset \neighbors{u}[T]$, and for all $w \in \sawLayer{T_u}{1}$ we have

\[
\absolute{\pairwiseInfluence{T}[][u, w]} = \absolute{\gibbsPr{T}{\inSet{w}}[\inSet{u}] - \gibbsPr{T}{\inSet{w}}[\notInSet{u}]} \le \frac{\weight[w]}{1 + \weight[w]} .
\]

Thus, by the , we get

\begin{align*}
\sum_{u \in \sawLayer{T}{k-1}} \absolute{\pairwiseInfluence{T}[][r, u]} \sum_{w \in \sawLayer{T_u}{1}} \absolute{\pairwiseInfluence{T}[][u, w]} \sawFunction[w]
&< \sum_{u \in \sawLayer{T}{k-1}} \absolute{\pairwiseInfluence{T}[][r, u]} \sum_{w \in \neighbors{u}[T]} \frac{\weight[w]}{1 + \weight[w]} \sawFunction[w] \\
&\le (1 - \spmcConstant) \sum_{u \in \sawLayer{T}{k-1}} \absolute{\pairwiseInfluence{T}[][r, u]} \sawFunction[u] .
\end{align*}

By the induction hypothesis, we obtain

\[
(1 - \spmcConstant) \sum_{u \in \sawLayer{T}{k-1}} \absolute{\pairwiseInfluence{T}[][r, u]} \sawFunction[u]
\le (1 - \spmcConstant) (1 - \spmcConstant)^{k-1} \spmcFunction[r]
= (1 - \spmcConstant)^{k} \spmcFunction[r] ,
\]

which concludes the proof.

Now, we use this layer-wise decay in the self-avoiding-walk tree to prove that <Ref> is satisfied.

Note that if $(\graph, \weights)$ satisfies the , the same holds for the instance $(\subgraph{\graph}{S}, \subgraph{\weights}{S})$ for the same function $\spmcFunction$ and constant $\spmcConstant$.

Assume $\subgraph{\graph}{S}$ is connected and let $\graph' = \subgraph{\graph}{S}$.
Further, let $T = \sawTree[\sawRoot, \graph']$ and $\sawCopy{S} = \bigcup_{v \in S} \sawCopies{v}[T]$, and define the function $\sawFunction\colon \sawCopy{S} \to \R_{> 0}$ as in <Ref>.
Recall that, by definition, $\pairwiseInfluence{\graph'}[][\sawRoot, \sawRoot] = 0$.
By <Ref>, we get

\begin{align*}
\sum_{v \in S} \absolute{\pairwiseInfluence{\graph'}[][\sawRoot, v]} \spmcFunction[v]
&= \sum_{v \in S \setminus \{\sawRoot\}} \absolute{\pairwiseInfluence{\graph'}[][\sawRoot, v]} \spmcFunction[v] \\
&= \sum_{v \in S \setminus \{\sawRoot\}} \absolute{\sum_{\sawCopy{v} \in \sawCopies{v}[T]} \pairwiseInfluence{T}[][\sawRoot, \sawCopy{v}]} \spmcFunction[v] \\
&\le \sum_{v \in S \setminus \{\sawRoot\}} \sum_{\sawCopy{v} \in \sawCopies{v}[T]} \absolute{\pairwiseInfluence{T}[][\sawRoot, \sawCopy{v}]} \sawFunction[\sawCopy{v}].
\end{align*}

Note that the sets $\sawCopies{v}[T]$ for $v \in S \setminus \{\sawRoot\}$ are a partition of $\sawCopy{S} \setminus \{\sawRoot\}$.
Recall that $\sawLayer{T}{k} \subset \sawCopy{S}$ denotes the vertices in $T$ at layer $k \in \N$, and observe that the sets $\sawLayer{T}{k}$ for $k \in \N_{>0}$ are a partition of $\sawCopy{S} \setminus \{\sawRoot\}$ as well.
Thus, we have

\[
\sum_{v \in S \setminus \{\sawRoot\}} \sum_{\sawCopy{v} \in \sawCopies{v}[T]} \absolute{\pairwiseInfluence{T}[][\sawRoot, \sawCopy{v}]} \sawFunction[\sawCopy{v}]
\le \sum_{k \in \N_{>0}} \sum_{w \in \sawLayer{T}{k}} \absolute{\pairwiseInfluence{T}[][\sawRoot, w]} \sawFunction[w] .
\]

By <Ref>, we obtain the desired bound:

\[
\sum_{k \in \N_{>0}} \sum_{w \in \sawLayer{T}{k}} \absolute{\pairwiseInfluence{T}[][\sawRoot, w]} \sawFunction[w]
\le \spmcFunction[\sawRoot] \sum_{k \in \N_{>0}} (1 - \spmcConstant)^k
= \frac{1}{\spmcConstant} \spmcFunction[\sawRoot] .
\]

Now, assume $\subgraph{\graph}{S}$ is not connected.
Set $\graph'$ to be the largest connected component in $\subgraph{\graph}{S}$ that contains $\sawRoot$ and let $S' \subset S$ be the set of vertices in $\graph'$.
The claim follows from applying the proof above to $\graph'$ with vertex set $S'$ and by observing that $\pairwiseInfluence{\subgraph{\graph}{S}}[][\sawRoot, v] = 0$ for all $v \in S \setminus S'$.

<Ref> immediately implies with <Ref> the following result for the mixing time of block dynamics under .

Let $(\graph, \weights)$ be an instance of the multivariate hard-core model.
Let $\clique$ be a given clique cover for $\graph$ of size $\numberOfCliques$, and let $\maxPartition = \max_{i \in [\numberOfCliques]} \{\partitionFunction[\subgraph{\graph}{\clique[i]}]\}$.
If $(\graph, \weight)$ satisfies the for a function $\spmcFunction$ and a constant $\spmcConstant$, then the mixing time of the block dynamics $\blockDynamics = \blockDynamics[\graph, \weight, \clique]$, starting from $\emptyset \in \independentSets[\graph]$, is bounded by

\[
\mix{\blockDynamics}{\err}[\emptyset] \le \numberOfCliques^{\bigO{1/\alpha^2}} \maxPartition^{\bigO{1/\alpha^2}} \ln\left( \frac{1}{\err} \right) .
\qedhere
\]

Finally, <Ref> together with <Ref> imply the following result.

Let $(\graph, \weights)$ be an instance of the multivariate hard-core model that satisfies the for a function $\spmcFunction$ and a constant $\spmcConstant$.
For every $S \subseteq \vertices$ it holds that $\eigenvalueOf{\pairwiseInfluence{\subgraph{\graph}{S}}}[1] \le \frac{1}{\spmcConstant}$.

§ COMPARING CLIQUE DYNAMICS TO BLOCK DYNAMICS

Using <Ref>, we show that a bound on the mixing time of the clique dynamics for any clique cover is obtained based on a bound for the mixing time of the block dynamics for the same clique cover.

Let $(\graph, \weights)$ be an instance of the multivariate hard-core model, let $\clique$ be a clique cover of $\graph$ with size $\numberOfCliques$, and let $\maxPartition = \max_{i \in [\numberOfCliques]} \{\partitionFunction[\clique[i]]\}$.
Let $\blockDynamics = \blockDynamics[\graph, \weights, \clique]$ denote the block dynamics and $\cliqueDynamics = \cliqueDynamics[\graph, \weights, \clique]$ the clique dynamics based on $\clique$.

\[
\eigenvalueOf{\transitionMatrix[\cliqueDynamics]}[2] \le 1 - \frac{1}{2 \maxPartition} \big(1 - \eigenvalueOf{\transitionMatrix[\blockDynamics]}[2]\big).
\qedhere
\]

We aim to apply <Ref>.
Note that, by $\stationary[\cliqueDynamics] = \gibbsDistribution = \stationary[\blockDynamics]$, we can choose $\statRatio = 1$.
We proceed by constructing a set of paths $\canonicalPaths$ and by upper-bounding $\flowRatio{\canonicalPaths}$.
For every $(\independentSet_s, \independentSet_t) \in \mcEdges{\blockDynamics}$, we choose the path $\canonicalPath[\independentSet_s \independentSet_t]$ via edges in $\mcAllEdges{\cliqueDynamics}$ as follows:

* $\canonicalPath[\independentSet_s \independentSet_t] = (\independentSet_s, \independentSet_t)$ if $\independentSet_s \symDiff \independentSet_t = \{v\}$ for some $v \in \vertices$, and

* $\canonicalPath[\independentSet_s \independentSet_t] = (\independentSet_s, \independentSet_s \cap \independentSet_t, \independentSet_t)$ if $\independentSet_s \symDiff \independentSet_t = \{v, w\}$ for $v \neq w$.

We set $\canonicalPaths$ to be the set of all such paths.
Note that we actually only use edges in $\mcEdges{\cliqueDynamics}$, which means that we can ignore self loops while bounding $\flowRatio{\canonicalPaths}$.
We proceed by doing a case distinction on the transition $(\independentSet, \independentSet') \in \mcEdges{\cliqueDynamics}$.

Case 1.
Consider $(\independentSet, \independentSet') \in \mcEdges{\cliqueDynamics}$ with $\independentSet = \independentSet' \cup \{v\}$ for a $v \notin \independentSet$ (i.e., removing $v$).
First, note that

\begin{align}
\notag
\transitionWeight{\cliqueDynamics}[\independentSet, \independentSet']
&= \gibbsDistributionFunction{\independentSet} \frac{1}{\numberOfCliques} \sum_{\substack{i \in [\numberOfCliques]: \\ v \in \clique[i]}} \gibbsDistributionFunction{\emptyset}[][\clique[i]][\zeroSpinConfig[\vertices \setminus \clique[i]]] \\
\notag
&= \gibbsDistributionFunction{\independentSet} \frac{1}{\numberOfCliques} \sum_{\substack{i \in [\numberOfCliques]: \\ v \in \clique[i]}} \frac{1}{\partitionFunction[\subgraph{\graph}{\clique[i]}]} \\
\label{eq:comparison_clique_dynamics:case1:1}
&\ge \gibbsDistributionFunction{\independentSet} \frac{1}{\numberOfCliques} \frac{1}{\maxPartition} \size{\set{i \in [\numberOfCliques]}{ v \in \clique[i]}} .
\end{align}

Further, for all $(\independentSet_s, \independentSet_t) \in \mcEdges{\blockDynamics}$ such that $(\independentSet, \independentSet') \in \mcEdges{\canonicalPath[\independentSet_s \independentSet_t]}$ it holds that $\independentSet_s = \independentSet$, and either $\independentSet_t = \independentSet'$ or $\independentSet_t = \independentSet' \cup \{w\}$ for some $w \in \vertices$ that shares a clique with $v$.
If $\independentSet_t = \independentSet'$, then we have

\begin{align}
\notag
\transitionWeight{\blockDynamics}[\independentSet, \independentSet']
&= \gibbsDistributionFunction{\independentSet} \frac{1}{\numberOfCliques} \sum_{\substack{i \in [\numberOfCliques]: \\ v \in \clique[i]}} \gibbsDistributionFunction{\emptyset}[][\clique[i]][\spinConfig[\vertices \setminus \clique[i]][][\independentSet]] \\
\notag
&= \gibbsDistributionFunction{\independentSet} \frac{1}{\numberOfCliques} \sum_{\substack{i \in [\numberOfCliques]: \\ v \in \clique[i]}} \dfrac{\gibbsDistributionFunction{\independentSet'}}{ \gibbsDistributionFunction{\independentSet'} + \sum\limits_{\substack{u \in \clique[i]:\\ \independentSet' \cup \{u\} \in \independentSets}} \gibbsDistributionFunction{\independentSet' \cup \{u\}}} \\
\label{eq:comparison_clique_dynamics:case1:2}
&= \gibbsDistributionFunction{\independentSet} \frac{1}{\numberOfCliques} \sum_{\substack{i \in [\numberOfCliques]: \\ v \in \clique[i]}} \dfrac{1}{ 1 + \sum\limits_{\substack{u \in \clique[i]:\\ \independentSet' \cup \{u\} \in \independentSets}} \weight[u]} .
\end{align}

Otherwise, if $\independentSet_t = \independentSet' \cup \{w\}$, we get

\begin{align}
\notag
\transitionWeight{\blockDynamics}[\independentSet, \independentSet' \cup \{w\} ]
&= \gibbsDistributionFunction{\independentSet} \frac{1}{\numberOfCliques} \sum_{\substack{i \in [\numberOfCliques]: \\ v, w \in \clique[i]}} \gibbsDistributionFunction{\{w\}}[][\clique[i]][\spinConfig[\vertices \setminus \clique[i]][][\independentSet]] \\
\notag
&= \gibbsDistributionFunction{\independentSet} \frac{1}{\numberOfCliques} \sum_{\substack{i \in [\numberOfCliques]: \\ v, w \in \clique[i]}} \dfrac{\gibbsDistributionFunction{\independentSet' \cup \{w\}}}{ \gibbsDistributionFunction{\independentSet'} + \sum\limits_{\substack{u \in \clique[i]:\\ \independentSet' \cup \{u\} \in \independentSets}} \gibbsDistributionFunction{\independentSet' \cup \{u\}}} \\
\label{eq:comparison_clique_dynamics:case1:3}
&= \gibbsDistributionFunction{\independentSet} \frac{1}{\numberOfCliques} \sum_{\substack{i \in [\numberOfCliques]: \\ v, w \in \clique[i]}} \dfrac{\weight[w]}{ 1 + \sum\limits_{\substack{u \in \clique[i]:\\ \independentSet' \cup \{u\} \in \independentSets}} \weight[u]} .
\end{align}

Combining <ref> and observing that $\length{\canonicalPath[\independentSet_s \independentSet_t]} \le 2$ for all involved paths yields

\begin{align*}
\sum_{\substack{(\independentSet_s, \independentSet_t) \in \mcEdges{\blockDynamics}: \\(\independentSet, \independentSet') \in \canonicalPath[\independentSet_s \independentSet_t]}} \length{\canonicalPath[\independentSet_s \independentSet_t]} \transitionWeight{\blockDynamics}[\independentSet_s, \independentSet_t]
&\le 2 \gibbsDistributionFunction{\independentSet} \frac{1}{\numberOfCliques} \sum_{\substack{i \in [\numberOfCliques]: \\ v \in \clique[i]}}
\left(\dfrac{1}{ 1 + \sum\limits_{\substack{u \in \clique[i]:\\ \independentSet' \cup \{u\} \in \independentSets}} \weight[u]} + \sum_{\substack{w \in \clique[i]:\\ \independentSet' \cup \{w\} \in \independentSets}} \dfrac{\weight[w]}{ 1 + \sum\limits_{\substack{u \in \clique[i]:\\ \independentSet' \cup \{u\} \in \independentSets}} \weight[u]}\right) \\
&= 2 \gibbsDistributionFunction{\independentSet} \frac{1}{\numberOfCliques} \size{\set{i \in [\numberOfCliques]}{ v \in \clique[i]}} .
\end{align*}

Together with <ref>, we get

\[
\frac{1}{\transitionWeight{\cliqueDynamics}[\independentSet, \independentSet']} \sum_{\substack{(\independentSet_s, \independentSet_t) \in \mcEdges{\blockDynamics}: \\(\independentSet, \independentSet') \in \canonicalPath[\independentSet_s \independentSet_t]}} \length{\canonicalPath[\independentSet_s \independentSet_t]} \transitionWeight{\blockDynamics}[\independentSet_s, \independentSet_t]
\le 2 \maxPartition.
\]

Case 2.
Consider $(\independentSet, \independentSet') \in \mcEdges{\cliqueDynamics}$ with $\independentSet' = \independentSet \cup \{v\}$ for some $v \notin \independentSet$ (i.e., adding $v$).
Note that, as $\cliqueDynamics$ is reversible, it holds that $(\independentSet', \independentSet) \in \mcEdges{\cliqueDynamics}$.
As $(\independentSet', \independentSet)$ is a transition that deletes $v$ from $\independentSet'$, resulting in $\independentSet$, it was already considered in the first case.
Further, by construction of $\canonicalPaths$, it holds that $(\independentSet, \independentSet')$ is on a path $\canonicalPath[\independentSet_s \independentSet_t]$ for any $(\independentSet_s, \independentSet_t) \in \mcEdges{\blockDynamics}$ if and only if $(\independentSet', \independentSet)$ is on the path $\canonicalPath[\independentSet_t \independentSet_s]$ for $(\independentSet_t, \independentSet_s) \in \mcEdges{\blockDynamics}$.
Due to reversibility of $\cliqueDynamics$ and $\blockDynamics$, we know that $\transitionWeight{\cliqueDynamics}$ and $\transitionWeight{\blockDynamics}$ are symmetric.
Thus, we can conclude from our result for $(\independentSet', \independentSet)$ in the first case that

\[
\frac{1}{\transitionWeight{\cliqueDynamics}[\independentSet, \independentSet']} \sum_{\substack{(\independentSet_s, \independentSet_t) \in \mcEdges{\blockDynamics}: \\(\independentSet, \independentSet') \in \canonicalPath[\independentSet_s \independentSet_t]}} \length{\canonicalPath[\independentSet_s \independentSet_t]} \transitionWeight{\blockDynamics}[\independentSet_s, \independentSet_t]
= \frac{1}{\transitionWeight{\cliqueDynamics}[\independentSet', \independentSet]} \sum_{\substack{(\independentSet_t, \independentSet_s) \in \mcEdges{\blockDynamics}: \\(\independentSet', \independentSet) \in \canonicalPath[\independentSet_t \independentSet_s]}} \length{\canonicalPath[\independentSet_t \independentSet_s]} \transitionWeight{\blockDynamics}[\independentSet_t, \independentSet_s]
\le 2 \maxPartition .
\]

As $\cliqueDynamics$ changes at most one vertex at each step, the above case distinction is complete and we get $\flowRatio{\canonicalPaths} \le 2 \maxPartition$, which by <Ref> concludes the proof.

We immediately obtain the following corollary, which is central for our proof of <Ref>.

Let $\blockDynamics = \blockDynamics[\graph, \weight, \clique]$.
Due to <Ref> we know that $\mix{\cliqueDynamics}{\err}[\emptyset] \le 2 \maxPartition \mix{\blockDynamics}{\err}[\emptyset]$.
Bounding $\mix{\blockDynamics}{\err}[\emptyset]$ based on <Ref> proves the claim.

§ THE MONOATOMIC HARD-SPHERE MODEL

We study the grand canonical ensemble of the monoatomic hard-sphere model in a $d$-dimensional finite cubic region $\volume = [0, \sidelength)^d$ of Euclidean space with side length $\sidelength \in \R_{\geq 1}$.
We write $\vol{\volume} = \sidelength^d$ for the volume of $\volume$.
The hard-sphere model describes the distribution of identical particles, represented as $d$-dimensional balls in $\volume$.
This distribution is governed by a fugacity parameter $\hsFugacity \in \R_{>0}$, describing the contribution of each particle to the chemical potential, and hard-core interactions between particles, meaning that no two particles are allowed to overlap.
For simplicity, it is common to assume particles to have volume $1$, meaning that their radius is $\radius = (1/\normSphere{d})^{1/d}$, where $\normSphere{d}$ denotes the volume of a unit sphere in $d$ dimensions.

A probabilistic interpretation of grand canonical ensemble is that the centers of particles are distributed according to a Poisson point process on $\volume$ with activity $\hsFugacity$, conditioned on the fact that particles are non-overlapping (i.e., each pair of distinct centers have distance at least $2r$).
Note that this implies that particles are indistinguishable, meaning that exchanging the positions of two particles results in exactly the same configuration of the system.
We aim for approximating the grand canonical partition function, which can be seen as the normalizing constant of the resulting distribution of system states.
As a reminder, the partition function can formally be defined as

\[
\hardSpherePrt[\volume, \hsFugacity] =
1 + \sum_{\numParticles \in \N_{> 0}}
\frac{\hsFugacity^\numParticles}{\numParticles !}
\int_{\volume^\numParticles} \valid[x^{(1)}, \dots, x^{(\numParticles)}] \,\d \lebesgue{d \times \numParticles} ,
\]

\[
\valid[x^{(1)}, \dots, x^{(\numParticles)}] = \begin{cases}
1 \emph{ if $\dist{x^{(i)}}{x^{(j)}} \ge 2r$ for all $i, j \in [\numParticles]$ with $i \neq j$} \\
0 \emph{ otherwise}
\end{cases}
\]

and $\lebesgue{d \times \numParticles}$ is the Lebesgue measure on $\R^{d \times \numParticles}$.

§.§ Hard-core representation

To apply our result for clique dynamics to the continuous hard-sphere model, we will approximate it by an instance of the hard-core model.
The main idea of this discretization is to restrict the centers of spheres to vertices in an integer grid, while scaling the fugacity $\hsFugacity$ and the radius $\radius$ appropriately.
The resulting discrete hard-sphere model can easily be transformed into a hard-core instance.
We proceed by formalizing the direct transformation from the continuous hard-sphere model instance to the discrete hard-core model.

Let $(\volume, \hsFugacity)$ be an instance of the continuous hard-sphere model with $\volume = [0, \sidelength)^d$.
Recall that we fixed the radius $\radius = (1/\normSphere{d})^{1/d}$.
Let $\grid[n] = \Z^d \cap [0, n)^d$ be a finite integer grid of side length $n \in \N_{>0}$.
For any $\resolution \in \R_{>0}$ such that $\resolution \sidelength  \in \N_{>0}$, the hard-core representation of $(\volume, \hsFugacity)$ with resolution $\resolution$ is a hard-core model $(\hsGraph{\resolution}, \hsWeight{\resolution})$ with $\hsGraph{\resolution} = (\hsVertices{\resolution}, \hsEdges{\resolution})$ and

* there is a vertex $\hsVertex{x} \in \hsVertices{\resolution}$ for each grid point $x \in \grid[\resolution \sidelength]$,

* there is an edge $(\hsVertex{x}, \hsVertex{y}) \in \hsEdges{\resolution}$ for any pair of grid points $x, y \in \grid[\resolution \sidelength]$ with $x \neq y$ and $\dist{x}{y} \le 2  \resolution \radius$, and

* $\hsWeight{\resolution} = \resolution^{-d} \hsFugacity$.

Note that in the above definition $\dist{x}{y}$ denotes the Euclidean distance.

We will use the following convergence result for the partition function of the hard-core representation in terms of the resolution $\resolution$ to approximate the hard-sphere partition function.

Note that it suffices to bound the additive error $\absolute{\hardSpherePrt[\volume, \hsFugacity] - \partitionFunction[\hsGraph{\resolution}, \hsWeight{\resolution}]}$.
Because $\hardSpherePrt[\volume, \hsFugacity] \ge 1$, this directly results in the desired multiplicative bound.

In order to obtain an additive bound, we start by transforming $\partitionFunction[\hsGraph{\resolution}, \hsWeight{\resolution}]$ to a form that is more similar to the form of $\hardSpherePrt[\volume, \hsFugacity]$.

Let $\volume = [0, \sidelength)^{d}$ and let $\rescale[\resolution]\colon \grid[\resolution \sidelength] \to \volume$ with $(x_1, \dots, x_d) \mapsto \rescale[\resolution][x] = \left( x_1/\resolution, \dots, x_d/\resolution \right)$.
Note that, for all $x^{(i)}, x^{(j)} \in \grid[\resolution \sidelength]$ it holds that

\[
\dist{x^{(i)}}{x^{(j)}} \ge 2 \resolution \radius
\dist{\rescale[\resolution][x^{(i)}]}{\rescale[\resolution][x^{(j)}]} \ge 2 \radius .
\]

Thus, we see that

\begin{align}
\notag
\partitionFunction[\hsGraph{\resolution}, \hsWeight{\resolution}]
&= \sum_{\independentSet \in \independentSets[\hsGraph{\resolution}]} \hsWeight{\resolution}^{\size{\independentSet}} \\
\notag
&= 1 + \sum_{\numParticles \in \N_{>0}} \sum_{\substack{\independentSet \in \independentSets[\hsGraph{\resolution}]\\ \size{\independentSet} = \numParticles}} \hsWeight{\resolution}^\numParticles \\
\notag
&= 1 + \sum_{\numParticles \in \N_{> 0}} \frac{\hsWeight{\resolution}^\numParticles}{\numParticles!} \sum_{\substack{\left( x^{(1)}, \dots, x^{(\numParticles)} \right) \\\in \left( \grid[\resolution \sidelength] \right)^\numParticles}}  \valid[\rescale[\resolution][x^{(1)}], \dots, \rescale[\resolution][x^{(\numParticles)}]] \\
\label{eq:discreteHardSpherePartitationFunction}
&= 1 + \sum_{\numParticles \in \N_{> 0}} \frac{\hsFugacity^\numParticles}{\numParticles!}
\sum_{\substack{\left( x^{(1)}, \dots, x^{(\numParticles)} \right) \\\in \left( \grid[\resolution \sidelength] \right)^\numParticles}}  \left(\frac{1}{\resolution}\right)^{d \cdot \numParticles} \valid[\rescale[\resolution][x^{(1)}], \dots, \rescale[\resolution][x^{(\numParticles)}]] .
\end{align}

We continue by rewriting

\[
\sum_{\substack{\left( x^{(1)}, \dots, x^{(\numParticles)} \right) \\\in \left( \grid[\resolution \sidelength] \right)^\numParticles}}  \left(\frac{1}{\resolution}\right)^{d \cdot \numParticles} \valid[\rescale[\resolution][x^{(1)}], \dots, \rescale[\resolution][x^{(\numParticles)}]]
\]

for any fixed $\numParticles \in \N_{> 0}$.
Let $\rescale[\resolution][\grid[\resolution \sidelength]] \subseteq \volume$ denote the image of $\rescale[\resolution]$, and let $\remap[\resolution]\colon \volume \to \rescale[\resolution][\grid[\resolution \sidelength]]$ with

\[
(x_1, \dots, x_d) \mapsto \left( \frac{\lfloor \resolution x_1 \rfloor }{\resolution}, \dots, \frac{\lfloor \resolution x_d \rfloor }{\resolution} \right).
\]

Further, for all $\numParticles \in \N_{> 0}$ and all $\left( x^{(1)}, \dots, x^{(\numParticles)} \right) \in \left( \rescale[\resolution][\grid[\resolution \sidelength]] \right)^\numParticles$, let

\begin{align*}
W^{(\resolution)}_{x^{(1)}, \dots, x^{(\numParticles)}}
& = \set{ \left( y^{(1)}, \dots, y^{(\numParticles)} \right) \in \volume^\numParticles}{ \forall i \in [\numParticles]\colon \remap[\resolution][y^{(i)}] = x^{(i)} } \\
& = \left( \invremap{\resolution}{x^{(1)}} \right) \times \dots \times \left( \invremap{\resolution}{x^{(\numParticles)}} \right) .
\end{align*}

Note that the sets $W^{(\resolution)}_{x^{(1)}, \dots, x^{(\numParticles)}}$ partition $\volume^{\numParticles}$ into $(d \times k)$-dimensional hypercubes of side length $1/\resolution$.
Thus, for all $\left( x^{(1)}, \dots, x^{(\numParticles)} \right) \in \left( \rescale[\resolution][\grid[\resolution \sidelength]] \right)^\numParticles$, it holds that

\[
\lebesgue{d \times \numParticles}[W^{(\resolution)}_{x^{(1)}, \dots, x^{(\numParticles)}}] = \left( \frac{1}{\resolution} \right)^{d \cdot k} .
\]

By this and by the definition of a Lebesgue integral for elementary functions, we obtain

\begin{align*}
\sum_{\substack{\left( x^{(1)}, \dots, x^{(\numParticles)} \right) \\\in \left( \grid[\resolution \sidelength] \right)^\numParticles}}
&	\left( \frac{1}{\resolution} \right)^{d \cdot k}
\valid[\rescale[\resolution][x^{(1)}], \dots, \rescale[\resolution][x^{(\numParticles)}]] \\
& = \sum_{\substack{\left( x^{(1)}, \dots, x^{(\numParticles)} \right) \\\in \left( \grid[\resolution \sidelength] \right)^\numParticles}}
\lebesgue{d \times \numParticles}[W^{(\resolution)}_{\rescale[\resolution][x^{(1)}], \dots, \rescale[\resolution][x^{(\numParticles)}]}] \cdot
\valid[\rescale[\resolution][x^{(1)}], \dots, \rescale[\resolution][x^{(\numParticles)}]] \\
& = \sum_{\substack{\left( x^{(1)}, \dots, x^{(\numParticles)} \right) \\\in \left( \rescale[\resolution][\grid[\resolution \sidelength]] \right)^\numParticles}}
\lebesgue{d \times \numParticles}[W^{(\resolution)}_{x^{(1)}, \dots, x^{(\numParticles)}}] \cdot
\valid[x^{(1)}, \dots, x^{(\numParticles)}] \\
& = \int_{\volume^{\numParticles}} \valid[\remap[\resolution][x^{(1)}], \dots, \remap[\resolution][x^{(\numParticles)}]] \,\d \lebesgue{d \times \numParticles} .
\end{align*}

Substituting this expression back into <ref> yields

\[
\partitionFunction[\hsGraph{\resolution}, \hsWeight{\resolution}]
= 1 + \sum_{\numParticles \in \N_{> 0}} \frac{\hsFugacity^\numParticles}{\numParticles!}
\int_{\volume^\numParticles} \valid[\remap[\resolution][x^{(1)}], \dots, \remap[\resolution][x^{(\numParticles)}]] \,\d \lebesgue{d \times \numParticles} .
\]

We now express $\absolute{\hardSpherePrt[\volume, \hsFugacity] - \partitionFunction[\hsGraph{\resolution}, \hsWeight{\resolution}]}$ in terms of the absolute difference of the integrals for all $\numParticles \in \N_{> 0}$.
It holds that

\begin{gather*}
\absolute{\int_{\volume^\numParticles} \valid[x^{(1)}, \dots, x^{(\numParticles)}] \,\d \lebesgue{d \times \numParticles} - \int_{\volume^\numParticles} \valid[\remap[\resolution][x^{(1)}], \dots, \remap[\resolution][x^{(\numParticles)}]] \,\d \lebesgue{d \times \numParticles}} \\
\le \int_{\volume^\numParticles} \absolute{\valid[x^{(1)}, \dots, x^{(\numParticles)}] - \valid[\remap[\resolution][x^{(1)}], \dots, \remap[\resolution][x^{(\numParticles)}]]} \,\d \lebesgue{d \times \numParticles} .
\end{gather*}

Let $N^{(\resolution)} \subseteq \volume^\numParticles$ be such that for all $\left( x^{(1)}, \dots, x^{(\numParticles)} \right) \in N^{(\resolution)}$ it holds that $\valid[x^{(1)}, \dots, x^{(\numParticles)}] \neq \valid[\remap[\resolution][x^{(1)}], \dots, \remap[\resolution][x^{(\numParticles)}]]$.
As $\valid$ is an indicator function, it holds that

\[
\int_{\volume^\numParticles} \absolute{ \valid[x^{(1)}, \dots, x^{(\numParticles)}] - \valid[\remap[\resolution][x^{(1)}], \dots, \remap[\resolution][x^{(\numParticles)}]] } \,\d \lebesgue{d \times \numParticles}
= \lebesgue{d \times \numParticles}[N^{(\resolution)}] .
\]

We construct a superset of $N^{(\resolution)}$, for which we calculate the Lebesgue measure.
First, note that $N^{(\resolution)} = \emptyset$ for $k=1$, as in this case $\valid[x^{(1)}] = \valid[\remap[\resolution][x^{(1)}]] = 1$ for all $x^{(1)} \in \volume$.
Further, let $K = \big( \sidelength \sqrt{d}/(2 \radius) \big)^d$.
Note that, for all $\numParticles > K$, it holds that at least two particles have distance less than $2 \radius$, meaning that such a configuration has always overlapping particles and $N^{(\resolution)} = \emptyset$.
We are left with considering $2 \le \numParticles \le K$.

We observe that, for all $\left( x^{(1)}, \dots, x^{(\numParticles)} \right) \in \volume^\numParticles$ such that

\[
\valid[x^{(1)}, \dots, x^{(\numParticles)}] \neq \valid[\remap[\resolution][x^{(1)}], \dots, \remap[\resolution][x^{(\numParticles)}]],
\]

there is a pair of points $x^{(i)}, x^{(j)}$ for $i, j \in [\numParticles]$ such that $i \neq j$ and

\begin{align*}
&\dist{x^{(i)}}{x^{(j)}} < 2 \radius \le \dist{\remap[\resolution][x^{(i)}]}{\remap[\resolution][x^{(j)}]} \ \textrm{ or}\\
&\dist{x^{(i)}}{x^{(j)}} \ge 2 \radius > \dist{\remap[\resolution][x^{(i)}]}{\remap[\resolution][x^{(j)}]} .
\end{align*}

As, for every point $x^{(i)} \in \volume$, it holds that

\[
\dist{x^{(i)}}{\remap[\resolution][x^{(i)}]} \le \frac{\sqrt{d}}{\resolution},
\]

there is a pair of points $x^{(i)}, x^{(j)}$ for $i, j \in [\numParticles]$ such that $i \neq j$ and

\[
\absolute{2 \radius - \dist{x^{(i)}}{x^{(j)}}} \le 2 \frac{\sqrt{d}}{\resolution} .
\]

For all $i, j \in [\numParticles]$ with $i \neq j$ let $S^{(\resolution)}_{i, j} \subseteq \volume^{\numParticles}$ be the set of points $\left( x^{(1)}, \dots, x^{(\numParticles)} \right) \in \volume^\numParticles$ such that this is the case.

\[
\lebesgue{d \times \numParticles}[N^{(\resolution)}]
\le \lebesgue{d \times \numParticles}[\bigcup_{1 \le i < j \le \numParticles} S^{(\resolution)}_{i, j}]
\le \sum_{1 \le i < j \le \numParticles} \lebesgue{d \times \numParticles}[S^{(\resolution)}_{i, j}] .
\]

By Fubini's theorem, noting that $S^{(\resolution)}_{i, j}$ only depends on $i$ and $j$, we get

\begin{align*}
\lebesgue{d \times \numParticles}[S^{(\resolution)}_{i, j}]
& = \int_{\volume^\numParticles}  \indicator{\absolute{2 \radius - \dist{x^{(i)}}{x^{(j)}}} \le 2 \frac{\sqrt{d}}{\resolution}} \,\d \lebesgue{d \times \numParticles} \\
& = \sidelength^{d (\numParticles - 2)} \int_{\volume^2}  \indicator{\absolute{2 \radius - \dist{x^{(i)}}{x^{(j)}}} \le 2 \frac{\sqrt{d}}{\resolution}}  \,\d \lebesgue{d \times 2} \\
& \le \sidelength^{d (\numParticles - 1)} \cdot \left( \left( 2 \radius + 2 \frac{\sqrt{d}}{\resolution} \right)^d - \left( 2 \radius - 2 \frac{\sqrt{d}}{\resolution} \right)^d \right)\ ,
\end{align*}

where the last equality comes from the fact that $\radius$ was chosen as the radius of a ball of volume $1$ in $d$ dimensions.
By the assumption $\resolution \ge 2 \sqrt{d}$ and the binomial theorem, we further bound

\begin{align*}
\left( 2 \radius + 2 \frac{\sqrt{d}}{\resolution} \right)^d - \left( 2 \radius - 2 \frac{\sqrt{d}}{\resolution} \right)^d &= \sum_{i = 0}^{d} 2\cdot\indicator{i \text{ is odd}} \binom{d}{i} \big(2 \radius\big)^{d - i} \left(2 \frac{\sqrt{d}}{\resolution}\right)^i\\
&\hspace*{-2 em}= \frac{2\sqrt{d}}{\resolution}\sum_{i = 1}^{d} 2\cdot\indicator{i \text{ is odd}} \binom{d}{i} \big(2 \radius\big)^{d - i} \left(2 \frac{\sqrt{d}}{\resolution}\right)^{i - 1}\\
&\leq \frac{2\sqrt{d}}{\resolution}\sum_{i = 1}^{d} 2\cdot\indicator{i \text{ is odd}} \binom{d}{i} \big(2 \radius\big)^{d - i} 1^{i - 1}\\
&\le 2\frac{2 \sqrt{d}}{\resolution} \big( 2 \radius + 1 \big)^d.
\end{align*}

Using this bound for $\lebesgue{d \times \numParticles}[S^{(\resolution)}_{i, j}]$, we obtain

\begin{align*}
\lebesgue{d \times \numParticles}[N^{(\resolution)}]
\le \numParticles^2 \cdot 2 \cdot \sidelength^{d (\numParticles - 1)} \cdot \frac{2 \sqrt{d}}{\resolution} \cdot \left( 2 \radius + 1 \right)^d .
\end{align*}

Thus, we get

\begin{align*}
\absolute{\hardSpherePrt[\volume, \hsFugacity] - \partitionFunction[\hsGraph{\resolution}, \hsWeight{\resolution}]}
& \le \sum_{\numParticles = 2}^{K} \frac{\hsFugacity^\numParticles}{\numParticles!} \lebesgue{d \times \numParticles}[N^{(\resolution)}] \\
& \le \frac{1}{\resolution}\sum_{\numParticles = 2}^{K} \frac{\hsFugacity^\numParticles}{\numParticles!} \numParticles^2 \cdot 4 \sidelength^{d (\numParticles - 1)} \cdot \sqrt{d} \cdot \left( 2 \radius + 1 \right)^d .
\end{align*}

We simplify the bound further by

\begin{align*}
\frac{1}{\resolution} \sum_{\numParticles = 2}^{K} \frac{\hsFugacity^\numParticles}{\numParticles!} \numParticles^2 \cdot 4 \sidelength^{d (\numParticles - 1)} \cdot \sqrt{d} \cdot \left( 2 \radius + 1 \right)^d
&\le \frac{1}{\resolution} K^2 \cdot 4 \sidelength^{d (K - 1)} \cdot \sqrt{d} \cdot \left( 2 \radius + 1 \right)^d \sum_{\numParticles = 2}^{K} \frac{\hsFugacity^\numParticles}{\numParticles!} \\
&\le \frac{1}{\resolution} K^2 \cdot 4 \sidelength^{d (K - 1)} \cdot \sqrt{d} \cdot \left( 2 \radius + 1 \right)^d \eulerE^{\hsFugacity},
\end{align*}

where the last inequality follows from the Taylor expansion of $\eulerE^x$ at $0$.

Overall, we bound

\begin{align*}
\absolute{\hardSpherePrt[\volume, \hsFugacity] - \partitionFunction[\hsGraph{\resolution}, \hsWeight{\resolution}]}
&\le \frac{1}{\resolution} K^2 \cdot 4 \sidelength^{d (K - 1)} \cdot \sqrt{d} \cdot \left( 2 \radius + 1 \right)^d \eulerE^{\hsFugacity}\\
& \le \frac{1}{\resolution} \eulerE^{\bigTheta{K  d \ln (\sidelength) + \ln \left( \radius + 1 \right) + \eulerE^{\hsFugacity}}} .
\end{align*}

Observe that $\radius \in \bigO{1}$ and $\eulerE^{\hsFugacity} \in \bigO{1}$.
Further, for $\radius = (1/\normSphere{d})^{1/d}$ it holds that $K \in \bigO{\sidelength^d}$.
Thus we have

\[
\absolute{\hardSpherePrt[\volume, \hsFugacity] - \partitionFunction[\hsGraph{\resolution}, \hsWeight{\resolution}]}
\le \frac{1}{\resolution} \eulerE^{\bigTheta{\sidelength^d  \ln (\sidelength^d)}}
= \frac{1}{\resolution} \eulerE^{\bigTheta{ \vol{\volume} \ln (\vol{\volume})}},
\]

which concludes the proof.

§.§ Approximation bound

We aim for applying <Ref> to the hard-core representation of the hard-sphere model.
In order to do so, we need a bound on the maximum degree $\hsDegree{\resolution}$ of the graph $\hsGraph{\resolution}$ for any sufficiently large resolution $\resolution$.
Let $\integerSphere{d}[s]$ denote the number of integer grid points in a $d$-dimensional sphere of radius $s$ centered at the origin.
Note that the number of neighbors of a vertex $\hsVertex{x} \in \hsVertices{\resolution}$ for any grid point $x \in \grid[\resolution \sidelength]$ is upper bounded by $\integerSphere{d}[2 \resolution r]$.
We use the following bound on $\integerSphere{d}$.

Let $\gaussCircleError \in (0, 1]$ and $s \in \R_{> 0}$.
For all $\resolution \ge \big( 2 \sqrt{d} \big)^d / (\gaussCircleError s)$ it holds that $\integerSphere{d}[\resolution s] \le (1 + \gaussCircleError) \cdot \normSphere{d} \cdot \left( \resolution s \right)^d$.

We start by considering a sphere of radius $\resolution s + \sqrt{d}$ at the origin.
Note that this enlarged sphere contains for each grid point $(x_1, \dots, x_d)$ in the original sphere the cubic region $[x_1, x_1 + 1] \times \dots \times [x_d, x_d + 1]$ of volume $1$.
Thus, the volume of the enlarged sphere is a trivial upper bound on the number of grid points in the original sphere.

Formally, we get

\[
\integerSphere{d}[\resolution s]
\le \normSphere{d} \cdot \left( \resolution s + \sqrt{d} \right)^d ,
\]

which we rewrite as

\[
\normSphere{d} \cdot \left( \resolution s + \sqrt{d} \right)^d
= \normSphere{d} \cdot \left( \resolution s \right)^d + \normSphere{d} \cdot \sum_{i \in [d]} \binom{d}{i} \left( 	\resolution s \right)^{d-i} \sqrt{d}^i	.
\]

Further, note that for our choice of $\resolution$ it holds that $\resolution s \ge 1$.
Thus, we get

\[
\normSphere{d} \cdot \left( \resolution s \right)^d + \normSphere{d} \cdot \sum_{i \in [d]} \binom{d}{i} \left( \resolution s \right)^{d-i} \sqrt{d}^i
\le
\normSphere{d} \cdot \left( \resolution s \right)^d + \normSphere{d} \cdot \left( \resolution s \right)^{d-1} \cdot 2^d \sqrt{d}^d
\normSphere{d} \cdot \left( \resolution s \right)^d \cdot \left( 1 + \frac{1}{\resolution s} \left( 2 \sqrt{d} \right)^d \right) .
\]

We conclude the proof by noting that $\big( 2 \sqrt{d} \big)^d / \resolution s \le \gaussCircleError$.

As we fixed $\radius = (1/\normSphere{d})^{1/d}$ we can immediately conclude that for every $\gaussCircleError \in (0, 1]$ there is some $\resolution_{\gaussCircleError} \in \bigTheta{1/\gaussCircleError}$ such that for all $\resolution \ge \resolution_{\gaussCircleError}$ it holds that

\[
\hsDegree{\resolution} \le (1 + \gaussCircleError) \left(2 \resolution \right)^d .
\]

Finally, the following general lemma will help us to turn a sampling scheme for $\gibbsDistribution[\hsGraph{\resolution}, \hsWeight{\resolution}]$ into a randomized approximation of $\partitionFunction[\hsGraph{\resolution}, \hsWeight{\resolution}]$.

Let $(\graph, \weights)$ be an instance of the multivariate hard-core model and let $\clique$ be a clique cover of size $\numberOfCliques$ with $\maxPartition = \max_{i \in [\numberOfCliques]} \{\partitionFunction[\subgraph{\hsGraph{\resolution}}{\clique[i]}]\}$.
Further, for $i \in [\numberOfCliques]$ let $\vertices_i = \vertices \setminus \bigcup_{j < i} \clique[j]$.
For every $\err \in (0, 1]$ there are $s \in \bigTheta{\numberOfCliques \maxPartition / \err^2}$ and $\err_s \in \bigTheta{\err/(\numberOfCliques \maxPartition)}$ such that a randomized $\err$-approximation of $\partitionFunction[\graph, \weights]$ can be computed by drawing $s$ samples $\err_s$-approximately from $\gibbsDistribution[\subgraph{\graph}{\vertices_i}]$ for each $i \in [\numberOfCliques]$.

Note that sampling from $\gibbsDistribution[\subgraph{\graph}{\vertices_i}]$ means sampling from $\gibbsDistribution[\graph]$ for $i = 0$ and ignoring all cliques $\{\clique_j\}_{j < i}$ for $i \ge 1$.

Set $\gaussCircleError = \delta/2$ and $\err' = \err/3$.
By combining <Ref> and <Ref>, we know that we can choose a resolution $\resolution \in \bigTheta{\eulerE^{\vol{\volume} \ln \vol{\volume}} / \left(\err' \gaussCircleError\right)} = \bigTheta{\eulerE^{\vol{\volume} \ln \vol{\volume}} / \left(\err \gaussCircleError\right)}$ such that

\begin{gather}
\label{eq:hard_sphere_approx:convergence}
1 - \err' \le \frac{\hardSpherePrt[\volume, \hsFugacity]}{\partitionFunction[\hsGraph{\resolution}, \hsWeight{\resolution}]} \le 1 + \err' \text{ and }\\
\label{eq:hard_sphere_approx:integer_sphere}
\hsDegree{\resolution} \le (1 + \gaussCircleError) \left(2 \resolution \right)^d .
\end{gather}

Note that $(1 - \err')^2 \ge 1 - \err$ and $(1 + \err')^2 \le 1 + \err$.
Thus, <ref> implies that it is sufficient to $\err'$-approximate $\partitionFunction[\hsGraph{\resolution}, \hsWeight{\resolution}]$.
We start by arguing that we can apply <Ref> to $\partitionFunction[\hsGraph{\resolution}, \hsWeight{\resolution}]$.
Then, we construct a clique cover and show that each step of the clique dynamics can be computed efficiently.
Finally, we will use <Ref> to get the desired approximation.

To apply <Ref>, we need to show that $\hsWeight{\resolution} \le \left(1 - \delta'\right) \criticalWeight{\hsDegree{\resolution}}$ for some $\delta' \in (0, 1]$.
To this end, we choose $\delta' = \delta/2$.
Due to <ref> we know that

\[
\criticalWeight{\hsDegree{\resolution}}
= \frac{(\hsDegree{\resolution} - 1)^{\hsDegree{\resolution} - 1}}{(\hsDegree{\resolution} - 2)^{\hsDegree{\resolution}}}
\ge \frac{\left((1 + \gaussCircleError) \left(2 \resolution \right)^d - 1\right)^{(1 + \gaussCircleError) \left(2 \resolution \right)^d - 1}}{\left((1 + \gaussCircleError) \left(2 \resolution \right)^d - 2\right)^{(1 + \gaussCircleError) \left(2 \resolution \right)^d}} .
\]

Now, note that

\[
\hsFugacity
\le (1 - \delta) \frac{\eulerE}{2^d}
\le \frac{1 - \frac{\delta}{2}}{1 + \frac{\delta}{2}} \frac{\eulerE}{2^d}
= \frac{1 - \delta'}{1 + \gaussCircleError} \frac{\eulerE}{2^d}
\le \left(1 - \delta'\right) \resolution^{d} \frac{\left((1 + \gaussCircleError) \left(2 \resolution \right)^d - 1\right)^{(1 + \gaussCircleError) \left(2 \resolution \right)^d - 1}}{\left((1 + \gaussCircleError) \left(2 \resolution \right)^d - 2\right)^{(1 + \gaussCircleError) \left(2 \resolution \right)^d}} ,
\]

where the last inequality comes from the fact that $x \frac{(x-1)^{x-1}}{(x-2)^{x}}$ converges to $\eulerE$ from above as $x \to \infty$.
Dividing by $\resolution^d$ yields $\hsWeight{\resolution} = \resolution^{-d} \hsFugacity \le \left(1 - \delta'\right) \criticalWeight{\hsDegree{\resolution}}$.

We now construct the clique cover that we are going to use.
This is done by dividing the grid $\grid[\resolution \sidelength]$ into cubic regions of side length $a = \left\lfloor \frac{2 \resolution}{\sqrt{d}} \normSphere{d}^{-1/d} \right\rfloor$.
Formally, for a tuple $(i_{1}, \dots, i_{d}) \in \N^d$, let

\[
\subgrid[i_{1}, \dots, i_{d}] = \set{(x_1, \dots, x_d) \in \grid }{\forall j \in [d]\colon i_j a \le x_j < (i_j + 1) a}.
\]

Note that for every pair of grid points $x, y \in \subgrid[i_{1}, \dots, i_{d}]$ it holds that $\dist{x}{y} < 2 \resolution \normSphere{d}^{-1/d} = 2 \resolution \radius$.
Thus, the set of vertices, corresponding to grid points in $\subgrid[i_{1}, \dots, i_{d}]$, form a clique in $\hsGraph{\resolution}$.
We obtain a clique cover $\clique$ of size $\numberOfCliques = \size{\clique} \in \bigO{\left(\resolution \sidelength / a \right)^d} = \bigO{\vol{\volume}}$.
Further, it holds that

\[
\maxPartition \le 1 + a^d \hsWeight{\resolution} = 1 + a^d \resolution^{-d} \hsFugacity \in \bigO{1}.
\]

By <Ref>, the clique dynamics based on $\clique$ have mixing time polynomial in $\vol{\volume}^{1/\delta'^2}$, thus also polynomial in $\vol{\volume}^{1/\delta^2}$, and in $\ln\left( 1 / \err_{s}\right)$ for any sampling error $\err_{s} \in (0, 1]$.

We proceed by arguing that we can compute each step efficiently.
Note that we cannot construct the graph explicitly, as it would be far to large for our choice of resolution $\resolution$.
However, by identifying each vertex by its corresponding grid point, deciding whether there is an edge between two vertices or if a vertex belongs to a certain clique can be done by comparing integers up to size $\bigO{\resolution \sidelength}$, which can be done in $\bigO{\ln\left(\resolution \sidelength\right)} = \bigO{\vol{\volume} \ln \vol{\volume}}$.
Choosing a clique from the clique cover can be done by choosing $d$ integers up to size $\bigO{\sidelength}$.
Finally, for a given clique $\clique[i]$, we can sample from $\gibbsDistributionFunction{~\cdot~}[\hsGraph{\resolution}, \hsWeight{\resolution}][\clique[i]][\zeroSpinConfig[\hsVertices{\resolution} \setminus \clique[i]]] = \gibbsDistribution[\subgraph{\hsGraph{\resolution}}{\clique[i]}, \hsWeight{\resolution}]$ by

sample $x \in \subgrid[i]$ uniformly at random, where $\subgrid[i]$ is the region of the grid corresponding to $\clique[i]$, and

return $\emptyset$ with probability $\frac{1}{\partitionFunction[\subgraph{\hsGraph{\resolution}}{\clique_i}]}$ and $\{\hsVertex{x}\}$ otherwise.

Note that <ref> involves sampling $d$ integers up to size $\bigO{a}$. In addition, step <ref> involves computing $\partitionFunction[\subgraph{\hsGraph{\resolution}}{\clique_i}] = 1 + \size{\clique[i]} \resolution^{-d} \hsFugacity$.
Thus, sampling from $\gibbsDistribution[\subgraph{\hsGraph{\resolution}}{\clique[i]}, \hsWeight{\resolution}]$ can be done in $\bigO{\ln (a)} = \bigO{\vol{\volume} \ln \vol{\volume}}$.

We now know that we can sample $\err_s$-approximately from $\gibbsDistribution[\hsGraph{\resolution}, \hsWeight{\resolution}]$ in time polynomial in $\vol{\volume}^{1/\delta^2}$ and $\ln(1/\err_s)$.
Applying <Ref> proves the theorem.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

booktitleProc. of STOC'20
titleImproved analysis of higher order random walks and applications

titleSpectral independence in high-dimensional expanders and applications to the hardcore model

journaltitleJournal of Mathematical Physics
titleRandom sampling for the monomer–dimer model on a lattice

booktitleProc. of STOC'18
titleInapproximability of the independent set polynomial in the complex plane

journaltitleRandom Structures & Algorithms
titleSpatial mixing and nonlocal Markov chains

journaltitleRandom Structures & Algorithms
titleSwendsen-Wang dynamics for general graphs in the tree uniqueness region

booktitleProc. of STOC'20
titleEfficient sampling and counting algorithms for the Potts model on \(\mathbb{Z}\)$^{d}$ at all temperatures

seriesFundamental Studies in Engineering
titleStatistical thermodynamics of simple liquids and their mixtures

booktitleProc. of SODA'20
titleCounting independent sets in unbalanced bipartite graphs

titleZeros and approximations of holant polynomials on the complex plane

booktitleProc. of APPROX/RANDOM'19
titleFast algorithms at low temperatures via Markov chains

titleRapid mixing for colorings via spectral independence

titleOptimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion

titleRapid mixing of Glauber dynamics up to uniqueness via contraction

journaltitleElectronic Journal of Probability
titleDisagreement percolation for the hard-sphere model

journaltitleThe Annals of Applied Probability
titleComparison theorems for reversible Markov chains

journaltitleRandom Structures & Algorithms
titleRandomly coloring sparse random graphs with fewer colors than the maximum degree

journaltitleSIAM Journal on Computing
titleOn counting independent sets in sparse graphs

booktitleProc. of SODA'14
titleMCMC sampling colourings and independent sets of $G(n, d/n)$ near uniqueness threshold

booktitleProc. of SODA'18
titleSampling random colorings of sparse random graphs

booktitleNovel Methods in Soft Matter Simulations
titleStatistical mechanics of coarse-graining

titleRapid mixing from spectral independence beyond the Boolean domain

journaltitleJournal of Statistical Physics
titleThe analyticity region of the hard sphere gas. Improved bounds

titlePolymer dynamics via cliques: New conditions for approximations

journaltitleRandom Structures & Algorithms
titleImproved inapproximability results for counting independent sets in the hard-core model

titleInapproximability of the independent set polynomial below the Shearer threshold

booktitleProc. of MFCS'20
noteTo appear
titleFast algorithms for general spin systems on bipartite expanders

journaltitleRandom Structures & Algorithms
titleSlow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs

titlePerfect simulation of the hard disks model by partial rejection sampling

Academic Press

booktitleTheory of Simple Liquids
editionFourth Edition
titleTheory of Simple Liquids

booktitleProc. of SODA'18
titleComputing the independence polynomial: From the tree threshold down to the roots

titleLower bounds on the critical density in the hard disk model via optimized metrics

titleCorrelation decay for hard spheres via Markov chains

booktitleProc. of STOC'19
titleAlgorithmic Pirogov–Sinai theory

journaltitleForum of Mathematics, Sigma
titleOn the hard sphere model and sphere packings in high dimensions

booktitleProc. of SODA'19
titleAlgorithms for #BIS-hard problems on expander graphs

booktitleProc. of ISAAC'03
titleRapid mixing of several Markov chains for a hard-core model

booktitleProbability Towards 2000
titlePerfect simulation for the area-interaction point process

journaltitleAdvances in Applied Probability
titlePerfect simulation using dominating processes on ordered spaces, with application to locally stable point processes

American Mathematical Society

titleMarkov chains and mixing times

booktitleProc. of SODA'13
titleCorrelation decay up to uniqueness in spin systems

booktitleLectures on probability theory and statistics
titleLectures on Glauber dynamics for discrete spin models

journaltitleThe Journal of Chemical Physics
titleEquation of state calculations by fast computing machines

titleAnalyticity for classical gasses via recursion

journaltitleSIGMETRICS Performance Evaluation Review
titleAnalysis of perfect sampling methods for hard-sphere models

journaltitleProbability Theory and Related Fields
titleGibbs rapidly samples colorings of $G (n, d/n)$

journaltitleProbability Theory and Related Fields
titleOn the hardness of sampling independent sets beyond the tree threshold

journaltitleSIAM Journal on Computing
titleDeterministic polynomial-time approximation algorithms for partition functions and graph polynomials

journaltitleJournal of Statistical Physics
titleSelf-avoiding walks and trees in spread-out lattices

journaltitleProbability Theory and Related Fields
titleImproved mixing condition on the grid for counting and sampling independent sets

Cambridge University Press

journaltitleCombinatorics, Probability and Computing
titleImproved bounds for mixing rates of Markov chains and multicommodity flow

journaltitleProbability Theory and Related Fields
titleSpatial mixing and the connective constant: Optimal bounds

booktitleProc. of FOCS'10
titleComputational transition at the uniqueness threshold

booktitleApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
titleImproved bounds on the phase transition for the hard-core model in 2-dimensions

Wiley Online Library

journaltitleRandom Structures & Algorithms
titleCombinatorial criteria for uniqueness of Gibbs measures

booktitleProc. of STOC'06
titleCounting independent sets up to the tree threshold