Cycles of each even lengths in balanced bipartite digraphs

Samvel Kh. Darbinyan

Institute for Informatics and Automation Problems, Armenian National Academy
of Sciences

E-mails<EMAIL_ADDRESS>
Abstract

Let $D$ be a strongly connected balanced bipartite directed graph of order
$2a\geq 4$. Let $x,y$ be distinct vertices in $D$. $\\{x,y\\}$ dominates a
vertex $z$ if $x\rightarrow z$ and $y\rightarrow z$; in this case, we call the
pair $\\{x,y\\}$ dominating. In this paper we prove:

(i). If $a\geq 4$ and $max\\{d(x),d(y)\\}\geq 2a-1$ for every dominating pair
of vertices $\\{x,y\\}$, $D$ then contains a cycle of length $2a-2$ or $D$ is
a directed cycle.

(ii). If $D$ contains a cycle of length $2a-2\geq 6$ and
$max\\{d(x),d(y)\\}\geq 2a-2$ for every dominating pair of vertices
$\\{x,y\\}$, then for any $k$, $1\leq k\leq a-1$, $D$ contains a cycle of
length $2k$.

(iii). If $a\geq 4$ and $max\\{d(x),d(y)\\}\geq 2a-1$ for every dominating
pair of vertices $\\{x,y\\}$, then for every $k$, $1\leq k\leq a$, $D$
contains a cycle of length $2k$ unless $D$ is isomorphic to only one
exceptional digraph of order eight.

Keywords: Digraphs, cycles, Hamiltonian cycles, bipartite balanced digraph,
pancyclic, even pancyclic, longest non-Hamiltonian cycles.

##  1 Introduction

We consider directed graphs (digraphs) in the sense of [3]. For convenience of
the reader terminology and notations will be given in details in section 2. A
cycle (path) is called Hamiltonian if it includes all the vertices of $D$. A
digraph $D$ is Hamiltonian if it contains a Hamiltonian cycle and is pancyclic
if it contains a cycle of length $k$ for any $3\leq k\leq n$, where $n$ is the
order of $D$. A balanced bipartite digraph of order $2m$ is even pancyclic if
it contains a cycle of length $2k$ for any $k$, $2\leq k\leq m$.

Bondy suggested [6] the following interesting ”metaconjecture”:

Almost any non-trivial condition of a graph (digraph) which that the graph
(digraph) is Hamiltonian also implies that the graph (digraph) is pancyclic.
(There may be a ”simple” family of exceptional graphs (digraphs)).

There are numerous sufficient conditions for the existence of a Hamiltonian
cycle in a graph (digraph) for which ”metaconjecture” of Bondy is true.

In this note, we will concerted with the degree conditions. Let us recall the
following well-known degree conditions (theorems 1.1-1.4) that guarantee that
a digraph is Hamiltonian.
Theorem 1.1 (Ghouila-Houri [12]). Let $D$ be a strongly connected digraph of
order $n\geq 3$. If $d(x)\geq n$ for all vertices $x\in V(D)$, then $D$ is
Hamiltonian.

Theorem 1.2 (Woodall [20]). Let $D$ be a digraph of order $n\geq 3$. If
$d^{+}(x)+d^{-}(y)\geq n$ for all pairs of vertices $x$ and $y$ such that
there is no arc from $x$ to $y$, then $D$ is Hamiltonian.

Theorem 1.3 (Meyniel [16]). Let $D$ be a strongly connected digraph of order
$n\geq 2$. If $d(x)+d(y)\geq 2n-1$ for all pairs of non-adjacent vertices in
$D$, then $D$ is Hamiltonian.

Notice that Meyniel’s theorem is a common generalization of Ghouila-Houri’s
and Woodall’s theorems. For a short proof of Theorem 1.3, see [7].

C. Thomassen [18] (for $n=2k+1$) and S. Darbinyan [9] (for $n=2k$) proved the
following theorem below. Before stating it (for any integer $m\geq 2$) we need
to introduce some additional notations.

Let $H(m,m)$ denote the set of digraphs $D$ of order $2m$ with vertex set
$A\cup B$ such that $\langle A\rangle\equiv\langle B\rangle\equiv K^{*}_{m}$,
there is no arc from $B$ to $A$, $d^{+}(x,B)\geq 1$ and $d^{-}(y,A)\geq 1$ for
every vertices $x\in A$ and $y\in B$.

Let $H(m,m-1,1)$ denote the set of digraphs $D$ of order $2m$ with vertex set
$A\cup B\cup\\{a\\}$ such that $|A|=|B|+1=m$, $\langle
B\cup\\{a\\}\rangle\subseteq K^{*}_{m}$ (i.e., $\langle B\cup\\{a\\}\rangle$
is an arbitrary digraph) the subdigraph $\langle A\rangle$ has no arc, $D$
contains all possible arcs between $A$ and $B$ and either $N^{-}(a)=B$ and
$A\subseteq N^{+}(a)$, or $N^{+}(a)=B$ and $A\subseteq N^{-}(a)$.

Let $H(2m)$ denote a digraph of order $2m$ with vertex set $A\cup
B\cup\\{x,y\\}$ such that $\langle A\cup\\{x\\}\rangle\equiv\langle
B\cup\\{y\\}\rangle\equiv K^{*}_{m}$, there is no are between $A$ and $B$,
$H(2m)$ also contains all arcs of the form $ya$, $bx$, where $a\in A$ and
$b\in B$, and either the arc $xy$ or both arcs $xy$ and $yx$.

Let $D_{6}$ be a digraph with vertex set $\\{x_{1},x_{2},\ldots,x_{5},x\\}$
and arc set

$\\{x_{i}x_{i+1}\,/1\leq i\leq 4\\}\cup\\{xx_{i}/\,1\leq i\leq
3\\}\cup\\{x_{1}x_{5},x_{2}x_{5},x_{5}x_{1},x_{5}x_{4},x_{3}x_{2},x_{3}x,x_{4}x_{1},x_{4}x\\}.$

By $D^{\prime}_{6}$ we denote a digraph obtained from $D_{6}$ by adding the
arc $x_{2}x_{4}$. Note that the digraphs $D_{6}$ and $D^{\prime}_{6}$ both are
not Hamiltonian and each of $D_{6}$ and $D^{\prime}_{6}$ contains a cycle of
length 5.

Theorem 1.4 ( Thomassen [18], Darbinyan [9]). If $D$ is a digraph of order
$n\geq 5$ with minimum degree at least $n-1$ and with minimum semi-degree at
least $n/2-1$. Then $D$ is Hamiltonian unless

(i) $D$ is isomorphic to $D_{5}$ or $D_{7}$ or $[(K_{m}\cup K_{m})+K_{1}]^{*}$
or $K^{*}_{m,m+1}\subseteq D\subseteq[K_{m}+\overline{K}_{m+1}]^{*},$ if
$n=2m+1$;

(ii) $D\in H(m,m)\cup
H(m,m-1,1)\cup\\{H(2m),\,H^{\prime}(2m),\,D_{6},\,D^{\prime}_{6},\overleftarrow{D_{6}},\,\overleftarrow{D^{\prime}_{6}}\\}$,
if $n=2m$. (The digraphs $D_{5}$ and $D_{7}$ are well-known and for
definitions of their, see, for example, [18]).

In [15, 17, 8, 10] it was shown that if a digraph $D$ satisfies the condition
one of Theorems 1.1-1.4, respectively, then $D$ also is pancyclic (unless some
extremal cases which are characterized).

Characterizations of even pancyclic bipartite tournaments was given in [5] and
[21]. A characterizations of pancyclic ordinary $k$-partite ($k\geq 3$)
tournaments was established in [13]. A characterizations of pancyclic ordinary
complete $k$-partite ($k\geq 3$) digraphs was derived in [14]. Amar and
Manoussakis [2] gave several sufficient conditions on the half-degrees of a
bipartite digraph for the existence of cycles and paths of various lengths.

Each of Theorems 1.1-1.4 imposes a degree condition on all pairs of
nonadjacent vertices (or on all vertices). In [2, 4] were shown some
sufficient conditions for hamiltonicity of digraphs in which the degree
conditions require only for some pairs of nonadjacent vertices. Let us recall
of them only the following theorem.

Theorem 1.5 (Bang-Jensen, Gutin, H.Li [4]). Let $D$ be a strongly connected
digraph of order $n\geq 2$. Suppose that $min\\{d(x),d(y)\\}\geq n-1$ and
$d(x)+d(y)\geq 2n-1$ for any pair of nonadjacent vertices $x,y$ with a common
in-neighbor. Then $D$ is Hamiltonian.

An analogue of Theorem 1.5 for bipartite digraphs was given by R. Wang [19]
and recently strengthened by the author [11].

Theorem 1.6 (R. Wang [19]). Let $D$ be a strongly connected balanced bipartite
digraph of order $2a$, where $a\geq 1$. Suppose that, for every dominating
pair of vertices $\\{x,y\\}$, either $d(x)\geq 2a-1$ and $d(y)\geq a+1$ or
$d(y)\geq 2a-1$ and $d(x)\geq a+1$. Then $D$ is Hamiltonian.

Before stating the next theorem we need to define a digraph of order eight.

Definition. Let $D(8)$ be a bipartite digraph with partite sets
$X=\\{x_{0},x_{1},x_{2},x_{3}\\}$ and $Y=\\{y_{0},y_{1},y_{2},y_{3}\\}$, and
let $D(8)$ contains the arcs $y_{0}x_{1}$, $y_{1}x_{0}$, $x_{2}y_{3}$,
$x_{3}y_{2}$ and all the arcs of the following 2-cycles: $x_{i}\leftrightarrow
y_{i}$, $i\in[0,3]$, $y_{0}\leftrightarrow x_{2}$, $y_{0}\leftrightarrow
x_{3}$, $y_{1}\leftrightarrow x_{2}$ and it $y_{1}\leftrightarrow x_{3}$, and
it contains no other arcs.

It is not difficult to check that $D(8)$ is strongly connected,
$max\\{d(x),d(y)\\}\geq 2a-2$ for every pair of vertices $\\{x,y\\}$ with a
common in-neighbor and is not Hamiltonian.

We also need the following definition.

Definition. Let $D$ be a balanced bipartite digraph of order $2a$, where
$a\geq 2$, and let $k$ be an integer. We say that $D$ satisfies condition
$B_{k}$ if for every dominating pair of vertices $x$ and $y$,
$max\\{d(x),d(y)\\}\geq 2a-2+k$ .

Theorem 1.7 (Darbinyan [11]). Let $D$ be a strongly connected balanced
bipartite digraph of order $2a$, where $a\geq 4$. Suppose that
$max\\{d(x),d(y)\\}\geq 2a-1$, for every dominating pair of vertices
$\\{x,y\\}$. Then either $D$ is Hamiltonian or isomorphic to the digraph
$D(8)$.

Motivated by the Bondy’s ”metaconjecture”, it is natural to set the following
problem:

Characterize those digraphs which satisfy the conditions of Theorem 1.6 (1.7)
but are not even pancyclic.

In this note we prove the following theorems.

Theorem 1.8. Let $D$ be a strongly connected balanced bipartite digraph of
order $2a\geq 8$ with partite sets $X$ and $Y$. Suppose that $D$ satisfies
condition $B_{1}$, i.e., $max\\{d(x),d(y)\\}\geq 2a-1$ for every dominating
pair of vertices $\\{x,y\\}$. Then $D$ contains a cycle of length $2a-2$ or
$D$ is a directed cycle.

Theorem 1.9. Let $D$ be a strongly connected balanced bipartite digraph of
order $2a\geq 8$ with partite sets $X$ and $Y$. If $D$ contains a cycle of
length $2a-2$ and satisfies condition $B_{0}$, i.e., $max\\{d(x),d(y)\\}\geq
2a-2$ for every dominating pair of vertices $\\{x,y\\}$, then $D$ contains a
cycle of length $2k$ for all $k$, where $1\leq k\leq a-1$.

Theorem 1.10. Let $D$ be a strongly connected balanced bipartite digraph of
order $2a\geq 8$ with partite sets $X$ and $Y$. If $D$ is not a directed cycle
and $max\\{d(x),d(y)\\}\geq 2a-1$ for every dominating pair of vertices
$\\{x,y\\}$, then either $D$ contains cycles of all even lengths less than
equal to $2a$ or $D$ is isomorphic to the digraph $D(8)$.

Of course, Theorem 1.10 is an immediate corollary of Theorems 1.7-1.9.

##  2 Terminology and Notations

In this paper we consider finite digraphs without loops and multiple arcs.
Terminology and notations not described below follow [2]. For a digraph $D$,
we denote by $V(D)$ the vertex set of $D$ and by $A(D)$ the set of arcs in
$D$. The order of $D$ is the number of its vertices. The arc of a digraph $D$
directed from $x$ to $y$ is denoted by $xy$ or $x\rightarrow y$ (we also say
that $x$ dominates $y$ or $y$ is an out-neighbour of $x$ and $x$ is an in-
neighbour of $y$), and $x\leftrightarrow y$ denotes that $x\rightarrow y$ and
$y\rightarrow x$ ($x\leftrightarrow y$ is called 2-cycle). If $x\rightarrow y$
and $y\rightarrow z$ we write $x\rightarrow y\rightarrow z$. If there is no
arc from $x$ to $y$ we shall use the notation $xy\notin A(D)$. For disjoint
subsets $A$ and $B$ of $V(D)$ we define $A(A\rightarrow B)$ as the set
$\\{xy\in A(D)/x\in A,y\in B\\}$ and $A(A,B)=A(A\rightarrow B)\cup
A(B\rightarrow A)$. If $x\in V(D)$ and $A=\\{x\\}$ we sometimes write $x$
instead of $\\{x\\}$. If $A$ and $B$ are two disjoint subsets of $V(D)$ such
that every vertex of $A$ dominates every vertex of $B$, then we say that $A$
dominates $B$, denoted by $A\rightarrow B$. $A\mapsto B$ means that
$A\rightarrow B$ and there is no arc from $B$ to $A$. Similarly,
$A\leftrightarrow B$ means that $A\rightarrow B$ and $B\rightarrow A$. The
out-neighborhood of a vertex $x$ is the set $N^{+}(x)=\\{y\in V(D)/xy\in
A(D)\\}$ and $N^{-}(x)=\\{y\in V(D)/yx\in A(D)\\}$ is the in-neighborhood of
$x$. Similarly, if $A\subseteq V(D)$, then $N^{+}(x,A)=\\{y\in A/xy\in
A(D)\\}$ and $N^{-}(x,A)=\\{y\in A/yx\in A(D)\\}$. The out-degree of $x$ is
$d^{+}(x)=|N^{+}(x)|$ and $d^{-}(x)=|N^{-}(x)|$ is the in-degree of $x$.
Similarly, $d^{+}(x,A)=|N^{+}(x,A)|$ and $d^{-}(x,A)=|N^{-}(x,A)|$. The degree
of the vertex $x$ in $D$ is defined as $d(x)=d^{+}(x)+d^{-}(x)$ (similarly,
$d(x,A)=d^{+}(x,A)+d^{-}(x,A)$). The subdigraph of $D$ induced by a subset $A$
of $V(D)$ is denoted by $D\langle A\rangle$ or $\langle A\rangle$ brevity. The
path (respectively, the cycle) consisting of the distinct vertices
$x_{1},x_{2},\ldots,x_{m}$ ( $m\geq 2$) and the arcs $x_{i}x_{i+1}$,
$i\in[1,m-1]$ (respectively, $x_{i}x_{i+1}$, $i\in[1,m-1]$, and $x_{m}x_{1}$),
is denoted by $x_{1}x_{2}\cdots x_{m}$ (respectively, $x_{1}x_{2}\cdots
x_{m}x_{1}$). The length of a cycle or a path is the number of its arcs. We
say that $x_{1}x_{2}\cdots x_{m}$ is a path from $x_{1}$ to $x_{m}$ or is an
$(x_{1},x_{m})$-path. The length of a cycle or a path is the number of its
arcs.

If $P$ is a path containing a subpath from $x$ to $y$ we let $P[x,y]$ denote
that subpath. Similarly, if $C$ is a cycle containing vertices $x$ and $y$,
$C[x,y]$ denotes the subpath of $C$ from $x$ to $y$. Given a vertex $x$ of a
path $P$ or a cycle $C$, we denote by $x^{+}$ (respectively, by $x^{-}$) the
successor (respectively, the predecessor) of $x$ (on $P$ or $C$), and in case
of ambiguity, we precise $P$ or $C$ as a subscript (that is $x^{+}_{P}$ …).

A digraph $D$ is strongly connected (or, just, strong) if there exists a path
from $x$ to $y$ and a path from $y$ to $x$ for every pair of distinct vertices
$x,y$.

Two distinct vertices $x$ and $y$ are adjacent if $xy\in A(D)$ or $yx\in A(D)$
(or both). For integers $a$ and $b$, $a\leq b$, let $[a,b]$ denote the set of
all the integers which are not less than $a$ and are not greater than $b$. Let
$C$ be a non-Hamiltonian cycle in digraph $D$. An $(x,y)$-path $P$ is a
$C$-bypass if $|V(P)|\geq 3$, $x\not=y$ and $V(P)\cap V(C)=\\{x,y\\}$. The
length of the path $C[x,y]$ is the gap of $P$ with respect to $C$.

A digraph $D$ is a bipartite if there exists a partition $X$, $Y$ of $V(D)$
into two partite sets such that every arc of $D$ has its end-vertices in
different partite sets. It is called balanced if $|X|=|Y|$. The underlying
graph of a digraph $D$ is denoted by $UG(D)$, it contains an edge $xy$ if
$x\rightarrow y$ or $y\rightarrow x$ (or both).

##  3  Preliminaries

Let us recall some results (Lemmas 3.1-3 .3) which will be used in this paper.

Lemma 3.1 ([11]). Let $D$ be a strongly connected balanced bipartite digraph
of order $2a\geq 8$. If $D$ satisfies condition $B_{1}$, then the following
holds:

(i) $UG(D)$ is 2-connected;

(ii) if $C$ is a cycle of length $m$, $2\leq m\leq 2a-2$, then $D$ contains a
$C$-bypass.

Lemma 3.2 ([11]). Let $D$ be a strongly connected balanced bipartite digraph
of order $2a\geq 8$ other than the directed cycle of length $2a$. If $D$
satisfies condition $B_{0}$, then $D$ has a non-Hamiltonian cycle of length at
least four.

Lemma 3.3 ([1]). Let $D$ be a bipartite digraph of order $n$ which contains a
cycle $C$ of length $2b$, where $2\leq 2b\leq n-1$. Let $x$ be a vertex not
contained in $C$. If $d(x,V(C))\geq b+1$, then $D$ contains cycles of every
even length $m$, $2\leq m\leq 2b$, through $x$.

Now we prove the following lemma.

Lemma 3.4. Let $D$ be a strongly connected balanced bipartite digraph of order
$2a\geq 8$ with partite sets $X$ and $Y$. Assume that $D$ satisfies condition
$B_{0}$. Let $C=x_{1}y_{1}x_{2}y_{2}\ldots x_{k}y_{k}x_{1}$ be a longest non-
Hamiltonian cycle in $D$, where $k\geq 2$, $x_{i}\in X$ and $y_{i}\in Y$. If
in $D$ there exists a $C$-bypass whose gap with respect to $C$ is equal to
one, then $k=a-1$, i.e., the longest non-Hamiltonian cycle in $D$ has length
equal to $2a-2$.

Proof of Lemma 3.4. Without loss of generality, we assume that
$P:=x_{1}u_{1}u_{2}\ldots u_{s}y_{1}$ ($s\geq 1$) is a $C$-bypass. Suppose
that the lemma is not true, that is $k\leq a-2$. Then $u_{1}\in Y$ and
$u_{s}\in X$ and $R:=V(D)\setminus V(C)=\\{u_{1},u_{2},\ldots,u_{s}\\}$. Note
that $|R|=s\geq 4$. Since $C$ is a longest non-Hamiltonian cycle in $D$, it is
not difficult to show that

$d^{+}(u_{1},\\{u_{3},u_{4},\ldots,,u_{s}\\})=d^{-}(u_{s},\\{u_{1},u_{2},\ldots,u_{s-2}\\})=d^{+}(x_{1},\\{u_{2},u_{3},\ldots,u_{s}\\})=0,$
$None$

and the following arcs

$u_{s-1}x_{2},\,y_{k}u_{2},\,x_{k}u_{1},\,u_{s}y_{2},\,u_{3}x_{2},x_{1}u_{3},\,y_{k-1}x_{1},\,y_{1}x_{3},\,u_{2}y_{1}$
$None$

are not in $A(D)$ (for otherwise, $D$ contains a non-Hamiltonian cycle longer
than $C$). Note that $\\{u_{s},x_{1}\\}$ is a dominating pair. Therefore, by
condition $B_{0}$ we have

$max\\{d(x_{1}),d(u_{s})\\}\geq 2a-2.$ $None$

If $|R|=s\geq 6$, then from (1) and (2) we have
$d^{-}(u_{s},\\{u_{1},u_{3}\\})=d^{+}(x_{1},\\{u_{3},u_{5}\\})=0$ and the arcs
$u_{s}y_{2}$ and $y_{k-1}x_{1}$ are not in $A(D)$. Therefore, $d(u_{s})$ and
$d(x_{1})\leq 2a-3$, which contradicts (3).

Assume therefore that $|R|=4$ (i.e., $s=4$) and consider the following two
cases.

Case 1. The vertices $u_{1}$ and $u_{4}$ are not adjacent.

Then

$d(u_{1})\leq 2a-3\quad\hbox{and}\quad d(u_{4})\leq 2a-3$ $None$

since $x_{k}u_{1}$ and $u_{4}y_{2}\notin A(D)$ by (2). From (3) and the second
inequality of (4) it follows that $d(x_{1})\geq 2a-2$. By (2) we have
$x_{1}u_{3}$ and $y_{k-1}x_{1}\notin A(D)$. This together with $d(x_{1})\geq
2a-2$ implies that $\\{u_{1},u_{3},y_{1}\\}\rightarrow x_{1}$. In particular,
$\\{u_{1},u_{3}\\}$ is a dominating pair. From the first inequality of (4) and
condition $B_{0}$ it follows that $d(u_{3})\geq 2a-2$. On the other hand, by
(2) we have $x_{1}u_{3}$ and $u_{3}x_{2}\notin A(D)$. Hence, $u_{4}\rightarrow
u_{3}\rightarrow u_{2}$, $x_{k}\rightarrow u_{3}$. Thus,
$\\{u_{2},u_{4}\\}\rightarrow u_{3}$, which means that $\\{u_{2},u_{4}\\}$ is
a dominating pair. Therefore, by condition $B_{0}$, $d(u_{2})\geq 2a-2$ since
$d(u_{4})\geq 2a-3$ by (4). From $d(u_{2})\geq 2a-2$ and $y_{k}u_{2}\notin
A(D)$, $u_{2}y_{1}\notin A(D)$ (by (2)) it follows that $u_{2}\rightarrow
u_{1}$. Thus, $x_{k}u_{3}u_{2}u_{1}x_{1}y_{1}\ldots y_{k-1}x_{k}$ is a cycle
of length $2a-2$, which is a contradiction.

Case 2. The vertices $u_{1}$ and $u_{4}$ are adjacent.

Then, by (1), we have $u_{4}\mapsto u_{1}$. We divide this case into two
subcases.

Subcase 2.1. $d(x_{1})\leq 2a-3$.

Then $d(u_{4})\geq 2a-2$ because of (3) (recall that $s=4$). Then, since, by
(1) and (2), the arcs $u_{1}u_{4}$ and $u_{4}y_{2}$ are not in $A(D)$, it
follows that

$d(u_{4})=2a-2,\quad y_{1}\rightarrow u_{4}\rightarrow
u_{3}\quad\hbox{and}\quad y_{2}\rightarrow u_{4}.$ $None$

If $u_{3}\rightarrow x_{3}$, then by (5) we have that
$y_{1}u_{4}u_{1}u_{2}u_{3}x_{3}\ldots y_{1}$ is a cycle of length $2a-2$, a
contradiction. Assume therefore that $u_{3}x_{3}\notin A(D)$ (possibly
$x_{3}=x_{1}$). This together with $x_{1}u_{3}\notin A(D)$ and
$u_{3}x_{2}\notin A(D)$ (by (2)) implies that $d(u_{3})\leq 2a-3$. Therefore,
by condition $B_{0}$ we have,

$d(y_{1})\geq 2a-2\quad\hbox{and}\quad d(y_{2})\geq 2a-2$ $None$

since $\\{u_{3},y_{1},y_{2}\\}\rightarrow u_{4}$ by (5).

Assume that $k\geq 3$, i.e., the cycle $C$ has length at least 6. Since $D$
contains the following arcs $x_{1}\rightarrow u_{1},u_{4}\rightarrow
y_{1},u_{4}\rightarrow u_{1}$ and $y_{1}\rightarrow u_{4}$, it is not
difficult to show that $y_{2}x_{4}\notin A(D)$ and $u_{2}y_{2}\notin A(D)$
(possibly $x_{4}=x_{1}$) (for otherwise, if $y_{2}\rightarrow x_{4}$, then the
cycle $x_{1}u_{1}u_{2}u_{3}u_{4}y_{1}x_{2}y_{2}x_{4}\ldots x_{1}$ has length
$2a-2$; if $u_{2}\rightarrow y_{2}$, then now the cycle
$x_{1}y_{1}u_{4}u_{1}u_{2}y_{2}\ldots x_{1}$ has length $2a-2$, which is a
contradiction). This together with $u_{4}y_{2}\notin A(D)$ (by (2)) gives
$d(y_{2})\leq 2a-3$. This contradicts the second inequality of (6).

Now assume that $k=2$. It is easy to see that $y_{1}x_{1}\notin A(D)$ (for
otherwise, $y_{1}x_{1}u_{1}u_{2}u_{3}u_{4}y_{1}$ is a cycle of length 6).
This, $u_{2}y_{1}\notin A(D)$ and $d(y_{1})\geq 2a-2$ (by (6)) imply that
$y_{1}\rightarrow u_{2}$ and $x_{2}\rightarrow y_{1}$. For the vertex $y_{2}$
we have that $u_{4}y_{2}\notin A(D)$, $y_{2}u_{2}\notin A(D)$ and
$x_{1}\rightarrow y_{2}\rightarrow x_{2}$, $u_{2}\rightarrow y_{2}$ because of
the second inequality of (6). Therefore, $y_{2}x_{1}y_{1}u_{4}u_{1}u_{2}y_{2}$
is a cycle of length 6, a contradiction.

Subcase 2.2. $d(x_{1})\geq 2a-2$.

By (2) we have $x_{1}u_{3}$ and $y_{k-1}x_{1}\notin A(D)$. This together with
$d(x_{1})\geq 2a-2$ implies that $d(x_{1})=2a-2$ and

$u_{1}\rightarrow x_{1},\,\,u_{3}\mapsto x_{1},\,\,x_{1}\rightarrow y_{k}.$
$None$

Assume that $k\geq 3$. Then, because of $y_{k-1}x_{1}\notin A(D)$,
$y_{k-1}\not=y_{1}$ and (7), we have

$\\{u_{1},u_{3},y_{1}\\}\rightarrow x_{1}.$

It is not difficult to show that $d^{+}(y_{k},\\{u_{2},u_{4}\\})=0$ (since
$\\{u_{1},u_{3}\\}\rightarrow x_{1}$ and $u_{4}\rightarrow u_{1}$), and
$x_{k-1}y_{k}\notin A(D)$ (if $x_{k-1}\rightarrow y_{k}$, then
$x_{1}u_{1}u_{2}u_{3}u_{4}y_{1}\ldots x_{k-1}y_{k}x_{1}$ is a cycle of length
$2a-2$). Therefore, $d(y_{k})\leq 2a-3$. Then from condition $B_{0}$ we have
$d(u_{1})\geq 2a-2$ and $d(y_{1})\geq 2a-2$, since
$\\{u_{1},y_{1},y_{k}\\}\rightarrow x_{1}$. The inequality $d(u_{1})\geq 2a-2$
together with $u_{1}u_{4}$ and $x_{k}u_{1}\notin A(D)$ implies that
$u_{1}\leftrightarrow x_{2}$. Now we have that the arcs $y_{1}u_{4}$,
$u_{2}y_{1}$ and $y_{1}x_{3}$ are not in $A(D)$. Thus $d(y_{1})\leq 2a-3$,
which contradicts that $d(y_{1})\geq 2a-2$.

Now assume that $k=2$. We consider the vertex $y_{2}$. It is easy to see that
$y_{2}u_{2}\notin A(D)$ and $d(y_{2},\\{u_{4}\\})=0$ (if $y_{2}\rightarrow
u_{4}$, then, by (7), we have that $y_{2}u_{4}u_{1}x_{1}y_{1}x_{2}y_{2}$) is a
cycle of length 6. Therefore, $d(y_{2})\leq 2a-3$. This together with
condition $B_{0}$ implies that $d(u_{3})\geq 2a-2$, since
$\\{y_{2},u_{3}\\}\rightarrow x_{1}$. The inequality $d(u_{3})\geq 2a-2$
together with $x_{1}u_{3}$, $u_{3}x_{2}\notin A(D)$ implies that
$x_{2}\rightarrow u_{3}$. Hence, the cycle
$x_{2}u_{3}u_{4}u_{1}x_{1}y_{1}x_{2}$ is a cycle of length 6, a contradiction.
Lemma 3.4 is proved.

##  4 The proofs of the main results

Proof of Theorem 1.8. Suppose, on the contrary, that $D$ is not a directed
cycle and $D$ contains no cycle of length $2a-2$. Let
$C=x_{1}y_{1}x_{2}y_{2}\ldots x_{k}y_{k}x_{1}$ be a longest non-Hamiltonian
cycle in $D$, where $x_{i}\in X$ and $y_{i}\in Y$. By Lemma 3.2, $D$ contains
a non-Hamiltonian cycle of length at least 4, i.e., $2\leq k\leq a-2$. By
Lemma 3.1(ii), $D$ contains a $C$-bypass. Let $P:=uu_{1}\ldots u_{s}v$ be a
$C$-bypass ($s\geq 1$). Suppose that the gap of $P$ is minimum among the gaps
of all $C$-bypasses.

From Lemma 3.4 it follows that $|V(C[u,v])|\geq 3$. The proof splits into
cases, depending on the length of $C$-bypass $P$ and on the length of
$C[u,v]$.

Case 1. $s\geq 2$.

Then $2\leq s\leq|V(C[u,v])|-2$. Note that $\\{u_{s},v^{-}_{C}\\}$ is a
dominating pair. Since $C$ is a longest non-Hamiltonian cycle in $D$ and
$C$-bypass $P$ has the minimum gap among the gaps of all $C$-bypasses, it
follows that $v^{-}_{C}$ is not adjacent to any vertex on $P[u_{1},u_{s}]$ and
$u_{s}$ is not adjacent to any vertex on $C[u^{+}_{C},v^{-}_{C}]$. Notice that
each of $P[u_{1},u_{s}]$ and $C[u^{+}_{C},v^{-}_{C}]$ contains at least one
vertex from each partite set. Therefore, $max\\{d(u_{s}),d(v^{-}_{C})\\}\leq
2a-2$, which contradicts condition $B_{1}$ since $\\{u_{s},v^{-}_{C}\\}$ is a
dominating pair.

Case 2. $s=1$.

It is easy to see that $u$ and $v$ belong to the same partite set and
$|V(C[u,v])|$ is odd. Now, without loss of generality, assume that $x_{1}=u$,
$v=x_{r}$ and $u_{1}=y$. Then $y\in Y$. Denote $R:=V(D)\setminus V(C)$ and
$C^{\prime}:=V(C[y_{1},y_{r-1}])$. Now we consider two subcases ($r\geq 3$ and
$r=2$).

Subcase 2.1. $r\geq 3$.

Let $x$ be an arbitrary vertex of $X\cap R$. Note that $\\{y,y_{r-1}\\}$ is a
dominating pair. Recall that $y$ is not adjacent to any vertices of
$C^{\prime}$. Therefore,

$d(y)\leq 2a-2\quad\hbox{and}\quad d(x_{i})\leq 2a-2\quad\hbox{for all}\quad
x_{i}\in X\cap C^{\prime},$ $None$

since $X\cap C^{\prime}\not=\emptyset$. The first inequality of (8) together
with condition $B_{1}$ implies that

$d(y_{r-1})\geq 2a-1,$

which in turn implies that $y_{r-1}$ and every vertex of $X$ are adjacent. In
particular, $y_{r-1}$ and $x$ are adjacent.

Assume first that $x\rightarrow y_{r-1}$. Then $\\{x,x_{r-1}\\}$ is a
dominating pair. By the second inequality of (8) we have $d(x_{r-1})\leq
2a-2$. On the other hand, since $C$-bypass $P$ has the minimum gap among the
gaps of all $C$-bypasses, it follows that $y_{1}x$ and $yx\notin A(D)$.
Therefore, $d(x)\leq 2a-2$. Thus, $max\\{d(x),d(x_{r-1})\\}\leq 2a-2$, which
is a contradiction since $\\{x,x_{r-1}\\}$ is a dominating pair.

Assume second that $xy_{r-1}\notin A(D)$. Then $y_{r-1}\rightarrow x$, since
$x$ and $y_{r-1}$ are adjacent. By the arbitrariness of $x$, we may assume
that $y_{r-1}\mapsto X\cap R$. Combining this with $d(y_{r-1})\geq 2a-1$ we
obtain that $|R|=2$, i.e., $|V(C)|=2a-2$, which contradicts the supposition
that $D$ contains no cycle of length $2a-2$.

Subcase 2.2. $r=2$.

Now note that $\\{y,y_{1}\\}$ is a dominating pair. By condition $B_{1}$ ,
$max\\{d(y),d(y_{1})\\}\geq 2a-1$. Without loss of generality, we may assume
that $d(y)\geq 2a-1$ (if $d(y_{1})\geq 2a-1$, then we will consider the cycle
$Q:=x_{1}yx_{2}\ldots x_{1}$, which has the same length as $C$ and
$x_{1}y_{1}x_{2}$ is a $Q$-bypass), which in turn implies that $y$ and every
vertex of $X$ are adjacent. Notice that $|X\cap R|\geq 2$, since $|R|\geq 4$.
This together with $d(y)\geq 2a-1$ implies that there exists a vertex $x\in
X\cap R$ such that $x\leftrightarrow y$. To complete the proof we now will
prove the following three claims below.

Claim 1. For any $x_{i}\in X\cap V(C)$, if $x_{i}\rightarrow y$, then
$xy_{i}\notin A(D)$; if $y\rightarrow x_{i}$, then $y_{i-1}x\notin A(D)$.

Indeed, for otherwise if $x_{i}\rightarrow y$ and $x\rightarrow y_{i}$, then
the cycle $x_{i}yxy_{i}x_{i+1}\ldots x_{1}$ is longer than $C$, and if
$y\rightarrow x_{i}$ and $y_{i-1}\rightarrow x$, the cycle
$y_{i-1}xyx_{i}y_{i}\ldots y_{i-1}$ is longer than $C$, a contradiction to the
maximality of $C$.

From Claim 1 it immediately follows the following :

Claim 2. If there exists a vertex $x_{i}\in X\cap V(C)$ such that
$x_{i}\rightarrow y\rightarrow x_{i+1}$, then $x$ and $y_{i}$ are not
adjacent.

Claim 3. If there is a vertex $x_{i}\in X\cap V(C)$ such that
$x_{i}\leftrightarrow y$, then $x_{i+1}\mapsto y$ and $y\mapsto x_{i-1}$ are
impossible.

Proof of Claim 3. Suppose, on the contrary, that there is a vertex $x_{i}\in
X\cap V(C)$ such that $x_{i}\leftrightarrow y$ and $x_{i+1}\mapsto y$ or
$y\mapsto x_{i-1}$. Combining this with $d(y)\geq 2a-1$, we obtain that $y$
and every vertex of $X\cap R$ form a 2-cycle. In particular, any two vertices
of $X\cap R$ form a dominating pair. If $x_{i+1}\mapsto y$, then $y\rightarrow
x_{i+2}$ and, by Claim 2, the vertex $y_{i+1}$ and every vertex $z$ of $X\cap
R$ are nonadjacent. If $y\mapsto x_{i-1}$, then $y\rightarrow x_{i+1}$ and, by
Claim 2, the vertex $y_{i}$ and every vertex $z$ of $X\cap R$ are nonadjacent.
In both cases we have $d(z)\leq 2a-2$ for all $z\in X\cap R$, which
contradicts condition $B_{1}$ since $|X\cap R|\geq 2$. Claim 3 is proved.

Now we can finish the proof of Theorem 1.8.

From Claim 3 and $d(y)\geq 2a-1$ it follows that $y$ and every vertex of
$X\cap V(C)$ form a 2-cycle. Combining this with Claim 2, we obtain that $x$
and every vertex $y_{i}$ are not adjacent, which in turn implies that

$d(y_{i})\leq 2a-2\quad\hbox{and}\quad d(x)\leq 2a-2.$ $None$

Note that for any $x_{i}$, $\\{x,x_{i}\\}$ is a dominating pair, since
$\\{x,x_{i}\\}\rightarrow y$. This together with the second inequality of (9)
and condition $B_{1}$ implies that $d(x_{i})\geq 2a-1$ for all $x_{i}$. Hence,
any $x_{i}$ forms a 2-cycle with every vertex of $Y$ maybe except one. If
$x_{i}$ and $y_{j}$ form a 2-cycle and $y_{j}\not=y_{i-1}$,then
$\\{y_{i-1},y_{j}\\}\rightarrow x_{i}$ (i.e., $\\{y_{i-1},y_{j}\\}$ is a
dominating pair) which is a contradiction because of (9). Assume therefore
that $d(x_{i},\\{y_{j}\\})\leq 1$ for all $y_{j}\not=y_{i-1}$. It follows that
$y_{i}x_{i}\notin A(D)$ and $|Y\cap V(C)|=2$, i.e., the cycle $C$ has length
to equal 4. Thus, we may assume that for any $x_{i}$ there is no $y_{j}$ other
than $y_{i-1}$ such that $y_{j}\rightarrow x_{i}$. We have $y_{1}x_{1}\notin
A(D)$, $y_{2}x_{2}\notin A(D)$, $x_{2}\rightarrow y_{1}$ and $x_{1}\rightarrow
y_{2}$. Therefore $x_{2}$ forms a 2-cycle with every vertex of $Y\cap R$ since
$d(x_{2})\geq 2a-1$ and $y_{2}x_{2}\notin A(D)$. Let $w\in Y\cap R$ be an
arbitrary vertex other that $y$. Then $w\leftrightarrow x_{2}$ and hence,
$\\{y_{1},w\\}$ is a dominating pair. By the first inequality of (9) and
condition $B_{1}$ we have $d(w)\geq 2a-1$, which in turn implies that
$x\rightarrow w$ or $w\rightarrow x$. If $x\rightarrow w$, then
$x_{1}yxwx_{2}y_{2}x_{1}$ is a cycle of length 6. If $w\rightarrow x$, then
$x_{2}wxyx_{1}y_{1}x_{2}$ is a cycle of length 6. In both cases we have a
longer non-Hamiltonian cycle than $C$, which is a contradiction and completes
the discussion of Subcase 2.2. Theorem 1.8 is proved.

Proof of Theorem 1.9. Let $C=x_{1}y_{1}x_{2}y_{2}\ldots x_{a-1}y_{a-1}x_{1}$
be a cycle of length $2a-2$ in $D$, where $x_{i}\in X$ and $y_{i}\in Y$. Let
the vertices $x$ and $y$ are not on $C$, where $x\in X$ and $y\in Y$. We
distinguish two cases.

Case 1. $d(x)\geq 2a-2$ or $d(y)\geq 2a-2$.

Without loss of generality, we may assume that $d(x)\geq 2a-2$. Since
$d(x)=d(x,\\{y\\})+d(x,V(C))$ and since $a\geq 4$, it follows that
$d(x,V(C))\geq 2a-4\geq a$. Therefore, by Lemma 3.3, $D$ contains cycles of
all even lengths less than or equal to $2a-2$.

Case 2. $d(x)\leq 2a-3$ and $d(y)\leq 2a-3$.

Without loss of generality, we may assume that $x\rightarrow y_{1}$ since $D$
is strong. We have, $\\{x,x_{1}\\}\rightarrow y_{1}$, i.e., $\\{x,x_{1}\\}$ is
a dominating pair. Therefore, by condition $B_{0}$, $d(x_{1})\geq 2a-2$. It is
easy to see that $D$ contains a cycle of length two since $a\geq 4$.

Assume first that there exists a vertex $y_{l}$ of $V(C)$ such that $x_{1}$
and $y_{l}$ are not adjacent. It is clear that
$y_{l}\notin\\{y_{1},y_{a-1}\\}$. Moreover, $x_{1}$ together with every vertex
$y_{i}$ other than $y_{l}$ forms a 2-cycle. Therefore $x_{1}y_{1}x_{2}\ldots
y_{j}x_{1}$ is a cycle of length $2j$ for every $j\in[1,l-1]\cup[l+1,a-1]$.

Now we will show that $D$ contains also a cycle of length $2l$. If $3\leq
l\leq a-3$, then $x_{1}y_{2}x_{3}\ldots x_{l+1}y_{l+1}x_{1}$ is a cycle of
length $2l$. Assume therefore that $l=a-2$ or $l=2$. Let $l=a-2\geq 3$. Then
$x_{1}\leftrightarrow y_{2}$ and $x_{1}y_{2}x_{3}\ldots y_{a-1}x_{1}$ is a
cycle of length $2l=2a-4$. If $l=a-2=2$, then $a=4$ and $x_{1}\leftrightarrow
y$. By condition $B_{0}$, it is not difficult to see that $d(y_{3})\geq 2a-2$
and $d(y_{1})\geq 2a-2$ since $\\{y,y_{1},y_{3}\\}\rightarrow x_{1}$ and
$d(y)\leq 2a-3$. From this it follows that $d(y_{3},\\{x,x_{2}\\})\geq 2$, and
in any possible case $D$ contains a cycle of length 4. If $l=2\not=a-2$, then
$x_{1}\leftrightarrow y_{a-2}$ and $x_{1}y_{a-2}x_{a-1}y_{a-1}x_{1}$ is a
cycle of length 4. Thus, $D$ contains cycles of every length
$2,4,\ldots,2a-2$.

Assume second that $x_{1}$ and every vertex $y_{i}$ of $V(C)$ are adjacent. If

$x_{1}\rightarrow\\{y_{2},y_{3},\ldots,y_{a-2}\\}\quad\hbox{or}\quad\\{y_{2},y_{3},\ldots,y_{a-2}\\}\rightarrow
x_{1}$ $None$

then it is easy to check that $D$ contains a cycle of length $2k$ for all
$k\in[1,a-2]$. Assume therefore that (10) is not true. Using the fact that
$d(x_{1})\geq 2a-2$, it is not difficult to see that $y_{1}\rightarrow
x_{1}\rightarrow y_{a-1}$. Indeed, if $y_{1}x_{1}\notin A(D)$, then from

$2a-4\leq
d(x_{1},V(C))=d^{+}(x_{1},\\{y_{1},y_{2},\ldots,y_{a-1}\\})+d^{-}(x_{1},\\{y_{2},y_{3},\ldots,y_{a-1}\\})$

it follows that $d^{+}(x_{1},\\{y_{1},y_{2},\ldots,y_{a-1}\\})=a-1$ or
$d^{-}(x_{1},\\{y_{2},y_{3},\ldots,y_{a-1}\\})=a-2$, which contradicts the
assumption that (10) is not true. Therefore, $y_{1}\rightarrow x_{1}$.
Similarly one can show that $x_{1}\rightarrow y_{a-1}$. Since $x_{1}$ and
every vertex $y_{i}\in V(C)$ are adjacent and since (10) is false, using
$y_{1}\rightarrow x_{1}\rightarrow y_{a-1}$, we obtain that there are two
distinct vertices $y_{k}$ and $y_{l}$ such that $y_{k}\mapsto x_{1}$ and
$x_{1}\mapsto y_{l}$ where $2\leq k\leq a-2$ and $2\leq l\leq a-2$. This
together with $d(x_{1})\geq 2a-2$ implies that $x_{1}$ and every vertex of
$Y\setminus\\{y_{k},y_{l}\\}$ form a 2-cycle.

Assume first that $l<k$. Then $2\leq l<k\leq a-2$ and

$\\{y_{1},y_{2},\ldots,y_{l-1},y_{l+1},\ldots,y_{a-1}\\}\rightarrow
x_{1}\quad\hbox{and}\quad x_{1}\rightarrow\\{y_{1},y_{2},\ldots,y_{k-1}\\}$

Therefore, the cycle $x_{1}y_{1}x_{2}\ldots x_{j}y_{j}x_{1}$, where
$j\in[1,a-1]\setminus\\{l\\}$, is a cycle of length $2j$, and the cycle
$x_{1}y_{2}x_{3}\ldots x_{l+1}y_{l+1}x_{1}$ is a cycle of length $2l$. Thus
$D$ contains cycles of every length $2,4,\ldots,2a-2$.

Assume next that $k<l$. Then $2\leq k<l\leq a-2$ and
$\\{y_{1},y_{2},\ldots,y_{l-1},y_{l+1},\ldots,y_{a-1}\\}\rightarrow x_{1}$.
From this we have that $x_{1}y_{1}x_{2}\ldots x_{j}y_{j}x_{1}$ is a cycle of
length $2j$ for all $j\in[1,l-1]\cup[l+1,a-2]$.

Now we want to show that $D$ contains also a cycle of length $2l$. If $k\geq
3$, then $x_{1}\rightarrow y_{2}$ and the cycle $x_{1}y_{2}x_{3}\ldots
x_{l+1}y_{l+1}x_{1}$ is a cycle of length $2l$. Assume therefore that $k=2$.
Then

$x_{1}\rightarrow\\{y_{3},y_{4},\ldots,y_{a-1}\\}\quad\hbox{and}\quad\\{y_{l+1},y_{l+2},\ldots,y_{a-1}\\}\rightarrow
x_{1}.$

Hence, if $l\leq a-3$, then the cycle $x_{1}y_{3}x_{4}\ldots
x_{l+2}y_{l+2}x_{1}$ is a cycle of length $2l$. Thus we have $k=2$ and
$l=a-2$. It remains to show that $D$ contains a cycle of length $2l=2a-4$.
Recall that $y_{2}\mapsto x_{1}$ and $x_{1}\mapsto y_{a-2}$. Since
$x_{1}\leftrightarrow y$, it follows that $\\{y,y_{a-1}\\}$ is a dominating
pair. By the assumption of Case 2, $d(y)\leq 2a-3$. Therefore, from condition
$B_{0}$ it follows that $d(y_{a-1})\geq 2a-2$. If $y_{a-1}\rightarrow x_{2}$
or $x_{a-2}\rightarrow y_{a-1}$, then $y_{a-1}x_{2}y_{2}\ldots x_{a-1}y_{a-1}$
or $x_{a-2}y_{a-1}x_{1}y_{1}\ldots y_{a-3}x_{a-2}$ is a cycle of length
$2a-4$, respectively for $y_{a-1}\rightarrow x_{2}$ and $x_{a-2}\rightarrow
y_{a-1}$. Assume therefore that $y_{a-1}x_{2}\notin A(D)$ and
$x_{a-2}y_{a-1}\notin A(D)$. Then, since $d(y_{a-1})\geq 2a-2$, we have
$y_{a-1}\leftrightarrow x$ and hence, the cycle $y_{a-1}xy_{1}x_{1}y_{3}\ldots
x_{a-1}y_{a-1}$ is a cycle of length $2a-4$. Thus we have shown that $D$
contains cycles of every even length $m$, $2\leq m\leq 2a-2$. Theorem 1.9 is
proved.

Proof of Theorem 1.10. By Theorem 1.7, either $D$ contains a cycle of length
$2a$ (i.e., $D$ is Hamiltonian) or $D$ is isomorphic to the digraph $D(8)$. By
Theorem 1.8, if $D$ is not a directed cycle, then it contains a cycle of
length $2a-2$. Now by Theorem 1.9, $D$ contains cycles of every even length
$2k$, where $1\leq k\leq a-1$. Therefore, if $D$ is other than $D(8)$ and a
directed cycle, then $D$ is even pancyclic. Theorem 1.10 is proved.

## References

  * [1] D. Amar, Y. Manoussakis, Cycles and Paths of many lengths in bipartite digraphs, Journal Combinatorial Theory Ser. B 50 (1990), 254-264.
  * [2] J. Bang-Jensen, Y. Guo, A.Yeo, A new sufficient condition for a digraph to be Hamiltonian, Discrete Applied Mathematics, 95 (1999) 61-72.
  * [3] J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, 2000.
  * [4] J. Bang-Jensen, G. Gutin, H. Li, Sufficient conditions for a digraph to be Hamiltonian, Journal of Graph Theory, 22 (20) (1996) 181-187.
  * [5] L.W. Beineke, C. Little, Cycles in bipartite tournaments, Journal Combinatorial Theory Ser. B 32 (1) (1982) 140-145.
  * [6] J.A. Bondy, Pancyclic graphs I, Journal Combinatorial Theory Ser. B 11 (1971) 80-84.
  * [7] J.A. Bondy, C. Thomassen, A short proof of Meyniel’s theorem, Discrete Mathematics, 19 (1) (977) 195-197.
  * [8] S.Kh. Darbinyan, Pancyclicity of digraphs with the Meyniel condition, Studia Scientiarum Mathematicarum Hungarica, 20 (1-4) (1985) 95-117) (Ph. D. Thesis, Institute Mathematici Akademy Nauk BSSR, Minsk, 1981). (in Russian).
  * [9] S.Kh. Darbinyan, A sufficient condition for the Hamiltonian property of digraphs with large semidegrees, Akademy Nauk Armyan. SSR Doklady, 82 (1) (1986) 6-8 (see also arXiv: 1111.1843v1 [math.CO] 8 Nov 2011).
  * [10] S.Kh. Darbinyan, On the pancyclicity of digraphs with large semidegrees, Akademy Nauk Armyan. SSR Doklady, 83 (4) (1986) 99-101 (see also arXiv: 1111.1841v1 [math.CO] 8 Nov 2011).
  * [11] S.Kh. Darbinyan, Sufficient conditions for Hamiltonian cycles in bipartite digraphs, arXiv:1604.08733 [math. CO] 29 Apr 2016.
  * [12] A. Ghouila-Houri, Une condition suffisante d’existence d’un circuit hamiltonien, Comptes Rendus de I’ Academie des Sciences Paris Ser. A-B 25 (1960) 495-497.
  * [13] G. Gutin, A characterization of vertex pancyclic partly oriented $k$-partite tournaments, Vesti Acad. Navuk BSSR Ser. Fiz-mat. Navuk 2 (1989) 41-46.
  * [14] G. Gutin, A characterization of vertex pancyclic and pancyclic ordinary complete multipartite digraphs, Discrete Mathematics, 141 (1995) 153-162.
  * [15] R. Häggkvist, C. Thomassen, On pancyclic digraphs, Journal Combinatorial Theory Ser. B 20 (1), (1976) 20-40.
  * [16] M. Meyniel, Une condition suffisante d’existence d’un circuit hamiltonien dans un graphe oriente, Journal Combinatorial Theory Ser. B 14 (1973) 137-147.
  * [17] C. Thomassen, An Ore-type condition implying a digraph to be pancyclic, Discrete Mathematics, 19 (1) (1977) 85-92.
  * [18] C. Thomassen, Long cycles in digraphs, Proceeding London Mathematical Society, 3 (42) (1981) 231-251.
  * [19] R. Wang, A sufficient conditions for a balanced bipartite digraph to be Hamiltonian, arXiv:1506.07949 [math. CO] 26 Jun 2015.
  * [20] D.R. Woodall, Sufficient conditions for circuits in graphs, Proceeding London Mathematical Society, 24 (1972) 739-755.
  * [21] C.-Q. Zhang, Vertex even-pancylicity in bipartite tournaments, J. Nanjing Univ. Math. Biquaretely 1 (1982) 85-88.


$\displaystyle=\braket{i[\hat{H},\hat{A}]}=\braket{\psi^{\prime}}{i[g\hat{\sigma}^{x},\hat{A}^{\prime}]}{\psi^{\prime}},$
(138)

where $\ket{\psi^{\prime}}=\hat{V}\ket{\psi}$ and
$\hat{A}^{\prime}=\hat{V}\hat{A}\hat{V}^{\dagger}$. Using the above
discussion, we have

$\displaystyle\left|\frac{d\braket{\hat{A}}}{dt}\right|=2\Delta
H^{\prime}\sqrt{\braket{\hat{A}^{\prime
2}}^{\prime}-\sum_{\mu=1,2}\braket{\hat{A}^{\prime},\hat{\lambda}_{\mu}}^{\prime
2}},$ (139)

where $\braket{\cdots}^{\prime}=\braket{\psi^{\prime}}{\cdots}{\psi^{\prime}}$
and

$\displaystyle\Delta H^{\prime 2}=g^{2}(1-\braket{\hat{\sigma}^{x}}^{\prime
2}),$ (140)

$\lambda_{1}=\hat{\mathbb{I}}$, and

$\displaystyle\hat{\lambda}_{2}=\frac{\hat{\sigma}^{x}-\braket{\hat{\sigma}^{x}}^{\prime}}{\sqrt{\braket{(\hat{\sigma}^{x}-\braket{\hat{\sigma}^{x}}^{\prime})^{2}}}}.$
(141)

Now, straightforward calculation leads to $\Delta H^{\prime}=\Delta H$,
$\braket{\hat{A}^{\prime 2}}^{\prime}=\braket{\hat{A}^{2}}$, and
$\braket{\hat{A}^{\prime},\hat{\lambda}_{\mu}}^{\prime}=\braket{\hat{A},\hat{\Lambda}_{\mu}}$.
Then, we find the equality condition in the form of Eq. (136) holds even in
this general case.

##  Appendix D Other bounds based on invariant observables

Here, we discuss two additional applications of our bounds based on invariant
observables in Eq. (27) in the main text, assuming the unitary time evolution
$\frac{d\hat{\rho}(t)}{dt}=-i[\hat{H}(t),\hat{\rho}(t)]$. The first one is to
consider the (instantaneous) energy eigenstates of $\hat{H}(t)$,
$\ket{E_{\alpha}}\>(\alpha=1,2,\cdots)$. We can take

$\displaystyle\hat{\Lambda}_{\mu}=\frac{\ket{E_{\mu}}\bra{E_{\mu}}}{\sqrt{\braket{E_{\mu}}{\hat{\rho}}{E_{\mu}}}},$
(142)

which satisfy the orthonormalization condition. We then have

$\displaystyle\left|\frac{d\braket{\hat{A}}}{dt}\right|\leq\sqrt{\braket{\hat{A}^{2}}-\sum_{\mu}\frac{\braket{E_{\mu}}{\\{\hat{\rho},\hat{A}\\}}{E_{\mu}}^{2}}{4\braket{E_{\mu}}{\hat{\rho}}{E_{\mu}}}}\sqrt{I_{Q}}.$
(143)

Another example is to take the power of $\hat{\rho}\>(=\hat{\rho}(t))$
assuming the mixed state, since $d\braket{\hat{\rho}^{n}}/dt=0$ due to the
conservation of purity. We here consider the simplest case
$\hat{\Lambda}_{1}=\mathbb{\hat{I}}$ and
$\hat{\Lambda}_{2}=({\hat{\rho}}-\braket{{\hat{\rho}}})/\sqrt{\braket{({\hat{\rho}}-\braket{{\hat{\rho}}})^{2}}}$.
In this case, we find

$\displaystyle\left|\frac{d\braket{\hat{A}}}{dt}\right|\leq\Delta
A\sqrt{I_{Q}}\sqrt{1-\phi_{A\rho}^{2}}.$ (144)

##  Appendix E Proof of Eq. (62)

We express the Hamiltonian as

$\displaystyle\hat{H}=h_{I}\hat{\mathbb{I}}+h_{x}\hat{\mathbb{\sigma}}^{x}+h_{y}\hat{\mathbb{\sigma}}^{y}+h_{z}\hat{\mathbb{\sigma}}^{z}.$
(145)

We have

$\displaystyle\Delta
H^{2}=h_{x}^{2}(1-\braket{\hat{\mathbb{\sigma}}^{x}}^{2})+h_{y}^{2}(1-\braket{\hat{\mathbb{\sigma}}^{y}}^{2})+h_{z}^{2}(1-\braket{\hat{\mathbb{\sigma}}^{z}}^{2})$
$\displaystyle-2h_{x}h_{y}\braket{\hat{\mathbb{\sigma}}^{x}}\braket{\hat{\mathbb{\sigma}}^{y}}-2h_{x}h_{z}\braket{\hat{\mathbb{\sigma}}^{x}}\braket{\hat{\mathbb{\sigma}}^{z}}-2h_{z}h_{y}\braket{\hat{\mathbb{\sigma}}^{z}}\braket{\hat{\mathbb{\sigma}}^{y}}$
(146)

and

$\displaystyle\left|\frac{{d}\braket{\hat{\sigma}^{x}}}{{d}t}\right|^{2}$
$\displaystyle=4(h_{y}\braket{\hat{\sigma}^{z}}-h_{z}\braket{\hat{\sigma}^{y}})^{2}$
$\displaystyle\left|\frac{{d}\braket{\hat{\sigma}^{y}}}{{d}t}\right|^{2}$
$\displaystyle=4(h_{x}\braket{\hat{\sigma}^{z}}-h_{z}\braket{\hat{\sigma}^{x}})^{2}$
$\displaystyle\left|\frac{{d}\braket{\hat{\sigma}^{z}}}{{d}t}\right|^{2}$
$\displaystyle=4(h_{y}\braket{\hat{\sigma}^{x}}-h_{x}\braket{\hat{\sigma}^{y}})^{2}.$
(147)

Using
$\braket{\hat{\sigma}^{x}}^{2}+\braket{\hat{\sigma}^{y}}^{2}+\braket{\hat{\sigma}^{z}}^{2}=1$,
we obtain Eq. (62).

##  Appendix F Proof of Eq. (73)

To prove Eq. (73), we first note that

$\displaystyle B_{k}$
$\displaystyle=\left\langle\hat{A}_{k}-\sum_{\mu}\braket{\hat{A}_{k},\hat{\Lambda}_{\mu}}\hat{\Lambda}_{\mu},\hat{L}\right\rangle$
$\displaystyle=\left\langle\hat{A}_{k}-\sum_{\mu}\braket{\hat{A}_{k},\hat{\Lambda}_{\mu}}\hat{\Lambda}_{\mu},\hat{L}_{1}\right\rangle$
$\displaystyle=\left\langle\hat{A}_{k}-\sum_{\mu}\braket{\hat{A}_{k},\hat{\Lambda}_{\mu}}\hat{\Lambda}_{\mu},\hat{L}_{1}-\sum_{\mu}\braket{\hat{L}_{1},\hat{\Lambda}_{\mu}}\hat{\Lambda}_{\mu}\right\rangle$
(148)

for $1\leq k\leq K$.

We next consider $(K+1)$-dimensional vector $\vec{B}^{\prime}$, which is given
by

$\displaystyle\vec{B}^{\prime}=\left(\vec{B},\left\langle\hat{L}_{2}-\sum_{\mu}\braket{\hat{L}_{2},\hat{\Lambda}_{\mu}}\hat{\Lambda}_{\mu},\hat{L}_{1}-\sum_{\mu}\braket{\hat{L}_{1},\hat{\Lambda}_{\mu}}\hat{\Lambda}_{\mu}\right\rangle\right)^{\mathsf{T}}.$
(149)

In a manner similar to Appendix A, we have

$\displaystyle({\vec{B}^{\prime}})^{\mathsf{T}}(D^{\prime})^{-1}\vec{B}^{\prime}\leq\mathcal{F}_{11},$
(150)

where $\mathcal{F}_{zz^{\prime}}$ is given in Eq. (VI.1) and $D^{\prime}$ is
block-diagonalized as

$\displaystyle D^{\prime}=\begin{pmatrix}D&\vec{0}\\\
\vec{0}^{\mathsf{T}}&\mathcal{F}_{22}\\\ \end{pmatrix},$ (151)

where we have used the relation

$\displaystyle 0$
$\displaystyle=\left\langle\hat{A}_{k}-\sum_{\mu}\braket{\hat{A}_{k},\hat{\Lambda}_{\mu}}\hat{\Lambda}_{\mu},\hat{L}_{2}\right\rangle$
$\displaystyle=\left\langle\hat{A}_{k}-\sum_{\mu}\braket{\hat{A}_{k},\hat{\Lambda}_{\mu}}\hat{\Lambda}_{\mu},\hat{L}_{2}-\sum_{\mu}\braket{\hat{L}_{2},\hat{\Lambda}_{\mu}}\hat{\Lambda}_{\mu}\right\rangle.$
(152)

Then we have

$\displaystyle(D^{\prime})^{-1}=\begin{pmatrix}D^{-1}&\vec{0}\\\
\vec{0}^{\mathsf{T}}&\mathcal{F}_{22}^{-1}\\\ \end{pmatrix}.$ (153)

From Eq. (151), we immediately obtain Eq. (73):

$\displaystyle\vec{B}^{\mathsf{T}}D^{-1}\vec{B}\leq\mathcal{F}_{11}-\frac{\mathcal{F}_{12}^{2}}{\mathcal{F}_{22}}=\frac{\mathrm{Det}[\mathcal{F}]}{\mathcal{F}_{22}}.$
(154)

While we have subtracted
$\sum_{\mu}\braket{\hat{L}_{k},\hat{\Lambda}_{\mu}}\hat{\Lambda}_{\mu}$ from
$\hat{L}_{k}$ above, a similar discussion can be made without this
subtraction. In this case, we obtain

$\displaystyle\vec{B}^{\mathsf{T}}D^{-1}\vec{B}\leq\mathcal{I}_{11}-\frac{\mathcal{I}_{12}^{2}}{\mathcal{I}_{22}}=\frac{\mathrm{Det}[\mathcal{I}]}{\mathcal{I}_{22}}.$
(155)

instead.

##  Appendix G Velocity limit for multiple observables based on the local
conservation law of probability

Here, we discuss the detail of the velocity limit for multiple observables
based on the local conservation law of probability.

###  G.1 Derivation of the case for multiple observables

While we can consider both classical and quantum systems, we here use the
quantum description to keep generality. We assume that (invariant) observables
are diagonal in the $i$-basis, i.e.,

$\displaystyle\hat{A}_{k}=\sum_{i}(a_{k})_{i}\ket{i}\bra{i}$ (156)

and

$\displaystyle\hat{\Lambda}_{\nu}=\sum_{i}(\lambda_{\nu})_{i}\ket{i}\bra{i}.$
(157)

We also assume the orthonormalization condition for $\nabla\Lambda_{\nu}$,
instead of $\hat{\Lambda}_{\nu}$. That is,

$\displaystyle\braket{\nabla\Lambda_{\mu},\nabla\Lambda_{\nu}}_{r}=\delta_{\mu\nu}.$
(158)

The proof of the multiple-observable bound is similar to that in Appendix A.
Let us consider the general case with multi-parameters $y_{1},\cdots,y_{Z}$ as
in Appendix A and assume the continuity equation

$\displaystyle\partial_{y_{z}}p_{i}=-\sum_{j(\neq i)}J_{ji}^{z},$ (159)

We first notice that $B_{kz}$ in Eq. (111) is given by

$\displaystyle B_{kz}=\braket{\nabla A_{k},\mathbf{u}_{z}}_{r}$ (160)

with $(\mathbf{u}_{z})_{ij}=J_{ij}^{z}/r_{ij}$. As we assume that invariant
operators satisfy
$\partial_{y_{z}}\braket{\hat{\Lambda}_{\mu}}-\braket{\partial_{y_{z}}{\hat{\Lambda}_{\mu}}}=0$
for all $z$ and $\mu$, we have
$\braket{\nabla\Lambda_{\mu},\mathbf{u}_{z}}_{r}=0$. Then we have

$\displaystyle\sum_{kz}a_{k}b_{z}B_{kz}=\left\langle\sum_{k}a_{k}\left(\nabla
A_{k}-\sum_{\mu}f^{\prime}_{k\mu}\nabla\Lambda_{\mu}\right),\sum_{z}b_{z}\mathbf{u}_{z}\right\rangle_{r}.$
(161)

for real vectors $(a_{1},\cdots,a_{K})$, $(b_{1},\cdots,b_{Z})$, and
$\\{f_{k\mu}^{\prime}\\}$. As in Appendix A, we find that
$f^{\prime}_{k\mu}=\braket{\nabla A_{k},\nabla\Lambda_{\mu}}_{r}$ provides a
tight bound compared with the other choices, so we assume this choice in the
following.

Using the Cauchy-Schwarz inequality, we have

$\displaystyle\sum_{kzk^{\prime}z^{\prime}}a_{k}a_{k^{\prime}}b_{z}b_{z^{\prime}}B_{kz}B_{k^{\prime}z^{\prime}}\leq\sum_{kzk^{\prime}z^{\prime}}a_{k}a_{k^{\prime}}b_{z}b_{z^{\prime}}\mathcal{D}_{kk^{\prime}}\mathcal{U}_{zz^{\prime}},$
(162)

where

$\displaystyle\mathcal{D}_{kk^{\prime}}:=\braket{\nabla A_{k},\nabla
A_{k^{\prime}}}_{r}-\sum_{\mu}\braket{\nabla
A_{k},\nabla\Lambda_{\mu}}_{r}\braket{\nabla\Lambda_{\mu},\nabla
A_{k^{\prime}}}_{r}$ (163)

and

$\displaystyle\mathcal{U}_{zz^{\prime}}:=\braket{\mathbf{u}_{z},\mathbf{u}_{z^{\prime}}}_{r}.$
(164)

Just as in Appendix A, we can show two equivalent matrix inequalities

$\displaystyle B^{\mathsf{T}}\mathcal{D}^{-1}B\preceq\mathcal{U}$ (165)

and

$\displaystyle B\mathcal{U}^{-1}B^{\mathsf{T}}\preceq\mathcal{D}.$ (166)

If we take $Z=1$, (162) indicates

$\displaystyle\vec{B}\vec{B}^{\mathsf{T}}\preceq\mathcal{D}U$ (167)

and

$\displaystyle\vec{B}^{\mathsf{T}}\mathcal{D}^{-1}\vec{B}\leq U,$ (168)

which we have presented in the main text. If we instead consider $K=1$ and
$Z\neq 1$, we have a matrix inequality

$\displaystyle\vec{\mathsf{B}}\vec{\mathsf{B}}^{\mathsf{T}}\preceq\mathcal{U}\left(\braket{\nabla
A,\nabla A}_{r}-\sum_{\mu}\braket{\nabla
A,\nabla{\Lambda}_{\mu}}_{r}^{2}\right)$ (169)

and a scalar inequality

$\displaystyle\vec{\mathsf{B}}^{\mathsf{T}}\mathcal{U}^{-1}\vec{\mathsf{B}}\leq\left(\braket{\nabla
A,\nabla A}_{r}-\sum_{\mu}\braket{\nabla
A,\nabla{\Lambda}_{\mu}}_{r}^{2}\right),$ (170)

where we have assumed that $\mathcal{U}$ has an inverse.

###  G.2 Derivation of Eq. (VII.2) in the main text

We derive Eq. (VII.2) in the main text, assuming the single-particle quantum
system whose Hamiltonian is given in Eq. (94). We take $M=0$, i.e., neglect
the term concerning $\nabla\Lambda_{\mu}$.

We first show that, if $r_{ij}\leq r^{\prime}_{ij}$ for all $i$ and $j$, we
have a matrix inequality $\mathcal{D}\preceq\mathcal{D}^{\prime}$, where
$\mathcal{D}_{kk^{\prime}}:=\braket{\nabla A_{k},\nabla A_{k^{\prime}}}_{r}$
and $\mathcal{D}^{\prime}_{kk^{\prime}}:=\braket{\nabla A_{k},\nabla
A_{k^{\prime}}}_{r^{\prime}}$. Indeed, $\mathcal{D}^{\prime}-\mathcal{D}$ has
matrix elements given by

$\displaystyle\mathcal{D}^{\prime}_{kk^{\prime}}-\mathcal{D}_{kk^{\prime}}=\braket{\nabla
A_{k},\nabla A_{k^{\prime}}}_{r^{\prime}-r},$ (171)

which is positive semidefinite. Thus, $\mathcal{D}\preceq\mathcal{D}^{\prime}$
holds, and then

$\displaystyle\vec{B}^{\mathsf{T}}\mathcal{D^{\prime}}^{-1}\vec{B}\leq\vec{B}^{\mathsf{T}}\mathcal{D}^{-1}\vec{B}\leq
U.$ (172)

We now take

$\displaystyle r_{ij}=|H_{ij}\rho_{ji}|\leq
r^{\prime}_{ij}=|H_{ij}|\frac{p_{i}+p_{j}}{2}$ (173)

with $H_{ij}=J_{h}(\delta_{i,j+1}+\delta_{i,j-1})$. In this case,

$\displaystyle{\mathcal{D}^{\prime}}_{kk^{\prime}}:=$ $\displaystyle
J_{h}\sum_{i}\frac{p_{i}}{2}\left((\nabla A_{k})_{i,i+1}(\nabla
A_{k^{\prime}})_{i,i+1}+(\nabla A_{k})_{i,i-1}(\nabla
A_{k^{\prime}})_{i,i-1}\right),$ (174)

where we neglect the boundary contribution, assuming that $p_{i}$ becomes
vanishing for $i\rightarrow\pm\infty$.

For $K=2$, we especially have

$\displaystyle\frac{\mathcal{D}^{\prime}_{22}|\frac{{d}\braket{\hat{A}_{1}}}{{d}t}|^{2}-2\mathcal{D}^{\prime}_{12}\frac{{d}\braket{\hat{A}_{1}}}{{d}t}\frac{{d}\braket{\hat{A}_{2}}}{{d}t}+\mathcal{D}^{\prime}_{11}|\frac{{d}\braket{\hat{A}_{2}}}{{d}t}|^{2}}{\mathcal{D}^{\prime}_{11}\mathcal{D}^{\prime}_{22}-|\mathcal{D}^{\prime}_{12}|^{2}}\leq
U,$ (175)

where $U\leq 2C_{H}-2E_{\mathrm{trans}}^{2}/C_{H}$ (see (90)). Noting that
$C_{H}=2J_{h}$ and introducing $\mathcal{C}=\mathcal{D}^{\prime}/J_{h}$, we
have

$\displaystyle\frac{\mathcal{C}_{22}|\frac{{d}\braket{\hat{A}_{1}}}{{d}t}|^{2}-2\mathcal{C}_{12}\frac{{d}\braket{\hat{A}_{1}}}{{d}t}\frac{{d}\braket{\hat{A}_{2}}}{{d}t}+\mathcal{C}_{11}|\frac{{d}\braket{\hat{A}_{2}}}{{d}t}|^{2}}{\mathcal{C}_{11}\mathcal{C}_{22}-|\mathcal{C}_{12}|^{2}}\leq
4J_{h}U.$ (176)

Finally, straightforward calculation leads to Eq. (VII.2) in the main text:

$\displaystyle|\mathcal{V}_{1}-\tilde{\chi}\mathcal{V}_{2}|$
$\displaystyle\leq\sqrt{(1-\tilde{\chi}^{2})(4J_{h}U-\mathcal{V}_{2}^{2})}$
$\displaystyle\leq\sqrt{(1-\tilde{\chi}^{2})(4J_{h}^{2}-E_{\mathrm{trans}}^{2}-\mathcal{V}_{2}^{2})},$
(177)

where
$\mathcal{V}_{k}:=\frac{{d}\braket{\hat{A}_{k}}}{{d}t}/\sqrt{\mathcal{C}_{kk}}$,
and
$\tilde{\chi}:=\mathcal{C}_{12}/\sqrt{\mathcal{C}_{11}\mathcal{C}_{22}}\leq
1$.

As an example, let us consider the position operator
$\hat{A}_{1}=\hat{x}=\sum_{i}i\ket{i}\bra{i}$ and the imbalance operator for
odd-even density, $\hat{s}=\sum_{i}(4\lfloor i/2\rfloor-2i+1)\ket{i}\bra{i}$.
We then have

$\displaystyle(\nabla x)_{i,i+1}=1,\quad(\nabla s)_{i,i+1}=-2(-1)^{i},$ (178)

and $\mathcal{C}_{11}=1,\mathcal{C}_{12}=\mathcal{C}_{21}=0$, and
$\mathcal{C}_{22}=4$. Thus, $\tilde{\chi}=0$ and we have

$\displaystyle|\partial_{t}\braket{\hat{x}}|^{2}+\frac{|\partial_{t}\braket{\hat{s}}|^{2}}{4}\leq
4J_{h}^{2}-E_{\mathrm{trans}}^{2}.$ (179)

## References

  * Callen [1998] H. B. Callen, Thermodynamics and an introduction to thermostatistics (1998).
  * Mazur [1969] P. Mazur, Non-ergodicity of phase functions in certain systems, Physica 43, 533 (1969).
  * Suzuki [1971] M. Suzuki, Ergodicity, constants of motion, and bounds for susceptibilities, Physica 51, 277 (1971).
  * Zotos  _et al._ [1997] X. Zotos, F. Naef, and P. Prelovsek, Transport and conservation laws, Phys. Rev. B 55, 11029 (1997).
  * Rigol  _et al._ [2007] M. Rigol, V. Dunjko, V. Yurovsky, and M. Olshanii, Relaxation in a completely integrable many-body quantum system: An ab initio study of the dynamics of the highly excited states of 1d lattice hard-core bosons, Phys. Rev. Lett. 98, 050405 (2007).
  * Barato and Seifert [2015] A. C. Barato and U. Seifert, Thermodynamic uncertainty relation for biomolecular processes, Phys. Rev. Lett. 114, 158101 (2015).
  * Gingrich  _et al._ [2016] T. R. Gingrich, J. M. Horowitz, N. Perunov, and J. L. England, Dissipation bounds all steady-state current fluctuations, Phys. Rev. Lett. 116, 120601 (2016).
  * Horowitz and Gingrich [2020] J. M. Horowitz and T. R. Gingrich, Thermodynamic uncertainty relations constrain non-equilibrium fluctuations, Nature Physics 16, 15 (2020).
  * Dechant [2018] A. Dechant, Multidimensional thermodynamic uncertainty relations, Journal of Physics A: Mathematical and Theoretical 52, 035001 (2018).
  * Dechant and Sasa [2021] A. Dechant and S.-i. Sasa, Improving thermodynamic bounds using correlations, Phys. Rev. X 11, 041061 (2021).
  * Mandelstam and Tamm [1945] L. Mandelstam and I. Tamm, The energy–time uncertainty relation in non-relativistic quantum mechanics, J. Phys. 9, 249 (1945).
  * Fleming [1973] G. N. Fleming, A unitarity bound on the evolution of nonstationary states, Il Nuovo Cimento A (1965-1970) 16, 232 (1973).
  * Bhattacharyya [1983] K. Bhattacharyya, Quantum decay and the mandelstam-tamm-energy inequality, Journal of Physics A: Mathematical and General 16, 2993 (1983).
  * Anandan and Aharonov [1990] J. Anandan and Y. Aharonov, Geometry of quantum evolution, Phys. Rev. Lett. 65, 1697 (1990).
  * Pfeifer [1993] P. Pfeifer, How fast can a quantum state change with time?, Phys. Rev. Lett. 70, 3365 (1993).
  * Margolus and Levitin [1998] N. Margolus and L. B. Levitin, The maximum speed of dynamical evolution, Physica D: Nonlinear Phenomena 120, 188 (1998).
  * Giovannetti  _et al._ [2003] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum limits to dynamical evolution, Phys. Rev. A 67, 052109 (2003).
  * Levitin and Toffoli [2009] L. B. Levitin and T. Toffoli, Fundamental limit on the rate of quantum dynamics: The unified bound is tight, Phys. Rev. Lett. 103, 160502 (2009).
  * Mondal  _et al._ [2016] D. Mondal, C. Datta, and S. Sazim, Quantum coherence sets the quantum speed limit for mixed states, Physics Letters A 380, 689 (2016).
  * Marvian  _et al._ [2016] I. Marvian, R. W. Spekkens, and P. Zanardi, Quantum speed limits, coherence, and asymmetry, Phys. Rev. A 93, 052331 (2016).
  * Campaioli  _et al._ [2018] F. Campaioli, F. A. Pollock, F. C. Binder, and K. Modi, Tightening quantum speed limits for almost all states, Phys. Rev. Lett. 120, 060409 (2018).
  * Il’in and Lychkovskiy [2021] N. Il’in and O. Lychkovskiy, Quantum speed limit for thermal states, Phys. Rev. A 103, 062204 (2021).
  * Ness  _et al._ [2022] G. Ness, A. Alberti, and Y. Sagi, Quantum speed limit for states with a bounded energy spectrum, Phys. Rev. Lett. 129, 140403 (2022).
  * O’Connor  _et al._ [2021] E. O’Connor, G. Guarnieri, and S. Campbell, Action quantum speed limits, Phys. Rev. A 103, 022210 (2021).
  * Deffner and Campbell [2017] S. Deffner and S. Campbell, Quantum speed limits: from heisenberg’s uncertainty principle to optimal quantum control, Journal of Physics A: Mathematical and Theoretical 50, 453001 (2017).
  * Gong and Hamazaki [2022] Z. Gong and R. Hamazaki, Bounds in nonequilibrium quantum dynamics, International Journal of Modern Physics B 36, 2230007 (2022).
  * Bason  _et al._ [2012] M. G. Bason, M. Viteau, N. Malossi, P. Huillery, E. Arimondo, D. Ciampini, R. Fazio, V. Giovannetti, R. Mannella, and O. Morsch, High-fidelity quantum driving, Nature Physics 8, 147 (2012).
  * Lam  _et al._ [2021] M. R. Lam, N. Peter, T. Groh, W. Alt, C. Robens, D. Meschede, A. Negretti, S. Montangero, T. Calarco, and A. Alberti, Demonstration of quantum brachistochrones between distant states of an atom, Phys. Rev. X 11, 011035 (2021).
  * Ness  _et al._ [2021] G. Ness, M. R. Lam, W. Alt, D. Meschede, Y. Sagi, and A. Alberti, Observing crossover between quantum speed limits, Science advances 7, eabj9119 (2021).
  * Taddei  _et al._ [2013] M. M. Taddei, B. M. Escher, L. Davidovich, and R. L. de Matos Filho, Quantum speed limit for physical processes, Phys. Rev. Lett. 110, 050402 (2013).
  * Deffner and Lutz [2013a] S. Deffner and E. Lutz, Quantum speed limit for non-markovian dynamics, Phys. Rev. Lett. 111, 010402 (2013a).
  * del Campo  _et al._ [2013] A. del Campo, I. L. Egusquiza, M. B. Plenio, and S. F. Huelga, Quantum speed limits in open system dynamics, Phys. Rev. Lett. 110, 050403 (2013).
  * Xu  _et al._ [2014] Z.-Y. Xu, S. Luo, W. L. Yang, C. Liu, and S. Zhu, Quantum speedup in a memory environment, Phys. Rev. A 89, 012307 (2014).
  * Zhang  _et al._ [2014] Y.-J. Zhang, W. Han, Y.-J. Xia, J.-P. Cao, and H. Fan, Quantum speed limit for arbitrary initial states, Scientific reports 4, 1 (2014).
  * Mirkin  _et al._ [2016] N. Mirkin, F. Toscano, and D. A. Wisniacki, Quantum-speed-limit bounds in an open quantum evolution, Phys. Rev. A 94, 052125 (2016).
  * Funo  _et al._ [2019] K. Funo, N. Shiraishi, and K. Saito, Speed limit for open quantum systems, New Journal of Physics 21, 013006 (2019).
  * Okuyama and Ohzeki [2018] M. Okuyama and M. Ohzeki, Quantum speed limit is not quantum, Phys. Rev. Lett. 120, 070402 (2018).
  * Shanahan  _et al._ [2018] B. Shanahan, A. Chenu, N. Margolus, and A. del Campo, Quantum speed limits across the quantum-to-classical transition, Phys. Rev. Lett. 120, 070401 (2018).
  * Ito [2018] S. Ito, Stochastic thermodynamic interpretation of information geometry, Phys. Rev. Lett. 121, 030605 (2018).
  * Ito and Dechant [2020] S. Ito and A. Dechant, Stochastic time evolution, information geometry, and the cramér-rao bound, Phys. Rev. X 10, 021056 (2020).
  * Nicholson  _et al._ [2020] S. B. Nicholson, L. P. Garcia-Pintos, A. del Campo, and J. R. Green, Time–information uncertainty relations in thermodynamics, Nature Physics 16, 1211 (2020).
  * Shiraishi  _et al._ [2018] N. Shiraishi, K. Funo, and K. Saito, Speed limit for classical stochastic processes, Phys. Rev. Lett. 121, 070601 (2018).
  * Falasco and Esposito [2020] G. Falasco and M. Esposito, Dissipation-time uncertainty relation, Phys. Rev. Lett. 125, 120604 (2020).
  * Adachi  _et al._ [2022] K. Adachi, R. Iritani, and R. Hamazaki, Universal constraint on nonlinear population dynamics, Communications Physics 5, 129 (2022).
  * García-Pintos [2022] L. P. García-Pintos, Diversity and fitness uncertainty allow for faster evolutionary rates, arXiv preprint arXiv:2202.07533 (2022).
  * Hoshino  _et al._ [2022] M. Hoshino, R. Nagayama, K. Yoshimura, J. F. Yamagishi, and S. Ito, A geometric speed limit for acceleration by natural selection in evolutionary processes, arXiv preprint arXiv:2207.04640 (2022).
  * Uhlmann [1992] A. Uhlmann, An energy dispersion estimate, Physics Letters A 161, 329 (1992).
  * Jones and Kok [2010] P. J. Jones and P. Kok, Geometric derivation of the quantum speed limit, Phys. Rev. A 82, 022107 (2010).
  * Deffner and Lutz [2013b] S. Deffner and E. Lutz, Energy–time uncertainty relation for driven quantum systems, Journal of Physics A: Mathematical and Theoretical 46, 335302 (2013b).
  * Pires  _et al._ [2015] D. P. Pires, L. C. Céleri, and D. O. Soares-Pinto, Geometric lower bound for a quantum coherence measure, Phys. Rev. A 91, 042330 (2015).
  * Pires  _et al._ [2016] D. P. Pires, M. Cianciaruso, L. C. Céleri, G. Adesso, and D. O. Soares-Pinto, Generalized geometric quantum speed limits, Phys. Rev. X 6, 021031 (2016).
  * García-Pintos  _et al._ [2022] L. P. García-Pintos, S. B. Nicholson, J. R. Green, A. del Campo, and A. V. Gorshkov, Unifying quantum and classical speed limits on observables, Phys. Rev. X 12, 011038 (2022).
  * Dechant and Sasa [2018a] A. Dechant and S.-i. Sasa, Entropic bounds on currents in langevin systems, Phys. Rev. E 97, 062101 (2018a).
  * Van Vu and Hasegawa [2021] T. Van Vu and Y. Hasegawa, Geometrical bounds of the irreversibility in markovian systems, Phys. Rev. Lett. 126, 010601 (2021).
  * Nakazato and Ito [2021] M. Nakazato and S. Ito, Geometrical aspects of entropy production in stochastic thermodynamics based on wasserstein distance, Phys. Rev. Res. 3, 043093 (2021).
  * Dechant  _et al._ [2022] A. Dechant, S.-i. Sasa, and S. Ito, Geometric decomposition of entropy production in out-of-equilibrium systems, Phys. Rev. Res. 4, L012034 (2022).
  * Dechant [2022] A. Dechant, Minimum entropy production, detailed balance and wasserstein distance for continuous-time markov processes, Journal of Physics A: Mathematical and Theoretical 55, 094001 (2022).
  * Hamazaki [2022] R. Hamazaki, Speed limits for macroscopic transitions, PRX Quantum 3, 020319 (2022).
  * Van Vu and Saito [2023a] T. Van Vu and K. Saito, Thermodynamic unification of optimal transport: Thermodynamic uncertainty relation, minimum dissipation, and thermodynamic speed limits, Phys. Rev. X 13, 011013 (2023a).
  * Yoshimura  _et al._ [2023] K. Yoshimura, A. Kolchinsky, A. Dechant, and S. Ito, Housekeeping and excess entropy production for general nonlinear dynamics, Phys. Rev. Res. 5, 013017 (2023).
  * Van Vu and Saito [2023b] T. Van Vu and K. Saito, Topological speed limit, Phys. Rev. Lett. 130, 010402 (2023b).
  * Yung [2006] M.-H. Yung, Quantum speed limit for perfect state transfer in one dimension, Phys. Rev. A 74, 030303(R) (2006).
  * Caneva  _et al._ [2009] T. Caneva, M. Murphy, T. Calarco, R. Fazio, S. Montangero, V. Giovannetti, and G. E. Santoro, Optimal control at the quantum speed limit, Phys. Rev. Lett. 103, 240501 (2009).
  * Murphy  _et al._ [2010] M. Murphy, S. Montangero, V. Giovannetti, and T. Calarco, Communication at the quantum speed limit along a spin chain, Phys. Rev. A 82, 022318 (2010).
  * Ashhab  _et al._ [2012] S. Ashhab, P. C. de Groot, and F. Nori, Speed limits for quantum gates in multiqubit systems, Phys. Rev. A 85, 052327 (2012).
  * Bukov  _et al._ [2019] M. Bukov, D. Sels, and A. Polkovnikov, Geometric speed limit of accessible many-body state preparation, Phys. Rev. X 9, 011034 (2019).
  * Campbell and Deffner [2017] S. Campbell and S. Deffner, Trade-off between speed and cost in shortcuts to adiabaticity, Phys. Rev. Lett. 118, 100601 (2017).
  * Funo  _et al._ [2017] K. Funo, J.-N. Zhang, C. Chatou, K. Kim, M. Ueda, and A. del Campo, Universal work fluctuations during shortcuts to adiabaticity by counterdiabatic driving, Phys. Rev. Lett. 118, 100602 (2017).
  * Giovannetti  _et al._ [2001] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum-enhanced positioning and clock synchronization, Nature 412, 417 (2001).
  * Giovannetti  _et al._ [2004] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum-enhanced measurements: beating the standard quantum limit, Science 306, 1330 (2004).
  * Tóth and Apellaniz [2014] G. Tóth and I. Apellaniz, Quantum metrology from a quantum information science perspective, Journal of Physics A: Mathematical and Theoretical 47, 424006 (2014).
  * Mohan and Pati [2022] B. Mohan and A. K. Pati, Quantum speed limits for observables, Phys. Rev. A 106, 042436 (2022).
  * Shiraishi and Saito [2021] N. Shiraishi and K. Saito, Speed limit for open systems coupled to general environments, Phys. Rev. Res. 3, 023074 (2021).
  * Das and Green [2023] S. Das and J. R. Green, Speed limits on deterministic chaos and dissipation, Phys. Rev. Res. 5, L012016 (2023).
  * Gorini  _et al._ [1976] V. Gorini, A. Kossakowski, and E. C. G. Sudarshan, Completely positive dynamical semigroups of n-level systems, Journal of Mathematical Physics 17, 821 (1976).
  * Lindblad [1976] G. Lindblad, On the generators of quantum dynamical semigroups, Communications in Mathematical Physics 48, 119 (1976).
  * Liu  _et al._ [2019] J. Liu, H. Yuan, X.-M. Lu, and X. Wang, Quantum fisher information matrix and multiparameter estimation, Journal of Physics A: Mathematical and Theoretical 53, 023001 (2019).
  * Note [1] If $D$ has $\bar{K}$ zero eigenvalues, we can construct a projection operator $\hat{\mathcal{P}}$ to the subspace with no zero eigenvalues. From the matrix inequality in Eq. (10), we have $\hat{\mathcal{P}}\vec{B}\vec{B}^{\mathsf{T}}\hat{\mathcal{P}}\preceq\hat{\mathcal{P}}D\hat{\mathcal{P}}$. When we regard $\hat{\mathcal{P}}D\hat{\mathcal{P}}$ as a $(K-\bar{K})\times(K-\bar{K})$ matrix, it is positive-definite and has an inverse. Then, Eq. (12) holds true by replacing $D$ with $\hat{\mathcal{P}}D\hat{\mathcal{P}}$.
  * Tsang  _et al._ [2020] M. Tsang, F. Albarelli, and A. Datta, Quantum semiparametric estimation, Phys. Rev. X 10, 031023 (2020).
  * Mierzejewski and Vidmar [2020] M. Mierzejewski and L. Vidmar, Quantitative impact of integrals of motion on the eigenstate thermalization hypothesis, Phys. Rev. Lett. 124, 040603 (2020).
  * Schrödinger [1999] E. Schrödinger, About heisenberg uncertainty relation, arXiv preprint quant-ph/9903100 (1999).
  * Nicholson and Green [2021] S. B. Nicholson and J. R. Green, Thermodynamic speed limits from the regression of information, arXiv preprint arXiv:2105.01588 (2021).
  * Note [2] Strictly speaking, operators can anti-commute $\\{\hat{A}_{k},\hat{A}_{l}\\}=0\tmspace+{.2222em}(k\neq l)$ even for the classical case, where they also commute $[\hat{A}_{k},\hat{A}_{l}]=0$. However, such operators are limited to the trivial ones satisfying $\hat{A}_{k}\hat{A}_{l}=\hat{A}_{l}\hat{A}_{k}=0\tmspace+{.2222em}(k\neq l)$. In that case, each operator $\hat{A}_{k}$ should act on the different Hilbert subspace $\mathcal{H}_{k}$, where we perform the orthogonal decomposition of the total Hilbert space as $\mathcal{H}=\bigoplus@\slimits@_{k}\mathcal{H}_{k}$. In stark contrast, by allowing non-commutativity, anti-commutation relation holds for more nontrivial sets of operators, which act on the same Hilbert space without the orthogonal decomposition.
  * Maldacena and Stanford [2016] J. Maldacena and D. Stanford, Remarks on the sachdev-ye-kitaev model, Phys. Rev. D 94, 106002 (2016).
  * Hasegawa [2023] Y. Hasegawa, Thermodynamic correlation inequality, arXiv preprint arXiv:2301.03060 (2023).
  * Nielsen and Chuang [2002] M. A. Nielsen and I. Chuang, Quantum computation and quantum information (2002).
  * Note [3] Indeed, observables should be diagonal with respect to the basis of the vertices of the graph, which describes the system.
  * Lieb and Robinson [1972] E. H. Lieb and D. W. Robinson, The finite group velocity of quantum spin systems, in  _Statistical mechanics_ (Springer, 1972) pp. 425–431.
  * Nachtergaele and Sims [2006] B. Nachtergaele and R. Sims, Lieb-robinson bounds and the exponential clustering theorem, Communications in mathematical physics 265, 119 (2006).
  * Bravyi  _et al._ [2006] S. Bravyi, M. B. Hastings, and F. Verstraete, Lieb-robinson bounds and the generation of correlations and topological quantum order, Phys. Rev. Lett. 97, 050401 (2006).
  * Lashkari  _et al._ [2013] N. Lashkari, D. Stanford, M. Hastings, T. Osborne, and P. Hayden, Towards the fast scrambling conjecture, Journal of High Energy Physics 2013, 1 (2013).
  * Abanin  _et al._ [2015] D. A. Abanin, W. De Roeck, and F. Huveneers, Exponentially slow heating in periodically driven many-body systems, Phys. Rev. Lett. 115, 256803 (2015).
  * Kuwahara  _et al._ [2016] T. Kuwahara, T. Mori, and K. Saito, Floquet–magnus theory and generic transient dynamics in periodically driven many-body quantum systems, Annals of Physics 367, 96 (2016).
  * Abanin  _et al._ [2017] D. Abanin, W. De Roeck, W. W. Ho, and F. Huveneers, A rigorous theory of many-body prethermalization for periodically driven and closed quantum systems, Communications in Mathematical Physics 354, 809 (2017).
  * Kukuljan  _et al._ [2017] I. Kukuljan, S. Grozdanov, and T. Prosen, Weak quantum chaos, Phys. Rev. B 96, 060301(R) (2017).
  * Gong  _et al._ [2020a] Z. Gong, N. Yoshioka, N. Shibata, and R. Hamazaki, Universal error bound for constrained quantum dynamics, Phys. Rev. Lett. 124, 210606 (2020a).
  * Gong  _et al._ [2020b] Z. Gong, N. Yoshioka, N. Shibata, and R. Hamazaki, Error bounds for constrained dynamics in gapped quantum systems: Rigorous results and generalizations, Phys. Rev. A 101, 052122 (2020b).
  * Villani [2009] C. Villani,  _Optimal transport: old and new_ , Vol. 338 (Springer, 2009).
  * Dalfovo  _et al._ [1999] F. Dalfovo, S. Giorgini, L. P. Pitaevskii, and S. Stringari, Theory of bose-einstein condensation in trapped gases, Rev. Mod. Phys. 71, 463 (1999).
  * Dechant and Sasa [2018b] A. Dechant and S.-i. Sasa, Current fluctuations and transport efficiency for general langevin systems, Journal of Statistical Mechanics: Theory and Experiment 2018, 063209 (2018b).
  * Pandey  _et al._ [2022] V. Pandey, D. Shrimali, B. Mohan, S. Das, and A. K. Pati, Speed limits on correlations in bipartite quantum systems, arXiv preprint arXiv:2207.05645 (2022).
  * Carabba  _et al._ [2022] N. Carabba, N. Hörnedal, and A. del Campo, Quantum speed limits on operator flows and correlation functions, Quantum 6, 884 (2022).
  * Hörnedal  _et al._ [2023] N. Hörnedal, N. Carabba, K. Takahashi, and A. del Campo, Geometric operator quantum speed limit, wegner hamiltonian flow and operator growth, arXiv preprint arXiv:2301.04372 (2023).
  * Hamazaki [2023] R. Hamazaki, Limits to fluctuation dynamics, arXiv preprint arXiv:2309.07301 (2023).
  * Deffner [2020] S. Deffner, Quantum speed limits and the maximal rate of information production, Phys. Rev. Research 2, 013161 (2020).
  * Pires  _et al._ [2021] D. P. Pires, K. Modi, and L. C. Céleri, Bounding generalized relative entropies: Nonasymptotic quantum speed limits, Phys. Rev. E 103, 032105 (2021).
  * Mohan  _et al._ [2022] B. Mohan, S. Das, and A. K. Pati, Quantum speed limits for information and coherence, New Journal of Physics 24, 065003 (2022).
  * Campaioli  _et al._ [2022] F. Campaioli, C.-s. Yu, F. A. Pollock, and K. Modi, Resource speed limits: maximal rate of resource variation, New Journal of Physics 24, 065001 (2022).
  * Pires [2022] D. P. Pires, Unified entropies and quantum speed limits for nonunitary dynamics, Phys. Rev. A 106, 012403 (2022).
  * Pandey  _et al._ [2023] V. Pandey, S. Bhowmick, B. Mohan, U. Sen, _et al._ , Fundamental speed limits on entanglement dynamics of bipartite quantum systems, arXiv preprint arXiv:2303.07415 (2023).
  * Hörnedal  _et al._ [2022] N. Hörnedal, N. Carabba, A. S. Matsoukas-Roubeas, and A. del Campo, Ultimate speed limits to the growth of operator complexity, Communications Physics 5, 207 (2022).
  * Goldstein  _et al._ [2013] S. Goldstein, T. Hara, and H. Tasaki, Time scales in the approach to equilibrium of macroscopic quantum systems, Phys. Rev. Lett. 111, 140401 (2013).
  * Goldstein  _et al._ [2015] S. Goldstein, T. Hara, and H. Tasaki, Extremely quick thermalization in a macroscopic quantum system for a typical nonequilibrium subspace, New Journal of Physics 17, 045002 (2015).
  * Reimann [2016] P. Reimann, Typical fast thermalization processes in closed many-body systems, Nature communications 7, 1 (2016).
  * de Oliveira  _et al._ [2018] T. R. de Oliveira, C. Charalambous, D. Jonathan, M. Lewenstein, and A. Riera, Equilibration time scales in closed many-body quantum systems, New Journal of Physics 20, 033032 (2018).
  * Schiulaz  _et al._ [2019] M. Schiulaz, E. J. Torres-Herrera, and L. F. Santos, Thouless and relaxation time scales in many-body quantum systems, Phys. Rev. B 99, 174313 (2019).
  * García-Pintos  _et al._ [2017] L. P. García-Pintos, N. Linden, A. S. L. Malabarba, A. J. Short, and A. Winter, Equilibration time scales of physically relevant observables, Phys. Rev. X 7, 031027 (2017).
  * Eisert  _et al._ [2015] J. Eisert, M. Friesdorf, and C. Gogolin, Quantum many-body systems out of equilibrium, Nature Physics 11, 124 (2015).
  * Albarelli and Demkowicz-Dobrzański [2022] F. Albarelli and R. Demkowicz-Dobrzański, Probe incompatibility in multiparameter noisy quantum metrology, Phys. Rev. X 12, 011039 (2022).
  * Weinberg and Bukov [2017] P. Weinberg and M. Bukov, QuSpin: a Python Package for Dynamics and Exact Diagonalisation of Quantum Many Body Systems part I: spin chains, SciPost Phys. 2, 003 (2017).
  * Weinberg and Bukov [2019] P. Weinberg and M. Bukov, Quspin: a python package for dynamics and exact diagonalisation of quantum many body systems. part ii: bosons, fermions and higher spins, SciPost Phys 7, 97 (2019).