# The effect of GREA on the gravitational collapse of neutron stars

Juan García-Bellido<EMAIL_ADDRESS>Instituto de Física Teórica
UAM-CSIC, Universidad Autonóma de Madrid, Cantoblanco 28049 Madrid, Spain

###### Abstract

General Relativistic Entropic Acceleration (GREA) gives a general framework in
which to study multiple out-of-equilibrium phenomena in the context of general
relativity, like the late accelerated expansion of the universe or the
formation of galaxies and the large scale structure of the universe. Here we
analyze the conditions for collapse of a star of degenerate neutrons in the
presence of entropy production due to the gravitational collapse itself. We
find that the final mass and radius of the neutron star differs from that
obtained with the adiabatic Tolman-Oppenheimer-Volkoff equation by a factor of
order 15%. We also find that the minimum mass of a neutron star is $\sim
1.1\,M_{\odot}$ and the maximum mass around $2.4\,M_{\odot}$. We discuss the
possible implications for the search and interpretation of binary coalescing
systems like neutron stars and neutron star-black holes detectable via their
multimessenger (gravitational and electromagnetic wave) emission upon merging.

††preprint: IFT-UAM/CSIC-23-16

##  I I. Introduction

The physics of compact objects like black holes and neutron stars is a topic
of maximum interest for the community, both in astrophysics and fundamental
physics Shapiro and Teukolsky (1983). It encounters the most extreme
environments where gravity is important and where we can test the theory of
general relativity.

The physics of neutron stars (NS) has become an active field of research Faber
and Rasio (2012) thanks to the recent detection of gravitational waves (GW)
from the merger of two neutron stars in GW170817 Abbott et al. (2017), which
has opened the possibility to explore directly the inner structure of neutron
stars and their equation of state Guerra Chaves and Hinderer (2019).

Moreover, the distribution in size and masses of neutron stars has important
consequences for the astrophysics of stellar evolution and their collapse
through supernovae explosions, as well as in the interpretation of GW events
as coming from NSBH binaries or Black Hole (BH) binaries, as in GW190425
Abbott et al. (2020a) and GW190814 Abbott et al. (2020b); Clesse and García-
Bellido (2022).

On the other hand, our understanding of the nature and stability of stars in
general, and neutron stars in particular, rely on specific assumptions about
their equations of state and hydrodynamical equilibrium in the context of
general relativity. These boundary conditions assume the coarsegrained
macroscopic entropy to be conserved upon gravitational collapse. We explore in
this paper the effects that entropic forces associated with gravitational
collapse have on the final state of neutron stars, and in particular their
masses and radii.

While fundamental interactions can be derived from an action principle among
fundamental particles, thermodynamics arises from the coarsegraining of
microscopic degrees of freedom in the context of statistical mechanics, and
can be incorporated into the action as phenomenological constraints. In a
recent work Espinosa-Portales and García-Bellido (2021), we described a
generally covariant formalism for out-of-equilibrium phenomena in the context
of gravitational systems, and thus modified the equations of general
relativity (GR) to include dissipative phenomena and the growth of entropy. We
found that the thermodynamical constraint introduced a new term in the matter
energy-momentum tensor which could be understood as a bulk viscosity term. As
we will describe in the next section, such a viscous term induces a negative
pressure that can account for what we called general relativistic entropic
acceleration (GREA), which could explain the present acceleration of the
universe from first principles García-Bellido and Espinosa-Portales (2021),
without the need to introduce an ad hoc and extremely finetuned cosmological
constant. Such a scenario is consistent with the present cosmological
observations Arjona et al. (2022) and could be tested in the near future with
precise observations from deep galaxy surveys.

In this paper we explore the consequences of GREA on the gravitational
collapse of neutron stars, and we derive a range of allowed masses for neutron
stars that differs from those obtained in the absence of entropy production,
irrespective of the internal equation of state. Present astrophysical data
already suggest that such a range is in better agreement with observations,
and in the future the determination of their masses and radii via the
detection of gravitational waves from BNS mergers will allow one to constrain
better the equation of state in the interior of neutron stars.

##  II II. Gravitational collapse in GREA

Here we descrive the set of equations that we will resolve in the context of
gravitational collapse of degenerate neutron matter when there is entropy
production due to gravitational collapse. The GREA equations are a
modification of GR Espinosa-Portales and García-Bellido (2021)

$G_{\mu\nu}=R_{\mu\nu}-\frac{1}{2}Rg_{\mu\nu}=\kappa\,(T_{\mu\nu}-f_{\mu\nu})\equiv\kappa\,{\cal
T}_{\mu\nu}\,,$ (1)

where $f_{\mu\nu}$ satisfies the thermodynamic constraint

$\frac{\partial{\cal L}_{m}}{\partial S}\delta S=\sqrt{-g}f_{\mu\nu}\delta
g^{\mu\nu}\,,$

arising from the fundamental laws of thermodynamics

$\displaystyle-dW=-\vec{F}\cdot d\vec{x}$ $\displaystyle=$ $\displaystyle
dU+\left(P-T\frac{dS}{dV}\right)dV$ (2) $\displaystyle\equiv$ $\displaystyle
dU+\tilde{P}\,dV$

where we have defined an effective pressure $\tilde{P}$ which reduces to the
usual fluid pressure $P$ in the absence of entropy production. This extra
component to the Einstein equations can be interpreted as an effective bulk
viscosity term of a real (non-ideal) fluid Espinosa-Portales and García-
Bellido (2021)

$f_{\mu\nu}=\zeta\,D_{\lambda}u^{\lambda}\,(g_{\mu\nu}+u_{\mu}u_{\nu})=\zeta\,\Theta\,h_{\mu\nu}\,,$
(3)

such that the covariantly-conserved energy-momentum tensor becomes

$\displaystyle{\cal T}^{\mu\nu}$ $\displaystyle=$ $\displaystyle
P\,g^{\mu\nu}+(\epsilon+P)u^{\mu}u^{\nu}-\zeta\,\Theta\,h^{\mu\nu}$ (4)
$\displaystyle=$
$\displaystyle\tilde{P}\,g^{\mu\nu}+(\epsilon+\tilde{P})u^{\mu}u^{\nu}\,,$ (5)

and, imposing the thermodynamic constraint (2), the bulk viscosity coefficient
$\zeta$ can be written as

$\zeta=\frac{T}{\Theta}\frac{dS}{dV}\,.$ (6)

In the case of an expanding universe, $\Theta=\frac{d}{dt}\ln V=3H$ and the
coefficient becomes $\zeta=T\dot{S}/(9H^{2}a^{3})$, see García-Bellido and
Espinosa-Portales (2021), with $S$ the entropy per comoving volume of the
Universe. Entropy production therefore implies $\zeta>0$.

Note that the energy-momentum tensor is still diagonal, ${\cal T}^{\mu}_{\ \
\nu}={\rm diag}(-\epsilon,\,\tilde{P},\,\tilde{P},\,\tilde{P})$, and that the
$00$ component is unchanged with respect to GR. Only the $ij$ component has
the entropy-growth dependence via $\tilde{P}$.

The Raychaudhuri equation for geodesic motion in the absence of shear
($\sigma=0$) and vorticity ($\omega=0$) is

$\displaystyle\frac{D}{d\tau}\Theta+\frac{1}{3}\Theta^{2}$ $\displaystyle=$
$\displaystyle-\sigma_{\mu\nu}\sigma^{\mu\nu}+\omega_{\mu\nu}\omega^{\mu\nu}-R_{\mu\nu}u^{\mu}u^{\nu}$
$\displaystyle=$
$\displaystyle-\kappa\left(T_{\mu\nu}u^{\mu}u^{\nu}+\frac{1}{2}T^{\lambda}_{\
\,\lambda}-\frac{3}{2}\zeta\Theta\right)$ $\displaystyle=$
$\displaystyle-\frac{\kappa}{2}(\epsilon+3\tilde{P})=-\frac{\kappa}{2}\left(\epsilon+3P-3T\frac{dS}{dV}\right)\,.$

Due to the extra entropic term in the effective pressure $\tilde{P}$, even for
matter that satisfies the strong energy condition, $\epsilon+3P>0$, it is
possible to prevent gravitational collapse, i.e.
$\dot{\Theta}+\Theta^{2}/3>0$, as long as the production of entropy is
significant enough, $3TdS/dV>(\epsilon+3P)>0$.

##  III III. TOV equations in GREA

The gravitational collapse of a fluid of $N$ relativistic particles of mass
$m$ has an associated Boltzmann entropy

$\displaystyle S$ $\displaystyle=$ $\displaystyle k_{\rm B}\,\ln\int\\!\\!\int
d^{3}q_{1}\dots d^{3}q_{N}\,d^{3}p_{1}\dots d^{3}p_{N}\,f(q_{i}\,p_{i})$ (8)
$\displaystyle=$ $\displaystyle k_{\rm
B}\,N\,\ln\left[\frac{V}{N}\left(\frac{\langle
p^{2}\rangle}{4\pi^{2}\hbar^{2}}\right)^{3/2}\right]\,.$

The gravitational collapse of a star occurs far from equilibrium. On the one
hand, the collapse reduces phase-space volume due to the spatial contraction.
On the other hand, the fluid is heated upon contraction and thus increases its
average momentum-squared, $\langle p^{2}\rangle$. If we use the virial theorem
$\langle K\rangle=-\frac{1}{2}\langle V\rangle$ for a bounded system under
gravity,

$\frac{1}{2}m\,\langle v^{2}\rangle=\frac{3}{2}k_{\rm
B}T=\frac{GM(r)m}{2\,r}\,,$ (9)

we see that

$\displaystyle S$ $\displaystyle=$ $\displaystyle k_{\rm
B}\,N\,\ln\left[\frac{V}{N}\left(\frac{3m\,k_{\rm
B}T}{4\pi^{2}\hbar^{2}}\right)^{3/2}\right]$ $\displaystyle=$ $\displaystyle
k_{\rm
B}\,N\,\ln\left[\frac{V}{N}\left(\frac{m^{2}c^{2}}{4\pi^{2}\hbar^{2}}\cdot\frac{GM(r)}{Nc^{2}r}\right)^{3/2}\right]\,.$

and thus the dependence of the entropy on the volume $V$ is always positive,
$dS/dV>0$, and therefore a contraction, $dV<0$, implies a local decrease in
entropy, $dS<0$. The second law of Thermodynamics is ensured by the fact that
the heating of the star upon contraction will induce photon and neutrino
production (via electro-weak interactions) which will radiate away, producing
a flux of entropy out of the star that overall ensures $dS>0$. In most cases,
even matter is shed away in gigantic thermonuclear reactions known as
supernovae.

Let us now study the general relativistic equations that determine the final
state of collapse that leads to a neutron star (NS) with energy density
$\epsilon(\rho)=\rho\,c^{2}+\varepsilon$, and pressure $P(\rho)$, such that
$T^{\mu}_{\ \,\nu}={\rm diag}(-\epsilon,\,P,\,P,\,P)$. Let us assume a metric
for the interior of the star given by

$ds^{2}=-e^{2\Phi(r)}dt^{2}+e^{2\Psi(r)}dr^{2}+r^{2}d\Omega^{2}\,,$ (11)

Where $\Phi$ and $\Psi$ are only $r$-dependent. The $00$-component of the
Einstein equations is not modified, so we have the solution Tolman (1939);
Oppenheimer and Volkoff (1939)

$\Psi(r)=-\frac{1}{2}\ln\left(1-\frac{2GM(r)}{r}\right)\,,$ (12)

where

$M(r)=\int 4\pi\,r^{2}\,dr\,\epsilon(r)\,.$ (13)

We will now assume that the spherically symmetric collapse has an associated
entropy production (III), so that the condition of hydrostatic equilibrium,
$u^{\mu}=((-g_{00})^{-1/2},\,0),\ \partial_{0}g_{\mu\nu}=0$, remains valid,
but where the covariant conservation of the full energy-momentum tensor is now

$D_{\mu}{\cal T}^{\mu}_{\
\nu}=\partial_{\nu}\tilde{P}+(\epsilon+\tilde{P})\,\partial_{\nu}\ln\sqrt{-g_{00}}=0\,,$
(14)

while the radial component gives the $\Phi(r)$ equation

$\partial_{r}(P-\zeta\Theta)+(\epsilon+P-\zeta\Theta)\,\Phi^{\prime}(r)=0\,.$
(15)

Note that we differentiate here between the total energy density
$\epsilon(\rho)$ and the rest-mass density $\rho=m\,n$.

The spatial part of the Einstein equations gives rise to the modified Tolman-
Oppenheimer-Volkoff equation

$\tilde{P}^{\prime}(r)=-\frac{GM(r)}{r^{2}}\left(\epsilon(r)+\tilde{P}(r)\right)\frac{1+4\pi
r^{3}\tilde{P}(r)/M(r)}{1-2GM(r)/r}\,.$ (16)

The neutron fluid may have an equation of state $P(\rho)$ which is
undetermined in principle, and may go from fully relativistic to non-
relativistic. The individual neutrons have energies
$E^{2}(p)=m^{2}c^{4}+p^{2}c^{2}$ inside the star. If we assume the neutron
fluid becomes degenerate with Fermi distribution $f_{F}(p)=\theta(p_{F}-p)$,
with Fermi momentum $p_{F}$, then the number density is ($g=2$ for two spin
states)

$\displaystyle n_{F}$ $\displaystyle=$ $\displaystyle 2\int\frac{d^{3}{\bf
p}}{\hbar^{3}(2\pi)^{3}}\,f_{F}(p)$ (17) $\displaystyle=$ $\displaystyle
2\int_{0}^{p_{F}}\\!\frac{4\pi
p^{2}dp}{\hbar^{3}(2\pi)^{3}}=\frac{p_{F}^{3}}{3\pi^{2}\hbar^{3}}\,,$

so that

$x_{F}\equiv\frac{p_{F}}{mc}=\left(\frac{3}{8\pi}\right)^{1/3}\frac{h}{mc}\,n_{F}^{1/3}=A\,\rho^{1/3}\,,$
(18)

in terms of the rest-mass density, $\rho=m\,n_{F}$, while the pressure becomes

$\displaystyle P(x_{F})$ $\displaystyle=$ $\displaystyle 2\int\frac{d^{3}{\bf
p}}{\hbar^{3}(2\pi)^{3}}\,\frac{p^{2}c^{2}}{3E(p)}\,f_{F}(p)$ (19)
$\displaystyle=$ $\displaystyle 2\int_{0}^{p_{F}}\\!\frac{4\pi
p^{2}dp}{\hbar^{3}(2\pi)^{3}}\,\frac{p^{2}c^{2}}{3\sqrt{m^{2}c^{4}+p^{2}c^{2}}}$
$\displaystyle=$ $\displaystyle\rho\,\frac{x_{F}}{4}\,I(x_{F})\,,$

where

$I(x)\equiv\frac{1}{2x^{4}}\left(3\sinh^{-1}(x)+(2x^{3}-3x)\sqrt{1+x^{2}}\right)\,,$
(20)

with asymptotics: $I(x)=4x/5$ in the NR limit, $x_{F}\ll 1$, and $I(x)=1$ in
the ultrarelativistic limit, $x_{F}\gg 1$, which corresponds to equations of
state $P(\rho)\propto\rho^{5/3}$ and $\rho^{4/3}$ in the NR and UR limits,
respectively. The speed of sound becomes

$c_{s}^{2}=\frac{dP(\rho)}{d\rho}=\frac{1}{3}\frac{x_{F}^{2}}{\sqrt{1+x_{F}^{2}}}\,.$
(21)

We will now take into account the laws of thermodynamics out-of-equilibrium,
$d(\epsilon V)=-PdV+TdS$, to obtain a solution to the modified TOV equation
(16), using $V=Nm/\rho$ for fixed number of particles $N$ and Eq. (III),

$d\left(\frac{\epsilon(\rho)}{\rho}\right)=\tilde{P}(\rho)\,\frac{d\rho}{\rho^{2}}=\left(P(\rho)-\rho\,\frac{k_{\rm
B}T}{mc^{2}}\right)\frac{d\rho}{\rho^{2}}\,,$ (22)

which can be integrated

$\epsilon(\rho)=\rho\,H(x_{F})-\frac{k_{\rm B}T}{mc^{2}}\,\rho\,\ln\rho\,,$
(23)

with

$H(x)\equiv\frac{3}{8x^{3}}\left((2x^{3}+x)\sqrt{1+x^{2}}-\sinh^{-1}(x)\right)\,.$
(24)

Taken together, we see that the specific enthalpy is

$\epsilon^{\prime}(\rho)=\frac{\epsilon(\rho)+\tilde{P}(\rho)}{\rho}=\sqrt{1+x_{F}^{2}}-\frac{k_{\rm
B}T}{mc^{2}}(\ln\rho+1)\,.$ (25)

Note that we recover the usual expressions in the limit $k_{\rm B}T\ll
mc^{2}$, where the entropic force contribution to gravitational collapse is
negligible. However, in our case, due to the Virial theorem, gravitational
collapse brings together a heating up of the neutron fluid, with an important
entropy production, so we must take it into account. As we well see, however,
the actual temperatures inside the neutron star never reach more than around
80 MeV, well below the neutron mass, so we are still in the degenerate Fermi
gas approximation.

We can solve simultaneously the TOV Eq. (16) and the mass equation,
$M^{\prime}(r)=4\pi r^{2}\epsilon(r)$, by choosing as ”radial” coordinate the
rest-mass density $\rho$,

$\begin{array}[]{rl}{\displaystyle\frac{dM}{d\rho}}\\!&={\displaystyle
4\pi\,r(\rho)^{2}\epsilon(\rho)\,\frac{dr}{d\rho}}\\\\[14.22636pt]
{\displaystyle\frac{dr}{d\rho}}\\!&={\displaystyle\frac{\tilde{P}^{\prime}(\rho)}{\tilde{P}^{\prime}(r)}=\frac{P^{\prime}(\rho)-k_{\rm
B}T/mc^{2}}{\tilde{P}^{\prime}(r)}}\end{array}$ (26)

where in the denominator we substitute the TOV Eq. (16) as a function of
$\rho$. We can now take the radial dependence of the temperature from the
Virial theorem, Eq. (9),

$\frac{3k_{\rm B}T}{mc^{2}}=\frac{GM(r)}{c^{2}r}\,.$ (27)

The best way to solve the equations is to choose some units and write them as
dimensionless equations. We will choose the solar mass $M_{\odot}$ as unit of
mass, the solar Schwarzschild radius $r_{S}=2GM_{\odot}/c^{2}=3$ km as unit of
distance and $\rho_{0}=3M_{\odot}/(4\pi r_{S}^{3})=1.8\times 10^{16}$ g/cm3 as
unit of mass density, which is about 90 times the mean density of a NS. In
this case, the TOV equations (26) are written in terms of
$\bar{m}=M/M_{\odot}$, $\bar{r}=r/r_{S}$ and $\bar{\rho}=\rho/\rho_{c}$.

We solve the coupled equations by varying the central density
$\rho_{c}=\rho(r=0)$ in units of $\rho_{0}$ until the density drops to zero.
At that moment the star ends, with radius $R=r(\rho=0)$, and the exterior
metric becomes that of Schwarzschild with $M=M(R)$.

Figure 1: The plane $(M,\,R)$ for neutron stars evolving through out-of-
equilibrium gravitational collapse. The blue curve corresponds to the usual
TOV-Ad solutions, while the green curve arises from the modified TOV-GREA
equations. The red dashed line is the lower limit imposed by the speed of
sound, while the purple dotted line bounds the collapse to a black hole.

In Fig. 1 we show the plane $(M,\,R)$ for a series of values of the central
density, from $\rho_{c}=10^{-3}\rho_{0}$ in the top left, all the way until
$\rho_{c}=100\rho_{0}$ at the center, for both adiabatic and entropic
collapse. Overall the $(M,\,R)$ curves look very similar in the two cases.
There is, however, a difference in the minimum and maximum masses attained for
neutron stars in hydrostatic equilibrium. For the entropic case, the minimum
mass is always above $1.1\,M_{\odot}$ and the maximum mass always below
$2.4\,M_{\odot}$, which seems to be in better agreement with astrophysical
observations than the range for adiabatic case.

In Fig. 2 we show the radial profiles of the star density (in units of the
central core density), mass (in solar masses) and temperature (in units of the
neutron mass over 100). It is clear that the entropic forces act mostly in the
exterior part of the star, where the temperature is non-negligible. This
effect is enough to produce masses of neutron stars that are around 15% larger
than those in the adiabatic solutions.

Figure 2: The density, mass and temperature profiles inside the neutron star
in hydrostatic equilibrium for adiabatic (dashed line) and entropic
(continuous line) collapse. The difference is only appreciable in the outer
parts of the star. For these figures, we have chosen the core density
$\rho_{c}=0.06\,\rho_{0}$ for the NS with the largest possible mass in both
cases.

##  IV V. Conclusions

We have studied the effect of the general relativistic entropic force induced
by the entropy production during gravitational collapse of a neutron star on
the final state in hydrodynamic equilibrium of degenerate nuclear matter. We
solve the modified Tolman-Oppenheimer-Volkoff equations with the extra
pressure term proportional to the temperature inside the neutron star and the
growth of entropy, by varying the central density and finding the matter
profiles inside the star.

We find that the NS with the largest core densities have masses and radii,
$(M(M_{\odot}),\,R({\rm km}))=(1.28,\,10.6)$ and $(1.37,\,11.3)$ for TOV-Ad
and TOV-GREA, respectively, which only differ by about 15%. On the other hand,
the maximum and minimium masses are rather different, $(M_{\rm
max}(M_{\odot}),\,R({\rm km}))=(2.17,\,17.7)$ and $(2.38,\,17.1)$ and $(M_{\rm
min}(M_{\odot}),\,R({\rm km}))=(0.82,\,8.9)$ and $(1.07,\,8.9)$ for TOV-Ad and
TOV-GREA, respectively. These results suggest that, irrespective of the
internal equation of state, the entropic forces associated with gravitational
collapse have an important effect on the final equilibrium profiles and the
actual masses and radii of neutron stars.

These results may have important consequences for our interpretation of the
nature of the compact bodies that form inspiraling binaries, and finally merge
emitting a burst of gravitational waves that can be measured with laser
interferometers like LIGO-Virgo-KAGRA Coupechoux et al. (2023) and, in the
future, the Einstein Telescope Maggiore et al. (2020). The investigation of
the NS equation of state derived from these collisions Guerra Chaves and
Hinderer (2019) will thus have to be implemented in the context of the
entropic forces acting upon gravitational collapse down to stable
configurations that later on form coalescing binaries.

##  V Acknowledgements

The author acknowledges support from the Research Project PID2021-123012NB-C43
[MICINN-FEDER], and the Centro de Excelencia Severo Ochoa Program
CEX2020-001007-S.

## References

  * Shapiro and Teukolsky (1983) S. L. Shapiro and S. A. Teukolsky, _Black holes, white dwarfs, and neutron stars: The physics of compact objects_ (1983), ISBN 978-0-471-87316-7.
  * Faber and Rasio (2012) J. A. Faber and F. A. Rasio, Living Rev. Rel. 15, 8 (2012), eprint 1204.3858.
  * Abbott et al. (2017) B. P. Abbott et al. (LIGO Scientific, Virgo, Fermi-GBM, INTEGRAL), Astrophys. J. Lett. 848, L13 (2017), eprint 1710.05834.
  * Guerra Chaves and Hinderer (2019) A. Guerra Chaves and T. Hinderer, J. Phys. G 46, 123002 (2019), eprint 1912.01461.
  * Abbott et al. (2020a) B. P. Abbott et al. (LIGO Scientific, Virgo), Astrophys. J. Lett. 892, L3 (2020a), eprint 2001.01761.
  * Abbott et al. (2020b) R. Abbott et al. (LIGO Scientific, Virgo), Astrophys. J. Lett. 896, L44 (2020b), eprint 2006.12611.
  * Clesse and García-Bellido (2022) S. Clesse and J. García-Bellido, Phys. Dark Univ. 38, 101111 (2022), eprint 2007.06481.
  * Espinosa-Portales and García-Bellido (2021) L. Espinosa-Portales and J. García-Bellido, Phys. Dark Univ. 34, 100893 (2021), eprint 2106.16012.
  * García-Bellido and Espinosa-Portales (2021) J. García-Bellido and L. Espinosa-Portales, Phys. Dark Univ. 34, 100892 (2021), eprint 2106.16014.
  * Arjona et al. (2022) R. Arjona, L. Espinosa-Portales, J. García-Bellido, and S. Nesseris, Phys. Dark Univ. 36, 101029 (2022), eprint 2111.13083.
  * Tolman (1939) R. C. Tolman, Phys. Rev. 55, 364 (1939).
  * Oppenheimer and Volkoff (1939) J. R. Oppenheimer and G. M. Volkoff, Phys. Rev. 55, 374 (1939).
  * Coupechoux et al. (2023) J. F. Coupechoux, R. Chierici, H. Hansen, J. Margueron, R. Somasundaram, and V. Sordini (2023), eprint 2302.04147.
  * Maggiore et al. (2020) M. Maggiore et al., JCAP 03, 050 (2020), eprint 1912.02622.


As $G_1$ is a $(2,2)$-circuit, this implies $G_1 \cong B_1$.
However, then $F'_1 \cong K_4$, which contradicts the fact that $F'_1$ is an atom of $H_t$. Hence there exist no non-trivial 2-vertex-separations or 3-edge-separations of $G_1$ and moreover $G_1 \ncong B_1$.
Also, $G_1 \ncong K_5^-$, since $G_1$ is not 3-connected.
So, Theorem <ref> implies that $G_1 \cong B_2$ or $G_1$ contains two admissible nodes.

If $G_1 \cong B_2$ then we may suppose without loss of generality that $d_{F'_{1}}(x) = 2$ and set $N_{F'_{1}}(x) = \{y, a\}$. Let $G'$ be the graph given by the edge-reduction of $G$ that contracts $xa$ and deletes $xy$. Then $G' \cong G_{3}$, so $G'$ is $\mathcal{M}(2,2)$-connected. Hence $G$ has an admissible edge-reduction.

If $G_1$ contains two admissible nodes then let $\{w, z\} = V(G_1) \setminus V(F'_1)$ and let $v$ be an admissible node in $G_1$.
Let $G'_1$ be the graph given by the admissible 1-reduction of $G_1$ that deletes $v$ and adds the edge $e$.
As $v \notin \{w, x, y, z\}$ and $v \in Y$,
$v$ is a node in $G$ and $e \notin E$.
Now let $G'$ be the graph given by the 1-reduction of $G$ that deletes $v$ and adds the edge $e$.
Then $G'$ is isomorphic to a 2-join of $(G'_1, G_3)$ and so $G'$ is $\mathcal{M}(2,2)$-connected by Lemma <ref>.
Therefore $G$ has either an admissible 1-reduction or an admissible edge-reduction.

$(F'_1, F'_2)$ is a non-trivial 2-vertex-separation of $H_{t}$ and $E(F'_1) \cap E(F'_2) = \emptyset$.

Let $V(F'_1) \cap V(F'_2) = \{x, y\}$. Let $F'_3 = G[(V \setminus V(F'_1)) \cup \{x, y\}])$.
As $|V(F'_1) \cap X| \leq 1$, $(F'_1, F_3')$ is a non-trivial 2-vertex-separation of $G$ and $E(F'_1) \cap E(F'_3) = \emptyset$.
Let $(G_1, G_2)$ be the 1-separation of $H_t$ with respect to $(F'_1, F'_2)$ and let $(\tilde{G}_{2}, \tilde{G}_{1})$ be the 1-separation of $H_t$ with respect to $(F'_2, F'_1)$. Lemma <ref> implies either $G_1$ and $G_2$ are $(2,2)$-circuits
and $\tilde{G}_{1}$ and $\tilde{G}_{2}$ are not,
or $\tilde{G}_{1}$ and $\tilde{G}_{2}$ are $(2,2)$-circuits
and $G_{1}$ and $G_{2}$ are not.
We consider these possibilities as separate subcases.

$\tilde{G}_{1}$ and $\tilde{G}_{2}$ are $(2,2)$-circuits.

Let $(\tilde{G}_{3}, \tilde{G}_{1})$ be the 1-separation of $G$ with respect to $(F'_{3}, F'_{1})$.
By our assumption, $G_{1}$ is not a $(2,2)$-circuit.
Since $\tilde{G}_1$ is a $(2,2)$-circuit that contains $G_1$,
it follows that $G_1$ is $(2,2)$-sparse and so not $\mathcal{M}(2,2)$-connected.
Hence, Lemma <ref> implies that $\tilde{G}_{3}$ is $\mathcal{M}(2,2)$-connected.

As $F'_1$ is an atom of $G$, there is no non-trivial 3-edge-separation of $G_1$.
If there exists a non-trivial 2-vertex-separation of $G_1$,
then $\{x,y\}$ must be the corresponding vertex cut.
As $F'_1$ is an atom of $G$, one of the components of the 2-vertex-separation must be a $K_4$ subgraph of $F'_1$ containing $xy$,
however this contradicts that $xy \notin E$.
Hence there are no non-trivial 2-vertex-separations or 3-edge-separations of $\tilde{G}_{1}$.
Also, as $\tilde{G}_{1}$ is not 3-connected, $\tilde{G}_{1} \ncong K_5^-$.
Hence Theorem <ref> implies that $\tilde{G}_{1} \cong B_{1}$ or $B_{2}$, or $\tilde{G}_{1}$ contains two admissible nodes.

If $\tilde{G}_{1} \cong B_{1}$ then $F'_{1} \cong K_{4}^{-}$ with $F_1'=\{x,y,r,s\}$ for some vertices $r,s$.
Let $G'$ be the graph given by the $K_{4}^{-}$-reduction of $G$ that deletes $r$ and $s$ and adds the edge $xy$. Then $G' = \tilde{G}_{3}$, so $G'$ is $\mathcal{M}(2,2)$-connected and the $K_{4}^{-}$-reduction is admissible.
If $\tilde{G}_{1} \cong B_{2}$ then $F'_{1}$ is isomorphic to $K_4$ with an added vertex connected to exactly one vertex in the $K_4$.
Furthermore, the vertex with degree 1 in $F_1'$ must be either $x$ or $y$.
We may suppose without loss of generality that $d_{F'_{1}}(x) = 1$ and set $a$ to be the single neighbour of $x$ in $F_1'$.
Let $G'$ be the graph given by the edge-reduction of $G$ that contracts $xa$ and deletes $ya$.
Then $G'$ is isomorphic to a $K_4^-$-extension of $\tilde{G}_{3}$,
so $G'$ is $\mathcal{M}(2,2)$-connected by Lemma <ref> and this edge-reduction is admissible.

If $\tilde{G}_1$ contains two admissible nodes then let $\{w, z\} = V(G_1) \setminus V(F'_1)$ and let $v$ be an admissible node in $\tilde{G}_1$.
Let $\tilde{G}'_1$ be the graph given by the admissible 1-reduction of $\tilde{G}_1$ that deletes $v$ and adds the edge $e$.
As $v \notin \{w, x, y, z\}$ and $v \in Y$,
$v$ is a node in $G$ and $e \notin E$.
Now let $G'$ be the graph given by the 1-reduction of $G$ that deletes $v$ and adds the edge $e$.
Then $G'$ is isomorphic to a 1-join of $(\tilde{G}_{3}, G'_{1})$ and so $G'$ is $\mathcal{M}(2,2)$-connected by Lemma <ref>,
completing this subcase.

$G_{1}$ and $G_2$ are $(2,2)$-circuits.

Let $(G_{1}, G_{3})$ be a 1-separation of $G$ with respect to the non-trivial 2-vertex-separation $(F'_{1}, F'_{3})$.
By Lemma <ref>,
$G_{3}$ is $\mathcal{M}(2,2)$-connected.
As $F'_{1}$ is an atom of $H_{t}$, there are no non-trivial 2-vertex-separations or 3-edge-separations of $G_{1}$.
Therefore Theorem <ref> implies that $G_{1} \cong K_5^-, B_{1}$, or $B_{2}$, or $G_{1}$ contains two admissible nodes.

If $G_{1} \cong K_5^-$ then $F'_{1}$ is isomorphic to one of two graphs (see Figure <ref>). Let $V(F'_{1}) = \{x, y, a, b, c\}$. We may suppose without loss of generality that $d_{F'_{1}}(c) = 4$. If $ab \in E(F'_{1})$ then we may suppose without loss of generality that $ay \notin E(F'_{1})$. In either case, let $G'$ be the graph given by the edge-reduction of $G$ that contracts $by$ and deletes $bc$. Then $G' \cong G_{3}$, and hence this is an admissible edge-reduction.

[draw=gray!30!white,fill=gray!30!white] plot[smooth, tension=1] coordinates(0,0) (2.5,1.5) (0,3) – plot[smooth, tension=1] coordinates(0,0) (2.5,1.5) (0,3);
[draw=white,fill=white] plot[smooth, tension=1] coordinates(0,0) (1,1.5) (0,3);
[white,thick] (0,0) – (0,3);

(0,3) circle (3pt) node[anchor=south]$x$;
(0,0) circle (3pt) node[anchor=north]$y$;
(-2,3) circle (3pt) node[anchor=south]$a$;
(-4,1.5) circle (3pt) node[anchor=east]$c$;
(-2,0) circle (3pt) node[anchor=north]$b$;

[black,thick] (0,0) – (-2,0) – (-4,1.5) – (-2,3) – (0,3) – (-4,1.5) – (0,0);
[black,thick] (-2,3) – (0,0);
[black,thick] (-2,0) – (0,3);

[thick] plot[smooth, tension=1] coordinates(0,0) (1,1.5) (0,3);
[thick] plot[smooth, tension=1] coordinates(0,0) (2.5,1.5) (0,3);
[rectangle, draw=white, fill=white] (b) at (-1,-2) $(i)$;

(1.7,1) circle (0pt)node[anchor=south]$F'_3$;

[draw=gray!30!white,fill=gray!30!white] plot[smooth, tension=1] coordinates(12,0) (14.5,1.5) (12,3) – plot[smooth, tension=1] coordinates(12,0) (14.5,1.5) (12,3);
[draw=white,fill=white] plot[smooth, tension=1] coordinates(12,0) (13,1.5) (12,3);
[white,thick] (12,0) – (12,3);

(12,3) circle (3pt) node[anchor=south]$x$;
(12,0) circle (3pt) node[anchor=north]$y$;
(10,3) circle (3pt) node[anchor=south]$a$;
(8,1.5) circle (3pt) node[anchor=east]$c$;
(10,0) circle (3pt) node[anchor=north]$b$;

[black,thick] (12,0) – (10,0) – (8,1.5) – (10,3) – (12,3) – (8,1.5) – (12,0);
[black,thick] (10,3) – (10,0) – (12,3);
[thick] plot[smooth, tension=1] coordinates(12,0) (13,1.5) (12,3); [thick] plot[smooth, tension=1] coordinates(12,0) (14.5,1.5) (12,3);
[rectangle, draw=white, fill=white] (b) at (11,-2) $(ii)$;

(13.7,1) circle (0pt)node[anchor=south]$F'_3$;

The graph $G$ in the subcase $G_1 \cong K_5^-$ of Case <ref>.

If $G_{1} \cong B_{1}$ then, as $F'_{1}$ is an atom of $H_{t}$, $F'_{1}$ is isomorphic to one of two graphs (see Figure <ref>). We may suppose without loss of generality that $d_{F'_{1}}(x) = 2$. Let $N_{F'_{1}}(x) = \{a, b\}$ such that $d_{F'_{1}}(a) \leq d_{F'_{1}}(b)$. In either case, let $G'$ be the graph given by the edge-reduction of $G$ that contracts $xa$ and deletes $xb$. Then $G'$ is isomorphic to a 2-join of $(B_{2}, G_{3})$ and hence $G'$ is $\mathcal{M}(2,2)$-connected by Lemma <ref>. So $G$ has an admissible edge-reduction.

[draw=gray!30!white,fill=gray!30!white] plot[smooth, tension=1] coordinates(0,0) (2.5,1.5) (0,3) – plot[smooth, tension=1] coordinates(0,0) (2.5,1.5) (0,3);
[draw=white,fill=white] plot[smooth, tension=1] coordinates(0,0) (1,1.5) (0,3);
[white,thick] (0,0) – (0,3);

(0,3) circle (3pt) node[anchor=west]$y$;
(0,0) circle (3pt) node[anchor=north]$x$;
(-2,3) circle (3pt) node[anchor=east]$b$;
(-2,0) circle (3pt) node[anchor=north]$a$;
(-2,5) circle (3pt);
(0,5) circle (3pt);

[black,thick] (0,0) – (-2,0) – (-2,3) – (0,3);
[black,thick] (-2,3) – (0,0);
[black,thick] (-2,0) – (0,3) – (0,5) – (-2,5) – (0,3);
[black,thick] (0,5) – (-2,3) – (-2,5);
[thick] plot[smooth, tension=1] coordinates(0,0) (1,1.5) (0,3);
[thick] plot[smooth, tension=1] coordinates(0,0) (2.5,1.5) (0,3);
[rectangle, draw=white, fill=white] (b) at (-1,-2) $(i)$;

(1.7,1) circle (0pt)node[anchor=south]$F'_3$;

[draw=gray!30!white,fill=gray!30!white] plot[smooth, tension=1] coordinates(12,0) (14.5,1.5) (12,3) – plot[smooth, tension=1] coordinates(12,0) (14.5,1.5) (12,3);
[draw=white,fill=white] plot[smooth, tension=1] coordinates(12,0) (13,1.5) (12,3);
[white,thick] (12,0) – (12,3);

(12,3) circle (3pt)node[anchor=south]$y$;
(12,0) circle (3pt)node[anchor=north]$x$;
(10,3) circle (3pt)node[anchor=south]$a$;
(10,0) circle (3pt)node[anchor=north]$b$;
(8,0) circle (3pt);
(8,3) circle (3pt);

[black,thick] (8,3) – (10,0) – (8,0) – (8,3) – (10,3) – (12,0) – (10,0) – (10,3) – (12,3);
[black,thick] (8,0) – (10,3);
[black,thick] (10,0) – (12,3);
[thick] plot[smooth, tension=1] coordinates(12,0) (13,1.5) (12,3); [thick] plot[smooth, tension=1] coordinates(12,0) (14.5,1.5) (12,3);
[rectangle, draw=white, fill=white] (b) at (11,-2) $(ii)$;

(13.7,1) circle (0pt)node[anchor=south]$F'_3$;

The graph $G$ in the subcase $G_1 \cong B_1$ of Case <ref>.

If $G_{1}$ contains two admissible nodes,
then either there exists $v \in V(F'_{1}) \setminus \{x, y\}$ such that $v$ is an admissible node in $G_{1}$, or $x$ and $y$ are the only admissible nodes of $G_{1}$. In the first case, let $G'_{1}$ be given by an admissible 1-reduction of $G_{1}$ at $v$ that adds the edge $e$.
Importantly, $e \neq xy$, since $xy$ is an edge of $G_1$.
As $v \notin \{x, y\}$, $v$ is a node in $G$ also.
Let $G'$ be given by the 1-reduction of $G$ at $v$ that adds the edge $e$.
Then $G'$ is isomorphic to a 1-join of $(G'_{1}, G_{3})$, so $G'$ is $\mathcal{M}(2,2)$-connected by Lemma <ref>.
Hence $G$ has an admissible edge-reduction.
Alternatively, suppose that $x$ and $y$ are the only admissible nodes of $G_{1}$. Let $N_{G_{1}}(x) = \{a, b, y\}$ and let $G'_{1}$ be given by the admissible 1-reduction of $G_{1}$ that removes $x$ and adds the edge $e$ (see Figure <ref>).
As this 1-reduction is admissible, $d_{G'_{1}}(y) \geq 3$, so $e \in \{ya, yb\}$.
Without loss of generality we may suppose that $e = ya$, so $ya \notin E$.
Let $G'$ be the edge-reduction of $G$ that contracts $xa$ and deletes $xb$. Then, as $xy, ya \notin E$, $G'$ is isomorphic to a 1-join of $(G'_{1}, G_{3})$ and hence is $\mathcal{M}(2,2)$-connected by Lemma <ref>. Therefore $G$ has an admissible edge-reduction.

(-4,10) circle (27pt);
(1.5,10) circle (27pt);
(7.5,10) circle (27pt);
(9.6,10) circle (27pt);

(-2.5,10.5) circle (2pt) node[anchor=south]$x$;
(-2.5,9.5) circle (2pt) node[anchor=north]$y$;
(-3.6,9.3) circle (2pt);
(-4,10.1) circle (2pt) node[anchor=east]$b$;
(-3.7,10.7) circle (2pt) node[anchor=east]$a$;

[black] (-3.7,10.7) – (-2.5,10.5) – (-2.5,9.5);
[black] (-4,10.1) – (-2.5,10.5);
[black] (-3.7,9.7) – (-2.5,9.5) – (-3.6,9.3);
[black] (-1.5,10) – (-.5,10) – (-.6,9.9);
[black] (-.5,10) – (-.6,10.1);
[rectangle, draw=white, fill=white] (b) at (-3.5,8.2) $G_1$;

(3,9.5) circle (2pt) node[anchor=north]$y$;
(1.9,9.3) circle (2pt);
(1.5,10.1) circle (2pt) node[anchor=east]$b$;
(1.8,10.7) circle (2pt) node[anchor=east]$a$;

[black] (3,9.5) – (1.8,10.7);
[black] (1.8,9.7) – (3,9.5) – (1.9,9.3);
[rectangle, draw=white, fill=white] (b) at (2,8.2) $G_1'$;

(9,10.5) circle (2pt) node[anchor=west]$x$;
(9,9.5) circle (2pt) node[anchor=west]$y$;
(7.9,9.3) circle (2pt);
(7.5,10.1) circle (2pt) node[anchor=east]$b$;
(7.8,10.7) circle (2pt) node[anchor=east]$a$;

[black] (7.5,10.1) – (9,10.5) – (7.8,10.7);
[black] (7.9,9.3) – (9,9.5) – (7.8, 9.7);
[black] (11,10) – (12,10) – (11.9,9.9);
[black] (12,10) – (11.9,10.1);
[rectangle, draw=white, fill=white] (b) at (8,8.2) $G$;

[thick] plot[smooth, tension=1] coordinates(13.5,10.48) (13.5,9.5) (14.5,9.3) (15.3,9.4) (14.7,10) (15.3,10.6)(14.5,10.7) (13.5,10.48);

[thick] plot[smooth, tension=1] coordinates(16.5,10.48) (16.5,9.5) (15.5,9.3) (14.7,9.4) (15.3,10) (14.7,10.6)(15.5,10.7) (16.5,10.48);

(15,9.4) circle (2pt) node[anchor=north]$y$;
(14.4,9.5) circle (2pt);
(14.1,10.3) circle (2pt) node[anchor=east]$b$;
(15,10.6) circle (2pt) node[anchor=south]$a$;

[black] (14.4,9.5) – (15,9.4) – (14.3,9.9);
[black] (11,10) – (12,10) – (11.9,9.9);
[black] (12,10) – (11.9,10.1);
[rectangle, draw=white, fill=white] (b) at (15,8.2) $G'$;

The subcase of Case <ref> when $G_1$ is not isomorphic to $K_5^-$, $B_1$ of $B_2$. Here $G'$ is the 1-join of $G_1'$ and $G_3$.

If $G_{1} \cong B_{2}$ then, as $F'_{1}$ is an atom of $H_{t}$, $G$ is isomorphic to the graph shown in Figure <ref>.
Let $\{u\} = N_{F'_{1}}(x) \cap N_{F'_{1}}(y)$ and let

\begin{align*}
G'_{1} = (V(G_{1}) \cup \{w, z\}, (E(G_{1}) \setminus \{xu\}) \cup \{xw, xz, yw, yz, wz\});
\end{align*}

see Figure <ref>.
Then $G'_{1}$ is isomorphic to a 1-join of $(B_{2}, B_{1})$ so $G'_{1}$ is $\mathcal{M}(2,2)$-connected by Lemma <ref>.
We now turn our attention to $G_{3}$.
As $|V(G_{3})| +|E(G_3)| = |V|+|E| - 9$,
it follows from our initial induction assumption (see the first paragraph of the proof) that either $G_3$ is isomorphic to $K_5^-$ or $B_1$, or there exists an admissible $K_{4}^{-}$-reduction, edge-reduction, or edge-deletion of $G_{3}$.
As $G_3$ is not 3-connected, $G_3 \not\cong K_5^-$.
If $G_3 \cong B_1$ then $G$ is isomorphic to the graph on the right of Figure <ref>, and hence has an admissible $K_4^-$-reduction.
Suppose that there exists an admissible $K_{4}^{-}$-reduction, edge-reduction, or edge-deletion of $G_{3}$.
Label the two vertices in $V(G_{3}) = V(F'_{3})$ as $w',z'$.

[draw=gray!30!white,fill=gray!30!white] plot[smooth, tension=1] coordinates(0,0) (2.5,1.5) (0,3) – plot[smooth, tension=1] coordinates(0,0) (2.5,1.5) (0,3);
[draw=white,fill=white] plot[smooth, tension=1] coordinates(0,0) (1,1.5) (0,3);

[white,thick] (0,0) – (0,3);

(0,3) circle (3pt)node[anchor=south]$y$;
(0,0) circle (3pt)node[anchor=north]$x$;
(-1,4) circle (3pt);
(-1,1.5) circle (3pt)node[anchor=east]$u$;
(-1,-1) circle (3pt);
(-2,3) circle (3pt);
(-2,0) circle (3pt);

[black,thick] (-2,0) – (-1,1.5) – (0,3) – (-1,4) – (-2,3) – (0,0) – (-1,-1) – (-2,0) – (0,0);
[black,thick] (0,3) – (-2,3);
[black,thick] (-1,4) – (-1,1.5) – (-1,-1);

[thick] plot[smooth, tension=1] coordinates(0,0) (1,1.5) (0,3); [thick] plot[smooth, tension=1] coordinates(0,0) (2.5,1.5) (0,3);
[rectangle, draw=white, fill=white] (b) at (0,-2) $G$;

(1.7,1) circle (0pt)node[anchor=south]$F'_3$;

(10,3) circle (3pt)node[anchor=south]$y$;
(10,0) circle (3pt)node[anchor=north]$x$;
(9,4) circle (3pt);
(9,1.5) circle (3pt)node[anchor=east]$u$;
(9,-1) circle (3pt);
(8,3) circle (3pt);
(8,0) circle (3pt);
(12,0) circle (3pt)node[anchor=north]$w$;
(12,3) circle (3pt)node[anchor=south]$z$;

[black,thick] (8,0) – (9,1.5) – (10,3) – (9,4) – (8,3) – (9,1.5);
[black,thick] (10,0) – (9,-1) – (8,0) – (10,0);
[black,thick] (10,0) – (12,3) – (12,0) – (10,0) – (10,3) – (8,3);
[black,thick] (9,4) – (9,1.5) – (9,-1);
[black,thick] (12,0) – (10,3) – (12,3);
[rectangle, draw=white, fill=white] (b) at (10,-2) $G'_1$;

(1.7,1) circle (0pt)node[anchor=south]$F'_3$;

The graphs $G$ and $G'_1$ in the subcase $G_1 \cong B_2$ of Case <ref>.

If there exists an admissible $K_{4}^{-}$-reduction of $G_{3}$ then the same $K_{4}^{-}$ is present in $G$ as an induced subgraph. Let $G'_{3}$ be the graph given by the $K_{4}^{-}$-reduction of $G_{3}$ and let $G'$ be the graph given by the $K_{4}^{-}$-reduction of $G$. Then $G'$ is isomorphic to a 1-join of $(G_{1}, G'_{3})$ and so $G'$ is $\mathcal{M}(2,2)$-connected by Lemma <ref>. Hence $G$ has an admissible $K_{4}^{-}$-reduction.

If there exists an admissible edge-reduction of $G_{3}$, let this contract $e$ and delete $f$ and call the resulting graph $G'_{3}$. As this edge-reduction is admissible, $e \notin \{xy, xw', xz', yw', yz', w'z'\}$ and $f \notin \{xw', xz, yw', yz', w'z'\}$.
Hence $e \in E$, and $f \in E$ if and only if $f \neq xy$.
Suppose that $f \neq xy$ and let $G'$ be given by the edge-reduction of $G$ that contracts $e$ and deletes $f$.
Then $G'$ is isomorphic to a 1-join of $(G_{1}, G'_{3})$ and so $G'$ is $\mathcal{M}(2,2)$-connected by Lemma <ref>. Hence $G$ has an admissible edge-reduction.
Now suppose $f = xy$.
Without loss of generality we may suppose that $e = xa$ for some $a \in V(F'_{3})-y$ and denote the vertex resulting from the contraction of $e$ by $x'$.

Let $G'$ be given by the edge-reduction of $G$ that contracts $e$ and deletes $xu$.
If $ya \in E(G_3)$ then $G'$ is isomorphic to a 2-join of $(G'_1,G'_3)$ with $x'$ relabelled as $x$.
Since both $G_1'$ and $G_3'$ are $\mathcal{M}(2,2)$-connected,
$G'$ is $\mathcal{M}(2,2)$-connected also by Lemma <ref>.
If $ya \notin E(G_3)$ then $x'y \notin E(G'_3)$.
Let $(G_{4}, G_{5})$ be a 1-separation of $G'_{3}$ on $(G'_{3}[V(G'_{3}) \setminus \{w', z'\}], G'_{3}[\{x', y, w', z',\}])$ and let $(\tilde{G}_{5}, \tilde{G}_{4})$ be a 1-separation of $G'_{3}$ on $(G'_{3}[\{x', y, w', z'\}], G'_{3}[V(G'_{3}) \setminus \{w', z'\}])$.
Then $G'$ is isomorphic to a 1-join of $(G_{4}, G'_{1})$.
As $\tilde{G}_{5} \cong K_{4}$, Lemma <ref> implies that $G_{4}$ is $\mathcal{M}(2,2)$-connected.
So Lemma <ref> gives that $G'$ is $\mathcal{M}(2,2)$-connected. Therefore $G$ has an admissible edge-reduction.

Lastly, if there exists an admissible edge-deletion of $G_{3}$ that deletes the edge $e$,
then $e \notin \{xw', xz', yw', yz', w'z'\}$.
If $e \neq xy$ then $G-e$ is isomorphic to a $1$-join of $(G_{1}, G_{3}-e)$ and so $G-e$ is $\mathcal{M}(2,2)$-connected by Lemma <ref>.
Suppose $e = xy$.
Given $G_{3,1} := G_{3}[V(G'_{3}) \setminus \{w', z'\}]-e$ and $G_{3,2} := G_{3}[\{x, y, w', z'\}]-e$, let $(G_{4}, G_{5})$ be a 1-separation of $G_{3}-e$ on $(G_{3,1}, G_{3,2})$ and let $(\tilde{G}_{5}, \tilde{G}_{4})$ be a 1-separation of $G_{3}-e$ on $(G_{3,2}, G_{3,1})$.
As $\tilde{G}_{5} \cong K_{4}$,
Lemma <ref> implies that $G_{4}$ is $\mathcal{M}(2,2)$-connected.
Since $G-xu$ is isomorphic to a 1-join of $(G_{4}, G'_{1})$,
Lemma <ref> implies that $G-xu$ is $\mathcal{M}(2,2)$-connected. Therefore $G$ has an admissible edge-deletion.
This concludes the proof.

A graph $G$ is $\mathcal{M}(2,2)$-connected if and only if $G$ can be generated from $K_5^-$ or $B_1$ by generalised vertex splits, $K_4^-$-extensions and edge additions such that each generalised vertex split preserves $\mathcal{M}(2,2)$-connectivity.

The case when $G$ is a $(2,2)$-circuit is Theorem <ref>. The case when $G$ is not a $(2,2)$-circuit, in one direction, follows from Lemmas <ref> and <ref>. The converse follows from Theorem <ref>.

Finally we can now easily obtain the main result of this section.

By Proposition <ref> and Lemma <ref>,
a graph is $M(2,2)$-connected if and only if it is redundantly rigid in $X$ and 2-connected.
The result now follows from Corollary <ref>.

§ CHARACTERISING GLOBALLY RIGID GRAPHS IN ANALYTIC NORMED PLANES

The main result of the paper (Theorem <ref>) is obtained in this section. We begin by stating two results from [23]. The first concerns the base graphs from Theorem <ref> (see Figure <ref>)[It is worth pointing out that for a given norm, global rigidity for such small graphs can be checked computationally. However, giving a rigorous proof for all analytic norms simultaneously is non-trivial.] and the second is an analogue of the “averaging theorem” of Connelly and Whiteley [15].

The graphs $K_5^-$ and $B_1$ are globally rigid in any analytic normed plane.

Let $(G,p)$ be a globally rigid and infinitesimally rigid framework in a smooth normed space $X$ with finitely many linear isometries.
Then there exists an open neighbourhood $U$ of $p$ where $(G,q)$ is globally rigid and infinitesimally rigid in $X$ for all $q \in U$.

§.§ K4--extensions

In this subsection we prove that $K_4^-$-extensions preserve global rigidity in analytic normed planes. We first require the following lemma.

Let $X$ be a non-Euclidean normed plane.
Then for all but a finite number of points $x \in X$ with $\| x\|=1$,
if $g$ is an isometry and $g(x) = x$ then $g$ is the identity map.

Let $A$ be the set of points $x \in X$ where $\|x \| =1$ and there exists a non-trivial linear isometry $g_x$ with $g_x(x) = x$.
We note that if $x,y \in A$ are linearly independent then $g_x(y) \neq y$ (as otherwise $g_x$ must be the identity map),
thus the cardinality of $A$ is less than twice the cardinality of the group of linear isometries of $X$.
The result now follows as all non-Euclidean normed planes have a finite amount of linear isometries (see <cit.>).

Let $X$ be an analytic normed plane, let $z \in X$ be any non-zero point,
and define $\H$ and $'̋$ to be the two open half-planes formed by the line through $0$ and $z$.
It was shown in \cite[Theorem 4.3]{DN} that there exists a unique map $R_z :X →X$ (called the \emph{$z$-reflection}) defined by the following properties: (i) if $x ∈X$ does not lie on the line through $0$ and $z$, then $R_z(x)$ is the unique point distinct from $x$ where $R_z(x) = x$ and $R_z(x) - z = x - z$, and (ii) if $x ∈X$ lies on the line through $0$ and $z$, then $R_z(x) = x$.
The map $R_z$ has additional useful properties that we will require.  Firstly, it is a homeomorphism and an involution, and it is an analytic diffeomorphism when its domain and codomain are restricted to the set of points that do not lie on the line through $0$ and $z$. Secondly, any point in $$̋ will be mapped to a point in $\H'$ and vice versa.

Let $X$ be an analytic normed plane,
$z \in X$ be any non-zero point and $\H$ be an open half plane formed by the line through $0$ and $z$.
Suppose that $R_z$ is not an isometry.
Then for any two points $x,y$ that lie in the closure of $ℋ$ and for any $ε>0$,
there exists $x',y' ∈$̋ such that $\|x-x'\|<\varepsilon$, $\|y-y'\|<\varepsilon$ and

\begin{align*}
\|R_z(x')- R_z(y')\| \neq \|x'-y'\|, \qquad \|x'- R_z(y')\| \neq \|x'-y'\|, \qquad \|R_z(x')- y'\| \neq \|x'-y'\|.
\end{align*}

Define $U \subset \H \times \H$ to be the connected subset of all points $(x,y)$ where $x ≠y$.
It will suffice for us to show that the sets
\begin{align*}
D := \{(x,y) \in U : \|R_z(x)- R_z(y)\| \neq \|x-y\| \}, \qquad D' := \{(x,y) \in U : \|x- R_z(y)\| \neq \|x-y\| \}
\end{align*}
are both open conull subsets of $U$.

Define $f : U →ℝ$ to be the analytic function that maps $(x,y) ∈U$ to $R_z(x)- R_z(y) - x-z$,
and define $g : U →ℝ$ to be the analytic function that maps $(x,y) ∈U$ to $x- R_z(y) - x-z$.
It is immediate that the zero sets of $f$ and $g$ are the sets $U ∖D$ and $U ∖D'$ respectively.
As both $f$ and $g$ are analytic and the set $U$ is connected,
their zero sets are either closed null sets or the entirety of $U$ (see [48]);
i.e., either $D$ (respectively $D'$) is empty or $D$ (respectively $D'$) is an open conull set.
If $D = ∅$ then $R_z$ is an isometry (as it is an involution and invariant on the line through $0$ and $z$),
hence $U ∖D$ is a closed conull set.
To see that $D'$ cannot be empty,
note that $x - R_z(x) - x - x ≠0$ and the map $R_z$ is continuous,
hence we must have $g(x,y) ≠0$ for sufficiently close $x$ and $y$.
\end{proof}

By using $z$-reflections, we can now prove that $K_4^-$-extensions preserve globally rigidity in analytic normed planes. We refer the reader to Section \ref{sec:redundant} for the definition of the compact differentiable manifold $𝒞(G,p)$.

\begin{thm}\label{thm:k4-}
Let $G=(V,E)$ be a globally rigid graph in an analytic normed plane $X$ and let $G'=(V',E')$ be formed from $G$ by a $K_4^-$-extension.
Then $G'$ is globally rigid in $X$ also.
\end{thm}

\begin{proof}
Suppose $G'$ is formed from $G$ by the $K_4^-$-extension applied to the edge $v_1v_2$ that adds vertices $u_1,u_2$.
Since $G$ is globally rigid,
we can choose a completely strongly regular framework $(G,p)$ that is globally rigid with $p_{v_1}=0$ and $p_{v_2} = z$ for some $\|z\|=1$;
by Lemma \ref{l:limitedisom},
we may assume we chose $z$ such that,
given any non-trivial linear isometry $g$,
we have $g(z) \neq z$.
By Theorem \ref{thm:red},
$(G,p)$ is redundantly rigid.
Since $(G,p)$ is completely strongly regular, the set $\mathcal{C}(G - v_1 v_2,p)$ is finite.
Furthermore, for any placement $q \in X^V$ where $f_{G-v_1v_2}(q) = f_{G-v_1v_2}(p)$, we have	$\|q_{v_1} - q_{v_2}\| = \|p_{v_1} - p_{v_2}\|$ if and only if $q \sim p$.
For any equivalence class $\tilde{q} \in \mathcal{C}(G,p)$,
we note that $\|q_{v_1} - q_{v_2}\| = \|q'_{v_1} - q'_{v_2}\|$ for all $q,q' \in \tilde{q}$.
Since $\mathcal{C}(G - v_1 v_2,p)$ is a finite set,
it follows that
\begin{align*}
t := \min \left\{ |\|q_{v_1} - q_{v_2}\| - \|p_{v_1} - p_{v_2}\| |: f_{G-v_1v_2}(q) = f_{G-v_1v_2}(p), ~ q \not\sim p \right\}.
\end{align*}
is well-defined and non-zero.

Choose $\varepsilon < t/4$.
Let $\H, \H'$ be the open hyperplanes defined by the line through $0,z$.
By our choice of $z$,
the $z$-reflection $R_z$ is not an isometry.
By Lemma \ref{l:zreflection},
there exists $x_1,x_2 \in \H$ such that $\|x_1\| < \varepsilon$, $\|x_2 - z\| < \varepsilon$, $\|R_z(x_1) - R_z(x_2)\| \neq \|x_1-x_2\|$, $\|x_1 - R_z(x_2)\| \neq \|x_1-x_2\|$ and $\|R_z(x_1) - x_2\| \neq \|x_1-x_2\|$.
We will now choose $p'$ to be a placement of $G'$ where $p'_v=p_v$ for all $v \in V$ and $p'_{u_i} = x_i$ for each $i \in \{1,2\}$.
As $\|p'_{v_i} - p'_{u_i} \| < \varepsilon$ for $i \in \{1,2\}$,
we have for any $q \in f_{G'}^{-1}(f_{G'}(p'))$ that
\begin{align*}
\Big|\left\|q_{v_1} - q_{v_2} \| - \|q_{u_1} - q_{u_2} \right\|\Big| \leq \|(q_{v_1} - q_{u_1}) + (q_{u_2} - q_{v_2})\| \leq \|q_{v_1} - q_{u_1}\| + \|q_{v_2} - q_{u_2}\| < 2 \varepsilon
\end{align*}
for any $q \in f_{G'}^{-1}(f_{G'}(p'))$ we have
\begin{eqnarray*}
\Big|\|q_{v_1} - q_{v_2} \| - \|p'_{v_1} - p'_{v_2} \| \Big| &=&
\Big|\|q_{v_1} - q_{v_2} \| - \|q_{u_1} - q_{u_2} \| + \|p'_{u_1} - p'_{u_2} \| - \|p'_{v_1} - p'_{v_2} \| \Big|\\
&\leq& \Big|\|q_{v_1} - q_{v_2} \| - \|q_{u_1} - q_{u_2} \| \Big| + \Big| \|p'_{u_1} - p'_{u_2} \| - \|p'_{v_1} - p'_{v_2} \| \Big|\\
&<& 4 \varepsilon < t.
\end{eqnarray*}
By our choice of $t$ it follows that for all $q \in f_{G'}^{-1}(f_{G'}(p'))$ we have $\|q_{v_1}-q_{v_2}\| = \|p'_{v_1}-p'_{v_2}\|$,
and thus $(G',p')$ is globally rigid if and only if $(G'+v_1 v_2,p')$ is globally rigid.

Fix a placement $q \in X^V$ where $(G'+v_1v_2,q) \sim (G'+v_1v_2,p')$.
As $(G,p)$ is a globally rigid subframework of $(G'+v_1v_2,p')$,
we may suppose we chose $q$ such that $q_v=p'_v$ for all $v \in V$.
By the uniqueness of the $z$-reflection $R_z$,
we have $q_{u_i} \in \{ p'_{u_i}, R_z(p'_{u_i}) \}$ for each $i \in \{1,2\}$.
However, by our choice of $x_1,x_2$, we must have $q_{u_i} = p'_{u_i}$ for each $i \in \{1,2\}$.
It follows that $(G'+ v_1 v_2,p')$ is globally rigid,
and thus $(G',p')$ is also globally rigid.

We conclude by proving $(G',p')$ is infinitesimally rigid;
it will then follow from Theorem \ref{thm:ave} that $G'$ is globally rigid.
Choose an infinitesimal flex $a \in X^{V'}$ of $(G',p')$.
Since $(G,p)$ is redundantly rigid,
$a$ restricted to the vertices of $G$ must be a trivial infinitesimal flex.
As every non-Euclidean normed plane has finitely many linear isometries (see \cite[Proposition 2.5(ii)]{dew2}),
we may suppose that $a_v = 0$ for all $v \in V$.
By our choice of $x_1$ and $x_2$,
the vectors $p'_{u_i}- p'_{v_1}$ and $p'_{u_i}- p'_{v_2}$ are linearly independent for each $i \in \{1,2 \}$.
As $X$ is smooth,
the vectors $p'_{u_i}- p'_{v_1}$ and $p'_{u_i}- p'_{v_2}$ have unique support functionals,
and as $X$ is strictly convex,
the support functionals $\varphi_{p'_{u_i}- p'_{v_1}}$ and $\varphi_{p'_{u_i}- p'_{v_2}}$ are linearly independent.
For each $i,j \in \{1,2\}$ we have
\begin{align*}
\varphi_{p'_{u_i}- p'_{v_j}}(a_{u_i} - a_{v_j}) = \varphi_{p'_{u_i}- p'_{v_j}}(a_{u_i}) = 0.
\end{align*}
Hence $a_{u_1} =a_{u_2} = 0$,
i.e., $a$ is trivial and $(G',p')$ is infinitesimally rigid.
\end{proof}

\subsection{Main result}

Similarly to how $K_4^-$-extensions preserve global rigidity in analytic normed planes,
generalised vertex split also preserve global rigidity when certain criteria are met.

\begin{thm}[{\cite[Theorem 5.4]{DHN}}]\label{thm:vsplitglobal}
Let $G$ be a globally rigid graph in an analytic normed plane $X$.
Let $G'$ be a generalised vertex split of $G$ at the vertex $z$ with new vertices $u,v$ and suppose that $G'-uv$ is rigid in $X$.
Then $G'$ is globally rigid in $X$.
\end{thm}

With this, we are now finally ready to prove our main result (Theorem \ref{thm:grne}). Recall that this states, for a graph $G=(V,E)$ with $|V|\geq 5$ and an analytic normed plane $X$, $G$ is globally rigid in $X$ if and only if $G$ is 2-connected and redundantly rigid in $X$.

\begin{proof}[Proof of Theorem \ref{thm:grne}]
If $G$ is globally rigid in $X$ then it is 2-connected and redundantly rigid in $X$ by Theorem \ref{thm:hendrickson}.
Conversely, suppose $G$ is 2-connected and redundantly rigid in $X$.
By Theorem \ref{thm:1},
$G$ can be generated from $K_5^-$ or $B_1$ by generalised vertex splits that preserve redundant rigidity in $X$, $K_4^-$-extensions and edge additions.
The graphs $K_5^-$ and $B_1$ are globally rigid in $X$ by Lemma \ref{lem:basegraphs}.
By Theorem \ref{thm:k4-},
$K_4^-$-extensions preserve global rigidity in $X$,
and by Theorem \ref{thm:vsplitglobal} generalised vertex splits that preserve redundant rigidity in $X$ also preserve global rigidity in $X$.
Since edge additions certainly preserve global rigidity, the proof is complete.
\end{proof}

We remark that the characterisation is effective since there exist efficient algorithms that can check redundant rigidity in $X$ [7, 44] and 2-connectivity [57].
There is also an immediate link between global rigidity in analytic normed planes and global rigidity in the Euclidean plane.

\begin{cor}\label{cor:euclidean}
Let $G=(V,E)$ be a globally rigid graph in $\mathbb{E}^2$ with $|V| \geq 2$ and let $X$ be an analytic normed plane.
Then $G$ is globally rigid in $X$ if and only if $|E| > 2|V|-2$.
\end{cor}

\begin{proof}
If $G$ is globally rigid in $X$ then $|E| > 2|V|-2$ by Theorems \ref{thm:grne} and \ref{thm:rigidne}.
For the converse suppose $G$ is globally rigid in $\mathbb{E}^2$ with $|E| > 2|V|-2$.
Since $G$ is simple, $|V|\geq 5$, and so $G$ is 2-connected by Theorem \ref{thm:euclidglobal}.
Choose any edge $e$ of $G$.
By Theorems \ref{thm:euclidglobal} and \ref{thm:rigide},
there exists a
spanning $(2,3)$-tight subgraph $H \subset G-e$.
As $|E| > 2|V|-2$,
there exists an edge $f$ contained in $G-e$ but not $H$.
The graph $H+f$ is $(2,2)$-tight, hence $G-e$ is rigid in $X$ by Theorem \ref{thm:rigidne}. Since $e$ was arbitrary, the result follows from Theorem \ref{thm:grne}.
\end{proof}

\subsection{Sufficient conditions for global rigidity}
Motivated by analogous results in the Euclidean setting, e.g., 6-connectivity implies global rigidity \cite[Theorem 7.2]{J&J}, we give some sufficient conditions for global rigidity in analytic normed planes.
We begin by recalling three well-known results from graph theory.
We denote the vertex and edge connectivity of a graph $G$ by $\kappa(G)$ and $\lambda(G)$ respectively.

\begin{thm}[[9]]\label{t:cls}
A graph $G=(V,E)$ is $2k$-edge-connected if and only if for all $F \subseteq E$ with $|F|\leq k$,
the graph $G-F$ contains $k$ edge-disjoint spanning trees.
\end{thm}

\begin{thm}[[29]]\label{thm:hv08}
Let $G=(V,E)$ be a graph with minimum degree $\delta$ and maximal degree $\Delta$,
and let $G^c= (V,E^c)$ be the complement of $G$.
\begin{enumerate}[(i)]
\item \label{thm:hv08.1} Either $\lambda(G) = k$ or $\lambda(G^c) = |V| - \Delta - 1$.
\item \label{thm:hv08.2} $\kappa(G) + \kappa(G^c) \geq \min \{\delta , |V| - \Delta - 1 \} + 1$.
\end{enumerate}
\end{thm}

\begin{thm}[{\cite[Theorem 1]{chartrand}}]\label{thm:chartrand-edge-conn}
Let $G = (V,E)$ be a graph with minimum degree $\delta$.
If $\delta \geq \left\lfloor \frac{|V|}{2}\right\rfloor$ then $G$ is $\delta$-edge-connected.
\end{thm}

We first obtain a sufficient connectivity condition for global rigidity.

\begin{cor}\label{c:connected}
Any 2-connected and 4-edge-connected graph is globally rigid in any analytic normed plane.
\end{cor}

\begin{proof}
The theorem follows from Theorems \ref{thm:grne}, \ref{thm:rigidne} and \ref{t:cls}.
\end{proof}

It is easy to see that these connectivity conditions are best possible since 2-connectivity is a necessary condition for global rigidity (Theorem \ref{thm:connectivity}) and there exist graphs that are both 2-connected and 3-edge-connected but do not contain a $(2,2)$-tight spanning subgraph (e.g., the complete bipartite graph $K_{3,3}$).
We go out on a limb and conjecture that every $2d$-edge-connected and 2-connected graph is globally rigid in any $d$-dimensional normed space with a finite number of linear isometries. (Recall that when $d>2$ and the norm is non-Euclidean, the weaker property of rigidity is only understood in certain special cases [22].)

We next use Corollary \ref{c:connected} to obtain sufficient minimum degree conditions for global rigidity.

\begin{cor}
Let $G=(V,E)$ be a graph with minimum degree $\delta \geq 4$ and maximal degree $\Delta \leq |V| - 5$.
Then either $G$ or its complement $G^c=(V,E^c)$ are globally rigid in any analytic normed plane.
\end{cor}

\begin{proof}
By Theorem \ref{thm:hv08}(\ref{thm:hv08.1}),
at least one of $G$ and $G^c$ is 4-edge-connected.
Without loss of generality we may assume $G$ is 4-edge-connected.
By Theorem \ref{thm:hv08}(\ref{thm:hv08.2}), $\kappa(G) + \kappa(G^c) \geq 5$.
If $\kappa(G) \geq 2$ then $G$ is globally rigid in any analytic normed plane by Corollary \ref{c:connected}.
If $\kappa(G) \leq 1$ then $4 \leq \kappa(G^c) \leq \lambda (G^c)$,
and hence $G^c$ is is globally rigid in any analytic normed plane by Corollary \ref{c:connected}.
\end{proof}

\begin{cor}\label{cor:ham}
Let $G = (V,E)$ be a graph with minimum degree $\delta$ and let $X$ be an analytic normed plane.
If $\delta \geq \max \{4, |V|/2\}$,
then $G$ is globally rigid in $X$.
\end{cor}

\begin{proof}
By Dirac's theorem,
$G$ contains a Hamilton cycle and is hence 2-connected.
By Theorem \ref{thm:chartrand-edge-conn},
$G$ is 4-edge-connected.
Hence $G$ is globally rigid in $X$ by Corollary \ref{c:connected}.
\end{proof}

Corollary \ref{cor:ham} is best possible.
We can see this by constructing counterexamples with $n$ vertices and minimum degree $\delta$ for each of the three cases:
$\delta < \lfloor n/2 \rfloor$, $n$ is odd and $\delta = \lfloor n/2 \rfloor$, and $\delta \leq 3$.
For $\delta < \lfloor n/2 \rfloor$ we may take the disjoint union of any two complete graphs $K_s,K_t$ where $s+t = n$ and $s,t \geq \lfloor n/2 \rfloor$.
If $n$ is odd and $\delta = \lfloor n/2 \rfloor$,
then we can construct a connected but not 2-connected graph by gluing two copies of $K_{\lceil n/2 \rceil}$ at a single vertex.
for $\delta \leq 3$ we note that every cycle and every cubic graph graph is $(2,2)$-sparse and so cannot be redundantly rigid in any non-Euclidean normed plane.

Next we give spectral sufficiency conditions for global rigidity in analytic normed planes.
Define the \emph{algebraic connectivity} of a graph to be the second smallest eigenvalue of the Laplacian matrix of the graph.

\begin{cor}
Let $G$ be a 2-connected graph with minimum degree $\delta \geq 5$ and algebraic connectivity $\mu > \frac{4}{\delta +1}$.
Then $G$ is globally rigid in any analytic normed plane.
\end{cor}

\begin{proof}
By \cite[Theorems 4.10 \& 4.12(ii)]{cdgg22} and Theorem \ref{thm:rigidne},
$G$ is redundantly rigid in any analytic normed plane.
The result now follows from Theorem \ref{thm:grne}.
\end{proof}

An alternative sufficient condition for global rigidity in $d$-dimensional Euclidean space was provided by Tanigawa [56]. Our next result, which follows from Theorem \ref{thm:grne}, shows that an analogous statement is true for analytic normed planes.

\begin{cor}\label{cor:vertexred}
Let $G = (V,E)$ be a graph, $|V|\geq 3$ and $X$ be an analytic normed plane.
If $G -v$ is rigid in $X$ for all $v \in V$ then $G$ is globally rigid in $X$.
\end{cor}

\begin{proof}
Since rigid graphs are connected and $|V|\geq 3$, $G$ is $2$-connected. Moreover by considering any edge incident to a given vertex, $G$ must be redundantly rigid in $X$. Hence $G$ is globally rigid in $X$ by Theorem \ref{thm:grne}.
\end{proof}

Again one might expect the corollary to remain valid in arbitrary dimensions, under the hypothesis that the normed space has finitely many linear isometries.

Our combinatorial description of global rigidity can also easily be applied to \emph{vertex-transitive} (the automorphism group acts transitively on the vertex set) or \emph{edge-transitive} (the automorphism group acts transitively on the edge set) graphs with sufficient minimum degree.

\begin{cor}\label{cor:trans}
Let $G = (V,E)$ be a connected graph with minimum degree $\delta \geq 4$.
If $G$ is vertex-transitive or edge-transitive,
then $G$ is globally rigid in any analytic normed plane.
\end{cor}

\begin{proof}
Since $\delta \geq 4$ and $G$ is connected, if $G$ is vertex-transitive it is 4-connected by \cite[Theorem 3.4.2]{GodsilRoyle},
and if $G$ is edge-transitive it is 4-connected by \cite[Corollary 1A]{Watkins}.
Hence $G$ is globally rigid in any analytic normed plane by Corollary \ref{c:connected}.
\end{proof}

We conclude the paper by applying Corollary \ref{c:connected} to two natural random graph models.
An \emph{Erd\"{o}s-R\'{e}nyi random graph} $G_{n,p}$ is a graph with $n$ vertices where each edge exists with probability $p$.

\begin{cor}
Let $G_{n,p}$ be an Erd\"{o}s-R\'{e}nyi random graph with
\begin{align*}
p = \frac{\log (n) + k\log \log (n) + c_n}{n}
\end{align*}
for some positive integer $k$ and some real sequence $(c_n)_{n \in \mathbb{N}}$.
Then the following holds for any analytic normed plane $X$.
\begin{enumerate}[(i)]
\item\label{c:errandom1} If $k = 1$ then:
\begin{enumerate}[(a)]
\item $G_{n,p}$ is rigid in $X$ a.a.s. if $c_n \rightarrow \infty$.
\item $G_{n,p}$ is flexible in $X$ a.a.s. if $c_n \rightarrow -\infty$.
\end{enumerate}
\item\label{c:errandom2} If $k = 2$ then:
\begin{enumerate}[(a)]
\item $G_{n,p}$ is globally rigid in $X$ a.a.s. if $c_n \rightarrow \infty$.
\item $G_{n,p}$ is not globally rigid in $X$ a.a.s. if $c_n \rightarrow -\infty$.
\end{enumerate}
\end{enumerate}
\end{cor}

\begin{proof}
We first consider the case where $c_n \rightarrow \infty$.
By \cite[Corollary 1.2]{LNPR},
$G_{n,p}$ is rigid in $\mathbb{E}^{k+1}$ a.a.s.
First suppose $k=1$.
As $G_{n,p}$ is rigid in $\mathbb{E}^{2}$ a.a.s.,
Theorem \ref{thm:rigide} implies $G_{n,p}$ contains a spanning $(2,3)$-tight subgraph $H$ a.a.s.
Since the expected number of edges of $G_{n,p}$ is $\frac{1}{2}(n-1)(\log (n) + \log \log (n) + c_n)$ which is strictly larger than $2n-3$ for sufficiently large $n$,
there exists an edge $e \in E(G_{n,p}) \sm E(H)$ a.a.s.
As $H+e$ (when both $H$ and $e$ exist) is a $(2,2)$-tight graph,
$G_{n,p}$ is rigid in $X$ a.a.s. by Theorem \ref{thm:rigidne}.
Now suppose $k=2$.
By \cite[Theorem 1.18]{GHT},
$G_{n,p}$ is globally rigid in $\mathbb{E}^2$ a.a.s.
Since the expected number of edges of $G_{n,p}$ is $\frac{1}{2}(n-1)(\log (n) + \log \log (n) + c_n)$ which is strictly larger than $2n-2$ for sufficiently large $n$,
$G_{n,p}$ is globally rigid in $X$ a.a.s. by Corollary \ref{cor:euclidean}.

We now consider the case where $c_n \rightarrow -\infty$.
Here we have that $G_{n,p}$ has minimum degree at most $k$ a.a.s.;
see \cite[Section 7]{boll} for more details.
If $k=1$ then $G_{n,p}$ is flexible in $X$ a.a.s.
If $k=2$ then $G_{n,p}$ is not redundantly rigid in $X$ a.a.s., and hence is not globally rigid in $X$ a.a.s., by Theorem \ref{thm:grne}.
\end{proof}

Let $\mathcal{G}_{n,k}$ be the set of all $k$-regular graphs with $n$ vertices.
By equipping the set $\mathcal{G}_{n,k}$ with the uniform probability measure,
we define a graph chosen at random from $\mathcal{G}_{n,k}$ to be a \emph{random $k$-regular graph}.

\begin{cor}
Let $G$ be a random $k$-regular graph and let $X$ be an analytic normed plane.
If $k \geq 4$ then $G$ is globally rigid in $X$ a.a.s.
\end{cor}

\begin{proof}
A random $k$-regular graph is $k$-connected a.a.s. [61],
hence $G$ is globally rigid in $X$ a.a.s. by Corollary \ref{c:connected}.
\end{proof}

\bibliographystyle{abbrv}
\def\lfhook#1{\setbox0=\hbox{#1}{\ooalign{\hidewidth
\lower1.5ex\hbox{'}\hidewidth\crcr\unhbox0}}}
\begin{thebibliography}{40}

[1] T. G. Abbott, \emph{Generalizations of Kempe’s Universality Theorem}, Masters thesis, MIT, 2008.

[2] R. Abraham, J. E. Marsden, {\em Foundations of mechanics, second edition}, Addison-Wesley, Reading Massachusetts, 1978.

[3] B. Anderson, P. Belhumeur, T. Eren, D. Goldenberg, A. Morse, W. Whiteley and Y. Yang, \emph{Graphical properties of easily localizable sensor networks}, Wireless Networks 15:2, 2009, 177--191.

[4] L. Asimow and B. Roth, \emph{The rigidity of graphs}, Transactions of the American Mathematical Society 245, 1978, 279--289.

[5] B.~Beauzamy, {\em Introduction to Banach spaces and their geometry}, North-Holland Mathematics Studies, 68. Notas de Matemática [Mathematical Notes], 86. North-Holland Publishing Co., Amsterdam, 1985.

[6] A. Berg and T. Jordan,
\emph{A Proof of Connelly's Conjecture on $3$-connected Circuits of the Rigidity Matroid},
J. Combin. Theory Ser. B 88, 2003, 77--97.

[7] A. R. Berg and T. Jord\'an, \emph{Algorithms for graph rigidity and scene analysis}, In: Algorithms-ESA 2003, volume 2832 of Lecture Notes in Comput. Sci., Springer, Berlin, 2003, 78--89.

[8] B. Bollob\'{a}s, {\em Random graphs, second edition},  Cambridge  Studies in Advanced Mathematics 73, Cambridge University Press, Cambridge, 2001.

[9] P.A. Catlin, \emph{Edge-connectivity and edge-disjoint spanning trees}, preprint, 2005, \url{https://math.wvu.edu/~hlai2/Pdf/Catlin_Pdf/Catlin49a.pdf}.

[10] G. Chartrand, \emph{A graph-theoretic approach to a communications problem}, SIAM J. Appl. Math. 14:4, 1966, 778--781.

[11] S.M. Cioabă, S. Dewar, G. Grasegger, X. Gu \emph{Graph rigidity properties of Ramanujan graphs}, preprint, 2022, arXiv:2206.03983.

[12] I.~Cioranescu, {\em Geometry of Banach spaces, duality mappings and nonlinear problems}, Mathematics and its Applications, 62. Kluwer Academic Publishers Group, Dordrecht, 1990.

[13] R. Connelly, \emph{Rigidity and energy}, Inventiones, 66:1, 1982, 11--33.

[14] R. Connelly, \emph{Generic global rigidity}, Discrete and Computational Geometry 33, 2005, 549--563.

[15] R. Connelly and W. Whiteley, \emph{Global rigidity: the effect of coning}, Discrete Comput. Geom. 43:4, 2010, 717--735.

[16] C.R. Coullard and L. Hellerstein, \emph{Independence and port oracles for matroids, with an application to computational learning theory}, Combinatorica 16, 1996, 189--208.

[17] S. Dewar, {\em The rigidity of countable frameworks in normed spaces}, PhD thesis, Lancaster University (2019).

[18] S. Dewar, {\em Infinitesimal rigidity in normed planes}, SIAM J. Discrete Math. 34:2, 2020, 1205--1231.

[19] S. Dewar, \emph{Infinitesimal rigidity and prestress stability for frameworks in normed spaces}, preprint, 2021, arXiv:2109.14468.

[20] S. Dewar, \emph{Equivalence of continuous, local and infinitesimal rigidity in normed spaces}, Discrete Comput. Geom. 65, 2021, 655--679.

[21] S. Dewar, J. Hewetson and A. Nixon, \emph{Coincident-point rigidity in normed planes}, preprint, 2021, arXiv:2112.10480.

[22] S. Dewar, D. Kitson and A. Nixon, {\em Which graphs are rigid in $\ell_p^d$?}, Journal of Global Optimization 83, 2022, 49--71.

[23] S. Dewar and A. Nixon, \emph{Generalised rigid body motions in non-Euclidean planes with applications to global rigidity}, Journal of Mathematical Analysis and its Applications, 514:1, 2022, 126259.

[24] A. Frank, \emph{Connections in combinatorial optimization}, Oxford Lecture Series in Mathematics and Its Applications, 2011.

[25] C. Godsil, G. F. Royle, {\em Algebraic Graph Theory: Volume 207 of Graduate Texts in Mathematics}, Springer Science \& Business Media, 2013.

[26] S. Gortler, A. Healy and D. Thurston, \emph{Characterizing generic global rigidity}, American Journal of Mathematics 132:4, 2010, 897--939.

[27] S. Gortler and D. Thurston, \emph{Characterizing the universal rigidity of generic frameworks}, Discrete Comput. Geom. 51, 2014, 1017--1036.

[28] S. Gortler and D. Thurston, \emph{Generic Global Rigidity in Complex and Pseudo-Euclidean Spaces},  In: Rigidity and Symmetry, Fields Institute Communications 70, Springer, New York, NY, 2014, 131--154.

[29] A. Hellwig, L. Volkmann,
\emph{The connectivity of a graph and its complement},
Discrete Applied Mathematics 156:17, 2008, 3325--3328.

[30] B. Hendrickson, \emph{Conditions for unique graph realizations}, SIAM Journal on Computing 21:1, 1992, 65--84.

[31] B. Jackson and T. Jord\'{a}n, \emph{Connected Rigidity Matroids and Unique Realisations of Graphs}, Journal of Combinatorial Theory, Series B 94, 2005, 1--29.

[32] B. Jackson, V. Kaszanitzky and A. Nixon, \emph{Rigid cylindrical frameworks with two coincident points}, Graphs and Combinatorics 35:1, 2019, 141--168.

[33] B. Jackson and A. Nixon, \emph{Global rigidity of generic frameworks on the cylinder}, Journal of Combinatorial Theory, Series B 139, 2019, 193--229.

[34] B.~Jackson, B.~Servatius, H.~Servatius, {\em The 2-dimensional rigidity of certain families of graphs}, J. Graph Theory 54:2, 2007, 154--166.

[35] E. Kastis, D. Kitson and J. McCarthy, \emph{Symbol Functions for Symmetric Frameworks}, Journal of Mathematical Analysis and Applications 497:2, 2021, 124895.

[36] D. Kitson, \emph{Finite and infinitesimal rigidity with polyhedral norms}, Discrete and Computational Geometry 54:2, 2015, 390--411.

[37] D. Kitson and R. Levene, \emph{Graph rigidity for unitarily invariant matrix norms}, Journal of Mathematical Analysis and Applications 491:2, 2020, 124353.

[38] D. Kitson, A. Nixon and B. Schulze, \emph{Rigidity of symmetric frameworks in normed spaces}, Linear Algebra and its Applications 607, 2020, 231--285.

[39] D. Kitson and S.C. Power, \emph{Infinitesimal rigidity for non-Euclidean bar-joint frameworks}, Bulletin of the London Mathematical Society 46:4, 2014, 685--697.

[40] S. G. Krantz and H. R. Parks, {\em A primer of real analytic functions}, Birkh\"{a}user Verlag, 1992.

[41] G. Laman, \emph{On graphs and rigidity of plane skeletal structures}, Journal of Engineering Mathematics 4, 1970, 331--340.

[42] C. Lavor, L. Liberti, B. Donald, B. Worley, B. Bardiaux, T. Malliavin and M. Nilges, \emph{Minimal NMR distance information for rigidity of protein graphs}, Discrete Applied Mathematics 256, 2019, 91--104.

[43] J. Lee, {\em Manifolds and differential geometry}, Graduate studies in mathematics Volume 107, American Mathematical Society, Providence RI, 2010.

[44] A. Lee and I. Streinu, {\em Pebble game algorithms and sparse graphs}, Discrete Math. 308:8, 2008, 1425--1437.

[45] A. Lew, E. Nevo, Y. Peled and O.E. Raz, {\em Sharp threshold for rigidity of random graphs}, preprint, 2022, arXiv:2202.09917.

[46] J. E. Marsden, T. Raitu, R. Abraham, \emph{Manifolds, tensor analysis, and applications, third edition}, Springer-Verlag New York, 2002.

[47] S. Mazur and S. M. Ulam, \emph{Sur les transformations isométriques d’espaces vectoriels normés}, Comptes Rendus de l'Académie des Sciences Paris 194, 1932, 946--948.

[48] B.~Mityagin, \emph{The zero set of a real analytic function}, preprint, 2015, arXiv:1512.07276.

[49] C. Nash-Williams, \emph{Edge-disjoint spanning trees of finite graphs}, Journal of the London Mathematical Society 36, 1961, 445--450.

[50] A. Nixon, \emph{A constructive characterisation of circuits in the simple $(2,2)$-sparsity matroid}, European Journal of Combinatorics 42, 2014, 92--106.

[51] A. Nixon, J.C. Owen, and S.C. Power, \emph{Rigidity of frameworks supported on surfaces}, SIAM Journal on Discrete Mathematics 26:4, 2012, 1733--1757.

[52] A. Nixon, B. Schulze and W. Whiteley, \emph{Rigidity through a projective lens}, Applied Sciences 11:24, 2021, 11946.

[53] A. Nixon and W. Whiteley, \emph{Change of metrics in rigidity theory}, In: Handbook of Geometric Constraint Systems Principles, 2018.

[54] H. Pollaczek-Geiringer, \emph{Uber die Gliederung ebener Fachwerke}, Zeitschrift fur Angewandte Mathematik und Mechanik (ZAMM) 7, 1927, 5--72.

[55] F. Saliola and W. Whiteley, \emph{Some notes on the equivalence of first-order rigidity in various geometries}, preprint, 2007 arXiv:0709.3354.

[56] S. Tanigawa, \emph{Sufficient conditions for the global rigidity of graphs}, Journal of Combinatorial Theory, Series B 113, 2015, 123--140.

[57] R. Tarjan, \emph{Depth-first search and linear graph algorithms}, SIAM Journal on Computing 1:2, 1972, 146–-160.

[58] A. C. Thompson, {\em Minkowski geometry}, Encyclopedia of Mathematics and its Applications, Cambridge University Press, 1996.

[59] M.E.~Watkins, {\em Connectivity of transitive graphs}, Journal of Combinatorial Theory 8:1, 1970, 23--29.

[60] W.~Whiteley, {\em Vertex splitting in isostatic frameworks}, Structural Topology 16, 1990, 23--30.

[61] N.C. Wormald, {\em The asymptotic connectivity of labelled regular graphs}, Journal of Combinatorial Theory Series B 31:2, 1981, 156--167.

\end{thebibliography}

\end{document}


# Automatic Exploration of Textual Environments with Language-Conditioned
Autotelic Agents

Laetitia Teodorescu
Inria
<EMAIL_ADDRESS>
Xingdi Yuan
Microsoft Research
<EMAIL_ADDRESS>
Marc-Alexandre Côté
Microsoft Research
<EMAIL_ADDRESS>
Pierre-Yves Oudeyer
Inria
<EMAIL_ADDRESS>
This extended abstract discusses the opportunities and challenges of studying
intrinsically-motivated agents for exploration in textual environments.

Humans begin their life with very few skills, and over the course of only a
few years learn complex motor coordination and locomotion capabilities, begin
mastering vocalization and language, and form a rich model of their physical
and social surroundings. One of the main drivers of this phenomenal knowledge
acquisition is intrinsically-motivated exploration Oudeyer and Kaplan (2007),
for instance through exploratory play Chu and Schulz (2020); Davidson et al.
(2022). The developmental perspective on AI tries to emulate this exploratory
behavior in artificial agents to achieve mastery of diverse and complex
repertoires of skills Forestier et al. (2017). When placed in open-ended
environments, a successful intrinsically motivated agent will explore the
space of interesting and diverse outcomes, ignoring random and unachievable
subspaces of the world, reusing its previously acquired skills as stepping
stones Stanley and Lehman (2015) to discover new ones.

One possible implementation of exploration in RL agents are so-called
autotelic agents Colas (2021), that is, goal-conditioned Reinforcement
Learning (RL) agents operating in rewardless environments that are able to
choose what goal to pursue. In this case, the reward is given by a goal-
satisfaction function and not extrinsically by the environment. Goal-
conditioned policies have been extensively studied in the case of extrinsic
goals Schaul et al. (2015). In the case of intrinsically chosen goals, the
goal-selection mechanism allows autotelic agents to form a self-curriculum,
progressing from easier to increasingly harder goals until all achievable
skills have been mastered. In this perspective, the goal representation is of
paramount importance. Most previous works (for instance Andrychowicz et al.
(2017)) have used concrete end-state representations such as raw observations,
images or embeddings, which has some drawbacks. A goal should be insensitive
to changes in the environment that are uncontrollable (such as the color of
the sky), to avoid the agent targeting impossible goals (for instance changing
the sky color), or to provide useful abstraction for goal achievement (such as
considering the goal of navigating to the garden is satisfied regardless of
sky color). Furthermore, the agent should ideally be able to combine known
goals into novel ones. Goals expressed as language Tam et al. (2022); Colas et
al. (2020); Mu et al. (2022) fulfill both conditions: they are at once
abstract and combinatorial Szabó (2020); they are thus a prime way for
autotelic agents to self-specify goals to be executed in the environment.

##  1 A bridge between autotelic agents and text environments

The main point of this essay is the relevance of studying language autotelic
agents in textual environments Côté et al. (2018); Hausknecht et al. (2020);
Wang et al. (2022), both for testing exploration methods in a context that is
at once simple experimentally and rich from the perspective of environment
interactions; and for transferring the skills of general-purpose agents
trained to explore in an autonomous way to the predefined tasks of textual
environment benchmarks. We identify three key properties, plus one additional
benefit, of text worlds:

1. Depth of learnable skills: skills learnable in the world should involve multiple low-level actions and be nested, such that mastering one skill opens up the possibility of mastering more complex skills. Interactive fiction (IF) Hausknecht et al. (2020) games usually feature an entire narrative and extensive maps, such that navigating and passing obstacles requires many successful actions (and subgoals) to be completed. While the original TextWorld levels were not as deep as would be desirable, other non-IF text worlds such as ScienceWorld feature nested repertoires of skills (such as learning to navigate to learn to grow plants to learn the rules of Mendelian genomics);

2. Breadth of the world: there should be many paths to explore in the environment; this ensures that we train agents that are able to follow a wide diversity of possible goals, instead of learning to achieve goals along a linear path. This allows us to study generally-capable agents. Some IF games are very linear, having a clear progression from start to finish (e.g., Acorn Court, Detective; others have huge maps that an agent has to explore before it can progress in the quest (e.g., Zork, Hitchhiker’s Guide to the Galaxy). Exploration heuristics are a part of some successful methods for playing IF with RL Yao et al. (2020). ScienceWorld Wang et al. (2022) has an underlying physical engine allowing for a combinatorial explosion of possibilities like making new objects, combining existing objects, changing states of matter, etc.

3. Niches of progress: real-world environments have both easy skills and unlearnable skills. Our simulated environments should mimic this property to test the agent’s ability to focus only on highly learnable parts of the space and avoid spending effort on uncontrollable aspects of the environment. In textual environments, high depth implies that some skills are much more learnable than others, already implementing some progress niches. The combinatorial property of language goals allows us to define many unfeasible goals, goals that an autotelic agent has to avoid spending too many resources on.

4. Language representation for goals: a language-conditioned agent has to learn to ground its goal representation in its environment Harnad (1990); Hill et al. (2020), to know when a given observation or sequence of observations satisfies a given goal, or to know what goals were achieved in a given trajectory. This grounding is made much simpler in environments with a single modality; relating language goals to language observations is simpler than grounding language in pixels or image embeddings. This allows us to study language-based exploration in a simpler context.

##  2 Drivers of exploration in autotelic agents

We identify three main drivers of exploration in autotelic agents.
Environments we use should support exploration algorithms that implement these
principles; the resulting agents then have a chance to acquire a diverse set
of skills that can be repurposed for solving the benchmarks proposed by
textual environments.

1. Goal self-curriculum: automatic goal selection Portelas et al. (2020) allows the agent to refine its skills on the edge of what it currently masters. Among metrics used to select goals are novelty/surprise of a goal Tam et al. (2022); Burda et al. (2018), intermediate competence on goals Campero et al. (2020), ensemble disagreement Pathak et al. (2019), or (absolute) learning progress Colas et al. (2019). Progress niches in textual environments support such goal curriculum;

2. Additional exploration after goal achievement: after achieving a given goal, the agent continue to run for a time to push the boundary of explored space Ecoffet et al. (2021). The depth of text worlds makes goal chaining relevant, such that an agent that has achieved a known goal can imagine additional goals to pursue. Random exploration can also be used once a known goal has been achieved. Agents exploring in textual environments and choosing uniformly among the set of valid actions in a given state have a high chance of effecting meaningful changes in the environment, making discovery of new skills probable. This property is relevant in any environment with high depth, and both IF and ScienceWorld fit this description.

3. Goal composition: as mentioned above, this means using the compositionality afforded by language goals to imagine novel goals in the environment Colas et al. (2020). Goal-chaining is an example of composition, but language offers many other composition possibilities, such as recombining known verbs, nouns and attributes in novel ways, or making analogies. This is relevant if there exists some transfer between the skills required to accomplish similar goal constructions (e.g., picking up an apple and picking up a carrot requires very similar actions if both are in the kitchen). This is at least partially true in textual environments where objects of the same type usually have similar affordances.

##  3 Challenges for autotelic textual agents

Text worlds bring a set of unique challenges for autotelic agents, among which
we foresee:

1. The goal space can be very large. An agent with a limited training budget needs to focus on a subset of the goal space, possibly discovering only a fraction of what is discoverable within the environment. This calls for finer goal-sampling approaches that encourage the agent at making the most out of its allocated time to explore the environment. In addition, we need better methods to push the agent’s exploration towards certain parts of the space (e.g., warm-starting the replay buffer with existing trajectories, providing linguistic common-sense knowledge);

2. The action space is also very large in textual environments, making exploration (especially methods based on random action selection) potentially challenging.

3. Agents must be trajectory-efficient for a given goal; complex goals might be seen only once;

4. Catastrophic forgetting needs to be alleviated, so that learning to achieve new goals does not impair the skills learned previously;

5. Partial observability means that agent architectures need to include some form of memory.

Agents trained in such environments will learn a form of language use, not by
predicting the most likely sequence of words from a large-scale dataset
Radford and Narasimhan (2018); Brown et al. (2020) but by learning to use it
pragmatically to effect changes in the environment. Of course, the limits of
the autotelic agent’s world will mean the limits of its language; an
interesting development is to build agents that explore textual environments
to refine external linguistic knowledge provided by a pretrained language
model. This external knowledge repository can be seen as culturally-
accumulated common sense, a perspective that is related to so-called
Vygotskian AI Colas (2021) in which a developmental agent learns by
interacting with an external social partner that imparts outside language
knowledge and organizes the world so as to facilitate the autotelic agent’s
exploration.

To conclude, textual environments are ideal testbeds for autotelic language-
conditioned agents, and conversely such agents can bring progress on text
world benchmarks. There is also promise in the interaction between exploratory
agents and large language models encoding exterior linguistic knowledge.
Preliminary steps have been taken in this direction Madotto et al. (2020) but
the full breadth of drivers of exploration we identify has yet to be studied.
We hope to foster discussion, define concrete implementations and identify
challenges by bringing together the developmental perspective on AI and the
textual environment community.

## References

  * Andrychowicz et al. (2017) Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Pieter Abbeel, and Wojciech Zaremba. 2017.  Hindsight experience replay.  _Advances in neural information processing systems_ , 30.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Burda et al. (2018) Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. 2018.  Exploration by random network distillation.  _arXiv preprint arXiv:1810.12894_.
  * Campero et al. (2020) Andres Campero, Roberta Raileanu, Heinrich Küttler, Joshua B Tenenbaum, Tim Rocktäschel, and Edward Grefenstette. 2020.  Learning with amigo: Adversarially motivated intrinsic goals.  _arXiv preprint arXiv:2006.12122_.
  * Chu and Schulz (2020) Junyi Chu and Laura Schulz. 2020.  Play, curiosity, and cognition.  _Annual Review of Developmental Psychology_ , 2.
  * Colas (2021) Cédric Colas. 2021.  _Towards Vygotskian Autotelic Agents : Learning Skills with Goals, Language and Intrinsically Motivated Deep Reinforcement Learning_.  Theses, Université de Bordeaux.
  * Colas et al. (2019) Cédric Colas, Pierre Fournier, Mohamed Chetouani, Olivier Sigaud, and Pierre-Yves Oudeyer. 2019.  Curious: intrinsically motivated modular multi-goal reinforcement learning.  In _International conference on machine learning_ , pages 1331–1340. PMLR.
  * Colas et al. (2020) Cédric Colas, Tristan Karch, Nicolas Lair, Jean-Michel Dussoux, Clément Moulin-Frier, Peter Dominey, and Pierre-Yves Oudeyer. 2020.  Language as a cognitive tool to imagine goals in curiosity driven exploration.  _Advances in Neural Information Processing Systems_ , 33:3761–3774.
  * Côté et al. (2018) Marc-Alexandre Côté, Akos Kádár, Xingdi Yuan, Ben Kybartas, Tavian Barnes, Emery Fine, James Moore, Matthew Hausknecht, Layla El Asri, Mahmoud Adada, et al. 2018.  Textworld: A learning environment for text-based games.  In _Workshop on Computer Games_ , pages 41–75. Springer.
  * Davidson et al. (2022) Guy Davidson, Todd M Gureckis, and Brenden M Lake. 2022.  Creativity, compositionality, and common sense in human goal generation.
  * Ecoffet et al. (2021) Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. 2021\.  First return, then explore.  _Nature_ , 590(7847):580–586.
  * Forestier et al. (2017) Sébastien Forestier, Rémy Portelas, Yoan Mollard, and Pierre-Yves Oudeyer. 2017.  Intrinsically motivated goal exploration processes with automatic curriculum learning.  _arXiv preprint arXiv:1708.02190_.
  * Harnad (1990) Stevan Harnad. 1990.  The symbol grounding problem.  _Physica D: Nonlinear Phenomena_ , 42(1-3):335–346.
  * Hausknecht et al. (2020) Matthew Hausknecht, Prithviraj Ammanabrolu, Marc-Alexandre Côté, and Xingdi Yuan. 2020.  Interactive fiction games: A colossal adventure.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 7903–7910.
  * Hill et al. (2020) Felix Hill, Olivier Tieleman, Tamara von Glehn, Nathaniel Wong, Hamza Merzic, and Stephen Clark. 2020.  Grounded language learning fast and slow.  _arXiv preprint arXiv:2009.01719_.
  * Madotto et al. (2020) Andrea Madotto, Mahdi Namazifar, Joost Huizinga, Piero Molino, Adrien Ecoffet, Huaixiu Zheng, Alexandros Papangelis, Dian Yu, Chandra Khatri, and Gokhan Tur. 2020.  Exploration based language learning for text-based games.  _arXiv preprint arXiv:2001.08868_.
  * Mu et al. (2022) Jesse Mu, Victor Zhong, Roberta Raileanu, Minqi Jiang, Noah Goodman, Tim Rocktäschel, and Edward Grefenstette. 2022.  Improving intrinsic exploration with language abstractions.  _arXiv preprint arXiv:2202.08938_.
  * Oudeyer and Kaplan (2007) Pierre-Yves Oudeyer and Frederic Kaplan. 2007.  What is intrinsic motivation? a typology of computational approaches.  _Frontiers in neurorobotics_ , 1:6–6.  18958277[pmid].
  * Pathak et al. (2019) Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. 2019.  Self-supervised exploration via disagreement.  In _International conference on machine learning_ , pages 5062–5071. PMLR.
  * Portelas et al. (2020) Rémy Portelas, Cédric Colas, Lilian Weng, Katja Hofmann, and Pierre-Yves Oudeyer. 2020.  Automatic curriculum learning for deep rl: A short survey.  _arXiv preprint arXiv:2003.04664_.
  * Radford and Narasimhan (2018) Alec Radford and Karthik Narasimhan. 2018.  Improving language understanding by generative pre-training.
  * Schaul et al. (2015) Tom Schaul, Dan Horgan, Karol Gregor, and David Silver. 2015.  Universal value function approximators.  page 1312–1320.
  * Stanley and Lehman (2015) Kenneth O. Stanley and Joel Lehman. 2015.  _Why Greatness Cannot Be Planned: The Myth of the Objective_.  Springer Publishing Company, Incorporated.
  * Szabó (2020) Zoltán Gendler Szabó. 2020.  Compositionality.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_ , Fall 2020 edition. Metaphysics Research Lab, Stanford University.
  * Tam et al. (2022) Allison C Tam, Neil C Rabinowitz, Andrew K Lampinen, Nicholas A Roy, Stephanie CY Chan, DJ Strouse, Jane X Wang, Andrea Banino, and Felix Hill. 2022\.  Semantic exploration from language abstractions and pretrained representations.  _arXiv preprint arXiv:2204.05080_.
  * Wang et al. (2022) Ruoyao Wang, Peter Jansen, Marc-Alexandre Côté, and Prithviraj Ammanabrolu. 2022.  Scienceworld: Is your agent smarter than a 5th grader?  _arXiv preprint arXiv:2203.07540_.
  * Yao et al. (2020) Shunyu Yao, Rohan Rao, Matthew Hausknecht, and Karthik Narasimhan. 2020.  Keep calm and explore: Language models for action generation in text-based games.  _arXiv preprint arXiv:2010.02903_.