# Building graphs with high minimum degree on a budget

Kyriakos Katsamaktsis  Department of Mathematics, University College London,
Gower Street, London WC1E 6BT, UK. Email<EMAIL_ADDRESS>Research supported by the Engineering and Physical Sciences Research Council
[grant number EP/W523835/1].  Shoham Letzter  Department of Mathematics,
University College London, Gower Street, London WC1E 6BT, UK. Email:
<EMAIL_ADDRESS>Research supported by the Royal Society.

###### Abstract

We consider the problem of constructing a graph of minimum degree $k\geq 1$ in
the following controlled random graph process, introduced recently by Frieze,
Krivelevich and Michaeli. Suppose the edges of the complete graph on $n$
vertices are permuted uniformly at random. A player, Builder, sees the edges
one by one, and must decide irrevocably upon seeing each edge whether to
purchase it or not.

Suppose Builder purchases an edge if and only if at least one endpoint has
degree less than $k$ in her graph. Frieze, Krivelevich and Michaeli observed
that this strategy succeeds in building a graph of minimum degree at least $k$
by $\tau_{k}$, the hitting time for having minimum degree $k$. They
conjectured that any strategy using $\varepsilon n$ fewer edges, where
$\varepsilon>0$ is any constant, fails with high probability.

In this paper we disprove their conjecture. We show that for $k\geq 2$ Builder
has a strategy which purchases $n/9$ fewer edges and succeeds with high
probability in building a graph of minimum degree at least $k$ by $\tau_{k}$.
For $k=1$ we show that any strategy using $\varepsilon n$ fewer edges fails
with probability bounded away from 0, and exhibit such a strategy that
succeeds with probability bounded away from 0.

##  1 Introduction

The _uniform random graph_ $\mathbf{G}_{n,m}$ is the random graph drawn
uniformly out of all labelled $n$-vertex graphs with $m$ edges. The series of
papers by Erdős and Rényi during 1959-1966 [7, 8, 6, 9] started an in-depth
study of random graphs, where they explored how a typical $\mathbf{G}_{n,m}$
varies as $m$ grows from $0$ to $\binom{n}{2}$. The study of random discrete
structures and their applications has grown to one of the most active and
fruitful areas of research in combinatorics, with connections to many other
fields of study, including theoretical computer science, number theory,
analysis and statistical physics.

Let $N=\binom{n}{2}$ and $e_{1},\ldots,e_{N}$ be a uniformly random
permutation of the edges of the complete graph on $V=[n]$. Then we can
identify $\mathbf{G}_{n,m}$ with the first $m$ edges in the permutation. The
_random graph process_ is the nested sequence
$\left(\mathbf{G}_{n,m}\right)_{m=0}^{N}$ of random graphs. One of the most
striking discoveries of Erdős and Rényi was that several _increasing_
properties appear rather suddenly in the random graph process. Recall that a
_graph property_ $\mathcal{P}$ is a collection of graphs with vertices in $V$,
and is _increasing_ if it is closed under the addition of edges with both ends
in $V$. For example, the property of being Hamiltonian and the property of
being connected are increasing properties. They showed that for several
increasing properties $\mathcal{P}$, including being connected, there is an
$m_{0}=m_{0}(n)$ such that, when $m$ is much larger than $m_{0}$ (in an
appropriate sense), _with high probability_ 111We say that a sequence of
events $(A_{n})_{n\in\mathbb{N}}$ holds _with high probability_ if
$\lim_{n\rightarrow\infty}\mathbf{P}\\!\left[A_{n}\right]\rightarrow 1$.
$\mathbf{G}_{n,m}$ satisfies $\mathcal{P}$, and when $m$ is much smaller than
$m_{0}$, with high probability $\mathbf{G}_{n,m}$ does not satisfy
$\mathcal{P}$. The _hitting time_ for an increasing property $\mathcal{P}$ is
defined to be the random variable $\tau_{\mathcal{P}}=\min\\{m\in[N]:\text{
$\mathbf{G}_{n,m}$ satisfies $\mathcal{P}$}\\}$. A central problem in the
theory of random graphs asks to determine asymptotically the hitting time for
various graph properties.

The question of determining $\tau_{\mathrm{HC}}$, the hitting time for
Hamiltonicity, was first raised by Erdős and Rényi in 1960 [7], and
subsequently studied by several authors. The breakthrough is due to Pósa [16]
and Korshunov [14], who independently showed in 1976 that, for some constant
$C$, when $m\geq Cn\log n$, with high probability $\mathbf{G}_{n,m}$ is
Hamiltonian. Their result was improved by various authors until Komlós and
Szemerédi in 1983 [13] and independently Korshunov in 1977 [15] showed that
with high probability it is asymptotically the same as $\tau_{\geq 2}$, the
hitting time for having minimum degree at least $2$. Erdős and Rényi in 1961
[8] proved that with high probability $\tau_{\geq_{2}}=(1+o(1))\frac{n\log
n}{2}$, so this seems to settle the question of ‘when’ the random graph
process becomes Hamiltonian. However, the precise control on the number of
edges allows us to ask more probing questions. Komlós and Szemerédi in 1983
[13] claimed and a year later Bollobás proved [3] that, in fact, with high
probability, $\tau_{\mathrm{HC}}=\tau_{\geq 2}$. That is, with high
probability, the very edge that increases the minimum degree to 2 is the one
that makes the random graph process Hamiltonian. This type of result is the
strongest possible one can hope for regarding the emergence of an increasing
property in the random graph process.

Clearly a graph with $n$ vertices needs only $n$ edges to be Hamiltonian, far
fewer than the approximately $\frac{n\log n}{2}$ at the hitting time. Is there
an algorithm that finds a Hamilton cycle in the random graph process by time
$\tau_{\mathrm{HC}}$ by considering only $o(n\log n)$ edges? Motivated by this
question, Frieze, Krivelevich and Michaeli [11] introduced the following
controlled random graph process. Suppose there is a player, Builder, who sees
the edges in the random permutation $e_{1},\ldots,e_{N}$ one by one, and must
decide irrevocably upon seeing $e_{i}$ whether to purchase it or not. A
_$(t,b)$ -strategy_ is an online algorithm (deterministic or randomised) that
Builder follows in the above model where she sees only the first $t$ edges in
the random permutation of $E(K_{n})$ and is allowed to purchase at most $b$ of
them. Builder’s objective is for her graph to satisfy a given increasing graph
property $\mathcal{P}$. For example, there is a simple
$(\tau_{{{\rm{con}}}},n-1)$-strategy such that Builder’s graph is connected at
the hitting time for connectivity: Builder purchases an edge if and only if it
decreases the number of connected components in her graph. Regarding
Hamiltonicity, Frieze, Krivelevich and Michaeli [11, Theorem 3] showed that
there exists a $(\tau_{\mathrm{HC}},Cn)$-strategy such that with high
probability $B_{\tau_{\mathrm{HC}}}$ is Hamiltonian, where $C$ is a large
constant. Anastos [1] observed that $C$ cannot be improved to $1+o(1)$.
However, in the same paper he showed that if Builder is allowed to see an
additional $\varepsilon\tau_{\mathrm{HC}}$ edges after $\tau_{\mathrm{HC}}$,
then she can purchase at most $(1+o(1))n$ edges and ensure that with high
probability her graph is Hamiltonian.

The current paper and Theorem 1 in [11] consider the problem of Builder
constructing a graph of minimum degree at least a constant $k\geq 1$ at the
hitting time $\tau_{k}$ for the property of having minimum degree at least
$k$. Let $B_{i}$ be Builder’s graph just before the edge $e_{i+1}$ is
revealed. Suppose that Builder follows the obvious greedy strategy, i.e. that
she purchases $e_{i}$ if and only if at least one of its ends has degree at
most $k-1$ in $B_{i-1}$. This strategy clearly succeeds in building a graph
with minimum degree at least $k$ at time $\tau_{k}$. By following this
strategy, Builder’s graph is distributed according to the _k-th nearest
neighbour_ random graph model. This model was studied by Frieze and Cooper
[5], who proved that with high probability the resulting graph $O_{k}$ has
$(o_{k}+o(1))n$ edges, for some explicit constant $o_{k}\in(k/2,3k/4]$ (cf.
Corollary 2.10). Hence, this gives a $(\tau_{k},(o_{k}+o(1))n)$-strategy for
Builder that (always) succeeds in constructing a graph of minimum degree at
least $k$.

Conjecture 7 in [11] asserts that for any constant $\varepsilon>0$, if Builder
follows any $(\tau_{k},(o_{k}-\varepsilon)n)$-strategy, with high probability
her graph fails to have minimum degree at least $k$. Since $o_{1}=3/4$ and
$o_{k}\geq\frac{k}{2}+\frac{3}{8}$ for $k\geq 2$ (cf. Corollary 2.10), the
next two theorems disprove this conjecture, for the cases $k\geq 2$ and $k=1$
respectively.

######  Theorem 1.1.

Let $k\geq 2$ be an integer and $\delta>0$ be constant. Builder has a
$(\tau_{k},(k/2+2^{-k}+\delta)n)$-strategy that with high probability yields a
graph with minimum degree at least $k$.

######  Theorem 1.2.

Let $C>0$ be constant. Builder has a
$\left(\tau_{1},(1/2+C^{-1/2}/2)n\right)$-strategy that with probability at
least $(1-o(1))\frac{\sqrt{C}}{{\rm e}^{C}}$ yields a graph with minimum
degree at least 1.

However, as the next theorem shows, a weaker version of [11, Conjecture 7]
holds for $k=1$. Recall that $o_{1}=3/4$.

######  Theorem 1.3.

Let $\varepsilon>0$ be constant. Any
$\left(\tau_{1},(3/4-\varepsilon)n\right)$-strategy of Builder fails, with
probability at least $\frac{\varepsilon^{3}}{100}$, in building a graph with
minimum degree at least 1.

Notation. Throughout $n$ is assumed to be sufficiently large, and this is the
only assumption made in all instances of asymptotic notation. We set $V=[n]$
and $N=\binom{n}{2}$. We use $e_{1},\ldots,e_{N}$ to denote a uniformly random
permutation of the edges of the complete graph on $V$, so $e_{i}$ is the edge
at the $i$-th step of the random graph process. We denote by
$\mathbf{G}_{n,i}$ the graph at the $i$-th step of the random graph process,
i.e. the graph on $V$ with edges $\\{e_{1},\ldots,e_{i}\\}$. The minimum
degree of a graph $G$ is $\delta(G)$ and the maximum degree is $\Delta(G)$.

##  2 Preliminaries

The next theorem, which estimates the number of degree $d$ vertices in
$\mathbf{G}_{n,Cn}$, follows from a straightforward application of the second
moment method, see [10, Theorem 3.3]. It is also a simple consequence of a
more general result of Bollobás [2].

######  Theorem 2.1.

Let $d$ be a fixed positive integer and $C,\delta$ be positive constants. Let
$X_{d}$ be the number of vertices of degree $d$ in $\mathbf{G}_{n,Cn}$, and
let $\mu_{d}=\frac{C^{d}{\rm e}^{-C}}{d!}\cdot n$. Then, with high
probability, $\left|X_{d}-\mu_{d}\right|\leq\delta\mu_{d}$.

Next we state two concentration inequalities: Chernoff’s bound and McDiarmid’s
inequality.

######  Theorem 2.2 (Chernoff’s bound, see [12, eq. (2.5, 2.6) and Theorem
2.8]).

Let $X$ be the sum of mutually independent indicator random variables and
write $\mu=\mathbb{E}\left[X\right]$. Then for any $0<t\leq\mu$,

$\mathbf{P}\\!\left[\left|X-\mu\right|\geq t\right]\leq 2{\rm
e}^{-\frac{t^{2}}{3\mu}}.$

######  Theorem 2.3 (McDiarmid’s inequality).

Let $X_{1},\ldots,X_{m}$ be independent random variables with $X_{i}$ taking
values in a set $S_{i}$. Let $f:\prod_{i\in[m]}S_{i}\rightarrow\mathbb{R}$ be
a function such that for any
$\mathbf{x},\mathbf{x}^{\prime}\in\prod_{i\in[m]}S_{i}$ differing only at the
$k^{\text{th}}$ coordinate we have

$\left|f(\mathbf{x})-f(\mathbf{x}^{\prime})\right|\leq c_{k},$

for some $c_{k}\in\mathbb{R}$. Then, for every $t>0$,

$\mathbf{P}\big{[}\,\left|f(X_{1},\ldots,X_{m})-\mathbb{E}\left[f(X_{1},\ldots,X_{m})\right]\right|>t\,\big{]}\leq
2\exp\left(-\frac{2t^{2}}{\sum_{k=1}^{m}c_{k}^{2}}\right).$

We will use at several points the following straightforward consequence of
Chernoff’s bound and the union bound.

######  Proposition 2.4.

With high probability, the maximum degree of $\mathbf{G}_{n,m}$ with $m=O(n)$
is at most $10\log n$.

For a modern treatment of the next two theorems see chapter 4 of [10]. The
first one determines when, with high probability, the random graph process
starts having minimum degree at least $k$.

######  Theorem 2.5 (Erdős and Renyi [8]).

Let $m=\frac{n}{2}\left(\log n+(k-1)\log\log n+f(n)\right)$.

$\mathbf{P}\\!\left[\delta(\mathbf{G}_{n,m})\geq
k\right]=\begin{cases}1-o(1)&\text{ if $f(n)\rightarrow\infty$}\\\ o(1)&\text{
if $f(n)\rightarrow-\infty$.}\end{cases}$

The next one shows that, with high probability, once a random graph has
minimum degree at least 1, it is also connected.

######  Theorem 2.6 (Bollobás and Thomason [4]).

In the random graph process, with high probability the hitting time for
connectivity is the same as for minimum degree $1$.

For two real random variables $X,Y$, we say $X$ _stochastically dominates_ $Y$
if for all $t\in\mathbb{R}$ $\mathbf{P}\\!\left[X\geq
t\right]\geq\mathbf{P}\\!\left[Y\geq t\right]$. The next lemma is standard,
see e.g. Section 23.9 of [10] for a proof.

######  Lemma 2.7.

Let $Y_{1},\ldots,Y_{n}$ be arbitrary real random variables, and let
$X_{1},\ldots,X_{n}$ be mutually independent real random variables.

Suppose that for all $i\in[n]$ and $a_{1},\ldots,a_{i-1}\in\mathbb{R}$,
$Y_{i}$ conditioned on $Y_{1}=a_{1},\ldots,Y_{i-1}=a_{i-1}$ stochastically
dominates $X_{i}$. Then $\sum_{i=1}^{n}Y_{i}$ stochastically dominates
$\sum_{i=1}^{n}X_{i}$.

Suppose instead that for all $i\in[n]$ and
$a_{1},\ldots,a_{i-1}\in\mathbb{R}$, $Y_{i}$ conditioned on
$Y_{1}=a_{1},\ldots,Y_{i-1}=a_{i-1}$ is stochastically dominated by $X_{i}$.
Then $\sum_{i=1}^{n}X_{i}$ stochastically dominates $\sum_{i=1}^{n}Y_{i}$.

The next lemma gives a simple $(O(n),\frac{k+o(1)}{2}n)$-strategy that
produces, with high probability, a graph in which almost all vertices have
degree at least $k$. It is due to Frieze, Krivelevich and Michaeli [11]. For
completeness, we give a detailed proof. We remark that here and throughout the
paper we use the convention that $B_{i}$ is Builder’s graph just before the
edge $e_{i+1}$ is revealed.

######  Lemma 2.8 (Lemma 2.15, [11]).

Let $k\geq 1$ be an integer, $\varepsilon\in(0,1)$ a constant and set
$C=k\varepsilon^{-2}$. Suppose that for all $i\in[Cn]$, if both ends of
$e_{i}$ have degree less than $k$ in $B_{i-1}$, then Builder purchases
$e_{i}$. Then, with high probability, $B_{Cn}$ has at most $\varepsilon n$
vertices of degree at most $k-1$.

###### Proof.

Let

$U_{i}=\\{v\in V:\deg_{B_{i}}(v)\leq k-1\\}$

be the set of vertices of degree at most $k-1$ in Builder’s graph right after
she has seen $e_{i}$ and decided whether to purchase it. Hence, if both ends
of $e_{i}$ are in $U_{i-1}$ then $e_{i}$ is purchased by Builder. Let $X_{i}$
be the indicator random variable for the event that either
$\left|U_{i-1}\right|\leq\varepsilon n$, or both ends of $e_{i}$ are in
$U_{i-1}$. Let $a_{1},\ldots,a_{i-1}\in\\{0,1\\}$ and write
$\mathbf{X}_{<i}=\mathbf{a}_{<i}$ for the condition
$X_{1}=a_{1},\ldots,X_{i-1}=a_{i-1}$. Then

$\displaystyle\mathbf{P}\Big{[}X_{i}=1\>\Big{|}\>\mathbf{X}_{<i}=\mathbf{a}_{<i}\Big{]}$
$\displaystyle\qquad=\mathbf{P}\Big{[}X_{i}=1\>\Big{|}\>\mathbf{X}_{<i}=\mathbf{a}_{<i},\,\left|U_{i-1}\right|>\varepsilon
n\Big{]}\>\cdot\>\mathbf{P}\Big{[}\left|U_{i-1}\right|>\varepsilon
n\>\Big{|}\>\mathbf{X}_{<i}=\mathbf{a}_{<i}\Big{]}$
$\displaystyle\qquad\qquad+\
\mathbf{P}\Big{[}X_{i}=1\>\big{|}\>\mathbf{X}_{<i}=\mathbf{a}_{<i},\,\left|U_{i}\right|\leq\varepsilon
n\Big{]}\>\cdot\>\left(1-\mathbf{P}\Big{[}\left|U_{i-1}\right|>\varepsilon
n\>\Big{|}\>\mathbf{X}_{<i}=\mathbf{a}_{<i}\Big{]}\right)$
$\displaystyle\qquad\geq\,\frac{\binom{\varepsilon n}{2}}{\binom{n}{2}}\
\mathbf{P}\Big{[}\left|U_{i-1}\right|>\varepsilon
n\>\big{|}\>\mathbf{X}_{<i}=\mathbf{a}_{<i}\Big{]}+1\cdot\left(1-\mathbf{P}\Big{[}\left|U_{i-1}\right|>\varepsilon
n\>\big{|}\>\mathbf{X}_{<i}=\mathbf{a}_{<i}\Big{]}\right)$
$\displaystyle\qquad\geq\,2\varepsilon^{2}/3.$

In particular, if $Y_{1},\ldots,Y_{Cn}$ are independent indicator random
variables with mean $2\varepsilon^{2}/3$, then $X_{i}$ conditioned on
$\mathbf{X}_{<i}=\mathbf{a}_{<i}$ stochastically dominates $Y_{i}$. Therefore,
by Lemma 2.7, $\sum_{i=1}^{Cn}X_{i}$ stochastically dominates
$\sum_{i=1}^{Cn}Y_{i}$. Chernoff’s bound implies that, with probability at
least $1-{\rm e}^{-\Omega(kn)}$, $\sum_{i=1}^{Cn}Y_{i}$ is at least
$1/2\cdot\varepsilon^{2}\cdot Cn=kn/2$, and so the same holds for
$\sum_{i=1}^{Cn}X_{i}$. Therefore, either for some $i\in[Cn]$,
$\left|U_{i}\right|\leq\varepsilon n$, or Builder bought at least $kn/2$ edges
with both ends of degree at most $k-1$ in Builder’s graph right before
purchasing them. In the former case the conclusion of the lemma follows since
$\left|U_{i}\right|$ is clearly decreasing in $i$, and in the latter case an
easy calculation shows that $\left|U_{Cn}\right|=0$. ∎

Recall that $O_{k}$ is the random graph model which consists of the first $k$
edges incident to each vertex in the random graph process. Moreover, recall
that Frieze and Cooper [5] showed that there exists a constant $o_{k}$ such
that with high probability $e(O_{k})=(o_{k}+o(1))n$. Corollary 3.2 in [11]
provides estimates for $o_{k}$, following [5]. The following proposition
essentially follows from the proof of Corollary 3.2 in [11]. The latter is not
stated in this way because the authors are interested in the regime where $k$
is large.

######  Proposition 2.9 (Corollary 3.2, [11]).

$o_{k}=\frac{k}{2}+\frac{1}{4}\sum_{i=0}^{k-1}\binom{2i}{i}2^{-2i}$

###### Sketch.

Following the proof of Corollary 3.2 in [11], set

$f(k)=\sum_{i,j=0}^{k}\binom{i+j}{i}2^{-i-j}.$

Then [11, Corollary 3.2] proves that $o_{k}=k-\frac{f(k-1)}{4}$. Since, as
noted in [11, Corollary 3.2], $f(k)=f(k-1)+2-\binom{2k}{k}2^{-2k}$ and
$f(0)=1$, we have

$f(k)=1+2k-\sum_{i=1}^{k}\binom{2i}{i}2^{-2i}.$

Substituting in $o_{k}=k-\frac{f(k-1)}{4}$ yields the required expression
(summing now the binomial coefficients from $i=0$). ∎

The previous proposition directly implies the following.

######  Corollary 2.10.

$o_{1}=3/4$ and $o_{k}\geq k/2+3/8$ for $k\geq 2$.

The next lemma will be useful when Builder follows a certain strategy for the
first $Cn$ steps of the random graph, and then we wish to estimate the degree
of vertices in the graph spanned by the edges exposed between steps $Cn+1$ and
$\tau_{k}$.

######  Lemma 2.11.

Let $k\geq 1$ be an integer, and $m\in[c_{1}n\log n,c_{2}n\log n]$, where
$c_{1},c_{2}>0$ are constants. Let $H$ be a graph on $V$ with maximum degree
at most $10\log n$. Suppose we draw uniformly at random and with repetition
edges from the complete graph on $V$ until there are $m$ distinct edges. Then,
with high probability, for every $v\in V$ such that at least one of the edges
drawn is incident to $v$ in $H$, there are at least $k$ distinct edges
incident to $v$ which are not in $H$.

###### Proof.

Let $L_{v}\subseteq E(H)$ be the set of edges incident to $v\in V$, so
$\left|L_{v}\right|\leq 10\log n$. Let $t$ be the (random) number of edges we
draw with repetition until we see $m$ distinct edges.

We claim that with high probability $t\in[m,m+(\log n)^{3}]$. Indeed, let
$X_{i},i\in[m]$, be the random variable counting the number of edges drawn
until the $i$-th distinct edge, and set $X_{0}=0$. Then $X_{i}-X_{i-1}$ is a
geometric random variable with mean $\frac{1}{1-(i-1)/\binom{n}{2}}$, and

$\displaystyle\mathbb{E}\left[X_{m}\right]=\sum_{i=1}^{m}\mathbb{E}\left[X_{i}-X_{i-1}\right]$
$\displaystyle=\sum_{i=1}^{m}\frac{1}{1-(i-1)/\binom{n}{2}}$
$\displaystyle=\sum_{i=1}^{m}\left(1+\frac{i-1}{\binom{n}{2}}+O\left(\frac{i^{2}}{n^{4}}\right)\right)$
$\displaystyle=m+\Theta\left(\frac{m^{2}}{n^{2}}\right)+O\left(\frac{m^{3}}{n^{4}}\right)$
$\displaystyle=m+\Theta((\log n)^{2}).$

Let $Y$ be the number of repeated edges until we see $m$ distinct edges. Then
the above calculation implies $\mathbb{E}\left[Y\right]=O((\log n)^{2})$,
whence from Markov’s inequality with high probability $Y\leq(\log n)^{3}$.
Therefore $t\in[m,m+(\log n)^{3}]$, with high probability.

To complete the proof of the lemma we now show that, when drawing $t$ edges
with repetition, for some $t\in[m,m+(\log n)^{3}]$, with high probability, for
every $v$ with at least one edge drawn from $L_{v}$, there are at least $k$
(distinct) incident edges not in $L_{v}$. Let $\hat{e}_{1},\ldots,\hat{e}_{t}$
be the drawn edges and let $A_{v,j}$ be the event that $\hat{e}_{j}\in L_{v}$.
Let $B_{v,j}$ be the event that the number of distinct edges in
$\\{\hat{e}_{1},\dots,\hat{e}_{t}\\}\setminus\hat{e}_{j}$ incident to $v$ and
disjoint from $L_{v}$ is at most $k-1$. The lemma follows from the next claim.

######  Claim 2.12.

For every $t\in[m,m+(\log n)^{3}]$, the probability that there exist $v\in
V,j\in[t]$ such that $A_{v,j}\cap B_{v,j}$ holds is at most $1/n$.

###### Proof.

Fix $v\in V$, $j\in[t]$. Because $\hat{e}_{1},\ldots,\hat{e}_{t}$ are drawn
with repetition, the events $A_{v,j},B_{v,j}$ are independent. We have
$\mathbf{P}\\!\left[A_{v,j}\right]\leq\frac{10\log n}{\binom{n}{2}}$.

For $n$ sufficiently large,

$\displaystyle\mathbf{P}\\!\left[B_{v,j}\right]$
$\displaystyle\leq\sum_{\ell=0}^{k-1}\,\binom{t}{\ell}\,\left(\frac{n-1}{\binom{n}{2}}\right)^{\ell}\,\left(1-\frac{n-1-10\log
n-(k-1)}{\binom{n}{2}}\right)^{t-\ell}$
$\displaystyle\leq\sum_{\ell=0}^{k-1}(c_{2}n\log n+(\log n)^{3})^{\ell}\
2^{\ell}n^{-\ell}\ \left(1-\frac{(2-o(1))}{n}\right)^{(c_{1}-o(1))n\log n}$
$\displaystyle\leq\sum_{\ell=0}^{k-1}\left(2c_{2}n\log n\right)^{\ell}\
2^{\ell}\>n^{-\ell}\;\exp\left(-c_{1}\log n\right)$
$\displaystyle\leq\sum_{\ell=0}^{k-1}(4c_{2})^{\ell}(\log
n)^{\ell}\>n^{-c_{1}}$ $\displaystyle\leq(\log n)^{k}\,n^{-c_{1}}$
$\displaystyle\leq n^{-c_{1}/2}.$

Hence, the probability there exist $v\in V,j\in[t]$ such that $A_{v,j}\cap
B_{v,j}$ holds is, by the union bound over the choice of $v,j$, at most
$n\cdot t\cdot\frac{10\log n}{\binom{n}{2}}\cdot n^{-c_{1}/2}\leq 1/n.$ ∎

This completes the proof of the lemma. ∎

##  3 Proof of Theorem 1.1

Given $k\geq 2$ and $\delta>0$, fix $0<\varepsilon<1$ and $C>0$ such that:
$\varepsilon<\frac{\delta}{2k}$ and $C=k\varepsilon^{-2}$.

Before delving into the details, we outline Builder’s strategy, which we give
formally in Algorithm 1. For the first $Cn$ edges Builder’s strategy is as
follows. For $i\in[Cn]$, Builder purchases $e_{i}=x_{i}y_{i}$ if and only if
either $\deg_{B_{i-1}}(x_{i}),\deg_{B_{i-1}}(y_{i})<k$ or at least one of
$x_{i},y_{i}$ has degree 0 in $\mathbf{G}_{n,i-1}$. We call edges of the
former kind _efficient_ and edges of the latter kind (which are not of the
former kind) _inefficient_. Builder’s strategy for $i\geq Cn+1$ is to purchase
$e_{i}$ if and only if at least one end of $e_{i}$ has degree less than $k$ in
$B_{i-1}$.

Algorithm 1 Builder’s strategy for a graph with minimum degree at least $k$ by
$\tau_{k}$

1:Input: Let $e_{1},\dots,e_{N}$ be a uniformly random permutation of
$E(K_{n})$.

2:$B_{0}\leftarrow\emptyset$

3:for $i=1,\dots,Cn$ do

4: if both ends of $e_{i}$ have degree less than $k$ in $B_{i-1}$ or least one
of has degree $0$ then

5: $B_{i}\leftarrow B_{i-1}\cup e_{i}$

6: else

7: $B_{i}\leftarrow B_{i-1}$

8: end if

9:end for

10:for $i=Cn+1,\dots,\tau_{k}$ do

11: if at least one end of $e_{i}$ has degree less than $k$ in $B_{i-1}$ then

12: $B_{i}\leftarrow B_{i-1}\cup e_{i}$

13: else

14: $B_{i}\leftarrow B_{i-1}$

15: end if

16:end for

17:return $B_{\tau_{k}}$

For $i\in[Cn]$ let

$Z_{i}=\\{v\in V:\deg_{\mathbf{G}_{n,i}}(v)=0\\}$

and

$Y_{i}=\\{v\in V:1\leq\deg_{B_{i}}(v)\leq k-1\\}.$

The next claim shows that, with high probability, after the first $Cn$ edges
are exposed almost all vertices in Builder’s graph have degree $k$, yet her
graph has relatively few edges.

######  Claim 3.1.

Reveal the first $Cn$ edges in the random graph process and suppose Builder
follows Algorithm 1. Then with high probability

  1. 1.

$e(B_{Cn})\leq(k/2+2^{-k}+\delta/2)n$ and

  2. 2.

$\left|Y_{Cn}\cup Z_{Cn}\right|\leq\varepsilon n$.

The next claim implies that, with high probability, by time $\tau_{k}$
Builder’s graph has minimum degree at least $k$.

######  Claim 3.2.

With high probability, for every $v\in Y_{Cn}$, there are at least $k-1$ edges
incident to $v$ among $e_{Cn+1},\ldots,e_{\tau_{k}}$.

Before proving the claims, we show how to use them to derive Theorem 1.1.

###### Proof of Theorem 1.1.

First we argue that following Algorithm 1, with high probability,
$\deg_{B_{\tau_{k}}}(v)\geq k$ for all $v\in V$. Lines 4 and 11 of Algorithm 1
imply that $\deg_{B_{i}}(v)=0$ if and only if $\deg_{\mathbf{G}_{n,i}}(v)=0$.
Hence, for every $v\notin Y_{Cn}\cup Z_{Cn}$, $\deg_{B_{Cn}}(v)\geq k$. By
definition of $\tau_{k}$ and $Z_{Cn}$, every vertex in $Z_{Cn}$ will see at
least $k$ incident edges among $\\{e_{Cn+1},\ldots,e_{\tau_{k}}\\}$, since
none of the first $Cn$ edges are incident to $Z_{Cn}$. By 3.2, with high
probability, every vertex in $Y_{Cn}$ will see at least $k-1$ incident edges
among $\\{e_{Cn+1},\ldots,e_{\tau_{k}}\\}$. Therefore, in the second for-loop
of Algorithm 1 Builder will purchase at least $k$ incident edges for each
$v\in Z_{Cn}$, and at least $k-\deg_{B_{Cn}}(v)$ incident edges to each $v\in
Y_{Cn}$. Hence, with high probability, $\deg_{B_{\tau_{k}}}(v)\geq k$ for all
$v\in V$.

It remains to show that, with high probability,
$e(B_{\tau_{k}})\leq(k/2+2^{-k}+\delta)n$. By 3.1, with high probability
$\left|Y_{Cn}\cup Z_{Cn}\right|\leq\varepsilon n$. Hence, the number of edges
Builder purchases during the second for-loop of Algorithm 1 is at most
$k\varepsilon n$. Therefore, with high probability, the total number of edges
bought is at most

$e(B_{Cn})+k\varepsilon
n\leq(k/2+2^{-k}+\delta/2+k\varepsilon)n\leq(k/2+2^{-k}+\delta)n,$

where we used the upper bound on $e(B_{Cn})$ from 3.1. ∎

We now prove the two claims.

###### Proof of 3.1.

Lemma 2.8 implies the second point of the lemma. Clearly, the number of
efficient edges bought is at most $kn/2$. It remains to show that, with high
probability, the number of inefficient edges is at most $(2^{-k}+\delta/2)n$.

For $r,s\in[n],r\geq s,$ let $\Phi(r,s)$ be the collection of edges in the
_whole_ random graph process (i.e. all $\binom{n}{2}$ edges) which increase
the degree of one of their ends to $r$ and the other end to $s$, and set
$\phi(r,s)=\left|\Phi(r,s)\right|$. The inefficient edges are a subset of
$\mathbf{G}_{n,Cn}$, and by Proposition 2.4, with high probability
$\Delta(\mathbf{G}_{n,Cn})\leq 10\log n$. Therefore, with high probability,
the number of inefficient edges is at most $\sum_{r=k+1}^{10\log n}\phi(r,1).$

We want to show, using McDiarmid’s inequality, that $\phi(r,s)$ is, with high
probability, concentrated around its mean, for $s\leq r\leq 10\log n$.
However, because $\mathbb{E}\left[\phi(r,s)\right]$ is linear (as we shall
soon see) and is determined by quadratically many variables, applying
McDiarmid’s inequality directly to $\phi(r,s)$ would not give concentration
with high probability. To avoid this issue, let $m=n(\log n)^{10}/2$, let
$\Phi_{m}(r,s)=\Phi(r,s)\cap\mathbf{G}_{n,m}$ be the subset of the first $m$
edges in the random graph process that are in $\Phi(r,s)$ and write
$\phi_{m}(r,s)=\left|\Phi_{m}(r,s)\right|$.

Define

$\mu_{r,s}=\frac{1}{2^{\delta(r,s)}}\binom{r+s-1}{s-1}2^{-r-s+1},$

where $\delta(r,s)$ is $1$ if $r=s$ and $0$ otherwise (Kronecker delta). We
will show that, with high probability, $\phi(r,s)=(1+o(1))\mu_{r,s}n$ for all
$1\leq s\leq r\leq 10\log n$.

To do so, we first note that $\phi(r,s)=\phi_{m}(r,s)$, with sufficiently high
probability. To obtain concentration, we will reveal the first $m$ steps of
the random graph process in two stages. First we sample the graph at step $m$
of the random graph process, $\mathbf{G}_{n,m}$, and show that with
sufficiently high probability $\mathbf{G}_{n,m}$ is _almost-regular_ i.e.
$\deg_{\mathbf{G}_{n,m}}(v)=(1+O((\log n)^{-2}))(\log n)^{10}$ for all $v\in
V$. We will then calculate the expectation of $\phi_{m}(r,s)$ conditioned on
$\mathbf{G}_{n,m}$ being any given graph $G$, and show that this expectation
is $(1+o(1))\mu_{r,s}n$ for every almost-regular $G$. Next, conditioned on
$\mathbf{G}_{n,m}$ being a fixed graph $G$, we sample the first $m$ steps of
the random graph process by selecting a uniformly random permutation of
$E(G)$. Using McDiarmid’s inequality, we will show that $\phi_{m}(r,s)$
conditioned on $\mathbf{G}_{n,m}=G$ is, with high probability, concentrated
around its mean. Then the required result, i.e. the concentration of
$\phi(r,s)$ around its mean for all relevant $r,s$, will follow easily.

Fix $r,s$ such that $1\leq s\leq r\leq 10\log n$. First, note that
$\phi(r,s)=\phi_{m}(r,s)$ whenever $\delta(\mathbf{G}_{n,m})\geq 10\log n$, so
$\phi(r,s)=\phi_{m}(r,s)$ with probability $1-\exp\left(-\Omega((\log
n)^{2}\right)$.

Now let $G$ be any graph on $V$ with $m$ edges. We claim that
$\mathbb{E}\big{[}\phi_{m}(r,s)\>|\>\mathbf{G}_{n,m}=G\big{]}$ equals

$\displaystyle\frac{1}{2^{\delta(r,s)}}\sum_{u,v\in V(G):\,\,uv\in
E(G)}\frac{1}{\deg_{G}(u)+\deg_{G}(v)-1}\,\frac{\dbinom{\,\deg_{G}(u)-1\,}{r-1}\,\dbinom{\,\deg_{G}(v)-1}{s-1}\,}{\dbinom{\,\deg_{G}(u)\>+\>\deg_{G}(v)-2\,}{r+s-2}}.$
(1)

This was (essentially) already noted in [5] for $r,s\in[k]$ ($k$ constant),
when we do not condition on $\mathbf{G}_{n,m}$ being any fixed graph. To see
why this is true, note that for $r\neq s$, the event $e=uv\in\Phi_{m}(r,s)$ is
the union of the (disjoint) events that $e$ gives degree $r$ to $u$ and degree
$s$ to $v$, and vice-versa. For $r=s$ of course we have only one such event.
Thus it suffices to show that the probability, over a random permutation of
$E(G)$, that $uv$ gives degree $r$ to $u$ and $s$ to $v$ is

$\frac{1}{\deg_{G}(u)+\deg_{G}(v)-1}\,\frac{\dbinom{\,\deg_{G}(u)-1\,}{r-1}\,\dbinom{\,\deg_{G}(v)-1}{s-1}\,}{\dbinom{\,\deg_{G}(u)\>+\>\deg_{G}(v)-2\,}{r+s-2}}$

and then (1) follows by linearity of expectation. The event in question is
determined by the first $r+s-1$ edges incident to $\\{u,v\\}$ and occurs if
both $uv$ is the edge at position $r+s-1$ in the permutation of the
$\deg_{G}(u)+\deg_{G}(v)-1$ edges incident to either $u$ or $v$; and among the
first $r+s-2$ edges incident to either $u$ or $v$, exactly $r-1$ are incident
to $u$ and $s-1$ are incident to $v$. It readily follows that this event
occurs with the claimed probability. Indeed, the denominator is the number of
ways of choosing $r+s-1$ edges among the $\deg_{G}(u)+\deg_{G}(v)-1$ edges
touching $u$ or $v$, with a single distinguished edge (the one in position
$r+s-1$), and the numerator is the number of ways of choosing this many edges
so that the distinguished edge is $uv$ and the remaining $r+s-2$ edges consist
of $r-1$ edges touching $u$ and $s-1$ edges touching $v$.

Now suppose that $G$ is almost-regular, i.e. that $\deg_{G}(v)=(1+O((\log
n)^{-2})(\log n)^{10}$ for every $v\in V$. Using this assumption, (1) and that
$\binom{a}{b}=\left(1+O(\frac{b^{2}}{a})\right)\frac{a^{b}}{b!}$, we get that
for all such $G$,

$\mathbb{E}\big{[}\phi_{m}(r,s)\>|\>\mathbf{G}_{n,m}=G\big{]}=(1+o(1))\,\frac{1}{2^{\delta(r,s)}}\,\binom{r+s-1}{s-1}\,2^{-r-s+1}\,n.$
(2)

We now show that $\phi_{m}(r,s)$ conditioned on $\mathbf{G}_{n,m}=G$ is
concentrated around its mean. For this we use McDiarmid’s inequality, which is
applicable in the random graph process, because we can generate a uniformly
random permutation of $E(G)$ in the following way222Simply permuting uniformly
at random $E(G)$ does not allow us to use McDiarmid’s inequality because the
position of edges are not independent from one another.. Fix a continuous
probability distribution $\mathcal{D}$ and for each $e\in E(G)$ let
$X_{e}\sim\mathcal{D}$ be an independent sample from $\mathcal{D}$. Ordering
the edges from smallest sampled value to largest yields a uniformly random
permutation of $E(G)$. To apply the inequality for $\phi_{m}(r,s)$, suppose we
unilaterally change the value $X_{uv}$ sampled for the edge
$uv\in\mathbf{G}_{n,m}$, and leave the values sampled for all other edges
$\\{X_{e}:e\in E(G)\setminus uv\\}$ unchanged. We claim that then
$\phi_{m}(r,s)$ changes by at most 4. To see this, observe that the graph
spanned by $\Phi_{m}(r,s)$ has $\Delta(\Phi_{m}(r,s))\leq 2$: each vertex can
only be incident to edges whose position in the random permutation increase
its degree to $r$ or $s$. Changing $X_{uv}$ can affect only edges incident to
$u$ or $v$, hence changing $\phi_{m}(r,s)$ by at most $4$. Thus, McDiarmid’s
inequality (Theorem 2.3) implies that

$\displaystyle\mathbf{P}\\!\left[\,\big{|}\phi_{m}(r,s)-\mathbb{E}\big{[}\phi_{m}(r,s)\>|\>\mathbf{G}_{n,m}=G\big{]}\big{|}\geq
n^{2/3}\right]$ $\displaystyle\leq 2\exp\left(-\frac{2n^{4/3}}{16m}\right)$
$\displaystyle=\exp\left(-\Omega\left((\log n)^{2}\right)\right).$

In particular, using (2), with probability $1-\exp\left(-\Omega\left((\log
n)^{2}\right)\right)$, we have that $\phi_{m}(r,s)$ conditioned on
$\mathbf{G}_{n,m}=G$ is $(1+o(1))\mu_{r,s}n$.

Therefore, since $\mathbf{G}_{n,m}$ is almost-regular with probability
$1-\exp\left(-\Omega\left((\log n)^{2}\right)\right)$ (by Chernoff’s bound,
Theorem 2.2), because we have $\phi_{m}(r,s)=\phi(r,s)$ with probability
$1-\exp\left(-\Omega\left((\log n)^{2}\right)\right)$, and by a union bound
over $s,r$ with $1\leq s\leq r\leq 10\log n$, we have that
$\phi(r,s)=(1+o(1))\mu_{r,s}n$, with high probability.

In particular, with high probability, $\phi(r,1)=(1+o(1))2^{-r}$, for every
$r$ with $k+1\leq r\leq 10\log n$. Hence, with high probability, the number of
inefficient edges bought is at most

$(1+o(1))\left(\sum_{r=k+1}^{10\log n}2^{-r}n\right)\leq(2^{-k}+\delta/2)n,$

as required. ∎

###### Proof of 3.2.

By Proposition 2.4, with high probability $\Delta(\mathbf{G}_{n,Cn})\leq
10\log n$. Condition on this event.

Draw with repetition edges $(\hat{e}_{i})_{i\geq 1}$ until $t=\frac{n}{2}(\log
n+(k-2)\log\log n+\log\log\log n)$ distinct edges are drawn. Let $\hat{G}$ be
the graph of these $t$ distinct edges and let
$\hat{G}_{i}=\\{\hat{e}_{1},\ldots,\hat{e}_{i}\\}$.

We couple $(\hat{G}_{i})_{i\geq 1}$ with $(\mathbf{G}_{n,j})_{j\geq Cn+1}$ in
the following natural way. Suppose $\mathbf{G}_{n,j}$ is the current stage of
the random graph process and $\hat{e}_{i}$ is the edge we have just drawn. If
$\hat{e}_{i}\notin\mathbf{G}_{n,j}$, we set $e_{j+1}:=\hat{e}_{i}$ and so
update $\mathbf{G}_{n,j+1}:=\mathbf{G}_{n,j}\cup\\{\hat{e}_{i}\\}$. Otherwise,
$e_{j+1}$ remains unrevealed, we do not update $\mathbf{G}_{n,j}$, and keep
drawing edges with repetition until we draw a new one. Clearly every edge not
in $\mathbf{G}_{n,j}$ has the same probability of being added, so the coupling
indeed induces the random graph process.

By Lemma 2.11 and Theorem 2.5, with high probability, every $v\in Y_{Cn}$ has
$k-1$ distinct incident edges in $\hat{G}\setminus\mathbf{G}_{n,Cn}$: indeed,
by Theorem 2.5 with high probability every vertex $v$ has at least $k-1$
incident edges in $\hat{G}$, and for each $v$ either all incident edges are
disjoint from $\mathbf{G}_{n,Cn}$, or otherwise by Lemma 2.11 at least $k-1$
are. The latter is applicable since $t=\Theta(n\log n)$ and
$\Delta(\mathbf{G}_{n,Cn})\leq 10\log n$.

Finally, by Theorem 2.5, with high probability, $\tau_{k}>t+Cn$. Hence, indeed
we have
$E(\hat{G}\setminus\mathbf{G}_{n,Cn})\subseteq\\{e_{Cn+1},\ldots,e_{\tau_{k}}\\}$,
with high probability. ∎

##  4 Proof of Theorems 1.3 and 1.2

Set $\varepsilon=C^{-1/2}$. We assume $\varepsilon<3/4$, since otherwise both
theorems easily hold. Theorem 1.3 trivially holds because then Builder’s graph
is empty. Theorem 1.2 holds because then Builder can purchase $(o_{1}+1/8)n$
edges by emulating $O_{1}$ (using $o_{1}=3/4$).

We will keep track of the following sets of vertices.

$\displaystyle X_{i}$ $\displaystyle=\\{v\in V:\deg_{B_{i}}(v)\geq 1\\}$
$\displaystyle Y_{i}$ $\displaystyle=\\{v\in V:\deg_{B_{i}}(v)=0\text{ and
}\deg_{\mathbf{G}_{n,i}}(v)\geq 1\\}$ $\displaystyle Z_{i}$
$\displaystyle=\\{v\in V:\deg_{\mathbf{G}_{n,i}}(v)=0\\}.$

For both theorems we will use the following lemma, which we prove at the end
of this section. Notice the first part of the lemma makes no assumption
whatsoever on Builder’s strategy.

######  Lemma 4.1.

Let $m\in[Cn]$ and suppose Builder has gone through the first $m$ steps of the
random graph process. For every strategy Builder may follow for edges
$e_{j},j\geq m+1$, $B_{\tau_{1}}$ has an isolated vertex with probability at
least
$\frac{(1-o(1))\left|Y_{m}\right|}{\left|Y_{m}\right|+\left|Z_{m}\right|}$.

Suppose that for $j\geq m+1$ Builder follows the strategy of purchasing
$e_{j}$ if and only if at least one end of $e_{j}$ is isolated in $B_{j-1}$.
Then with probability
$\frac{(1-o(1))\left|Z_{m}\right|}{\left|Y_{m}\right|+\left|Z_{m}\right|}$,
$B_{\tau_{1}}$ has no isolated vertices.

We now prove Theorem 1.2 according to which Builder has a
$(\tau_{1},(1/2+C^{-1/2}/2))$-strategy which succeeds in building a graph with
minimum degree at least $1$, with probability at least
$(1-o(1))\frac{\sqrt{C}}{e^{C}}$.

###### Proof of Theorem 1.2.

Builder has the following strategy, given formally in Algorithm 2 (any
variables inside the algorithm agree with the notation defined outside), for
constructing a graph with minimum degree at least 1 by time $\tau_{1}$. For
the first $Cn$ edges, Builder purchases an edge if and only if both endpoints
are isolated. For the remaining edges, she purchases an edge if and only if at
least one end is isolated. Lemma 2.8 implies that, with high probability,
$\left|Y_{Cn}\cup Z_{Cn}\right|\leq\frac{n}{\sqrt{C}}$, and Theorem 2.1 yields
that with high probability $\left|Z_{Cn}\right|\geq(1-o(1)){\rm e}^{-C}n$.
Condition on these two events. Then from Lemma 4.1, $B_{\tau_{1}}$ has no
isolated vertices with probability at least
$(1-o(1))\frac{\left|Z_{Cn}\right|}{\left|Y_{Cn}\right|+\left|Z_{Cn}\right|}\geq(1-o(1))\frac{\sqrt{C}}{{\rm
e}^{C}}.$ It remains to show that $e(B_{\tau_{1}})\leq(1/2+C^{-1/2}/2)n$.
Inspecting Algorithm 2 (or simply the definitions), it is not hard to see that
$Y_{i}\cup Z_{i}\subseteq Y_{i-1}\cup Z_{i-1}$: only lines 15 and 28 add
elements to $Y_{i}$, and in both cases vertices move to $Y_{i}$ from
$Z_{i-1}$. Also, it is clear that $Z_{i}\subseteq Z_{i-1}$, see lines 11, 16,
24 and 29 of Algorithm 2. Therefore, during the second for-loop, i.e. for
edges $e_{j},j\geq Cn+1$, Builder will purchase only edges incident to
$Y_{Cn}\cup Z_{Cn}$. Moreover, for $j\geq Cn+1$, $\left|Y_{j}\cup
Z_{j}\right|$ strictly decreases by at least 1 for each purchased edge. For
$j\leq Cn+1$, clearly $\left|Y_{j}\cup Z_{j}\right|$ decreases by exactly 2
(lines 7, 10 and 11 of Algorithm 2). Therefore

$\displaystyle e(B_{\tau_{1}})$ $\displaystyle\leq e(B_{Cn})+\left|Y_{Cn}\cup
Z_{Cn}\right|$ $\displaystyle=(n-\left|Y_{Cn}\cup
Z_{Cn}\right|)/2+\left|Y_{Cn}\cup Z_{Cn}\right|\leq(1+C^{-1/2})n/2,$

as required. ∎

Algorithm 2 Builder’s $(\tau_{1},(3/4-\varepsilon)n)$-strategy for a graph
with minimum degree 1

1:Input: Let $e_{1},\dots,e_{N}$ be a uniformly random permutation of
$E(K_{n})$.

2:$B_{0}\leftarrow\emptyset$ $\triangleright$ $B_{i}$ is Builder’s graph at
step $i$

3:$X_{0}\leftarrow\emptyset$ $\triangleright$ non-isolated vertices in $B_{i}$
at step $i$

4:$Y_{0}\leftarrow\emptyset$ $\triangleright$ isolated vertices in $B_{i}$,
non-isolated in random graph process at step $i$

5:$Z_{0}\leftarrow V$ $\triangleright$ isolated vertices in graph process at
step $i$ (so also in $B_{i}$)

6:for $i=1,\dots,Cn$ do

7: if $e_{i}\subseteq Y_{i-1}\cup Z_{i-1}$ then $\triangleright$ if both ends
of $e_{i}$ are isolated in $B_{i-1}$

8: $B_{i}\leftarrow B_{i-1}\cup e_{i}$

9: $X_{i}\leftarrow X_{i-1}\cup e_{i}$

10: $Y_{i}\leftarrow Y_{i-1}\setminus e_{i}$

11: $Z_{i}\leftarrow Z_{i-1}\setminus e_{i}$

12: else

13: $B_{i}\leftarrow B_{i-1}$

14: $X_{i}\leftarrow X_{i-1}$

15: $Y_{i}\leftarrow(Y_{i-1}\cup e_{i})\setminus X_{i}$ $\triangleright$ add
only previously isolated ends of $e_{i}$

16: $Z_{i}\leftarrow Z_{i-1}\setminus e_{i}$

17: end if

18:end for

19:for $i=Cn+1,\dots,\tau_{1}$ do

20: if $e_{i}\cap(Y_{i-1}\cup Z_{i-1})\neq\emptyset$ then $\triangleright$ if
at least one end of $e_{i}$ is isolated in $B_{i-1}$

21: $B_{i}\leftarrow B_{i-1}\cup e_{i}$ $\triangleright$ same updates as in
first for-loop

22: $X_{i}\leftarrow X_{i-1}\cup e_{i}$

23: $Y_{i}\leftarrow Y_{i-1}\setminus e_{i}$

24: $Z_{i}\leftarrow Z_{i-1}\setminus e_{i}$

25: else$\triangleright$ same updates as in first for-loop

26: $B_{i}\leftarrow B_{i-1}$

27: $X_{i}\leftarrow X_{i-1}$

28: $Y_{i}\leftarrow(Y_{i-1}\cup e_{i})\setminus X_{i}$ $\triangleright$ add
only previously isolated ends of $e_{i}$

29: $Z_{i}\leftarrow Z_{i-1}\setminus e_{i}$

30: end if

31:end for

32:return $B_{\tau_{1}}$

Now we prove Theorem 1.3 which asserts that any
$(3/4-\varepsilon,\tau_{1})$-strategy fails in building a graph with minimum
degree at least $1$, with probability at least $\frac{\varepsilon^{3}}{100}$.

###### Proof of Theorem 1.3.

This is an immediate consequence of Lemma 4.1 and the next claim.

######  Claim 4.2.

If $\left|Y_{i}\right|\leq\delta n$ for all $i\in[Cn]$, then by time $Cn$
Builder has purchased at least $(o_{1}-6\delta C-\delta-2{\rm e}^{-C}-o(1))n$
edges.

Set $\delta=\frac{\varepsilon}{50C}$ and suppose Builder follows a strategy
such that $e(B_{\tau_{1}})\leq(o_{1}-\varepsilon)n$. Then
$e(B_{\tau_{1}})<(o_{1}-7\delta C-\delta-2{\rm e}^{-C})n$ (recalling
$\varepsilon=C^{-1/2}$), so the contrapositive of 4.2 implies that for some
$i\in[Cn]$, $\left|Y_{i}\right|\geq\delta n$. Hence, by Lemma 4.1,
$B_{\tau_{1}}$ has an isolated vertex with probability at least
$(1-o(1))\frac{\left|Y_{i}\right|}{\left|Y_{i}\right|+\left|Z_{i}\right|}\geq\frac{\delta}{2}=\frac{\varepsilon}{100C}=\frac{\varepsilon^{3}}{100}$.

###### Proof of 4.2.

For $i\in[Cn]$, let $I_{i}$ be the indicator random variable for the event
that $e_{i}$ is incident to $Y_{i-1}$ and $\left|Y_{i-1}\right|\leq\delta n$.
Conditioned on any choice of values for $I_{1},\ldots,I_{i-1}$, the expected
value of $I_{i}$ is at most $\frac{\delta n\cdot(n-1)}{\binom{n}{2}}=2\delta.$
Hence, Lemma 2.7 implies that $\sum_{i=1}^{Cn}I_{i}$ is stochastically
dominated by a sum of $Cn$ independent indicator random variables with mean
$2\delta$ each, for which we can apply Chernoff’s bound. The latter gives
that, with high probability, $\sum_{i=1}^{Cn}I_{i}\leq 3\delta Cn$. Condition
on this being the case.

Because the claim assumes that $\left|Y_{i}\right|\leq\delta n$ for all
$i\in[Cn]$, $I_{i}$ is 1 if and only if $e_{i}$ is incident to $Y_{i-1}$.
Hence, $\sum_{i=1}^{Cn}I_{i}$ is precisely the number of edges $e_{i}$
incident to $Y_{i-1}$.

Let $X_{Cn}^{\prime}=X_{Cn}\cap\left(\bigcup_{i=1}^{Cn-1}Y_{i}\right)$ be the
set of vertices for which Builder did not purchase the first incident edge in
the random graph process, but did purchase a later edge (by step $Cn$). Since
a vertex may move from $Y_{i-1}$ to $X_{i}$ only if there is an edge incident
to $Y_{i-1}$, $\left|X_{Cn}^{\prime}\right|\leq 2\sum_{i=1}^{Cn}I_{i}\leq
6\delta Cn.$ Therefore, all but at most $6\delta Cn$ vertices in $X_{Cn}$ are
such that Builder bought the first incident edge to them. Let $E_{1}\subseteq
E(B_{Cn})$ be the collection of edges that Builder bought and were the first
incident edge to one of their endpoints.

We will compare Builder’s graph with the $O_{1}$ graph at this stage of the
random graph process. Recall that $O_{1}$ consists of the first edge incident
to each vertex in the random graph process, and that $O_{1}$ with high
probability has at least $(o_{1}-o(1))n$ edges; condition on this being the
case. Let $O_{1}^{Cn}$ be the subgraph of $O_{1}$ with edges
$E(O_{1})\cap\\{e_{1},\ldots,e_{Cn}\\}$, so in particular
$E(O_{1}^{Cn})\supseteq E_{1}$. Notice that any other edge in $E(O_{1}^{Cn})$
is the first edge in the random graph process incident to some vertex in
$X_{Cn}^{\prime}\cup Y_{Cn}$, so $\left|E(O_{1}^{Cn})\setminus
E_{1}\right|\leq\left|X_{Cn}^{\prime}\cup Y_{Cn}\right|$. Therefore,

$\left|E(O_{1}^{Cn})\right|\leq\left|E_{1}\right|+\left|X_{Cn}^{\prime}\right|+\left|Y_{Cn}\right|\leq\left|E_{1}\right|+6\delta
Cn+\delta n.$ (3)

Similarly, $\left|E(O_{1})\setminus
E(O_{1}^{Cn})\right|\leq\left|Z_{Cn}\right|$: every edge in $E(O_{1})\setminus
E(O_{1}^{Cn})$ is the first edge in the random graph process incident to a
vertex in $Z_{Cn}$. Hence, with high probability,
$\left|E(O_{1})\right|-\left|E(O_{1}^{Cn})\right|\leq\left|Z_{Cn}\right|\leq
2{\rm e}^{-C}n,$ using Theorem 2.1 for the last inequality. Combining this
with (3) we deduce that

$\left|E(O_{1})\right|\leq\left|E_{1}\right|+6\delta Cn+\delta n+2{\rm
e}^{-C}n\leq e(B_{Cn})+6\delta Cn+\delta n+2{\rm e}^{-C}n.$

Rearranging gives $e(B_{Cn})\geq(o_{1}-6\delta C-\delta-2{\rm e}^{-C}-o(1))n$,
as required. ∎

This completes the proof of Theorem 1.3. ∎

All that remains is to prove Lemma 4.1.

###### Proof of Lemma 4.1.

As in 3.2, draw with repetition edges $(\hat{e}_{i})_{i\geq 1}$ from
$E(K_{n})$ and let $(\hat{G}_{i})_{i\geq 1}$ be the corresponding graph
process, i.e. $\hat{G}_{i}$ is the (simple) graph spanned by
$\hat{e}_{1},\ldots,\hat{e}_{i}$. We couple $(\hat{G}_{i})_{i\geq 1}$ with
$(\mathbf{G}_{n,j})_{j\geq m+1}$ in the obvious way; see the proof of 3.2 for
the details. Let

$\hat{\tau}_{1}=\min\\{i\geq 1:\text{for every }v\in Y_{m}\cup
Z_{m},\,\deg_{\hat{G}_{i}}(v)\geq 1\\}.$

######  Claim 4.3.

With high probability, a unique endpoint of $\hat{e}_{\hat{\tau}_{1}}$ is
isolated in $\hat{G}_{\hat{\tau}_{1}-1}$.

We prove 4.3 in the end. Condition on its conclusion holding. Let $v\in
Y_{m}\cup Z_{m}$ be the endpoint of $\hat{e}_{\hat{\tau}_{1}}$ in $Y_{m}\cup
Z_{m}$ that is isolated in $\hat{G}_{\hat{\tau}_{1}-1}$ and notice that, by
symmetry, $v$ is uniformly distributed in $Y_{m}\cup Z_{m}$.

Suppose $v\in Y_{m}$. Then every vertex is non-isolated in the random graph
process before $\hat{e}_{\hat{\tau}_{1}}$ is drawn: vertices in $X_{m}\cup
Y_{m}$ are non-isolated in $\mathbf{G}_{n,m}$, and every vertex in $Z_{m}$ has
an incident edge among $\\{\hat{e}_{1},\ldots,\hat{e}_{\hat{\tau}_{1}-1}\\}$,
so indeed
$\mathbf{G}_{n,\tau_{1}}\subseteq\mathbf{G}_{n,m}\cup\hat{G}_{\hat{\tau}_{1}-1}$.
Moreover, $v$ is isolated in $B_{\tau_{1}}$: none of the edges
$e_{j},j\in[m+1,\tau_{1}]$, is incident to $v$, so $v$ is isolated in
$B_{\tau_{1}}$, no matter what strategy Builder follows for these steps, since
she purchased no edge from $e_{1},\ldots,e_{m}$ that is incident to $v$. This
proves the first part of the lemma, as the probability that
$\hat{e}_{\hat{\tau}_{1}}$ has a unique isolated vertex in
$\hat{G}_{\hat{\tau}_{1}-1}$, which is in $Y_{m}$, is at least
$(1-o(1))\frac{|Y_{m}|}{|Y_{m}|+|Z_{m}|}$.

To prove the second part of the lemma, suppose $v\in Z_{m}$. Then
$\hat{e}_{\hat{\tau}_{1}}$ is the first incident edge to $v$ in the random
graph process, and since all other vertices in $Z_{m}$ have an incident edge
among $\hat{e}_{1},\ldots,\hat{e}_{\hat{\tau}_{1}-1}$, we deduce
$e_{\tau_{1}}=\hat{e}_{\hat{\tau}_{1}}$. Notice that Builder’s strategy of
purchasing the first incident edge to each vertex ensures that
$\deg_{B_{\tau_{1}}}(u)\geq 1$ for all $u\in Z_{m}$, since each edge incident
to $u\in Z_{m}$ is disjoint from $\mathbf{G}_{n,m}$, and thus she can purchase
it. Hence the lemma follows if, with high probability, for every $u\in Y_{m}$,
there is at least one incident edge in
$\hat{G}_{\hat{\tau}_{1}}\setminus\mathbf{G}_{n,m}$. This follows from the
assumption that $v\in Z_{\hat{\tau}_{1}}$ which implies that every vertex in
$Y_{m}$ has an incident edge in $\hat{G}_{\hat{\tau}}$, from Lemma 2.11, which
is applicable since, with high probability, $\Delta(\mathbf{G}_{n,m})\leq
10\log n$ by Proposition 2.4 and $e(\hat{G}_{\hat{\tau}_{1}})=\Theta(n\log
n)$, the latter being a direct consequence of Theorem 2.5. Indeed, if
$e(\hat{G}_{\hat{\tau}_{1}})\geq n\log n$, by Theorem 2.5, with high
probability $\hat{G}_{\hat{\tau}_{1}}$ has no isolated vertices. If
$e(\hat{G}_{\hat{\tau}_{1}})\leq\frac{n\log n}{3}$, then
$\hat{G}_{\hat{\tau}_{1}}\cup\mathbf{G}_{n,m}\subseteq\mathbf{G}_{n,m^{\prime}}$
where $m^{\prime}=\frac{n\log n}{3}+Cn$, and Theorem 2.5 yields that, with
high probability, $\hat{G}_{\hat{\tau}_{1}}\cup\mathbf{G}_{n,m}$ has isolated
vertices, which must be in $Z_{m}$.

###### Proof of 4.3.

Let $t=\frac{n\left(\log n-\log\log n\right)}{2}$. The expected number of
isolated vertices in $\hat{G}_{t}$ among $Y_{m}\cup Z_{m}$ is at most

$\displaystyle{\quad}\left|Y_{m}\cup
Z_{m}\right|\cdot\left(1-\frac{n-1}{\binom{n}{2}}\right)^{\frac{n}{2}\left(\log
n-\log\log n\right)}$ $\displaystyle\leq n\
\exp\left(-\frac{2}{n}\,\frac{n}{2}\left(\log n-\log\log n\right)\right)$
$\displaystyle=\log n.$

Therefore, by Markov’s inequality, with high probability the number of
isolated vertices in $\hat{G}_{t}$ is at most $(\log n)^{2}$. We condition on
this event. We condition also on the event that $\hat{\tau}_{1}=O(n\log n)$,
which holds with high probability: indeed, the argument in the paragraph
immediately preceding the current claim yields that, with high probability,
$e(\hat{G}_{\hat{\tau}_{1}})=\Theta(n\log n)$, and the calculations at the
beginning of Lemma 2.11 show that with high probability only $o(n\log n)$
edges among $\Theta(n\log n)$ drawn with replacement are repeated.

The claim will follow if among the remaining $\hat{\tau}_{1}-t$ edges (drawn
with replacement) none has both ends among $Y_{m}\cup Z_{m}$ which are
isolated in $\hat{G}_{t}$. As the following calculation shows, the expected
number of such edges is $o(1)$:

$(\hat{\tau}_{1}-t)\ \frac{\binom{(\log n)^{2}}{2}}{\binom{n}{2}}\leq O(n\log
n)\cdot O\left(\frac{(\log n)^{4}}{n^{2}}\right)=o(1).$

Hence, from Markov’s inequality, with high probability no such edges are
drawn. ∎

This completes the proof of Lemma 4.1. ∎

##  5 Concluding remarks

In this paper we studied the problem of constructing a graph with minimum
degree $k\geq 1$ in the controlled random graph process introduced in [11].
Theorem 1.1 disproves [11, Conjecture 7] in a strong form for $k\geq 2$.
Determining the optimal budget that yields a graph with minimum degree at
least $k$ by time $\tau_{k}$, with at least a given probability, remains an
interesting open problem. Similarly, Theorems 1.3 and 1.2 disprove [11,
Conjecture 7] for $k=1$. It would be interesting to determine the exact
dependence between the budget and the optimal success probability.

## References

  * [1] M. Anastos, _Constructing Hamilton cycles and perfect matchings efficiently_ , arXiv:2209.09860, 2022.
  * [2] B. Bollobás, _Vertices of given degree in a random graph_ , J. Graph Theory 6 (1982), 147–155.
  * [3] , _The evolution of sparse graphs._ , Proc. Cambridge Combinatorial Conf. in honour of Paul Erdős (Bollobás, B., ed.), Graph Theory and Combinatorics, Academic Press, 1984, pp. 35–57.
  * [4] B. Bollobás and A. Thomason, _Random graphs of small order_ , Annals of Discr. Math. (1985), 47–97.
  * [5] C. Cooper and A. Frieze, _On the connectivity of random k-th nearest neighbour graphs_ , Comb. Probab. Comput. 4 (1995), no. 4, 343–362.
  * [6] P. Erdős and A. Rényi, _On random graphs I_ , Publ. Math. Debrecen 6 (1959), 290–297.
  * [7] , _On the evolution of random graphs_ , Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17–61.
  * [8] , _On the strength of connectedness of a random graph_ , Acta Math. Acad. Sci. Hungar. 12 (1961), 261–267.
  * [9] , _On the existence of a factor of degree one of a connected random graph_ , Acta Math. Acad. Sci. Hungar. 17 (1966), 359–368.
  * [10] A. Frieze and M. Karoński, _Introduction to random graphs_ , Cambridge University Press, 2016, https://www.math.cmu.edu/$\sim$af1p/BOOK.pdf.
  * [11] A. Frieze, M. Krivelevich, and P. Michaeli, _Fast construction on a restricted budget_ , arXiv:2207.07251, 2022.
  * [12] S. Janson, A. Ruciński, and T. Łuczak, _Random Graphs_ , John Wiley & Sons, 2011.
  * [13] J. Komlós and E. Szemerédi, _Limit distributions for the existence of Hamilton cycles in a random graph_ , Discrete Math. 43 (1983), 55–63.
  * [14] A. D. Korshunov, _Solution of a problem of Erdős and Rényi on Hamilton cycles in non-oriented graphs_ , Soviet Mat. Dokl. 17 (1976), 760–764.
  * [15] , _Solution of a problem of Erdős and Rényi about Hamilton cycles in non-oriented graphs_ , Metody Diskr. Anal. Teoriy Upr. Syst., Sb. Trudov Novosibirsk (in Russian) 31 (1977), 17–56.
  * [16] L. Pósa, _Hamiltonian circuits in random graphs_ , Discrete Math. 17 (1976), 359–364.


# Non-stationary heat conduction in one-dimensional chains with conserved
momentum.

Oleg V. Gendelman  Faculty of Mechanical Engineering, Technion – Israel
Institute of Technology, Haifa, Israel  Alexander V. Savin  Semenov Institute
of Chemical Physics, Russian Academy of Sciences, Moscow 117977, Russia

###### Abstract

The Letter addresses the relationship between hyperbolic equations of heat
conduction and microscopic models of dielectrics. Effects of the non-
stationary heat conduction are investigated in two one-dimensional models with
conserved momentum: Fermi-Pasta-Ulam (FPU) chain and chain of rotators (CR).
These models belong to different universality classes with respect to
stationary heat conduction. Direct numeric simulations reveal in both models a
crossover from oscillatory decay of short-wave perturbations of the
temperature field to smooth diffusive decay of the long-wave perturbations.
Such behavior is inconsistent with parabolic Fourier equation of the heat
conduction. The crossover wavelength decreases with increase of average
temperature in both models. For the FPU model the lowest order hyperbolic
Cattaneo-Vernotte equation for the non-stationary heat conduction is not
applicable, since no unique relaxation time can be determined.

###### pacs:

44.10.+i; 05.45.-a; 05.60.-k; 05.70.Ln

It is well-known that parabolic Fourier equation of heat conduction implies
infinite speed of the signal propagation and thus is inconsistent with
causality p1 ; p2 ; p3 ; p4 ; p5 . Numerous modifications were suggested to
recover the hyperbolic character of the heat transport equation p2 . Perhaps,
the most known is the lowest-order approximation known as Cattaneo-Vernotte
(CV) law p1 ; p2 . In its one-dimensional version it is written as

$(1+\tau\frac{\partial}{\partial t})\vec{q}=-\kappa\nabla T$ (1)

where $\kappa$ is standard heat conduction coefficient and $\tau$ is
characteristic relaxation time of the system. The latter can be of macroscopic
order p5 . Importance of the hyperbolic heat conduction models for description
of a nanoscale heat transfer has been recognized p6 ; p7 .

Only few papers dealt with numeric verification of such laws from the first
principles p8 . As it is well-known now from numerous numeric simulations and
few analytic results, the relationship between the microscopic structure and
applicability of the Fourier law for description of the stationary heat
conduction is highly nontrivial and depends both on size and dimensionality of
the model p9 . In particular, the heat conduction coefficient can diverge in
the thermodynamic limit. Hyperbolic equations describing the non-stationary
heat conduction inevitably include more empiric constants and therefore their
relationship to the microscopic models can be even less trivial. To the best
of our knowledge, no conclusive data exist in this respect.

This Letter deals with a study of spatial and temporal peculiarities of the
non-stationary heat conduction in two simple one-dimensional models with
conserved momentum – Fermi-Pasta-Ulam (FPU) chain and chain of rotators (CR).
From the viewpoint of the stationary heat conduction, these two systems are
known to belong to different universality classes. Namely, in the FPU chain
the heat conduction coefficient diverges with the size of the system p10 ,
whereas in the CR model it converges to a finite value p11 ; p12 ; p13 . So,
it is interesting to check whether other differences between these models
models will reveal themselves in the problem of non-stationary heat
conduction.

In order to investigate this process, one should choose the parameters to
measure. This question is not easy, since the situation in this problem is
different from the stationary heat conduction, where only one commonly
accepted macroscopic equation exists and only one empiric parameter should be
computed. The simplest CV law already has two independent coefficients,
whereas more elaborate approximations can include even more parameters. Just
because many different empiric equations exist, it is not desirable to pick
one of them ab initio and to fit the data to find particular set of constants.
Instead, it seems reasonable to look for some quantity which will characterize
the process of the non-stationary conduction and can be measured from the
simulations without relying on particular approximate equation. For this sake,
we choose the characteristic length which characterizes the scale at which the
nonstationarity effects are significant.

In order to explain the appearance of this scale, let us refer to 1D version
of the CV equation for the temperature:

$\tau\frac{\partial^{2}T}{\partial t^{2}}+\frac{\partial T}{\partial
t}=\alpha\frac{\partial^{2}T}{\partial x^{2}}$ (2)

where $\alpha$ is the temperature conduction coefficient.

Let us consider the problem of non-stationary heat conduction in a one-
dimensional specimen with periodic boundary conditions $T(L,t)=T(0,t)$, where
$T(x,t)$ is the temperature distribution, $L$ is the length of the specimen,
$t\geq 0$. If it is the case, one can expand the temperature distribution to
Fourier series:

$T(x,t)=\sum_{n=-\infty}^{\infty}a_{n}(t)\exp(2\pi inx/L)$ (3)

with $a_{n}(t)=a_{-n}^{*}(t)$, since $T(x,t)$ is real function.

Substituting (2) to (3), one obtains the equations for time evolution of the
modal amplitudes:

$\tau\ddot{a}_{n}+\dot{a}_{n}+4\pi^{2}n^{2}\alpha a_{n}/L^{2}=0.$ (4)

Solutions of Eq. (4) are written as:

$\begin{array}[]{l}{a_{n}(t)=C_{1n}\exp(\lambda_{1}t)+C_{2n}(\lambda_{2}t)}\\\
{\lambda_{1,2}=\left(-1\pm\sqrt{1-{16\pi^{2}n^{2}\alpha\tau}/{L^{2}}}\right)/2}\end{array}$
(5)

where $C_{1n}$ and $C_{2n}$ are constants determined by the initial
distribution.

¿From (5) it immediately follows that for sufficiently short modes the
temperature profile will relax in oscillatory manner:

$\displaystyle n>L/4\pi\sqrt{\alpha\tau},$ $\displaystyle
a_{n}(t)\sim\exp(-t/2\tau)\exp(i\omega_{n}t),$ (6)
$\displaystyle\omega_{n}=\left(\sqrt{{16\pi^{2}n^{2}\alpha\tau}/{L^{2}}-1}\right)/2\tau$

If the specimen is rather long ($L>>4\pi\sqrt{\alpha\tau}$) then for small
wavenumbers (acoustic modes):

$\lambda_{1}\approx-1/\tau,\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \lambda_{2}\approx-{4\pi^{2}n^{2}\alpha}/{L^{2}}.$ (7)

The first eigenvalue describes fast initial transient relaxation, and the
second one corresponds to stationary slow diffusion and, quite naturally, does
not depend on $\tau$. So, we can conclude that there exists a critical length
of the mode

$l^{*}=4\pi\sqrt{\alpha\tau},$ (8)

which separates between two different types of the relaxation: oscillatory and
diffusive. The oscillatory behavior is naturally related to the hyperbolicity
of the system. Existence of this critical scale characterizes the deviance of
the system from parabolic Fourier law.

Figure 1:  Relaxation of initial periodic thermal profile in the chain of
rotators, $Z=64$, $L=1024$, (a) $T_{0}=0.2$, $A=0.05$ (oscillatory decay) and
(b) $T_{0}=0.5$, $A=0.15$ (smooth decay of the initial thermal profile).

This critical wavelength scale $l^{*}$ can be measured directly from the
numeric simulation without relying on any particular empiric equation of the
non-stationary heat conduction. The numeric experiment should be designed in
order to simulate the relaxation of thermal profile to its equilibrium value
for different spatial modes of the initial temperature distribution. We
simulate the periodic chain of particles with conserved momentum with
Hamiltonian

$H=\sum_{n=1}^{N}\frac{1}{2}\dot{u}_{n}^{2}+V(u_{n+1}-u_{n})\leavevmode\nobreak\
.$ (9)

In order to obtain the initial nonequilibrium temperature distribution, all
particles in the chain were embedded in the Langevin thermostat. For this
sake, the following system of equations was simulated:

$\displaystyle\ddot{u}_{n}$ $\displaystyle=$ $\displaystyle
V^{\prime}(u_{n+1}-u_{n})-V^{\prime}(u_{n}-u_{n-1})-\gamma_{n}\dot{u}_{n}+\xi_{n}$
$\displaystyle n$ $\displaystyle=$ $\displaystyle 1,...,N$ (10)

where $\gamma_{n}$ is the relaxation coefficient of the $n$-th particle and
the white noise $\xi_{n}$ is normalized by the following conditions:

$\left\langle\xi_{n}\right\rangle=0,\left\langle\xi_{n}(t_{1})\xi_{k}(t_{2})\right\rangle=2\sqrt{\gamma_{n}\gamma_{k}}T_{n}\delta_{nk}\delta(t_{1}-t_{2}),$
(11)

where $T_{n}$ is the prescribed temperature of the $n$-th particle. The
numeric integration has been performed for $\gamma_{n}=0.1$ for every $n$ and
within time interval $t=250$. After that, the Langevin thermostat was switched
off and relaxation of the system to a stationary temperature profile was
studied for various initial distributions $T_{n}$ for two particular choices
of the nearest-neighbor interaction described above (FPU and chain of
rotators):

$V_{1}(x)=x^{2}/2+x^{4}/4,\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ V_{2}(x)=1-\cos x.$

Separate analysis of individual spatial modes will provide insight into the
global behavior of the system only if these modes are, at least approximately,
not interacting. For CV equation (2) this is the case since it is linear.
However, we do not rely on it a priori and the absence of interaction between
different spatial relaxation modes should be checked numerically. We simulate
the relaxation of the initial thermal profile comprising five different modes:

$T_{n}=T_{0}+\sum_{i=4}^{8}A_{i}\cos[2\pi(n-1)/2^{i}]$ (12)

in cyclic chain of $N=2^{10}$ particles, with average temperature $T_{0}=1$
and modal amplitudes $A_{4}=...=A_{8}=0.02$ for the CR potential, and with
$T_{0}=20$, $A_{4}=...=A_{8}=0.4$ for the FPU potential. Both simulations
demonstrated almost complete lack of interaction between the modes. No other
modes were excited with visible amplitudes. Each mode in the collective
excitation relaxed similarly to the profile obtained when it was excited
individually. So, it is possible to conclude that for given values of the
parameters the equation of the non-stationary heat conduction should be
approximately linear and separate analysis of spatial relaxation modes is
justified.

In order to study the relaxation of different spatial modes of the initial
temperature distribution, its profile has been prescribed as

$T_{n}=T_{0}+A\cos[2\pi(n-1)/Z]$ (13)

where $T_{0}$ is he average temperature, $A$ – amplitude of the perturbation,
$Z$ – the length of the mode (number of particles). The overall length of the
chain $L$ has to be multiple of $Z$ in order to ensure the periodic boundary
conditions. The results were averaged over $10^{6}$ realizations of the
initial profile in order to reduce the effect of fluctuations.

Figure 2:  (Color online) Evolution of the relaxation profile in the chain of
rotators with change of the mode length $Z$. Time dependence of the mode
maximum $T(1+Z/2)$ (red lines) and minimum $T(1)$ (blue lines) are depicted
with average temperature $T_{0}=0.4$ and $Z=16\times 2^{k-1}$, $k=1,...,5$,
scaling time $t_{k}=2^{k-1}$. For all simulations length of chain $L=1024$.

Typical result of the simulation is presented at Fig. 1. The chain of rotators
of the same length $N=1024$ and the same modal wavelength $Z=64$ demonstrates
qualitatively different relaxation behavior for different temperatures – the
oscillatory one for lower temperature and the smooth decay – for higher
temperature. This observation suggests that the critical wavelength mentioned
above, if it exists, should decrease with the temperature increase. However,
its existence should be checked for constant temperature and varying
wavelength.

Such simulations are presented at Fig. 2 (for the CR) and Fig. 3 (for the FPU
chain). In both models one observes oscillatory decay for the short
wavelengths and smooth exponential decay for relatively long waves. It means
that for both models there exists some critical wavelength $l^{*}$ which
separates two types of the decay and thus the effect of the non-stationary
heat conduction is revealed.

Figure 3:  (Color online) Evolution of the relaxation profile in the FPU chain
with change of the mode length $Z$. Time dependence of the mode maximum
$T(1+Z/2)$ (red lines) and minimum $T(1)$ (blue lines) are depicted with
average temperature $T_{0}=20$ and $Z=16\times 2^{k-1}$, $k=1,...,7$, scaling
time $t_{k}=2^{k-1}$, length $L=1024$.

Results presented at Fig. 3 allow one to conclude that the critical wavelength
for the FPU chain for given temperature may be estimated as $512<l^{*}<1024$.
The interpretation of Fig. 2 is not that straightforward. It is clear that
$32<l^{*}<128$, but for $Z=64$ the result is not clear. Within the accuracy of
the simulation, it seems that only finite number of the oscillations is
observed. It is possible to speculate that such behavior is not consistent
with the lowest order CV equation, since expressions (6), (7) suggest either
infinite number of the oscillations, or at most single crossing of the average
temperature or no crossing at all. Possible interpretation may be that if the
modal wavelength is close enough to the critical, the second-order CV model is
not sufficient any more and the nonlocal effects of higher order should be
taken into account. Still, these conclusions should be verified by more
detailed simulations in the vicinity of the crossover wavelength.

Figure 4:  (Color online) Exponential decay of the normalized oscillation
amplitude in the chain of rotators $A(t)=(T(1+Z/2)(t)-T_{0})/A)$ for the
average temperature $T_{0}=0.3$, initial amplitude $A=0.05$ and different
periods of the thermal profile $Z=16\times 2^{k-1}$, $k=1,2,3$. The straight
lines illustrates the decay of the maximum envelope according to
$A=\exp(-\lambda t)$ with universal value $\lambda=0.015$ for all three
simulations.  Figure 5:  (Color online) Exponential decay of the normalized
oscillation amplitude in the FPU chain $a(t)=(T(1+Z/2)(t)-T_{0})/A$ for the
average temperature $T_{0}=10$, initial amplitude $A=0.05$ and different
periods of the thermal profile $Z=16\times 2^{k-1}$, $k=1,...,5$. The straight
lines illustrates the decay of the maximum envelope according to
$A=\exp(-\lambda t)$ with values $\lambda=0.0015$, 0.003, 0.008, 0.024 and
0.06 for $k=1$, 2, 3, 4 and 5.

The latter observation has motivated us to check whether the data of numeric
simulations in these one-dimensional models offer a support for the CV
macroscopic equation. For this sake, one can check another prediction of this
equation – the independence of the amplitude decrement of the relaxation
profile on the wavelength in the oscillatory regime (6). The results of
simulation are presented at Fig. 4 (CR) and Fig. 5 (FPU). One can see that for
the chain of rotators the above prediction more or less corresponds to the
simulation results. For the FPU chain the decrement is strongly dependent on
the wavelength, at odds with the CV equation. In this latter case, no unique
relaxation time exists.

To summarize, we reveal the hyperbolicity effects of the non-stationary heat
conduction in one-dimensional models of dielectrics without relying on any
particular empiric equation. There exists a critical modal wavelength $l^{*}$
which separates between oscillating and diffusive relaxation of the
temperature field; such crossover (actually, the oscillatory decay of the
temperature field perturbations) is inconsistent with parabolic Fourier
equation. So, if the size of the system is close to this critical scale, more
exact macroscopic equations should be used for description of the non-
stationary heat conduction. In both models studied the critical size decreases
with the temperature increase. As for the CV equation itself, in the FPU chain
this equation clearly contradicts the simulations for the short-wave
perturbations of the temperature field. In the chain of rotators it seems to
be inconsistent with the simulations in the vicinity of the critical
wavelength, however is more or less justified for longer and shorter modes.
One can speculate that this difference between two models is related to their
difference with respect to the stationary heat conduction – saturating versus
size dependent behavior of the heat conduction coefficient p9 ; p10 ; p11 ;
p12 ; p13 .

The authors are very grateful to Israel Science Foundation for financial
support. The authors also thank the Joint Supercomputer Center of the Russian
Academy of Sciences for using computer facilities.

## References

  * (1) P. Vernotte, C. R. Acad. Sci. 246, 3154 (1958).
  * (2) C. Cattaneo, C. R. Acad. Sci. 247, 431 (1958).
  * (3) D.S. Chandrasekhararaiah, Appl. Mech. Rev., 39, 355 (1986).
  * (4) D.S. Chandrasekhararaiah Appl. Mech. Rev., 51, 705 (1998).
  * (5) C.I. Christov and P.M. Jordan, Phys. Rev. Lett., 94, 154301 (2005).
  * (6) P. Heino, Journal of Comput. and Theor. Nanoscience, 4, 896 (2007).
  * (7) J. Shiomi and S. Maruyama, Phys. Rev B 73, 205420 (2006).
  * (8) S. Volz et al, Phys. Rev. B, 54, 340 (1996).
  * (9) S. Lepri, R. Livi and A. Politi, Phys. Reports, 377, 1 (2003).
  * (10) S. Lepri, R. Livi and A. Politi, Phys. Rev. Lett. 78 1896 (1997).
  * (11) O.V. Gendelman and A.V. Savin, Phys. Rev. Lett. 84 2381 (2000).
  * (12) C. Giardina, R. Livi, A. Politi and M. Vassalli, Phys. Rev. Lett. 84 2144 (2000).
  * (13) A.V. Savin and O.V. Gendelman, Fiz. Tverd. Tela (Leningrad) 43, 341 (2001) [Sov. Phys. Solid State 43, 355 (2001)].