# Practical Synchronization for OTFS

Mohsen Bayat, Sanoopkumar P. S., and Arman Farhang This publication has
emanated from research conducted with the financial support of Science
Foundation Ireland under Grant number 19/FFP/7005(T). Department of Electronic
& Electrical Engineering, Trinity College Dublin, Ireland
{bayatm, pungayis<EMAIL_ADDRESS>
###### Abstract

In the existing literature on joint timing and frequency synchronization of
orthogonal time frequency space modulation (OTFS), practically infeasible
impulse pilot with large peak-to-average power ratio (PAPR) is deployed.
Hence, in this paper, we propose a timing offset (TO) and carrier frequency
offset (CFO) estimation for OTFS over a linear time-varying (LTV) channel,
using a low PAPR pilot structure. The proposed technique utilizes the recently
proposed practically feasible pilot structure with a cyclic prefix (PCP). We
exploit the periodic properties of PCP in both delay and time domains to find
the starting point of each OTFS block. Furthermore, we propose a two-stage CFO
estimation technique with over an order of magnitude higher estimation
accuracy than the existing estimator using the impulse pilot. In the first
stage, a coarse CFO estimate is obtained which is refined in the second stage,
through our proposed maximum likelihood (ML) based approach. The proposed ML-
based approach deploys the generalized complex exponential basis expansion
model (GCE-BEM) to capture the time variations of the channel, absorb them
into the pilot and provide an accurate CFO estimate. Since our proposed
synchronization technique utilizes the same pilot deployed for channel
estimation, it does not require any additional overhead. Finally, we evaluate
the performance of our proposed synchronization technique through simulations.
We also compare and show the superior performance of our proposed technique to
the only other existing joint TO and CFO estimation method in OTFS literature.

###### Index Terms:

OTFS, timing offset estimation, carrier frequency offset estimation, maximum
likelihood estimation.

##  I Introduction

Orthogonal time-frequency space (OTFS) is a prominent waveform candidate for
the sixth-generation (6G) wireless communication systems due to its robustness
to time-varying wireless channel and backward compatibility with orthogonal
frequency division multiplexing (OFDM), [1]. Unlike OFDM, OTFS places
modulated data symbols in the delay Doppler (DD) domain and spreads it on the
time-frequency (TF) plane, thus exploiting the full diversity gain of the time
and frequency selective channel in high mobility scenarios, [2]. Since the
performance of multicarrier modulations depends on the orthogonality among
subcarriers, timing and carrier synchronization are of paramount importance in
modern wireless communication systems. Even though there exists a large body
of work on OFDM synchronization [3], OTFS literature on this topic is still in
its infancy.

Timing offset (TO) and/or carrier frequency offset (CFO) estimation in OTFS
are addressed in [4, 5, 6, 7]. A threshold-based TO offset estimation
technique for OTFS uplink transmission using random access (RA) preamble is
presented in [4]. In [5], the authors developed a correlation-based method for
TO estimation in OTFS downlink transmission, which uses a preamble consisting
of a linear frequency-modulated (LFM) waveform and two OTFS symbols. Due to
the rapid variation of the channel in high mobility scenarios, the TO
estimated at the base station using the preamble would be outdated during the
data transmission phase. Hence, the methods developed in [4] and [5] are not
suitable for high-mobility scenarios, and CFO estimation is not addressed in
either [4] or [5].

A time domain joint channel-CFO estimation and time domain equalization
technique for OTFS are presented in [6]. In [6], the CFO is estimated and
compensated as a part of the channel which hinders the pre-compensation of the
CFO at the user terminal which is unsuitable for uplink transmissions.
Recently, in [7], we addressed the TO and CFO estimation in the OTFS systems,
where we developed a correlation-based estimation scheme that exploited the
periodic structure of the pilot in the delay-time domain. The embedded impulse
pilot which is proposed in [8] and widely used for channel estimation in OTFS
systems is employed in [6] and [7].

Accurate TO and CFO synchronization using the methods proposed in [6] and [7]
requires a high-power impulse pilot. However, the high power of the impulse
pilot and the zero guards around it increases the peak-to-average power ratio
(PAPR) of the transmitted signal [9]. High PAPR of the transmitted signal will
result in a reduction in the efficiency of the power amplifier at the radio
frequency (RF) front end, [10]. Hence, the widely used impulse pilot is not
suitable for practical applications. To address this issue in [9], we proposed
a novel embedded pilot which uses a constant amplitude pilot sequence with a
cyclic prefix (CP), called pilot with cyclic prefix (PCP), placed along
multiple delay bins of a single Doppler bin in the delay-Doppler domain. PCP
significantly reduces the PAPR of the transmitted signal and thus, it is more
suitable for practical applications than impulse pilot.

Based on the above, the very limited literature available on the
synchronization in OTFS uses practically infeasible pilot structures. Hence,
to address this issue in this paper, we develop a practical TO and CFO
estimation for OTFS, using the PCP deployed for channel estimation in [9]. We
exploit the periodicity of the PCP in the delay-time domain and propose a
correlation-based TO and coarse CFO estimation. Furthermore, to improve the
accuracy of CFO estimation we approximate the time variation of the channel
using a generalized complex exponential basis expansion model (GCE-BEM) [11].
We propose a maximum likelihood (ML) CFO fine estimation technique that
provides over an order of magnitude higher estimation accuracy than the
existing estimator using the impulse pilot. To corroborate our claims, we
analyze the performance of our proposed TO and CFO estimation techniques
through simulations. In our simulations, we study the mean and variance of the
TO estimation error and the mean square error (MSE) of the CFO estimates.

The rest of this paper is organized as follows. Section II describes the
system model. The proposed estimation techniques are presented in Sections III
and IV, respectively, and their performance is evaluated by simulations in
Section V. Finally, Section VI concludes the paper.

$Notations$: Scalar values, vectors, and matrices are denoted by normal
letters, boldface lowercase, and boldface uppercase, respectively.
$\rm{diag}[.]$, $\rm{blkdiag}[.]$, $(\\!(.)\\!)_{k}$, and $\max_{k}\\{.\\}$,
present a diagonal matrix, block diagonal matrix, $k^{\rm{th}}$ circular
shift, and maximum of a function regarding $k$, respectively. $|.|$,
$\angle.$, and $\rm{Re}\\{.\\}$ denote the gain, phase, and real part of the
complex argument, respectively. $\mathbf{I}_{N}$ is an identity matrix with
size $N\times N$. The superscripts $(.)^{\rm{H}}$, $(.)^{\rm{T}}$ and
$(.)^{-1}$ indicate hermitian, transpose, and inverse operations,
respectively. $\mathbb{C}^{M\times N}$ stands for a set of complex values with
size $M\times N$ and the Kronecker product is denoted by $\otimes$. Finally,
$\mathcal{O}(.)$ presents the order of the complexity for a function.

##  II System Model

We consider an OTFS system with $M$ delay and $N$ Doppler bins, with a Doppler
resolution of $\Delta\nu=\frac{1}{MNT_{\rm s}}$ and a delay resolution of
$\Delta\tau=T_{\rm s}$, where $T_{\rm s}$ is the sampling period [1]. The data
symbols and the pilot sequence are multiplexed together to form the delay-
Doppler domain OTFS transmitted block $\mathbf{D}\in\mathbb{C}^{M\times N}$
with the elements $D[m,n]$ for $m=0,\ldots,M-1$ and $n=0,\ldots,N-1$. In this
paper, we deploy the pilot structure, PCP, that was originally proposed for
channel estimation in [9], also for synchronization. Considering $L$ as the
channel length, in PCP, a constant amplitude Zadoff-Chu (ZC) sequence with
length $L$ is placed in the Doppler bin $n_{\rm{p}}$ and the delay bins
$m_{\rm{p}},\ldots,m_{\rm{p}}+L-1$. The last $L-1$ samples of this sequence
are then appended as a CP in the Doppler bin $n_{\rm{p}}$ and the delay bins
$m_{\rm{p}}-L,\ldots,m_{\rm{p}}-1$. The remaining Doppler bins within the
pilot region are set to zero. The delay-Doppler domain OTFS block where the
PCP is embedded with data symbols, is shown in Fig. 1.

The OTFS transmitter spreads the symbols $D[m,n]$ from the delay-Doppler to
the delay-time domain by taking inverse discrete Fourier (IDFT) across the
Doppler dimension, [2],

$X[m,l]=\frac{1}{\sqrt{N}}\sum_{n=0}^{N-1}D[m,n]e^{\frac{j2\pi ln}{N}},$ (1)

where $l=0,\ldots,N-1$ is the time index and $m=0\ldots,M-1$ is the delay
index. The delay-time domain signal is then converted to the serial stream
$\mathbf{x}=[x[0],\ldots,x[MN-1]]^{\rm T}$, where $x[lM+m]=X[m,l]$. Finally,
the OTFS transmit signal $s[k]$ is formed by appending a CP with the length
$L_{\rm{CP}}\geq L-1$ at the beginning of the OTFS block. Assuming ideal
pulse-shaping, the received delay-time signal for $B$ OTFS blocks, after
transmission over the linear time-varying (LTV) channel and in presence of TO
and CFO, can be represented as

$r[k]=e^{j\frac{2\pi\varepsilon
k}{MN}}\sum_{i=0}^{B-1}\sum_{\ell=0}^{L-1}h[\ell,k]s[k-\ell-\theta-
iN_{\rm{T}}]+\eta[k],$ (2)

where $0\leq k\leq L_{\rm CP}+MN-1$, $\theta$ and $\varepsilon$ are the TO and
CFO values, normalized by the delay and doppler spacings, respectively, and
$N_{\rm{T}}=MN+L_{\rm CP}$. $h[\ell,k]$ is the delay-time domain channel
impulse response of the $k^{\text{th}}$ delay tap at $\ell^{\text{th}}$ time
instant. $\eta[k]$ is the complex additive white Gaussian noise (AWGN) with
the variance $\sigma_{\eta}^{2}$.

##  III Proposed TO Estimation Technique

Figure 1: PCP structure in both delay-Doppler and delay-time domains.

In this section, we present our proposed TO estimation technique for OTFS
using PCP. PCP has a very attractive dual periodicity property in the delay-
time domain. The periodicity of PCP in the delay dimension is due to the
presence of CP. Meanwhile, the periodicity in the time domain is due to the
spreading effect of the OTFS transmitter which scales and then repeats each
pilot sample across the time dimension. We exploit this dual periodicity of
the PCP in the delay and time dimensions to estimate the TO. We consider the
TO as $\theta=\theta_{\rm{d}}+M\theta_{\rm{t}}$, where $\theta_{\rm d}$ and
$\theta_{\rm t}$ are the TO in delay and time dimensions, respectively. Our
proposed TO estimator finds $\theta_{\rm d}$ and $\theta_{\rm t}$ in two
stages, without any estimation range limitation.

###  III-A TO estimation in delay dimension

The delay-time domain pilot sequence in the delay dimension can be split into
two identical halves, each with the length $L-1$, see Fig. 1. Assuming that
the time variation of the channel within the pilot duration in delay, i.e.,
$2L-1$ samples, is negligible, the LTV channel over this duration can be
considered as linear time-invariant (LTI). Hence, the periodic property of the
pilot along the delay dimension is preserved and the TO can be estimated by
searching for two identical halves in the received pilot signal. However,
channel time variations along the time dimension are not negligible. As it was
shown in [7], the identical parts of the pilot along the time dimension should
be brought as close as possible to each other to exploit the periodicity in
time for TO estimation. The extreme case for this is satisfied for PCP in the
delay-time domain as all the pilot samples in a given delay bin $m\in\\{m_{\rm
p}-L,\ldots,m_{\rm p}+L-1\\}$ have the same amplitude and the linear phase of
${{2\pi n_{\rm{p}}l}/{N}}$ for $l=0,1,\ldots,N-1$. For instance, when $n_{\rm
p}=N/2$, the adjacent pilot samples across each delay row have a phase
difference of $\pi$, see Fig. 1. The impulse pilot in [7] can only exploit the
diversity in $L$ delay bins for TO estimation. In contrast, PCP achieves an
improved timing estimation performance, as it takes advantage of the full
diversity provided by all the $2L-1$ delay bins allocated to pilot
transmission.

Figure 2: Sliding window for estimation of $\theta_{\rm d}$.

As shown in Fig. 2, our proposed TO estimator searches for a periodic signal
with identical parts in both delay and time dimensions using a sliding window.
To find the periodic sequence in the delay dimension, we define a window with
two halves covering $L-1$ samples each. The window slides across the delay
dimension to find two pairs of data samples with the highest similarity. In
fact, the window searches for the pilot sequences with two identical halves
along the delay dimension. To cast this process into a mathematical
formulation, using the received signal $r[k]$, we define the timing metric

$P_{\rm{d}}[m]=\sum_{i=0}^{N-1}\sum_{u=0}^{L-2}r^{*}[iM+m+u]r[iM+m+u+L],$ (3)

that can be efficiently implemented in an iterative manner as

$\displaystyle
P_{\rm{d}}[m+1]=P_{\rm{d}}[m]-\sum_{i=0}^{N-1}r^{*}[iM+m]r[iM+m+1]$
$\displaystyle+\sum_{i=0}^{N-1}r^{*}[iM+m+L-2]r[iM+m+L-1],$ (4)

where $m\\!=\\!0,\ldots,M-1$ and $l\\!=\\!0,\ldots,N-1$. Consequently,
${\theta}_{\rm d}$ is estimated by finding the peak of this timing metric as

$\hat{\theta}_{\rm
d}={\arg}\max_{m}\\{|P_{\rm{d}}[m]|\\}-(m_{\rm{p}}-L)-L_{\rm{CP}}-\lfloor\mu_{{h}}\rfloor,$
(5)

where
$\mu_{{h}}=\frac{\sum_{\ell=0}^{L-1}(\ell+1)\alpha^{2}_{\ell}}{\sum_{\ell=0}^{L-1}\alpha^{2}_{\ell}}$
is the mean of delay that is imposed by the channel and $\alpha_{\ell}$ for
$\ell=0,\ldots,L-1$ represents the channel power delay profile (PDP), [12].
The multipath effect of the channel leads to a bias in the TO estimate that
can be corrected by the knowledge of the channel’s first-order moment [13].
The proposed estimator even works without this knowledge by increasing the CP
length with $\lfloor\mu_{{h}}\rfloor$ samples.

Figure 3: Sliding window for estimation of $\theta_{\rm t}$.

###  III-B TO estimation in time dimension

The peak of the correlation function $P_{\rm{d}}[m]$ on the row
$m^{\prime}_{\rm p}-L=\hat{\theta}_{\rm d}+(m_{\rm
p}-L)+L_{\rm{CP}}+\lfloor\mu_{h}\rfloor$ of the delay-time grid can provide an
estimate of $\theta_{\rm t}$, where $m^{\prime}_{\rm p}=\hat{\theta}_{\rm
d}+m_{\rm p}$. However, this estimate is not very accurate. This is while even
a single error in time cannot be afforded as the estimation error of one
sample in $\theta_{\rm t}$ leads to an effective error of $M$ samples in the
final TO estimate. This highlights the importance of the need for a highly
accurate estimation of $\theta_{\rm t}$. Thus, to estimate $\theta_{\rm t}$,
we deploy a sliding window with the length $2N-1$ that covers the delay bins
$m^{\prime}_{\rm{p}}-L,\ldots,m^{\prime}_{\rm{p}}+L-1$ and slides along time,
see Fig. 3. This window calculates the correlation between every two adjacent
samples in time for all $2L-1$ delay bins in the pilot region. This process
can be mathematically shown as

$P_{\rm{t}}[l]=\sum_{i=m^{\prime}_{\rm{p}}-L}^{m^{\prime}_{\rm{p}}+L-1}\sum_{v=0}^{N-2}r^{*}[(l+v)M+i]r[(l+v+1)M+i],$
(6)

that can be iteratively implemented as

$\displaystyle
P_{\rm{t}}[l+1]=P_{\rm{t}}[l]-\sum_{i=m^{\prime}_{\rm{p}}-L}^{m^{\prime}_{\rm{p}}+L-1}r^{*}[lM+i]r[(l+1)M+i]$
$\displaystyle+\sum_{i=m^{\prime}_{\rm{p}}-L}^{m^{\prime}_{\rm{p}}+L-1}r^{*}[(l+N-2)M+i]r[(l+N-1)M+i],$
(7)

where $l=0,1,...,N-1$. Hence, $\theta_{\rm{t}}$ is estimated by finding the
peak of $P_{\rm{t}}$, i.e.,

$\hat{\theta}_{\rm t}={\arg}\max_{l}\\{|P_{\rm{t}}[l]|\\}.$ (8)

Fig. 4 shows a snapshot of the timing metrics at the SNR of $20$ dB for an
OTFS system with $M=128$ and $N=32$ for both LTI and LTV channels.

After correcting the TO with $\hat{\theta}=\hat{\theta}_{\rm
d}+M\hat{\theta}_{\rm t}$, in the following section, we propose a novel two-
stage CFO estimation technique. Our proposed technique finds a coarse estimate
of the CFO by using the angle of the timing metric that we used for TO
estimation, and then this estimate is refined by using our proposed ML
estimation technique.

##  IV CFO Estimation Using Maximum Likelihood

Figure 4: One snapshot of the timing metrics in delay and time dimensions for
SNR=20 dB where $(\theta_{\rm{d}}+L_{\rm{CP}})=72$ and $\theta_{\rm{t}}=15$.
$\displaystyle\mathbf{H}_{l}=\\!\\!\begin{bmatrix}h[0,L_{\rm{CP}}+lM+m_{\rm{p}}]&h[L\\!-\\!1,L_{\rm{CP}}+lM+m_{\rm{p}}]&\cdots&h[1,L_{\rm{CP}}+lM+m_{\rm{p}}]\\\
h[1,L_{\rm{CP}}+lM+m_{\rm{p}}+1]&h[0,L_{\rm{CP}}+lM+m_{\rm{p}}+1]&\cdots&h[2,L_{\rm{CP}}+lM+m_{\rm{p}}+1]\\\
\vdots&\vdots&\ddots&\vdots\\\
h[L-1,L_{\rm{CP}}+lM+m_{\rm{p}}+L\\!-\\!1]&h[L-2,L_{\rm{CP}}+lM+m_{\rm{p}}+L\\!-\\!1]&\cdots&h[0,L_{\rm{CP}}+lM+m_{\rm{p}}+L\\!-\\!1]\end{bmatrix}$
(13)

Considering this phase difference, and averaging the correlation angle over
the delay bins allocated with the pilot at the timing instant
$\hat{\theta}_{\rm t}$ from (6),

$\displaystyle\Upsilon_{\hat{\theta}_{\rm
t}}=\\!\frac{1}{2L-1}\sum_{i=m^{\prime}_{\rm{p}}-L}^{m^{\prime}_{\rm{p}}+L-1}{\angle}\\!\sum_{v=0}^{N-2}$
$\displaystyle(r^{*}[(\hat{\theta}_{\rm t}+v)M+i]\times$ $\displaystyle
r[(\hat{\theta}_{\rm t}+v+1)M+i]),$ (9)

a coarse CFO estimate can be obtained as

$\hat{\varepsilon}_{\rm c}=\frac{N}{2\pi}\Upsilon_{\hat{\theta}_{\rm
t}}-n_{\rm{p}}.$ (10)

To refine this CFO estimate and improve the estimation accuracy, in the
following, we develop an ML-based technique as a fine CFO estimation stage.

After correcting the TO, the received pilots in the delay bins $m_{\rm{p}}$ to
$m_{\rm{p}}+L-1$ over all the bins along the time dimension are used for CFO
estimation. For ease of explanation, in the rest of the paper, the received
pilots refer to the received signal in the delay bins $m_{\rm{p}}$ to
$m_{\rm{p}}+L-1$. After removing the CP from the received pilot, and stacking
the resulting signals at different time slots, $\mathbf{r}_{l,\rm p}=[r[L_{\rm
CP}+lM+m_{\rm p}],\ldots,r[L_{\rm CP}+lM+m_{\rm p}+L-1]]^{\rm T}$, into the
vector $\mathbf{r}^{\rm{p}}=[\mathbf{r}_{0,\rm p}^{\rm T},\mathbf{r}_{1}^{\rm
T},\ldots,\mathbf{r}_{N-1,\rm p}^{\rm T}]^{\rm{T}}\in\mathbb{C}^{NL\times 1}$,
using (2), $\mathbf{r}^{\rm{p}}$ can be expressed as,

$\mathbf{r}^{\rm{p}}=\mathbf{\Gamma}(\varepsilon)\mathbf{H}\mathbf{s}^{\rm{p}}+\boldsymbol{\eta},$
(11)

where,
$\mathbf{\Gamma(\varepsilon)}\\!=\\!{\rm{blkdiag}}[\mathbf{\Gamma}_{0},\mathbf{\Gamma}_{1},\ldots,\mathbf{\Gamma}_{N-1}]$
with

$\displaystyle\mathbf{\Gamma}_{l}={\rm{diag}}[e^{\frac{j2\pi\varepsilon(L_{\rm{CP}}+lM+m_{\rm{p}})}{N_{\rm{T}}}},e^{\frac{j2\pi\varepsilon(L_{\rm{CP}}+lM+m_{\rm{p}}+1)}{N_{\rm{T}}}},\ldots,$
$\displaystyle
e^{\frac{j2\pi\varepsilon(L_{\rm{CP}}+lM+m_{\rm{p}}+L-1)}{N_{\rm{T}}}}],$ (12)

and
$\mathbf{H}\\!=\\!{\rm{blkdiag}}[\mathbf{H}_{0},\mathbf{H}_{1},...,\mathbf{H}_{N-1}]$
with $\mathbf{H}_{l}$ being the channel matrix, whose structure is shown in
(13), on the top of the next page. In (11),
$\mathbf{s}^{\rm{p}}=[\mathbf{s}_{0,{\rm p}}^{\rm
T},\ldots,\mathbf{s}_{N-1,{\rm p}}^{\rm T}]^{\rm{T}}\in\mathbb{C}^{NL\times
1}$, $\mathbf{s}_{l,{\rm p}}$ is the transmitted delay-time pilot samples in
the delay bins $m_{\rm{p}}$ to $m_{\rm{p}}+L-1$ and the time slot $l$.
$\boldsymbol{\eta}\sim\mathcal{CN}(\mathbf{0},\mathbf{\sigma}_{\eta}^{2}\mathbf{I}_{LN})$
is the AWGN vector with size $LN\times 1$ that affects the pilot. By
interchanging the convolution order in (11), the received pilot at the time
slot $l$ can be expressed as

$\mathbf{r}_{l,{\rm p}}=\mathbf{\Gamma}_{l}(\varepsilon)\mathbf{A}_{l,{\rm
p}}\mathbf{h}_{l}+\boldsymbol{\eta}_{l},$ (14)

where $\mathbf{A}_{l,{\rm p}}=[\mathbf{S}_{l,{\rm
p}}^{0},...,\mathbf{S}_{l,{\rm p}}^{L-1}]$, $\mathbf{S}_{l,{\rm
p}}^{\ell}={\rm{diag}}[(\\!(\mathbf{s}_{l,{\rm p}})\\!)_{\ell}]$,
$\mathbf{h}_{l}=[(\mathbf{h}_{l}^{0})^{\rm{T}},(\mathbf{h}_{l}^{1})^{\rm{T}},\ldots,(\mathbf{h}_{l}^{L-1})^{\rm{T}}]^{\rm{T}}$,
and
$\mathbf{h}_{l}^{\ell}=[h[\ell,L_{\rm{CP}}+lM+m_{\rm{p}}],h[\ell,L_{\rm{CP}}+lM+m_{\rm{p}}+1],\ldots,h[\ell,L_{\rm{CP}}+lM+m_{\rm{p}}+L-1]]^{\rm{T}}$
for $\ell=0,1,\ldots,L-1$. $\boldsymbol{\eta}_{l}\in\mathbb{C}^{L\times 1}$ is
the AWGN at time slot $l$ affecting the pilot.

BEM-based methods are used for approximating the time variation of the LTV
channels. Depending on the basis functions, different BEM methods such as
complex exponential based (CE-BEM)[14], polynomial based BEM [15], Karhunen-
Loeve (KL) decomposition based BEM [16], are presented in the literature. Due
to its simplicity and high accuracy, in this paper, we use the oversampled
GCE-BEM [11] to approximate the channel time variation in the delay-time
domain. The channel coefficient for the $\ell^{\text{th}}$ path at the time
instant $k$ can be expressed using GCE-BEM as

$h[\ell,k]=\sum_{q=0}^{Q-1}B[k,q]c_{\ell}(q),$ (15)

where $B[k,q]\\!=\\!e^{j2\frac{2\pi(q-\lceil Q/2\rceil)k}{KMN}}$,
$0\\!\leq\\!k\\!\leq\\!MN\\!-\\!1$, $0\\!\leq\\!\ell\\!\leq\\!L\\!-\\!1$ and
$1\leq q\leq Q$. For the accurate approximation of the time variation of the
channel, the oversampling factor and the number of basis functions are chosen
as $K\\!\geq\\!1$ and $Q=\lceil 2K\nu_{\rm{max}}(MNT_{\rm s})\rceil+1$,
respectively, [11]. Using (15), $\mathbf{h}_{l}$ can be expressed in terms of
BEM coefficients as

$\mathbf{h}_{l}=(\mathbf{I}_{L}\otimes\mathbf{B}^{\rm p}_{l})\mathbf{c},$ (16)

where $\mathbf{B}^{\rm p}_{l}=B[k,q]\,\forall k\in\\{L_{\rm{CP}}+lM+m_{\rm
p},L_{\rm{CP}}+lM+m_{\rm p}+1,\ldots,L_{\rm{CP}}+lM+m_{\rm p}+L-1\\}$,
$\mathbf{c}=[\mathbf{c}_{0}^{\rm T},\mathbf{c}_{1}^{\rm
T},\ldots,\mathbf{c}_{L-1}^{\rm T}]^{\rm T}$ and
$\mathbf{c}_{\ell}=[c_{\ell}(0),c_{\ell}(1),\ldots,c_{\ell}(Q-1)]^{\rm T}$.
Inserting, (16) in (14), $\mathbf{r}^{\rm p}$ in (11) can be approximated
using GCE-BEM as

${\mathbf{r}}^{\rm{p}}={\mathbf{\Gamma}}(\varepsilon){\mathbf{G}}{\mathbf{c}}+{\boldsymbol{\eta}},$
(17)

where $\mathbf{G}=[{\mathbf{G}}_{0}^{\rm T},{\mathbf{G}}_{1}^{\rm
T},\ldots,{\mathbf{G}}_{N-1}^{\rm T}]^{\rm T}$ and
${\mathbf{G}}_{l}={\mathbf{A}}_{l}(\mathbf{I}_{L}\otimes\mathbf{B}^{\rm
p}_{l})$ for $l=0,1,\ldots,N-1$.

For a given pair $(\mathbf{c},\varepsilon)$, the vector $\mathbf{r}^{\rm{p}}$
is assumed to have the Gaussian distribution with the mean
$\mathbf{\Gamma}(\varepsilon)\mathbf{G}\mathbf{c}$ and covariance matrix
$\mathbf{\sigma}_{\eta}^{2}\mathbf{I}_{LN}$, [17]. Thus, the joint probability
density function of $\mathbf{r}^{\rm{p}}$, parameterized by
$(\tilde{\mathbf{c}},\tilde{\varepsilon})$, is given by

$f(\mathbf{r}^{\rm{p}};\tilde{\mathbf{c}},\tilde{\varepsilon})=\frac{1}{(\pi\sigma_{\rm{\eta}}^{2})^{NL}}e^{\frac{-1}{\sigma_{\rm{\eta}}^{2}}[\mathbf{r}^{\rm{p}}-\mathbf{\Gamma}(\tilde{\varepsilon})\mathbf{G}\tilde{\mathbf{c}}]^{\rm{H}}[\mathbf{r}^{\rm{p}}-\mathbf{\Gamma}(\tilde{\varepsilon})\mathbf{G}\tilde{\mathbf{c}}]}.$
(18)

Thus, the ML estimates of the BEM coefficient vector and the CFO are obtained
as

$(\hat{\mathbf{c}},\hat{\varepsilon})=\arg\max_{\tilde{\mathbf{c}},\tilde{\varepsilon}}\\{f({\mathbf{r}}^{{\rm
p}};\tilde{\mathbf{c}},\tilde{\varepsilon})\\}.$ (19)

Taking the logarithm and removing the constant terms, the estimation problem
in (19) can be simplified as

$(\hat{\mathbf{c}},\hat{\varepsilon})=\arg\max_{\tilde{\mathbf{c}},\tilde{\varepsilon}}\\{g(\tilde{\mathbf{c}},\tilde{\varepsilon})\\},$
(20)

where
$g(\tilde{\mathbf{c}},\tilde{\varepsilon})=\frac{-1}{\sigma_{\rm{\eta}}^{2}}[\mathbf{r}^{\rm{p}}-\mathbf{\Gamma}(\tilde{\varepsilon})\mathbf{G}\tilde{\mathbf{c}}]^{\rm{H}}[\mathbf{r}^{\rm{p}}-\mathbf{\Gamma}(\tilde{\varepsilon})\mathbf{G}\tilde{\mathbf{c}}]$
is the joint cost function. The maximization problem in (20) can be solved in
two steps. In step 1, we find the $\tilde{\mathbf{c}}$ which maximizes the
joint cost function parameterized by $\tilde{\varepsilon}$. In step 2, the
$\tilde{\mathbf{c}}$ obtained in step 1 is used to find a new cost function
for $\tilde{\varepsilon}$ and we perform a grid search in the vicinity of
coarse CFO estimate to find the fine CFO estimate which maximizes the cost
function for $\tilde{\varepsilon}$. Thus, we fix the $\tilde{\varepsilon}$ and
the $\tilde{\mathbf{c}}$ that maximizes
$g(\tilde{\mathbf{c}},\tilde{\varepsilon})$ can be obtained as

$\tilde{\mathbf{c}}(\tilde{\varepsilon})=(\mathbf{G}^{\rm{H}}\mathbf{G})^{-1}\mathbf{G}^{\rm{H}}\mathbf{\Gamma}^{\rm{H}}(\tilde{\varepsilon})\mathbf{r}^{\rm{p}}.$
(21)

Substituting $\tilde{\mathbf{c}}(\tilde{\varepsilon})$ into
$g(\tilde{\mathbf{c}},\tilde{\varepsilon})$, the cost function for CFO can be
obtained as

$g_{\rm{CFO}}(\tilde{\varepsilon})=(\mathbf{r}^{\rm{p}})^{\rm{H}}\mathbf{\Gamma}(\tilde{\varepsilon})\mathbf{\Lambda}\mathbf{\Gamma}^{\rm{H}}(\tilde{\varepsilon})\mathbf{r}^{\rm{p}},$
(22)

where
$\mathbf{\Lambda}=\mathbf{G}(\mathbf{G}^{\rm{H}}\mathbf{G})^{-1}\mathbf{G}^{\rm{H}}$.
The fine estimate of CFO can then be obtained using a single-dimensional
search centered around the coarse CFO estimate $\hat{\varepsilon}_{\rm c}$ in
(10) as

$\hat{\varepsilon}={\arg}\max_{\tilde{\varepsilon}}\\{g_{\rm{CFO}}(\tilde{\varepsilon})\\}.\vspace{-0.1cm}$
(23)

In addition, channel estimation can also be developed using the estimated CFO.
The BEM coefficients can be estimated after obtaining the CFO estimate as,
$\hat{\mathbf{c}}=(\mathbf{G}^{\rm{H}}\mathbf{G})^{-1}\mathbf{G}^{\rm{H}}\mathbf{\Gamma}^{\rm{H}}(\hat{\varepsilon})\mathbf{r}^{\rm{p}}$,
and finally the complete LTV channel in delay-time can be estimated using
(15).

Figure 5: TO estimation comparison for the impulse pilot and PCP where
$M\\!\\!=\\!\\!128$ and $N\\!\\!=\\!\\!32$.

Regarding complexity, the periodic structure of the pilot in the delay-time
domain can reduce the complexity of the maximum-likelihood estimator. In other
words, the existing repetition of every $L$ pilot sample leads to a reduction
of the complexity of the estimator by a factor of $L$. Additionally,
$\mathbf{\Lambda}$ is a symmetric matrix that provides the opportunity to only
calculate half of the cost function, which reduces the complexity by a factor
of 2. Thus, the cost function in (22) can be calculated in the form

$g_{\rm{CFO}}(\tilde{\varepsilon})=-\beta[0]+2{\rm{Re}}\\{\sum_{m=0}^{N-1}\beta[m]e^{\frac{j2\pi
m\tilde{\varepsilon}}{N}}\\},\vspace{-0.2cm}$ (24)

and

$\beta[m]=\\!\\!\sum_{k=0}^{NL-1-mL}\\!\\!\mathbf{\Lambda}[(\\!(k+mL)\\!)_{NL},k]{r^{\rm{p}}}^{*}[(\\!(k+mL)\\!)_{NL}]r^{\rm{p}}[k],$
(25)

where $\mathbf{\Lambda}[i,j]$ and $r^{\rm{p}}[i]$ are the $[i,j]^{\rm{th}}$
and $i^{\rm{th}}$ entries of the $\mathbf{\Lambda}$ and $\mathbf{r}^{\rm{p}}$,
respectively. Calculating the coast function
$g_{\rm{CFO}}(\tilde{\varepsilon})$ using (22) requires
$\mathcal{O}(N^{2}L^{2})$ complex multiplications. However, it can be reduced
to $\mathcal{O}(\frac{N^{2}L}{2})$ by using (24) and (25).

##  V Simulation Results

Figure 6: TO estimation comparison vs. normalized maximum Doppler spread for
PCP at SNR=20 dB.

In this section, we numerically analyze the performance of both the proposed
estimation techniques. The reduced-OTFS system with 16-QAM symbols in this
analysis is formed by $M=64,128,256$ and $N=64,32,16$ delay and Doppler bins,
respectively [18]. We use the extended vehicular A (EVA) channel model with
length $L=21$, [19], the bandwidth of $8.25$ MHz and the delay-Doppler
resolution $(\Delta\tau,\Delta\nu)=(121.21\,\rm{nsec},2.01\,\rm{kHz})$. The
power of the PCP is set to 40 dB and the pilot is inserted at the center of
the Doppler axis within delay bins, $m_{\rm{p}}-L$ to $m_{\rm{p}}+L-1$, [9].
To model the channel with GCE-BEM, we choose the oversampling factor $K=4$ and
the order of BEM basis functions $Q=1,3,6,8$ for different normalized maximum
Doppler spreads of $\nu_{\rm{max}}=0,0.66,1.64,2.73$ kHz, respectively [11].
Throughout our simulations, the normalized TO and CFO values are randomly
generated from a uniform distribution in the range
$[-\frac{MN}{2},\frac{MN}{2})$ and $[-\frac{N-\nu_{\rm
max}T}{2},\frac{N-\nu_{\rm max}T}{2})$, respectively, where $T=MNT_{\rm{s}}$
is the total time duration of an OTFS block.

In Fig. 5, we compare the performance of our proposed TO estimation technique
using PCP with the impulse pilot-assisted method proposed in [7]. We analyze
the estimation error mean and variance as a function of signal-to-noise ratio
(SNR), for the normalized Doppler spread of
$\nu_{\rm{max}}T\\!\approx\\!1.36$. The PDP of the channel leads to a small
bias in the proposed estimation technique. Although we removed
$\lfloor\mu_{\rm{h}}\rfloor$ from the estimated TO in (5), the existing bias
in Fig. 5 originates from the fractional part of the mean delay in the
channel. This figure also shows that, for the same pilot power level, the
proposed technique outperforms the technique in [7]. Fig. 6 shows the
performance of the proposed TO estimator as a function of normalized Doppler
spread, for different combinations of $M$ and $N$, and a fixed $MN=4096$. It
can be observed that as the normalized Doppler spread increases, estimation
accuracy also increases. This improvement originates from the diversity
provided by the time-selectivity of the channel.

To analyze the performance of our proposed CFO estimation technique, we assume
perfect knowledge of TO. In Fig. 7, we evaluate the MSE performance of our
proposed CFO estimation technique as a function of SNR and compare it with the
CFO estimation technique proposed in [7]. It can be observed that the CFO
estimation proposed in this paper gives an order of magnitude better
estimation accuracy than the method using impulse pilot in [7]. In Fig. 8, we
study the performance of our proposed CFO estimator as a function of Doppler
spread. Furthermore, our results show that the MSE performance degrades as the
Doppler spread or the number of delay bins increases. Higher $M$ leads to a
channel with more time variation within a column of the OTFS block which is
the main reason for CFO estimation degradation.

##  VI Conclusion

Figure 7: CFO estimation comparison for the impulse pilot and PCP where
$M\\!\\!=\\!\\!128$ and $N\\!\\!=\\!\\!32$.

In this paper, we proposed TO and CFO estimation techniques for OTFS using
PCP. We exploit the periodicity property of PCP in the time domain to develop
the correlation-based metrics for TO and CFO estimation. Furthermore, the TO
estimation accuracy is improved using diversity offered by the constant
amplitude PCP in different delay bins. To improve the accuracy of the CFO
estimate we approximated the time variation of the channel using GCE-BEM and
developed an ML estimator. Additionally, we also developed low-complexity
implementation strategies for the proposed techniques. Since we use the same
practical pilot used for channel estimation, the proposed method does not
impart additional overhead for synchronization. Hence the proposed
synchronization methods are highly apt for practical OTFS systems in high
mobility scenarios in the envisioned 6G systems.

Figure 8: CFO estimation comparison vs. normalized maximum Doppler spread for
PCP at SNR=20 dB.

## References

  * [1] R. Hadani, S. Rakib, M. Tsatsanis, A. Monk, A. J. Goldsmith, A. F. Molisch, and R. Calderbank, “Orthogonal time frequency space modulation,” in _IEEE Wireless Commun. and Netw. Conf._ , 2017, pp. 1–6.
  * [2] A. Farhang, A. RezazadehReyhani, L. E. Doyle, and B. Farhang-Boroujeny, “Low complexity modem structure for OFDM-based orthogonal time frequency space modulation,” _IEEE Wireless Commun. Lett._ , vol. 7, no. 3, pp. 344–347, 2018.
  * [3] M. Morelli, C.-C. J. Kuo, and M.-O. Pun, “Synchronization techniques for orthogonal frequency division multiple access (OFDMA): A tutorial review,” _Proc. of the IEEE_ , vol. 95, no. 7, pp. 1394–1427, 2007.
  * [4] A. K. Sinha, S. K. Mohammed, P. Raviteja, Y. Hong, and E. Viterbo, “OTFS based random access preamble transmission for high mobility scenarios,” _IEEE Trans. on Veh. Technol._ , vol. 69, no. 12, pp. 15 078–15 094, 2020\.
  * [5] M. S. Khan, Y. J. Kim, Q. Sultan, J. Joung, and Y. S. Cho, “Downlink synchronization for OTFS-based cellular systems in high Doppler environments,” _IEEE Access_ , vol. 9, pp. 73 575–73 589, 2021.
  * [6] S. S. Das, V. Rangamgari, S. Tiwari, and S. C. Mondal, “Time domain channel estimation and equalization of CP-OTFS under multiple fractional Dopplers and residual synchronization errors,” _IEEE Access_ , vol. 9, pp. 10 561–10 576, 2021.
  * [7] M. Bayat and A. Farhang, “Time and frequency synchronization for OTFS,” _IEEE Wireless Commun. Lett._ , vol. 11, no. 12, pp. 2670–2674, 2022.
  * [8] P. Raviteja, K. T. Phan, Y. Hong, and E. Viterbo, “Embedded delay-Doppler channel estimation for orthogonal time frequency space modulation,” in _IEEE Veh. Technol. Conf._ , 2018, pp. 1–5.
  * [9] P. S. Sanoopkumar and A. Farhang, “A practical pilot for channel estimation of OTFS,” in _IEEE Commun. Conf._ , 2023.
  * [10] S. Gao and J. Zheng, “Peak-to-average power ratio reduction in pilot-embedded OTFS modulation through iterative clipping and filtering,” _IEEE Commun. Lett._ , vol. 24, no. 9, pp. 2055–2059, 2020.
  * [11] J. K. Tugnait, S. He, and H. Kim, “Doubly selective channel estimation using exponential basis models and subblock tracking,” _IEEE Trans. on Signal Process._ , vol. 58, no. 3, pp. 1275–1289, 2010.
  * [12] A. F. Molisch, _Wireless communications_ , 2011, pp. 793–816.
  * [13] C. Mensing, S. Plass, and A. Dammann, “Synchronization algorithms for positioning with OFDM communications signals,” in _Workshop on Positioning, Navigation, and Commun._ , 2007, pp. 205–210.
  * [14] F. Qu and L. Yang, “On the estimation of doubly-selective fading channels,” in _Annu. Conf. on Info. Sci. and Syst._ , 2008, pp. 1279–1284.
  * [15] P. Muneer and S. M. Sameer, “Joint ML estimation of CFO and channel, and a low complexity turbo equalization technique for high mobility OFDMA uplinks,” _IEEE Trans. on Wireless Commun._ , vol. 14, no. 7, pp. 3642–3654, 2015.
  * [16] Q. Zhang, X. Zhao, Y. Zeng, and S. Song, “Efficient estimation of fast fading OFDM channels,” in _IEEE Int. Conf. on Commun._ , vol. 10, 2006, pp. 4601–4605.
  * [17] M. Morelli and U. Mengali, “Carrier-frequency estimation for transmissions over selective channels,” _IEEE Trans. on Commun._ , vol. 48, no. 9, pp. 1580–1589, 2000.
  * [18] P. Raviteja, Y. Hong, E. Viterbo, and E. Biglieri, “Practical pulse-shaping waveforms for reduced-cyclic-prefix OTFS,” _IEEE Trans. on Veh. Technol._ , vol. 68, no. 1, pp. 957–961, 2019.
  * [19] 3GPP, “Evolved universal terrestrial radio access (E-UTRA); base station (BS) radio transmission and reception,” 3rd Generation Partnership Project (3GPP), TS 36.104 V15.3.0, 2018.


242022166699

# Constant Congestion Brambles††thanks:  The research leading to the results
presented in this paper was partially carried out during the Parameterized
Algorithms Retreat of the University of Warsaw, PARUW 2020, held in Krynica-
Zdrój in February 2020. This research is part of projects that have received
funding from the European Research Council (ERC) under the European Union’s
Horizon 2020 research and innovation programme Grant Agreements 648527
DISTRUCT (Meike Hatzel) and 714704 CUTACOMBS (Marcin Pilipczuk, Manuel Sorge).

Meike Hatzel1  Marcin Pilipczuk2  Paweł Komosa2  Manuel Sorge2  TU Berlin,
Germany
University of Warsaw, Poland

(2020-08-06; 2021-10-12; 2022-02-09)

###### Abstract

A _bramble_ in an undirected graph $G$ is a family of connected subgraphs of
$G$ such that for every two subgraphs $H_{1}$ and $H_{2}$ in the bramble
either $V(H_{1})\cap V(H_{2})\neq\emptyset$ or there is an edge of $G$ with
one endpoint in $V(H_{1})$ and the second endpoint in $V(H_{2})$. The _order_
of the bramble is the minimum size of a vertex set that intersects all
elements of a bramble.

Brambles are objects dual to treewidth: As shown by Seymour and Thomas, the
maximum order of a bramble in an undirected graph $G$ equals one plus the
treewidth of $G$. However, as shown by Grohe and Marx, brambles of high order
may necessarily be of exponential size: In a constant-degree $n$-vertex
expander a bramble of order $\Omega(n^{1/2+\delta})$ requires size exponential
in $\Omega(n^{2\delta})$ for any fixed $\delta\in(0,\frac{1}{2}]$. On the
other hand, the combination of results of Grohe and Marx and Chekuri and
Chuzhoy shows that a graph of treewidth $k$ admits a bramble of order
$\widetilde{\Omega}(k^{1/2})$ and size $\widetilde{\mathcal{O}}(k^{3/2})$.
($\widetilde{\Omega}$ and $\widetilde{\mathcal{O}}$ hide polylogarithmic
divisors and factors, respectively.)

In this note, we first sharpen the second bound by proving that every graph
$G$ of treewidth at least $k$ contains a bramble of order
$\widetilde{\Omega}(k^{1/2})$ and congestion $2$, i.e., every vertex of $G$ is
contained in at most two elements of the bramble (thus the bramble is of size
linear in its order). Second, we provide a tight upper bound for the lower
bound of Grohe and Marx: For every $\delta\in(0,\frac{1}{2}]$, every graph $G$
of treewidth at least $k$ contains a bramble of order
$\widetilde{\Omega}(k^{1/2+\delta})$ and size
$2^{\widetilde{\mathcal{O}}(k^{2\delta})}$.

###### keywords:

bramble, constant congestion

##  1 Introduction

_Treewidth_ is a well-known measure of how tree-like a graph is: For example,
a graph is a forest if and only if it has treewidth at most $1$, while an
$n$-vertex clique has treewidth $n-1$. The notion of treewidth, coined by the
Graph Minors project (Robertson and Seymour, 1984), has found many
applications both in graph theory and algorithm design. (The definition of
tree decompositions and treewidth can be found in section 2.)

The notion of a _bramble_ is an elegant and tight obstacle to treewidth. Given
an undirected graph $G$, a bramble $\mathcal{B}$ is a family of connected
subgraphs of $G$ such that for every $H_{1},H_{2}\in\mathcal{B}$, either
$V(H_{1})\cap V(H_{2})\neq\emptyset$ or there is an edge of $G$ with one
endpoint in $V(H_{1})$ and one endpoint in $V(H_{2})$. The measure of
complexity of a bramble is its order: a _hitting set_ of a bramble
$\mathcal{B}$ is a set $X\subseteq V(G)$ such that $X\cap V(H)\neq\emptyset$
for every $H\in\mathcal{B}$, and the _order_ of a bramble is the minimum size
of such a hitting set. A simple argument shows that for every bramble
$\mathcal{B}$ in $G$, every tree decomposition of $G$ needs to contain a bag
hitting $\mathcal{B}$, thus the treewidth of $G$ plus one bounds the maximum
order of a bramble in $G$. The beauty of the bramble definition lies in the
(highly nontrivial) fact that the above relation is tight: There is always a
bramble in $G$ of order equal to the treewidth of $G$ plus one (Seymour and
Thomas, 1993).

However, while treewidth has found numerous applications in algorithm design,
the use of brambles in algorithms is scarce. The main reason for that lies in
the result of Grohe and Marx (2009): While a bramble provides a dual object
tightly related to treewidth, it can be of size exponential in the graph. In
particular, for every $\delta\in(0,1]$, in any $n$-vertex constant-degree
expander the treewidth is $\Omega(n)$, but any bramble of order
$\Omega(n^{1/2+\delta})$ has size111Grohe and Marx (2009) formally only proved
a $\Omega(n^{\delta})$ lower bound, but a slightly more careful analysis of
their calculations shows a lower bound of $\Omega(n^{2\delta})$ in the
exponent. exponential in $\Omega(n^{2\delta})$. Hence, to certify that the
treewidth is larger than $n^{1/2+\delta}$, one is required to look at
exponential-size brambles.

On the positive side, Grohe and Marx (2009) proved that every $n$-vertex graph
of treewidth $k$ admits a bramble of order $\Omega(\sqrt{k}/\log^{2}k)$ and
size $\mathcal{O}(k^{3/2}\log n)$. Combining this with the result of Chekuri
and Chuzhoy (2015) stating that every graph $G$ of treewidth $k$ admits a
topological minor of maximum degree $3$, $\mathcal{O}(k^{4})$ vertices, and
treewidth at least $k/p(\log k)$ for some polynomial $p$, one obtains that a
graph of treewidth $k$ admits a bramble of order
$\widetilde{\Omega}(\sqrt{k})$ and size $\widetilde{\mathcal{O}}(k^{3/2})$.
Here, $\widetilde{\Omega}(\cdot)$ and $\widetilde{\mathcal{O}}(\cdot)$ omit
polylogarithmic divisors and factors, respectively.

In this note, we provide the following two strengthenings and tightenings of
the results of Grohe and Marx.

First, we improve the positive result with respect to the bramble size to
brambles of congestion $2$. A bramble $\mathcal{B}$ in a graph $G$ is of
_congestion_ $c$ if every vertex of $G$ is in at most $c$ elements of
$\mathcal{B}$. Clearly, the order of a bramble $\mathcal{B}$ of congestion $c$
is at least $|\mathcal{B}|/c$, so, in brambles of constant congestion, the
size and order are within a constant multiplicative factor of each other. A
bramble of congestion $1$ implies a clique minor of the same size. Thus large
grids show that it is possible to have arbitrarily large treewidth without
having a bramble of congestion $1$ and size $5$. In contrast, our
strengthening of the results of Grohe and Marx (2009) shows that there is
always a bramble of order $\widetilde{\Omega}(\sqrt{k})$ and congestion $2$.

######  Theorem 1.1.

There exists a polynomial $p(\cdot)$ such that for every positive integer $k$
and every graph $G$ of treewidth at least $k$ the graph $G$ contains a bramble
of order at least $\sqrt{k}/p(\log k)$ and congestion $2$.

On a high level, the proof of theorem 1.1 follows similar lines as the
construction of treewidth sparsifiers by Chekuri and Chuzhoy (2015). A graph
of the required treewidth $k$ contains a large so-called strong path-of-sets
system, as shown by Chekuri and Chuzhoy (2016). From such a system we can
build an auxiliary graph whose vertices represent long paths which can be
arbitrarily interlinked by pairwise disjoint paths. On the vertex set of this
auxiliary graph, we can play what is called the cut-matching game. By a result
from Khandekar et al. (2009) on this game there is a strategy to construct an
expander subgraph of the auxiliary graph within
$\mathcal{O}(\left(\log{k}\right)^{2})$ rounds of adding perfect matchings. We
then transfer this back to the path-of-sets system by embedding each round in
a different set to obtain the expander as something similar to a minor (models
of vertices might intersect, but only twice). A large enough expander contains
a large clique as a minor; this was shown by Kawarabayashi and Reed (2010).
The minor models of the clique vertices then provide the desired bramble.

Second, we provide a tight matching bound (up to polylogarithmic factors) to
the Grohe-Marx lower bound on the size of a bramble.

######  Theorem 1.2.

There exists a polynomial $p(\cdot)$ such that for every constant
$\delta\in(0,0.5]$ and every integer $k$, every graph $G$ of treewidth at
least $k$ contains a bramble of order at least $k^{0.5+\delta}/p(\log k)$ and
with at most $2^{k^{2\delta}\cdot p(\log k)}$ elements.

Here, the construction follows the general ideas of the construction of Grohe
and Marx (2009) of the bramble of order $\Omega(\sqrt{k}/\log^{2}k)$ and size
$\mathcal{O}(k^{3/2}\log n)$, but with different parameters and more elaborate
probabilistic analysis.

After introducing notation and toolbox from previous works in section 2, we
prove theorem 1.1 in section 3 and theorem 1.2 in section 4.

##  2 Preliminaries

###  2.1 Notation and basic definitions

For each $n\in\mathbb{N}$ we use $[n]$ to denote $\\{1,\ldots,n\\}$. Let $G$
be a graph. A graph $H$ is a _minor_ of $G$ if it can be obtained from $G$ by
a series of edge deletions, vertex deletions, and edge contractions. We can
also consider a minor to be a map
$f:\mathchoice{V\\!\left(H\right)}{V\\!\left(H\right)}{V\left(H\right)}{V\left(H\right)}\to
2^{\mathchoice{V\\!\left(G\right)}{V\\!\left(G\right)}{V\left(G\right)}{V\left(G\right)}}$
such that
$\mathchoice{f\\!\left(v\right)}{f\\!\left(v\right)}{f\left(v\right)}{f\left(v\right)}$
is connected for all
$v\in\mathchoice{V\\!\left(H\right)}{V\\!\left(H\right)}{V\left(H\right)}{V\left(H\right)}$,
$\mathchoice{f\\!\left(u\right)}{f\\!\left(u\right)}{f\left(u\right)}{f\left(u\right)}\cap\mathchoice{f\\!\left(v\right)}{f\\!\left(v\right)}{f\left(v\right)}{f\left(v\right)}=\emptyset$
for $u\neq v$ and if
$uv\in\mathchoice{E\\!\left(H\right)}{E\\!\left(H\right)}{E\left(H\right)}{E\left(H\right)}$
then there are
$u^{\prime}\in\mathchoice{f\\!\left(u\right)}{f\\!\left(u\right)}{f\left(u\right)}{f\left(u\right)}$
and
$v^{\prime}\in\mathchoice{f\\!\left(v\right)}{f\\!\left(v\right)}{f\left(v\right)}{f\left(v\right)}$
with
$u^{\prime}v^{\prime}\in\mathchoice{E\\!\left(G\right)}{E\\!\left(G\right)}{E\left(G\right)}{E\left(G\right)}$.
The map $f$ is called a _model_ of $H$ in $G$ and we refer to
$\mathchoice{f\\!\left(v\right)}{f\\!\left(v\right)}{f\left(v\right)}{f\left(v\right)}$
as the _model of vertex $v$_ for all
$v\in\mathchoice{V\\!\left(H\right)}{V\\!\left(H\right)}{V\left(H\right)}{V\left(H\right)}$.
A _subdivision_ of a graph $H$ is a graph that can be obtained from $H$ by a
series of edge subdivisions, that is, replacing an edge $uv$ by a new vertex
$w$ and two new edges $uw$ and $wv$. A graph $H$ is a _topological minor_ of
$G$ if a subdivision of $H$ is isomorphic to a subgraph of $G$.

Though we avoid working with the definition directly, we also define the
treewidth of $G$. A _tree-decomposition_ of $G$ is a tuple
$\left(T,\beta\right)$ where $T$ is a tree and
$\beta:\mathchoice{V\\!\left(T\right)}{V\\!\left(T\right)}{V\left(T\right)}{V\left(T\right)}\to
2^{\mathchoice{V\\!\left(G\right)}{V\\!\left(G\right)}{V\left(G\right)}{V\left(G\right)}}$
a map of the tree vertices to subsets of vertices in $G$ called _bags_. The
map $\beta$ has to have the following properties:

  1. 1.

Every vertex
$v\in\mathchoice{V\\!\left(G\right)}{V\\!\left(G\right)}{V\left(G\right)}{V\left(G\right)}$
occurs in some bag.

  2. 2.

If
$v\in\mathchoice{\beta\\!\left(t\right)}{\beta\\!\left(t\right)}{\beta\left(t\right)}{\beta\left(t\right)}\cap\mathchoice{\beta\\!\left(t^{\prime}\right)}{\beta\\!\left(t^{\prime}\right)}{\beta\left(t^{\prime}\right)}{\beta\left(t^{\prime}\right)}$
for $t\neq t^{\prime}$, then
$v\in\mathchoice{\beta\\!\left(t^{\prime\prime}\right)}{\beta\\!\left(t^{\prime\prime}\right)}{\beta\left(t^{\prime\prime}\right)}{\beta\left(t^{\prime\prime}\right)}$
for all $t^{\prime\prime}$ lying on the unique path between $t$ and
$t^{\prime}$ in $T$.

  3. 3.

For every
$uv\in\mathchoice{E\\!\left(G\right)}{E\\!\left(G\right)}{E\left(G\right)}{E\left(G\right)}$
there is a
$t\in\mathchoice{V\\!\left(T\right)}{V\\!\left(T\right)}{V\left(T\right)}{V\left(T\right)}$
such that
$u,v\in\mathchoice{\beta\\!\left(t\right)}{\beta\\!\left(t\right)}{\beta\left(t\right)}{\beta\left(t\right)}$.

The _width_ of $\left(T,\beta\right)$ is defined as
$\max\\{\left|\mathchoice{\beta\\!\left(t\right)}{\beta\\!\left(t\right)}{\beta\left(t\right)}{\beta\left(t\right)}\right|-1\mid
t\in\mathchoice{V\\!\left(T\right)}{V\\!\left(T\right)}{V\left(T\right)}{V\left(T\right)}\\}$
and the _treewidth_ of $G$ is defined to be the minimum width of a tree-
decomposition of $G$.

A _linkage_ $\mathcal{L}$ in $G$ is a set of vertex-disjoint paths. We say it
is an $A$-$B$-linkage for
$A,B\subseteq\mathchoice{V\\!\left(G\right)}{V\\!\left(G\right)}{V\left(G\right)}{V\left(G\right)}$,
if all its paths start in $A$ and end in $B$, are otherwise disjoint from $A$
and $B$ and $\left|\mathcal{L}\right|=\left|A\right|=\left|B\right|$.

######  Definition 2.1 (well-linked).

A set of vertices $X$ in a graph $G$ is _well-linked_ if for all $A,B\subseteq
X$ with $\left|A\right|=\left|B\right|$ there is an $A$-$B$-linkage in
$G-\left(X\setminus\left(A\cup B\right)\right)$.

######  Definition 2.2 (bramble).

A _bramble_ $\mathcal{B}$ in $G$ is a collection of connected subgraphs
$B_{1},\dots,B_{s}$ such that for any two elements $B_{i},B_{j}$ we have
$\mathchoice{V\\!\left(B_{i}\right)}{V\\!\left(B_{i}\right)}{V\left(B_{i}\right)}{V\left(B_{i}\right)}\cap\mathchoice{V\\!\left(B_{j}\right)}{V\\!\left(B_{j}\right)}{V\left(B_{j}\right)}{V\left(B_{j}\right)}\neq\emptyset$
or there exists
$e=uv\in\mathchoice{E\\!\left(G\right)}{E\\!\left(G\right)}{E\left(G\right)}{E\left(G\right)}$
with
$u\in\mathchoice{V\\!\left(B_{i}\right)}{V\\!\left(B_{i}\right)}{V\left(B_{i}\right)}{V\left(B_{i}\right)}$
and
$v\in\mathchoice{V\\!\left(B_{j}\right)}{V\\!\left(B_{j}\right)}{V\left(B_{j}\right)}{V\left(B_{j}\right)}$.
The bramble $\mathcal{B}$ is of _size_ $s$. A _hitting set_ of $\mathcal{B}$
is a vertex subset
$H\subseteq\mathchoice{V\\!\left(G\right)}{V\\!\left(G\right)}{V\left(G\right)}{V\left(G\right)}$
such that for all $i\in[s]$ we have
$H\cap\mathchoice{V\\!\left(B_{i}\right)}{V\\!\left(B_{i}\right)}{V\left(B_{i}\right)}{V\left(B_{i}\right)}\neq\emptyset$.
The _order_ of $\mathcal{B}$ is the minimum size of a hitting set of
$\mathcal{B}$, i.e. $\min\\{\left|H\right|\mid
H\subseteq\mathchoice{V\\!\left(G\right)}{V\\!\left(G\right)}{V\left(G\right)}{V\left(G\right)}\text{
such that }\forall i\in[s]\colon H\cap B_{i}\neq\emptyset\\}$. The
_congestion_ of bramble $\mathcal{B}$ is the maximum, taken over all vertices
$v\in V(G)$, of the number of elements that contain $v$, i.e.
$\max_{v\in\mathchoice{V\\!\left(G\right)}{V\\!\left(G\right)}{V\left(G\right)}{V\left(G\right)}}\left|\\{B_{i}\mid
v\in\mathchoice{V\\!\left(B_{i}\right)}{V\\!\left(B_{i}\right)}{V\left(B_{i}\right)}{V\left(B_{i}\right)}\\}\right|$.

######  Definition 2.3 (expander).

A graph $G$ is an _$\alpha$ -expander_ if for every partition
$\left(S,S^{\prime}\right)$ of the vertex set with $S,S^{\prime}\neq\emptyset$
we have

$\displaystyle\frac{\left|\mathchoice{E\\!\left(S,S^{\prime}\right)}{E\\!\left(S,S^{\prime}\right)}{E\left(S,S^{\prime}\right)}{E\left(S,S^{\prime}\right)}\right|}{\min\\{\left|S\right|,\left|S^{\prime}\right|\\}}\geq\alpha,$

where
$\mathchoice{E\\!\left(S,S^{\prime}\right)}{E\\!\left(S,S^{\prime}\right)}{E\left(S,S^{\prime}\right)}{E\left(S,S^{\prime}\right)}$
is the set of edges in $G$ that have one endpoint in $S$ and the other in
$S^{\prime}$.

###  2.2 Treewidth sparsifiers

We use the following treewidth sparsification result of Chekuri and Chuzhoy
(2015).

######  Theorem 2.3 (Chekuri and Chuzhoy (2015), Theorem 1.1).

There exists a polynomial $p(\cdot)$ such that for every integer $k$, every
graph $G$ of treewidth at least $k$ contains a topological minor with (i)
$\mathcal{O}(k^{4})$ vertices, (ii) maximum degree $3$, and (iii) treewidth at
least $k/p(\log k)$.

Theorem 2.1 asserts that, for the cost of some polylogarithmic factors on the
treewidth we can assume that the considered graph has maximum degree $3$ and
size polynomial in the treewidth when deriving a bramble from a given graph.

###  2.3 The cut-matching game

The _cut-matching game_ is a two-player game. The two players are called the
_cut_ player and the _matching_ player. They play in turns on an even-size set
$V$ of vertices, building a (multi)graph $H$ with $V(H)=V$. Initially the
graph $H$ has no edges.

In each turn, the cut player chooses a partition $\left(A,B\right)$ of $V$
into two equal-size sets. Then the matching player chooses a matching $M$
between $A$ and $B$. The matching is added to $H$ (with multiplicities, i.e.,
if one of the edges of $M$ is already present in $H$, an additional copy is
added, increasing the multiplicity). If the graph $H$ is an
$\mathchoice{\Omega\\!\left(1\right)}{\Omega\\!\left(1\right)}{\Omega\left(1\right)}{\Omega\left(1\right)}$-expander
at the end of a round the game ends. If the game ends we say it _yields_ the
new graph $H$. We can consider the graph $H$ as _consisting_ of the matchings
$M_{1},\dots,M_{r}$ chosen throughout the $r$ rounds of the game.

######  Theorem 2.3 (Khandekar et al. (2009), Lemma 3.1 and 3.2).

There is a strategy for the cut player that, with high probability, yields an
$\mathchoice{\Omega\\!\left(1\right)}{\Omega\\!\left(1\right)}{\Omega\left(1\right)}{\Omega\left(1\right)}$-expander
after $\mathcal{O}(\left(\log h\right)^{2})$ rounds, where $h=|V|$.

A typical application for the cut-matching game is as follows. Let $G$ be a
graph and let $X\subseteq V(G)$ be a well-linked set of even size $h=|X|$.
Consider a cut-matching game played on $V=X$. The matching player is simulated
by a flow computation: For every partition of $X$ into $A$ and $B$, the graph
$G$ contains an $A$-$B$-linkage $\mathcal{P}$ by well-linkedness of $X$. The
returned matching of the matching player corresponds to how the paths of
$\mathcal{P}$ match the vertices of $X$. Then, if the cut player plays the
strategy of Khandekar et al. (2009), after $\mathcal{O}((\log h)^{2})$ rounds
it obtains an expander; note that this expander has maximum degree
$\mathcal{O}((\log h)^{2})$ and can be embedded (with congestion) into $G$ as
a union of $\mathcal{O}((\log h)^{2})$ linkages.

The concept of path-of-sets systems introduced in the following subsection can
be used to ensure that the linkages are disjoint and thus, to the price of
constant congestion elsewhere, allow us to ged rid of the congestion caused
when embedding the expander into $G$.

###  2.4 Path-of-sets systems

The following definition was introduced and used by Chekuri and Chuzhoy (2016)
to prove a polynomial bound for the excluded-grid theorem. We use it here in
conjunction with a cut-matching game to obtain an expander graph.

######  Definition 2.4 (path-of-sets system).

Let $G$ be a graph. A _path-of-sets system_ of _width_ $h$ and _length_ $r$
(also called _$\left(h,r\right)$ -path-of-sets system_) in $G$ is a tuple
$\left(\mathcal{S},\mathcal{A},\mathcal{B},\mathcal{P}\right)$ consisting of
three sequences of pairwise disjoint vertex sets
$\mathcal{S}=S_{1},\dots,S_{r}$, $\mathcal{A}=A_{1},\dots,A_{r}$ and
$\mathcal{B}=B_{1},\dots,B_{r}$, and a sequence of linkages
$\mathcal{P}=\mathcal{P}_{1},\dots,\mathcal{P}_{r-1}$ whose paths are pairwise
disjoint such that

  1. 1.

for all $i\in[r]$ the graph
$\mathchoice{G\\!\left[S_{i}\right]}{G\\!\left[S_{i}\right]}{G\left[S_{i}\right]}{G\left[S_{i}\right]}$
is connected,

  2. 2.

for all $i\in[r]$ we have $A_{i}\subseteq S_{i}$, $B_{i}\subseteq S_{i}$,
$\left|A_{i}\right|=\left|B_{i}\right|=h$, and $A_{i}\cap B_{i}=\emptyset$, as
well as for all $A\subseteq A_{i}$ and $B\subseteq B_{i}$ of same size there
is an $A$-$B$-linkage within
$\mathchoice{G\\!\left[S_{i}\right]}{G\\!\left[S_{i}\right]}{G\left[S_{i}\right]}{G\left[S_{i}\right]}$,

  3. 3.

for all $i\in[r-1]$ we have $\mathcal{P}_{i}$ consists of $h$ disjoint
$B_{i}$-$A_{i+1}$-paths that are internally disjoint to any set of
$\mathcal{S}$.

A path-of-sets system is called _strong_ , if for all $i\in[r]$ we have that
$A_{i}$ is well-linked in $G[S_{i}]$ and so is $B_{i}$.

We will indeed only use strong path-of-sets systems.

Chekuri and Chuzhoy proved that every graph with large enough treewidth
contains a path-of-sets system of large length and width.

######  Theorem 2.4 (Chekuri and Chuzhoy (2016), Theorem 3.5).

There exist two constants $c_{1},c_{2}>0$ and a polynomial-time randomised
algorithm that, given a graph $G$ of treewidth $k$ and integers $w,\ell>2$,
such that $k/\left(\log k\right)^{c_{1}}>c_{2}w\ell^{48}$, with high
probability returns a strong path-of-sets system of width $w$ and length
$\ell$ in $G$.

Note that the above implies that such a path-of-sets system always exists,
because, by the statement of the theorem, there is a non-zero probability that
the algorithm successfully produces such a system.

######  Corollary 2.5.

There exists a polynomial $p(\cdot,\cdot)$ with positive coefficients and a
function
$\mathchoice{f\\!\left(h,r\right)}{f\\!\left(h,r\right)}{f\left(h,r\right)}{f\left(h,r\right)}=hr^{48}p(\log
h,\log r)$ such that, for all integers $h,r\geq 2$, every graph $G$ of
treewidth at least
$\mathchoice{f\\!\left(h,r\right)}{f\\!\left(h,r\right)}{f\left(h,r\right)}{f\left(h,r\right)}$
contains a strong path-of-sets system of width $h$ and length $r$.

######  Proof 2.6.

Let $c_{1}$, $c_{2}$ be the constants from theorem 2.3 and let
$c^{\prime}_{1}=\lceil c_{1}\rceil$. Pick
$p(x,y)=c_{2}((48+2c^{\prime}_{1})(\log(c_{3})+x+y))^{c^{\prime}_{1}}$, where
we specify $c_{3}>1$ later. Denote $f=f(h,r)$ and take a graph $G$ of
treewidth at least $f$. We claim that we may apply the algorithm of theorem
2.3 to $G$, with $w=h$ and $\ell=r$. It suffices to show that

$\frac{f}{\left(\log f\right)^{c_{1}}}>c_{2}hr^{48}\text{.}$ (1)

Since $f=hr^{48}p(\log h,\log r)$, we have $c_{2}f/p(\log h,\log
r)=c_{2}hr^{48}$. Thus,

$p(\log h,\log r)/c_{2}>(\log f)^{c_{1}}$ (2)

implies equation 1. To see equation 2, observe that the following from bottom
to top imply equation 2

$\displaystyle((48+2c^{\prime}_{1})\log(c_{3}hr))^{c^{\prime}_{1}}$
$\displaystyle>(\log f)^{c_{1}}$
$\displaystyle(48+2c^{\prime}_{1})\log(c_{3}hr)$ $\displaystyle>\log f$
$\displaystyle(c_{3}hr)^{48}\cdot(c_{3}hr)^{2c^{\prime}_{1}}$
$\displaystyle>hr^{48}c_{2}((48+2c^{\prime}_{1})(\log(c_{3})+\log h+\log
r))^{c^{\prime}_{1}}$ $\displaystyle(c_{3}hr)^{2c^{\prime}_{1}}$
$\displaystyle>c_{2}((48+2c^{\prime}_{1})(\log(c_{3}hr)))^{c^{\prime}_{1}}$
$\displaystyle\frac{(c_{3}hr)^{2}}{\log(c_{3}hr)}$
$\displaystyle>(c_{2})^{1/c^{\prime}_{1}}(48+2c^{\prime}_{1})$ $\displaystyle
c_{3}hr$
$\displaystyle>(c_{2})^{1/c^{\prime}_{1}}(48+2c^{\prime}_{1})\text{.}$

Thus, equation 1 holds for an appropriate choice of $c_{3}$, as required.

This structure is used in the proof of theorem 1.1 to combine it with the cut-
matching game defined above. Every set $S_{i}$ is used to embed one of the
matchings chosen by the matching player, this way none of them intersect in
$G$. This of course brings up the new problem of them not being on the same
vertex set, which can be taken care of with the vertices being represented by
paths instead of single vertices. The whole construction then only has
congestion two, as paths and linkages can meet within the $S_{i}$.

###  2.5 Expanders contain cliques

The reason for us to construct an expander in the given graph is that it is
known that expanders do contain large clique minors. We can use the minor
model of a clique to construct a bramble, as seen later, so expanders are
closely related to brambles.

######  Theorem 2.6 (Kawarabayashi and Reed (2010)).

There is a constant $c>0$ such that every $\alpha$-expander $G$ on $n$
vertices and maximum degree at most $d$ contains a clique on at least
$c\alpha\sqrt{n}/d$ vertices as a minor.

######  Proof 2.7.

This is a simple corollary of a theorem of Kawarabayashi and Reed (2010). They
showed that there is a constant $c^{\prime}>0$ and a constant
$n_{0}\in\mathbb{N}$ such that, for every $n,t\in\mathbb{N}$ with $n\geq
n_{0}$, if $H$ is a graph with $n$ vertices that does not contain a clique
minor on $t$ vertices, then $H$ has a $2/3$-separator of size at most
$c^{\prime}t\sqrt{n}$ (see Kawarabayashi and Reed (2010), Theorem 1.2).
Herein, a $2/3$-separator is a vertex subset $S\subseteq V(H)$ such that each
connected component in $H-S$ has size at most $2|V(H)|/3$.

Now let $G$ be as in theorem 2.4. First, put $c$ small enough so that if
$n<n_{0}$, then $c\alpha\sqrt{n}/d<1$. By Kawarabayashi and Reed’s theorem, it
now suffices to show that we furthermore may choose the constant $c$ such that
$G$ does not have a $2/3$-separator of size at most $c^{\prime}t\sqrt{n}$ for
$t=c\alpha\sqrt{n}/d$. Indeed, pick any vertex subset $S\subseteq V(G)$ of
size at most $c^{\prime}t\sqrt{n}=c^{\prime}c\alpha n/d$. If $S$ is a
$2/3$-separator, then we claim that we may take the union $W$ of the vertex
sets of some connected components in $G-S$ such that $n/4\leq|W|\leq n/2$. To
see that such a union $W$ exists, consider the following. If there is a
component of size larger than $n/2$, then the other components give the
desired $W$: Since the largest component $C$ has size at most $2n/3$, the
remaining components contain at least $\ell$ vertices, where $\ell=n/3-|S|\geq
n/3-c^{\prime}c\alpha n/d$. Since $\alpha\leq d$ we have $\ell\geq
n/3-c^{\prime}cn$. By putting $c$ small enough, we have $\ell\geq n/4$. Thus
the union of the vertex sets of components other than $C$ give the desired $W$
if there is a component of size larger than $n/2$. Otherwise, if there is a
component of size at least $n/4$, then this component gives the desired $W$.
Otherwise, iteratively add to the initially empty union $W$ the smallest
components in order of increasing size until their total size exceeds $n/4$.
Note that $|W|\leq n/2$ because there is no component of size at least $n/4$.
Thus, indeed, we may choose $W$ as a union of connected components in $G-S$
such that $n/4\leq|W|\leq n/2$.

Since $G$ is an $\alpha$-expander and has maximum degree at most $d$, we then
have $|N(W)|\geq\alpha|W|/d\geq\alpha n/(4d)$. Since $N(W)\subseteq S$,
picking any $c$ satisfying $c<1/(4c^{\prime})$ thus yields that $S$ is not a
$2/3$-separator, as required.

###  2.6 Lovász Local Lemma

In the analysis in section 4 we will need the Lovász Local Lemma. The
following simplified variant suffices.

######  Theorem 2.7 (See Alon and Spencer (2004), Lemma 5.1.1).

Let $\mathcal{A}=\\{A_{1},\ldots,A_{n}\\}$ be a finite set of events over some
probability space. Let $\Delta\in\mathbb{N}$ such that each event in
$\mathcal{A}$ is independent of all but at most $\Delta$ other events in
$\mathcal{A}$. Suppose that there is a real number $x$ with $0\leq x<1$ such
that for all $i\in[n]$ we have $\mathrm{Pr}(A_{i})\leq x\cdot(1-x)^{\Delta}$.
Then $\mathrm{Pr}(\bigwedge_{i=1}^{n}\overline{A_{i}})\geq(1-x)^{n}$.

##  3 Brambles of high order and congestion two

In this section we prove the first result (theorem 1.1) of this note, namely
that every graph with large enough treewidth contains a bramble of high order
and low congestion.

We recall theorem 1.1: See 1.1

$\cdots$$S_{1}$$S_{2}$$S_{r}$$A_{1}$$B_{1}$$A_{2}$$B_{2}$$A_{r}$$B_{r}$$P_{1}$$T_{a}$$P_{\alpha}$$\mathcal{P}_{1}$$\mathcal{L}_{1}$$\mathcal{Q}_{2}$$A^{1}_{2}$$A^{2}_{2}$$Q(e)\in\mathcal{Q}_{r}$

Figure 1: $\mathcal{P}_{1}$ is the $B_{1}$-$A_{2}$-linkage and
$\mathcal{L}_{1}$ the $A_{1}$-$B_{1}$-linkage that both exist by definition of
the path-of-sets system. The path $P_{1}$ is given as one example of the paths
starting in $A_{1}$ and ending in $B_{r}$, within $S_{1}$ it uses the path in
$\mathcal{L}_{1}$ starting in the right vertex and then it continues with the
path of $\mathcal{P}_{1}$ starting in the vertex the path of $\mathcal{L}_{1}$
ends in. In $S_{2}$ we see the partition $(A_{2}^{1},A^{2}_{2})$ of $A_{2}$
chosen in the second round of the cut matching game together with the linkage
$\mathcal{Q}_{2}$ providing the answer of the matching player. In $S_{r}$ the
picture shows the path $Q(e)\in\mathcal{Q}_{r}$ for the edge $e\in M_{r}$ with
endpoint $\alpha$. The yellow edges in $A_{1}$ represent the spanning tree
$T_{a}$ of the model of a vertex $a$ in the clique minor obtained from $H$.

######  Proof 3.1.

Let $G$ be of treewidth at least $k$. Let $q$ be the polynomial and $f$ be the
function in corollary 2.5. Let $c\geq 1$ and $h^{\prime}_{0}$ be constants
such that the cut player wins the cut-matching game within $c(\log
h^{\prime})^{2}$ rounds on a vertex set of size $h^{\prime}$, $h^{\prime}\geq
h^{\prime}_{0}$, when using the strategy from theorem 2.2. Pick

$h=\left\lfloor\frac{k}{q(\log k,c(\log k)^{2}+1)\cdot(c(\log
k)^{2}+1)^{48}}\right\rfloor$

and $r=\lfloor c(\log h)^{2}+1\rfloor$. Note that we may add a large enough
constant to the polynomial $p$ in order to make the guarantee of theorem 1.1
trivial if $h\leq h^{\prime}_{0}$. Assume thus that the cut player wins in at
most $r$ rounds on a vertex set of size $h$. Observe that

$f(h,r)=hr^{48}q(\log h,\log r)\leq\frac{k\cdot(c(\log h)^{2}+1)^{48}\cdot
q(\log h,\log r)}{q(\log k,c(\log k)^{2}+1)\cdot(c(\log
k)^{2}+1)^{48}}\leq\frac{k\cdot q(\log h,\log r)}{q(\log k,c(\log k)^{2}+1)}$

where the second inequality holds since $h\leq k$ because $c\geq 1$ and $q$
has only positive coefficients. Furthermore, for the same reasons we have
$q(\log h,\log r)\leq q(\log k,c(\log k)^{2}+1)$ and thus $f(h,r)\leq k$.

It follows that $G$ has treewidth at least $f(h,r)$ and thus, by corollary
2.5, graph $G$ contains a strong $(h,r)$-path-of-sets system
$\left(\mathcal{S},\mathcal{A},\mathcal{B},\mathcal{P}\right)$. Let
$\mathcal{S}=S_{1},\dots,S_{r}$, $\mathcal{A}=A_{1},\dots,A_{r}$,
$\mathcal{B}=B_{1},\dots,B_{r}$, and
$\mathcal{P}=\mathcal{P}_{1},\ldots,\mathcal{P}_{r-1}$. For illustration of
the remaining part of the proof, see figure 1. By property ii) of path-of-sets
systems $\left(\mathcal{S},\mathcal{A},\mathcal{B},\mathcal{P}\right)$
contains an $A_{i}$-$B_{i}$-linkage $\mathcal{L}_{i}$ within
$\mathchoice{G\\!\left[S_{i}\right]}{G\\!\left[S_{i}\right]}{G\left[S_{i}\right]}{G\left[S_{i}\right]}$
for all $1\leq i\leq r$. Also for all $1\leq i<r$, $\mathcal{P}_{i}$ is a
$B_{i}$-$A_{i+1}$-linkage which is vertex-disjoint from each set $S_{j}$,
$j\in[r]$ within the path-of-sets system, except for $S_{i}$ and $S_{i+1}$ to
which $\mathcal{P}_{i}$ is disjoint except for the endpoints of its paths. We
thus combine the linkages $\mathcal{L}_{1},\dots,\mathcal{L}_{r}$ and
$\mathcal{P}_{1},\dots,\mathcal{P}_{r-1}$ to obtain $h$ pairwise disjoint
paths $P_{1},\dots,P_{h}$ starting in $A_{1}$ and ending in $B_{r}$. Each of
these paths now has exactly one vertex in every $A_{i}$ and every $B_{i}$,
$i\in[r]$.

We now play the cut-matching game on the set $V=[h]$ with the strategy for the
cut player of theorem 2.2. The game lasts at most $r$ rounds. At each round
$i\in[r]$, we simulate the matching player as follows: For a given partition
$\left(V^{1},V^{2}\right)$ of $[h]$, we define for both $c=1,2$ the set
$A_{i}^{c}\subseteq A_{i}$ as those vertices $v\in A_{i}$ that lie on a path
$P_{j}$ with $j\in V^{c}$. Since the path-of-sets system is strong, $A_{i}$ is
well-linked in $G[S_{i}]$. We thus use the well-linkedness of $A_{i}$ in
$G[S_{i}]$ to obtain a $A_{i}^{1}$-$A_{i}^{2}$-linkage $\mathcal{Q}_{i}$
contained in $G[S_{i}]$. Finally, the matching player answers with a matching
$M_{i}$ that corresponds to which elements of $A_{i}^{1}$ were connected to
which elements of $A_{i}^{2}$. In formulas,

$M_{i}=\\{\alpha\beta\mid\alpha\in V^{1},\beta\in V^{2}\text{, and
}\mathcal{Q}_{i}\text{ contains a path with endpoints in }P_{\alpha}\text{ and
}P_{\beta}\\}\text{.}$

Let $H$ be the graph at the end of the cut-matching game. Since $H$ is an
$\Omega(1)$-expander of maximum degree $\mathcal{O}((\log h)^{2})$, by theorem
2.4, it contains a clique minor of size $t$ where $t=\Omega(\sqrt{h}/(\log
h)^{2})$. Denote the model of this clique as $(K_{a})_{a\in[t]}$. That is, the
sets $K_{a}$, $a\in[t]$, are pairwise disjoint subsets of $V(H)$, each
$H[K_{a}]$ is connected, and for every $ab\in\binom{[t]}{2}$ there exists
$j_{a,b}\in K_{a}$ and $j_{b,a}\in K_{b}$ with $j_{a,b}j_{b,a}\in E(H)$. Let
$T_{a}$ be a spanning tree of $H[K_{a}]$.

Since $H$ consists of the matchings $M_{1},\ldots,M_{r}$, to every edge $e\in
E(H)$ we can associate the path $Q(e)\in\mathcal{Q}_{i}$ that induced $e$,
that is, $e\in M_{i}$, $e=\alpha\beta$, and $Q(e)$ has its endpoints on the
paths $P_{\alpha}$ and $P_{\beta}$.

For every $a\in[t]$, we construct a connected subgraph $G_{a}$ of $G$
consisting of the paths $P_{\alpha}$ for each $\alpha\in K_{a}$, the paths
$Q(e)$ for each $e\in E(T_{a})$, and the paths $Q(j_{a,b}j_{b,a})$, excluding
the endpoint on $P_{j_{b,a}}$, for all $a,b\in t$ with $a<b\leq t$. Then, as
$(K_{a})_{a\in[t]}$ is a clique model in $H$, $(G_{a})_{a\in[t]}$ is a bramble
in $G$. Furthermore, $(G_{a})_{a\in[t]}$ is of congestion $2$ as every vertex
of $G$ can lie on at most one path $P_{\alpha}$ and at most one path $Q(e)$.
Finally, $t=\Omega(\sqrt{h}/(\log h)^{2})=\widetilde{\Omega}(\sqrt{k})$.

##  4 Upper bound for exponential brambles

In this section we prove theorem 1.2. For convenience we restate it below. See
1.2

#### Treewidth sparsifier.

It is straightforward to lift a bramble in a topological minor $H$ of a graph
$G$ to a bramble in $G$ without decreasing the order of the bramble. Thus, by
hiding the polylogarithmic loss on the treewidth of theorem 2.1 within the
$p(\cdot)$ factor of theorem 1.2, we can assume that we consider a graph $G$
of treewidth at least $k$ and $|V(G)|=\widetilde{\mathcal{O}}(k^{4})$.

#### Concurrent flow.

Let us define a _flow_ $f_{u,v}$ between two vertices $u$ and $v$ as a
weighted collection of pairwise distinct paths between $u$ and $v$ (if $u=v$
then the only possible path in $f_{u,v}$ has length 0). The _units of flow
sent through a vertex $w$_ by $f_{u,v}$ is the sum of the weights of the paths
in $f_{u,v}$ that contain $w$. The _value_ of $f_{u,v}$ is defined as the
units of flow sent through $u$ (or equivalently through $v$). For a set
$W\subseteq V(G)$, a _concurrent flow of value $\nu$ and congestion $\gamma$_
is a collection of $|W|^{2}$ flows $(f_{u,v})_{(u,v)\in W\times W}$ such that

  * •

$f_{u,v}$ sends exactly $\nu$ units of flow from $u$ to $v$; and

  * •

for each vertex $w$ the total flow over all flows $f_{u,v}$ sent through $w$
is at most $\gamma$.

We need the following well-known result on well-linked sets and multicommodity
flows; for a proof, see, e.g., the first paragraph of the proof of Lemma 14 by
Grohe and Marx (2009).

######  Lemma 4.1 (Grohe and Marx (2009)).

Let $G$ be a graph of treewidth at least $k$. Then there exists a set
$W\subseteq V(G)$ of size at least $k/3$ and a concurrent flow of value $1$
and congestion at most $\beta k\log k$, for some constant $\beta$ (not
dependent on $k$).

Note that the sum of the values of all flows in a concurrent flow of value $1$
is $\mathcal{O}(k^{2})$; the essence of lemma 4.1 is that only a tiny part of
it, an $\mathcal{O}((\log k)/k)$ fraction, can pass through a single vertex.
Without loss of generality, we can assume that the constant $\beta$ of lemma
4.1 satisfies $\beta>1/9$ (which we need for technical reasons later on).

#### Sampling a path.

Let $G$ be a graph. Similarly as Grohe and Marx (2009), we use the concurrent
flow given by lemma 4.1 to sample paths between vertices of a given subset of
$V(G)$. From now on, let $W\subseteq V(G)$ be a set of size exactly
$\lfloor\nicefrac{{k}}{{3}}\rfloor$ and $(f_{u,v})_{(u,v)\in W\times W}$ the
concurrent flow given by lemma 4.1 applied to $G$. (Note that, if the size of
the set $W$ promised by lemma 4.1 is larger than
$\lfloor\nicefrac{{k}}{{3}}\rfloor$ we can omit vertices from $W$ and drop the
corresponding flows from the concurrent flow obtaining a concurrent flow of
the same value and at most the same congestion.) For each $(u,v)\in W\times W$
let $\mathcal{P}_{u,v}$ be the family of paths in $f_{u,v}$ and let
$f_{u,v}(P)$ be the flow value passed along a path $P\in\mathcal{P}_{u,v}$
(i.e. the weight of $P$ in $f_{u,v}$). Since the value of $f_{u,v}$ is $1$,
flow $f_{u,v}$ can be interpreted as a probability distribution over
$\mathcal{P}_{u,v}$.

######  Claim 1.

Fix $x\in V(G)$. Assume that we are sampling two vertices $u,v\in W$ uniformly
at random and then sampling a path from $u$ to $v$ according to the following
distribution: the probability of sampling $P\in\mathcal{P}_{u,v}$ equals
$f_{u,v}(P)$ (and paths not from $\mathcal{P}_{u,v}$ have zero probability).
Then, the probability that $x$ lies on a sampled path is at most $9\beta\log
k/k$.

######  Proof 4.2.

The experiment in the statement is equivalent to sampling a pair $(u,v)\in
W\times W$ and then sampling a path $P\in\mathcal{P}_{u,v}$ according to
$f_{u,v}$ as a probability distribution on $\mathcal{P}_{u,v}$. Since there
are at most $k^{2}/9$ possible choices for $f_{u,v}$, the probability that $x$
is on the sampled path is bounded above by $9\bar{f}(x)/k^{2}$, where
$\bar{f}(x)$ is the total amount of flow passing through $x$. Since
$\bar{f}(x)\leq\beta k\log k$ by the congestion property of the concurrent
flow $(f_{u,v})$, the claim follows.

#### Sampling a closed walk.

Let $\ell:=\lfloor\frac{k^{0.5+\delta}}{72\beta}\rfloor$. By _sampling a walk
$\mathcal{W}$_ we mean the following experiment. Sample uniformly and
independently at random $\ell$ vertices $s_{1},s_{2},\ldots,s_{\ell}\in W$ and
then, for every $i\in[\ell]$, sample path
$P_{i}\in\mathcal{P}_{s_{i},s_{i+1}}$ according to $f_{s_{i},s_{i+1}}$ (with
indices cyclically modulo $\ell$). The walk $\mathcal{W}$ is then the
concatenation of $P_{1},P_{2},\ldots,P_{\ell}$. Note that the vertices
$s_{1},\ldots,s_{\ell}$ are not necessarily distinct.

We use claim 1 in the following way.

######  Claim 2.

Let $\alpha$ be a real number with $0<\alpha<1$ and let $X\subseteq V(G)$ be
of size at most $\alpha\ell/\log k$. Sample a walk $\mathcal{W}$. Then,

$\mathrm{Pr}(X\cap V(\mathcal{W})=\emptyset)\geq\exp\left(-\mathcal{O}(\alpha
k^{2\delta})\right).$

######  Proof 4.3.

Let $s_{1},\ldots,s_{\ell}$ and $P_{1},\ldots,P_{\ell}$ be as in the
definition of sampling a walk.

Let $A_{i}$ be the event that $X\cap V(P_{i})\neq\emptyset$. Claim 1 with
union bound over all $x\in X$ implies that

$\mathrm{Pr}(A_{i})\leq\frac{9\alpha\beta\ell}{k}\leq\frac{\alpha}{8k^{0.5-\delta}}.$
(3)

Observe that $A_{i}$ is independent of $A_{j}$ unless $i=j+1$ or $i+1=j$ (with
indices cyclically modulo $\ell$). That is, $A_{i}$ is independent of all but
two other events $A_{i}$.

Let $\pi(k)$ denote the right-hand side of equation 3; note that $\pi(k)<1/8$.
Then, $\mathrm{Pr}(A_{i})\leq(4\pi(k))\cdot(1-4\pi(k))^{2}$. Hence, by the
Lovász Local Lemma (theorem 2.5), we obtain that

$\mathrm{Pr}\left(\bigwedge_{i=1}^{\ell}\overline{A_{i}}\right)\geq\prod_{i=1}^{\ell}\left(1-4\pi(k)\right)\geq\left(1-\frac{\alpha}{2k^{0.5-\delta}}\right)^{\frac{k^{0.5+\delta}}{72\beta}}=\left(\left(1-\frac{1}{\frac{2k^{0.5-\delta}}{\alpha}}\right)^{\frac{2k^{0.5-\delta}}{\alpha}}\right)^{\frac{\alpha
k^{2\delta}}{144\beta}}.$ (4)

From the folklore relation $(1+1/x)^{x}\leq e\leq(1+1/x)^{x+1}$ for all
positive $x$ we obtain that the right-hand side of equation 4 is in

$\exp\left(-\mathcal{O}\left(\frac{\alpha
k^{2\delta}}{\beta}\right)\right)=\exp\left(-\mathcal{O}(\alpha
k^{2\delta})\right).$

This concludes the proof of the claim.

#### Many closed walks sampled independently form a bramble.

Claim 2 asserts that there is a nontrivial chance that a hitting set of size
at most $\alpha\ell/\log k$ misses a sampled walk. On the other hand, two
walks sampled independently at random intersect with high probability, so we
can sample a large number of walks that pairwise intersect.

######  Claim 3.

Let $\mathcal{W}_{1}$ and $\mathcal{W}_{2}$ be two walks sampled
independently. Then,

$\mathrm{Pr}(V(\mathcal{W}_{1})\cap
V(\mathcal{W}_{2})=\emptyset)\leq\exp\left(-\Omega(k^{2\delta})\right).$

Consequently, for some universal constant $\lambda>0$, if one samples a family
$\mathcal{B}$ of $\lfloor\exp(\lambda k^{2\delta})\rfloor$ walks (each walk is
sampled independently), then the walks pairwise intersect with probability
larger than $0.5$.

######  Proof 4.4.

The second part of the claim follows directly from the first part by union
bound.

For the first part, let $s_{1},\ldots,s_{\ell}$ be the vertices sampled in the
process of sampling $\mathcal{W}_{1}$ and
$s_{1}^{\prime},\ldots,s_{\ell}^{\prime}$ be the vertices sampled in the
process of sampling $\mathcal{W}_{2}$. It suffices to show that

$\mathrm{Pr}(\\{s_{1},\ldots,s_{\ell}\\}\cap\\{s_{1}^{\prime},\ldots,s_{\ell}^{\prime}\\}=\emptyset)\leq\exp\left(-\Omega(k^{2\delta})\right).$

Let $S=\\{s_{1},\ldots,s_{\ell}\\}$. Observe that
$\ell=\lfloor\frac{k^{0.5+\delta}}{72\beta}\rfloor<\lfloor
k/12\rfloor\leq|W|/2$. Hence, for each $i\in[\ell]$

$\mathrm{Pr}(s_{i}\in\\{s_{1},\ldots,s_{i-1}\\})<0.5.$

Let $X_{i}=1$ if $s_{i}\notin\\{s_{1},\ldots,s_{i-1}\\}$ and $X_{i}=0$
otherwise. Then, we have $|S|=\sum_{i=1}^{\ell}X_{i}$ and
$\mathrm{Pr}(X_{i}=1)>0.5$.

Let $X_{1}^{\prime},X_{2}^{\prime},\ldots,X_{\ell}^{\prime}$ be independent
symmetrical Bernoulli variables. From the previous paragraph we infer that for
every real $r$ we have $\mathrm{Pr}(\sum_{i=1}^{\ell}X_{i}\geq
r)\geq\mathrm{Pr}(\sum_{i=1}^{\ell}X_{i}^{\prime}\geq r)$. Hence, by the
Chernoff inequality
$\mathrm{Pr}(\sum_{i=1}^{\ell}X_{i}^{\prime}\leq(1-a)\mu)\leq e^{-a^{2}\mu/2}$
for $0\leq a\leq 1$, where $\mu=\ell/2$ is the expected value of
$\sum_{i=1}^{\ell}X_{i}^{\prime}$, we have:

$\mathrm{Pr}(|S|<\ell/4)=\mathrm{Pr}\left(\sum_{i=1}^{\ell}X_{i}<\ell/4\right)\leq\mathrm{Pr}\left(\sum_{i=1}^{\ell}X_{i}^{\prime}<\ell/4\right)\leq
e^{-\ell/16}.$

The above allows us to condition now on the event $|S|\geq\ell/4$. Let us move
to sampling vertices $s_{i}^{\prime}$. We have

$\mathrm{Pr}(\forall_{i=1}^{\ell}s_{i}^{\prime}\notin
S)=\left(1-\frac{|S|}{k}\right)^{\ell}\leq\left(1-\frac{\ell/4}{k}\right)^{\ell}\leq\exp\left(-\Omega(k^{2\delta})\right)\text{,
as required.}$

Let $\lambda>0$ be the constant of Claim 3 and let $\mathcal{B}$ be a sequence
of $\lfloor\exp(\lambda k^{2\delta})\rfloor$ closed walks sampled
independently. Claim 3 asserts that with probability more than $0.5$ the
family $\mathcal{B}$ (where every walk is interpreted as its vertex set) is a
bramble in $G$.

#### Order of the sampled bramble.

We now show that for a sufficiently small constant $\alpha>0$, with
probability more than $0.5$ for every set $X\subseteq V(G)$ of size at most
$\alpha\ell/\log k$ there exists $\mathcal{W}\in\mathcal{B}$ that is disjoint
with $X$. Together with the fact that $\mathcal{B}$ is a bramble with
probability larger than $0.5$, this proves that with positive probability both
$\mathcal{B}$ is a bramble and the minimum size of a hitting set of
$\mathcal{B}$ is $\Omega(k^{0.5+\delta}/\log k)$, concluding the proof of
theorem 1.2.

By claim 2, for a single walk $\mathcal{W}\in\mathcal{B}$, we have

$\mathrm{Pr}(X\cap V(\mathcal{W})=\emptyset)\geq\exp\left(-\mathcal{O}(\alpha
k^{2\delta})\right).$

Recall that the walks in $\mathcal{B}$ are sampled independently, so, for a
fixed vertex subset $X\subseteq V(G)$, the events $(X\cap
V(\mathcal{W})=\emptyset)_{\mathcal{W}\in\mathcal{B}}$ are independent. Hence,
for a fixed vertex subset $X\subseteq V(G)$ of size at most $\alpha\ell/\log
k$ we have

$\mathrm{Pr}(\forall_{\mathcal{W}\in\mathcal{B}}X\cap
V(\mathcal{W})\neq\emptyset)\leq\left(1-\exp\left(-\mathcal{O}(\alpha
k^{2\delta})\right)\right)^{\lfloor\exp(\lambda
k^{2\delta})\rfloor}\leq\exp\left(-\exp(\lambda/2\cdot k^{2\delta})\right).$

Here, in the last inequality we have chosen $\alpha$ small enough so that
$\alpha$ times the constant hidden in the big-$\mathcal{O}$ notation is
smaller than $\lambda/2$. As $|V(G)|=\widetilde{\mathcal{O}}(k^{4})$, there
are $2^{\mathcal{O}(\alpha k^{0.5+\delta})}$ choices of a set $X\subseteq
V(G)$ of size at most $\alpha\ell/\log k$. By union bound over the possible
sets $X$ we obtain:

$\mathrm{Pr}\left(\exists_{X\subseteq V(G)}|X|\leq\alpha\ell/\log
k\wedge\forall_{\mathcal{W}\in\mathcal{B}}X\cap
V(\mathcal{W})\neq\emptyset\right)\leq\exp\left(\mathcal{O}(\alpha
k^{0.5+\delta})-\exp(\lambda/2\cdot k^{2\delta})\right).$

By choosing $\alpha$ sufficiently small, the last expression can be made to be
less than $0.5$.

Hence, with probability more than $0.5$ the family $\mathcal{B}$ does not
admit a hitting set of size at most $\alpha\ell/\log k$ and with probability
more than $0.5$ the family $\mathcal{B}$ is a bramble. By the union bound,
$\mathcal{B}$ is a bramble of order $\widetilde{\Omega}(k^{0.5+\delta})$ with
positive probability. This concludes the proof of theorem 1.2.

## References

  * Alon and Spencer (2004) N. Alon and J. H. Spencer.  _The Probabilistic Method_.  John Wiley & Sons, 2004.
  * Chekuri and Chuzhoy (2015) C. Chekuri and J. Chuzhoy.  Degree-3 treewidth sparsifiers.  In P. Indyk, editor, _Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015_ , pages 242–255. SIAM, 2015.  10.1137/1.9781611973730.19.  URL https://doi.org/10.1137/1.9781611973730.19.
  * Chekuri and Chuzhoy (2016) C. Chekuri and J. Chuzhoy.  Polynomial bounds for the grid-minor theorem.  _J. ACM_ , 63(5):40:1–40:65, 2016.  10.1145/2820609.  URL https://doi.org/10.1145/2820609.
  * Grohe and Marx (2009) M. Grohe and D. Marx.  On tree width, bramble size, and expansion.  _J. Comb. Theory, Ser. B_ , 99(1):218–228, 2009\.  10.1016/j.jctb.2008.06.004.  URL https://doi.org/10.1016/j.jctb.2008.06.004.
  * Kawarabayashi and Reed (2010) K. Kawarabayashi and B. Reed.  A separator theorem in minor-closed classes.  In _2010 IEEE 51st Annual Symposium on Foundations of Computer Science_ , pages 153–162. IEEE, 2010.
  * Khandekar et al. (2009) R. Khandekar, S. Rao, and U. Vazirani.  Graph partitioning using single commodity flows.  _Journal of the ACM (JACM)_ , 56(4):1–15, 2009\.
  * Robertson and Seymour (1984) N. Robertson and P. D. Seymour.  Graph minors. III. planar tree-width.  _J. Comb. Theory, Ser. B_ , 36(1):49–64, 1984\.  10.1016/0095-8956(84)90013-3.  URL https://doi.org/10.1016/0095-8956(84)90013-3.
  * Seymour and Thomas (1993) P. D. Seymour and R. Thomas.  Graph searching and a min-max theorem for tree-width.  _J. Comb. Theory, Ser. B_ , 58(1):22–33, 1993\.  10.1006/jctb.1993.1027.  URL https://doi.org/10.1006/jctb.1993.1027.