# Linear Colouring of Binomial Random Graphs

Austin Eide, Paweł Prałat Department of Mathematics, Toronto Metropolitan
University, Toronto, ON, Canada; e-mail<EMAIL_ADDRESS>of
Mathematics, Toronto Metropolitan University, Toronto, ON, Canada; e-mail:
<EMAIL_ADDRESS>
###### Abstract

We investigate the linear chromatic number
$\chi_{\text{lin}}(\mathcal{G}(n,p))$ of the binomial random graph
$\mathcal{G}(n,p)$ on $n$ vertices in which each edge appears independently
with probability $p=p(n)$. For dense random graphs ($np\to\infty$ as
$n\to\infty$), we show that asymptotically almost surely
$\chi_{\text{lin}}(\mathcal{G}(n,p))\geq n(1-O((np)^{-1/2}))=n(1-o(1))$.
Understanding the order of the linear chromatic number for subcritical random
graphs ($np<1$) and critical ones ($np=1$) is relatively easy. However,
supercritical sparse random graphs ($np=c$ for some constant $c>1$) remain to
be investigated.

##  1 Introduction

Let $G=(V,E)$ be a graph and let $\phi:V\to\\{1,\dots,k\\}$ be an assignment
of $k$ colours to the vertices of $G$. We say that $\phi$ is a proper
$k$-colouring if for each $\\{v,w\\}\in E$, $\phi(v)\neq\phi(w)$. The
chromatic number of $G$, denoted $\chi(G)$, is the smallest positive integer
$k$ such that a proper $k$-colouring of $G$ exists.

Given a colouring $\phi$ and subset $S\subseteq V$, we say that a vertex $v\in
S$ is a centre for $S$ if $\phi(v)$ is distinct from $\phi(w)$ for all $w\neq
v$ in $S$. A centred $k$-colouring of $G$ is a $k$-colouring of $G$ such that
for every connected subgraph $H\subseteq G$, $V(H)$ has a centre. The centred
chromatic number $\chi_{\text{cen}}(G)$ is the smallest $k$ such that a
centred $k$-colouring of $G$ exists. Observe that a centred colouring is
necessarily proper, since each edge $\\{v,w\\}\in E$ comprises a connected
subgraph of $G$. Hence we have the inequality
$\chi(G)\leq\chi_{\text{cen}}(G)$.

The centred chromatic number is an important and natural graph parameter that
has been introduced under numerous names in the literature: rank function
[21], vertex ranking number (or ordered colouring) [8], weak colouring number
[12]. Its study was systematically undertaken by Nešetřil and Ossona de Mendez
under the name of _tree-depth_ [18]. The notion of tree-depth is related to
the one of tree-width. The tree-width of a graph can be seen as a measure of
closeness to a tree, while the tree-depth takes also into account the diameter
of the tree. Both serve as important measures of sparsity of a graph [19, 20].

A linear $k$-colouring of $G$ is a $k$-colouring such that every subgraph of
$G$ that is a path has a centre. The corresponding linear chromatic number
$\chi_{\text{lin}}(G)$ is defined in the obvious way. A linear colouring is
necessarily proper, as each edge $\\{v,w\\}\in E$ is a path of length one. On
the other hand, a centred colouring is necessarily linear, since path
subgraphs are connected. Therefore, we have
$\chi(G)\leq\chi_{\text{lin}}(G)\leq\chi_{\text{cen}}(G)$. (In other works,
e.g., [27], the term linear colouring has been used to refer to proper
colourings with the property that the subgraph induced any pair of colour
classes is a disjoint union of paths. This is distinct from the meaning here.)

The linear chromatic number was introduced by Kun, O’Brien, Pilipczuk, and
Sulivan [15] who were motivated by finding efficiently-computable
approximations of tree-depth in the class of bounded expansion graphs. The
authors of [15] provide a family of graphs that contains, for every
$\epsilon>0$, a graph $G$ with
$\chi_{\text{cen}}(G)>(2-\epsilon)\chi_{\text{lin}}(G)$ and based on that they
stated the following, quite bold, conjecture:

######  Conjecture 1.1 ([15]).

For all graphs $G$, $\chi_{\text{cen}}(G)\leq 2\chi_{\text{lin}}(G)$.

We are far away from proving this conjecture. The only class of graphs for
which centred chromatic number is known to be bounded by a linear function of
linear chromatic number is the class of bounded degree trees [15, Theorem 4].
Currently the best upper bound is proved by Bose, Dujmović, Houdrouge,
Javarsineh, and Morin [5] who were able to prove that

$\chi_{\text{cen}}(G)\leq\chi_{\text{lin}}(G)^{10}\Big{(}\log(\chi_{\text{lin}}(G))\Big{)}^{O(1)}.$

This result improved the bound proved by Czerwiński, Nadara, and Pilipczuk [6]
(they reduced the exponent from 190 to 19) which, in turn, improved the
original bound by Kun at al. [15] (with exponent 190). Bose at al. [5] provide
further evidence in support of the conjecture by establishing that, if $G$ is
a $k\times k$ pseudo-grid, then
$\chi_{\text{cen}}(G)=O(\chi_{\text{lin}}(G))$.

In this paper, we investigate the binomial random graph $\mathcal{G}(n,p)$
that is formally defined as a distribution over the class of graphs with the
set of nodes $[n]:=\\{1,\ldots,n\\}$ in which every pair
$\\{i,j\\}\in\binom{[n]}{2}$ appears independently as an edge in $G$ with
probability $p$. Note that $p=p(n)$ may (and usually does) tend to zero as $n$
tends to infinity. Most results in this area are asymptotic by nature. We say
that $\mathcal{G}(n,p)$ has some property _asymptotically almost surely_ (or
_a.a.s._) if the probability that $\mathcal{G}(n,p)$ has this property tends
to $1$ as $n$ goes to infinity. For more about this model see, for example,
[4, 11, 10].

The binomial random graph $\mathcal{G}(n,p)$ is notoriously a good candidate
for constructing counterexamples to conjectures that seem to be false,
including the seminal result of Erdős from 1959 [9] that “many consider [to
be] one of the most pleasing uses of the probabilistic method, as the result
is surprising and does not appear to call for nonconstructive techniques” (see
[3]). The _girth_ of a graph is the size of its shortest cycle. Erdős showed
in [9] that for any $k$ and $\ell$ there exists a graph $G$ with girth more
than $\ell$ and $\chi(G)>k$.

Alternatively, one can investigate random graphs to support various
conjectures that seem to be true. In particular, $\mathcal{G}(n,p)$ with
$p=1/2$ yields a uniform distribution of (labeled) graphs on $n$ vertices, so
showing that a given conjecture holds a.a.s. for $\mathcal{G}(n,1/2)$ is
equivalent to proving that almost all graphs satisfy the conjecture. Many open
problems are supported by such statements including the following, clearly
biased, small sample of results of this flavour: Meyniel’s conjecture [24,
25], Tutte’s conjecture [26], and Jaeger’s conjecture [7].

The results presented in this paper for dense binomial random graphs
$\mathcal{G}(n,p)$ (that is, in the regime when $np\to\infty$) support
Conjecture 1.1. Our main theorem is the following.

######  Theorem 1.2.

Let $\omega=\omega(n)\leq n$ be any function that tends to infinity as
$n\to\infty$, and let $p=\omega/n$. Then, the following holds a.a.s.:

$\chi_{\text{lin}}(\mathcal{G}(n,p))\geq n-\frac{510n}{\sqrt{\omega}}.$

In our proofs, we did not try to optimize the constants. Since
$\chi_{\text{lin}}(G)\leq\chi_{\text{cen}}(G)$ and, trivially,
$\chi_{\text{cen}}(G)\leq n$, Theorem 1.2 implies that a.a.s.
$\chi_{\text{lin}}(G(n,p))=(1+o(1))\chi_{\text{cen}}(G(n,p))=(1+o(1))n$. In
particular, we conclude that Conjecture 1.1 holds for almost all graphs.

Supporting Conjecture 1.1 is a nice implication but understanding the
behaviour of the linear chromatic number for $\mathcal{G}(n,p)$ seems to be
interesting on its own. In particular, our result implies the lower bound for
the centred chromatic number of dense binomial random graphs proved in [22],
where it was shown that $\chi_{\text{cen}}(G(n,\omega/n))\geq
n-O\left(n/\sqrt{\omega}\right)$ a.a.s.

Investigating the linear chromatic number for very sparse random graphs,
before the giant component is formed, is relatively easy. Observations from
[22] give us the following.

######  Theorem 1.3.

The following holds a.a.s.:

$\chi_{\text{lin}}(\mathcal{G}(n,c/n))=\begin{cases}\Theta(\log\log
n)\quad&\text{if}\quad c\in(0,1)\\\ \Theta(\log n)\quad&\text{if}\quad
c=1.\end{cases}$

On the other hand, supercritical sparse random graphs (when $p=c/n$ for some
constant $c>1$) remain to be investigated. The proof of our main result,
Theorem 1.2, can be adjusted to show that a.a.s.
$\chi_{\text{lin}}(\mathcal{G}(n,c/n))=\Theta(n)$, provided that $c$ is large
enough. However, there seems to be no hope to apply the current argument to
prove it for any $c>1$. Maybe a.a.s.
$\chi_{\text{lin}}(\mathcal{G}(n,c/n))=o(n)$ for some $c>1$? That would show
that Conjecture 1.1 is false, since a.a.s.
$\chi_{\text{cen}}(\mathcal{G}(n,c/n))=\Theta(n)$ for any $c>1$.

The paper is structured as follows. We first provide a high level sketch of
the proof of the main theorem, Theorem 1.2 (see Subsection 1.1). Section 2 is
devoted to the proof of Theorem 1.2. Observations that prove Theorem 1.3 can
be found in Section 3.

###  1.1 Sketch of the Proof of Theorem 1.2

The starting point of the proof is an idea from the paper of Alon, McDiarmid,
and Reed [2] on acyclic colourings. Let $x=x(n)\in(0,1)$ and consider any
colouring of the vertices of $\mathcal{G}(n,p)$ which uses as most $(1-x)n$
colour classes. By removing at most one vertex from each class, we can make
the sizes of all classes even. Since we remove at most $(1-x)n$ vertices, a
set $S$ of size at least $xn$ remains. Vertices in $S$ are necessarily in even
classes and so of size at least $2$. In particular, colours that were
initially present only one time disappeared. Finally, we (arbitrarily) pair
the vertices within each colour class, resulting in at least $xn/2$ pairs of
vertices, where each pair is a subset of a single colour class. Let
$\mathcal{P}$ be the set of pairs formed at this step.

We call a path in $\mathcal{G}(n,p)$ bad if it has no centre, and observe that
any path on vertices from $S$ which visits each pair of $\mathcal{P}$ either
exactly twice or not at all is bad. To show that the coloring we started with
is not linear, we seek a bad path for the pairing $\mathcal{P}$. Maybe in each
pairing $\mathcal{P}$ there is always a short bad path? The answer is ‘no’—it
is relatively easy to construct a large set of pairs with no short bad paths
a.a.s. Alternatively, one might simply look for a Hamilton path on the
vertices in $S$. This also turns out to be too much to ask for as, in general,
the subgraph of $\mathcal{G}(n,p)$ induced by the vertices in $S$ may not even
be connected. Indeed, there are many isolated vertices in $\mathcal{G}(n,p)$
for $p$ below the threshold for connectivity $\bar{p}=\log n/n$ so this
subgraph can have many isolated vertices.

However, something slightly weaker turns out to be true. By repeatedly
removing pairs of vertices in $S$ which contain a vertex of small degree until
no such pairs remain, we reach a subset $S^{\prime}\subseteq S$ and a sub-
pairing $\mathcal{P}^{\prime}\subseteq\mathcal{P}$. (This procedure is
reminiscent of the construction of the $k$-core of the subgraph induced by
$S$.) Provided that $x$ is large enough, one can show that, a.a.s., not too
many pairs are removed and that the resulting set $S^{\prime}$ induces a
connected subgraph with good expansion. Using the now-standard rotation-
extension technique of Pósa [23], it can then be shown that this subgraph has
a Hamilton path a.a.s. Since $\mathcal{P}^{\prime}\subseteq\mathcal{P}$, any
such path is bad, and hence the colouring we started with is a.a.s. not
linear.

##  2 Dense Case: $np\to\infty$ (Proof of Theorem 1.2)

We will use the following specific instances of Chernoff’s bound. Let
$X\in\textrm{Bin}(n,p)$ be a random variable distributed according to a
Binomial distribution with parameters $n$ and $p$. Then, a consequence of
_Chernoff’s bound_ (see e.g. [11, Theorem 2.1]) is that for any $t\geq 0$ we
have

$\displaystyle\textsf{Pr}(X\geq\textsf{E}X+t)$ $\displaystyle\leq$
$\displaystyle\exp\left(-\frac{t^{2}}{2(\textsf{E}X+t/3)}\right)$ (1)
$\displaystyle\textsf{Pr}(X\leq\textsf{E}X-t)$ $\displaystyle\leq$
$\displaystyle\exp\left(-\frac{t^{2}}{2\textsf{E}X}\right).$ (2)

We define a set-pairing to be a pair $(S,\mathcal{P})$ where $S\subseteq[n]$
is a set of even size and $\mathcal{P}$ is a set of the form

$\\{\\{v_{1},v_{2}\\},\\{v_{3},v_{4}\\},\dots,\\{v_{|S|-1},v_{|S|}\\}\\}$

where $v_{1},v_{2},\dots,v_{|S|}$ is some ordering of the vertices of $S$.
Given set-pairings $(S,\mathcal{P})$ and $(S^{\prime},\mathcal{P}^{\prime})$,
we say that $(S^{\prime},\mathcal{P}^{\prime})\subseteq(S,\mathcal{P})$ if and
only if $S^{\prime}\subseteq S$ and $\mathcal{P}^{\prime}\subseteq P$.

Throughout this section, $\omega=\omega(n)$ will denote a function of $n$
which grows to infinity arbitrarily slowly and satisfies $\omega\leq n$ so
that $p=\omega/n\leq 1$. Recall that for a graph $G$ on vertex set $[n]$ and
$S\subseteq[n]$, we let $G[S]$ denote the subgraph of $G$ induced by the
vertices in $S.$

Let $(S,\mathcal{P})$ be a set-pairing and let $G$ be a graph on vertex set
$[n]$. For a given $k\geq 0$ we define the $k$-core of $(S,\mathcal{P})$ in
$G$, denoted $C_{k}^{G}(S,\mathcal{P})$ to be the maximal induced subgraph of
$G[S]$ with minimum degree at least $k$ and such that if $v\in
V(C_{k}^{G}(S,\mathcal{P}))$ and $\\{v,w\\}\in\mathcal{P}$, then $w\in
V(C_{k}^{G}(S,\mathcal{P}))$. Note that any maximal subgraph satisfying these
conditions is necessarily unique, else a larger subgraph satisfying the same
conditions could be constructed by taking a union. Thus the definition is
unambiguous (though the $k$-core may be empty). Moreover, to find the $k$-core
of $(S,\mathcal{P})$ one may repeatedly remove vertices of degree less than
$k$ (together with their partners in $\mathcal{P}$) until there is no vertex
of degree less than $k$.

The key feature of $C_{k}^{G}(S,\mathcal{P})$ is that it respects the original
pairing $\mathcal{P}$: for any $\\{v,w\\}\in\mathcal{P}$, either both $v$ and
$w$ are in the $k$-core, or neither of them is. In this subsection, we
establish some properties of $k$-cores of set pairings $(S,\mathcal{P})$ in
the binomial random graph $\mathcal{G}(n,p)$. When the host graph is clear
from context, we simply write $C_{k}(S,\mathcal{P})$.

We will first show that $k$-cores are large (Subsection 2.1) and have good
expansion properties (Subsection 2.2). The results in these two subsections
are adaptations of similar results in [14, Section 3] to the present
application. These observations, combined via sprinkling with the rotation-
extension technique of Pósa, imply that the corresponding $k$-cores have
Hamilton paths (Subsection 2.3).

###  2.1 $k$-cores are Large

Our first lemma shows that, a.a.s., for every set-pairing $(S,\mathcal{P})$
with $|S|\geq cn/\sqrt{\omega}$, the core $C_{|S|p/3}(S,\mathcal{P})$ in
$\mathcal{G}(n,p)$ has at least $|S|/2$ vertices.

######  Lemma 2.1.

Let $p=\omega/n$, $c>0$, and let $G=\mathcal{G}(n,p)$. Then, a.a.s. for every
set-pairing $(S,\mathcal{P})$ with $|S|\geq cn/\sqrt{\omega}$, there exists a
set-pairing $(S^{\prime},\mathcal{P}^{\prime})\subseteq(S,\mathcal{P})$ such
that $|S^{\prime}|\geq|S|/2$ and the subgraph $G[S^{\prime}]$ has minimum
degree at least $|S|p/3$.

###### Proof.

First, fix a set-pairing $(S,\mathcal{P})$ with $|S|\geq
cn/\sqrt{\omega}=\Omega(\sqrt{n})$. We build a sub set-pairing
$(S^{\prime},\mathcal{P}^{\prime})$ using the following simple algorithm. Set
$S_{0}=S$ and $\mathcal{P}_{0}=\mathcal{P}$. For $i=0,1,2,\dots$, if
$G[S_{i}]$ contains a vertex of degree less than $|S|p/3$, then let $v_{i+1}$
be the smallest such vertex, and let $w_{i+1}$ be its partner such that
$\\{v_{i+1},w_{i+1}\\}\in\mathcal{P}_{i}$; set
$S_{i+1}=S_{i}\setminus\\{v_{i+1},w_{i+1}\\}$ and
$\mathcal{P}_{i+1}=P_{i}\setminus\\{\\{v_{i+1},w_{i+1}\\}\\}$. If no vertex of
degree less than $|S|p/3$ exists in $G[S_{i}]$ (which is trivially true if
$S_{i}=\varnothing$), then the algorithm terminates after $i$ steps.

Let $T=T(S,\mathcal{P})$ be the termination time of the algorithm and let
$S^{\prime}=S_{T}$. If $T<|S|/2$, then clearly $G[S^{\prime}]$ is a subgraph
of $\mathcal{G}(n,p)$ on $|S|-2T$ vertices of minimum degree at least
$|S|p/3$. To prove the lemma, we will show that a.a.s.
$T(S,\mathcal{P})\leq|S|/4$ for all set-pairings $(S,\mathcal{P})$ with
$|S|\geq cn/\sqrt{\omega}$.

For each $i\geq 1$, let $B_{i}=\\{v_{1},v_{2},\dots,v_{i}\\}$, where the
$v_{j}$’s are as defined in the algorithm. By construction, we have
$|E(B_{i},S_{i})|<i\cdot|S|p/3$. Suppose that $T>|S|/4$. Then, at step
$t=\left\lfloor|S|/4\right\rfloor$ of the algorithm, we find disjoint sets
$B_{t}$ and $S_{t}$ of sizes $\lfloor|S|/4\rfloor=(1+o(1))|S|/4$ and
$|S|-2\lfloor|S|/4\rfloor=(1+o(1))|S|/2$, respectively, such that

$|E(B_{t},S_{t})|<\left\lfloor\frac{|S|}{4}\right\rfloor\cdot\frac{|S|p}{3}\leq\frac{|S|^{2}\omega}{12n}.$

The preceding shows that for any set-pairing $(S,\mathcal{P})$ with $|S|\geq
cn/\sqrt{\omega}$, the event $\\{T(S,\mathcal{P})>|S|/4\\}$ implies the
existence of a pair of disjoint sets $P,Q\subseteq[n]$ such that
$|P|=\left\lfloor|S|/4\right\rfloor$, $|Q|=|S|-2\lfloor|S|/4\rfloor$, and
$|E(P,Q)|<\frac{|S|^{2}\omega}{12n}$. Thus,

$\textsf{Pr}\left(\bigcup_{(S,\mathcal{P})}\left\\{T(S,\mathcal{P})>\frac{|S|}{4}\right\\}\right)\leq\textsf{Pr}\left(\bigcup_{P,Q}\left\\{|E(P,Q)|<\frac{s^{2}\omega}{12n}\right\\}\right),$
(3)

where the union on the left is taken over all set-pairings with $|S|\geq
cn/\sqrt{\omega}$ and the union on the right is over all disjoint $P,Q$ with
$|P|=\left\lfloor s/4\right\rfloor$, $|Q|=s-2\left\lfloor s/4\right\rfloor$,
and $s\geq cn/\sqrt{\omega}$.

Consider a fixed pair of disjoint sets $P,Q$ of sizes $\lfloor s/4\rfloor$ and
$s-2\lfloor s/4\rfloor$, respectively, for some $s\geq cn/\sqrt{\omega}$. The
cut size $|E(P,Q)|$ is the binomial random variable
$X\sim\textrm{Bin}(|P||Q|,p)$ with mean

$\textsf{E}[X]=|P||Q|p=(1+o(1))\frac{s^{2}\omega}{8n}.$

From Chernoff’s bound (2) applied with
$t=\textsf{E}[X]-\frac{s^{2}\omega}{12n}=(1+o(1))\textsf{E}[X]/3$, we then get

$\displaystyle\textsf{Pr}\left(|E(P,Q)|<\frac{s^{2}\omega}{12n}\right)$
$\displaystyle\leq$
$\displaystyle\exp\left\\{-(1+o(1))\frac{\textsf{E}[X]}{18}\right\\}~{}=~{}\exp\left\\{-(1+o(1))\frac{s^{2}\omega}{144n}\right\\}$
$\displaystyle\leq$
$\displaystyle\exp\left\\{-\frac{s^{2}\omega}{150n}\right\\}~{}\leq~{}\exp\left\\{-\frac{cs\sqrt{\omega}}{150}\right\\},$

where the second equality holds for $n$ sufficiently large, and in the final
equality we use the fact that $s\geq cn/\sqrt{\omega}$. For a given $s$, the
number of choices for the sets $P$ and $Q$ is at most

$\binom{n}{\left\lfloor s/4\right\rfloor}\binom{n}{s-2\left\lfloor
s/4\right\rfloor}\leq
n^{O(1)}\left(\frac{4ne}{s}\right)^{s/4}\left(\frac{2ne}{s}\right)^{s/2}=n^{O(1)}\left(\frac{2^{\frac{4}{3}}ne}{s}\right)^{\frac{3s}{4}}.$

(The $n^{O(1)}$ factor is the price paid for getting rid of ceilings; the
constant implied in the $O(\cdot)$ notation does not depend on $s$.) Using the
fact that $s\geq cn/\sqrt{\omega}$, the right-hand side above is at most

$n^{O(1)}\left(\frac{2^{\frac{4}{3}}\sqrt{\omega}e}{c}\right)^{\frac{3s}{4}}=\exp\left\\{(1+o(1))\frac{3s}{8}\log\omega\right\\}\leq\exp\left\\{\frac{s\log\omega}{2}\right\\}.$

(The inequality holds for $n$ sufficiently large.) Thus, the probability that
there exist disjoint sets $P,Q$ of sizes $\lfloor s/4\rfloor$ and $s-2\lfloor
s/4\rfloor$, respectively, such that $|E(P,Q)|\leq\frac{s^{2}\omega}{12n}$ is
at most

$\exp\left\\{-\frac{cs\sqrt{\omega}}{150}+\frac{s\log\omega}{2}\right\\}=\exp\left\\{-\frac{cs\sqrt{\omega}}{150}\left(1-\frac{75\log\omega}{c\sqrt{\omega}}\right)\right\\}\leq\exp\left\\{-\frac{cs\sqrt{\omega}}{200}\right\\}.$

(As always, the inequality holds for $n$ sufficiently large.) It follows that

$\displaystyle\textsf{Pr}\left(\bigcup_{P,Q}\left\\{|E(P,Q)|\leq\frac{s^{2}\omega}{12n}\right\\}\right)$
$\displaystyle\leq$ $\displaystyle\sum_{s=\lceil
cn/\sqrt{\omega}\rceil}^{n}\exp\left\\{-\frac{cs\sqrt{\omega}}{200}\right\\}$
$\displaystyle\leq$ $\displaystyle ne^{-\Omega(n)}=o(1).$

Based on (3), we conclude that a.a.s. $T(S,\mathcal{P})\leq|S|/4$ for all set-
pairings $(S,\mathcal{P})$ with $|S|\geq cn/\sqrt{\omega}$. This completes the
proof of the lemma. ∎

###  2.2 $k$-cores are Good Expanders

The previous lemma, Lemma 2.1, shows that, a.a.s., for every set-pairing
$(S,\mathcal{P})$ with $|S|\geq 2cn/\sqrt{\omega}$, the core
$C_{|S|p/3}(S,\mathcal{P})$ in $\mathcal{G}(n,p)$ has at least $|S|/2\geq
cn/\sqrt{\omega}$ vertices. By definition, the minimum degree of
$C_{|S|p/3}(S,\mathcal{P})$ is at least
$|S|p/3\geq|V(C_{|S|p/3}(S,\mathcal{P}))|p/3$. Our next lemma implies that
a.a.s. for every set-pairing $(S,\mathcal{P})$ with $|S|\geq
2cn/\sqrt{\omega}$, the core $C_{|S|p/3}(S,\mathcal{P})$ in $\mathcal{G}(n,p)$
is a good expander.

######  Lemma 2.2.

Let $p=\omega/n$ and $c>0$. The following properties hold a.a.s.:

  1. i)

For any subgraph $H$ of $\mathcal{G}(n,p)$ on at least $cn/\sqrt{\omega}$
vertices with $\delta(H)\geq|V(H)|p/3$, we have $|N_{H}(X)\setminus X|>2|X|$
for every $X\subseteq V(H)$ with $|X|\leq|V(H)|/45$.

  2. ii)

Every induced subgraph $H$ of $\mathcal{G}(n,p)$ with $\delta(H)\geq|V(H)|p/3$
on at least $cn/\sqrt{\omega}$ vertices is connected.

###### Proof.

We begin with i). Suppose that there is a subgraph $H$ of $\mathcal{G}(n,p)$
on $s\geq cn/\sqrt{\omega}$ vertices with minimum degree at least $sp/3$ that
fails the expansion condition in the statement. Let $X\subseteq V(H)$ be a
subset of vertices with $|X|\leq s/45$ and such that $|N_{H}(X)\setminus
X|\leq 2|X|.$ Then, $N_{H}(X)\setminus X$ is contained in some $Y\subseteq
V(H)$, disjoint from $X$, with $|Y|=2|X|$. In $H$, there are at most
$\binom{|X|}{2}+|X||Y|\leq\frac{5}{2}|X|^{2}$ possible edges incident with
$X.$ At least

$\frac{\delta(H)|X|}{2}\geq\frac{sp|X|}{6}=\frac{s\omega|X|}{6n}$

of these edges must be present in $H$, and hence also in $\mathcal{G}(n,p)$.
Writing $|X|=j\leq s/45$, the probability that this occurs for a given pair of
sets $X$ and $Y$ is at most

$\binom{\left\lfloor\frac{5}{2}j^{2}\right\rfloor}{\left\lceil\frac{s\omega
j}{6n}\right\rceil}p^{\lceil s\omega
j/6n\rceil}\leq\left(\frac{15ejn}{s\omega}p\right)^{\lceil s\omega
j/6n\rceil}\leq\left(\frac{15ej}{s}\right)^{s\omega j/6n}.$

For $s\geq cn/\sqrt{\omega}$, let $\mathcal{B}_{s}$ be the event that there
exists a subgraph $H$ of $\mathcal{G}(n,p)$ with $s$ vertices and minimum
degree at least $sp/3$ such that the expansion condition in the statement of
the lemma fails. We have

$\displaystyle\textsf{Pr}(\mathcal{B}_{s})$ $\displaystyle\leq$
$\displaystyle\sum_{j=1}^{\lfloor
s/45\rfloor}\binom{n}{j}\binom{n}{2j}\left(\frac{15ej}{s}\right)^{s\omega
j/6n}$ (4) $\displaystyle\leq$ $\displaystyle\sum_{j=1}^{\lfloor
s/45\rfloor}\left[\frac{1}{4}\left(\frac{ne}{j}\right)^{3}\left(\frac{15ej}{s}\right)^{s\omega/6n}\right]^{j}$
$\displaystyle\leq$ $\displaystyle\sum_{j=1}^{\lfloor
s/45\rfloor}\left[\frac{1}{4}\left(\frac{ne}{j}\right)^{3}\left(\frac{15ej}{s}\right)^{c\sqrt{\omega}/6}\right]^{j},$

where in the final inequality we use that $15ej/s<1$ for $j\leq\lfloor
s/45\rfloor$ and that $s\geq cn/\sqrt{\omega}$. We will show that the last sum
above is $o(1/n)$ uniformly in $s$. This will suffice to finish the proof of
part i), since it implies that

$\textsf{Pr}\left(\bigcup_{s=\lceil
cn/\sqrt{\omega}\rceil}^{n}\mathcal{B}_{s}\right)\leq\sum_{s=\lceil
cn/\sqrt{\omega}\rceil}^{n}\textsf{Pr}(\mathcal{B}_{s})=n\cdot o(1/n)=o(1).$

Now, we bound the sum (4). We remark first that, since $\omega\leq n$, we have
$s\geq cn/\sqrt{\omega}=c\sqrt{n}$ and, in particular, $s\gg\log n$. We will
split the sum (4) into two parts corresponding to $j\leq\lfloor\log n\rfloor$
and, respectively, $j>\lfloor\log n\rfloor.$

For $1\leq j\leq\lfloor\log n\rfloor$, we have

$\frac{1}{4}\left(\frac{ne}{j}\right)^{3}\left(\frac{15ej}{s}\right)^{c\sqrt{\omega}/6}\leq\frac{(ne)^{3}}{4}\left(\frac{15e\log
n}{c\sqrt{n}}\right)^{c\sqrt{\omega}/6}=:g(n).$

where in the inequality we use that $1\leq j\leq\log n$ and $s\geq c\sqrt{n}$.
It is easy to see that $g(n)=o(1/n)$, and hence

$\sum_{j=1}^{\lfloor\log
n\rfloor}\left[\frac{1}{4}\left(\frac{ne}{j}\right)^{3}\left(\frac{15ej}{s}\right)^{c\sqrt{\omega}/6}\right]^{j}\leq\sum_{j=1}^{\lfloor\log
n\rfloor}(g(n))^{j}=O(g(n))=o(1/n).$

For $\lfloor\log n\rfloor+1\leq j\leq\left\lfloor\frac{s}{45}\right\rfloor$,
observe that

$\displaystyle\frac{1}{4}\left(\frac{ne}{j}\right)^{3}\left(\frac{15ej}{s}\right)^{c\sqrt{\omega}/6}$
$\displaystyle=$
$\displaystyle\frac{(15e^{2})^{3}}{4}\left(\frac{n}{s}\right)^{3}\left(\frac{15ej}{s}\right)^{c\sqrt{\omega}/6-3}$
$\displaystyle\leq$
$\displaystyle\frac{(15e^{2})^{3}}{4}\left(\frac{\sqrt{\omega}}{c}\right)^{3}\left(\frac{15e}{45}\right)^{c\sqrt{\omega}/6-3}:=h(n).$

Now,
$h(n)=\exp\left\\{O(\log\omega)-\Omega(\sqrt{\omega})\right\\}=\exp\left\\{-\Omega(\sqrt{\omega})\right\\}=o(1)$,
and hence for $n$ large enough, $h(n)<1/3<1/e$ and so we have

$\displaystyle\sum_{j=\lfloor\log n\rfloor+1}^{\lfloor
s/45\rfloor}\left[\frac{1}{4}\left(\frac{ne}{j}\right)^{3}\left(\frac{15ej}{s}\right)^{c\sqrt{\omega}/6}\right]^{j}$
$\displaystyle\leq$ $\displaystyle\sum_{j=\lfloor\log
n\rfloor+1}^{\infty}(h(n))^{j}=O\left((h(n))^{\log n}\right)$ $\displaystyle=$
$\displaystyle O((1/3)^{\log n})=o(1/n).$

Thus, we conclude that for $s\geq cn/\sqrt{\omega}$, the sum (4) is $o(1/n)$,
uniformly in $s$. This completes the proof of part i).

For ii), let $H$ be an induced subgraph on $s\geq cn/\sqrt{\omega}$ vertices
with $\delta(H)\geq|V(H)|p/3$. By part i), we may assume that $H$ does not
have a component with $\frac{s}{45}$ or fewer vertices. If $H$ has more than
one component of size greater than $s/45$, then we find a pair of disjoint
sets of $\left\lceil s/45\right\rceil$ vertices each which induce no edges
between them in $\mathcal{G}(n,p)$. (The assumption that $H$ is induced is
necessary here.) The probability of finding such sets is at most

$\displaystyle\binom{n}{\lceil s/45\rceil}^{2}(1-p)^{\lceil s/45\rceil^{2}}$
$\displaystyle\leq$ $\displaystyle
O(\omega)\left(\frac{45ne}{s}\right)^{2s/45}e^{-s^{2}\omega/45^{2}n}$
$\displaystyle\leq$ $\displaystyle
O(\omega)\left(\frac{45e\sqrt{\omega}}{c}\right)^{2s/45}e^{-cs\sqrt{\omega}/45^{2}}$
$\displaystyle=$
$\displaystyle\exp\left\\{-\frac{cs\sqrt{\omega}}{45^{2}}\left(1-O\left(\frac{\log\omega}{\sqrt{\omega}}\right)\right)\right\\}$
$\displaystyle\leq$
$\displaystyle\exp\left\\{-\frac{cs\sqrt{\omega}}{50^{2}}\right\\},$

with the final inequality holding for $n$ large enough. Thus, the probability
that there exists an induced subgraph $H$ on $s\geq cn/\sqrt{\omega}$ vertices
with multiple components of size greater than $s/45$ is at most

$\sum_{s=\lceil
cn/\sqrt{\omega}\rceil}^{n}\exp\left\\{-\frac{cs\sqrt{\omega}}{50^{2}}\right\\}\leq
ne^{-\Omega(n)}=o(1).$

We conclude that a.a.s., every induced subgraph $H$ of $\mathcal{G}(n,p)$ on
at least $cn/\sqrt{\omega}$ vertices with $\delta(H)\geq|V(H)|p/3$ is
connected. This finishes part ii) of the proof and so the proof of the lemma
is finished. ∎

###  2.3 Sprinkling and Pósa Rotations

The main result in this section is the following.

######  Theorem 2.3.

Let $p=\omega/n$ and $G=\mathcal{G}(n,p)$. Then, a.a.s., for all set-pairings
$(S,\mathcal{P})$ with $|S|\geq 510n/\sqrt{\omega}$, there is a nonempty sub-
pairing $(S^{\prime},\mathcal{P}^{\prime})\subseteq(S,\mathcal{P})$ such that
$G[S^{\prime}]$ has a Hamilton path.

Before we prove Theorem 2.3, let us show that Theorem 1.2 follows from it.

###### Proof of Theorem 1.2..

Let $p=\omega/n$. Let $\phi:[n]\to\\{1,2,\dots,c\\}$ be a colouring of the
vertices of $\mathcal{G}(n,p)$ with $c\leq n-510n/\sqrt{\omega}$ colour
classes. We construct a set-pairing $(S(\phi),\mathcal{P}(\phi))$ associated
to $\phi$ as follows. For each $j\in\\{1,2,\dots,c\\}$, if $|\phi^{-1}(j)|$ is
odd, let $v$ be the smallest vertex in $\phi^{-1}(j)$ and set
$S_{j}:=\phi^{-1}(j)\setminus\\{v\\}$; otherwise, let $S_{j}:=\phi^{-1}(j)$.

For each $j$ such that $s_{j}:=S_{j}>0$, let
$v_{j_{1}},v_{j_{2}},\dots,v_{j_{s_{j}}}$ be the vertices of $S_{j}$ in
increasing order, and define the pairing
$\mathcal{P}_{j}:=\\{\\{v_{j_{1}},v_{j_{2}}\\},\\{v_{j_{3}},v_{j_{4}}\\},\dots,\\{v_{j_{s_{j}-1}},v_{j_{s_{j}}}\\}\\}$.
Finally, define the set-pairing $(S(\phi),\mathcal{P}(\phi))$ by

$S(\phi):=\bigcup_{j=1}^{c}S_{j}\quad\text{ and
}\quad\mathcal{P}(\phi):=\bigcup_{j=1}^{c}\mathcal{P}_{j}.$

Note that

$|S(\phi)|=\left|\bigcup_{j=1}^{c}S_{j}\right|=\sum_{j=1}^{c}|S_{j}|\geq\sum_{j=1}^{c}(|\phi^{-1}(j)|-1)=n-c\geq\frac{510n}{\sqrt{\omega}}.$

If $\phi$ is a linear colouring of $\mathcal{G}(n,p)$, then
$(S(\phi),\mathcal{P}(\phi))$ cannot contain any nonempty sub-pairing
$(S^{\prime}(\phi),\mathcal{P}^{\prime}(\phi))$ with a Hamilton path. But, by
Theorem 2.3 and the fact that $|S(\phi)|\geq 510n/\sqrt{\omega}$, a.a.s.
$(S(\phi),\mathcal{P}(\phi))$ contains such a sub-pairing, regardless which
colouring $\phi$ with at most $n-510n/\sqrt{\omega}$ colour classes is
considered. Thus, we conclude that a.a.s. no linear colouring of
$\mathcal{G}(n,p)$ with at most $n-510n/\sqrt{\omega}$ colour classes exists,
and hence a.a.s.

$\chi_{\text{lin}}(\mathcal{G}(n,p))>n-\frac{510n}{\sqrt{\omega}},$

which finishes the proof of Theorem 1.2. ∎

It remains to prove Theorem 2.3. To that end, we will use the rotation-
extension technique of Pósa [23]. This procedure requires a two-round exposure
of the edges of $\mathcal{G}(n,p)$. That is, to generate the random graph for
a given $p$, we choose two values $0\leq p_{1},p_{2}\leq p$ such that
$p=p_{1}+p_{2}-p_{1}p_{2}$, then generate independent random graphs
$\mathcal{G}(n,p_{1})$ and $\mathcal{G}(n,p_{2})$. It is easy to see that the
graph obtained by taking the union of $\mathcal{G}(n,p_{1})$ and
$\mathcal{G}(n,p_{2})$, and collapsing any double edges into single edges is
distributed as $\mathcal{G}(n,p)$. In our case, $p=\omega/n$, and we can take
$p_{1}=\frac{\omega}{2n}$ and
$p_{2}=\frac{\omega}{2n}+\epsilon\geq\frac{\omega}{2n}$, where
$\epsilon=O((\omega/n)^{2})$.

Rather than giving a full explanation of the technique here, we refer instead
to the treatment in [10, Chapter 6]. The crucial lemma is the following, which
is a straightforward consequence of [13, Corollary 2.10]:

######  Lemma 2.4.

Let $r$ be a positive integer, and let $G=(V,E)$ be a connected graph in which
every subset $X\subseteq V$ of size $|X|\leq r$ satisfies $|N(X)\setminus
X|>2|X|.$ Suppose that the longest path in $G$ has $h\leq|V|-2$ edges. Then
there are at least $r^{2}/2$ non-edges of $G$ such that the addition of any
one of them results in a graph $G^{\prime}$ whose longest path has at least
$h+1$ edges.

In the light of the above lemma, we will call a graph $H$ good if $H$ is
connected and satisfies $|N(X)\setminus X|>2|X|$ for every $X\subseteq V(H)$
with $|X|\leq|V(H)|/45$.

We will use the following observation.

######  Lemma 2.5.

Let $G_{1}$ be any simple graph on vertex set $[n]$. Sample
$\mathcal{G}(n,p_{2})$ and consider $G=G_{1}\cup\mathcal{G}(n,p_{2})$,
collapsing double edges if needed. Then, the following property holds a.a.s.:
for all subsets $S\subseteq[n]$ with $|S|\geq 255n/\sqrt{\omega}$ such that
$G_{1}[S]$ is good, $G[S]$ contains a Hamilton path.

###### Proof.

Consider a set $S\subseteq[n]$ of size $|S|\geq 255n/\sqrt{\omega}$ that
induces a good subgraph $H=G_{1}[S]$. Using Lemma 2.4, we will greedily build
a Hamilton path on the vertices in $S$ as the edges of $\mathcal{G}(n,p_{2})$
are exposed one-by-one. For a graph $G$, define $\lambda(G)$ to be the number
of edges in a longest path in $G$.

Let $\\{e_{1},e_{2},\dots,e_{r}\\}$ be the edges in $\mathcal{G}(n,p_{2})$
which join pairs of vertices in $S$, listed in a random order. Note that $r$
is distributed as $\text{Bin}\left(\binom{|S|}{2},p_{2}\right)$, which has
mean asymptotic to $|S|^{2}p_{2}/2\geq 255^{2}n/4.$ Using Chernoff’s bound
(2), it is easy to show that $r\geq|S|^{2}p_{2}/4$ with probability
$1-o(2^{-n})$. We condition on this outcome, and henceforth assume
$r\geq|S|^{2}p_{2}/4$. Note that we only exposed the number of edges in
$\mathcal{G}(n,p_{2})$ that fall into the set $S$; the locations of these
edges are still unexposed.

For $1\leq j\leq r$, inductively define $H_{j}=H_{j-1}\cup\\{e_{j}\\}$, where
we take $H_{0}=H$. Since we assume $H$ is good, and adding edges to a good
graph preserves the property of being good, $H_{j}$ is good for all $j$.

Now, fix $j\geq 0$ and condition on the outcome of $H_{j}$ (there is no
conditioning necessary for $j=0$, when we simply have $H_{0}=H$). Suppose that
$\lambda(H_{j})<|S|-1$, that is, $H_{j}$ does not have a Hamilton path. By
Lemma 2.4, there exists a set $B_{j}$ of at least
$\frac{|S|^{2}}{2\cdot(45)^{2}}=\frac{|S|^{2}}{4050}$ non-edges of $H_{j}$
such that if $e_{j+1}\in B_{j}$, then we have
$\lambda(H_{j+1})\geq\lambda(H_{j})+1$. The edge $e_{j+1}$ is uniformly
distributed over pairs of vertices in $S$ which are not in the set
$\\{e_{1},e_{2},\dots,e_{j}\\}$. Crudely, there are at most $\binom{|S|}{2}$
such pairs. Since none of the pairs in $B_{j}$ are in
$\\{e_{1},e_{2},\dots,e_{j}\\}$ by definition, we therefore have

$\textsf{Pr}(e_{j+1}\in
B_{j}\,|\,e_{1},e_{2},\dots,e_{j})\geq\binom{|S|}{2}^{-1}\frac{|S|^{2}}{4050}\geq\frac{1}{2025}\,,$

given that $\lambda(H_{j})<|S|-1$. Clearly, if $\lambda(H_{j})=|S|-1$, then
$\lambda(H_{j+1})=|S|-1$ as well. So for any $0\leq j\leq r-1$, either $H_{j}$
has a Hamilton path, or the length of a longest path increases by at least $1$
from $H_{j}$ to $H_{j+1}$ with probability at least $1/2025$, independently of
the history up to time $j$. Thus, for as long as $H_{j}$ has no Hamilton path,
$\lambda(H_{j})$ stochastically dominates a Binomial random variable with mean
$j/2025.$ In particular,

$\displaystyle\textsf{Pr}(H_{r}\text{ has no Hamilton path})$
$\displaystyle\leq$ $\displaystyle\textsf{Pr}(\lambda(H_{r})<|S|-1)$ (5)
$\displaystyle\leq$
$\displaystyle\textsf{Pr}\left(\text{Bin}\left(r,\frac{1}{2025}\right)<|S|-1\right).$

Conditioned on $r\geq|S|^{2}p_{2}/4$, the $\text{Bin}(r,\frac{1}{2025})$
random variable has mean

$\frac{r}{2025}\geq\frac{1}{2025}\frac{|S|^{2}p_{2}}{4}\geq\frac{1}{16200}\left(\frac{255n}{\sqrt{\omega}}\right)^{2}\frac{\omega}{n}>4n,$

where in the last inequality we use the fact that $255>2\sqrt{16200}\approx
254.558.$ By Chernoff’s bound (2) with
$t=\frac{r}{2025}-n>\frac{3}{4}\cdot\frac{r}{2025}$,

$\displaystyle\textsf{Pr}\left(\text{Bin}\left(r,\frac{1}{2025}\right)<|S|-1\right)$
$\displaystyle\leq$
$\displaystyle\textsf{Pr}\left(\text{Bin}\left(r,\frac{1}{2025}\right)<n\right)$
$\displaystyle\leq$
$\displaystyle\exp\left\\{-\frac{9}{32}\cdot\frac{r}{2025}\right\\}$
$\displaystyle\leq$ $\displaystyle\exp\left\\{-\frac{9n}{8}\right\\}$
$\displaystyle=$ $\displaystyle o(2^{-n}),$

and so $\textsf{Pr}(H_{r}\text{ has no Hamilton path})=o(2^{-n})$ as well by
(5).

In summary, we have shown that, conditioned on $r\geq|S|^{2}p_{2}/4$, the
subgraph $H_{r}=G[S]$ contains a Hamilton path with probability $1-o(2^{-n})$.
Since $r\geq|S|^{2}p_{2}/4$ also with probability $1-o(2^{-n}),$ it follows
that $\textsf{Pr}(G[S]\text{ has no Hamilton path})=o(2^{-n}).$ A union bound
over the at most $2^{n}$ choices for the set $S$ completes the proof of the
lemma. ∎

Now, we can finish the proof of Theorem 2.3.

###### Proof of Theorem 2.3.

By Lemma 2.1, applied to $\mathcal{G}(n,p_{1})$ with $p_{1}=p/2=(\omega/2)/n$,
a.a.s., for every set pairing $(S,\mathcal{P})$ with

$|S|\geq\frac{(255\sqrt{2})n}{\sqrt{\omega/2}}=\frac{510n}{\sqrt{\omega}},$

there exists a set-pairing
$(S^{\prime},\mathcal{P}^{\prime})\subseteq(S,\mathcal{P})$ such that
$|S^{\prime}|\geq|S|/2\geq 255n/\sqrt{\omega}$ and the subgraph
$G[S^{\prime}]$ has minimum degree at least
$|S|p_{1}/3\geq|S^{\prime}|p_{1}/3$. By Lemma 2.2, applied again to
$\mathcal{G}(n,p_{1})$, a.a.s. every induced subgraph $H$ of
$\mathcal{G}(n,p_{1})$ on at least

$\frac{(255/\sqrt{2})n}{\sqrt{\omega/2}}=\frac{255n}{\sqrt{\omega}}$

vertices with $\delta(H)\geq|V(H)|p_{1}/3$ is good.

Combining the two above observations together, we establish that a.a.s. in
$\mathcal{G}(n,p_{1})$, for every set-pairing $(S,\mathcal{P})$ with $|S|\geq
510n/\sqrt{\omega}$, there exists an induced subgraph that is good and has at
least $255n/\sqrt{\omega}$ vertices. Then, by Lemma 2.5, a.a.s. each of these
subgraphs becomes Hamiltonian after adding the edges from
$\mathcal{G}(n,p_{2})$. This finishes the proof of the theorem. ∎

##  3 Sparse Case: $np\leq 1$ (Proof of Theorem 1.3)

In this section, we give some results about
$\chi_{\text{lin}}(\mathcal{G}(n,p))$ in the regime $p=c/n$, $c\leq 1$. These
results are implied directly by the arguments of Perarnau and Serra from [22],
where the centred chromatic number of $\mathcal{G}(n,p)$ is studied under the
name of tree-depth. The relevant result therein is the following.

######  Theorem 3.1 ([22] Theorem 1.2).

The following hold a.a.s.:

$\chi_{\text{cen}}(\mathcal{G}(n,c/n))=\begin{cases}\Theta(\log\log
n)\quad&c\in(0,1)\\\ \Theta(\log n)\quad&c=1.\end{cases}$

Since $\chi_{\text{lin}}(G)\leq\chi_{\text{cen}}(G)$ for any graph $G$,
Theorem 3.1 is already enough to conclude that
$\chi_{\text{lin}}(\mathcal{G}(n,c/n))$ is $O(\log\log n)$ a.a.s. when $c<1$,
and $O(\log n)$ a.a.s. when $c=1.$ As we will see, the techniques used in [22]
to prove the lower bounds in Theorem 3.1 apply equally well to linear
colourings, thus allowing us to deduce Theorem 1.3.

Let us make a few observations. First, for any graph $G$, since any linear
colouring of $G$ is necessarily a linear colouring of every subgraph of $G$,
we have

$\chi_{\text{lin}}(G)\geq\max_{H\subseteq G}\chi_{\text{lin}}(H),$ (6)

where the maximum is taken over all subgraphs $H$ of $G$. Next, observe that
any connected subgraph of the path on $k$ vertices $P_{k}$ is necessarily a
path, and hence linear and the centred colourings are equivalent on a path:

$\chi_{\text{cen}}(P_{k})=\chi_{\text{lin}}(P_{k}).$ (7)

Finally, it is well known, and easy to show, that

$\chi_{\text{cen}}(P_{k})=\lfloor\log_{2}k\rfloor+1.$ (8)

Together, (6), (7), and (8) imply that for any graph $G$ and any component $C$
of $G$, we have

$\chi_{\text{lin}}(G)\geq\log_{2}(\text{diam}(C)).$ (9)

Observation (9) is all we need to prove Theorem 1.3.

###### Proof of Theorem 1.3.

Recall that we only need to show the lower bounds on
$\chi_{\text{lin}}(\mathcal{G}(n,c/n))$; the upper bounds are implied by
Theorem 3.1.

For $c<1$, the diameter of the largest component in $\mathcal{G}(n,c/n)$ is
typically of order $\sqrt{\log n}$, but there are components of smaller
cardinality with diameter of order $\log n$ (see [16]). We conclude that
a.a.s. $\chi_{\text{lin}}(\mathcal{G}(n,c/n))=\Omega(\log\log n)$ by (9).

Similarly, for $c=1$, the diameter of the largest component in
$\mathcal{G}(n,1/n)$ is known to be typically of order $n^{1/3}$ (see [17])
implying that a.a.s. $\chi_{\text{lin}}(\mathcal{G}(n,c/n))=\Omega(\log n)$. ∎

Let us mention that [22] provides weaker lower bounds for the diameter of
$\mathcal{G}(n,c/n)$ when $c\leq 1$ but strong enough to give the same (up to
a multiplicative constant) lower bounds for
$\chi_{\text{lin}}(\mathcal{G}(n,c/n))$. Moreover, for $c>1$, a.a.s.
$\mathcal{G}(n,c/n)$ contains a path of length $\Omega(n)$ (see, for example,
[1]) and so a.a.s. $\chi_{\text{lin}}(\mathcal{G}(n,c/n))=\Omega(\log n)$. In
fact, the non-existence of linear colouring is clearly a monotonic property so
the same bound is implied by the fact that a.a.s.
$\chi_{\text{lin}}(\mathcal{G}(n,1/n))=\Omega(\log n)$.

## References

  * [1] Miklós Ajtai, János Komlós, and Endre Szemerédi.  The longest path in a random graph.  Combinatorica, 1:1–12, 1981.
  * [2] Noga Alon, Colin McDiarmid, and Bruce Reed.  Acyclic coloring of graphs.  Random Structures & Algorithms, 2(3):277–288, 1991.
  * [3] Noga Alon and Joel H Spencer.  The probabilistic method.  John Wiley & Sons, 2016.
  * [4] Béla Bollobás.  Random graphs.  Cambridge University Press, 2001.
  * [5] Prosenjit Bose, Vida Dujmović, Hussein Houdrouge, Mehrnoosh Javarsineh, and Pat Morin.  Linear versus centred chromatic numbers.  arXiv preprint arXiv:2205.15096, 2022.
  * [6] Wojciech Czerwinski, Wojciech Nadara, and Marcin Pilipczuk.  Improved bounds for the excluded-minor approximation of treedepth.  SIAM Journal on Discrete Mathematics, 35(2):934–947, 2021.
  * [7] Michelle Delcourt, Reaz Huq, and Paweł Prałat.  Almost all 9-regular graphs have a modulo-5 orientation, 2023.  arXiv:2210.12103.
  * [8] Jitender S Deogun, Ton Kloks, Dieter Kratsch, and Haiko Müller.  On vertex ranking for permutation and other graphs.  In STACS 94: 11th Annual Symposium on Theoretical Aspects of Computer Science Caen, France, February 24–26, 1994 Proceedings 11, pages 747–758. Springer, 1994.
  * [9] Paul Erdős.  Graph theory and probability.  Canadian Journal of Mathematics, 11:34–38, 1959.
  * [10] Alan Frieze and Michał Karoński.  Introduction to random graphs.  Cambridge University Press, 2016.
  * [11] Svante Janson, Tomasz Łuczak, and Andrzej Ruciński.  Random graphs.  John Wiley & Sons, 2011.
  * [12] Hal A Kierstead and Daqing Yang.  Orderings on graphs and game coloring number.  Order, 20:255–264, 2003.
  * [13] Michael Krivelevich, Eyal Lubetzky, and Benny Sudakov.  Hamiltonicity thresholds in achlioptas processes.  Random Structures & Algorithms, 37(1):1–24, 2010.
  * [14] Michael Krivelevich, Eyal Lubetzky, and Benny Sudakov.  Cores of random graphs are born hamiltonian.  Proceedings of the London Mathematical Society, 109(1):161–188, 2014.
  * [15] Jeremy Kun, Michael P O’Brien, Marcin Pilipczuk, and Blair D Sullivan.  Polynomial treedepth bounds in linear colorings.  Algorithmica, 83(1):361–386, 2021.
  * [16] Tomasz Łuczak.  Random trees and random graphs.  Random structures & algorithms, 13(3-4):485–500, 1998.
  * [17] Asaf Nachmias and Yuval Peres.  Critical random graphs: Diameter and mixing time1.  The Annals of Probability, 36(4):1267–1286, 2008.
  * [18] Jaroslav Nešetřil and Patrice Ossona De Mendez.  Tree-depth, subgraph coloring and homomorphism bounds.  European Journal of Combinatorics, 27(6):1022–1041, 2006.
  * [19] Jaroslav Nešetřil and Patrice Ossona De Mendez.  Sparsity: graphs, structures, and algorithms, volume 28.  Springer Science & Business Media, 2012.
  * [20] Jaroslav Nešetřil and Patrice Ossona de Mendez.  On low tree-depth decompositions.  Graphs and combinatorics, 31(6):1941–1963, 2015.
  * [21] Jaroslav Nešetřil and Saharon Shelah.  On the order of countable graphs.  European Journal of Combinatorics, 24(6):649–663, 2003.
  * [22] Guillem Perarnau and Oriol Serra.  On the tree-depth of random graphs.  Discrete Applied Mathematics, 168:119–126, 2014.
  * [23] Lajos Pósa.  Hamiltonian circuits in random graphs.  Discrete Mathematics, 14(4):359–364, 1976.
  * [24] Paweł Prałat and Nicholas Wormald.  Meyniel’s conjecture holds for random graphs.  Random Structures & Algorithms, 48(2):396–421, 2016.
  * [25] Paweł Prałat and Nicholas Wormald.  Meyniel’s conjecture holds for random d-regular graphs.  Random Structures & Algorithms, 55(3):719–741, 2019.
  * [26] Paweł Prałat and Nick Wormald.  Almost all 5-regular graphs have a 3-flow.  Journal of Graph Theory, 93(2):147–156, 2020.
  * [27] Raphael Yuster.  Linear coloring of graphs.  Discrete mathematics, 185(1-3):293–297, 1998.


††thanks: These authors contributed equally to this study.††thanks: These
authors contributed equally to this study.

# Statistical and dynamical aspects of quantum chaos in a kicked Bose-Hubbard
dimer

Chenguang Liang  Beijing National Laboratory for Condensed Matter Physics,
Institute of Physics, Chinese Academy of Sciences, Beijing 100190, China
School of Physical Sciences, University of Chinese Academy of Sciences,
Beijing, 100049, China  Yu Zhang  Beijing National Laboratory for Condensed
Matter Physics, Institute of Physics, Chinese Academy of Sciences, Beijing
100190, China  School of Physical Sciences, University of Chinese Academy of
Sciences, Beijing, 100049, China  Shu Chen<EMAIL_ADDRESS>Beijing National
Laboratory for Condensed Matter Physics, Institute of Physics, Chinese Academy
of Sciences, Beijing 100190, China  School of Physical Sciences, University of
Chinese Academy of Sciences, Beijing, 100049, China

###### Abstract

Systems of interacting bosons in double-well potentials, modeled by two-site
Bose-Hubbard models, are of significant theoretical and experimental interest
and attracted intensive studies in contexts ranging from many-body physics and
quantum dynamics to the onset of quantum chaos. In this work we systematically
study a kicked two-site Bose-Hubbard model (Bose-Hubbard dimer) with the on-
site potential difference being periodically modulated. Our model can be
equivalently represented as a kicked Lipkin-Meshkov-Glick model and thus
displays different dynamical behaviors from the kicked top model. By analyzing
spectral statistics of Floquet operator, we unveil that the system undergoes a
transition from regularity to chaos with increasing the interaction strength.
Then based on semiclassical approximation and the analysis of Rényi entropy of
coherent states in the basis of Floquet operator eigenstates, we reveal the
local chaotic features of our model, which indicate the existence of
integrable islands even in the deep chaotic regime. The semiclassical analysis
also suggests that the system in chaotic regime may display different
dynamical behavior depending on the choice of initial states. Finally, we
demonstrate that dynamical signatures of chaos can be manifested by studying
dynamical evolution of local operators and out of time order correlation
function as well as the entanglement entropy. Our numerical results exhibit
the richness of dynamics of the kicked Bose-Hubbard dimer in both regular and
chaotic regimes as the initial states are chosen as coherent spin states
located in different locations of phase space.

##  I Introduction

The two-mode or two-site Bose-Hubbard model is a prototype model to study many
fundamental quantum dynamical phenomena, including the Landau-Zenner physics
LZ1 , LZ2 , WuB , Jospheson effect DW1 , DW2 , self trapping Smerzi1999 ,
Smerzi2001 , FuLB  and quantum chaos Strzys , Kidd , BHDimer2013 . A Bose gas
trapped in a double-well potential or modulated optical lattice can be
effectively described by a two-site Bose-Hubbard model (Bose-Hubbard dimer)
Korsch , Chuchem , Leggett , Links , ZhouHQ . With the experimental progress
in cold atoms, the cold atomic system has become an ideal platform for
exploring these intriguing dynamical phenomena Albiez , Levy , Exp-kicktop ,
Exp-kicktop2 . As a minimum model for studying many-body dynamics, the Bose-
Hubbard dimer has attracted intensive studies in the past years Korsch ,
Chuchem , Links , ZhouHQ . Although exhibiting rich dynamical phenomena Tonel
, it is known that the Bose-Hubbard dimer is integrable Links , ZhouHQ  and
thus does not support chaotic dynamics. Nevertheless, chaotic dynamical
behavior can occur when the tunneling amplitude is periodically modulated
BHDimer2013 , Kidd . If the periodical modulation of tunneling is applied in
pulse, the model can be effectively described by a kicked top model, which is
one of paradigmatic models widely used to understand quantum chaos Kicktop ,
Lombardi , Fox , Ghose , Kicktop1997 , WangXG , Dorgra , Kidd2020 , KickPtop ,
lerosepra , WangQ2021 , WangQ2023 .

While the classical chaos is well defined as the exponential sensitivity to
the initial condition, the canonical definition of quantum chaos is still on
debate due to the unitary property of quantum dynamics, especially for the
quantum systems without classical correspondence Berry , WuB2021 , Haake . A
traditional approach to define and diagnosis quantum chaos, originated from
the Bohigas-Giannoni-Schmit conjecture BGS , is level spacing statistics. It
allows us to identify a given quantum system as chaotic system when its level
spacing statistics closely match the theoretical predictions derived from
random matrix theory (RMT)Berry-1977spectrum , BGS , PhysRep , Huse , Atas ,
Guhr . Besides the spectral statistics, the statistics of eigenvectors also
provide useful signatures for detecting quantum chaos Berry1977 , Zyczkowski ,
PhysRep , Haake1990 , Kus , WangQ2023 , WangQ2021 . In last decades, inspired
by the huge progress in the quantum experimental techniques and the theory of
quantum information, the quantum chaos attracted much renewed attention from
many different views, including the development of new tools for detecting
quantum chaos and the application of quantum chaos to the forefront of
research. Important diagnostic tools include the entanglement WangXG ,
Lombardi , Ghose , znidaric08 , Huse13 , bianchijhep , bianchipra , Nahum ,
Fazio  and the out-of-time-ordered correlator (OTOC) Larkin , Kitaev ,
Maldacena , which provide alternative ways to pursue signatures of chaos from
the dynamics of quantum information.Recent studies on various systems of
interest have proven the OTOC to be a useful tool for studying quantum chaos
and thermalization in quantum systems Larkin , Kitaev , Maldacena , Swingle ,
Swingle-pra , Xu , OTOC2017 , OTOC2022 , OTOC19 , JPD . Although the
exponential growth of OTOCs, or fast scrambling of quantum correlations, on
short timescale is commonly considered as an indicator of chaos in many
quantum systems OTOC2017 , OTOC2022 , OTOC19 , recent studies unveil the
existence some counterexamples, which exhibit exponential growth of OTOCs
resulting from unstable fixed points Richter , Fazio , CaoX , Galitski2020 ,
Richter2023 , Cameo , Kidd2021 . While the OTOCs in the periodically modulated
Bose-Hubbard dimer are found to display obviously distinct behaviors in the
chaotic and regular regimes Kidd2020 , scrambling dynamical behaviors around
the saddle point of Bose-Hubbard dimers are also studied in Ref.Richter2023 ,
Kidd2021 .

In this work, we study a generalized model of the kicked Bose-Hubbard dimer
with the on-site potential difference being modulated periodically and explore
the signatures of chaos by analyzing the spectrum and eigenvector statistics
of the Floquet operator and the dynamical behaviors of OTOC and entanglement
entropy. While the spectral statistics of Floquet operator indicates the
existence of transition from regularity to chaos with increasing the
interaction strength, the analysis of Rényi entropy of coherent states in the
basis of Floquet operator eigenstates reveals distribution features in phase
space, resembling the semiclassical Poincaré section. Insights from the
semiclassical correspondence imply that our system displays fruitful dynamical
phenomena in various parameter regimes with different initial states, which
are witnessed by observing dynamical behaviors of local operators, OTOC and
entanglement entropy. We note that our model can not be reduced to the kicked
top model, which can be realized by modulating the tunneling or the
interaction strength of the kicked Bose-Hubbard dimer, and thus displays
different dynamics from the previous studied models Kicktop , Lombardi , Fox ,
Ghose , Kicktop1997 , WangXG , Dorgra , Kidd2020 , KickPtop , lerosepra ,
WangQ2021 , WangQ2023 .

The remainder of this paper is structured as follows. In Sec. II, we introduce
the model. In sec. III, we use the spectral statistics of Floquet unitary
operator to show transitions from regular dynamics to quantum chaos at
different parameters. In sec. IV, we first present the Husimi distribution
function of Floquet eigenstates. Based on the semiclassical approximation, we
give the Poincaré section of systems. Then we study the phase space
localization measure by means of multifractality dimensions of coherent state.
Based on knowledge in previous section, we study the quantum dynamics with
typical initial states in sec. V. In sec. VI, we give a summary and outlook.

##  II Model

We consider the kicked Bose-Hubbard dimer model described by

$\displaystyle H$ $\displaystyle=$
$\displaystyle\nu(b_{1}^{\dagger}b_{2}+b_{2}^{\dagger}b_{1})+\frac{U}{N}\sum_{i=1}^{2}n_{i}(n_{i}-1)$
(1) $\displaystyle+\frac{\mu}{2}(n_{1}-n_{2})\sum_{t}\delta(t-n\tau),$

where $n_{i}=b^{\dagger}_{i}b_{i}$, $b_{i}$ and $b^{\dagger}_{j}$ are the
boson destruction and creation operators fulfilling the commutation

$[b_{i},b^{\dagger}_{j}]=\delta_{ij},[b^{\dagger}_{i},b^{\dagger}_{j}]=[b_{i},b_{j}]=0,$
(2)

$\nu$ is the hopping amplitude between two sites, $U$ is the on site
interaction strength, and $\mu$ denotes the periodically applied potential
difference between two wells with the period $\tau$.

Using the boson operator, we can define the angular momentum operators

$\displaystyle J_{x}=\frac{b_{1}^{\dagger}b_{2}+b_{2}^{\dagger}b_{1}}{2}$ (3)
$\displaystyle J_{y}=\frac{i(b_{1}^{\dagger}b_{2}-b_{2}^{\dagger}b_{1})}{2}$
(4) $\displaystyle J_{z}=\frac{b_{1}^{\dagger}b_{1}-b_{2}^{\dagger}b_{2}}{2}.$
(5)

where $J_{a}(a=x,y,z)$ are the components of angular momentum operator
$\hat{J}$. One can check they satisfy the commutation
relation$[J_{i},J_{j}]=i\epsilon_{ijk}J_{k}$ and
$\hat{J}^{2}=\frac{N}{2}\left(\frac{N}{2}+1\right)$. Since the total particle
number $\hat{N}=n_{1}+n_{2}$ is a conserved quantity, after omitting some
constants, the model (1) can be represented as

$H=2J_{x}+\frac{k}{2J}J_{z}^{2}+\mu J_{z}\sum_{t}\delta(t-n\tau),$ (6)

where we have set $\nu=1$ as the unit of energy, $J=\frac{N}{2}$ and $k=2U$.
Our model is different from the celebrated kicked-top model Kicktop , Lombardi
, Fox , Ghose , Kicktop1997 , WangXG , which reads as

$H=\frac{k}{2J}J_{z}^{2}+\mu J_{x}\sum_{t}\delta(t-n\tau).$ (7)

In comparison with kicked-top model, our model does not have the parity
symmetry. Instead, it more resembles the kicked Lipkin-Meshkov-Glick (LMG)
model Fazio , LMG2017  if we focus on the totally symmetric space.

##  III Spectrum statistics of Floquet operator

The time evolution operator corresponding the Hamiltonian (6) is the unitary
Floquet operator :

$U=e^{-i\mu J_{z}}e^{-i(2J_{x}+\frac{k}{2J}J_{z}^{2})\tau}$ (8)

and we choose $\tau=1$ for convenience. The spectral statistics for a
periodically driven quantum system can be carried out by analyzing the
quasienergies (or eigenphases) of the Floquet operator. Next we study the
spectral statistics of the unitary Floquet operator to show the transition
from regular to chaos. The eigenphases of the Floquet operator $U$ are defined
as

$U|\Phi_{i}\rangle=e^{i\omega_{i}}|\Phi_{i}\rangle,$

where $\omega_{i}$ denotes the ith eigenphase of $U$ with corresponding
eigenstate $|\Phi_{i}\rangle$. As $\\{\omega_{i}\\}$ are $2\pi$ periodic, the
values of $\omega_{i}$ are restricted within the principal range $[-\pi,\pi)$.

The level spacing ratios $r_{n}$ are defined as

$r_{n}=\frac{\min(d_{n},d_{n+1})}{\max(d_{n},d_{n+1})}$

where $d_{n}=\omega_{n+1}-\omega_{n}$ is the spacing between two successive
levels with $\omega_{n}$ being the nth eigenphase of the Floquet operator. The
crossover from regular (integrable) to chaos in the model can be diagnosed by
the mean level spacing ratio (MLSR) $\langle r\rangle$, defined as

$\langle r\rangle=\frac{1}{\mathcal{N}-1}\sum_{n=1}^{\mathcal{N}-1}r_{n},$ (9)

where $\mathcal{N}$ is the dimensions of Hilbert space of $U$. For regular
systems, the Poisson statistics yields $\langle r\rangle_{P}\approx 0.386$,
while for chaotic systems which fulfill Wigner-Dyson statistics, the mean
value $\langle r\rangle_{WD}\approx 0.53$ Huse , Atas . In Fig.1, we display
$\langle r\rangle$ in the parameter space spanned by $k$ and $u$. The $\langle
r\rangle$ is periodic as the $\mu$ changes $2\pi$, and when $\mu$ is close to
$2n\pi,n\in\mathcal{Z}$, the value of $\langle r\rangle$ indicates it
belonging to the integrable regime. Varying $\mu$ and increasing $k$ can
induce the crossover from integrable to chaotic regime. To see it clearly, in
Fig.2 we show how $\langle r\rangle$ changes at different $k$ with fixed
$\mu=3$ and $6$. It is clear that the model is always in the integrable regime
when $\mu=6$. In the following discussion, we will focus on the case $\mu=3$
with different $k$.

Figure 1: Mean level spacing ratio $\langle r\rangle$ as a function of $k$ and
$\mu$ . When $k$ is small, the system is always in regular regime for any $u$.
With the increase of $\mu$, periodical regular-chaotic crossover appears in
regime with larger $k$. Here we take $J=1000$. Figure 2: Mean level spacing
ratio $\langle r\rangle$ as a function of $k$ at fixed $\mu=3$ and $\mu=6$,
respectively.

##  IV Husimi distributions of eigenstates and phase space localization
measure

Even though the level statistics of dynamical systems becomes a standard probe
in the studies of quantum chaos, it cannot detect the local chaotic features
in quantum systems. In order to get a straightforward understanding of the
onset of chaos, it is instructive to establish links between the properties of
eigenstates of Floquet operator and the trajectories of classically chaotic
systems. To this end, we shall first display Husimi distributions for various
eigenstates of Floquet operator, which reflect the quantum phase-space
distributions of Floquet eigenstates, in the regular and chaotic regimes,
respectively. Then we show the phase space Poincaré section under the
semiclassical approximation and reveal local chaotic features via the study of
the phase space localization measure by means of multifractality dimensions of
coherent state.

Figure 3: The first row: (a)-(c) are Husimi function rescaled by its maximum
value for three randomly chosen eigenstates of Floquet operator in the regular
regime with parameters $\mu=3$ and $k=1$. The second row: (d)-(f) are Husimi
function rescaled by its maximum value for three randomly chosen eigenstates
of Floquet operator in the chaotic regime with parameters $\mu=3$ and $k=8$.
Here we fix $J=150$.

###  IV.1 Husimi distribution function

As a kind of smoothed (coarsely grained) Wigner distribution Wigner , Husimi ,
the Husimi distribution serves as a tool to reveal various aspects of
eigenstates within the phase space ShiKJ , Takahashi , offering insights into
their localization properties. To define the Husimi function, we employ the
generalized coherent spin states Coherentstate , WMZhang , SCS , SCS2  given
by

$\displaystyle|\theta,\phi\rangle=\exp[i\theta(J_{x}\sin\phi-
J_{y}\cos\phi)]|J,J\rangle,$ (10)

where $\theta\in[0,\pi]$ and $\phi\in[-\pi,\pi)$, providing the orientation of
$\hat{J}$. These coherent states satisfy

$\frac{1}{J}\langle\phi,\theta|\hat{J}|\phi,\theta\rangle=(\cos{\phi}\sin{\theta},\sin{\phi}\sin{\theta},\cos{\theta}).$

The Husimi function in the phase space for the $n$th eigenstate
$|\Phi_{n}\rangle$ of the Floquet operator $U$ is given by

$Q_{n}(\phi,\theta)=|\langle\theta,\phi|\Phi_{n}\rangle|^{2}.$ (11)

To gain an intuitive understanding, we depict the Husimi distribution of
several randomly chosen eigenstates of Floquet operator for different values
of $k$ in Fig.3. In the regular regime with $k=1$ and $\mu=3$, the Husimi
distributions display similar behaviors of regular periodic orbits, as shown
in Figs.3(a)-(c). On the other hand, in the chaotic regime, exemplified by the
case with $k=8$ and $\mu=3$ as shown in Figs.3(d)-(f)), the Husimi
distribution in the phase space become random and irregular.

Figure 4: First row (a)-(d): phase space Poincaré section of the classic
equation of motions. The initial states $\left(\theta,\phi\right)$ are
selected on grid of 20 $\times$20 on the phase space. Each trajectory is
evolved for 400 kicks. The parameter $\mu$ is fixed at 3, and $k=1,3,5$, and
$8$ from (a) to (d), respectively. Second row (e)-(h): The multifractal
dimension of coherent states, calculated on a grid of 100$\times$100 on the
parameter space of $\theta$ and $\phi$. The parameter $\mu$ is fixed at 3, and
and $k=1,3,5$, and $8$ from (e) to (h), respectively. In (e) and (h), we
marked the coherent states which we shall be utilized as initial states in the
calculation of dynamics in sec. V

###  IV.2 Semiclassical approximation

When $J\rightarrow\infty$, our model has a well defined quantum-classical
correspondence, so the chaotic behaviour of the quantum system can be also
manifested in its semiclassical dynamics. Defining $\hat{m}=\hat{J}/J$, in the
limit of $J\rightarrow\infty$, we see that $\hat{m}$ behaves as classical
angular momentum due to the vanishing of commutators between $m_{\alpha}$
($\alpha=x,y,z$). As the classical angular momentum
$\hat{m}=(m_{x},m_{y},m_{z})$ is a unit vector, it can be parameterized in
terms of the azimuthal angle $\theta$ and polar angle $\phi$ as
$\hat{m}=(\cos{\phi}\sin{\theta},\sin{\phi}\sin{\theta},\cos{\theta})$, where
$\theta\in[0,\pi]$ and $\phi\in[-\pi,\pi)$. Hence, the classical phase space
is a two-dimensional space with variables $\phi=\arctan{m_{y}/m_{x}}$ and
$\theta=\arccos{m_{z}}$. We use the $\hat{m}$ to re-express Hamiltonian as

$H=J\left[2m_{x}+\frac{k}{2}m_{z}^{2}+\mu
m_{z}\sum_{t}\delta(t-n\tau)\right].$ (12)

The full dynamical map can be obtained by following two steps. Firstly we
consider the evolution of time-independent part
$H=J(2m_{x}+\frac{k}{2}m_{z}^{2})$, the classical equation of motion of
$\hat{m}$ is

$\displaystyle\dot{m_{x}}=-km_{y}m_{z},$ (13)
$\displaystyle\dot{m_{y}}=-2m_{z}+km_{x}m_{z},$ (14)
$\displaystyle\dot{m_{z}}=2m_{y},$ (15)

where the coefficient J can be canceled by the commutation of $\hat{m}$. Then
the kicked part of the Floquet operator alone yields the map

$\displaystyle\tilde{m}_{x}=\cos{\mu}m_{x}-\sin{\mu}m_{y},$ (16)
$\displaystyle\tilde{m}_{y}=\sin{\mu}m_{x}+\cos{\mu}m_{y},$ (17)
$\displaystyle\tilde{m}_{z}=m_{z}.$ (18)

In the first row of Fig.(4), we present the Poincaré section for different
values of the parameter $k$, while keeping $\mu$ fixed at $\mu=3$. When $k=1$,
as illustrated in Fig.4(a), the model is in the integrable regime,
characterized by closed classical orbits and two approximate unstable fixed
points. When the value of $k$ increases, as exemplified by the cases of $k=3$
and $k=5$ shown in Figs. 4 (b) and 4(c), respectively, two closed periodic
orbits in the integrable regime vanish, and the remaining two gradually
decrease in size. Finally, for the case of $k=8$ shown in Fig.4 (d),
corresponding to $\langle r\rangle\approx 0.53$, the system enters the quantum
chaotic regime. In this regime, all periodic orbits in the bulk of the phase
space disappear, except for a few very small isolated unstable fixed points
(which shall be further discussed in the next section). However, two
integrable islands emerge in corner regions of phase space around
$\theta\approx 0$ and $\pi$, respectively. We numerically check that these two
integrable islands still survive when $k$ is very large.

###  IV.3 Multifractality dimensions of coherent states

In order to further characterize the phase space structure and get more
insight into the quantum-classical correspondence, we study the multifractal
properties of the coherent states in this subsection. We still use the
generalized coherent spin states given by Eq.(10). To define the Rényi entropy
and multifractal dimensions of coherent states, we expand it in the
orthonormal eigensates basis of the Floquet operators $U$

$|\theta,\phi\rangle=\sum_{i=1}^{\mathcal{N}}c_{i}|\Phi_{i}\rangle,$ (19)

where the $|\Phi_{i}\rangle$ is the $i$-th eigensates of Floquet operator and
$c_{i}=\langle\Phi_{i}|\theta,\phi\rangle$. Then we can define the Rényi
entropy $S_{q}$ and multifractal dimensions $D_{q}$ Dq1 , Dq2 :

$S_{q}=\frac{1}{1-q}\ln{\sum_{i=1}^{\mathcal{N}}|c_{i}|^{2q}}\quad\text{and}\quad
D_{q}=\frac{S_{q}}{\ln\mathcal{N}}.$ (20)

For finite $\mathcal{N}$, we have $D_{q}\in[0,1]$. The values of $D_{q}$
decrease with increasing $q$ for $q\geq 0$. The fractal dimensions of
$\mathcal{D}_{q}^{\infty}$ are obtained via
$\mathcal{D}_{q}^{\infty}=\lim_{\mathcal{N}\to\infty}D_{q}$ in the limit of
$\mathcal{N}\to\infty$. The fractal dimensions measure the degree of
ergodicity of a quantum state in Hilbert space. For a completely localized
state $\mathcal{D}_{q}^{\infty}=0$ for $q>0$, whereas
$\mathcal{D}_{q}^{\infty}=1$ denotes an extended state in the Hilbert space of
Floquet operator and thus corresponds to an ergodic state. The multifractal
states are the extended non-ergodic states and characterized by
$0<\mathcal{D}_{q}^{\infty}<1$. In our calculation, we choose $q=2$ with
$\mathcal{D}_{2}$ being the logarithm of the well-known participation ratio.
In the second row of Fig.4, we depict $D_{2}$ as a function of $\phi$ and
$\theta$ for different values of $k$. Comparing this with the first row of
Fig.(4), we observe a very similar structure to the Poincaré section discussed
in Section IV.2. Such a similarity suggests that the multifractal dimensions
of coherent states exhibit an obvious correspondence to the underlying
semiclassical Poincaré section and thus provide very useful information for
understanding quantum chaos WangQ2021 , Renyi-jpa , WangQ-Dicke .

In the case of $k=1$ shown in Fig.4 (e), the positions of $D_{q}\approx 0$ are
located at the regions corresponding to the most regular closed periodic
orbits around the stable fixed points in the Poincaré sections, indicating the
coherent states located at these points are the localized states in the
Hilbert space, while the points with higher multifractal dimension are along
the longer periodic orbits. As the $k$ increases, $D_{2}$ take larger values
and exhibit an approximately uniform distribution in the rest of phase space
except for some integrable islands in the bulk, as shown in Fig.4 (f) and
Fig.4 (g). When $k$ enters the quantum chaotic regime as shown in Fig.4 (h),
where all integrable islands in the bulk disappear, the coherent states have
high fractal dimensions almost everywhere in the bulk, but there are still
some points with small values in the bulk which is related to isolated
unstable fixed points in the semiclassical dynamics Kicktop . These small
patches are blurred in the background and need to be carefully found in the
Poincaré section. Finally, within large integrable islands near the south and
north poles of the phase space, the fractal dimensions reach minimal values,
even within chaotic regimes.

We also define the average multifractal dimensions

$\bar{D_{2}}=\frac{1}{4\pi}\int dSD_{2},$

which represent the average $D_{2}$ across the entire phase space. In Fig.5,
we plot $\bar{D_{2}}$ versus $k$ for various $J=100$, $200$ and $300$. While
$\bar{D_{2}}$ changes slowly with increasing $k$ for smaller $k$. Our results
illustrate a rapid growth of $\bar{D_{2}}$ with increasing $k$ when $k>1.6$,
resembling the behavior of the mean level spacing ratio presented in Fig.2.
However, as $k$ enters the chaotic regime, $\bar{D_{2}}$ begins to exhibit
oscillations. This distinct behavior from the mean level spacing ratio is
attributed to the existence of integrable islands even for large $k$.

Figure 5: Average multifractal dimension $\bar{D_{2}}$ as a function of $k$
for different $J$. The parameter $\mu$ is fixed at $3$. Figure 6: Dynamics of
$S_{z}$ from different initial coherent states. The first row: (a)-(c) is in
the regular regime with parameters $\mu=3$ and $k=1$. From left to right, the
initial states correspond to diamond, circle and star points marked in the
Fig.4 (e). The second row: (d)-(f) is in the chaotic regime with parameters
$\mu=3$ and $k=8$. From left to right, the initial states correspond to
diamond, circle and star points marked in the Fig.4 (h). Here we fix $J=800$.

##  V signatures from quantum dynamics

In the previous section, we have analyzed our system through its structure of
spectral and eigenvector statistics as well as its semiclassical dynamics. We
have conformed some interesting local dynamical features which can not be
captured by the statistics of spectrum of Floquet operator. Based on the
analysis of phase space localization measure of eigenvector statistics and its
corresponding classical phase space trajectories, we infer that the choice of
different initial states may give rise to quite different quantum dynamics
even for system with the same mean level spacing ratio of spectrum statistics.
In this section we study the quantum dynamics to further display the feature
of our model. For simplicity, we focus on the cases of $k=1$ and $k=8$.

###  V.1 Dynamical evolution of local operators

Before the discussion for the quantum dynamical signature of chaos, we
calculate the dynamical evolution of local operator observable $S_{z}(t)$,
namely

$S_{z}(t)=\frac{1}{J}\langle\psi_{0}|J_{z}(t)|\psi_{0}\rangle.$ (21)

Here the initial states are chosen as the coherent states studied in the
previous section. To see them clear, we marked our initial states in Fig.4 (e)
and Fig.4(h) by using the diamond, circle and star points, respectively. We
display our numerical results in Fig.6.

The first row of Fig.6 illustrates the dynamics in the integrable regime. When
the initial states originate from short closed orbits, $S_{z}(t)$ exhibits
persistently oscillating behavior as shown in Fig.6(a). However, if the
initial states are associated with long periodic orbits or unstable fixed
points (Fig.6 (b) and (c)), the oscillations eventually decay. In the chaotic
regimes, for the majority of initial states, as depicted in Fig.6 (d),
$S_{z}(t)$ rapidly decays to a stationary state. When the initial state is
chosen at unstable fixed point, $S_{z}(t)$ decays more slowly in an
oscillating way, as displayed in Fig.6 (e). Conversely, within the integrable
islands, the dynamics of $S_{z}$ remains frozen at the initial states,
exhibiting a self-trapping behavior, as shown in Fig.6 (f).

###  V.2 Dynamics of OTOC

The OTOC, as a new way to understand and diagnose quantum chaos, has been
discussed from many different fields in recent years Maldacena , Swingle ,
Swingle-pra , OTOC2017 , OTOC2022 , OTOC19 , Xu . It is defined as

$C(t)=-\left\langle[\hat{W}(t),\hat{V}]^{2}\right\rangle,$ (22)

where $\left\langle\cdots\right\rangle$ denotes the expectation values,
$\hat{W}$ and $\hat{V}$ are two operators, and $\hat{W}(t)=U^{\dagger}WU$.
Note that $C(t)\geq 0$ if $\hat{W}$ and $\hat{V}$ are Hermitian operators.
Analogy to the classical Lyaponouv exponents, OTOC is expected to have the
exponential growth at early time in quantum chaotic systems. While recently
some works found for integrable model the OTOC also can have exponential
growth if the initial states near the non-stable fixed point in classical
limit Richter , CaoX , Galitski2020 , Richter2023 , Cameo , Kidd2021 . Here we
study the square commutator between two $J_{z}$ operator, namely

$C_{zz}(t)=-\left(\frac{1}{J}\right)^{2}\langle\psi_{0}|\left[J_{z}(t),J_{z}\right]^{2}|\psi_{0}\rangle,$
(23)

where we still choose the coherent state given by (10) as the initial state
$|\psi_{0}\rangle$. As we will illustrate in Fig.7, in both regular and
chaotic regimes, the growth behaviour of OTOC strongly depends on its initial
states. Based on the Poincaré section and multifractal dimensions of coherent
states, we select separately three representative initial states for regular
and chaotic cases, respectively, as marked in Fig.4 (e) and Fig.4 (h) by using
diamond, circle and star points.

Figure 7: OTOC initialized from different initial coherent states. The first
row: (a)-(c) are in the regular regime with parameters $\mu=3$ and $k=1$. From
left to right, the initial states correspond to diamond, circle and star
points marked in Fig.4(e). The second row: (d)-(f) are in the chaotic regime
with parameters $\mu=3$ and $k=8$. From left to right, the initial states
correspond to diamond, circle and star points marked in Fig.4 (h). Here
$J=100,200$ and $800$, respectively.  Figure 8: Entanglement entropy versus
$t$ for different initial coherent states. (a) is in the regular regime with
parameters $\mu=3$ and $k=1$. Three initial states correspond to diamond,
circle and star points in Fig.4 (e), respectively. (b) is in the chaotic
regime with parameters $\mu=3$ and $k=8$. Three initial states correspond to
diamond, circle and star points in Fig.4 (h), respectively. Here we take
$J=400$.

In the regular regime with $k=1$, the diamond point is situated on short
closed periodic orbits near the stable fixed point, exhibiting very small
Rényi entropy. The OTOC from this point, as depicted in Fig.7(a), exhibits a
slow linear growth, and the saturation values are remarkably small. In
contrast, the circle point lies on a long periodic orbit in the Poincaré
section, featuring higher Rényi entropy compared to its surrounding points.
This orbit connects to unstable fixed points in the Poincaré section. The OTOC
from this circle point, illustrated in Fig. 7 (b), grows exponentially at
early times, reaching a larger saturation value. When the star point is
situated near the unstable fixed point in the Poincaré section, the OTOC
growth is clearly exponential at early times, as shown in Fig.7 (c),
resembling the chaos case discussed below. Additionally, its saturation values
are larger than those of the former point, reaching a level comparable to the
chaotic case.

In the chaotic regime with $k=8$, the diamond point exhibits a large Rényi
entropy, corresponding to a randomly chosen point in the Poincaré section,
which represents a majority of points in the phase space. The OTOC evolving
from this initial state, as depicted in Fig.7 (d), exhibits standard
exponential growth at early times and quickly reaches saturation. The circle
point is situated at an isolated unstable fixed point, surrounded by random
trajectories. The OTOC evolving from this circle point, as illustrated in
Fig.7 (e), also exhibits exponential growth, but grows much slower than the
case from the diamond point. Finally, the star point is located in deep
integrable islands, featuring minimal Rényi entropy. The OTOC evolving from
this star point, as shown in Fig.7 (f), no longer grows exponentially, and its
saturation value is much smaller than the values in Figs.7 (d) and (e),
reaching the same level as the regular case. With the increase in $J$, the
saturation value is further suppressed.

###  V.3 Dynamics of entanglement entropy

The dynamics of entanglement entropy has been applied to detect chaos in
quantum systems WangXG , znidaric08 , Huse13 , bianchijhep , bianchipra . A
large spin system can be effectively represented as a many-qubit system, such
as in our model and the LMG model, both of which can be viewed as systems
composed of $J$ qubits. Employing the decomposition method from WangXG ,
Vidal05 , Gisin , we calculate the von Neumann entanglement entropy of the
reduced density matrix $\rho_{s}$ after tracing out $s^{\prime}=J-s$ qubits:
$S_{E}=-\text{Tr}{\rho_{s}\ln{\rho_{s}}}$. In the following calculation, we
consider $s=2$. Using the same initial states as utilized in the dynamics of
OTOC, we explore the dynamical evolution of the entanglement entropy.

Similar to the behaviors observed in the OTOC for different initial states, in
the regular regime with $k=1$, as depicted in Fig.8 (a), the entanglement
originating from a small closed orbit exhibits persistent oscillations.
Meanwhile, when initialized from a long periodic orbit or an unstable fixed
point, the entanglement entropy grows with oscillations and reaches a higher
saturation value. In the chaotic regime with $k=8$, as illustrated in Fig.8
(b), the entanglement entropy experiences rapid growth, swiftly approaching
saturation when initialized from the point where the OTOC exhibits standard
exponential growth. In contrast, for the case of an unstable fixed point, akin
to the OTOC dynamics, the entanglement entropy reaches saturation at a more
gradual pace compared to the majority of cases. Finally, when initialized from
deep integrable islands, the entanglement entropy remains stagnant and hovers
around zero.

##  VI Summary

In summary, we systematically study a kicked Bose Hubbard dimer, which can be
effectively described by a kicked LMG model, and uncover signatures of chaos
in the system from both statistical and dynamical aspects. The diagnosis of
spectral statistics of Floquet operator reveals the periodical dependence of
$\mu$ and the existence of transition from regular to chaotic dynamics with
the increase in $k$. Furthermore, insights from semiclassical dynamics and
analysis of phase space localization measure suggest that the system may
display fruitful dynamical phenomena in various parameter regimes with
different initial states, which are confirmed by studying the dynamics of
local operators, OTOC and entanglement entropy. Our results exhibit the
richness of dynamics in the kicked Bose-Hubbard dimer.

###### Acknowledgements.

We thank Libin Fu for helpful discussions. The financial supports from the
National Natural Science Foundation of China (Grant No. 12174436 and
T2121001), and Strategic Priority Research Program of the Chinese Academy of
Sciences (Grant No. XDB33000000) are gratefully acknowledged.

## References

  * [1] L. D. Landau, Zur Theorie der Energieubertragung II, Phys. Z. Sowjetunion 2, 46 (1932).
  * [2] G. Zener, Non-adiabatic crossing of energy levels, Proc. R. Soc. London A 137, 696 (1932).
  * [3] B. Wu and Q. Niu, Nonlinear Landau-Zener tunneling, Phys. Rev. A 61, 023402 (2000).
  * [4] G. J. Milburn, J. Corney, E. M. Wright, and D. F. Walls, Quantum dynamics of an atomic Bose-Einstein condensate in a double-well potential, Phys. Rev. A 55, 4318 (1997).
  * [5] A. Smerzi, S. Fantoni, S. Giovanazzi, and S. R. Shenoy, Quantum Coherent Atomic Tunneling between Two Trapped Bose-Einstein Condensates, Phys. Rev. Lett. 79, 4950 (1997).
  * [6] S. Raghavan, A. Smerzi, S. Fantoni, and S. R. Shenoy, Coherent oscillations between two weakly coupled Bose-Einstein condensates: Josephson effects, $\pi$ oscillations, and macroscopic quantum self-trapping, Phys. Rev. A 59, 620 (1999).
  * [7] J. R. Anglin, P. Drummond, and A. Smerzi, Exact quantum phase model for mesoscopic Josephson junctions, Phys. Rev. A 64, 063605 (2001).
  * [8] G.-F. Wang, L.-B. Fu, and J. Liu, Periodic modulation effect on self-trapping of two weakly coupled Bose-Einstein condensates, Phys. Rev. A 73, 013619 (2006).
  * [9] M P Strzys, E. M. Graefe, and H. J. Korsch, Kicked Bose Hubbard systems and kicked tops-destruction and stimulation of tunneling, New J. Phys. 10, 013024 (2008).
  * [10] C. Khripkov, D. Cohen, and A. Vardi, Coherence dynamics of kicked Bose-Hubbard dimers: Interferometric signatures of chaos, Phys. Rev. E 87, 012910 (2013).
  * [11] R. A. Kidd, M. K. Olsen, and J. F. Corney, Quantum chaos in a Bose-Hubbard dimer with modulated tunneling, Phys. Rev. A 100, 013625 (2019).
  * [12] A. J. Leggett, Bose-Einstein condensation in the alkali gases: Some fundamental concepts, Rev. Mod. Phys. 73, 307 (2001).
  * [13] E. M. Graefe and H. J. Korsch, Semiclassical quantization of an N-particle Bose-Hubbard model Phys. Rev. A 76, 032116 (2007).
  * [14] M. Chuchem, K. Smith-Mannschott, M. Hiller, T. Kottos, A. Vardi, and D. Cohen, Quantum dynamics in the bosonic Josephson junction, Phys. Rev. A 82, 053617 (2010).
  * [15] J. Links and H.-Q. Zhou, Exact Form Factors for the Josephson Tunneling Current and Relative Particle Number Fluctuations in a Model of Two Coupled Bose Einstein Condensates, Lett. Math. Phys. 60, 275 (2002).
  * [16] Huan-Qiang Zhou, Jon Links, R. H McKenzie and Xi-Wen Guan, Exact results for a tunnel-coupled pair of trapped Bose Einstein condensates, J. Phys. A: Math. Gen. 36 L113 (2003).
  * [17] M. Albiez, R. Gati, J. Fölling, S. Hunsmann, M. Cristiani, and M. K. Oberthaler, Direct Observation of Tunneling and Nonlinear Self-Trapping in a Single Bosonic Josephson Junction, Phys. Rev. Lett. 95, 010402 (2005).
  * [18] S. Levy, E. Lahoud, I. Shomroni, and J. Steinhauer, The a.c. and d.c. Josephson effects in a Bose-Einstein condensate, Nature (London) 449, 579 (2007).
  * [19] J. Tomkovic, W. Muessel, H. Strobel, S. Löck, P. Schlagheck, R. Ketzmerick, and M. K. Oberthaler, Experimental observation of the Poincaré-Birkhoff scenario in a driven many-body quantum system, Phys. Rev. A 95, 011602(R) (2017).
  * [20] S. Chaudhury, A. Smith, B. E. Anderson, S. Ghose and P. S. Jessen, Quantum signatures of chaos in a kicked top, Nature, 461, 768 (2009).
  * [21] A. P. Tonel, J. Links, A. Foerster, Quantum dynamics of a model for two Josephson-coupled Bose–Einstein condensates, J, Phys. A 38, 1235 (2005).
  * [22] F. Haake, M. Kuś, and R. Scharf, Classical and quantum chaos for a kicked top, Z. Phys. B: Condens. Matter 65, 381 (1987).
  * [23] R. F. Fox and T. C. Elston, Chaos and a quantum-classical correspondence in the kicked top, Phys. Rev. E 50, 2553 (1994).
  * [24] V. Constantoudis and N. Theodorakopoulos, Lyapunov exponent, stretching numbers, and islands of stability of the kicked top. Phys. Rev. E 56, 5189 (1997).
  * [25] X. Wang, S. Ghose, B. C. Sanders, and B. Hu, Entanglement as a signature of quantum chaos, Phys. Rev. E 70, 016217 (2004).
  * [26] S. Ghose, R. Stock, P. Jessen, R. Lal, and A. Silberfarb, Chaos, entanglement, and decoherence in the quantum kicked top, Phys. Rev. A 78, 042318 (2008).
  * [27] M. Lombardi and A. Matzkin, Entanglement and chaos in the kicked top, Phys. Rev. E 83, 016207 (2011).
  * [28] S. Dogra, V. Madhok, and A. Lakshminarayan, Quantum signatures of chaos, thermalization, and tunneling in the exactly solvable few-body kicked top, Phys. Rev. E 99, 062217 (2019).
  * [29] R. A. Kidd, A. Safavi-Naini, and J. F. Corney, Thermalization in a Bose-Hubbard dimer with modulated tunneling, Phys. Rev. A 102, 023330 (2020).
  * [30] Manuel H. Mu$\tilde{n}$oz-Arias, Pablo M. Poggi, and Ivan H. Deutsch,Nonlinear dynamics and quantum chaos of a family of kicked p-spin models, Phys. Rev. E 103, 052212
  * [31] A. Lerose and S. Pappalardi, Bridging entanglement dynamics and chaos in semiclassical systems, Phys. Rev. A, 102, 032404 (2020).
  * [32] Q. Wang and M. Robnik, Multifractality in Quasienergy Space of Coherent States as a Signature of Quantum Chaos Signature of Quantum Chaos, Entropy, 23, 1347 (2021).
  * [33] Q. Wang and M. Robnik, Statistics of phase space localization measures and quantum chaos in the kicked top model, Phys. Rev. E 107, 054213 (2023).
  * [34] M. Berry, Quantum chaology, not quantum chaos, Phys. Scr. 40, 335 (1989).
  * [35] F. Haake, Quantum Signatures of Chaos, 3rd ed. (Springer, Berlin, 2010).
  * [36] Z. Wang, Y. Wang, and B. Wu, Quantum chaos and physical distance between quantum states, Phys. Rev. E 103, 042209 (2021).
  * [37] O. Bohigas, M.J. Giannoni and C. Schmit, Characterization of Chaotic Quantum Spectra and Universality of Level Fluctuation Laws. Phys. Rev. Lett. 52, 1 (1984).
  * [38] M. V. Berry and M. Tabor, Level clustering in the regular spectrum. Proc. R. Soc. A 356, 375 (1977).
  * [39] V. Oganesyan and D. A. Huse, Localization of interacting fermions at high temperature. Phys. Rev. B 75, 155111 (2007).
  * [40] Y. Y. Atas, E. Bogomolny, O. Giraud and G. Roux, Distribution of the Ratio of Consecutive Level Spacings in Random Matrix Ensembles, Phys. Rev. Lett. 110, 084101 (2013).
  * [41] T. Guhr, A. Mueller-Gröeling, and H. A. Weidenm ller, Random matrix theories in quantum physics: Common concepts, Phys. Rep. 299, 189 (1998).
  * [42] F. M. Izrailev, Simple models of quantum chaos: Spectrum and eigenfunctions, Phys. Rep. 196, 299 (1990).
  * [43] M.V. Berry, Regular and irregular semiclassical wavefunctions. J. Phys. A 10, 2083 (1977).
  * [44] M. Kus, J. Mostowski and F. Haake, Universality of eigenvector statistics of kicked tops of different symmetries, J. Phys. A: Math. Gen. 21 L1073 (1988).
  * [45] K. Zyczkowski, Indicators of quantum chaos based on eigenvector statistics, J. Phys. A: Math. Gen. 23, 4427 (1990).
  * [46] F. Haake and K. Zyczkowski, Random-matrix theory and eigenmodes of dynamical systems. Phys. Rev. A 42, 1013 (1990).
  * [47] Marko Znidaric, Tomaz Prosen, and Peter Prelovsek,Many-body localization in the Heisenberg xxz magnet in a random field, Phys. Rev. B 77, 064426 (2008).
  * [48] Hyungwon Kim and David A. Huse, Ballistic Spreading of Entanglement in a Diffusive Nonintegrable System, Phys. Rev. Lett. 111, 127205 (2013)
  * [49] Bianchi, E., Hackl, L. Yokomizo, N. Linear growth of the entanglement entropy and the Kolmogorov-Sinai rate. J. High Energ. Phys. 2018, 25 (2018).
  * [50] Lucas Hackl, Eugenio Bianchi, Ranjan Modak, and Marcos Rigol, Entanglement production in bosonic systems: Linear and logarithmic growth, Phys. Rev. A 97, 032321 (2018)
  * [51] Adam Nahum, Jonathan Ruhman, Sagar Vijay, and Jeongwan Haah,Quantum Entanglement Growth under Random Unitary Dynamics, Phys. Rev. X 7, 031016
  * [52] Silvia Pappalardi, Angelo Russomanno, Bojan Zunkovic, Fernando Iemini, Alessandro Silva, and Rosario Fazio, Scrambling and entanglement spreading in long-range spin chains, Phys. Rev. B 98, 134303 (2018).
  * [53] Larkin, Anatoly I., and Yu N. Ovchinnikov. ”Quasiclassical method in the theory of superconductivity.” Sov Phys JETP 28.6 (1969): 1200.
  * [54] A. Kitaev, Hidden correlations in the hawking radiation and thermal noise, talks given at The Fundamental Physics Prize Symposium, 10 November 2014, and at The KITP, 12 February 2015.
  * [55] J. Maldacena, S. H. Shenker, and D. Stanford, A bound on chaos, J. High Energy Phys. 08 (2016) 106.
  * [56] B. Swingle, G. Bentsen, M. Schleier-Smith, and P. Hayden, Measuring the scrambling of quantum information, Phys. Rev.A 94, 040302(R) (2016).
  * [57] B. Swingle, Unscrambling the physics of out-of-time-order correlators, Nat. Phys. 14, 988 (2018).
  * [58] S. Xu, and B. Swingle, Scrambling dynamics and out-of-time ordered correlators in quantum many-body systems: a tutorial, arXiv:2202.07060.
  * [59] E. B. Rozenbaum, S. Ganeshan, and V. Galitski, Lyapunov Exponent and Out-of-Time-Ordered Correlator’s Growth Rate in a Chaotic System, Phys. Rev. Lett. 118, 086801 (2017).
  * [60] M. Zonnios, J. Levinsen, M. M. Parish, F. A. Pollock, and K. Modi, Signatures of Quantum Chaos in an Out-of-Time-Order Tensor, Phys. Rev. Lett. 128, 150601 (2022).
  * [61] R. J. Lewis-Swan, A. Safavi-Naini, J. J. Bollinger, and A. M. Rey, Unifying scrambling, thermalization and entanglement through measurement of fidelity out-of-time-order correlators in the Dicke model, Nat. Commun. 10, 1581 (2019).
  * [62] Sreeram PG, V. Madhok, and A. Lakshminarayan, Out-of-time-ordered correlators and the Loschmidt echo in the quantum kicked top: how low can we go? J. Phys. D 54, 274004 (2021).
  * [63] Q. Hummel, B. Geiger, J. D. Urbina, and K. Richter, Reversible Quantum Information Spreading in Many-Body Systems near Criticality, Phys. Rev. Lett. 123, 160401 (2019).
  * [64] T. Xu, T. Scaffidi, and X. Cao, Does Scrambling Equal Chaos? Phys. Rev. Lett. 124, 140602 (2020).
  * [65] E. B. Rozenbaum, L. A. Bunimovich, and V. Galitski, Early-Time Exponential Instabilities in Nonchaotic Quantum Systems, Phys. Rev. Lett. 125, 014101 (2020)
  * [66] S. Pilatowsky-Cameo, J. Chávez-Carlos, M. A. Bastarrachea-Magnani, P. Stránský, S. Lerma-Hernández, L. F. Santos, and J. G. Hirsch, Positive quantum Lyapunov exponents in experimental systems with a regular classical limit, Phys. Rev. E 101, 010202(R) (2020).
  * [67] R. A. Kidd, A. Safavi-Naini, and J. F. Corney, Saddle-point scrambling without thermalization, Phys. Rev. A 103, 033304 (2021).
  * [68] M. Steinhuber, P. Schlagheck, J. D. Urbina, and K. Richter, Dynamical transition from localized to uniform scrambling in locally hyperbolic systems, Phys. Rev. E 108, 024216 (2023).
  * [69] A. Russomanno, F. Iemini, M. Dalmonte, and R. Fazio, Floquet time crystal in the Lipkin-Meshkov-Glick model, Phys. Rev. B 95, 214307 (2017).
  * [70] E. Wigner, On the quantum correction for thermodynamic equilibrium, Phys. Rev. 40, 749 (1932).
  * [71] K. Husimi, Some Formal Properties of the Density Matrix, Proc. Phys. Math. Soc. Jpn. 22, 264 (1940).
  * [72] S.-J. Chang and K.-J. Shi, Time evolution and eigenstates of a quantum iterative system, Phys. Rev. Lett. 55, 269 (1985).
  * [73] K. Takahashi, Wigner and Husimi Functions in Quantum Mechanics, J. Phys. Soc. Jpn. 55, 762 (1986).
  * [74] W. M. Zhang, D. H. Feng and R. Gilmore, Coherent states: Theory and some applications. Rev. Mod. Phys. 62, 867 (1990).
  * [75] J. P. Gazeau, Coherent States in Quantum Optics; Wiley-VCH: Berlin, Germany, 2009.
  * [76] J. M. Radcliffe, Some properties of coherent spin states. J. Phys. A 4, 313 (1971).
  * [77] G. M. Ariano, L. R. Evangelista and M. Saraceno, Classical and quantum structures in the kicked-top model. Phys. Rev. A 45, 3646 (1992).
  * [78] A. D. Mirlin and F. Evers, Multifractality and critical fluctuations at the Anderson transition, Phys. Rev. B 62, 7920 (2000).
  * [79] J. Martin, I. Garcia-Mata, O. Giraud and B. Georgeot, Multifractal wave functions of simple quantum maps. Phys. Rev. E, 82, 046206 (2010).
  * [80] S. Gnutzmann and K. Zyczkowski, Rényi-Wehrl entropies as measures of localization in phase space, J. Phys. A: Math. Gen. 34, 10123 (2001).
  * [81] Q. Wang and M. Robnik, Statistical properties of the localization measure of chaotic eigenstates in the Dicke model, Phys. Rev. E 102, 032212 (2020).
  * [82] Jos I. Latorre, Romn Ors, Enrique Rico, and Julien Vidal, Entanglement entropy in the Lipkin-Meshkov-Glick model, Phys. Rev. A 71, 064101(2005)
  * [83] Florian Frwis, Roman Schmied, and Nicolas Gisin, Tighter quantum uncertainty relations following from a general probabilistic bound, Phys. Rev. A 92, 012102(2015)