[a]I. Soler

# Supercurrent renormalization of $\cal{N}$ = 1 supersymmetric Yang-Mills
theory on the lattice

G. Bergner  M. Costa  H. Panagopoulos  S. Piemonte  G. Spanoudes

###### Abstract

Supersymmetry on the lattice is explicitly broken by the gluino mass and
lattice artifacts. However, it can be restored in the continuum limit by fine
tuning the parameters based on the renormalized Ward identities. On the
renormalization step not only the mass but also the renormalization of the
supercurrent needs to be addressed. Here we present a lattice investigation to
obtain the renormalization factors of the supercurrent for $\mathcal{N}$=1
Super-Yang Mills theory in a gauge invariant renormalization scheme. We also
provide the conversion factors which are necessary in order to translate our
results to the more standard $\overline{\rm MS}$ scheme.

##  1 Introduction

Even though the lattice discretization breaks supersymmetry (SUSY) explicitly,
Curci and Veneziano [1] showed for $\mathcal{N}=1$ supersymmetric Yang-Mills
(SYM) that chiral symmetry and supersymmetry can both be recovered in the
continuum limit by tuning a single parameter, the gluino mass. This approach
has been successfully applied in numerical simulations providing also first
insights about the particle spectrum of the theory [2, 3].

In supersymmetric theories containing matter supermultiplets, such as SQCD,
the number of parameters that need fine tuning is significantly larger. A
tuning based on Ward identities becomes challenging. In particular
renormalization coefficients of the supercurrent need to be determined
numerically in this approach. In this work we study the renormalization of the
supercurrent and compare non-perturbative effects to perturbation estimates.

As a first exploratory step we will study the renormalization of the
supercurrent for $\mathcal{N}=1$ supersymmetric Yang-Mills (SYM) on the
lattice. We will do so by computing, non-perturbatively, the renormalization
factors in a gauge-invariant renormalization scheme (GIRS) [4]. Furthermore,
we will compute the conversion factors from GIRS to $\overline{\rm MS}$ scheme
perturbatively in dimensional regularization. Then we will be able to convert
our lattice regularized GIRS renormalization factors to the more standard
$\overline{\rm MS}$ scheme.

##  2 The model

$\mathcal{N}=1$ SYM is the simplest four-dimensional supersymmetric gauge
theory. This theory describes the strong interactions between the carriers of
the gauge force, the gluons, and their super-partners, the gluinos, which are
Majorana fermions transforming under the adjoint representation of the gauge
group. The gluons are represented by the non-Abelian gauge field
$u^{a}_{\mu}(x)$ and the gluinos by the fermionic field $\lambda^{a}(x)$,
where $a=1,...,N_{c}^{2}-1$. The on-shell Lagrangian for $\mathcal{N}=1$ in
Euclidean space is

$\displaystyle\mathcal{L}=\frac{1}{4}u^{a}_{\mu\nu}u^{a}_{\mu\nu}+\frac{1}{2}\bar{\lambda^{a}}\gamma_{\mu}(D_{\mu}\lambda)^{a},$
(1)

where $u^{a}_{\mu\nu}$ is the non-Abeliean field strength tensor and $D_{\mu}$
is the gauge covariant derivative acting as
$(D_{\mu}\lambda)^{a}=\partial_{\mu}\lambda^{a}+gf_{abc}u_{\mu}^{b}\lambda^{b}$.
The infinitesimal supersymmetry transformation leaving the action of the
theory invariant is given by

$\displaystyle\delta u_{\mu}^{a}(x)=-i\bar{\xi}\gamma_{\mu}\lambda^{a}(x)$
$\displaystyle\delta\lambda^{a}(x)=\frac{1}{2}\sigma_{\mu\nu}u_{\mu\nu}^{a}(x)\xi,$
(2)

where $\sigma_{\mu\nu}=\frac{1}{2}[\gamma_{\mu},\gamma_{\nu}]$ and $\xi$ is a
Grassmann variable corresponding to the infinitesimal parameter of the
transformation. Applying Noether’s theorem to the classical theory, the
symmetry transformation Eq.(2) leads to the conserved supercurrent

$S_{\mu}(x)\equiv-\sigma_{\nu\rho}\gamma_{\mu}{\rm
tr}_{c}(\,u_{\nu\,\rho}(x)\lambda(x)).$ (3)

Defining the theory at the quantum level requires regularization and
renormalization which leads to important modifications. On the lattice,
supersymmetry is broken by the addition of a gluino mass term and by the
explicit breaking of Lorentz symmetry. Under renormalization the mass term
gets additively renormalised and the supercurrent mixes with another dimension
7/2 operator

$T_{\mu}(x)\equiv 2\,\gamma_{\nu}{\rm tr}_{c}(\,u_{\mu\,\nu}(x)\lambda(x)).$
(4)

The corresponding Ward identity for the supercurrent after such modification
reads as

$\displaystyle
Z_{SS}\big{<}\nabla_{\mu}S_{\mu}(x)Q(y)\big{>}+Z_{ST}\big{<}\nabla_{\mu}T_{\mu}(x)Q(y)\big{>}=m_{S}\big{<}\chi(x)Q(y)\big{>}+O(a),$
(5)

where $Z_{SS}$ and $Z_{ST}$ are the renormalization coefficients of the
supercurrent $S^{R}_{\mu}=Z_{SS}S_{\mu}+Z_{ST}T_{\mu}$ and $m_{s}$ is the
renormalized gluino mass; $Q(y)$ can be any operator localized at a point
$y\neq x$.

We will explore in this work the renormalization of the Supercurrent operators
$S_{\mu},T_{\mu}$ on the lattice both numerically by Monte-Carlo simulations
and using perturbation theory.

##  3 Renormalization and GIRS scheme

Our main goal is to compute the renormalization of the supercurrent both
perturbatively and non-perturbatively. Therefore the first step is to decide
on a proper renormalization scheme that can be applicable in both situations.
In this work we will use the GIRS scheme [4] which is reminiscent of the
X-space renormalization scheme. The GIRS is defined through the
renormalization conditions

$\displaystyle\langle\mathcal{O}^{\rm{GIRS}}_{X}(x)\mathcal{O}^{\rm{GIRS}}_{Y}(y)\rangle|_{{}_{x-y=\bar{z}}}\equiv
Z_{X}^{\rm{GIRS}}Z_{Y}^{\rm{GIRS}}\langle\mathcal{O}^{\rm{B}}_{X}(x)\mathcal{O}^{\rm{B}}_{Y}(y)\rangle|_{{}_{x-y=\bar{z}}}=\langle\mathcal{O}_{X}(x)\mathcal{O}_{Y}(y)\rangle^{\rm{tree}}|_{{}_{x-y=\bar{z}}},$

for $X,Y$ two operators of interest and $(x\neq y)$ in order to avoid
potential contact terms; the superscript $B$ denotes bare quantities. This
scheme is appealing because the two-point Green functions
$\langle\mathcal{O}^{\rm{B}}_{X}(x)\mathcal{O}^{\rm{B}}_{Y}(y)\rangle|_{{}_{x-y=\bar{z}}}$
can be computed both non-perturbatively and also in perturbation theory. Even
more important, choosing gauge-invariant operators, only the mixing between
these operators and other gauge-invariant operators is relevant, which makes
this scheme particularly suitable for lattice computations. Considering the
gauge invariant operators $\mathcal{O}_{X},\mathcal{O}_{Y}=S_{\mu},T_{\mu}$
the resulting mixing matrix relating the bare and renormalized supercurrent
operators is

$\displaystyle\begin{pmatrix}{S}^{R}_{\mu}&\\\\[8.61108pt]
{T}^{R}_{\mu}\end{pmatrix}=\begin{pmatrix}Z_{SS}&Z_{ST}\\\\[8.61108pt]
Z_{TS}&Z_{TT}\end{pmatrix}\begin{pmatrix}{S}^{B}_{\mu}&\\\\[8.61108pt]
{T}^{B}_{\mu}\end{pmatrix}.$ (6)

To determine the 4 elements of the mixing matrix $Z$ we need 4 conditions:

  * •

Three conditions can be imposed by considering expectation values between the
two mixing operators 111A bar on $S_{\mu},T_{\mu}$ denotes the corresponding
charge conjugates

$\displaystyle G^{S\,S}_{\mu\nu}(x,y)\equiv\langle S_{\mu}(x)\
\overline{S}_{\nu}(y)\rangle\,\,\,$
$\displaystyle,\,\,\,G^{T\,T}_{\mu\nu}(x,y)\equiv\langle T_{\mu}(x)\
\overline{T}_{\nu}(y)\rangle\,\,\,,\,\,\,$ $\displaystyle
G^{S\,T}_{\mu\nu}(x,y)\equiv$ $\displaystyle\langle S_{\mu}(x)\
\overline{T}_{\nu}(y)\rangle.$ (7)

  * •

A fourth condition can be imposed on two-point Green’s functions involving
products of $S_{\mu}$ (or $T_{\mu}$) with other gauge-invariant operators of
equal or lower dimension. The only such operator with compatible behaviour
under the Lorentz group is the Gluino-Glue operator ${\cal
O}(x)\equiv\sigma_{\mu\nu}\,{\rm{tr}}_{c}(\,u_{\mu\nu}(x)\lambda(x))$ and a
corresponding Green’s function is

$G^{{\cal O}\,S}_{\mu}(x,y)\equiv\langle{\cal O}(x)\
\overline{S}_{\mu}(y)\rangle.$ (8)

There is a variety of ways to imposed the GIRS renormalization conditions.
Especially suitable for numerical lattice investigations is the following form
where we integrate over the spatial components of $z=y-x=(\vec{z},t)$ for the
sake of improving the signal

$\displaystyle\int d^{3}\vec{z}\ {\rm
Tr}\\{{\left[G^{S\,S}_{\mu\nu}(x,y)\right]}^{{\rm GIRS}}P_{\nu\mu}\\}$
$\displaystyle=$ $\displaystyle\int d^{3}\vec{z}\ {\rm
Tr}\\{{\left[G^{S\,S}_{\mu\nu}(x,y)\right]}^{\rm tree}P_{\nu\mu}\\},$ (9)
$\displaystyle\int d^{3}\vec{z}\ {\rm
Tr}\\{{\left[G^{T\,T}_{\mu\nu}(x,y)\right]}^{{\rm GIRS}}P_{\nu\mu}\\}$
$\displaystyle=$ $\displaystyle\int d^{3}\vec{z}\ {\rm
Tr}\\{{\left[G^{T\,T}_{\mu\nu}(x,y)\right]}^{\rm tree}P_{\nu\mu}\\},$ (10)
$\displaystyle\int d^{3}\vec{z}\ {\rm
Tr}\\{{\left[G^{S\,T}_{\mu\nu}(x,y)\right]}^{{\rm GIRS}}P_{\nu\mu}\\}$
$\displaystyle=$ $\displaystyle\int d^{3}\vec{z}\ {\rm
Tr}\\{{\left[G^{S\,T}_{\mu\nu}(x,y)\right]}^{\rm tree}P_{\nu\mu}\\},$ (11)
$\displaystyle\int d^{3}\vec{z}\ {\rm Tr}\\{{\left[G^{S\,{\cal
O}}_{\mu}(x,y)\right]}^{{\rm GIRS}}P_{\mu}\\}$ $\displaystyle=$
$\displaystyle\int d^{3}\vec{z}\ {\rm Tr}\\{{\left[G^{S\,{\cal
O}}_{\mu}(x,y)\right]}^{\rm tree}P_{\mu}\\}.$ (12)

$P_{\nu\mu}=\gamma_{\mu}\gamma_{4}\gamma_{\nu}$ and
$P_{\mu}=\gamma_{\mu}\gamma_{4}$ are projectors acting on the Dirac space that
project to states transforming properly under parity, time reversal and charge
conjugation. The repeated indices $\mu,\nu$ are not summed over and there is a
freedom on which components $\mu,\nu$ to choose. However, the operator
components need to be the same in all GIRS conditions Eq. (9–12), as in
principle, in this scheme, different components could give different
renormalization factors. The tree level values on the right hand side of Eq.
(9–12) after spatial integration are

$\displaystyle\int d^{3}\vec{z}\ {\rm Tr}\left[G^{SS,\,{\rm
tree}}_{\mu\nu}(x,y)\ P_{\nu\mu}\right]$ $\displaystyle=-\frac{(N_{c}^{2}-1)\
t}{\pi^{2}|t|^{5}}(1-\delta_{\mu 4}-\delta_{\nu
4}-3\,\delta_{\mu\nu}+4\,\delta_{\mu 4}\,\delta_{\nu 4}),$ (13)
$\displaystyle\int d^{3}\vec{z}\ {\rm Tr}\left[G^{TT,\,{\rm
tree}}_{\mu\nu}(x,y)\ P_{\nu\mu}\right]$
$\displaystyle=\phantom{+}\frac{(N_{c}^{2}-1)\
t}{4\pi^{2}|t|^{5}}(2+\delta_{\mu 4}+\delta_{\nu
4}+3\,\delta_{\mu\nu}-4\,\delta_{\mu 4}\,\delta_{\nu 4}),$ (14)
$\displaystyle\int d^{3}\vec{z}\ {\rm Tr}\left[G^{ST,\,{\rm
tree}}_{\mu\nu}(x,y)\ P_{\nu\mu}\right]$ $\displaystyle=-\frac{(N_{c}^{2}-1)\
t}{2\pi^{2}|t|^{5}}(1-\delta_{\mu 4}-\delta_{\nu
4}-3\,\delta_{\mu\nu}+4\,\delta_{\mu 4}\,\delta_{\nu 4}),$ (15)
$\displaystyle\int d^{3}\vec{z}\ {\rm Tr}\left[G^{S\mathcal{O},\,{\rm
tree}}_{\mu}(x,y)\ P_{\mu}\right]\ $ $\displaystyle=\phantom{+}0.$ (16)

It is instructive to write out the full set of GIRS conditions in terms of the
bare correlators. They lead to a set of quadratic equations for the
renormalization factors

$\displaystyle Z_{SS}^{2}\ {\rm
Tr}\left[G^{SS}_{\mu\nu}P_{\nu\mu}\right]+Z_{SS}\ Z_{ST}\ ({\rm
Tr}\left[G^{ST}_{\mu\nu}P_{\nu\mu}\right]+{\rm
Tr}\left[G^{TS}_{\mu\nu}P_{\nu\mu}\right])+Z_{ST}^{2}\ {\rm
Tr}\left[G^{TT}_{\mu\nu}P_{\nu\mu}\right]={\rm Tr}\left[G^{SS,{\rm
tree}}_{\mu\nu}P_{\nu\mu}\right],$ $\displaystyle Z_{TS}^{2}\ {\rm
Tr}\left[G^{SS}_{\mu\nu}P_{\nu\mu}\right]+Z_{TS}\ Z_{TT}\ ({\rm
Tr}\left[G^{ST}_{\mu\nu}P_{\nu\mu}\right]+{\rm
Tr}\left[G^{TS}_{\mu\nu}P_{\nu\mu}\right])+Z_{TT}^{2}\ {\rm
Tr}\left[G^{TT}_{\mu\nu}P_{\nu\mu}\right]={\rm Tr}\left[G^{TT,{\rm
tree}}_{\mu\nu}P_{\nu\mu}\right],$ $\displaystyle Z_{SS}\ \left(Z_{TS}\ {\rm
Tr}\left[G^{SS}_{\mu\nu}P_{\nu\mu}\right]+Z_{TT}\ {\rm
Tr}\left[G^{ST}_{\mu\nu}P_{\nu\mu}\right]\right)+Z_{ST}\ \left(Z_{TS}\ {\rm
Tr}\left[G^{TS}_{\mu\nu}P_{\nu\mu}\right]+Z_{TT}\ {\rm
Tr}\left[G^{TT}_{\mu\nu}P_{\nu\mu}\right]\right)=$ $\displaystyle\hskip
341.43306pt{\rm Tr}\left[G^{ST,{\rm tree}}_{\mu\nu}P_{\nu\mu}\right],$
$\displaystyle Z_{O}\left(Z_{SS}\ {\rm
Tr}\left[G^{SO}_{\mu}P_{\mu}\right]+Z_{ST}\ {\rm
Tr}\left[G^{TO}_{\mu}P_{\mu}\right]\right)={\rm Tr}\left[G^{SO,{\rm
tree}}_{\mu}P_{\mu}\right]=0,$ (17)

where on the last equation we used the renormalization of the Gluino-Glue
operator $\mathcal{O}^{R}=Z_{\mathcal{O}}\mathcal{O}^{B}$ and Eq. (16). From
Eq. (13–15) one can see that the particular choice of temporal indices for
either $\mu$ or $\nu$ will lead to a vanishing tree level value on the first
equation in (17). This in combination with the last equation above would
result in vanishing or indeterminate value for $Z_{SS}$ or $Z_{ST}$. Therefore
the only allowed components $\mu$, $\nu$ are the spatial ones.

##  4 Perturbative results in dimensional regularization and conversion
factors to $\overline{\rm MS}$

Instead of comparing perturbative and non-perturbative results on the GIRS
scheme we will follow a different approach. We will convert our results from
GIRS scheme to $\overline{\rm MS}$ using the conversion factors
$C^{GIRS,\overline{\rm MS}}$. This comes with the advantage that
$\overline{\rm MS}$ is more amenable to perturbation theory and the fitting of
the $Z$ factors on the numerical side is easier (see next section). The
conversion factors $C^{GIRS,\overline{\rm MS}}$ are the factors relating
$\overline{\rm MS}$ renormalized and GIRS renormalized operators

$\displaystyle\begin{pmatrix}C_{SS}^{{\rm GIRS},\ \overline{\rm
MS}}&C_{ST}^{{\rm GIRS},\ \overline{\rm MS}}\\\ \\\ C_{TS}^{{\rm GIRS},\
\overline{\rm MS}}&C_{TT}^{{\rm GIRS},\ \overline{\rm
MS}}\end{pmatrix}\cdot\begin{pmatrix}Z_{SS}^{{\ \rm R},\ {\rm
GIRS}}&Z_{ST}^{{\ \rm R},\ {\rm GIRS}}\\\ \\\ Z_{TS}^{{\ \rm R},\ {\rm
GIRS}}&Z_{TT}^{{\ \rm R},\ {\rm GIRS}}\end{pmatrix}$ $\displaystyle=$
$\displaystyle\begin{pmatrix}Z_{SS}^{{\ \rm R},\ \overline{\rm
MS}}&Z_{ST}^{{\rm R},\ \overline{\rm MS}}\\\ \\\ Z_{TS}^{{\ \rm R},\
\overline{\rm MS}}&Z_{TT}^{{\rm R},\ \overline{\rm MS}}\end{pmatrix},$ (18)

where R stands for a chosen regularization scheme and the conversion factors
themselves are regularization independent. We first obtained the conversion
factors by computing the renormalization constants to one-loop in perturbation
theory in dimensional regularization both for the $\overline{\rm MS}$ and the
GIRS scheme. From the action defined by the Lagrangian Eq. (1), after applying
the conventional Faddev-Popov method, one can obtain the corresponding bare
Green’s functions at tree-level and to one-loop order in dimensional
regularization (DR), involving respectively, the one-loop and two-loop Feynman
diagrams of Fig. 1.

Figure 1: One-loop and two-loop Feynman diagrams contributing to the tree-
level and one-loop two-point Green’s functions of Eqs. (7) and (8). A wavy
(solid, dashed) line represents gluons (gluinos, ghosts). The two crosses
denote the insertions of operators $S_{\mu},T_{\nu},\mathcal{O}$ appearing in
the definition of each two-point function.

As is standard practice, the pole terms ($1/\varepsilon^{n}$,
$n\in\mathbb{Z}^{+}$) are removed by defining the $\overline{\rm MS}$ mixing
matrix elements to have only negative integer powers of $\varepsilon$, i.e.,
$Z_{ij}^{{\rm DR},\overline{\rm
MS}}=\delta_{ij}+g^{2}(z_{ij}/\varepsilon)+\mathcal{O}(g^{4})$, where
$i,j=S,T$ and $Z_{\mathcal{O}}^{{\rm DR},\overline{\rm
MS}}=1+g^{2}(z_{\mathcal{O}}/\varepsilon)+\mathcal{O}(g^{4})$. Our results for
$Z_{ij}^{{\rm DR},\overline{\rm MS}}$, $Z_{\mathcal{O}}^{{\rm
DR},\overline{\rm MS}}$ read

$\displaystyle Z_{SS}^{{\rm DR},\overline{\rm MS}}$ $\displaystyle=$
$\displaystyle 1+\mathcal{O}(g^{4}),$ (19) $\displaystyle Z_{ST}^{{\rm
DR},\overline{\rm MS}}$ $\displaystyle=$ $\displaystyle\mathcal{O}(g^{4}),$
(20) $\displaystyle Z_{TS}^{{\rm DR},\overline{\rm MS}}$ $\displaystyle=$
$\displaystyle\frac{g^{2}}{16\,\pi^{2}}\;\frac{3N_{c}}{2\varepsilon}+\mathcal{O}(g^{4}),$
(21) $\displaystyle Z_{TT}^{{\rm DR},\overline{\rm MS}}$ $\displaystyle=$
$\displaystyle
1-\frac{g^{2}}{16\,\pi^{2}}\;\frac{3N_{c}}{\varepsilon}+\mathcal{O}(g^{4}),$
(22) $\displaystyle Z_{\mathcal{O}}^{{\rm DR},\overline{\rm MS}}$
$\displaystyle=$ $\displaystyle
1-\frac{g^{2}}{16\,\pi^{2}}\;\frac{3N_{c}}{\varepsilon}+\mathcal{O}(g^{4}),$
(23)

which agree with our recent one-loop calculations in Refs. [6, 5]. By
combining our one-loop results for the mixing matrix in ${\rm GIRS}$ Eqs. (17)
and in $\overline{\rm MS}$ Eqs. (19 – 22), we extract the one-loop conversion
factors

$\displaystyle C_{SS}^{{\rm GIRS},\ \overline{\rm MS}}$
$\displaystyle=1-\frac{g^{2}_{\overline{\rm
MS}}}{16\pi^{2}}\frac{17N_{c}}{6}+\mathcal{O}(g^{4}_{\overline{\rm MS}}),$
(24) $\displaystyle C_{ST}^{{\rm GIRS},\ \overline{\rm MS}}$
$\displaystyle=\frac{g^{2}_{\overline{\rm
MS}}}{16\pi^{2}}4N_{c}+\mathcal{O}(g^{4}_{\overline{\rm MS}}),$ (25)
$\displaystyle C_{TS}^{{\rm GIRS},\ \overline{\rm MS}}$
$\displaystyle=-\frac{g^{2}_{\overline{\rm
MS}}}{16\pi^{2}}\frac{3N_{c}}{2}\left(\frac{2}{3}+2\gamma_{E}+\ln(\bar{\mu}^{2}a\
t^{2})\right)+\mathcal{O}(g^{4}_{\overline{\rm MS}}),$ (26) $\displaystyle
C_{TT}^{{\rm GIRS},\overline{\rm MS}}$
$\displaystyle=1+\frac{g^{2}_{\overline{\rm
MS}}}{16\pi^{2}}N_{c}\left(\frac{7}{6}+6\gamma_{E}+3\ln(\bar{\mu}^{2}a\
t^{2})\right)+\mathcal{O}(g^{4}_{\overline{\rm MS}}).$ (27)

##  5 Non-perturbative results

For the lattice discretization of $\mathcal{N}=1$ SYM we employed: a tree-
level Symanzik improved gauge action and Wilson fermions for the gluino
fields. The action reads222 ${\rm tr}_{c}$ denotes trace over color matrices.

$\displaystyle{\cal S}^{L}_{\rm SYM}=\sum_{x}\Bigg{\\{}$
$\displaystyle\frac{2a^{4}}{g^{2}}\left[\frac{5}{3}\sum_{\rm plaq.}{\rm Re}\
{\rm tr}_{c}(1-U_{\rm plaq.})-\frac{1}{12}\sum_{\rm rect.}{\rm Re}\ {\rm
tr}_{c}(1-U_{\rm
rect.})\right]+\sum_{y}\frac{a^{3}}{2\kappa}\bar{\lambda}(x)D_{W}\lambda(y)\Bigg{\\}},$

where, $U_{\rm plaq.}(U_{\rm rect.})$ denotes $1{\times}1$ ($2{\times}1$)
rectangular Wilson loops and the lattice Wilson operator is represented in
terms of the hopping parameter $\kappa\equiv 1/(2m_{0}+8)$ as

$D_{W}=1-\kappa\big{[}(1-\gamma_{\mu})(V_{\mu}(x))\delta_{x+\mu,y}+(1+\gamma_{\mu})(V^{\dagger}{}_{\mu}(x-\mu))\delta_{x-\mu,y}\big{]}.$
(29)

One-level of stout smearing was used on the links $V_{\mu}(x)$, which in the
adjoint representation are given by $V_{\mu}^{ab}=2\,{\rm
tr_{c}}[U^{\dagger}_{\mu}(x)T^{a}U_{\mu}(x)T^{b}]$.

We considered the configurations from earlier works [3, 7] with ensembles
based on two different gauge groups $SU(2)$ and $SU(3)$. In case of the gauge
group $SU(3)$ the lattice action is different, see [7] for details. The
ensembles were generated at two different lattice sizes $V=L^{3}\times T$ of
$V_{1}=24^{3}\times 48$ and $V_{2}=32^{3}\times 64$ along with different
values of the coupling constant $\beta$ and different mass parameters
$\kappa$. As the behaviour of the renormalization constant did not change
qualitatively from the different ensembles, we will present here the ones
based on the $SU(2)$ group with a lattice size of $V_{1}=24^{3}\times 48$, two
different mass parameters $\kappa=0.14925,\ 0.14920$ and a gauge coupling of
$\beta=1.75$. The complete set of results for all ensembles are collected in
[8]. For comparison of the results, the lattice spacing can be estimated using
the QCD Sommer scale value $r_{0}=0.5\text{ fm}$ which leads to a lattice
spacing of $a=0.0554(11)\text{ fm}$.

The supercurrent and $\mathcal{O}$ operators are represented on the lattice
using clover plaquettes $\hat{F}_{\mu\nu}^{\alpha\beta}(x,t)$ and gluino
fields $\lambda(x)$. The correlators between $S_{\mu}$, $T_{\mu}$, and
$\mathcal{O}$ take the following generic omitting Lorentz, spinor and color
indices

$\langle A(t)\overline{B}(0)\rangle\equiv\sum_{\vec{x},\vec{y}}\langle
A(\vec{x},t)\overline{B}(\vec{y},0)\rangle=\sum_{\vec{x},\vec{y}}\langle{\rm
Tr}[\Gamma\hat{F}(\vec{x},t)D^{-1}(\vec{x},t|\vec{y},0)\hat{F}(\vec{y},0)\Gamma^{\prime}]\rangle_{G}=C^{\alpha\beta},$
(30)

for $A,B=S_{\mu},T_{\mu},\mathcal{O}$. The expectation value
$\langle\cdot\rangle_{G}$ indicates that the fermion has been integrated out.
$\Gamma$ and $\Gamma^{\prime}$ collect the combination of gamma matrices of
each operator and the inverse of the Dirac operator $D^{-1}(x|y)$ propagates a
gluino from $x$ to $y$. In order to use the set of four GIRS conditions Eq.
(9–12) we are constrained to use spatial projectors
$P_{i}=\gamma_{4}\gamma_{i}$ and $P_{ij}=\gamma_{i}\gamma_{4}\gamma_{j}$ with
$i=1,2,3$. We chose $i=j$ which has the advantage of giving better signal to
noise ratio. As an example we present two of the correlators in Fig. 2.

t$\text{Tr}\langle\mathcal{O}(t)S_{i}(0)P_{i}\rangle$

t$\text{Tr}\langle\mathcal{O}(t)T_{i}(0)P_{i}\rangle$

Figure 2: Correlators $\text{Tr}\langle\mathcal{O}(t)S_{i}(0)P_{i}\rangle$ and
$\text{Tr}\langle\mathcal{O}(t)T_{i}(0)P_{i}\rangle$ computed numerically on
the ensemble with $\kappa=0.14925$ and $\beta=1.75$ of the $V=24^{3}\times 48$
lattice.

Due to the gauge nature of these operators one is expected to find a
substantial amount of noise on the signal. To improve the signal we used
isotropy, time reversal, and charge conjugation to average equivalent
correlators. We used wall sources for the operators and we average over
spatial positions of the sink. This amounts to summing up over all $\vec{x}$
and $\vec{y}$ contributions of the correlator. Using the GIRS conditions which
on the lattice take the following form

$\displaystyle\frac{1}{3L^{3}}\sum_{\vec{x},\vec{y}}\sum_{i}\ {\rm
Tr}\left[G^{SS,\,{\rm GIRS}}_{ii}((\vec{x},t),(\vec{y},0))\
\gamma_{i}\gamma_{4}\gamma_{i}\right]$ $\displaystyle=$
$\displaystyle\frac{2(N_{c}^{2}-1)t}{\pi^{2}{|t|}^{5}},$ (31)
$\displaystyle\frac{1}{3L^{3}}\sum_{\vec{x},\vec{y}}\sum_{i}\ {\rm
Tr}\left[G^{TT,\,{\rm GIRS}}_{ii}((\vec{x},t),(\vec{y},0))\
\gamma_{i}\gamma_{4}\gamma_{i}\right]$ $\displaystyle=$
$\displaystyle\frac{5(N_{c}^{2}-1)t}{4\pi^{2}{|t|}^{5}},$ (32)
$\displaystyle\frac{1}{3L^{3}}\sum_{\vec{x},\vec{y}}\sum_{i}\ {\rm
Tr}\left[G^{ST,\,{\rm GIRS}}_{ii}((\vec{x},t),(\vec{y},0))\
\gamma_{i}\gamma_{4}\gamma_{i}\right]$ $\displaystyle=$
$\displaystyle\frac{(N_{c}^{2}-1)t}{\pi^{2}{|t|}^{5}},$ (33)
$\displaystyle\frac{1}{3L^{3}}\sum_{\vec{x},\vec{y}}\sum_{i}\ {\rm
Tr}\left[G^{S{\cal O},\,{\rm GIRS}}_{i}((\vec{x},t),(\vec{y},0))\
\gamma_{4}\gamma_{i}\right]$ $\displaystyle=$ $\displaystyle 0.$ (34)

Again these conditions lead to a set of second order equations for the
renormalization factors $Z$ similar to Eq. (17) but in their lattice
discretized versions.

In GIRS the time separation $t$ represents an energy scale for the
renormalization constants. The short distance part is dominated by contact
terms and lattice artifacts and has to be neglected. We use the conversion
factors explained in previous sections to convert GIRS to $\overline{\rm MS}$
scheme. This is expected to replace the dependence on the GIRS scale with the
the one on the $\overline{\mu}$ energy scale of the $\overline{\rm MS}$
scheme. After the conversion, a plateau like behaviour is expected at larger
distances and the dependence on time separation is replaced by a dependence on
the energy scale. More importantly, converting to the $\overline{\rm MS}$
scheme will allow us to compare directly with other results in perturbation
theory.

The result after applying the conversion factors to the $Z_{ST}/Z_{SS}$ factor
is shown in Fig. 3. We fitted the data points in time interval $t\in[5,11]$
where contact terms have decayed and the noise has still not overcome the
signal. The value obtained is $Z_{ST}/Z_{SS}=-0.0418(84)$ while the
perturbative one found in [5] but without clover improvement is
$Z_{ST}/Z_{SS}=0.10080$.

##  6 Summary and conclusions

We studied the renormalization of the supercurrent for $\mathcal{N}=1$ SYM. We
extracted the renormalization factors for the $S_{\mu}$ and $T_{\mu}$
operators in the GIRS scheme from bare correlators computed numerically on the
lattice. By finding the conversion factors $C^{GIRS,\overline{\rm MS}}$
perturbatively, we translated the non-perturbative results to the
$\overline{\rm MS}$ scheme where we could compare to perturbation theory.

We observed a significant disagreement between the perturbative and non-
perturbative determination of the $Z$ factors. Yet we have room for
improvement: simulating closer to the perturbative regime, including two-loop
terms in the perturbative computation or including smearing could improve the
agreement. They are feasible albeit complicated tasks, without any conceptual
hindrances.

It is worth reiterating at this point that the determination of $Z_{ST}^{{\rm
L},\overline{\rm MS}}/Z_{SS}^{{\rm L},\overline{\rm MS}}$ via GIRS, despite
the present discrepancy with perturbative estimates, stands to be very useful
in the study of more complicated theories, such as supersymmetric QCD, for the
purpose of reducing the number of undetermined parameters in Ward identities.

Acknowledgements: M.C., H.P. and G.S. acknowledge financial support from the
European Regional Development Fund and the Cyprus Research and Innovation
Foundation (Projects: EXCELLENCE/0918/0066 and EXCELLENCE/0421/0025. M.C. also
acknowledges partial support from the Cyprus University of Technology under
the "POSTDOCTORAL" program. G.S acknowledges financial support from H2020
project PRACE-6IP (Grant agreement ID: 823767). G.B. and I.S. acknowledge
financial support from the Deutsche Forschungsgemeinschaft (DFG) Grant No.
432299911 and 431842497

GIRS schemet$Z_{ST}/Z_{SS}$

$\overline{\rm MS}$ schemet

Figure 3:  $V=24^{3}\times 48$ lattice with $\kappa=0.14925$ (blue dots) and
$\kappa=0.14920$ (orange squares). The points on the $\kappa=0.14920$ ensemble
are shifted in $t$ by $+0.33$ for visibility. The error bars were estimated by
a jackknife analysis and measurements were done every 8th step on Monte-Carlo
time to reduce autocorrelations.

## References

  * [1] G. Curci and G. Veneziano, _Supersymmetry and the Lattice: A Reconciliation?_ , _Nucl. Phys. B_ 292 (1987) 555-572.
  * [2] S. Ali et al., _Analysis of Ward identities in supersymmetric Yang-Mills theory_ , _Eur. Phys. J. C_ 78 (2018) 404 [hep-lat/1802.07067].
  * [3] G. Bergner, P. Giudice, G. Münster, I. Montvay and S. Piemonte, _The light bound states of supersymmetric $SU(2)$ Yang-Mills theory_, _JHEP_ 03 (2016) 080 [hep-lat/1512.07014].
  * [4] M. Costa et al., _Gauge-invariant renormalization scheme in QCD: Application to fermion bilinears and the energy-momentum tensor_ , _Phys. Rev. D_ 103 (2021) 094509 [hep-lat/2102.00858].
  * [5] G. Bergner, M. Costa, H. Panagopoulos, I. Soler and G. Spanoudes, _Perturbative renormalization of the supercurrent operator in lattice N=1 supersymmetric Yang-Mills theory_ , _Phys. Rev. D_ 106 (2022) 034502 [hep-lat/2205.02012].
  * [6] M. Costa, H. Herodotou, P. Philippides and H. Panagopoulos, _Renormalization and mixing of the Gluino-Glue operator on the lattice_ , _Eur. Phys. J. C_ 81 (2021), 401 [hep-lat/2010.02683].
  * [7] S. Ali, G. Bergner, H. Gerber, I. Montvay, G. Münster, S. Piemonte and P. Scior, _Numerical results for the lightest bound states in $\mathcal{N}=1$ supersymmetric SU(3) Yang-Mills theory_, _Phys. Rev. Lett._ 122 (2019) 221601 [hep-lat/1902.11127].
  * [8] G. Bergner, M. Costa, H. Panagopoulos, S. Piemonte, I. Soler and G. Spanoudes, _Nonperturbative renormalization of the supercurrent in $\mathcal{N}=1$ Supersymmetric Yang-Mills Theory_, [hep-lat/2209.13934].


$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\sigma^{-1}(V(Z_{p,q}))$
belongs to
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X_{p}\cup
X_{q}$ and the required follows as
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(P_{p,q})\subseteq\sigma^{-1}(V(Z_{p,q}))$.
This completes the proof that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$ is a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.

We now prove that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$ is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-normal. Recall that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\cal
A$ be a c-diameter partition of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.
Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
be a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\cal
A$-cloud and let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}=\sigma(C)$
be a subset of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V({\Gamma})$.
As
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
is of diameter at most
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$,
then, from Observation 4,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}$
is also of diameter at most
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$.
Notice that if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
intersects some member
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W$
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
W}$, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}=\sigma(C)$
also intersects
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\sigma(W)$,
therefore
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}$
intersects some element of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q_{\rm
in}\cup Q_{\rm out}$. Assume
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}$
contains
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p\in
Q_{\rm in}\cup Q_{\rm out}$, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}\subseteq
N_{p}$. From Observation 4,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C\subseteq
X_{p}=\alpha(W_{p})$, therefore
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
satisfies Condition (A).

By construction, the distance in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\Gamma}$
between two elements of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q_{\rm
in}$ is either
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}2c+1$
or at least
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}4c+2$.
The distance in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\Gamma}$
between on elements of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q_{\rm
in}$ and any element of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q_{\rm
out}$ is a multiple of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}2c+1$.
This implies that if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p,q\in
Q$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p\not=q$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}N_{p}\cap
C^{\prime}\not=\emptyset$, and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}N_{q}\cap
C^{\prime}\not=\emptyset$, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q$
are linked.

By construction, if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q$
are linked, then for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}r\in
Q$ and every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}u\in
Z_{p,q}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
dist}_{\Gamma}(r,u)\geq\min({\bf dist}_{\Gamma}(r,p),{\bf dist}_{G}(r,q))$,
where for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}x\in
Q_{\rm in}$, the quantity
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
dist}_{{\Gamma}}(x,b_{\rm out})$ is interpreted as
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\min\\{{\bf
dist}_{\Gamma}(x,q^{\prime})\mid{q^{\prime}\in Q_{\rm out}}\\}$. This implies
that if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}$
intersects
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p,q}$
for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p,q\in
Q$, then for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}r\in
Q\setminus\\{p,q\\}$, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}$
does not intersect
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}N_{r}$.
We will use this fact in the next paragraph towards completing the proof of
Condition (B).

We now claim that if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}$
intersects two distinct paths in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{Z_{p,q}\mid(p,q)\in
Q^{2},p\neq q\\}$, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}$
intersects at most one of the sets in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{N_{q^{\prime}}\mid
q^{\prime}\in Q\\}$. Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p,q}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p^{\prime},q^{\prime}}$
be two distinct paths intersected by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}$.
We argue first that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p,q,p^{\prime},q^{\prime}$
cannot be all different. Indeed, if this is the case, as
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}$
intersects
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p,q}$
then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}$
cannot intersect
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}N_{p^{\prime}}$
or
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}N_{q^{\prime}}$
as
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p^{\prime},q^{\prime}\not\in\\{p,q\\}$.
As
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p^{\prime},q^{\prime}}\subseteq
N_{q^{\prime}}\cup N_{p^{\prime}}$, we have a contradiction. Assume now that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p=p^{\prime}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q\not=q^{\prime}$.
As
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}$
intersects
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p,q}$,
then it does not intersect
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}N_{r}$
for any
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}r\in
Q\setminus\\{p,q\\}$, and as it intersects
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p,q^{\prime}}$,
then it does not intersect
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}N_{r}$
for any
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}r\in
Q\setminus\\{p,q^{\prime}\\}$. We obtain that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{\prime}$
intersects at most one of the sets in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{N_{r}\mid
r\in Q\\}$ that is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}N_{p}$.
By definition of the states, we obtain that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
shadows at most one state that is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X_{p}$.
That completes the proof of condition (B). ∎

We define bellow three ways to transform a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.
In each of them,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}=({\cal X},\alpha,{\cal R},\beta)$ is an
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-normal
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
is an
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-cloud in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
front}_{\cal A}({\cal S})$.

  * 1.

The expansion procedure applies when
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
intersects at least two freeways of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$. Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X$
be the state of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$ shadowed by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
(this state is unique because of property (B) of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{A}$-normality).
We define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}({\cal
X}^{\prime},\alpha^{\prime},{\cal R}^{\prime},\beta^{\prime})={\sf
expand}({\cal S},C)$ such that

    * –

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
X}^{\prime}={\cal X}\setminus\\{X\\}\cup\\{X\cup C\\}$,

    * –

for each
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W\in{\cal
W}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\alpha^{\prime}(W)=X^{\prime}$
where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X^{\prime}$
is the unique set of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
X}^{\prime}$ such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W\subseteq
X^{\prime}$,

    * –

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
R}^{\prime}={\cal R}$, and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\beta^{\prime}=\beta$.

  * 2.

The clash procedure applies when
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
intersects exactly one freeway
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P$
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$. Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X_{1},X_{2}$
be the two states of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$ that intersect this freeway. Notice that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P=\beta(\alpha^{-1}(X_{1}),\alpha^{-1}(X_{2}))$,
as it is the only freeway with vertices in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X_{1}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X_{2}$.
Assume that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(C\cap
V(P))\cap X_{1}\not=\emptyset$ (if, not, then swap the roles of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X_{1}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X_{2}$).
We define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}({\cal
X}^{\prime},\alpha^{\prime},{\cal R}^{\prime},\beta^{\prime})={\sf
clash}({\cal S},C)$ as follows:

    * –

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
X}^{\prime}=\\{X_{1}\cup C\\}\cup\bigcup_{X\in{\cal
X}\setminus\\{X_{1}\\}}\\{{\sf cc}_{G}(X\setminus C,\alpha^{-1}(X))\\}$
(notice that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\alpha^{-1}(X)\subseteq
X\setminus C$, for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X\in{\cal
X}$, because of property (A) of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-normality),

    * –

for each
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W\in{\cal
W}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\alpha^{\prime}(W)=X^{\prime}$
where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X^{\prime}$
is the unique set of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
X}^{\prime}$ such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W\subseteq
X^{\prime}$,

    * –

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
R}^{\prime}={\cal R}\setminus\\{P\\}\cup\\{P^{\prime}\\}$, where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P^{\prime}=P_{1}\cup
P^{*}\cup P_{2}$ is defined as follows: let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}s_{i}$
be the first vertex of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
that we meet while traversing
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P$
when starting from its endpoint that belongs in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{i}$
and let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P_{i}$
the subpath of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P$
that we traversed that way, for
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}i\in\\{1,2\\}$.
We define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P^{*}$
by taking any path between
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}s_{1}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}s_{2}$
inside
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G[C]$,
and

    * –

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\beta^{\prime}=\beta\setminus\\{(\\{W_{1},W_{2}\\},P)\\}\cup\\{\\{W_{1},W_{2}\\},P^{\prime}\\}$.

  * 3:

The annex procedure applies when
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
intersects no freeway of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$ and touches some country
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X\in{\cal
X}$. We define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}({\cal
X}^{\prime},\alpha^{\prime},{\cal R}^{\prime},\beta^{\prime})={\sf anex}({\cal
S},C)$ such that

    * –

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
X}^{\prime}=\\{X_{1}\cup C\\}\cup\bigcup_{X\in{\cal
X}\setminus\\{X_{1}\\}}\\{{\sf cc}_{G}(X\setminus C,\alpha^{-1}(X))\\}$
(notice that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\alpha^{-1}(X)\subseteq
X\setminus C$, for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X\in{\cal
X}$, because of property (A) of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-normality),

    * –

for each
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W\in{\cal
W}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\alpha^{\prime}(W)=X^{\prime}$
where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X^{\prime}$
is the unique set of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
X}^{\prime}$ such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W\subseteq
X^{\prime}$,

    * –

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
R}^{\prime}={\cal R}$, and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\beta^{\prime}=\beta$.

######  Claim .

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}=({\cal X},\alpha,{\cal R},\beta)$ be an
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-normal
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C\in{\sf
front}_{\cal A}({\cal S})$. Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}^{\prime}={\sf action}({\cal S},C)$ where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
action}\in\\{{\sf expand},{\sf clash},{\sf anex}\\}$. Then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}^{\prime}$ is an
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-normal
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cost}({\cal S^{\prime}},{\cal A})\leq{\sf cost}({\cal S},{\cal A})$. Moreover,
if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cov}_{\cal S}(C)\geq 1$, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cost}({\cal S^{\prime}},{\cal A})<{\sf cost}({\cal S},{\cal A})$ and if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cov}_{\cal S}(C)=0$ (which may be the case only when
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
action}={\sf anex}$), then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|{\sf
indep}({\cal S^{\prime}})|<|{\sf indep}({\cal S})|$.

###### Proof of Claim 4.2..

We first show that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}^{\prime}$
is an
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-normal
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.
In each case, the construction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}^{\prime}$ makes sure that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
X^{\prime}}$ is a connected packing of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and that the countries are updated in a way that their capitals remain inside
them. Moreover, the highways are updated so to remain internally disjoint and
inside the corresponding updated countries. We next prove that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}^{\prime}$
is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{A}$-normal.
Condition (A) is invariant as the cloud we take into consideration cannot
intersect any
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W\in{\cal
W}$ and a cloud intersecting some capital
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W\in{\cal
W}$ cannot be disconnected from
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W$.
It now remains to prove condition (B). Because of Condition 4 of the
definition of a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration, if a cloud
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
intersects a freeway, then it shadows at least one state. Now assume that a
cloud
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
intersects two freeways in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}^{\prime}$,
then by construction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}^{\prime}$,
it also intersects at least the two same freeways in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}$.
This along with the fact that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}$
satisfies Condition (B), implies that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}^{\prime}$
satisfies condition (B) as well, as required.

Notice that, for any cloud
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{*}\in{\cal
A}\setminus\\{C\\}$, if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{*}$
does not intersect a state
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X$
in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$, then the corresponding state
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X^{\prime}$
in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}^{\prime}$, i.e., the state
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X^{\prime}=\alpha^{\prime}(\alpha^{-1}(X))$,
also does not intersect
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C^{*}$.
This means that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cost}({\cal S^{\prime}},{\cal A})\leq{\sf cost}({\cal S},{\cal A})$.

Notice now that by the construction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}^{\prime}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
is not in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
front}_{\cal A}({\cal S}^{\prime})$. In the case where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cov}_{\cal S}(C)\geq 1$ we have that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cost}({\cal S^{\prime}},{\cal A})<{\sf cost}({\cal S},{\cal A})$.

Notice that the case where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cov}_{\cal S}(C)=0$ happens only when
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
action}={\sf anex}$ and there is an edge with one endpoint in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
and one in some country
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X^{*}$
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$ that does not intersect
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$.
Moreover
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cc}_{G}(X\setminus C,\alpha^{-1}(X))=X$, for every state
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X$
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$. This implies that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
indep}(\mathcal{S}^{\prime})\subseteq{\sf indep}(\mathcal{S})$. As
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C\subseteq{\sf
indep}(\mathcal{S})$ and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C\cap{\sf
indep}(\mathcal{S}^{\prime})=\emptyset$, we conclude that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|{\sf
indep}(\mathcal{S}^{\prime})|<|{\sf indep}(\mathcal{S})|$ as required. ∎

To continue with the proof of Subsection 4.2 we explain how to transform the
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-normal
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$ of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
to a complete one. This is done in two phases. First, as long as there is an
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-cloud
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C\in{\sf
front}({\cal S})$ where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cov}_{\cal S}({C})\geq 1$, we apply one of the above three procedures
depending on the number of freeways intersected by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$.
We again use
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$ to denote the
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-normal
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
that is created in the end of this first phase. Notice that, as there is no
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-cloud with
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cov}_{\cal S}({C})\geq 1$, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cost}_{\cal A}({\cal S})=0$. The second phase is the application of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
anex}({\cal S},C)$, as long as some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C\in{\sf
front}_{\cal A}({\cal S})$ is touching some of the countries of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$. We claim that this procedure will be applied as long as there are
vertices in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
indep}(\mathcal{S})$. Indeed, if this is the case, the set
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
front}_{\cal A}({\cal S})$ is non-empty and by the connectivity of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
there is always a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C\in{\sf
front}_{\cal A}({\cal S})$ that is touching some country of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$. Therefore, as
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cost}_{\cal A}({\cal S})=0$ (by Claim 4.2), procedure
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
anex}({\cal S},C)$ will be applied again.

By Claim 4.2,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|{\sf
indep}(\mathcal{S})|$ is strictly decreasing during the second phase. We again
use
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$ for the final outcome of this second phase. We have that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
indep}(\mathcal{S})=\emptyset$ and we conclude that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$ is a complete
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-normal
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|{\sf
front}_{\cal A}({\cal S})|=0$.

We are now going to create a graph isomorphic to
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$
only by doing contractions in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.
For this we use
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}$,
a complete
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-normal
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|{\sf
front}_{\cal A}({\cal S})|=0$, obtained as describe before. We contract in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
every country of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}$
into a unique vertex. This can be done because the countries of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}$
are connected. Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$
be the resulting graph. By construction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$
is a contraction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$.
Because of Condition
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}4$
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration, every freeway of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}$
becomes an edge in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$.
This implies that there is a graph isomorphic to
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$
that is a subgraph of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$.
So
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{\Gamma}_{k^{\prime}}$
is isomorphic to a subgraph of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$
with the same number of vertices. Let see
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{\Gamma}_{k^{\prime}}$
as a subgraph of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$
and let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}e$
be an edge of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$
that is not an edge of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{\Gamma}_{k^{\prime}}$.
As
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}e$
is an edge of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$,
this implies that in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
there is two states of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}$
such that there is no freeway between them but still an edge. This is not
possible by construction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{S}$.
We deduce that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$
is isomorphic to
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{\Gamma}_{k^{\prime}}$.
Moreover, as
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|{\sf
front}_{\cal A}({\cal S})|=0$, then every cloud is a subset of a country. This
implies that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$
is also a contraction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$.
By contracting in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$
the edge corresponding to
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{a,({k^{\prime}-1,k^{\prime}-1})\\}$
in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{\Gamma}_{k^{\prime}}$,
we obtain that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{k^{\prime}}$
is a contraction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$.
Subsection 4.2 follows. ∎

###### Proof of Subsection 1.4.

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\lambda$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c_{1}$,
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c_{2}$
be integers. It is enough to prove that there exists an integer
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\lambda^{\prime}=\mathcal{O}(\lambda\cdot
c_{1}\cdot(c_{2})^{c})$ such that for every graph class
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{G}\in\mbox{\rm
SQGC}(c)$,

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\displaystyle\forall
G\in\mathcal{G}\ $
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\displaystyle{\sf
tw}(G)\leq\lambda\cdot({\bf bcg}(G))^{c}$
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\displaystyle\Rightarrow$
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\displaystyle\forall
F\in\mathcal{G}^{(c_{1},c_{2})}\ $
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\displaystyle{\sf
tw}(F)\leq\lambda^{\prime}\cdot({\bf bcg}(F))^{c}.$

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{G}\in\mbox{\rm
SQGC}(c)$ be a class of graph such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\forall
G\in\mathcal{G}\ \ {\sf tw}(G)\leq\lambda\cdot({\bf bcg}(G))^{c}$. Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\in\mathcal{G}^{(c_{1},c_{2})}$
and let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}J$
be two graphs such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G\in\mathcal{G}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G\leq^{(c_{1})}J\mbox{,
and }H\leq^{c_{2}}J$.
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}J$
exist by definition of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{G}^{(c_{1},c_{2})}$.

  * •

By definition of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}J$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
tw}(H)\leq{\sf tw}(J)$.

  * •

By Section 2,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
tw}(J)\leq(c_{1}+1)({\sf tw}(G)+1)-1$.

  * •

By definition of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{G}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
tw}(G)\leq\lambda\cdot{\bf bcg}(G)^{c}$.

  * •

By Subsection 4.2,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
bcg}(G)\leq(2c_{2}+1)({\bf bcg}(H)+2)+1$.

If we combine these four statements, we obtain that

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
tw}(H)\leq(c_{1}+1)(\lambda\cdot[(2c_{2}+1)({\bf bcg}(H)+2)+1]^{c}+1)-1.$

As the formula is independent of the graph class, the Subsection 1.4 follows.∎

##  5 Conclusions, extensions, and open problems

The main combinatorial result of this paper is that, for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$
and every apex-minor-free graph class
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$, the intersection class
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}_{d}({\cal G})$ has the SQGC property for
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c=1$.
Certainly, the main general question is to detect even wider graph classes
with the SQGM/SQGC property. In this direction, some insisting open issues are
the following:

  * •

Is the bound on the (multi-)degree necessary? Are there classes of
intersection graphs with unbounded or “almost bounded” maximum degree that
have the SQGM/SQGC property?

  * •

All so far known results classify graph classes in SQGM(1) or SQGC(1). Are
there (interesting) graph classes in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGM}(c)$ or
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGC}(c)$ for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1<c<2$
that do not belong in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGM}(1)$ or
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGC}(1)$ respectively? An easy (but trivial) example of such a class is the
class
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
Q}_{d}$ of the q-dimensional grids, i.e., the cartesian products of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q\geq
2$ equal length paths. It is easy to see that the maximum
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}k$
for which an
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}n$-vertex
graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G\in{\cal
Q}_{q}$ contains a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(k\times
k)$-grid as a minor is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}k=\Theta(n^{\frac{1}{2}})$.
On the other size, it can also be proven that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
tw}(G)=\Theta(n^{\frac{q-1}{q}})$. These two facts together imply that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
Q}_{q}\in\mbox{\rm SQGM}(2-\frac{2}{q})$ while
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
Q}_{q}\not\in\mbox{\rm SQGM}(2-\frac{2}{q}-\epsilon)$ for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\epsilon>0$.

  * •

Usually the graph classes in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGC}(1)$ are characterised by some “flatness” property. For instance, see the
results in [31, 34, 34] for
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$-minor
free graphs, where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is an apex graph. Can
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGC}(1)$ be useful as an intuitive definition of the “flatness” concept? Does
this have some geometric interpretation?

## References

  * [1] Stefan Arnborg, Jens Lagergren, and Detlef Seese.  Easy problems for tree-decomposable graphs.  Journal of Algorithms, 12:308–340, 1991.
  * [2] Julien Baste and Dimitrios M. Thilikos.  Contraction-bidimensionality of geometric intersection graphs.  In Daniel Lokshtanov and Naomi Nishimura, editors, 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 6-8, 2017, Vienna, Austria, volume 89 of LIPIcs, pages 5:1–5:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  doi:10.4230/LIPIcs.IPEC.2017.5.
  * [3] Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof.  Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth.  Information and Computation, 243:86–111, 2015.
  * [4] Julia Chuzhoy and Zihan Tan.  Towards tight(er) bounds for the excluded grid theorem.  J. Comb. Theory, Ser. B, 146:219–265, 2021.  doi:10.1016/j.jctb.2020.09.010.
  * [5] Bruno Courcelle.  The monadic second-order logic of graphs. I. Recognizable sets of finite graphs.  Information and Computation, 85(1):12–75, 1990.
  * [6] Bruno Courcelle.  The expression of graph properties and graph transformations in monadic second-order logic.  Handbook of Graph Grammars, pages 313–400, 1997.
  * [7] Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk.  Solving connectivity problems parameterized by treewidth in single exponential time.  In Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), pages 150–159, 2011.
  * [8] Erik D. Demaine.  Algorithmic Graph Minors and Bidimensionality.  In Proceedings of the 36th International Conference on Graph-theoretic Concepts in Computer Science (WG 2010), pages 2–2, 2010.
  * [9] Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos.  Bidimensional parameters and local treewidth.  SIAM Journal on Discrete Mathematics, 18(3):501–511, 2005.
  * [10] Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos.  Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs.  Journal of the ACM, 52(6):866–893, 2005.
  * [11] Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos.  Bidimensional structures: Algorithms, combinatorics and logic.  Dagstuhl Reports, 3(3):51–74, 2013.
  * [12] Erik D. Demaine and MohammadTaghi Hajiaghayi.  Fast algorithms for hard graph problems: Bidimensionality, minors, and local treewidth.  In Proceedings of the 12th International Symposium on Graph Drawing (GD 2004), volume 3383 of LNCS, pages 517–533, 2004.
  * [13] Erik D. Demaine and MohammadTaghi Hajiaghayi.  Bidimensionality: New connections between FPT algorithms and PTASs.  In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 590–601, 2005.
  * [14] Erik D. Demaine and MohammadTaghi Hajiaghayi.  The bidimensionality theory and its algorithmic applications.  The Computer Journal, 51(3):292–302, 2008.
  * [15] Erik D. Demaine and MohammadTaghi Hajiaghayi.  Linearity of grid minors in treewidth with applications through bidimensionality.  Combinatorica, 28(1):19–36, 2008.
  * [16] Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos.  The bidimensional theory of bounded-genus graphs.  SIAM Journal on Discrete Mathematics, 20(2):357–371, 2006.
  * [17] Reinhard Diestel, Tommy R. Jensen, Konstantin Yu. Gorbunov, and Carsten Thomassen.  Highly connected sets and the excluded grid theorem.  Journal of Combinatorial Theory. Series B, 75(1):61–73, 1999.
  * [18] Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos.  Fast subexponential algorithm for non-local problems on graphs of bounded genus.  In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), volume 4059 of LNCS, pages 172–183, 2006.
  * [19] Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos.  Catalan structures and dynamic programming in $\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$-minor-free graphs.  In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pages 631–640, 2008.
  * [20] Fedor V. Fomin, Erik D. Demaine, and MohammadTaghi Hajiaghayi.  Bidimensionality.  In Encyclopedia of Algorithms. Springer, 2015.
  * [21] Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos.  Contraction obstructions for treewidth.  Journal of Combinatorial Theory. Series B, 101(5):302–314, 2011\.
  * [22] Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh.  Bidimensionality and EPTAS.  In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pages 748–759, 2011.
  * [23] Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh.  Bidimensionality and geometric graphs.  In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 1563–1575, 2012.
  * [24] Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh.  Efficient computation of representative sets with applications in parameterized and exact algorithms.  In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pages 142–151, 2014.
  * [25] Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh.  Excluded grid minors and efficient polynomial-time approximation schemes.  J. ACM, 65(2):10:1–10:44, 2018.  doi:10.1145/3154833.
  * [26] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos.  Bidimensionality and kernels.  In Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 503–510, 2010.
  * [27] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos.  Bidimensionality and kernels.  CoRR, abs/1606.05689, 2016.
  * [28] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.  Approximation schemes via width/weight trade-offs on minor-free graphs.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2299–2318. SIAM, 2020.  doi:10.1137/1.9781611975994.141.
  * [29] Fedor V. Fomin and Dimitrios M. Thilikos Petr Golovach and.  Contraction bidimensionality: the accurate picture.  In 17th Annual European Symposium on Algorithms, volume 5757 of LNCS, pages 706–717. Springer, 2009.
  * [30] Fanica Gavril.  The intersection graphs of subtrees in trees are exactly the chordal graphs.  Journal of Combinatorial Theory, Series B, 16(1):47–56, 1974.
  * [31] Archontia C. Giannopoulou and Dimitrios M. Thilikos.  Optimizing the graph minors weak structure theorem.  SIAM Journal on Discrete Mathematics, 27(3):1209–1227, 2013.
  * [32] Alexander Grigoriev, Athanassios Koutsonas, and Dimitrios M. Thilikos.  Bidimensionality of Geometric Intersection Graphs.  In Proceedings of the 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), volume 8327 of LNCS, pages 293–305, 2014.
  * [33] Ken-ichi Kawarabayashi and Yusuke Kobayashi.  Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid.  In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), volume 14 of LIPIcs, pages 278–289, 2012.
  * [34] Ken-ichi Kawarabayashi, Robin Thomas, and Paul Wollan.  New proof of the flat wall theorem.  Journal of Combinatorial Theory, Series B, 2017.  To appear.
  * [35] Alexander Leaf and Paul D. Seymour.  Tree-width and planar minors.  Journal of Combinatorial Theory. Series B, 111:38–53, 2015.
  * [36] Jiří Matoušek.  String graphs and separators.  In Geometry, Structure and Randomness in Combinatorics, pages 61–97. Springer, 2014.
  * [37] Michal Pilipczuk.  Problems parameterized by treewidth tractable in single exponential time: A logical approach.  In Proceedings of the 36th International Conference on Mathematical Foundations of Computer Science (MFCS 2011), pages 520–531, 2011\.
  * [38] Neil Robertson and Paul D. Seymour.  Graph Minors. II. Algorithmic aspects of tree-width.  Journal of Algorithms, 7:309–322, 1986.
  * [39] Neil Robertson and Paul D. Seymour.  Graph minors. V. Excluding a planar graph.  Journal of Combinatorial Theory. Series B, 41(1):92–114, 1986.
  * [40] Neil Robertson, Paul D. Seymour, and Robin Thomas.  Quickly excluding a planar graph.  Journal of Combinatorial Theory. Series B, 62(2):323–348, 1994\.
  * [41] Juanjo Rué, Ignasi Sau, and Dimitrios M. Thilikos.  Dynamic programming for H-minor-free graphs.  In Proceedings of Computing and Combinatorics - 18th Annual International Conference, (COCOON 2012), pages 86–97, 2012.
  * [42] Juanjo Rué, Ignasi Sau, and Dimitrios M. Thilikos.  Dynamic programming for graphs on surfaces.  ACM Transactions on Algorithms, 10(2):1–8, 2014.
  * [43] Dimitrios M. Thilikos.  Graph minors and parameterized algorithm design.  In The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, pages 228–256, 2012.
  * [44] Dimitrios M. Thilikos.  Bidimensionality and parameterized algorithms (invited talk).  In 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, pages 1–16, 2015.