# Hyperbolic inflationary model with nonzero curvature

Andronikos Paliathanasis<EMAIL_ADDRESS>Institute of Systems Science,
Durban University of Technology, PO Box 1334, Durban 4000, South Africa
Instituto de Ciencias Físicas y Matemáticas, Universidad Austral de Chile,
Valdivia 5090000, Chile  Genly Leon<EMAIL_ADDRESS>Departamento de
Matemáticas, Universidad Católica del Norte, Avda. Angamos 0610, Casilla 1280
Antofagasta, Chile  Institute of Systems Science, Durban University of
Technology, PO Box 1334, Durban 4000, South Africa

###### Abstract

We consider a cosmological model consisting of two scalar fields defined in
the hyperbolic plane known as hyperbolic inflation. For the background space,
we consider a homogeneous and isotropic spacetime with nonzero curvature. We
study the asymptotic behaviour of solutions and we search for attractors in
the expanding regime. We prove that two hyperbolic inflationary stages are
stable solutions that can solve the flatness problem and describe acceleration
for both open and closed models, and additionally we obtain a Milne-like
attractor solution for the open model. We also investigate the contracting
branch obtaining mirror solutions with the opposite dynamical behaviours.

Scalar field; Multi-scalar field; Dynamical analysis; curvature

###### pacs:

98.80.-k, 95.35.+d, 95.36.+x

##  I Introduction

A simple mechanism that has been proposed to solve the homogeneity, isotropy,
and flatness problems are the so-called cosmic inflation guth ; lin . In the
inflation, the universe has gone through a rapid expansion which has been
driven by an exotic matter source with a negative pressure component known as
inflation. The importance of rapid expansion is that the size of the universe
increases so fast that it loses its memory of the initial conditions. The
source and the nature of the inflationary mechanism are still unknown. There
are various approaches which are based on scalar fields in01 ; in02 ; in03 ;
in04 ; in05 ; bsjd , on Chaplygin Gas in06 ; in07 ; in08  or on the
modification of the Einstein-Hilbert Action Integral in09 ; in10 ; in11 ; in12
.

An inflationary model which has drawn the attention of cosmologists in recent
years is the so-called hyperbolic inflation ch5 . It is a two-scalar field
inflationary model in which the kinetic part of the scalar fields lies on a
hyperbolic plane. The model is inspired by the $\sigma$-theory and this kind
of model has been widely studied as a dark energy alternative in the past sch1
; sch2 ; sch3 ; ch3 ; ch4 . In hyperbolic inflation, for the exponential
potential, the inflationary era is attributed to a scaling attractor in which
the inflation consists of the two-scalar fields and it does not slow-roll ch2
. Furthermore, because the scalar fields do not need to have the same values
at the beginning and the end of inflation, that means that there are no
observable non-Gaussianities in the power spectrum ch6 ; ch7 . The analytic
solution for the cosmological field equations of the hyperbolic inflation in a
spatially flat Friedmann–Lemaître–Robertson–Walker (FLRW) background space was
determined in sco01 . Other extensions were proposed recently in sco02 ; sco03
. Recently, the scalar hyperbolic inflationary model was investigated in the
case of anisotropic spacetimes, in which analytic solutions were determined
sco03 , while the dynamics were investigated in sco04 .

In this study, we investigate the dynamics of the hyperbolic inflation model
in the case of FLRW spacetime with nonzero curvature. Specifically, we are
interested to investigate if the given model can drive the dynamics so that a
future attractor be the inflationary solution or another spatially flat FLRW
universe. With this analysis, we shall understand further if this specific
multi-field model can solve the flatness problem. The dynamical analysis is an
essential approach for the study of physical viability for given gravitational
theories. See for instance dn1 ; dn2 ; dn3  and references therein.

The plan of the paper is as follows. In Section II we present the model of our
consideration and we define the field equations. Section III includes the main
analysis of this study in which we investigate the asymptotic dynamics for the
field equations. Finally, in Section V we discuss our results.

##  II Hyperbolic inflation

We consider the two-scalar field model ch5

$S=\int\sqrt{-g}dx^{4}\left(R-\frac{1}{2}g^{\mu\nu}\nabla_{\mu}\phi\nabla_{\nu}\phi-\frac{1}{2}g^{\mu\nu}e^{2\kappa\phi}\nabla_{\mu}\psi\nabla_{\nu}\psi-V\left(\phi\right)\right),$
(1)

where the two scalar fields $\phi\left(x^{\mu}\right)$ and
$\psi\left(x^{\nu}\right)$ have kinetic terms which lie on a two-dimensional
hyperbolic manifold.

For the background space we assume the FLRW universe

$ds^{2}=-dt^{2}+a^{2}\left(t\right)\left(\frac{dr^{2}}{1-Kr^{2}}+r^{2}\left(d\theta^{2}+\sin^{2}\theta
d\phi^{2}\right)\right),$ (2)

where $K$ is the spatial curvature for the three-dimensional hypersurface. For
$K=0$, we have a spatially flat universe, for $K=1$ we have a closed universe
and for $K=-1$ the line element (2) describes an open universe. In previous
studies the cosmological model with Action Integral (1) has been investigated
for $K=0$ ch2 . In the following we consider the case $K\neq 0$. Moreover, we
assume that the scalar fields inherit the symmetries of the spacetime (2)
which means $\phi\left(x^{\mu}\right)=\phi\left(t\right)$ and
$\psi\left(x^{\mu}\right)=\psi\left(t\right)$.

For the line element (2) and the Action Integral (1) we end with the
gravitational field equations

$\displaystyle-3H^{2}+\frac{1}{2}\dot{\phi}^{2}+\frac{1}{2}e^{2\kappa\phi}\dot{\psi}^{2}+V\left(\phi\right)-3Ka^{-2}=0~{},$
(3) $\displaystyle
2\dot{H}+3H^{2}+\frac{1}{2}\dot{\phi}^{2}+\frac{1}{2}e^{2\kappa\phi}\dot{\psi}^{2}-V\left(\phi\right)+Ka^{-2}=0~{},$
(4) $\displaystyle\ddot{\phi}+3H\dot{\phi}-\kappa
e^{2\kappa\phi}\dot{\psi}^{2}+V_{,\phi}\left(\phi\right)=0,$ (5)
$\displaystyle\ddot{\psi}+3H\dot{\psi}+2\kappa\dot{\phi}\dot{\psi}=0~{},$ (6)

where $H=\frac{\dot{a}}{a}$ is the Hubble function.

We can define the effective energy density, $\rho_{eff}$, and the effective
pressure, $p_{eff},~{}$as

$\displaystyle\rho_{eff}=\frac{1}{2}\dot{\phi}^{2}+\frac{1}{2}e^{2\kappa\phi}\dot{\psi}^{2}+V\left(\phi\right),$
(7) $\displaystyle
p_{eff}=\frac{1}{2}\dot{\phi}^{2}+\frac{1}{2}e^{2\kappa\phi}\dot{\psi}^{2}-V\left(\phi\right)~{}.$
(8)

Thus, the parameter for the equation of state for the effective cosmological
fluid is

$w_{eff}=\frac{p_{eff}}{\rho_{eff}}=\frac{\frac{1}{2}\dot{\phi}^{2}+\frac{1}{2}e^{2\kappa\phi}\dot{\psi}^{2}-V\left(\phi\right)}{\frac{1}{2}\dot{\phi}^{2}+\frac{1}{2}e^{2\kappa\phi}\dot{\psi}^{2}+V\left(\phi\right)}~{},$
(9)

while the deceleration parameter in the presence of spatial curvature is
$q=-1-\dot{H}/H^{2}$ and $\Omega_{K}=K\left(aH\right)^{-2}$.

##  III Dynamical analysis

In order to investigate the dynamics and the asymptotic behaviour of the field
equations we define new dimensionless variables. Indeed, we assume the new
independent variable, $d\tau=\sqrt{H^{2}+|K|a^{-2}}dt$, and the new dependent
variables

$\displaystyle\lambda=\frac{V^{\prime}\left(\phi\right)}{V\left(\phi\right)},x=\frac{\dot{\phi}}{\sqrt{6}\sqrt{H^{2}+|K|a^{-2}}},y^{2}=\frac{V\left(\phi\right)}{3\left(H^{2}+|K|a^{-2}\right)},$
(10) $\displaystyle
z=e^{\kappa\phi}\frac{\dot{\psi}}{\sqrt{6}\sqrt{H^{2}+|K|a^{-2}}},\eta=\frac{H}{\sqrt{H^{2}+|K|a^{-2}}}.$
(11)

The functional forms of the field equations depend upon the sign of curvature
$K$. That is,

$\displaystyle\frac{d\lambda}{d\tau}$
$\displaystyle=\sqrt{6}x\lambda^{2}\left(\Gamma\left(\lambda\right)-1\right),\quad\Gamma\left(\lambda\right)=\frac{1}{\lambda}\frac{V_{\phi\phi}}{V_{,\phi}},$
(12) $\displaystyle\frac{dx}{d\tau}$ $\displaystyle=\frac{1}{2}\Big{(}\eta
x\left(\text{sgn}(K)+3x^{2}-3y^{2}+3z^{2}-4\right)-\eta^{3}x(\text{sgn}(K)-1)+\sqrt{6}\left(2\kappa
z^{2}-\lambda y^{2}\right)\Big{)},$ (13) $\displaystyle\frac{dy}{d\tau}$
$\displaystyle=\frac{y}{2|K|}\Big{(}|K|\left(\eta^{3}+\eta\left(3x^{2}-3y^{2}+3z^{2}+2\right)+\sqrt{6}\lambda
x\right)+\eta\left(1-\eta^{2}\right)K\Big{)},$ (14)
$\displaystyle\frac{dz}{d\tau}$
$\displaystyle=\frac{1}{2}z\Big{(}-\left(\eta^{3}(\text{sgn}(K)-1)\right)-2\sqrt{6}\kappa
x+\eta\left(\text{sgn}(K)+3x^{2}-3y^{2}+3z^{2}-4\right)\Big{)},$ (15)
$\displaystyle\frac{d\eta}{d\tau}$
$\displaystyle=\frac{\left(\eta^{2}-1\right)\left(|K|\left(\eta^{2}+3\left(x^{2}-y^{2}+z^{2}\right)\right)+(1-\eta^{2})K\right)}{2|K|},$
(16)

with the Friedman constraint

$\eta^{2}-\left(\eta^{2}-1\right)\text{sgn}(K)-x^{2}-y^{2}-z^{2}=0.$ (17)

For the scalar field potential we assume the exponential function,
$V\left(\phi\right)=V_{0}e^{\lambda\phi}$ ch5 . In this case, $\lambda$ is a
constant parameter. Hence, we omit the additional equation (12) that is
trivially satisfied.

The deceleration parameter can be expressed in terms of the normalized
variables as

$\displaystyle q$
$\displaystyle=\frac{\eta^{2}-\eta^{2}\text{sgn}(K)+\text{sgn}(K)+3x^{2}-3y^{2}+3z^{2}}{2\eta^{2}}$
$\displaystyle=\left(1-\frac{1}{\eta^{2}}\right)\text{sgn}(K)+\frac{3\left(x^{2}+z^{2}\right)}{\eta^{2}}-1,$
(18)

and the effective equation of state parameter as

$\displaystyle
w_{eff}=1-\frac{2y^{2}}{x^{2}+y^{2}+z^{2}}=\frac{2\left(x^{2}+z^{2}\right)}{\eta^{2}+(1-\eta^{2})\text{sgn}(K)}-1.$
(19)

Now, we investigate separately the two cases, $K=1$ and $K=-1$.

###  III.1 Closed Universe

For $K=1$ the Friedmann constraint (17) reduces to

$1-x^{2}-y^{2}-z^{2}=0.$ (20)

We determine the stationary points of the system (12), (13), (14), (15) and
(16) for $K=1$ and we study their stability properties. Each stationary point
corresponds to a specific epoch of the cosmological evolution. It is important
to mention that from (20) parameters $x,y,z$ are constraints in a unitary
sphere. Moreover, we can use the constraint equation (20) to reduce the
dimension of the dynamical system. Indeed, we assume $y=\sqrt{1-x^{2}-z^{2}}$.
We remark that $y\rightarrow-y$ is a discrete symmetry for the field
equations. In addition, by definition parameter $\eta$ is constrained as
$\left|\eta\right|\leq 1$. The case $\left|\eta\right|=1$ corresponds to
spatially flat universes. A positive value of $\eta$ denotes an expanding
universe, i.e. $H>0$. Thus, in the following we focus on the expansion era
that is we assume $\eta>0$.

Label | $x$ | $z$ | $\eta$ | $e_{1}(P)$ | $e_{2}(P)$ | $e_{3}(P)$
---|---|---|---|---|---|---
$A_{1}^{+}$ | $1$ | $0$ | $1$ | $4$ | $-\sqrt{6}\kappa$ | $6+\sqrt{6}\lambda$
$A_{1}^{-}$ | $-1$ | $0$ | $1$ | $4$ | $\sqrt{6}\kappa$ | $6-\sqrt{6}\lambda$
$\bar{A}_{1}^{+}$ | $1$ | $0$ | $-1$ | $-4$ | $-\sqrt{6}\kappa$ | $-(6-\sqrt{6}\lambda)$
$\bar{A}_{1}^{-}$ | $-1$ | $0$ | $-1$ | $-4$ | $\sqrt{6}\kappa$ | $-(6+\sqrt{6}\lambda)$
$A_{2}$ | $-\frac{\lambda}{\sqrt{6}}$ | $0$ | $1$ | $\frac{1}{2}\left(\lambda^{2}-6\right)$ | $\lambda^{2}-2$ | $-3+\frac{1}{2}\lambda(2\kappa+\lambda)$
$\bar{A}_{2}$ | $\frac{\lambda}{\sqrt{6}}$ | $0$ | $-1$ | $-\frac{1}{2}\left(\lambda^{2}-6\right)$ | $-(\lambda^{2}-2)$ | $3-\frac{1}{2}\lambda(2\kappa+\lambda)$
$A_{3}^{+}$ | $-\frac{\sqrt{6}}{2\kappa+\lambda}$ | $\frac{\sqrt{2\kappa\lambda+\lambda^{2}-6}}{\sqrt{(2\kappa+\lambda)^{2}}}$ | $1$ | $4-\frac{12\kappa}{2\kappa+\lambda}$ | $-\frac{3\kappa+i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$ | $-\frac{3\kappa-i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$
$A_{3}^{-}$ | $-\frac{\sqrt{6}}{2\kappa+\lambda}$ | $-\frac{\sqrt{2\kappa\lambda+\lambda^{2}-6}}{\sqrt{(2\kappa+\lambda)^{2}}}$ | $1$ | $4-\frac{12\kappa}{2\kappa+\lambda}$ | $-\frac{3\kappa+i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$ | $-\frac{3\kappa-i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$
$\bar{A}_{3}^{+}$ | $\frac{\sqrt{6}}{2\kappa+\lambda}$ | $\frac{\sqrt{2\kappa\lambda+\lambda^{2}-6}}{\sqrt{(2\kappa+\lambda)^{2}}}$ | $-1$ | $-4+\frac{12\kappa}{2\kappa+\lambda}$ | $\frac{3\kappa+i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$ | $\frac{3\kappa-i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$
$\bar{A}_{3}^{-}$ | $\frac{\sqrt{6}}{2\kappa+\lambda}$ | $-\frac{\sqrt{2\kappa\lambda+\lambda^{2}-6}}{\sqrt{(2\kappa+\lambda)^{2}}}$ | $-1$ | $-4+\frac{12\kappa}{2\kappa+\lambda}$ | $\frac{3\kappa+i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$ | $\frac{3\kappa-i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$
$A_{4}^{+}$ | $-\frac{1}{\sqrt{3}}$ | $0$ | $\frac{\lambda}{\sqrt{2}}$ | $\sqrt{2}(\kappa-\lambda)$ | $-\frac{\lambda+\sqrt{8-3\lambda^{2}}}{\sqrt{2}}$ | $-\frac{\lambda-\sqrt{8-3\lambda^{2}}}{\sqrt{2}}$
$A_{4}^{-}$ | $\frac{1}{\sqrt{3}}$ | $0$ | $-\frac{\lambda}{\sqrt{2}}$ | $-\sqrt{2}(\kappa-\lambda)$ | $\frac{\lambda+\sqrt{8-3\lambda^{2}}}{\sqrt{2}}$ | $\frac{\lambda-\sqrt{8-3\lambda^{2}}}{\sqrt{2}}$

Table 1: The stationary points
$A=\left(x\left(A\right),z\left(A\right),\eta\left(A\right)\right)$ and
$\bar{A}=\left(x\left(\bar{A}\right),z\left(\bar{A}\right),\eta\left(\bar{A}\right)\right)$
of the dynamical system (21), (22), (23).

Hence, we obtain the reduced system:

$\displaystyle\frac{dx}{d\tau}$ $\displaystyle=3\eta
x\left(x^{2}+z^{2}-1\right)+\sqrt{\frac{3}{2}}\left(\lambda\left(x^{2}-1\right)+z^{2}(2\kappa+\lambda)\right),$
(21) $\displaystyle\frac{dz}{d\tau}$
$\displaystyle=z\left(3\eta\left(x^{2}+z^{2}-1\right)-\sqrt{6}\kappa
x\right),$ (22) $\displaystyle\frac{d\eta}{d\tau}$
$\displaystyle=\left(\eta^{2}-1\right)\left(3x^{2}+3z^{2}-1\right).$ (23)

The stationary points
$A=\left(x\left(A\right),z\left(A\right),\eta\left(A\right)\right)$ and
$\bar{A}=\left(x\left(\bar{A}\right),z\left(\bar{A}\right),\eta\left(\bar{A}\right)\right)$
of the dynamical system (21), (22), (23) are represented in table 1. Since the
points $\bar{A}$ have the time-reversal dynamical behaviour of the related
points $A$ under the change $(\tau,x,\eta)\mapsto(-\tau,-x,-\eta)$.
$A_{1}^{+}$ maps onto $\bar{A}_{1}^{-}$, $A_{1}^{-}$ maps onto
$\bar{A}_{1}^{+}$, $A_{2}$ maps onto $\bar{A}_{2}$, $A_{3}^{+}$ maps onto
$\bar{A}_{3}^{-}$, $A_{3}^{-}$ maps onto $\bar{A}_{3}^{+}$ and $A_{4}^{-}$
maps onto $A_{4}^{+}$ (where we have suppressed the bar). Then, we focus on
points $A$’s:

$\displaystyle A_{1}^{\pm}=\left(\pm
1,0,1\right),A_{2}=\left(-\frac{\lambda}{\sqrt{6}},0,1\right),$ $\displaystyle
A_{3}^{\pm}=\left(-\frac{\sqrt{6}}{2\kappa+\lambda},\pm\sqrt{\frac{\lambda^{2}+2\kappa\lambda-6}{\left(2\kappa+\lambda\right)^{2}}},1\right),A_{4}^{\pm}=\left(\mp\frac{1}{\sqrt{3}},0,\pm\frac{\lambda}{\sqrt{2}}\right).$

Stationary points, $A_{1}^{\pm}$, $A_{2}$ and $A_{3}^{\pm}$ describe spatially
flat universes. For the asymptotic solution at point $A_{1}^{\pm}$ we derive
$w_{eff}\left(A_{1}^{\pm}\right)=1$ and $q\left(A_{1}^{\pm}\right)=2$, which
means that the universe is dominated by the kinetic part of the scalar field
$\phi\left(t\right)$. Point $A_{2}$ provides
$w_{eff}\left(A_{2}\right)=\frac{\lambda^{2}-3}{3}$,
$q\left(A_{2}\right)=\frac{\lambda^{2}-2}{2}$, which is nothing other than the
quintessence scaling solution of dn1 . Acceleration occurs for
$\left|\lambda\right|<\sqrt{2}$.

Points $A_{3}^{\pm}$ describe the hyperbolic inflationary solutions,
$w_{eff}\left(A_{3}^{\pm}\right)=1-\frac{4\kappa}{2\kappa+\lambda}$ ,
$q\left(A_{3}^{\pm}\right)=2-\frac{6\kappa}{2\kappa+\lambda}$. Points are real
and physically acceptable when $2\kappa+\lambda\neq 0$ and
$\lambda^{2}+2\kappa\lambda-6>0$. Acceleration occurs when
$\left\\{\lambda\leq-\sqrt{2},\kappa<\lambda\right\\}$, or
$\left\\{-\sqrt{2}<\lambda<0,\kappa<\frac{6-\lambda^{2}}{2\lambda}\right\\}$,
or
$\left\\{0<\lambda<\sqrt{2},\kappa>\frac{6-\lambda^{2}}{2\lambda}\right\\}$,
or $\left\\{\lambda\geq\sqrt{2},\kappa>\lambda\right\\}$.

Furthermore, points $A_{4}^{\pm}$ exist for $\lambda^{2}<2$ and describe
Milne-like solutions with $a\left(t\right)=a_{0}t$ and
$w_{eff}\left(A_{4}^{\pm}\right)=-\frac{1}{3}$, $q\left(A_{4}^{\pm}\right)=0$.
Point $A_{4}^{+}$ describes an expanding universe for $\lambda>0$, while
$A_{4}^{-}$ corresponds to an expanding universe for $\lambda<0$.

To infer the stability properties of the stationary points we derive the
eigenvalues of the linearised system around the stationary points. Indeed, for
the points $A_{1}^{\pm}$ we find the eigenvalues
$e_{1}\left(A_{1}^{\pm}\right)=4$,
$e_{2}\left(A_{1}^{\pm}\right)=\mp\sqrt{6}\kappa~{}$,
$e_{3}\left(A_{1}^{\pm}\right)=6\pm\sqrt{6}\lambda$. Thus, points
$A_{1}^{\pm}$ are nonhyperbolic for $\kappa=0$ or $\lambda=\mp\sqrt{6}$. Point
$A_{1}^{+}$ is a source for $\lambda>-\sqrt{6}$ and $\kappa<0$. Point
$A_{1}^{-}$ is a source for $\lambda<\sqrt{6}$ and $\kappa>0$. Otherwise,
points $A_{1}^{\pm}$ are saddle points.

$A_{2}$ exists for $-\sqrt{6}\leq\lambda\leq\sqrt{6}$. We derive the
eigenvalues $e_{1}\left(A_{2}\right)=-3+\frac{\lambda^{2}}{2}$,
$e_{2}\left(A_{2}\right)=\lambda^{2}-2$ and
$e_{3}(A_{2})=-3+\frac{1}{2}\lambda\left(2\kappa+\lambda\right)$. Thus, point
$A_{2}$ is nonhyperbolic for $\lambda^{2}=2$ or $\lambda^{2}=6$ or
$\lambda\left(2\kappa+\lambda\right)=6$. Point $A_{2}$ is a sink when
$\lambda^{2}<2$ and $\lambda\left(2\kappa+\lambda\right)<6$, otherwise point
$A_{2}$ is a saddle point.

Points $A_{3}^{\pm}$ exist when $2\kappa+\lambda\neq 0$ and
$\lambda^{2}+2\kappa\lambda-6>0$. The eigenvalues are
$e_{1}\left(A_{3}^{\pm}\right)=4\left(1-3\frac{\kappa}{2\kappa+\lambda}\right)$,
$e_{2,3}\left(A_{3}^{\pm}\right)=-\frac{3\kappa\pm
i\sqrt{3\kappa\left(8\kappa^{2}\lambda+2\lambda\left(\lambda^{2}-6\right)+\kappa\left(8\lambda^{2}-27\right)\right)}}{2\kappa+\lambda}$.
We define
$\kappa_{\pm}=\frac{27-8\lambda^{2}}{16\lambda}\pm\frac{1}{16}\sqrt{3}\sqrt{-\frac{16\lambda^{2}-243}{\lambda^{2}}}$.
When hyperbolic, $A_{3}^{\pm}$ can be sink for
$\left\\{-\sqrt{\frac{13}{6}}<\lambda\leq-\sqrt{2},\kappa_{-}\leq\kappa<\lambda\right\\}$,
or
$\left\\{-\sqrt{2}<\lambda<0,\kappa_{-}\leq\kappa<\frac{6-\lambda^{2}}{2\lambda}\right\\}$,
or
$\left\\{0<\lambda<\sqrt{2},\frac{6-\lambda^{2}}{2\lambda}<\kappa\leq\kappa_{+}\right\\}$,
or
$\left\\{\sqrt{2}\leq\lambda<\sqrt{\frac{13}{6}},\lambda<\kappa\leq\kappa_{+}\right\\}$,
or $\left\\{\lambda\leq-\sqrt{\frac{13}{6}},\kappa<\lambda\right\\}$, or
$\left\\{-\sqrt{\frac{13}{6}}<\lambda<0,\kappa<\kappa_{-}\right\\}$, or
$\left\\{0<\lambda<\sqrt{\frac{13}{6}},\kappa>\kappa_{+}\right\\}$, or
$\left\\{\lambda\geq\sqrt{\frac{13}{6}},\kappa>\lambda\right\\}$. They can be
a saddle otherwise.

Finally, $A_{4}^{\pm}$ exists when $|\lambda|\leq\sqrt{2}$ with eigenvalues
$e_{1}\left(A_{4}^{\pm}\right)=\pm\sqrt{2}\left(\kappa-\lambda\right)$,
$e_{2}\left(A_{4}^{\pm}\right)=\mp\frac{\lambda-\sqrt{8-3\lambda^{2}}}{\sqrt{2}}$
and
$e_{3}\left(A_{4}^{\pm}\right)=\mp\frac{\lambda+\sqrt{8-3\lambda^{2}}}{\sqrt{2}}$
from which we conclude that in the expanding region the stationary points are
saddle points.

We conclude that there is an attractor in the expanding branch for the field
equations in the presence of positive spatial curvature dominated by
quintessence $A_{2}$, that is a sink when $\lambda^{2}<2$ and
$\lambda\left(2\kappa+\lambda\right)<6$. Moreover, the point $A_{3}^{\pm}$,
that exist when $2\kappa+\lambda\neq 0$ and $\lambda^{2}+2\kappa\lambda-6>0$
and correspond to inflationary power-law solutions can be attractors. We
continue by considering the negative curvature.

###  III.2 Open Universe

For an open FLRW universe and $K=-1$ the constraint (17) is

$x^{2}+y^{2}+z^{2}=2\eta^{2}-1.$ (24)

With the use of the constraint equation (24) the reduced dynamical system lies
on the three-dimensional surface. By definition $\eta^{2}\leq 1$.
Consequently, parameters $\left\\{x,y,z\right\\}$ are constrained , that is,
$\frac{1}{2}\leq\eta^{2}\leq 1$. To compare with the closed FLRW case, we
assume $y=\sqrt{2\eta^{2}-1-x^{2}-z^{2}}$. We remark that $y\rightarrow-y$ is
a discrete symmetry for the field equations. A positive value of $\eta$
denotes an expanding universe, i.e. $H>0$. Thus in the following we focus on
the expansion era that is we assume $\eta>0$.

Hence, the field equations are

$\displaystyle\frac{dx}{d\tau}$ $\displaystyle=-\sqrt{6}\eta^{2}\lambda+\eta
x\left(3x^{2}+3z^{2}-1\right)+\sqrt{\frac{3}{2}}\left(\lambda\left(x^{2}+1\right)+z^{2}(2\kappa+\lambda)\right)-2\eta^{3}x,$
(25) $\displaystyle\frac{dz}{d\tau}$
$\displaystyle=z\left(-2\eta^{3}+\eta\left(3x^{2}+3z^{2}-1\right)-\sqrt{6}\kappa
x\right),$ (26) $\displaystyle\frac{d\eta}{d\tau}$
$\displaystyle=\left(\eta^{2}-1\right)\left(-2\eta^{2}+3x^{2}+3z^{2}+1\right).$
(27)

Label | $x$ | $z$ | $\eta$ | $e_{1}(P)$ | $e_{2}(P)$ | $e_{3}(P)$
---|---|---|---|---|---|---
$B_{1}^{+}$ | $1$ | $0$ | $1$ | $4$ | $-\sqrt{6}\kappa$ | $6+\sqrt{6}\lambda$
$B_{1}^{-}$ | $-1$ | $0$ | $1$ | $4$ | $\sqrt{6}\kappa$ | $6-\sqrt{6}\lambda$
$\bar{B}_{1}^{+}$ | $1$ | $0$ | $-1$ | $-4$ | $-\sqrt{6}\kappa$ | $-\left(6-\sqrt{6}\lambda\right)$
$\bar{B}_{1}^{-}$ | $-1$ | $0$ | $-1$ | $-4$ | $\sqrt{6}\kappa$ | $-\left(6+\sqrt{6}\lambda\right)$
$B_{2}$ | $-\frac{\lambda}{\sqrt{6}}$ | $0$ | $1$ | $\frac{1}{2}\left(\lambda^{2}-6\right)$ | $\lambda^{2}-2$ | $\kappa\lambda+\frac{\lambda^{2}}{2}-3$
$\bar{B}_{2}$ | $\frac{\lambda}{\sqrt{6}}$ | $0$ | $-1$ | $-\frac{1}{2}\left(\lambda^{2}-6\right)$ | $-\left(\lambda^{2}-2\right)$ | $-\left(\kappa\lambda+\frac{\lambda^{2}}{2}-3\right)$
$B_{3}^{+}$ | $-\frac{\sqrt{6}}{2\kappa+\lambda}$ | $\frac{\sqrt{2\kappa\lambda+\lambda^{2}-6}}{\sqrt{(2\kappa+\lambda)^{2}}}$ | $1$ | $4-\frac{12\kappa}{2\kappa+\lambda}$ | $-\frac{3\kappa+i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$ | $-\frac{3\kappa-i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$
$B_{3}^{-}$ | $-\frac{\sqrt{6}}{2\kappa+\lambda}$ | $-\frac{\sqrt{2\kappa\lambda+\lambda^{2}-6}}{\sqrt{(2\kappa+\lambda)^{2}}}$ | $1$ | $4-\frac{12\kappa}{2\kappa+\lambda}$ | $-\frac{3\kappa+i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$ | $-\frac{3\kappa-i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$
$\bar{B}_{3}^{+}$ | $\frac{\sqrt{6}}{2\kappa+\lambda}$ | $\frac{\sqrt{2\kappa\lambda+\lambda^{2}-6}}{\sqrt{(2\kappa+\lambda)^{2}}}$ | $-1$ | $\frac{12\kappa}{2\kappa+\lambda}-4$ | $\frac{3\kappa+i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$ | $\frac{3\kappa-i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$
$\bar{B}_{3}^{-}$ | $\frac{\sqrt{6}}{2\kappa+\lambda}$ | $-\frac{\sqrt{2\kappa\lambda+\lambda^{2}-6}}{\sqrt{(2\kappa+\lambda)^{2}}}$ | $-1$ | $\frac{12\kappa}{2\kappa+\lambda}-4$ | $\frac{3\kappa+i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$ | $\frac{3\kappa-i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$
$B_{4}^{+}$ | $\frac{1}{\sqrt{3\lambda^{2}-3}}$ | $0$ | $-\sqrt{\frac{\lambda^{2}}{2(\lambda^{2}-1)}}$ | $\frac{\sqrt{2}(\lambda-\kappa)}{\sqrt{\lambda^{2}-1}}$ | $\frac{\lambda+\sqrt{8-3\lambda^{2}}}{\sqrt{2}\sqrt{\lambda^{2}-1}}$ | $\frac{\lambda-\sqrt{8-3\lambda^{2}}}{\sqrt{2}\sqrt{\lambda^{2}-1}}$
$B_{4}^{-}$ | $-\frac{1}{\sqrt{3\lambda^{2}-3}}$ | $0$ | $\sqrt{\frac{\lambda^{2}}{2(\lambda^{2}-1)}}$ | $-\frac{\sqrt{2}(\lambda-\kappa)}{\sqrt{\lambda^{2}-1}}$ | $-\frac{\lambda+\sqrt{8-3\lambda^{2}}}{\sqrt{2}\sqrt{\lambda^{2}-1}}$ | $-\frac{\lambda-\sqrt{8-3\lambda^{2}}}{\sqrt{2}\sqrt{\lambda^{2}-1}}$
$B_{5}$ | $0$ | $0$ | $\frac{1}{\sqrt{2}}$ | $-\sqrt{2}$ | $-\sqrt{2}$ | $\sqrt{2}$
$\bar{B}_{5}$ | $0$ | $0$ | $-\frac{1}{\sqrt{2}}$ | $\sqrt{2}$ | $\sqrt{2}$ | $-\sqrt{2}$

Table 2: The stationary points
$B=\left(x\left(B\right),z\left(B\right),\eta\left(B\right)\right)$ and
$\bar{B}=\left(x\left(\bar{B}\right),z\left(\bar{B}\right),\eta\left(\bar{B}\right)\right)$
of the dynamical system (25), (26), (27).

The stationary points
$B=\left(x\left(B\right),z\left(B\right),\eta\left(B\right)\right)$ and
$\bar{B}=\left(x\left(\bar{B}\right),z\left(\bar{B}\right),\eta\left(\bar{B}\right)\right)$
of the dynamical system (25), (26), (27) are presented in table 2. Since the
points $\bar{B}$ have the time-reversal dynamical behaviour of the related
points $B$ under the change $(\tau,x,\eta)\mapsto(-\tau,-x,-\eta)$.
$B_{1}^{+}$ maps onto $\bar{B}_{1}^{-}$, $B_{1}^{-}$ maps onto
$\bar{B}_{1}^{+}$, $B_{2}$ maps onto $\bar{B}_{2}$, $B_{3}^{+}$ maps onto
$\bar{B}_{3}^{-}$, $B_{3}^{-}$ maps onto $\bar{B}_{3}^{+}$, $B_{4}^{-}$ maps
onto $B_{4}^{+}$ (where we have suppressed the bar), $B_{5}$ maps onto
$\bar{B}_{5}$. Then, we focus on points $B$’s:

$\displaystyle B_{1}^{\pm}=\left(\pm
1,0,1\right),B_{2}=\left(-\frac{\lambda}{\sqrt{6}},0,1\right),$ $\displaystyle
B_{3}^{\pm}=\left(-\frac{\sqrt{6}}{2\kappa+\lambda},\pm\sqrt{\frac{\lambda^{2}+2\kappa\lambda-6}{\left(2\kappa+\lambda\right)^{2}}},1\right),$
$\displaystyle
B_{4}^{\pm}=\left(\pm\frac{1}{\sqrt{3\left(\lambda^{2}-1\right)}},0,\mp\sqrt{\frac{\lambda^{2}}{2(\lambda^{2}-1)}}\right),B_{5}=\left(0,0,\frac{1}{\sqrt{2}}\right).$

Stationary points $B_{1}^{\pm}$, $B_{2}$ and $B_{3}^{\pm}$ describe spatially
flat FLRW asymptotic solutions with physical properties similar with that of
points $A_{1}^{\pm},$ $A_{2}$ and $A_{3}^{\pm}$, respectively.

The eigenvalues of the linearised system around the stationary points
$B_{1}^{\pm}$ and $B_{2}$ are derived to be $e_{1}\left(B_{1}^{\pm}\right)=4$,
$e_{2}\left(B_{1}^{\pm}\right)=\mp\sqrt{6}\kappa$ ,
$e_{3}\left(B_{1}^{\pm}\right)=6\pm\sqrt{6}\lambda$ and
$e_{1}\left(B_{2}\right)=-3+\frac{\lambda^{2}}{2}$,
$e_{2}\left(B_{2}\right)=-2+\lambda^{2}$ ,
$e_{3}\left(B_{2}\right)=-3+\frac{1}{2}\lambda\left(2\kappa+\lambda\right)$.
Thus, points $B_{1}^{\pm}$ can be a source when
$\left\\{\pm\kappa<0,6\pm\sqrt{6}\lambda>0\right\\}$. $B_{2}$ is real only for
$\lambda^{2}<6$ and can be an attractor for $\lambda^{2}<2$ and
$\lambda\left(2\kappa+\lambda\right)<6$. Consequently this hyperbolic
inflationary solution is a future attractor.

As far as points $B_{3}^{\pm}$ are concerned, they exist when
$2\kappa+\lambda\neq 0$ and $\lambda^{2}+2\kappa\lambda-6>0$, and the
eigenvalues are $e_{1}(B_{3}^{\pm})=4-\frac{12\kappa}{2\kappa+\lambda}$,
$e_{2}(B_{3}^{\pm})=-\frac{3\kappa+i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$
and
$e_{3}(B_{3}^{\pm})=-\frac{3\kappa-i\sqrt{3\kappa\left[8\kappa^{2}\lambda+\kappa\left(8\lambda^{2}-27\right)+2\lambda\left(\lambda^{2}-6\right)\right]}}{2\kappa+\lambda}$.
Hence, when hyperbolic, $B_{3}^{\pm}$ can be sink for
$\left\\{-\sqrt{\frac{13}{6}}<\lambda\leq-\sqrt{2},\kappa_{-}\leq\kappa<\lambda\right\\}$,
or
$\left\\{-\sqrt{2}<\lambda<0,\kappa_{-}\leq\kappa<\frac{6-\lambda^{2}}{2\lambda}\right\\}$,
or
$\left\\{0<\lambda<\sqrt{2},\frac{6-\lambda^{2}}{2\lambda}<\kappa\leq\kappa_{+}\right\\}$,
or
$\left\\{\sqrt{2}\leq\lambda<\sqrt{\frac{13}{6}},\lambda<\kappa\leq\kappa_{+}\right\\}$,
or $\left\\{\lambda\leq-\sqrt{\frac{13}{6}},\kappa<\lambda\right\\}$, or
$\left\\{-\sqrt{\frac{13}{6}}<\lambda<0,\kappa<\kappa_{-}\right\\}$, or
$\left\\{0<\lambda<\sqrt{\frac{13}{6}},\kappa>\kappa_{+}\right\\}$, or
$\left\\{\lambda\geq\sqrt{\frac{13}{6}},\kappa>\lambda\right\\}$, where we
have defined
$\kappa_{\pm}=\frac{27-8\lambda^{2}}{16\lambda}\pm\frac{1}{16}\sqrt{3}\sqrt{-\frac{16\lambda^{2}-243}{\lambda^{2}}}$.
They can be a saddle otherwise. Therefore, these are also hyperbolic
inflationary solutions which can be a future attractor.

Points $B_{4}^{\pm}$ exist for $\lambda^{2}>2$ and describe Milne-like
solutions, $w_{eff}\left(B_{4}^{\pm}\right)=-\frac{1}{3}$ and
$q\left(B_{4}^{\pm}\right)=0$ with
$\eta\left(B_{4}^{\pm}\right)=\pm\sqrt{\frac{\lambda^{2}}{2\left(\lambda^{2}-1\right)}}$.
The eigenvalues are
$e_{1}\left(B_{4}^{\pm}\right)=\pm\sqrt{\frac{2}{\lambda^{2}-1}}\left(\lambda-\kappa\right)$,
$e_{2}\left(B_{4}^{\pm}\right)=\pm\frac{\lambda+\sqrt{\left(8-3\lambda^{2}\right)}}{\sqrt{2\left(\lambda^{2}-1\right)}}$
and
$e_{3}\left(B_{4}^{\pm}\right)=\pm\frac{\lambda-\sqrt{\left(8-3\lambda^{2}\right)}}{\sqrt{2\left(\lambda^{2}-1\right)}}$.
When hyperbolic, $B_{4}^{+}$ (respectively $B_{4}^{-}$) can be a sink
(respectively a source) for
$\left\\{-2\sqrt{\frac{2}{3}}<\lambda<-\sqrt{2},\kappa>\lambda\right\\}$, or
$\left\\{\lambda\leq-2\sqrt{\frac{2}{3}},\kappa>\lambda\right\\}$. $B_{4}^{+}$
(respectively $B_{4}^{-}$) can be a source (respectively a sink) for
$\left\\{\sqrt{2}<\lambda<2\sqrt{\frac{2}{3}},\kappa<\lambda\right\\}$, or
$\left\\{\lambda\geq 2\sqrt{\frac{2}{3}},\kappa<\lambda\right\\}$. They are
saddle otherwise.

Finally, $B_{5}$ is the vacuum solution with eigenvalues
$e_{1}\left(B_{5}\right)=-\sqrt{2}$, $e_{2}\left(B_{5}\right)=-\sqrt{2}$ and
$e_{3}\left(B_{5}\right)=\sqrt{2}$ that is always a saddle.

##  IV Hamiltonian analysis and analytic solution

We proceed our analysis with the construction of analytic solutions for the
field equations. Indeed, the field equations form a Hamiltonian system with
Hamiltonian function

$\displaystyle\mathcal{H}=-\frac{p_{a}^{2}}{12a^{2}}+\frac{1}{2a^{4}}\left(p_{\phi}^{2}+e^{-2\kappa\phi}p_{\psi}^{2}\right)+a^{2}V\left(\phi\right)-K,$
(28)
$\displaystyle\text{where}\;p_{a}=-6a^{2}a^{\prime}~{},~{}p_{\phi}=a^{4}\phi^{\prime}\text{
and }p_{\psi}=a^{4}e^{2\kappa\phi}\phi^{\prime},$ (29)

and $a^{\prime}=\frac{da}{d\xi}$ such that $d\xi=adt$.

For the exponential potential $V\left(\phi\right)=V_{0}e^{\lambda\phi}$ and
for the free parameters
$\left(\kappa,\lambda\right)=\left(-\frac{\sqrt{6}}{3},-\frac{\sqrt{6}}{3}\right)$,
the field equations admits the conservation law

$I_{0}=\left(\sqrt{6}p_{a}+ap_{\phi}\right)ae^{\frac{\sqrt{6}}{3}\phi}.$ (30)

Moreover, an additional conservation law is the

$I_{1}=a^{4}e^{2\frac{\sqrt{6}}{3}\phi}p_{\psi}.$ (31)

Consequently, the conservation laws $\left\\{\mathcal{H},I_{0},I_{1}\right\\}$
are independent and in involution, which means that the field equations form a
Liouville integrable dynamical system.

We follow the procedure presented earlier in sco01  and we consider the new
variables

$a=\left(\frac{8}{3}\left(xz-y^{2}\right)\right)^{\frac{1}{4}}~{},~{}\phi=\sqrt{\frac{3}{2}}\ln\left(\sqrt{\frac{2}{3}}\frac{\sqrt{xz-y^{2}}}{x}\right),~{}z=\frac{y}{x},$
(32)

such that the Hamiltonian function to become

$\mathcal{H}=\frac{1}{4}p_{y}-p_{x}p_{z}+V_{0}x-K$ (33)

and the conservation laws

$p_{x}=\Phi_{x}~{},~{}p_{y}=\Phi_{y}.$ (34)

Hence, the analytic solution of the field equations is

$x=x_{1}\xi+x_{0}~{},~{}y=y_{1}\xi+y_{0}~{},$ (35)

and

$z=\frac{\xi^{2}}{2}V_{0}+z_{1}\xi+z_{0}\text{~{}}.$ (36)

Finally, the constraint equation gives

$K=y_{1}^{2}-z_{1}x_{1}+x_{0}V_{0}.$ (37)

Thus for $y_{1}^{2}-z_{1}x_{1}+x_{0}V_{0}>0$ the exact solution is valid for a
closed universe while when $y_{1}^{2}-z_{1}x_{1}+x_{0}V_{0}<0$ the exact
solution describes an open universe, while the solution is real in the
original variables when $y_{1}^{2}-z_{1}x_{1}<0$. At this point it is
important to mention that the same solution is recovered under the change of
variable $\phi\rightarrow-\phi$ if initially we assume
$\left(\kappa,\lambda\right)=\left(\frac{\sqrt{6}}{3},\frac{\sqrt{6}}{3}\right)$.

Hence, the scale factor for large values of $\xi$, is determined
$a\left(\xi\right)\simeq\xi^{\frac{1}{2}},$that is, the Hubble function is
$H=\frac{1}{a^{2}}\frac{da}{d\xi}=\frac{1}{\xi^{\frac{3}{2}}}$, that is,
$\left(H\left(a\right)\right)^{2}=\frac{1}{4}a^{-6}$, and the deceleration
parameter is derived to be $q\left(\xi\right)=2$. That is nothing else than
the asymptotic solution described by points $A_{1}^{\pm}\,$ and $B_{1}^{\pm}$.
This means that the results derived from the analysis of the asymptotic are
confirmed by the analytical solution.

##  V Conclusions

In this study, we investigated the dynamics of hyperbolic inflation in the
presence of curvature in a homogeneous and isotropic universe. The question we
wanted to answer is if hyperbolic inflation solves the flatness problem.
Indeed, in an FLRW background space with nonzero curvature, we found as
stationary points the exact solutions which describe the hyperbolic inflation.
We focused on the expanding regime and in the case of a closed ($K=+1$)
universe, we found two types of attractors. Say, in the presence of positive
spatial curvature we have the solution dominated by quintessence $A_{2}$
(respectively $\bar{A}_{2}$) that is a sink (respectively a source) when
$\lambda^{2}<2$ and $\lambda\left(2\kappa+\lambda\right)<6$. Similar
conditions were found in the quintom context in Tot:2022dpr  (under the
parameter re-scaling $2\kappa\mapsto\kappa$, $A_{2}$ corresponds to
$\tilde{E}$, $\bar{A}_{2}$ corresponds to $\tilde{F}$). Moreover, the point
$A_{3}^{\pm}$, that exist when $2\kappa+\lambda\neq 0$ and
$\lambda^{2}+2\kappa\lambda-6>0$ and correspond to inflationary power law
solutions can be attractors. $A_{3}^{\pm}$ (respectively $\bar{A}_{3}^{\pm}$)
are related to the point $G$ (respectively $H$) studied in quintom context in
Tot:2022dpr .

On the other hand, in the case of an open ($K=-1$) universe, we find, as
before, a solution dominated by quintessence $B_{2}$ (respectively
$\bar{B}_{2}$), that is a sink (respectively a source) when $\lambda^{2}<2$
and $\lambda\left(2\kappa+\lambda\right)<6$, and the point $B_{3}^{\pm}$, that
exist when $2\kappa+\lambda\neq 0$ and $\lambda^{2}+2\kappa\lambda-6>0$ and
correspond to inflationary power law solutions which can be attractors.
Additionally we have the Milne-like (late- and early time-) attractor
solutions. Say, $B_{4}^{+}$ (respectively $B_{4}^{-}$) can be a sink
(respectively a source) for
$\left\\{-2\sqrt{\frac{2}{3}}<\lambda<-\sqrt{2},\kappa>\lambda\right\\}$, or
$\left\\{\lambda\leq-2\sqrt{\frac{2}{3}},\kappa>\lambda\right\\}$. $B_{4}^{+}$
(respectively $B_{4}^{-}$) can be a source (respectively a sink) for
$\left\\{\sqrt{2}<\lambda<2\sqrt{\frac{2}{3}},\kappa<\lambda\right\\}$, or
$\left\\{\lambda\geq 2\sqrt{\frac{2}{3}},\kappa<\lambda\right\\}$.

From the above analysis, it is clear that in a universe with initial
conditions of nonzero curvature, the hyperbolic inflationary solution exists.
We have proved that two hyperbolic inflationary stages are stable solutions
that can solve the flatness problem and describe acceleration for both open
and closed models, and additionally a Milne-like solution for the open model.
We also investigate the contracting branch obtaining mirror solutions with the
opposite dynamical behaviours. That result was also found to be valid with the
derivation of the analytic solution for the problem.

For a more general scalar field potential, it was found that this cosmological
model can be seen as a unified dark energy model ancqg  because it provides
various epochs of the cosmological evolution. We note that a similar result
will follow in the presence of curvature.

## Acknowledgments

This work is based on the research supported in part by the National Research
Foundation of South Africa (Grant Number 131604). Additionally, this research
is funded by Vicerrectoría de Investigación y Desarrollo Tecnológico at
Universidad Católica del Norte. The authors thank Dr. P. Christodoulidis for
various comments.

## References

  * (1) A. Guth, Phys. Rev. D 23, 347 (1981)
  * (2) A. Linde, Inflationary Cosmology, Lect. Notes Phys. 738, 1 (2008)
  * (3) L. Arturo Ureña-López, J. Phys. Conf. Ser. 761, 012076 (2016)
  * (4) P. Binetury and G. Dvali, Phys. Lett. B 388, 241 (1996)
  * (5) A. Linde, Phys. Rev. D 49, 748 (1994)
  * (6) A. Golovnev, V. Mukhanov and V. Vanchurin, JCAP 06, 009 (2008)
  * (7) V. Faraoni, Phys. Rev. D 53, 6813 (1996)
  * (8) S. Basilakos and J.D. Barrow, Phys. Rev. D 91, 103517 (2015)
  * (9) E.O. Kahya and B. Pourhassa, Astroph. Space Sci. 353, 677 (2014)
  * (10) O. Bertolami and V. Duvvuri, Phys. Lett. B 640, 121 (2006)
  * (11) J.D. Barrow and A. Paliathanasis, Phys. Rev. D 94, 083518 (2016)
  * (12) L. Sebastiani and R. Myrzakulov, IJGMMP 1530003 (2015)
  * (13) Q.-G. Hang, JCAP 02, 035 (2014)
  * (14) G.G.L. Nashed and W. El Hanafy, EPJC 74, 3099 (2014)
  * (15) A. Awad, W. El Hanafy, G.G.L. Nashed, S.D. Odintsov and V.K. Oikonomou, JCAP 07, 026 (2018)
  * (16) K. Bamba, G.G.L. Nashed, W. El Hanafy and Sh. K. Ibraheem, Phys. Rev. D 94, 083513 (2016)
  * (17) V.K. Oikonomou, Phys. Rev. D 95, 084023 (2017)
  * (18) A.R. Brown, Phys. Rev. Lett. 121, 251601 (2018)
  * (19) S.V. Chervon, Quantum Matter 2, 71 (2013)
  * (20) A. Paliathanasis, G. Leon and S. Pan, Gen. Rel. Gravit. 51, 106 (2019)
  * (21) A. Paliathanasis and M. Tsamparlis, Phys. Rev. D 90, 043529 (2014)
  * (22) A. Beesham, S.V. Chernov, S.D. Maharaj and A.S. Kubasov, Quantum Matter 2, 388 (2013)
  * (23) R.R. Abbyazov and S.V. Chernov, Grav. Cosmol. 18, 262 (2012)
  * (24) P. Christodoulidis, D. Roest and E.I. Sfakianakis, JCAP 12, 059 (2019)
  * (25) S. Mizuno and S. Mukohyama, Phys. Rev. D 96, 103533 (2017)
  * (26) T. Bjorkmo and M.C. David Marsh, JHEP 04, 172 (2019)
  * (27) P. Christodoulidis and A. Paliathanasis, JCAP 05, 038 (2021)
  * (28) A. Paliathanasis and G. Leon, Eur. Phys. J. Plus 137, 165 (2022)
  * (29) A. Paliathanasis, Universe 7, 323 (2021)
  * (30) C.-B. Chen and J. Soda, JCAP 09, 026 (2021)
  * (31) E.J. Copeland, A.R. Liddle and D. Wands, Phys. Rev. D 57, 4686 (1998)
  * (32) G. Leon and E.N. Saridakis, JCAP 04, 031 (2015)
  * (33) L. Amendola, D. Polarski and S. Tsujikawa, Phys. Rev. Lett. 98, 131302 (2007)
  * (34) B. Ratra, Phys. Rev. D 45, 1913 (1992)
  * (35) J. Tot, B. Yildirim, A. Coley and G. Leon, [arXiv:2204.06538 [gr-qc]].
  * (36) A. Paliathanasis, Class. Quantum Grav. 37, 19 (2020)


11institutetext: Université libre de Bruxelles (ULB), Brussels, Belgium
11email<EMAIL_ADDRESS>ETH Zurich, Zürich, Switzerland
22email<EMAIL_ADDRESS>
# Inapproximability of shortest paths on perfect matching polytopes††thanks:
The second author was supported by an ETH Postodctoral Fellowship.

Jean Cardinal 11 0000-0002-2312-0967 Raphael Steiner 22 0000-0002-4234-6136

###### Abstract

We consider the computational problem of finding short paths in the skeleton
of the perfect matching polytope of a bipartite graph. We prove that unless
$\P=\NP$, there is no polynomial-time algorithm that computes a path of
constant length between two vertices at distance two of the perfect matching
polytope of a bipartite graph. Conditioned on $\P\neq\NP$, this disproves a
conjecture by Ito, Kakimura, Kamiyama, Kobayashi and Okamoto [SIAM Journal on
Discrete Mathematics, 36(2), pp. 1102-1123 (2022)]. Assuming the Exponential
Time Hypothesis we prove the stronger result that there exists no polynomial-
time algorithm computing a path of length at most
$\left(\frac{1}{4}-o(1)\right)\frac{\log N}{\log\log N}$ between two vertices
at distance two of the perfect matching polytope of an $N$-vertex bipartite
graph. These results remain true if the bipartite graph is restricted to be of
maximum degree three.

The above has the following interesting implication for the performance of
pivot rules for the simplex algorithm on simply-structured combinatorial
polytopes: If $\P\neq\NP$, then for every simplex pivot rule executable in
polynomial time and every constant $k\in\mathbb{N}$ there exists a linear
program on a perfect matching polytope and a starting vertex of the polytope
such that the optimal solution can be reached in two monotone steps from the
starting vertex, yet the pivot rule will require at least $k$ steps to reach
the optimal solution. This result remains true in the more general setting of
pivot rules for so-called _circuit-augmentation algorithms_.

###### Keywords:

Polytopes Perfect matchings Linear programming Simplex method Pivot rules
Circuit-augmentation Inapproximability Combinatorial reconfiguration

##  1 Introduction

The history of linear programming is intimately intertwined with that of
Dantzig’s simplex algorithm. While the simplex and its many variants are among
the most studied algorithms ever, a number of fundamental questions remain
open. It is not known, for instance, whether there exists a pivot rule that
makes the simplex method run in strongly polynomial time. Since the
publication of the first examples of linear programs that make the original
simplex algorithm run in exponential time, many alternative pivot rules have
been proposed, fostering a tremendous amount of work in the past 75 years,
both from the combinatorial and complexity-theoretic point of views.

The simplex algorithm follows a monotone path on the skeleton of the polytope
defining the linear program. The following natural question was recently
raised by De Loera, Kafer, and Sanità [14]:

“Can one hope to find a pivot rule that makes the simplex method use a
shortest monotone path?”.

As an answer, they proved that given an initial solution to a linear program,
it is $\NP$-hard to find a 2-approximate shortest monotone path to an optimal
solution. It implies that unless $\P=\NP$, no polynomial-time pivot rule for
the simplex can be guaranteed to reach an optimal solution in a minimum number
of steps.

A similar result can also be deduced from two independent contributions, by
Aichholzer, Cardinal, Huynh, Knauer, Mütze, Steiner, and Vogtenhuber [2] on
one hand, and by Ito, Kakimura, Kamiyama, Kobayashi, and Okamoto [26] on the
other hand. They proved that the above result holds for perfect matching
polytopes of planar and bipartite graphs, albeit with a slightly weaker
inapproximability factor of $3/2$ instead of $2$. Ito et al. [26] conjecture
that there exists a constant-factor approximation algorithm for the problem of
finding a shortest path between two perfect matchings on the perfect matching
polytope.

Our main result is a disproof of this conjecture under the $\P\not=\NP$
assumption: Strengthening the previous inapproximability results mentioned
above, we show that unless $\P=\NP$ no $k$-approximation for a shortest path
between two vertices at distance $2$ of a bipartite perfect matching polytope
can be found in polynomial time, for any (arbitrarily large) choice of
$k\in\mathbb{N}$. We also give an even stronger inapproximability result under
the _Exponential Time Hypothesis_ (ETH). The latter states that the 3-SAT
problem cannot be solved in worst-case subexponential time, and is one of the
main computational assumptions of the fine-grained complexity program [38]. As
a consequence, there is not much hope of finding a pivot rule for the simplex
algorithm yielding good approximations of the shortest path towards an optimal
solution, even when the linear program is integer and its associated matrix
totally unimodular.

###  1.1 Our result

We consider the complexity of computing short paths on the 0/1 polytope
associated with perfect matchings of a bipartite graph. Given a balanced
bipartite graph $G=(V,E)$, where $V$ is partitioned into two equal-size
independent sets $A$ and $B$, we define the _perfect matching polytope_
$P_{G}\subseteq\mathbb{R}^{E}$ of $G$ as the convex hull of the 0/1 incidence
vectors of perfect matchings of $G$.

It is well-known (see e.g. Chapter 18 in [36]) that for _bipartite_ graphs
$G$, there is a nice halfspace representation of $P_{G}$. An edge-vector
$(x_{e})_{e\in E}\in\mathbb{R}^{E}$ is in $P_{G}$ if and only if the following
hold.

$\displaystyle\sum_{e\ni v}{x_{e}}$ $\displaystyle=1,\qquad(\forall v\in V)$
(1) $\displaystyle x_{e}$ $\displaystyle\geq 0,\qquad(\forall e\in E).$ (2)

The above is a compact encoding of $P_{G}$, with a number of constraints and
variables of size polynomial in $G$. The assumption that $G$ is bipartite is
crucial here: For non-bipartite $G$ the polytope defined by the above
constraints has non-integral vertices and is thus not a representation of
$P_{G}$ [36]. The matrix of this representation of a perfect matching polytope
of a bipartite graph $G$ is simply the vertex-edge-incidence matrix of $G$,
which is totally unimodular. The problem of maximizing a linear functional
$w^{T}x$ subject to constraints $(1)$ and $(2)$ corresponds exactly to the
problem of finding a perfect matching $M$ of $G$ whose weight $\sum_{e\in
M}{w_{e}}$ is maximal.

Given that the simplex algorithm moves along the edges of a polytope, it is
crucial for our considerations to understand adjacency of vertices on $P_{G}$.
The following result is well-known [12, 27].

###### Lemma 1

For a bipartite graph $G$, two vertices of $P_{G}$ corresponding to two
perfect matchings $M_{1}$ and $M_{2}$ are adjacent in the skeleton of $P_{G}$
if and only if the symmetric difference $M_{1}\Delta M_{2}$ is a cycle in $G$.

This cycle is said to be _alternating_ in both matchings, and one matching can
be obtained from the other by _flipping_ this alternating cycle. In general,
we will say that two perfect matchings are _at distance at most $k$_ from each
other on $P_{G}$, for some positive integer $k$, if one can be obtained from
the other by successively flipping at most $k$ alternating cycles.

Figure 1: Two perfect matchings at distance two on the perfect matching
polytope, but whose symmetric difference consists of an arbitrarily large
number of even cycles.

Note that given any two perfect matchings $M_{1}$ and $M_{2}$ of a bipartite
graph $G$, it is always the case that $M_{1}\Delta M_{2}$ is a collection of
vertex-disjoint even cycles that are alternating in both matchings. The number
of such cycles is therefore an upper bound on the distance between $M_{1}$ and
$M_{2}$ on $P_{G}$. Interestingly, this upper bound can be arbitrarily larger
than the actual distance. Figure 1 shows a construction of a graph $G$ with
two matchings at distance two on $P_{G}$, whose symmetric difference consists
of an arbitrary number of cycles.

Our main result is the following.

###### Theorem 1.1

Let $k\geq 2$ be any fixed integer. Unless $\P=\NP$, there does not exist any
polynomial-time algorithm solving the following problem:

Input: A bipartite graph $G$ of maximum degree $3$ and a pair of perfect
matchings $M_{1},M_{2}$ of $G$ at distance at most $2$ on the polytope
$P_{G}$.

Output: A path from $M_{1}$ to $M_{2}$ in the skeleton of $P_{G}$, of length
at most $k$.

More strongly, for every absolute constant $\delta>0$, unless the Exponential
Time Hypothesis fails, no polynomial-time algorithm can solve the above
problem when $k$ is allowed to grow with the number $N$ of vertices of $G$ as
$k(N)=\left\lfloor\left(\frac{1}{4}-\delta\right)\frac{\log N}{\log\log
N}\right\rfloor$.

A path on the perfect matching polytope of a bipartite graph $G$ is said to be
_monotone_ with respect to some weight vector $w=(w_{e})_{e\in
E}\in\mathbb{R}^{E}$ on the edges of $G$ if the perfect matchings along the
path have monotonically increasing total weights. Given two perfect matchings
$M_{1}$ and $M_{2}$ at distance two on the perfect matching polytope, one can
assign weights to edges so that (i) the path of length two between them is
strictly monotone, and (ii) $M_{2}$ is the unique matching of maximal weight
(this will be formally proven later in Lemma 4). This allows us to formulate
our result as one about the hardness of reaching an optimal solution from a
given feasible solution of a linear program on the perfect matching polytope.

###### Corollary 1

Unless $\P=\NP$, there does not exist any polynomial-time constant-factor
approximation algorithm for the following optimization problem:

Input: A bipartite graph $G=(V,E)$ of maximum degree $3$, a weight function
$E\to\mathbb{R}^{+}$, and a perfect matching $M$ of $G$.

Output: A shortest monotone path on $P_{G}$ from $M$ to a maximum-weight
perfect matching of $G$.

Furthermore, assuming ETH, for an arbitrary but fixed $\delta>0$ no
polynomial-time algorithm can achieve an approximation ratio of less than
$\left(\frac{1}{8}-\delta\right)\frac{\log N}{\log\log N}$, where $N:=|V(G)|$.

This corollary can be further interpreted as a statement on the existence of a
polynomial-time pivot rule that would make the simplex method use an
approximately shortest monotone path to a solution. Any such pivot rule could
be used as an approximation algorithm for the above problem, contradicting the
computational hypotheses.

###  1.2 Pivot rules for circuit-augmentation algorithms.

Our work on distances in the skeleton of $P_{G}$ for bipartite graphs $G$ was
originally motivated by questions regarding so-called _circuit moves (or
circuit augmentations)_ , that have been recently studied in linear
programming [10, 14, 32] as well as in the context of relaxations of the
Hirsch conjecture concerning the diameter of polytopes [9, 29]. A _circuit
move_ extends the simplex-paradigm of moving along an incident edge of the
constraint-polyhedron, by additionally allowing to move along certain non-edge
directions, called _circuits_. Given a linear program, the circuits in a well-
defined sense represent all possible edge-directions that could occur after
changing the right-hand side of the LP. The following is a formal definition.

######  Definition 1 (cf. Definition 1 in [14])

Given a polyhedron of the form

$\mathcal{P}=\\{\mathbf{x}\in\mathbb{R}^{n}|A\mathbf{x}=\mathbf{b},B\mathbf{x}\leq\mathbf{d}\\},$

a _circuit_ is a vector $\mathbf{g}\in\mathbb{R}^{n}\setminus\\{\mathbf{0}\\}$
such that

  1. 1.

$A\mathbf{g}=0$, and

  2. 2.

the support of $B\mathbf{g}$ is inclusion-wise minimal among the collection
$\\{B\mathbf{y}|A\mathbf{y}=\mathbf{0},y\neq\mathbf{0}\\}$.

Given an LP $\\{\max\mathbf{c}^{T}\mathbf{x}|\mathbf{x}\in\mathcal{P}\\}$ for
a polyhedron $\mathcal{P}$, a current feasible solution
$\mathbf{x}\in\mathcal{P}$ and a circuit $\mathbf{g}$ with
$\mathbf{c}^{T}\mathbf{g}>0$, a _circuit move_ then consists of moving to a
new feasible solution $\mathbf{x}^{\prime}=\mathbf{x}+t^{\ast}\mathbf{g}$,
where $t^{\ast}\geq 0$ is maximal w.r.t.
$\mathbf{x}+t^{\ast}\mathbf{g}\in\mathcal{P}$. Note that in general, an
optimization algorithm based on a pivot rule for circuit moves may traverse
several non-vertices of the polyhedron before reaching an optimal solution.

Our interest in the perfect matching polytope for understanding the complexity
of circuit-pivot algorithms came from the following observation.

###### Lemma 2

Let $G$ be a bipartite graph. Then

  1. 1.

A non-zero vector $\mathbf{g}\in\mathbb{R}^{E}$ is a circuit for $P_{G}$
(defined by the (in)equalities $(1)$ and $(2)$) if and only if there exists an
even cycle $C$ in $G$ decomposed into matchings $C^{+},C^{-}\subseteq C$
(alternately appearing along $C$) and $\alpha>0$ such that
$\mathbf{g}=\mathbf{g}(C,\alpha)$, where

$\mathbf{g}(C,\alpha)_{e}:=\begin{cases}\alpha,&\text{if }e\in
C^{+},\cr-\alpha,&\text{if }e\in C^{-},\cr 0,&\text{if }e\notin
C.\end{cases}.$

  2. 2.

If $x$ is a vertex of $P_{G}$, and $x^{\prime}\neq x$ is obtained from $x$ by
a circuit move, then $x^{\prime}$ is also a vertex of $P_{G}$ and adjacent to
$x$ on the skeleton of $P_{G}$.

This observation implies that any sequence of circuit moves, applied starting
from a vertex of $P_{G}$, will follow a monotone path on the skeleton of
$P_{G}$ from vertex to vertex. Consequently, Corollary 1 also yields an
inapproximability result for polynomial pivot rules for circuit augmentation,
as follows.

###### Corollary 2

Unless $\P=\NP$, there does not exist a polynomial-time constant-factor
approximation algorithm for the following problem.

Input: A bipartite graph $G$ of maximum degree $3$, a vertex $\mathbf{x}\in
P_{G}$ and a linear objective function.

Output: A shortest sequence of circuit moves on $P_{G}$ from $\mathbf{x}$ to
an optimal solution.

Furthermore, assuming ETH, no polynomial-time alorithm can achieve an
approximation ratio of less than $\left(\frac{1}{8}-\delta\right)\frac{\log
N}{\log\log N}$, where $N:=|V(G)|$ and $\delta>0$ is a constant.

###  1.3 Related works

Our work relates to two main threads of research in combinatorics and computer
science: one obviously related to the complexity of the simplex method and
linear programming in general, and another more recent one, aiming at building
a thorough understanding of the computational complexity of so-called
_combinatorial reconfiguration problems_.

#### Complexity of the simplex method.

In 1972, Klee and Minty showed that the original simplex method had an
exponential worst-case behavior on what came to be known as Klee-Minty cubes
[31]. Since then, many other variants have been shown to have exponential or
superpolynomial lower bounds [28, 7, 22, 4, 17], although subexponential rules
are known [24]. More dramatic complexity-theoretic results have been obtained
recently [1, 18]. In particular, it was shown by Fearney and Savani [19] that
Dantzig’s original simplex method can solve -complete problems: Given an
initial vertex, deciding whether some variable will ever be chosen by the
algorithm to enter the basis is -complete. The simplex method is also a key
motivation for studying the diameter of polytopes, in particular the Hirsch
conjecture, refuted in 2012 by Santos [35].

The hardness result on approximating monotone paths given by De Loera, Kafer,
and Sanità [14] is in fact a corollary of the -hardness of the following
problem: Given a feasible extreme point solution of the bipartite matching
polytope and an objective function, decide whether there is a neighbor extreme
point that is optimal. A related result for circulation polytopes was proved
by Barahona and Tardos [5]. These two results, as well as the hardness results
from Aichholzer et al. [2] and Ito et al. [26] rely on the -hardness of the
Hamiltonian cycle problem. In order to deal with the approximability of the
shortest path, we have to resort to more recent inapproximability results on
the longest cycle problem [6].

#### Reconfiguration of matchings.

The field of _combinatorial reconfiguration_ deals with the problems of
transforming a given discrete structure, typically a feasible solution of a
combinatorial optimization problem, into another one using elementary
combinatorial moves [25, 37, 34, 21]. The reachability problem, for instance,
asks whether there exists such a transformation, while the shortest
reconfiguration path problem asks for the minimum number of elementary moves.

A number of recent works in this vein deal with reconfiguration of matchings
in graphs [25, 30, 8, 11, 23]. Ito et al. [25] proved that the reachability
problem between matchings of size at least some input number $k$ and under
single edge addition or removal was solvable in polynomial time. This was
extended to an adjacency relation involving two edges by Kaminskí et al. [30].
The problem of finding the shortest reconfiguration path under this model was
shown to be -hard [11, 23]. Another line of work involves flip graphs on
perfect matchings in which the adjacency relation corresponds to flips of
alternating cycles of length exactly four [15, 16, 33, 8, 13]. Note that for
bipartite graphs, this flip graph is precisely the subgraph of the skeleton of
the perfect matching polytope that consists of edges of length two. Bonamy et
al. [8] proved that the reachability problem in these flip graphs is
-complete.

##  2 Proof of Theorem 1.1

###  2.1 Preliminaries

First note that perfect matchings of a balanced bipartite graph $G=(A\cup
B,E)$ can also be represented by orientations of $G$ in which every vertex in
$A$ has outdegree one and every vertex in $B$ has indegree one. The edges of
the matching are those oriented from $A$ to $B$. Alternating cycles in a
perfect matching are one-to-one with directed cycles in this orientation, and
flipping the cycle amounts to reverting the orientations of all its arcs. We
will switch from one representation to another when convenient.

We prove Theorem 1.1 by reducing from the problem of approximating the longest
directed cycle in a digraph. We rely on the following two results from
Björklund, Husfeldt, and Khanna given as Theorems 1 and 2 in [6].

######  Theorem 2.1 (Björklund, Husfeldt, Khanna [6])

Consider the problem of computing a long directed cycle in a given Hamiltonian
digraph $D$ on $n$ vertices.

  1. 1.

For every fixed $\varepsilon>0$, unless $\P=\NP$, there does not exist any
polynomial-time algorithm that returns a directed cycle of length at least
$n^{\varepsilon}$ in $D$.

  2. 2.

For every polynomial-time computable increasing function
$f:\mathbb{N}\to\mathbb{N}$ in $\omega(1)$, unless the Exponential Time
Hypothesis fails, there does not exist any polynomial-time algorithm that
returns a directed cycle of length at least $f(n)\log n$ in $D$.

Note that in the two problems, the input graph is guaranteed to be
Hamiltonian, yet it remains hard to explicitly _construct_ a directed cycle of
some guaranteed length. Characterising the approximability of the longest
cycle problem in undirected graphs is a longstanding open question [3, 20].

The second ingredient of our proof is the following lemma, perhaps of
independent interest, that bounds the increase in length of a longest directed
cycle after a number of cycle flips in a digraph.

###### Lemma 3

Let $G$ be an undirected graph, and let $C_{1},\ldots,C_{t}$ be a sequence of
(not necessarily distinct) cycles in $G$. Let $D_{0},D_{1},\ldots,D_{t}$ be a
sequence of orientations of $G$ such that for each $i\in[t]$ the cycle $C_{i}$
is directed in $D_{i-1}$ and such that $D_{i}$ is obtained from $D_{i-1}$ by
flipping $C_{i}$.

There exists a polynomial-time algorithm that, given as input a number $\ell$,
the orientations $D_{0},\ldots,D_{t}$ and a directed cycle $C$ in $D_{t}$ of
length $|C|>\ell^{t+1}$, computes a directed cycle in $D_{0}$ of length at
least $\ell$.

The bound of Lemma 3 can be shown to be essentially tight. We refer to Figure
2 for an illustration of the construction. The proof of Lemma 3 is deferred to
the end of this section.

Figure 2: A subcubic digraph in which the maximum length of a directed cycle
is 6, yet after flipping two cycles, we reach an orientation of the same graph
that has the outer face as a directed cycle, and thus contains a directed
cycle of length greater than $3\cdot 2\cdot 5$ (exactly $42$ in this example).
In general, by iterating the same construction, for every integer $k$ one can
construct a digraph with maximum directed cycle length $\ell=2k$ and such that
after flipping at most $t$ cycles, one can reach an orientation containing a
directed cycle of length at least $k\cdot(k-1)^{t-1}\cdot(2k-1)\simeq
2\cdot(\ell/2)^{t+1}$.

###  2.2 Reduction

Figure 3: Illustration of the reduction in the proof of Theorem 1.1. Every
vertex in the given Hamiltonian digraph $D$ (left) is replaced by the depicted
gadget (right), yielding a maximum degree-three bipartite graph with a perfect
matching.

We now give a proof of Theorem 1.1, assuming Lemma 3.

######  Proof (Theorem 1.1)

We consider the first problem in Theorem 2.1: For a fixed $\varepsilon>0$,
given a Hamiltonian digraph $D$ on $n$ vertices, return a directed cycle of
length at least $n^{\varepsilon}$. We first construct a digraph $D^{\prime}$
from $D$ by replacing every vertex $v$ of $D$ by the gadget illustrated on
Figure 3. The gadgets are obtained by applying the following transformations
to every vertex $v$ of $D$:

  1. 1.

The set of incoming arcs of $v$ is decomposed into a balanced binary tree with
$\text{deg}_{D}^{-}(v)$ leaves and a degree-one root identified to $v$. Each
internal node of this binary tree is further split into an arc. All arcs of
the tree are oriented towards the root.

  2. 2.

The set of outgoing arcs are split into a tree with $\text{deg}_{D}^{+}(v)$
leaves in a similar fashion, with all arcs oriented away from the root.

  3. 3.

Finally, the vertex $v$ itself is replaced by a directed 4-cycle, such that
the single incoming arc from the first tree and the single outgoing arc from
the second tree have adjacent endpoints on the cycle.

Figure 4: Flipping the 4-cycles of each gadget in $D^{\prime}$ can be done
with two successive cycle flips, using the Hamiltonian cycle of $D$.

The digraph $D^{\prime}$ thus obtained is bipartite and subcubic. Furthermore,
it is easy to see by construction that for every vertex $v\in V(D)$, the
corresponding gadget in $D^{\prime}$ has at most

$4\text{deg}_{D}^{-}(v)+4+4\text{deg}_{D}^{+}(v)\leq 8(n-1)+4<8n$

vertices, such that $N:=|V(D^{\prime})|<n\cdot 8n=8n^{2}$, and $D^{\prime}$ is
of polynomial size.

Furthermore, the orientation of $D^{\prime}$ is such that every vertex in one
side of the bipartition has outdegree one, and every vertex in the other has
indegree one, hence it corresponds to a perfect matching $M_{1}$. By flipping
the alternating 4-cycle in each gadget, we obtain another perfect matching
$M_{2}$. We observe that $M_{2}$ can be obtained from $M_{1}$ in two cycle
flips, by using the Hamiltonian cycle of $D$ twice (see Figure 4). Hence,
while $M_{1}\Delta M_{2}$ consists of $n$ disjoint 4-cycles, $M_{2}$ is in
fact at distance two from $M_{1}$ on the perfect matching polytope of
$D^{\prime}$. The underlying undirected graph of $D^{\prime}$ together with
the two perfect matchings $M_{1}$ and $M_{2}$ therefore constitute an instance
of the problem described in Theorem 1.1. We now show that any sequence of
length at most $k$ of alternating cycle flips transforming $M_{1}$ into
$M_{2}$ can be turned in polynomial time into a cycle of length at least
$n^{\varepsilon}$ in $D$, for some $\varepsilon>0$ depending solely on $k$.

Consider a sequence of $k$ cycles
$C^{\prime}_{1},C^{\prime}_{2},\ldots,C^{\prime}_{k}$ such that
$C^{\prime}_{1}$ is alternating in $D^{\prime}$, and $C^{\prime}_{i}$ is
alternating in the graph obtained from $D^{\prime}$ after flipping the cycles
$C^{\prime}_{1},C^{\prime}_{2},\ldots,C^{\prime}_{i-1}$, in this order, and
such that flipping all $k$ cycles in sequence transforms $M_{1}$ into $M_{2}$.
Observe that the sum of the lengths of the cycles in this sequence must be at
least $n$, since all the orientations of the $4$-cycles in the $n$ different
gadgets in $D^{\prime}$ have to be flipped, and since every single cycle
$C_{i}^{\prime}$ can intersect at most $|C_{i}^{\prime}|$ different
gadget-$4$-cycles. Let $\ell=\lceil n^{1/(k+2)}\rceil$. We have

$\sum_{i=1}^{k}|C^{\prime}_{i}|\geq
n=(1-o(1))\ell^{k+2}>\sum_{i=1}^{k}\ell^{i+1},$

hence from the pigeonhole principle, at least one cycle $C^{\prime}_{i}$ in
the sequence has length $|C^{\prime}_{i}|>\ell^{i+1}$. From Lemma 3, we can
now compute in polynomial time a directed cycle in $D^{\prime}$ of length at
least $n^{\varepsilon^{\prime}}$ for $\varepsilon^{\prime}=1/(k+2)$. Let us
call this cycle $C^{\prime}$. Note that for every gadget in $D^{\prime}$
corresponding to a vertex $v$ of $D$, either $C^{\prime}$ is vertex-disjoint
from this gadget, or it traverses it via exactly one directed path, consisting
of a leaf-to-root path in the in-tree, a directed path of length $7$ touching
the $4$-cycle of the gadget, and then a root-to-leaf path in the out-tree.
From this it follows that by contracting the edges of the gadgets, the cycle
$C^{\prime}$ in $D^{\prime}$ can be mapped to a cycle $C$ in $D$. Note that
the in- and out-degree of a vertex in $D$ is at most $n-1$, thus all the in-
and out-trees in $D^{\prime}$ corresponding to the gadgets have depth at most
$2\lceil\log_{2}n\rceil$. Consequently, the length of $C^{\prime}$ can be
shrinked by at most a factor of $4\lceil\log_{2}n\rceil+7$ by contracting the
gadgets. In other words, we obtain a directed cycle $C$ in $D$ of length at
least $n^{\varepsilon^{\prime}}/(4\lceil\log_{2}n\rceil+7)=n^{\varepsilon}$,
for $\varepsilon=\varepsilon^{\prime}-o(1)$. Hence if we can obtain in
polynomial time a sequence of at most $k=O(1)$ flips transforming $M_{1}$ into
$M_{2}$, we can also find a cycle of length at least $n^{\varepsilon}$ in $D$
for some fixed $\varepsilon>0$. This establishes the first statement of
Theorem 1.1.

It remains to prove the second statement. We consider the second problem in
Theorem 2.1, in which we seek a path of length at least $f(n)\log n$, for some
computable function $f(n)=\omega(1)$. Suppose that for some $\delta>0$ there
is a polynomial-time algorithm that can find a sequence of at most
$k=k(N)=\left\lfloor\left(\frac{1}{4}-\delta\right)\frac{\log N}{\log\log
N}\right\rfloor$ flips transforming $M_{1}$ into $M_{2}$. Note that

$k+2\leq\left(\frac{1}{4}-\delta\right)\frac{\log 8n^{2}}{\log\log
8n^{2}}+2<\frac{1}{2}(1-\delta)\frac{\log n}{\log\log n}$

for $n$ large enough (larger than some constant depending only on $\delta$).

Now, from the same reasoning as above, we can turn such an algorithm into a
polynomial-time algorithm that finds a directed cycle in $D$ of length at
least

$\frac{n^{1/(k+2)}}{4\lceil\log_{2}n\rceil+7}>\frac{n^{2\cdot\log\log
n/((1-\delta)\log n)}}{O(\log n)}=\Omega\left(\frac{\log^{2/(1-\delta)}n}{\log
n}\right)=f(n)\log n,$

for a computable function $f(n)=\Omega(\log^{2\delta/(1-\delta)}n)=\omega(1)$.
This, from Theorem 2.1, is impossible unless the Exponential Time Hypothesis
fails. ∎

In order to deduce Corollary 1 from Theorem 1.1, we need the following lemma.

###### Lemma 4

Given a bipartite graph $G=(V,E)$, let $M_{1}$ and $M_{2}$ be two perfect
matchings in $G$ at distance two on the perfect matching polytope, hence such
that $M_{2}=(M_{1}\Delta C_{1})\Delta C_{2}$ for some pair $C_{1},C_{2}$ of
cycles in $G$, and such that $M_{1}\Delta C_{1}=:M^{\prime}$ is also a perfect
matching. Then there exists a weight function $w:E\to\mathbb{R}^{+}$ such that

  1. 1.

$M_{2}$ is the unique maximum-weight perfect matching of $G$,

  2. 2.

$w(M_{1})<w(M^{\prime})<w(M_{2})$ (where $w(M)=\sum_{e\in M}w(e)$).

In other words, there exists a linear program over the perfect matching
polytope of $G$ such that the path $M_{1},M_{1}\Delta
C_{1}=M^{\prime}=M_{2}\Delta C_{2},M_{2}$ is a strictly monotone path and
$M_{2}$ is the unique optimum.

###### Proof

We first claim that $M_{1}\setminus(M_{2}\cup M^{\prime})\neq\emptyset$.
Indeed, the set of edges $M_{2}\cup M^{\prime}$ forms a subgraph of $G$ whose
components are the edges in $M_{2}\setminus C_{2}=M^{\prime}\setminus C_{2}$
and the cycle $C_{2}$. From this it is easy to see that if we were to have
that $M_{1}\subseteq M_{2}\cup M^{\prime}$, then necessarily
$M_{1}\in\\{M_{2},M^{\prime}\\}$, a contradiction to the fact that $M_{1}$ and
$M_{2}$ have distance exactly two. Now pick an edge $e_{0}\in
M_{1}\setminus(M_{2}\cup M^{\prime})$. Define a weighting
$w:E\rightarrow\mathbb{R}$ of the edges in $G$ as follows: $w(e_{0}):=0$,
$w(e):=1$ for every $e\in E\setminus(\\{e_{0}\\}\cup M_{2})$ and
$w(e):=1+\frac{1}{n}$ for every $e\in M_{2}$, where $n$ denotes the number of
vertices of $G$. It is now easily verified that $M_{2}$ is the unique maximum-
weight perfect matching in $G$, and that $w(M_{1})\leq
0+(\frac{n}{2}-1)(1+\frac{1}{n})<\frac{n}{2}\leq w(M^{\prime})<w(M_{2})$. This
proves the claim. ∎

###  2.3 Proof of Lemma 3

######  Proof (Lemma 3)

Let the orientations $D_{0},D_{1},\ldots,D_{t}$ of $G$ be given as input,
together with a directed cycle $C$ in $D_{t}$ and a number $\ell\in\mathbb{N}$
such that $|C|>\ell^{t+1}$.

Our algorithm starts by computing the sequence of cycles $C_{1},\ldots,C_{t}$
by determining for each $i\in[t]$ the set of edges with different orientation
in $D_{i-1}$ and $D_{i}$. Next we compute in polynomial time the subgraph $H$
of $G$ which is the union of the cycles $C_{1},\ldots,C_{t}$ in $G$. We in
particular compute a list of the vertex sets of its connected components,
which we call $Z_{1},\ldots,Z_{c}$ for some number $c\geq 1$.

For later use, let us prove the following fact:

Claim ($\ast$). For each $r\in[c]$ the induced subdigraph $D_{0}[Z_{r}]$ of
$D_{0}$ is strongly connected.

######  Proof (Claim ($\ast$))

For each $i\in[t]$, let us denote by $H_{i}$ the subgraph of $G$ consisting of
the vertices and edges on the cycles $C_{t-i+1},\ldots,C_{t}$. Then we have
$H_{t}=H$. We will establish the claim by proving inductively that for every
$i=1,2,\ldots,t$, every connected component of $H_{i}$ induces a strongly
connected subdigraph of $D_{t-i}$.

In the case $i=1$, this holds easily: The only connected component of $H_{1}$
is the cycle $C_{t}$, and since it forms a directed cycle both in $D_{t-1}$
and $D_{t}$, its vertices induce a strongly connected subdigraph of $D_{t-1}$,
as desired.

For the inductive step suppose we have established for some $1\leq i<t$ that
all components of $H_{i}$ induces strongly connected subgraphs of $D_{t-i}$.

Note that when we move from $H_{i}$ to $H_{i+1}$, the only change that happens
is the addition of the vertices and edges on the cycle $C_{t-i}$. If $C_{t-i}$
is vertex-disjoint from $H_{i}$, then it simply forms a new component in
$H_{i+1}$ and since it is a directed cycle in $D_{t-(i+1)}$, it induces a
strongly connected subdigraph thereof, while also all other components still
induce strongly connected subdigraphs, as their orientations are not affected
when flipping $C_{t-i}$.

Otherwise, $C_{t-i}$ together with all components of $H_{i}$ intersected by it
creates a new component $Z$ of $H_{i+1}$. Since each component intersected by
$C_{t-i}$ induces a strongly connected subdigraph of $D_{t-i}$ by our
assumption, and since $C_{t-i}$ is directed in $D_{t-i}$, it is easy to see
that also the new component $X$ induces a strongly connected subdigraph of
$D_{t-i}$. The only change when moving from $D_{t-i}$ to $D_{t-(i+1)}$ is that
the orientations of the arcs of $C_{t-i}$ are reverted. However, it is easily
seen that this operation preserves the fact that $X$ induces a strongly
connected subdigraph, since flipping $C$ maintains the pairwise reachability
of vertices on $C$ in the subdigraph induced by $X$.

All components of $H_{i}$ not intersected by $C_{t-i}$ remain components also
in $H_{i+1}$ and have the same orientations in $D_{t-(i+1)}$ as in $D_{t-i}$.
Hence, also they induce strongly connected subdigraphs of $D_{t-(i+1)}$, as
desired. This concludes the proof by the principle of induction. ∎

Let $(x_{0},x_{1},\ldots,x_{k-1},x_{k}=x_{0})$ be the cyclic list of vertices
on the directed cycle $C$ in $D_{t}$, with edges oriented from $x_{i}$ to
$x_{i+1}$ for all $i\in[k-1]$. By assumption on the input, we have
$k=|C|>\ell^{t+1}$.

We first check if $C$ is vertex-disjoint from $H$, in which case we may return
$C$, which is then also a directed cycle in $D_{0}$ of length
$k>\ell^{t+1}\geq\ell$, as desired.

Otherwise, $C$ intersects some of the components of $H$. We then for each
vertex $x_{i}\in V(C)$ compute a label $\text{lab}(x_{i})\in[c+1]$, defined as
$\text{lab}(x_{i}):=r$ if $x_{i}\in Z_{r}$ lies in the $r$-th component of
$H$, and $\text{lab}(x_{i}):=c+1$ if $x_{i}$ is not a vertex of $H$. We next
compute an auxiliary weighted directed multigraph $M$ on the vertex set $[c]$
as follows: For every maximal subsequence of $C$, of length at least two, of
the form $x_{i},x_{i+1},\ldots,x_{j}$ (addition to be understood modulo $k$)
such that $\text{lab}(x_{s})=c+1$ for all $s=i+1,\ldots,j-1$ (if any), we add
an additional arc from $\text{lab}(x_{i})$ to $\text{lab}(x_{j})$ and give it
weight $j-i$, the corresponding number of arcs in $C$. Note that the total arc
weight in $M$ is exactly $|C|$, while the total number of arcs is exactly
$|V(C)\cap V(H)|\leq|V(H)|$. The construction of $M$ is illustrated in Figure
5.

Figure 5: Construction of the auxiliary directed multigraph $M$ in the proof
of Lemma 3. The cycle $C$ is shown on the left, together with the connected
components of $H$ that it intersects. The resulting weighted directed
multigraph $M$ is shown on the right.

Furthermore, by definition every vertex in $M$ has the same number of incoming
and outgoing arcs. Hence, we may compute in polynomial time an edge-disjoint
decomposition of $M$ into directed cycles (including possible loops) in $M$.
Let $W_{1},\ldots,W_{p}$ for some $p\in\mathbb{N}$ be the list of edge-
disjoint directed cycles in this decomposition of $M$. We now create, for each
$W_{i}$, a directed cycle $K_{i}$ in $D_{0}$ of length
$|K_{i}|\geq\text{weight}(W_{i})$, where $\text{weight}(W_{i})$ is the total
arc weight of $W_{i}$, as follows:

Let $(l_{0},l_{1},\ldots,l_{s}=l_{0})$ be the cyclic vertex-sequence of
$W_{i}$.

For each arc $(l_{j},l_{j+1})$ in $W_{i}$, we consider the corresponding
subsequence $P(l_{j},l_{j+1})$ of $C$ which starts in $Z_{l_{j}}$, ends in
$Z_{l_{j+1}}$, and all whose internal vertices are not contained in $H$. We
note that since arcs outside $H$ have the same orientation in $D_{0}$ and
$D_{t}$, the subsequence $P(l_{j},l_{j+1})$ is a directed path or a directed
cycle also in $D_{0}$ which starts in $Z_{l_{j}}$ and ends in $Z_{l_{j+1}}$.

We first check whether there exists an index $j$ such that $P(l_{j},l_{j+1})$
is a directed cycle. In this case, necessarily $W_{i}$ is a loop (i.e. $s=0$)
and $l_{j}=l_{j+1}=l_{0}$. We thus may simply put $K_{i}:=P(l_{j},l_{j+1})$,
with $\text{weight}(W_{i})=|K_{i}|$ satisfied by definition of the weights in
$M$.

Otherwise, each of the $P(l_{j},l_{j+1})$ is a directed path in $D_{0}$. We
now make use of Claim $(\ast)$, which tells us that $D_{0}[Z_{l_{j}}]$ is
strongly connected for every $j=0,1,\ldots,s-1$. We may therefore compute in
polynomial time for each $j=0,1,\ldots,s-1$ a directed path $Q_{j}$ in
$D_{0}[Z_{l_{j}}]$ (possibly consisting of a single vertex) which connects the
endpoint of $P(l_{j-1},l_{j})$ to the starting point of $P(l_{j},l_{j+1})$
(index-addition modulo $s$). Crucially, note that any two directed paths in
the collection $\\{P(l_{j},l_{j+1}),Q_{j}|j=0,1,\ldots,s-1\\}$ are vertex-
disjoint except for shared common endpoints. We now compute the directed cycle
$K_{i}$ in $D_{0}$, which is the union of the directed paths
$P(l_{j},l_{j+1})$ and the directed paths $Q_{j}$ for $j=0,\ldots,s-1$. It is
clear that its length $|K_{i}|$ is lower-bounded by the sum of the lengths of
the $P(l_{j},l_{j+1})$, which by definition of $M$ equals the sum of arc-
weights on $W_{i}$, i.e., we indeed have $|K_{i}|\geq\text{weight}(W_{i})$
also in this case.

After having computed the directed cycles $K_{1},\ldots,K_{p}$ in $D_{0}$, the
algorithm checks whether one of the cycles has length $|K_{i}|\geq\ell$. If
so, it returns the cycle $K_{i}$ and the algorithm stops with the desired
output. Otherwise, we have $|K_{i}|<\ell$ for $i=1,\ldots,p$, which implies
that

$\ell^{t+1}<|C|=\text{weight}(M)=\sum_{i=1}^{p}{\text{weight}(W_{i})}\leq\sum_{i=1}^{p}{|K_{i}|}\leq
p(\ell-1).$

Note that $p$ is at most as large as the number of arcs in $M$, which in turn
is bounded by $|V(H)|$. We thus obtain

$\ell^{t+1}<|V(H)|\cdot(\ell-1)\leq\sum_{i=1}^{t}|C_{i}|\cdot(\ell-1).$

This yields that

$\sum_{i=1}^{t}{|C_{i}|}>\frac{\ell^{t+1}}{\ell-1}>\sum_{i=1}^{t}{\ell^{i}}.$

Therefore there exists $i\in\\{1,\ldots,t\\}$ such that $|C_{i}|>\ell^{i}$.
The algorithm proceeds by finding one cycle $C_{i}$ with this property. Note
that $C_{i}$ is a directed cycle in the orientation $D_{i-1}$ of $G$. Hence a
recursive call of the algorithm to the input $D_{0},D_{1},\ldots,D_{i-1}$ and
the cycle $C_{i}$ will yield a directed cycle of length at least $\ell$ in
$D_{0}$, as desired.

This proves the correctness of the described algorithm. As all the steps
between two recursive calls are executable in polynomial time in the size of
$G$ and $t$, and since there will clearly be at most $t-1$ recursive calls in
any execution of the algorithm, the whole algorithm runs in polynomial time,
as desired. ∎

###  2.4 Proof of Lemma 2

######  Proof (Lemma 2)

  1. 1.

We start by noting that the hyperplane restrictions $(1)$ and $(2)$ for the
perfect matching polytope $P_{G}$ can be expressed as
$P_{G}=\\{\mathbf{x}\in\mathbb{R}^{E}|A\mathbf{x}=\mathbf{b},B\mathbf{x}\leq\mathbf{d}\\}$,
where $A\in\mathbb{R}^{V\times E}$ is the vertex-edge incidence matrix of $G$,
$\mathbf{b}=\mathbf{1}$, $B=-I_{E}$ and $\mathbf{d}=\mathbf{0}$. Applying
Definition 1, this means that a vector
$\mathbf{g}\in\mathbb{R}^{E}\setminus\\{\mathbf{0}\\}$ is a circuit for
$P_{G}$ if and only if it is a support-minimal member of the set

$\mathcal{Y}=\left\\{\mathbf{y}\in\mathbb{R}^{E}\setminus\\{\mathbf{0}\\}\bigg{|}\sum_{e\ni
v}{y_{e}}=0\text{ for every }v\in V\right\\}.$

Now consider a circuit $\mathbf{g}\in\mathcal{Y}$ and let $H$ be the subgraph
of $G$ spanned by those $e\in E$ for which $\mathbf{g}_{e}\neq 0$. The
defining equations of $\mathcal{Y}$ immediately imply that $H$ has minimum
degree at least $2$. Thus $H$ contains a cycle $C$, which is necessarily even.
It is easy to check that the vectors $\mathbf{g}(C,\alpha),\alpha>0$ described
in the lemma form members of $\mathcal{Y}$. The support-minimality of
$\mathbf{g}$ thus implies that $\mathbf{g}$ is non-zero only on $C$. It now
easily follows that $\mathbf{g}=\mathbf{g}(C,\alpha)$ for some $\alpha>0$.
This concludes the proof of the first item.

  2. 2.

Let $\mathbf{x}$ be a vertex of $P_{G}$ and $M$ the corresponding perfect
matching of $G$. Let $\mathbf{x}^{\prime}\in P_{G}$ be a vector reachable via
a circuit-move from $\mathbf{x}$. This means that there is an even cycle $C$
in $G$ decomposed into two matchings $C^{+}$ and $C^{-}$, some $\alpha>0$ and
$t^{\ast}>0$ such that
$\mathbf{x}^{\prime}=\mathbf{x}+t^{\ast}\mathbf{g}(C,\alpha)$. The feasibility
of $\mathbf{x}^{\prime}$ implies that $\mathbf{x}_{e}<1$ for every $e\in
C^{+}$ and $\mathbf{x}_{e}>0$ for every $e\in C^{-}$, for otherwise an entry
of $\mathbf{x}^{\prime}$ would be strictly bigger than one or negative.
However, since $\mathbf{x}$ is the incidence vector of $M$, this implies that
$C^{+}=C\setminus M$ and $C^{-}=C\cap M$. Thus $C$ is an alternating cycle for
$M$, and $M^{\prime}:=M\Delta C$ is another perfect matching of $M$. By Lemma
1 $\mathbf{1}_{M^{\prime}}$ is adjacent to $\mathbf{x}=\mathbf{1}_{M}$ on the
skeleton of $P_{G}$. We now show that
$\mathbf{x}^{\prime}:=\mathbf{1}_{M^{\prime}}$, which will conclude the proof
of the claim. To see this, note that by definition of a circuit-move,
$t^{\ast}\geq 0$ was chosen maximal such that
$\mathbf{x}+t^{\ast}\mathbf{g}(C,\alpha)\in P_{G}$. Since moving in the
direction of the circuit $\mathbf{g}(C,\alpha)$ preserves all equality-
constraints $(1)$ in the hyperplane description of $P_{G}$, the maximality
implies that moving $t$ above $t^{\ast}$ would violate one of the inequality-
constraints $(2)$. Thus, there has to exist $e\in C$ such that
$\mathbf{x}^{\prime}_{e}=0$. On the other hand, we know that

$0=\mathbf{x}^{\prime}_{e}=\underbrace{\mathbf{x}_{e}}_{\in\\{0,1\\}}\pm\underbrace{t^{\ast}\alpha}_{>0},$

which implies that $t^{\ast}\alpha=1$. It follows that
$\mathbf{x}^{\prime}=\mathbf{x}+t^{\ast}\mathbf{g}(C,\alpha)=\mathbf{1}_{M^{\prime}}$,
as desired.

∎

## Acknowledgements

This work was initiated during a stay of the first author as a guest professor
at ETH Zurich in May-July 2022. He wishes to thank Prof. Emo Welzl for his
hospitality during this stay.

## References

  * [1] Ilan Adler, Christos H. Papadimitriou, and Aviad Rubinstein.  On simplex pivoting rules and complexity theory.  In Jon Lee and Jens Vygen, editors, Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings, volume 8494 of Lecture Notes in Computer Science, pages 13–24. Springer, 2014.
  * [2] Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber.  Flip distances between graph orientations.  Algorithmica, 83(1):116–143, 2021.
  * [3] Noga Alon, Raphael Yuster, and Uri Zwick.  Color-coding.  J. ACM, 42(4):844–856, 1995.
  * [4] David Avis and Oliver Friedmann.  An exponential lower bound for Cunningham’s rule.  Math. Program., 161(1-2):271–305, 2017.
  * [5] Francisco Barahona and Éva Tardos.  Note on Weintraub’s minimum-cost circulation algorithm.  SIAM J. Comput., 18(3):579–583, 1989.
  * [6] Andreas Björklund, Thore Husfeldt, and Sanjeev Khanna.  Approximating longest directed paths and cycles.  In Josep Díaz, Juhani Karhumäki, Arto Lepistö, and Donald Sannella, editors, Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings, volume 3142 of Lecture Notes in Computer Science, pages 222–233. Springer, 2004.
  * [7] Robert G. Bland.  New finite pivoting rules for the simplex method.  Math. Oper. Res., 2(2):103–107, 1977.
  * [8] Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa.  The perfect matching reconfiguration problem.  In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 80:1–80:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [9] Steffen Borgwardt, Elisabeth Finhold, and Charles Viss.  On the circuit diameter of dual transportation polyhedra.  SIAM J. Discrete Math., 29(1):113–121, 2015.
  * [10] Steffen Borgwardt and Charles Viss.  A polyhedral model for enumeration and optimization over the set of circuits.  Discret. Appl. Math., 308:68–83, 2022.
  * [11] Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, and Moritz Mühlenthaler.  Shortest reconfiguration of matchings.  In Ignasi Sau and Dimitrios M. Thilikos, editors, Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers, volume 11789 of Lecture Notes in Computer Science, pages 162–174. Springer, 2019.
  * [12] Vasek Chvátal.  On certain polytopes associated with graphs.  J. Comb. Theory, Ser. B, 18(2):138–154, 1975.
  * [13] Sebastian M. Cioabă, Gordon Royle, and Zhao Kuang Tan.  On the flip graphs on perfect matchings of complete graphs and signed reversal graphs.  Australas. J. Comb., 81:480–497, 2021.
  * [14] Jesús A. De Loera, Sean Kafer, and Laura Sanità.  Pivot rules for circuit-augmentation algorithms in linear optimization.  SIAM J. Optim., 32(3):2156–2179, 2022.
  * [15] Persi W. Diaconis and Susan P. Holmes.  Matchings and phylogenetic trees.  Proc. Natl. Acad. Sci. U.S.A., 95(25):14600–14602, 1998.
  * [16] Persi W. Diaconis and Susan P. Holmes.  Random walks on trees and matchings.  Electron. J. Probab., 7(6):1–17, 2002.
  * [17] Yann Disser, Oliver Friedmann, and Alexander V. Hopp.  An exponential lower bound for Zadeh’s pivot rule.  CoRR, abs/1911.01074, 2019.
  * [18] Yann Disser and Martin Skutella.  The simplex algorithm is NP-mighty.  ACM Trans. Algorithms, 15(1):5:1–5:19, 2019.
  * [19] John Fearnley and Rahul Savani.  The complexity of the simplex method.  In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 201–208. ACM, 2015.
  * [20] Harold N. Gabow and Shuxin Nie.  Finding a long directed cycle.  ACM Trans. Algorithms, 4(1):7:1–7:21, 2008.
  * [21] Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, and Yota Otachi.  Algorithmic meta-theorems for combinatorial reconfiguration revisited.  In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPIcs, pages 61:1–61:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [22] Donald Goldfarb and William Y. Sit.  Worst case behavior of the steepest edge simplex method.  Discret. Appl. Math., 1(4):277–285, 1979.
  * [23] Manoj Gupta, Hitesh Kumar, and Neeldhara Misra.  On the complexity of optimal matching reconfiguration.  In Barbara Catania, Rastislav Královic, Jerzy R. Nawrocki, and Giovanni Pighizzini, editors, SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings, volume 11376 of Lecture Notes in Computer Science, pages 221–233. Springer, 2019.
  * [24] Thomas Dueholm Hansen and Uri Zwick.  An improved version of the random-facet pivoting rule for the simplex algorithm.  In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 209–218. ACM, 2015.
  * [25] Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno.  On the complexity of reconfiguration problems.  Theor. Comput. Sci., 412(12-14):1054–1065, 2011.
  * [26] Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto.  Shortest reconfiguration of perfect matchings via alternating cycles.  SIAM J. Discret. Math., 36(2):1102–1123, 2022.
  * [27] Satoru Iwata.  On matroid intersection adjacency.  Discret. Math., 242(1-3):277–281, 2002.
  * [28] Robert G. Jeroslow.  The simplex algorithm with the pivot rule of maximizing criterion improvement.  Discret. Math., 4(4):367–377, 1973.
  * [29] Sean Kafer, Kanstantsin Pashkovich, and Laura Sanità.  On the circuit diameter of some combinatorial polytopes.  SIAM J. Discret. Math., 33(1):1–25, 2019.
  * [30] Marcin Kaminski, Paul Medvedev, and Martin Milanic.  Complexity of independent set reconfigurability problems.  Theor. Comput. Sci., 439:9–15, 2012.
  * [31] Victor Klee and George J. Minty.  How good is the simplex algorithm?  In Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin), pages 159–175. Academic Press, New York, 1972.
  * [32] Jesús A. De Loera, Raymond Hemmecke, and Jon Lee.  On augmentation algorithms for linear and integer-linear programming: From Edmonds-Karp to Bland and beyond.  SIAM J. Optim., 25(4):2494–2511, 2015.
  * [33] Ruy Fabila Monroy, David Flores-Peñaloza, Clemens Huemer, Ferran Hurtado, David R. Wood, and Jorge Urrutia.  On the chromatic number of some flip graphs.  Discret. Math. Theor. Comput. Sci., 11(2):47–56, 2009.
  * [34] Naomi Nishimura.  Introduction to reconfiguration.  Algorithms, 11(4):52, 2018.
  * [35] Francisco Santos.  A counterexample to the Hirsch conjecture.  Ann. Math., 176(1):383–412, 2012.
  * [36] Alexander Schrijver.  Combinatorial Optimization: Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics.  Springer, 2003.
  * [37] Jan van den Heuvel.  The complexity of change.  In Simon R. Blackburn, Stefanie Gerke, and Mark Wildon, editors, Surveys in Combinatorics 2013, volume 409 of London Mathematical Society Lecture Note Series, pages 127–160. Cambridge University Press, 2013\.
  * [38] Virginia V. Williams.  On some fine-grained questions in algorithms and complexity.  In Proceedings of the International Congress of Mathematicians (ICM 2018), pages 3447–3487. World Scientific, 2018.