# On the Ramsey-Turán density of triangles

Tomasz Łuczak  Adam Mickiewicz University, Faculty of Mathematics and Computer
Science, Poznań, Poland<EMAIL_ADDRESS>,  Joanna Polcyn  Adam Mickiewicz
University, Faculty of Mathematics and Computer Science, Poznań, Poland
<EMAIL_ADDRESS>and  Christian Reiher  Fachbereich Mathematik, Universität
Hamburg, Hamburg, Germany<EMAIL_ADDRESS>
###### Abstract.

One of the oldest results in modern graph theory, due to Mantel, asserts that
every triangle-free graph on $n$ vertices has at most $\lfloor n^{2}/4\rfloor$
edges. About half a century later Andrásfai studied dense triangle-free graphs
and proved that the largest triangle-free graphs on $n$ vertices without
independent sets of size $\alpha n$, where $2/5\leq\alpha<1/2$, are blow-ups
of the pentagon. More than 50 further years have elapsed since Andrásfai’s
work. In this article we make the next step towards understanding the
structure of dense triangle-free graphs without large independent sets.

Notably, we determine the maximum size of triangle-free graphs $G$ on $n$
vertices with $\alpha(G)\geq 3n/8$ and state a conjecture on the structure of
the densest triangle-free graphs $G$ with $\alpha(G)>n/3$. We remark that the
case $\alpha(G)\leq n/3$ behaves differently, but due to the work of Brandt
this situation is fairly well understood.

###### Key words and phrases:

Ramsey-Turán theory, extremal graph theory, triangle-free, independent sets.

###### 2010 Mathematics Subject Classification:

Primary: 05C35, Secondary: 05C69.

The first author is supported by National Science Centre, Poland, grant
2017/27/B/ST1/00873.

##  1\. Introduction

###  1.1. Ramsey-Turán theory

Mantel [M] proved in 1907 that balanced complete bipartite graphs maximise the
number of edges among all triangle-free graphs on a given set of vertices.
Later this result was generalized to $K_{\ell}$-free graphs by Turán [T] and,
asymptotically, to $H$-free graphs by Erdős and Stone [ES], and by Erdős and
Simonovits [ESim]. All of these works had a decisive impact on the development
of extremal graph theory.

Here we deal with one particular line of research systematically initiated by
Vera T. Sós and known as Ramsey-Turán theory (for a survey on this fascinating
area we refer to Simonovits and Sós [SS]). For $\ell\geq 3$ and $n\geq s\geq
0$ the Ramsey-Turán number $\mathrm{ex}_{\ell}(n,s)$ is the maximum number of
edges in a $K_{\ell}$-free graph on $n$ vertices which contains no independent
set consisting of more than $s$ vertices, i.e.,

$\mathrm{ex}_{\ell}(n,s)=\max_{G=(V,E)}\bigl{\\{}|E|\colon K_{\ell}\nsubseteq
G,\;|V|=n,\textrm{ and }\alpha(G)\leq s\bigl{\\}}\,.$

One usually considers the case that $n$ is large and thus, instead of
$\mathrm{ex}_{\ell}(n,s)$, one rather studies the Ramsey-Turán density
function $f_{\ell}\colon(0,1]\longrightarrow{\mathds{R}}$ defined by

$f_{\ell}(\alpha)=\lim\limits_{n\rightarrow\infty}\frac{\mathrm{ex}_{\ell}(n,\alpha
n)}{\binom{n}{2}}\,.$

For the existence of this limit we refer to [EHSS]. Notice that Turán’s
theorem implies

$\mathrm{ex}_{\ell}(n,s)=\bigl{(}1-o(1)\bigr{)}\frac{\ell-2}{\ell-1}\binom{n}{2}\quad\text{\
for\ }s\geq\Big{\lceil}\frac{n}{\ell-1}\Big{\rceil}\,,$ (1.1)

whence $f_{\ell}(\alpha)=\frac{\ell-2}{\ell-1}$ for all
$\alpha\geq\frac{1}{\ell-1}$. The central problem to determine the limit

$\varrho(K_{\ell})=\lim_{\alpha\to 0}f_{\ell}(\alpha)$

was solved for odd $\ell$ in [ES69] and proved to be very difficult for even
$\ell$. Following the ingenious contributions by Szemerédi [Sz72] and by
Bollobás and Erdős [BE76], this problem was finally solved by Erdős, Hajnal,
Sós, and Szemerédi [EHSS].

Recently Lüders and Reiher [LR-a] determined the value of $f_{\ell}(\alpha)$
whenever $\alpha$ is sufficiently small depending on $\ell$, so the extremal
behaviour of $K_{\ell}$-free graphs with small (linear) independence number is
now well understood. Despite this fact, we firmly believe that the problem to
determine $f_{\ell}(\alpha)$ for all
$\alpha\in\bigl{(}0,\frac{1}{\ell-1}\bigr{)}$ remains interesting.

###  1.2. Results on triangle-free graphs

In this article we restrict our attention to the innocent looking case
$\ell=3$, which seems surprisingly intricate to us. In other words, we
concentrate on triangle-free graphs and, eliminating some indices, we study
the behaviour of the function $\mathrm{ex}(n,s)=\mathrm{ex}_{3}(n,s)$ and its
‘scaled’ version $f(\alpha)=f_{3}(\alpha)$. We also write

$\mathscr{E}(n,s)=\bigl{\\{}G=(V,E)\colon K_{3}\nsubseteq
G,\;|V|=n,\;\alpha(G)\leq s,\textrm{ and }|E|=\mathrm{ex}(n,s)\bigr{\\}}$

for the corresponding families of extremal graphs.

In an early contribution from 1962 Andrásfai [A] studied the question of how
many edges a triangle-free graph on $n$ vertices, whose independence number is
at most $\alpha n$ for some given constant $\alpha$, can have. As a special
case of (1.1), for $\alpha\geq\frac{1}{2}$ Mantel’s Theorem yields
$\bigl{\lfloor}\frac{n^{2}}{4}\bigr{\rfloor}$ as an answer and for
$\alpha\leq\frac{1}{3}$ the “trivial” upper bound $\frac{1}{2}\alpha n^{2}$ is
essentially optimal (see the discussion at the end of this subsection), so the
question is most interesting when
$\alpha\in\bigl{(}\frac{1}{3},\frac{1}{2}\bigr{)}$. Andrásfai settled this
problem for all $\alpha\in\bigl{[}\frac{2}{5},\frac{1}{2}\bigr{]}$ and
conjectured for $\alpha\in\bigl{(}\frac{1}{3},\frac{1}{2}\bigr{)}$ that the
answer is describable in terms of appropriate blow-ups of certain graphs
nowadays bearing his name (see Conjecture 1.4 below).

######  Theorem 1.1 (Andrásfai).

For every nonnegative integer $n$ and every integer
$s\in\bigl{[}\frac{2}{5}n,\frac{1}{2}n\bigr{]}$ we have

$\mathrm{ex}(n,s)=n^{2}-4ns+5s^{2}\,.$

In particular, $f(\alpha)=2-8\alpha+10\alpha^{2}$ holds for every
$\alpha\in\bigl{[}\frac{2}{5},\frac{1}{2}\bigr{]}$.

Andrásfai [A] also determined the extremal families $\mathscr{E}(n,s)$ for
$s\in\bigl{[}\frac{2}{5}n,\frac{1}{2}n\bigr{]}$ and it turned out that all
extremal graphs in these families are blow-ups of the pentagon. We display a
sample case in Figure 1.1 and defer a more detailed discussion to Subsection
1.3. Our main result is a similar quadratic formula applicable to every
$\alpha\in\bigl{[}\frac{3}{8},\frac{2}{5}\bigr{]}$.

$3s-n$$3s-n$$n-2s$$n-2s$$n-2s$ Figure 1.1. Example of a graph in
$\mathscr{E}(n,s)$ for $2n/5\leq s\leq n/2$.

######  Theorem 1.2.

If $n\geq 0$ and $s\in\bigl{[}\frac{3}{8}n,\frac{2}{5}n\bigr{]}$, then

$\mathrm{ex}(n,s)=3n^{2}-15ns+20s^{2}\,.$

Consequently, we have

$f(\alpha)=6-30\alpha+40\alpha^{2}\quad\textrm{for
every}\quad\alpha\in\bigl{[}\tfrac{3}{8},\tfrac{2}{5}\bigr{]}\,.$

It follows from our proof that all extremal graphs for this result, i.e., all
graphs in a class of the form $\mathscr{E}(n,s)$ with
$s\in\bigl{[}\frac{3}{8}n,\frac{2}{5}n\bigr{]}$ are blow-ups of the well-known
Wagner graph here denoted by $\Gamma_{3}$, which is a triangle-free cubic
graph on $8$ vertices. A special case is shown in Figure 1.2.

$3s-n$$3s-n$$n-2s$$n-2s$$n-2s$$2n-5s$$2n-5s$$2n-5s$$3s-n$$3s-n$$3s-n$$3s-n$$3s-n$
Figure 1.2. Example of a graph in $\mathscr{E}(n,s)$ for $3n/8\leq s\leq
2n/5$.

We suspect that some of the tools we have developed for proving Theorem 1.2
will be relevant for a complete determination of the function $f$, even though
some new ideas will certainly be required. Before stating our version of
Andrásfai’s conjecture on $f$ we briefly recall another known result on this
function.

Notice that every triangle-free graph $G$ satisfies

$\Delta(G)\leq\alpha(G)\,,$

for the neighbourhood of every vertex is an independent set. Therefore

$\mathrm{ex}(n,s)\leq\tfrac{1}{2}ns$

holds for all $n\geq s\geq 0$ and $f(\alpha)\leq\alpha$ for $\alpha>0$
follows. We call these estimates the trivial bounds on $\mathrm{ex}(n,s)$ and
$f(\alpha)$, respectively.

In the regime $s<\frac{1}{3}n$ Brandt [B10] provided several constructions of
$s$-regular graphs on $n$ vertices whose independence number is equal to $s$,
and his work implies $f(\alpha)=\alpha$ for all
$\alpha\in\bigl{(}0,\frac{1}{3}\bigr{]}$. In view of this result and the above
theorems it remains to study the behaviour of $f(\alpha)$ for
$\alpha\in\bigl{(}\frac{1}{3},\frac{3}{8}\bigr{)}$. The next subsection offers
a conjecture for this range.

###  1.3. A conjecture on triangle-free graphs

Let us introduce one more piece of terminology. By a blow-up of a graph $G$ we
mean any graph $\hat{G}$ obtained from $G$ be replacing each of its vertices
$v_{i}$ by an independent set $V_{i}$ (that can be empty) and joining two
subsets $V_{i}$ and $V_{j}$ of vertices of $\hat{G}$ by all $|V_{i}||V_{j}|$
possible edges whenever the pair $\\{v_{i},v_{j}\\}$ is an edge of $G$. For
instance, Figure 1.1 shows a blow-up of the pentagon, where three consecutive
vertices are replaced by independent $(n-2s)$-sets (drawn red) while the
remaining two vertices are enlarged to (blue) independent $(3s-n)$-sets.

Let us recall that Andrásfai graphs are Cayley graphs
$\bigl{(}{\mathds{Z}}/(3k-1){\mathds{Z}},S\bigr{)}$ with $k\geq 1$ and
$S\subseteq{\mathds{Z}}/(3k-1){\mathds{Z}}$ being a sum-free subset of size
$k$. For definiteness, we denote the graph obtained for
$S=\\{k,\ldots,2k-1\\}$ by $\Gamma_{k}$. So explicitly two vertices $i$ and
$j$ of $\Gamma_{k}$ are adjacent if and only if $i-j\in S$. Following
$\Gamma_{1}=K_{2}$ the first few Andrásfai graphs are depicted in Figure 1.3.

$3s-n$$3s-n$$n-2s$$n-2s$$n-2s$$2n-5s$$2n-5s$$2n-5s$$3s-n$$3s-n$$3s-n$$3s-n$$3s-n$

$3s-n$$3s-n$$n-2s$$n-2s$$n-2s$$2n-5s$$2n-5s$$2n-5s$$3s-n$$3s-n$$3s-n$$3s-n$$3s-n$

$3s-n$$3s-n$$n-2s$$n-2s$$n-2s$$2n-5s$$2n-5s$$2n-5s$$3s-n$$3s-n$$3s-n$$3s-n$$3s-n$

$3s-n$$3s-n$$n-2s$$n-2s$$n-2s$$2n-5s$$2n-5s$$2n-5s$$3s-n$$3s-n$$3s-n$$3s-n$$3s-n$

$3s-n$$3s-n$$n-2s$$n-2s$$n-2s$$2n-5s$$2n-5s$$2n-5s$$3s-n$$3s-n$$3s-n$$3s-n$$3s-n$

Figure 1.3. Andrásfai graphs $\Gamma_{2}$, $\Gamma_{3}$, $\Gamma_{4}$,
$\Gamma_{5}$, and $\Gamma_{6}$.

Notice that $\Gamma_{k}$ is a triangle-free, $k$-regular graph on $3k-1$
vertices whose independence number is exactly $k$. Therefore, balanced blow-
ups of $\Gamma_{k}$ show that the trivial bound on $f(\alpha)$ is optimal if
$\alpha$ is of the form $\frac{k}{3k-1}$, i.e., that we have

$f\Big{(}\frac{k}{3k-1}\Big{)}=\frac{k}{3k-1}\quad\text{\ for all\ }\ k\geq
1\,.$ (1.2)

Like Andrásfai we believe that whenever $n\geq 0$ and
$s\in\bigl{(}\frac{1}{3}n,\frac{1}{2}n\bigr{]}$ there exists a graph
$G\in\mathscr{E}(n,s)$ which is a blow-up of an appropriate Andrásfai graph.
This leads to $f(\alpha)$ being piecewise quadratic on
$\bigl{(}\frac{1}{3},\frac{1}{2}\bigr{]}$ with critical values at
$\alpha_{k}=\frac{k}{3k-1}$ for $k\geq 2$. By optimizing over all blow-ups of
Andrásfai graphs we were led to the following function.

######  Definition 1.3.

For integers $n\geq s\geq 0$ we set

$g(n,s)=\begin{cases}\frac{1}{2}ns\,,&\text{ if $s\leq\frac{1}{3}n$}\cr
g_{k}(n,s)\,,&\text{ if $\frac{k}{3k-1}n\leq s<\frac{k-1}{3k-4}n$ for some
$k\geq 2$}\cr\bigl{\lfloor}\frac{n^{2}}{4}\bigr{\rfloor}\,,&\text{ if
$\frac{n}{2}\leq s\leq n$,}\end{cases}$

where

$g_{k}(n,s)=\tfrac{1}{2}k(k-1)n^{2}-k(3k-4)ns+\tfrac{1}{2}(3k-4)(3k-1)s^{2}\,.$
(1.3)

######  Conjecture 1.4.

For all integers $n\geq s\geq 0$ we have $\mathrm{ex}(n,s)\leq g(n,s)$. In
other words, every triangle-free $n$-vertex graph $G$ with $\alpha(G)\leq s$
has at most $g(n,s)$ edges.

Admittedly, one needs some time to get used to the functions $g_{k}(n,s)$
introduced in (1.3) but we believe that the motivation in terms of optimal
blow-ups of Andrásfai graphs renders the conjecture sufficiently natural (see
also [Vega]*Lemma 3.3). Observe that the functions $g_{2}(n,s)$ and
$g_{3}(n,s)$ are precisely the quadratic forms appearing in the Theorems 1.1
and 1.2. Therefore, Conjecture 1.4 is only open for
$s\in\bigl{(}\frac{1}{3}n,\frac{3}{8}n\bigr{)}$. Let us briefly indicate one
construction showing that, if true, Conjecture 1.4 is optimal for the most
interesting range of $\frac{s}{n}$.

######  Fact 1.5.

If $s\in\bigl{(}\frac{1}{3}n,\frac{1}{2}n\bigr{)}$, then $\mathrm{ex}(n,s)\geq
g(n,s)$.

###### Proof.

Let $k\geq 2$ be the unique integer with
$s\in\bigl{[}\frac{k}{3k-1}n,\frac{k-1}{3k-4}n\bigr{)}$. Take a blow-up $G$ of
$\Gamma_{k}$ obtained by replacing the vertices $1$, $k$, and $2k$ by sets of
size $(k-1)n-(3k-4)s$ and the remaining vertices by sets of size $3s-n$.
Clearly, $G$ is triangle-free. One can check that $G$ has $n$ vertices,
independence number $s$, and $g_{k}(n,s)$ edges. ∎

Let us observe that Conjecture 1.4 yields a precise prediction on the Ramsey-
Turán density function $f$, namely the following.

######  Conjecture 1.6.

The function $f\colon(0,1]\longrightarrow{\mathds{R}}$ is given by

$f(\alpha)=\begin{cases}\alpha\,,&\text{ if $\alpha\leq\frac{1}{3}$}\cr
f_{k}(\alpha)\,,&\text{ if $\frac{k}{3k-1}\leq\alpha<\frac{k-1}{3k-4}$ for
some $k\geq 2$}\cr\frac{1}{2},&\text{ if $\frac{1}{2}\leq\alpha\leq
1$},\end{cases}$

where

$f_{k}(\alpha)=k(k-1)-2k(3k-4)\alpha+(3k-4)(3k-1)\alpha^{2}\,.$ (1.4)

Notice that at the critical values $\alpha_{k}=\frac{k}{3k-1}$ this function
agrees with (1.2). The remainder of this introduction discusses further
evidence in support of Conjecture 1.4.

###  1.4. Minimum degree

There appears to be a mysterious analogy between the Ramsey-Turán problem for
triangles and the more thoroughly studied problem to describe the structure of
triangle-free graphs of large minimum degree. For instance, there is a similar
transition from chaos to structure occurring at $\frac{1}{3}n$. As reported in
[ES73] Hajnal constructed triangle-free graphs $G$ with
$\delta(G)\geq\bigl{(}\frac{1}{3}-o(1)\bigr{)}|V(G)|$ of arbitrarily large
chromatic number. On the other hand, Łuczak [Lu06] proved that for every
$\varepsilon>0$ all triangle-free graphs $G$ with
$\delta(G)\geq\bigl{(}\frac{1}{3}+\varepsilon\bigr{)}|V(G)|$ admit a
homomorphism into a triangle-free graph whose order can be bounded in terms of
$\varepsilon$. The ultimate variant of Łuczak’s result is due to Brandt and
Thomassé [BT], who proved that, actually, such graphs either admit a
homomorphism into some Andrásfai graph or into some so-called Vega graph (see
[BP]).

We will not introduce Vega graphs properly here and only remark that they can
be obtained from Andrásfai graph by adding $8$ vertices forming a cube as well
as several new edges, and possibly deleting at most two special vertices
afterwards. For $k\geq 10$ with $k\equiv 1,2,3\pmod{9}$ there are blow-ups of
appropriate Vega graphs with $3k-1$ vertices and independence number $k$ that
furnish additional extremal cases for (1.2).

Now several questions present themselves. Are Vega graphs so special that
their only appearances in extremal families $\mathscr{E}(n,s)$ are the
aforementioned regular ones? Or, perhaps, on the contrary, because of their
more sophisticated structure they admit blow-ups falsifying Conjecture 1.4?
Both these speculations seem to be false. There are non-trivial blow-ups of
Vega graphs which are in $\mathscr{E}(n,s)$. Nonetheless, it can be proved
that, in a sense made precise in [Vega], no ‘natural’ blow-up of an Andrásfai
graph or Vega graph can be a counterexample to Conjecture 1.4.

These facts have an interesting consequence. Together with the structure
theorem of Brandt and Thomassé they allow us to prove Conjecture 1.4 for
$\alpha\in\bigl{[}\frac{k}{3k-1},\frac{k}{3k-1}+\varepsilon_{k}\bigr{]}$,
where $k\geq 2$ and $\varepsilon_{k}$ is sufficiently small. Further details
and a conjectural explicit description of the extremal graph families
$\mathscr{E}(n,s)$ will be presented in our forthcoming article [Vega].

This article is organized as follows. In the next section we sketch some tools
and observations which we shall use later and which, hopefully, could be
useful in the quest of proving Conjecture 1.4 in full generality. The last
section is devoted to the proof of Theorem 1.2.

##  2\. Preliminaries

The goal of this section is to gather several results that we believe to be
relevant in general to the problem of determining $\mathrm{ex}(n,s)$ for
$s>n/3$. These preliminaries fall naturally into three groups. We start in
Subsection 2.1 with some facts concerning matchings and independent sets in
arbitrary, not necessarily triangle-free, graphs. Subsection 2.2 proceeds with
a discussion of symmetrisation operations – a device we shall use for
“simplifying” extremal graphs. Finally in Subsection 2.3 we use this technique
for investigating the structure of graphs that are extremal for the problem to
determine $\mathrm{ex}(n,s)$.

Throughout the article we follow standard graph theoretical notation. Thus,
for instance, $\deg_{G}(v)$ stands for the degree of a vertex $v$ of a graph
$G$, and by $\mathrm{N}_{G}(S)$ we mean the neighbourhood of the set of
vertices $S$. Moreover, we omit subscripts unless they are necessary to avoid
confusion. Given two disjoint sets $A$ and $B$ we define

$K(A,B)=\bigl{\\{}\\{a,b\\}\colon a\in A\text{ and }b\in B\bigr{\\}}\,.$

This is the edge set of the complete bipartite graph with vertex partition
$A\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}B$. For
two disjoint subsets $A$ and $B$ of vertices of $G$ we say that $A$ is
matchable into $B$ if the bipartite graph induced in $G$ by the sets $A$ and
$B$ contains a matching saturating $A$.

###  2.1. Matchings and independent sets

Clearly if $A$ and $Y$ are two disjoint independent sets in a graph $G$ with
$|Y|\leq|A|$, then there is an injective map from $Y$ to $A$. The following
simple consequence of Hall’s theorem, due to Andrásfai (see [A]*Lemma 2.3),
ensures that in case $|A|=\alpha(G)$ one such injection is exemplified by a
matching. For the reader’s convenience we include a short proof.

######  Fact 2.1.

Let $A$ and $Y$ be two disjoint independent sets in a graph $G$. If
$|A|=\alpha(G)$, then $Y$ is matchable into $A$.

###### Proof.

In the light of Hall’s theorem [Hall] it suffices to prove that for an
arbitrary $D\subseteq Y$ and its neighbourhood $A\cap\mathrm{N}(D)$ in $A$ we
have $|D|\leq|A\cap\mathrm{N}(D)|$. Since
$D\cup(A\smallsetminus\mathrm{N}(D))$ is independent in $G$, we have indeed

$|D|+|A|-|A\cap\mathrm{N}(D)|=|D\cup(A\smallsetminus\mathrm{N}(D))|\leq\alpha(G)=|A|\,.\qed$

In general, deleting edges from a graph may increase its independence number.
For our purposes it will be important to know that the following type of edge
deletions leave the independence number invariant.

######  Lemma 2.2.

Given a graph $G$, suppose

  1. $\bullet$

that $A\subseteq V(G)$ is an independent set of size $\alpha(G)$,

  2. $\bullet$

and that $M$ is a matching in $G$ from $V(G)\smallsetminus A$ to $A$, the size
of which is as large as possible.

If $G^{\prime}$ denotes the graph obtained from $G$ by isolating the vertices
in $A\smallsetminus V(M)$, i.e., by deleting all edges incident with them,
then $\alpha(G^{\prime})=\alpha(G)$.

###### Proof.

Since $G^{\prime}$ is a subgraph of $G$, we have
$\alpha(G^{\prime})\geq\alpha(G)$. For the converse direction we consider any
set $U\subseteq V(G)$ which is independent in $G^{\prime}$. Since
$U\smallsetminus A$ is independent in $G$, Fact 2.1 tells us that in $G$ there
exists a matching $N$ from $U\smallsetminus A$ to $A$ covering all vertices of
$U\smallsetminus A$. We contend that

$M^{\prime}=\\{e\in M\colon A\cap U\cap e\neq\varnothing\\}\cup N$

is a matching in $G$. Otherwise, there had to exist two edges, $e\in M$ with
$A\cap U\cap e\neq\varnothing$ and $f\in N$, sharing a vertex $x$. By $x\in
f\in N$ we have either $x\in U\smallsetminus A$ or $x\in A$. In the former
case the vertex of $e$ distinct from $x$ needs to be in $A\cap U$. In
particular, both ends of $e$ are in $U$, contrary to $e\in M\subseteq
E(G^{\prime})$ and $U$ being independent in $G^{\prime}$.

So we are left with the case $x\in A$. Now we have in fact $A\cap U\cap
e=\\{x\\}$ and both ends of $f$ are in $U$. Moreover, $x\in A\cap U\cap
e\subseteq A\cap V(M)$ shows that $f$ does not get deleted when we pass from
$G$ to $G^{\prime}$. This contradiction to $U$ being independent in
$G^{\prime}$ proves that $M^{\prime}$ is indeed a matching in $G$.

Therefore the maximality of $M$ yields

$|N|+|V(M)\cap A\cap U|=|M^{\prime}|\leq|M|=|V(M)\cap A\cap
U|+|V(M)\cap(A\smallsetminus U)|\,,$

i.e.,

$|U\smallsetminus A|=|N|\leq|V(M)\cap(A\smallsetminus U)|\,.$

Thus

$|U\smallsetminus A|\leq|A\smallsetminus U|\,,$

and, consequently, $|U|\leq|A|=\alpha(G)$, as desired. ∎

To unleash the full power of the foregoing lemma it is useful to know that
certain subsets of $V(G)$ can be forced to be subsets of $V(M)$. For such
purposes we shall employ the following observation.

######  Fact 2.3.

Let $H$ be a bipartite graph with vertex classes $R$ and $S$ in which the
largest matching has size $m$. If some set $R^{\prime}\subseteq R$ is
matchable into $S$, then $H$ contains a matching of size $m$ saturating all
vertices of $R^{\prime}$.

###### Proof.

Let $\mathscr{M}$ be the set of all matchings in $H$ having size $m$. Choose
first a matching $N$ from $R^{\prime}$ into $S$ saturating all vertices in
$R^{\prime}$, and then a matching $M\in\mathscr{M}$ for which $|M\cap N|$ is
maximal. We will show that $M$ covers $R^{\prime}$. Otherwise there was a
vertex $x\in R^{\prime}$ not covered by $M$. Let $z$ be the unique vertex with
$xz\in N$. By the maximality of $m$, the $m+1$ edges in $M\cup\\{xz\\}$ cannot
form a matching in $H$ and, consequently, we have $z\in V(M)$. So there is a
vertex $u$ such that $uz\in M$. But now
$M^{\prime}=(M\smallsetminus\\{uz\\})\cup\\{xz\\}$ is a matching in
$\mathscr{M}$ satisfying $|M^{\prime}\cap N|>|M\cap N|$, contradicting our
choice of $M$. ∎

###  2.2. Symmetrisation

One of the standard proofs of Turán’s theorem [T], due to Zykov [Zy], shows
that every $K_{\ell}$-free graph $G$ can be transformed into an
$(\ell-1)$-partite graph on the same vertex set by a sequence of
symmetrisation operations, in such a way that throughout the whole process the
number of edges never decreases. Indeed, this implies that $G$ does have at
most as many edges as the corresponding Turán graph. The symmetrisation step
employed by Zykov consists in taking two non-adjacent vertices $u$ and $v$,
deleting all edges incident with $u$, and then adding all edges from $u$ to
the neighbours of $v$.

Our proof of Theorem 1.2 utilises a modest generalisation of this idea. Given
a graph $G$ and two disjoint sets $A,B\subseteq V(G)$, we say that a graph
$G^{\prime}$ on the same vertex set as $G$ arises from $G$ by the generalised
Zykov symmetrisation $\mathbf{Sym}(A,B)$ if it is obtained by deleting all
edges incident with $B$ and afterwards adding all edges from $A$ to $B$.
Explicitly, this means

$V(G^{\prime})=V(G)\quad\text{ and }\quad
E(G^{\prime})=\bigl{(}E(G)\smallsetminus\\{e\in E(G):e\cap
B\neq\varnothing\\}\bigr{)}\cup K(A,B)\,.$

We will express this state of affairs by writing
$G^{\prime}=\mathbf{Sym}(G\,|\,A,B)$. In the special case where $B=\\{v\\}$ is
a singleton, we will often abbreviate $\\{v\\}$ to $v$, thus speaking, e.g. of
the operation $\mathbf{Sym}(A,v)$. For later use we record the following
obvious properties of these operations.

######  Fact 2.4.

Given a graph $G$ and two disjoint sets $A,B\subseteq V(G)$, let
$G^{\prime}=\mathbf{Sym}(G\,|\,A,B)$.

  1. ( )

If $|A|\geq\deg_{G}(b)$ holds for all $b\in B$, then $e(G^{\prime})\geq e(G)$.
If equality occurs, then all vertices in $B$ have degree $|A|$ in $G$ and $B$
is an independent set in $G$.

  2. ( )

If $A$ is independent and $G$ is triangle-free, then so is $G^{\prime}$.

###### Proof.

Part ( ) ‣ 2.4 follows from the estimate

$e(G^{\prime})-e(G)\geq\sum_{b\in B}\bigl{(}|A|-\deg_{G}(b)\bigr{)}\geq 0\,,$

where the first “$\geq$” sign takes into account that edges both of whose ends
are in $B$ are subtracted twice in the sum over $b\in B$. The statement
addressing the equality case should now be clear.

To prove part ( ) ‣ 2.4 we assume for the sake of contradiction that $xyz$ was
a triangle in $G^{\prime}$. Owing to $G-B=G^{\prime}-B$ we may suppose further
that $x\in B$. Now $y$ and $z$ are neighbours of $x$ in $G^{\prime}$ and,
hence, both of them are in $A$. But $A$ is still independent in $G^{\prime}$
and thus $yz$ cannot be an edge of $G^{\prime}$. ∎

Our next result describes a case where symmetrization preserves the
independence number.

######  Lemma 2.5.

Let $A$ and $B$ be two disjoint independent sets in a graph $G$ such that
$|A|=|B|=\alpha(G)$. If $M$ is a matching from $V(G)\smallsetminus(A\cup B)$
to $B$, whose size is as large as possible, $B^{\prime}\subseteq
B\smallsetminus V(M)$, and $G^{\prime}=\mathbf{Sym}(G\,|\,A,B^{\prime})$, then
$\alpha(G^{\prime})=\alpha(G)$.

###### Proof.

Since $A$ is independent in $G^{\prime}$, we have
$\alpha(G^{\prime})\geq\alpha(G)$. Now suppose conversely that $U\subseteq
V(G)$ is independent in $G^{\prime}$. We are to prove $|U|\leq\alpha(G)$.

If $A$ and $U$ are disjoint it follows from Lemma 2.2 (applied to $G-A$, $B$,
and $M$ here in place of $G$, $A$, and $M$ there) that
$|U|\leq\alpha(G-A)=\alpha(G)$, meaning that we are done.

It remains to consider the case $U\cap A\neq\varnothing$. Now
$K(A,B^{\prime})\subseteq E(G^{\prime})$ implies that $U$ is disjoint to
$B^{\prime}$. Therefore $U$ is independent in $G$ and so $|U|\leq\alpha(G)$. ∎

###  2.3. Some general results

Recall that for $n\geq s\geq 0$ we are interested in the quantity

$\displaystyle\mathrm{ex}(n,s)=\max\bigl{\\{}|E|\colon G=(V,E)\text{ is a
triangle-free graph with $|V|=n$ and $\alpha(G)\leq s$}\bigr{\\}}$

and that

$\mathscr{E}(n,s)=\bigl{\\{}G=(V,E)\colon K_{3}\nsubseteq
G,\;|V|=n,\;\alpha(G)\leq s,\textrm{ and }|E|=\mathrm{ex}(n,s)\bigr{\\}}$

denotes the corresponding family of extremal graphs.

We begin by observing that the estimate $\mathrm{ex}(n,s)\leq g_{k}(n,s)$
holds whenever $s$ is outside the range required by Conjecture 1.4.

######  Fact 2.6.

Let integers $n\geq s\geq 0$ and $k\geq 2$ be given. If
$s\notin\bigl{(}\frac{k}{3k-1}n,\frac{k-1}{3k-4}n\bigr{)}$, then

$\mathrm{ex}(n,s)\leq g_{k}(n,s)$

and equality can only hold if
$s\in\bigl{\\{}\frac{k}{3k-1}n,\frac{k-1}{3k-4}n\bigr{\\}}$.

###### Proof.

We check that under our assumption on $s$ the trivial upper bound
$\mathrm{ex}(n,s)\leq\frac{1}{2}ns$ is at least as good as $g_{k}(n,s)$. Since
for $s\notin\bigl{(}\frac{k}{3k-1}n,\frac{k-1}{3k-4}n\bigr{)}$,

$\displaystyle ns$ $\displaystyle\leq
ns+\bigl{(}kn-(3k-1)s\bigr{)}\bigl{(}(k-1)n-(3k-4)s\bigr{)}$
$\displaystyle=k(k-1)n^{2}-2k(3k-4)ns+(3k-4)(3k-1)s^{2}=2g_{k}(n,s)$

this is indeed the case and the statement about the equality case also easily
follows. ∎

In combination with Fact 1.5 this leads to the following alternative way of
defining $g(n,s)$ in case
$\frac{s}{n}\in\bigl{(}\frac{1}{3},\frac{1}{2}\bigr{)}$.

######  Corollary 2.7.

If $\frac{1}{3}n<s<\frac{1}{2}n$, then

$\displaystyle\hfill g(n,s)=\min\bigl{\\{}g_{k}(n,s)\colon k\geq
2\bigr{\\}}\,.$ $\Box$

Our first structural result on graphs in $\mathscr{E}(n,s)$ asserts that they
contain two disjoint independent sets of size $s$ (provided there is enough
space for them).

######  Lemma 2.8.

If $n$ and $s$ are two integers with $n\geq 2s\geq 0$, then every graph
$G\in\mathscr{E}(n,s)$ contains two disjoint independent sets of size $s$.

###### Proof.

Let $(X,Y)$ be a pair of disjoint independent sets in $G$ such that
$|X|=\alpha(G)$ and subject to this $|Y|$ is as large as possible. Clearly
$|Y|\leq|X|\leq s$ and we are to prove that equality holds throughout. This
could fail in two different ways.

Case 1. $|Y|<|X|$

Owing to $\alpha(G-X)=|Y|\leq|X|-1\leq s-1<n-s\leq v(G-X)$ there is an edge
$ab$ of $G$ with $a,b\not\in X$. If both of $a$ and $b$ have degree
$\alpha(G)$, then their neighbourhoods are two disjoint independent sets of
size $\alpha(G)$, thus contradicting our choice of the pair $(X,Y)$.

It follows that we may assume, without loss of generality, that
$\deg(a)<\alpha(G)$. By Fact 2.4 the graph
$G^{\prime}=\mathbf{Sym}(G\,|\,X,a)$ is triangle-free and has more edges than
$G$. So the extremality of $G$ entails that $G^{\prime}$ contains an
independent set of size $\alpha(G)+1$. Owing to $G-a=G^{\prime}-a$ any such
set needs to be of the form $Z\cup\\{a\\}$, where $Z$ is an independent set in
$G$ of size $\alpha(G)$. Due to the construction of $G^{\prime}$ the sets $X$
and $Z$ need to be disjoint and thus the pair $(X,Z)$ contradicts our choice
of $(X,Y)$.

Case 2. $|X|=|Y|=\alpha(G)<s$

Now $|V(G)\smallsetminus(X\cup Y)|\geq n-2(s-1)\geq 2$ and thus there are two
distinct vertices in this set, say $a$ and $b$. Let $G^{\prime}$ be the result
of applying first $\mathbf{Sym}(Y\cup\\{b\\},a)$ and then
$\mathbf{Sym}(X\cup\\{a\\},b)$ to $G$ (see Figure 2.1).

$X$$Y$$a$$b$$3s-n$$3s-n$$n-2s$$n-2s$$n-2s$$2n-5s$$2n-5s$$2n-5s$$3s-n$$3s-n$$3s-n$$3s-n$$3s-n$
Figure 2.1. Possibly new edges of $G^{\prime}$ are drawn green.

Observe that the sets $Y\cup\\{b\\}$ and $X\cup\\{a\\}$ are independent in
$G^{\prime}$, whence $G^{\prime}$ is triangle-free. Since $ab$ is an edge of
$G^{\prime}$, we have $\alpha(G^{\prime})\leq\alpha(G)+1\leq s$. Notice that
for a vertex $v$ of $G$ we have $\deg_{G}(v)\leq\alpha(G)=|X|=|Y|$ and so

$e(G^{\prime})\geq e(G)-\deg_{G}(a)-\deg_{G}(b)+|X|+|Y|+1>e(G)\,,$

which clearly contradicts the fact that $G\in\mathscr{E}(n,s)$. ∎

We conclude this section with a result that provides additional information on
the structure of some graphs in $\mathscr{E}(n,s)$.

######  Lemma 2.9.

Given two integers $n\geq 0$ and
$s\in\bigl{[}\frac{1}{3}n,\frac{1}{2}n\bigr{]}$, there exists a graph
$G\in\mathscr{E}(n,s)$ containing two disjoint independent sets $A$ and $B$ of
size $|A|=|B|=s$ having subsets $A^{\prime}\subseteq B$ and
$B^{\prime}\subseteq A$ with $|A^{\prime}|=|B^{\prime}|=3s-n$ and

$K(A^{\prime},A)\cup K(B^{\prime},B)\subseteq E(G)\,.$ (2.1)

###### Proof.

Let $G^{\prime}\in\mathscr{E}(n,s)$ and let $A,B\subseteq V(G^{\prime})$ be
any two disjoint independent sets of size $s$, the existence of which is
guaranteed by Lemma 2.8. Set $X=V(G^{\prime})\smallsetminus(A\cup B)$ and
denote by $M_{A}$ and $M_{B}$ maximum matchings in $G^{\prime}$ from $X$ to
$A$ and from $X$ to $B$, respectively.

Since $|X|=n-2s$ we have $|M_{A}|,|M_{B}|\leq n-2s$, wherefore the sets
$A_{*}=B\smallsetminus V(M_{B})$ and $B_{*}=A\smallsetminus V(M_{A})$ satisfy
$|A_{*}|,|B_{*}|\geq s-(n-2s)=3s-n$. Take arbitrary subsets
$A^{\prime}\subseteq A_{*}$, $B^{\prime}\subseteq B_{*}$ of size $3s-n$, and
let $G$ denote the graph arising from $G^{\prime}$ by applying first
$\mathbf{Sym}(A,A^{\prime})$ and then $\mathbf{Sym}(B,B^{\prime})$. Two
successive applications of Fact 2.4 and Lemma 2.5 tell us that $G$ is
triangle-free, $\alpha(G)=s$, and $e(G)\geq e(G^{\prime})$. Thus, we arrive at
a graph $G\in\mathscr{E}(n,s)$ for which (2.1) holds. ∎

##  3\. The proof of Theorem 1.2

###  3.1. Andrásfai’s result

Let us recall that $g_{2}(n,s)=n^{2}-4ns+5s^{2}$. The main result of this
subsection, Proposition 3.2 below, asserts that this expression is an upper
bound on the number of edges of triangle-free $n$-vertex graphs satisfying a
less restrictive condition than $\alpha(G)\leq s$. Therefore, this result
provides a technical strengthening of Andrásfai’s theorem quoted in the
introduction. Our reason for dealing with such a statement here is that we
refer to it in the proof that $\mathrm{ex}(n,s)\leq g_{3}(n,s)$. We start with
the following observation.

######  Lemma 3.1.

Let $n$ and $s$ be positive integers with
$s\in\bigl{[}\frac{1}{3}n,\frac{1}{2}n\bigr{]}$ and suppose that $G$ is a
triangle-free graph on $n$ vertices containing two disjoint independent sets
$A$ and $A^{\prime}$ with $|A|=s$ and $|A^{\prime}|\geq 3s-n$. If

  1. ( )

$\deg(a)\leq s$ for all $a\in A$,

and

  1. ( )

$\mathrm{N}(a^{\prime})=A$ for all $a^{\prime}\in A^{\prime}$,

then $e(G)\leq n^{2}-4ns+5s^{2}$.

###### Proof.

By passing to a subset if necessary we may assume $|A^{\prime}|=3s-n$. The
graph $G-(A\cup A^{\prime})$ has $n-s-(3s-n)=2(n-2s)$ vertices, so by Mantel’s
theorem it has at most $(n-2s)^{2}$ edges. By ( ) ‣ 3.1 all edges of $G-A$ are
actually edges of $G-(A\cup A^{\prime})$ and thus we have

$e(G)\leq\sum_{a\in A}\deg(a)+(n-2s)^{2}\,.$

Owing to ( ) ‣ 3.1 this leads to $e(G)\leq s^{2}+(n-2s)^{2}=n^{2}-4ns+5s^{2}$,
as desired. ∎

We remark that the tools we have developed so far lead to a short proof of
Andrásfai’s main result in [A].

###### Proof of Theorem 1.1.

Due to Lemma 2.9 there exists a graph $G\in\mathscr{E}(n,s)$ containing two
disjoint independent sets $A$ and $A^{\prime}$ with

$|A|=s,\quad|A^{\prime}|=3s-n,\quad\text{and}\quad K(A^{\prime},A)\subseteq
E(G)\,.$ (3.1)

Recall that the absence of triangles in $G$ implies
$\Delta(G)\leq\alpha(G)\leq s$. Thus $G$ and the sets $A$, $A^{\prime}$
satisfy the hypothesis of Lemma 3.1 and, consequently,

$\mathrm{ex}(n,s)=e(G)\leq n^{2}-4ns+5s^{2}\,.$

On the other hand, Fact 1.5 shows $\mathrm{ex}(n,s)\geq n^{2}-4ns+5s^{2}$.
(See also the blow-up of the pentagon presented in Figure 1.1.) ∎

The main result of this subsection is a generalisation of Theorem 1.1 that
allows vertices whose degree is larger than $s$. On the other hand, if one
applies the statement that follows to a triangle free graph $G$ with
$\alpha(G)=s\leq\tfrac{1}{2}n$, then $Z=\varnothing$ and an arbitrary choice
of $Q$ leads to the estimate $e(G)\leq n^{2}-4ns+5s^{2}$.

######  Proposition 3.2.

For $s\in\bigl{[}\frac{1}{3}n,\frac{1}{2}n\bigr{]}$, let $G$ be a triangle-
free graph on $n$ vertices containing an independent set $A$ of size $s$, for
which $\alpha(G-A)\leq s$. Let

$Z=\\{v\in V(G)\smallsetminus A\colon\deg(v)>s\\}$

and let $Q\subseteq V(G)\smallsetminus(A\cup Z)$ be any set with $|Q|\geq
3s-n$. If every independent set $Z^{\prime}\subseteq Z$ is matchable into
$V(G)\smallsetminus(A\cup Z^{\prime}\cup Q)$, then

$e(G)\leq n^{2}-4ns+5s^{2}\,.$

###### Proof.

Let $n$ and $s$ be fixed and assume for the sake of contradiction, that there
exists a counterexample, i.e., a triple $(G,A,Q)$ satisfying all the
assumptions of Proposition 3.2, but for which $G$ has more than
$n^{2}-4ns+5s^{2}$ edges. Among all such counterexamples we choose one for
which the size of the set

$Q^{\prime}=\\{q\in Q\colon\mathrm{N}(q)=A\\}$

is as large as possible. Observe that Lemma 3.1 applied to $Q^{\prime}$ here
in place of $A^{\prime}$ there yields $|Q^{\prime}|<3s-n$, whence

$Q^{\prime}\neq Q\,.$ (3.2)

Next we use the maximality of $Q^{\prime}$ for showing that the assumption
$\alpha(G-A)\leq s$ holds with equality.

######  Claim 3.3.

There is an independent set $B\subseteq V(G)\smallsetminus A$ of size $s$.

###### Proof.

Assume $\alpha(G-A)\leq s-1$. Owing to (3.2) we may pick a vertex $q_{*}\in
Q\smallsetminus Q^{\prime}$ and apply $\mathbf{Sym}(A,q^{*})$ to $G$, thus
getting a graph $G^{*}$. By Fact 2.4 and $q^{*}\not\in Z$ we know that $G^{*}$
is triangle-free and has at least as many edges as $G$. Clearly,
$\alpha(G^{*}-A)\leq\alpha(G-A)+1\leq s$ and the assumption of Proposition 3.2
holds for $G^{*}$ and the sets $A$, $Q$, and

$Z^{*}=\\{v^{*}\in V(G^{*})\smallsetminus
A\colon\deg_{G^{*}}(v^{*})>s\\}\subseteq Z\,.$

Since $|Q^{\prime}\cup\\{q^{*}\\}|>|Q^{\prime}|$, the maximality of
$|Q^{\prime}|$ implies that $(G^{*},A,Q)$ cannot be a counterexample to our
result, which yields

$e(G)\leq e(G^{*})\leq n^{2}-4ns+5s^{2}\,,$

contrary to the choice of $(G,A,Q)$. Thereby Claim 3.3 is proved. ∎

Working with the set $B$ obtained in the previous claim we define
$X=V(G)\smallsetminus(A\cup B)$ and $Z^{\prime}=Z\cap B$. Due to the
independence of $B$ and our hypothesis $Z^{\prime}$ is matchable into $X$. So
Fact 2.3 applied to $Z^{\prime}$, $B$, and $X$ here in place of $R^{\prime}$,
$R$, and $S$ there yields a maximum matching $M$ between $B$ and $X$ which
covers $Z^{\prime}$.

Now we set $B^{\prime}=B\smallsetminus V(M)$ and look at the graph
$G^{\prime}=\mathbf{Sym}(G\,|\,A,B^{\prime})$. Note that

$|B^{\prime}|\geq s-|X|=s-(n-2s)=3s-n\,.$

Fact 2.4 reveals that $G^{\prime}$ is triangle-free and satisfies
$e(G^{\prime})\geq e(G)$. Lemma 2.2 applied to $G-A$, $B$, and $M$ reveals
$\alpha(G^{\prime}-A)=\alpha(G-A)=s$ and, consequently, every $a\in A$ has at
most $s$ neighbours in $G^{\prime}$. Thus $G^{\prime}$, $A$, and $B^{\prime}$
here in place of $G$, $A$, and $A^{\prime}$ there satisfy the assumptions of
Lemma 3.1, meaning that

$e(G)\leq e(G^{\prime})\leq n^{2}-4ns+5s^{2}\,.$

This contradiction to $(G,A,Q)$ being a counterexample establishes Proposition
3.2. ∎

###  3.2. Blow-ups of Wagner graphs

The present subsection completes the proof of Theorem 1.2, asserting that
every graph $G\in\mathscr{E}(n,s)$ satisfies $e(G)\leq 3n^{2}-15ns+20s^{2}$.
Recall that by Lemma 2.8 any such graph $G$ contains two disjoint independent
sets $A$ and $B$ of size $s$. Our next result shows that if there exists a
further independent set of size $s$ having appropriate intersections with $A$
and $B$, then we can reach our goal.

######  Lemma 3.4.

Given $n\geq s\geq 0$ let $G$ be a triangle-free graph on $n$ vertices with
$\alpha(G)=s$. If $G$ contains three independent sets $A$, $B$, and $C$ of
size $s$ such that $A\cap B,A\cap C=\varnothing$ and $|B\cap C|\leq n-2s$,
then

$e(G)\leq 3n^{2}-15ns+20s^{2}\,.$

###### Proof.

Recall that by the case $k=3$ of Fact 2.6 we may assume
$\frac{3}{8}n<s<\frac{2}{5}n$. Our argument is reminiscent of the proof of
Lemma 2.9. Fix three independent sets $A$, $B$, and $C$ in $G$ such that $A$
is disjoint to $B$, $C$ and $|B\cap C|\leq n-2s$.

######  Claim 3.5.

We may assume that there are sets $B^{\prime}\subseteq A$,
$C^{\prime}\subseteq A\smallsetminus B^{\prime}$, and $A^{\prime}\subseteq
B\cap C$ of size $|A^{\prime}|=|B^{\prime}|=|C^{\prime}|=3s-n$ such that

$K(A^{\prime},A)\cup K(B^{\prime},B)\cup K(C^{\prime},C)\subseteq E(G)\,.$

###### Proof.

Take a maximum matching $M_{B}$ from $V(G)\smallsetminus(A\cup B)$ into $A$
and consider the graph $G_{1}=\mathbf{Sym}\bigl{(}G\,|\,B,A\smallsetminus
V(M_{B})\bigr{)}$. By Fact 2.4 this graph is triangle-free and satisfies
$e(G_{1})\geq e(G)$. Lemma 2.5 yields $\alpha(G_{1})=s$ and one checks easily
that $A$, $B$, and $C$ are still independent in $G_{1}$. Moreover,

$|A\smallsetminus V(M_{B})|\geq|A|-|V(G)\smallsetminus(A\cup
B)|=s-(n-2s)=3s-n>0$

so there is a set $B^{\prime}\subseteq A\smallsetminus V(M_{B})$ with
$|B^{\prime}|=3s-n$ and clearly we have $K(B^{\prime},B)\subseteq E(G_{1})$.

Next we observe that the assumption $|B\cap C|\leq n-2s$ entails
$|B\smallsetminus C|\geq 3s-n=|B^{\prime}|$ and therefore in $G_{1}$ the set
$B^{\prime}$ is matchable into $B\smallsetminus C$, which is a subset of
$V(G)\smallsetminus(A\cup C)$. So by Fact 2.3 there is a maximum matching
$M_{C}$ from $V(G)\smallsetminus(A\cup C)$ to $A$ which covers all vertices in
$B^{\prime}$. As in the previous paragraph one proves that the graph
$G_{2}=\mathbf{Sym}(G_{1}\,|\,C,A\smallsetminus V(M_{C}))$ is triangle-free,
has independence number $s$ and at least as many edges as $G_{1}$. Also, as
before one finds a set $C^{\prime}\subseteq A\smallsetminus V(M_{C})$ with
$|C^{\prime}|=3s-n$ and observes $K(C^{\prime},C)\subseteq E(G_{2})$. The sets
$A$, $B$, and $C$ are still independent in $G_{2}$ and our reason for
insisting on $B^{\prime}\subseteq V(M_{C})$ was that it ensures
$C^{\prime}\subseteq A\smallsetminus B^{\prime}$.

Finally, we let $M_{A}$ be a maximum matching in $G_{2}$ from
$V(G)\smallsetminus(A\cup B)$ to $B$ and put
$G_{3}=\mathbf{Sym}\bigl{(}G_{2}\,|\,A,B\smallsetminus V(M_{A})\bigr{)}$.
Standard arguments show that $G_{3}$ is triangle-free and satisfies
$\alpha(G_{3})=s$ as well as $e(G_{3})\geq e(G_{2})$. Furthermore, there is a
set $A^{\prime}\subseteq B\smallsetminus V(M_{A})$ with $|A^{\prime}|=3s-n$
such that $K(A^{\prime},A)\subseteq E(G_{3})$. Moreover, since $C\cup
A^{\prime}$ is an independent set, we have $A^{\prime}\subseteq C$.
Altogether, the graph $G_{3}$ has all desired properties and owing to
$e(G_{3})\geq e(G)$ we may continue the proof with $G_{3}$ instead of $G$.
This proves Claim 3.5. ∎

Now we set $n^{*}=4n-9s$, $s^{*}=n-2s$, $G^{*}=G-(A^{\prime}\cup
B^{\prime}\cup C^{\prime})$, and $A^{*}=B\smallsetminus A^{\prime}$,
$Q^{*}=C\smallsetminus B$.

######  Claim 3.6.

The numbers $n^{*}$ and $s^{*}$ as well as the triple $(G^{*},A^{*},Q^{*})$
satisfy the hypothesis of Proposition 3.2.

###### Proof.

A quick calculation based on $s\in\bigl{[}\frac{1}{3}n,\frac{2}{5}n\bigr{]}$
shows that $n^{*}>0$ and $s^{*}\in\bigl{[}\frac{1}{3}n^{*},\frac{1}{2}n^{*}]$,
i.e., that the size of $s^{*}$ is in the appropriate range. Owing to

$|V(G^{*})|=n-(|A^{\prime}|+|B^{\prime}|+|C^{\prime}|)=n-3(3s-n)=4n-9s=n^{*}$

and $|A^{*}|=|B|-|A^{\prime}|=s-(3s-n)=n-2s=s^{*}$ the sets $V(G^{*})$ and
$A^{*}$ have the correct size. Next, we would like to show
$\alpha(G^{*}-A^{*})\leq s^{*}$. If $J\subseteq V(G^{*})\smallsetminus A^{*}$
is independent in $G^{*}$, then $J\cup B^{\prime}$ is independent in $G$, and
thus we have $|J|\leq s-|B^{\prime}|=s^{*}$, as desired.

Regarding the set

$Z^{*}=\\{v\in V(G^{*})\smallsetminus A^{*}\colon\deg_{G^{*}}(v)>s^{*}\\}$

we contend

$Z^{*}\subseteq V(G)\smallsetminus(A\cup B\cup C)\,.$ (3.3)

Indeed, if $v\in V(G^{*})\cap A$, then
$\deg_{G^{*}}(v)=\deg_{G}(v)-|A^{\prime}|\leq s-(3s-n)=s^{*}$ and the same
reasoning applies to $B$ and $C$ in place of $A$ as well.

As a consequence of (3.3) we have $Q^{*}\subseteq
V(G^{*})\smallsetminus(A^{*}\cup Z^{*})$, as required. The assumption $|B\cap
C|\leq n-2s$ implies $|Q^{*}|=s-|B\cap C|\geq 3s-n=3s^{*}-n^{*}$, so $Q^{*}$
is sufficiently large for our purposes.

Finally, if $Z^{\prime}\subseteq Z^{*}$ is independent in $G^{*}$, then
$Z^{\prime}$ is also independent in $G$ and (3.3) shows that $Z^{\prime}$ has
to be disjoint to $A$. Thus, Fact 2.1 tells us that in $G$ there is a matching
$M$ from $Z^{\prime}$ to $A$. By Claim 3.5 and (3.3) such a matching can only
use the part $A\smallsetminus(B^{\prime}\cup C^{\prime})$ of $A$, meaning that
$Z^{\prime}$ is indeed matchable into $V(G^{*})\smallsetminus(A^{*}\cup
Z^{\prime}\cup Q^{*})$. Thereby Claim 3.6 is proved. ∎

Now the foregoing claim and Proposition 3.2 result in

$e(G^{*})\leq{n^{*}}^{2}-4n^{*}s^{*}+5{s^{*}}^{2}=5n^{2}-24ns+29s^{2}\,,$

so

$\displaystyle e(G)$
$\displaystyle=|B||B^{\prime}|+|C||C^{\prime}|+|A\smallsetminus(B^{\prime}\cup
C^{\prime})||A^{\prime}|+e(G^{*})$ $\displaystyle\leq
2s(3s-n)+(2n-5s)(3s-n)+(5n^{2}-24ns+29s^{2})$
$\displaystyle=3n^{2}-15ns+20s^{2}\,.\qed$

Perhaps somewhat surprisingly, the previous result allows us to study a
similar configuration, where $C$ is no longer disjoint to one of $A$ and $B$.

######  Lemma 3.7.

Suppose $n\geq s\geq 0$ and let $G$ be a triangle-free graph on $n$ vertices
with $\alpha(G)=s$ containing two disjoint independent sets $A$ and $B$ of
size $s$, which in turn have subsets $A^{\prime}\subseteq B$,
$B^{\prime}\subseteq A$ with $|A^{\prime}|=|B^{\prime}|=3s-n$ and

$K(A^{\prime},A)\cup K(B^{\prime},B)\subseteq E(G)\,.$

If $G$ contains a further independent set $C$ of size $s$ intersecting both
$A$ and $B$, then

$e(G)\leq 3n^{2}-15ns+20s^{2}\,.$

###### Proof.

Regarding $n$ and $s$ as being fixed we consider a counterexample with $|Q|$
maximal, where

$Q=\\{q\in V\colon\mathrm{N}(q)=C\\}\,.$

Let us start with a few basic observations. First of all, we have $C\cap
A^{\prime}=\varnothing$, because $K(A^{\prime},A)\subseteq E(G)$ and $A$
intersects $C$. Similarly, one checks $C\cap B^{\prime}=\varnothing$.
Furthermore, since $\Delta(G)\leq\alpha(G)=s$, the sets $(C\smallsetminus
A)\cup A^{\prime}$ and $(C\smallsetminus B)\cup B^{\prime}$ are independent.
Hence they consist of at most $s=|C|$ vertices each, which yields

$|A\cap C|\geq|A^{\prime}|=3s-n\quad\text{and}\quad|B\cap
C|\geq|B^{\prime}|=3s-n\,.$ (3.4)

Finally, using the definition of $Q$, the independence of $A$, $B$, and $C$,
and the fact that $C$ meets $A$ and $B$, one obtains

$Q\cap(A\cup B\cup C)=\varnothing\,.$ (3.5)

The maximality of $Q$ together with Lemma 3.4 leads to the following
statement.

######  Claim 3.8.

We have $V(G)=A\cup B\cup C\cup Q$.

###### Proof.

Assume contrariwise, that there exists a vertex $q\in V(G)\smallsetminus(A\cup
B\cup C\cup Q)$ and set $G^{\prime}=\mathbf{Sym}(G\,|\,C,q)$. The sets $A$,
$B$, $A^{\prime}$, $B^{\prime}$, and $C$ still satisfy the hypothesis of Lemma
3.7 in $G^{\prime}$. Moreover, Fact 2.4 tells us that $G^{\prime}$ is a
triangle-free graph with $e(G^{\prime})\geq e(G)$. Due to the maximality of
$|Q|$ all this is only possible if $\alpha(G^{\prime})>s$. This means that
there exists an independent set $D^{\prime}=\\{q\\}\cup D\subseteq
V(G^{\prime})$ in $G^{\prime}$ with $|D^{\prime}|>s$. As usual, $D$ needs to
be an independent set in $G$ with $|D|=s$ and $C\cap D=\varnothing$.

The case $k=3$ of Fact 2.6 allows us to assume $s>3n/8$, which leads to

$|A^{\prime}|+|B^{\prime}|+|C|+|D|=8s-2n>n\,.$

Thus $D\cap(A^{\prime}\cup B^{\prime})\neq\varnothing$ and without loss of
generality we may suppose $D\cap A^{\prime}\neq\varnothing$, which in turn
implies $D\cap A=\varnothing$. Moreover, we have

$|B\cap D|\leq|B\smallsetminus C|=|B|-|B\cap
C|\overset{\eqref{eq:CcapA}}{\leq}n-2s\,.$

So altogether the graph $G$ and the sets of vertices $A$, $B$, and $D$ satisfy
the assumption of Lemma 3.4 with $D$ here in place of $C$ there. But now
$e(G)\leq 3n^{2}-15ns+20s^{2}$ contradicts $G$ being a counterexample and,
hence, establishes Claim 3.8. ∎

Continuing the proof of Lemma 3.7 we observe that, owing to the definition of
$Q$, the set $(A\smallsetminus C)\cup Q$ is independent, and so $|Q|\leq|A\cap
C|$. In combination with Claim 3.8 this yields

$n\overset{\eqref{eq:QABC}}{=}|A\cup B\cup C|+|Q|\leq 3s-|A\cap C|-|B\cap
C|+|A\cap C|=3s-|B\cap C|\overset{\eqref{eq:CcapA}}{\leq}n\,,$

and equality holds throughout. In particular, we have $|Q|=|A\cap C|$ and
consequently $E=(A\smallsetminus C)\cup Q$ is an independent set consisting of
$s$ vertices. To complete the proof it suffices to show that the assumptions
of Lemma 3.4 are satisfied for $B$, $A$, and $E$ here in place of $A$, $B$,
and $C$ there. The condition $B\cap E=\varnothing$ is clear and in the light
of (3.4) we obtain

$|A\cap E|=|A\smallsetminus C|=|A|-|A\cap
C|\overset{\eqref{eq:CcapA}}{\leq}s-(3s-n)=n-2s\,.\qed$

We proceed to the main result of this article, which we reformulate as
follows.

######  Theorem 3.9.

If $n\geq s\geq 0$, then

$\mathrm{ex}(n,s)\leq g_{3}(n,s)=3n^{2}-15ns+20s^{2}\,.$ (3.6)

Moreover, for $s\in\bigl{[}\frac{3}{8}n,\frac{2}{5}n\bigr{]}$ equality holds.

###### Proof.

The statement on equality follows from the first part in view of Fact 1.5 (see
also Figure 1.2), so it remains to establish (3.6).

Arguing indirectly we take a counterexample $(n,s)$ with $n$ minimum. The case
$k=3$ of Fact 2.6 tells us

$\frac{n}{3}<\frac{3n}{8}<s<\frac{2n}{5}<\frac{n}{2}\,.$ (3.7)

By Lemma 2.9 there exists a graph $G\in\mathscr{E}(n,s)$ which contains two
disjoint independent sets $A$ and $B$ of size $s$ such that there are sets
$A^{\prime}\subseteq B$, $B^{\prime}\subseteq A$ with
$|A^{\prime}|=|B^{\prime}|=3s-n\overset{\eqref{eq:sn3}}{>}0$ and

$K(A^{\prime},A)\cup K(B^{\prime},B)\subseteq E(G)\,.$

Pick two arbitrary vertices $a\in A^{\prime}$, $b\in B^{\prime}$ and set
$G^{\prime}=G-\\{a,b\\}$. We shall consider two cases depending on the
independence number of $G^{\prime}$.

Case 1. $\alpha(G^{\prime})=s$.

Take an independent set $C\subseteq V(G^{\prime})$ of size $s$. Since the set
$C\cup\\{a\\}$ has size $s+1$ and thus fails to be independent in $G$, we have
$C\cap A\neq\varnothing$. A similar argument shows $C\cap B\neq\varnothing$
and, hence, $C$ is as demanded by Lemma 3.7. Consequently we have $e(G)\leq
3n^{2}-15ns+20s^{2}$, which contradicts $(n,s)$ being counterexample.

Case 2. $\alpha(G^{\prime})\leq s-1$.

Observe that the minimality of $n$ leads to

$\displaystyle e(G^{\prime})$ $\displaystyle\leq
3(n-2)^{2}-15(n-2)(s-1)+20(s-1)^{2}$
$\displaystyle=(3n^{2}-15ns+20s^{2})+(3n-10s+2)\,.$

Since (3.7) yields $3n+1\leq 8s$, this implies

$e(G^{\prime})\leq(3n^{2}-15ns+20s^{2})+(1-2s)$

and consequently we have

$e(G)=e(G^{\prime})+(2s-1)\leq 3n^{2}-15ns+20s^{2}\,,$

which again contradicts the assumption that $(n,s)$ is a counterexample. ∎

## References


# Random walks on regular trees can not be slowed down

Omer Angel  Department of Mathematics, University of British Columbia
<EMAIL_ADDRESS>,  Jacob Richey  Department of Mathematics, University of
British Columbia<EMAIL_ADDRESS>,  Yinon Spinka  Department of
Mathematics, University of British Columbia School of Mathematical Sciences.
Tel Aviv University. Tel Aviv 6997801, Israel<EMAIL_ADDRESS>and  Amir
Yehudayoff  Department of Mathematics, Technion-IIT<EMAIL_ADDRESS>
###### Abstract.

A random walk on a regular tree (or any non-amenable graph) has positive
speed. We ask whether such a walk can be slowed down by applying carefully
chosen time-dependent permutations of the vertices. We prove that on trees the
random walk can not be slowed down.

## 1 Introduction

One of the classical results relating the geometry of a space to the behaviour
of random walks on the space is that on any non-amenable graph the random walk
has positive speed, in that $\liminf_{t\to\infty}t^{-1}|X_{t}|$ exists and is
a.s. positive. On transitive graphs the limit is even an almost sure constant.
In particular, on the $d$ regular tree, denoted $\mathbb{T}_{d}$, the speed
for the simple random walk is $\frac{d-2}{d}$, which is positive as long as
$d>2$. The motivation for this paper is the question: Can we slow down the
particle?

Suppose that after each step $t$ of the random walk, we are allowed to apply
some permutation $\pi_{t}$ to the vertices of the tree, so that if the
particle is at $v$ it is transported to $\pi_{t}(v)$. If we observe the
particle and can choose $\pi_{t}$ accordingly, then we can constantly push it
back to any vertex we wish, so that it never moves. Our main finding is that
if the permutations do not depend on the location of the particle, then the
particle can not be slowed down.

### 1.1 Permuted random walks

We start by considering lazy random walks, where the results are cleaner for
mostly technical reasons (see the discussion below). We start by introducing
some notations. Fix $d\geq 2$, and let $\mathbb{T}=\mathbb{T}_{d}$ denote the
rooted infinite $d$-regular tree. The vertex set is denoted by
$V=V(\mathbb{T}_{d})$. The root of the tree is denoted by $v_{0}$. The depth
$|v|$ of a vertex $v\in V$ is its distance from the root. The neighborhood
$N(v)$ of $v$ is the set of vertices $u$ that are of distance at most one from
$v$. Note that since we are considering lazy random walks, it is convenient to
have $v\in N(v)$. Thus the size of $N(v)$ is $d+1$.

Let $(X_{t})_{t=0}^{\infty}$ be a lazy random walk on $\mathbb{T}$ started at
the root. The laziness parameter $\mathbb{P}(X_{t+1}=X_{t})$ is chosen to be
$\frac{1}{d+1}$. That is, $X_{0}=v_{0}$ and $X_{t+1}$ is a uniformly random
element of $N(X_{t})$. The (empirical) speed of $(X_{t})$ is defined to be the
process $(t^{-1}|X_{t}|)$. The strong law of large numbers implies that the
speed a.s. converges to $\frac{d-2}{d+1}$. Note that this also holds in the
case $d=2$ where $\mathbb{T}_{2}$ is the line and the speed is $0$. For more
on random walks on trees see e.g. [5, 9] and references therein.

The model we suggest for studying the slowing down of particles is as follows.
Before the particle starts to move, we can choose a sequence
$(\pi_{t})_{t=1}^{\infty}$ of permutations of $V$. (These do not need to be
finitary; any bijections of $V$ will do.) The permutation $\pi_{t}$ is applied
on the random walk at time $t$. Thus the permuted random walk $(Y_{t})$ starts
at the root, and its position at time $t+1$ is defined by
$Y_{t+1}=\pi_{t+1}(Y^{\prime}_{t+1})$, where $Y^{\prime}_{t+1}$ is a uniformly
random vertex in $N(Y_{t})$. The (empirical) speed of $(Y_{t})$ is the process
$(t^{-1}|Y_{t}|)$. In contrast with $(X_{t})$, the permuted random walk may
not have a limiting speed. The lower speed of the permuted random walk is
defined by $\liminf_{t\to\infty}t^{-1}|Y_{t}|$.

Permuted random walk have been studied before, both on their own merit, and as
a tool towards other ends. Pymar and Sousi [8] established uniform bounds on
hitting times for permuted random walks on finite regular graphs. Ganguly and
Peres [3] studied walks on an interval with a fixed uniform random
permutation. Recently, Chatterjee and Diaconis [1, 2] demonstrated that mixing
of certain Markov chains can be significantly sped up by adding a
deterministic permutation after each move. In a different direction, Gouëzel
[4] used permuted random walks to establish large deviation lower bounds on
the speed of random walks on hyperbolic spaces without moment assumptions on
the step distribution. One idea here is to condition on the long steps of the
walk, and consider the process as a permuted version of a walk with bounded
steps for which other methods can apply. The question at the heart of this
paper arose following a presentation of that work.

Our main result is that no matter how we select the permutations $(\pi_{t})$,
the permuted walk $(Y_{t})$ is not slower than $(X_{t})$.

######  Theorem 1.1.

For every $d\geq 2$, every sequence $(\pi_{t})$ of permutations of
$V(\mathbb{T}_{d})$, and every time $t\geq 0$, the depth of the permuted
random walk $|Y_{t}|$ stochastically dominates the depth of the lazy random
walk $|X_{t}|$. That is, for all $t,n\geq 0$,

$\mathbb{P}[|Y_{t}|\geq n]\geq\mathbb{P}[|X_{t}|\geq n].$

In particular, $\mathbb{E}|Y_{t}|\geq\mathbb{E}|X_{t}|$ for all $t\geq 0$, and
$\liminf_{t\to\infty}t^{-1}|Y_{t}|\geq\frac{d-2}{d+1}$ almost surely.

######  Remark 1.2.

The proesses $(X_{t})$ and $(Y_{t})$ in Theorem 1.1 correspond to a lazy
random walk that stays put with probability $\frac{1}{d+1}$. Theorem 1.1 holds
verbatim (with the obvious change to the constant $\frac{d-2}{d+1}$) as long
as the probability to stay put is at least $\frac{1}{d+1}$. In particular, it
holds when the chance to stay put is one half, which is a more common
definition of the lazy random walk. For details, see the remark after the
proof of Theorem 1.1.

Note that the theorem is informative even for $d=2$, where the limit speed is
zero. However, the laziness is required for Theorem 1.1 to hold. Indeed, for
the non-lazy walk on $\mathbb{T}_{d}$ we can have
$\mathbb{E}|Y_{1}|<\mathbb{E}|X_{1}|$ (or for any other $t$).

Theorem 1.1 is a special case of a more general phenomenon, which we describe
in the next two theorems. For a distribution $p$ on $V$, define
$p^{*}:\mathbb{N}\to[0,1]$ by letting $p^{*}(j)$ be the total mass of the $j$
largest atoms in $p$, or equivalently,

$p^{*}(s)=\max\\{p(J):J\subset V,|J|=s\\}.$

We say that a distribution $p$ majorizes a distribution $q$ if $p^{*}(j)\geq
q^{*}(j)$ for all $j\in\mathbb{N}$.

Denote by $p_{t}$ the distribution of $X_{t}$ and by $q_{t}$ the distribution
of $Y_{t}$, depending implicitly on the fixed permutations $(\pi_{t})$. The
stochastic domination asserted in Theorem 1.1 is a consequence of the
following more technical statement. The main reasons are that the distribution
$p_{t}$ is spherically symmetric and monotone in depth; for more details, see
Section 3.

######  Theorem 1.3.

For every $t\geq 0$, the distribution $p_{t}$ majorizes $q_{t}$.

The fact that $p_{t}$ majorizes $q_{t}$ can be interpreted as saying that the
amount of disorder in $q_{t}$ is at most that of $p_{t}$. Concretely, the
theorem implies that the Shannon entropy of $Y_{t}$ is at most the Shannon
entropy of $X_{t}$. There is no way to increase the entropy of a lazy random
walk on a regular tree by applying time dependent permutations.

A second interpretation of the theorem is that for every $t$, there is a
distribution $r_{t}$ on permutations of $V$, so that if $\sigma_{t}$ is
sampled from $r_{t}$ independently of $X_{t}$, then
$(X_{t},\sigma_{t}(X_{t}))$ has the same distribution as $(X_{t},Y_{t})$. In
other words, there is a distribution on a single permutation $\sigma_{t}$ that
allows to replace the iterative application of the $t$ permutations
$\pi_{1},\ldots,\pi_{t}$.

An even more general statement than Theorem 1.3 holds. Let $B_{n}=\\{v\in
V:|v|\leq n\\}$ denote the ball of radius $n\geq-1$ in the tree111The ball
$B_{-1}$ is empty. and $\partial B_{n}=B_{n}\setminus B_{n-1}$ the sphere of
radius $n$. Fix an order $v_{0},v_{1},v_{2},\ldots$ of $V$ with the following
property: for every $i<j$, it holds that $|v_{i}|\leq|v_{j}|$ and if
$|v_{i}|=|v_{j}|$ then the $d-1$ children of $v_{i}$ appear in the order
before the $d-1$ children of $v_{j}$. Initial segments of the form
$\\{v_{0},v_{1},\dots,v_{i}\\}$ are called quasi-balls. Note that every ball
is a quasi-ball. A distribution $p$ on $V$ is called greedily arranged if
$p(v_{i})\geq p(v_{i+1})$ for every $i$.

######  Theorem 1.4.

Let $p$ and $q$ be distributions on $V$ and let $p^{\prime}$ and $q^{\prime}$
be the corresponding distributions after a single step of a lazy random walk
started at $p$ and $q$, respectively. If $p$ is greedily arranged and
majorizes $q$, then $p^{\prime}$ is greedily arranged and majorizes
$q^{\prime}$.

Theorems 1.1 and 1.3 follow by a simple inductive argument from the last
theorem using the following two observations. First, the initial distribution
$p_{0}$ is greedily arranged, and majorizes $q_{0}$. Second, if a distribution
$p$ majorizes $q$, then it also majorizes any rearrangement of $q$ (i.e., a
distribution of the form $q\circ\pi$ for a permutation $\pi$ of $V$). Thus
Theorem 1.4 implies that for every $t\geq 0$ and every finite $J\subset V$,

(1.1) $p_{t}(B)\geq q_{t}(J),$

where $B$ is the quasi-ball of size $|B|=|J|$.

### 1.2 Non-lazy random walks

The last result is particular to lazy random walks on regular trees. For non-
lazy walks, it is too strong to be true. The distribution of a simple non-lazy
random walk on a regular tree is not greedily arranged because the tree is
bipartite; in particular, (1.1) may fail already for $t=1$.

On the other hand, versions of the above theorems do hold for non-lazy walks,
as we describe next. The limit speed of a simple (non-lazy) random walk on
$\mathbb{T}_{d}$ is $\frac{d-2}{d}$ a.s. As noted, for such random walks, the
same stochastic domination as in Theorem 1.1 does not hold. Nonetheless, we
prove that it almost holds (at least for $d>2$, when the tree is not the
line).

Denote by $N^{\prime}(v)$ the $d$ neighbors of $v$ not including $v$. Let
$(S_{t})$ be a simple random walk so that $S_{0}=v_{0}$ and $S_{t+1}$ is
uniform in $N^{\prime}(S_{t})$. Let $(Z_{t})$ be a permuted simple random walk
so that $Z_{0}=v_{0}$ and $Z_{t+1}$ is $\pi_{t+1}(Z^{\prime}_{t+1})$, where
$Z^{\prime}_{t+1}$ is uniform in $N^{\prime}(Z_{t})$.

######  Theorem 1.5.

For every $d>2$, every sequence $(\pi_{t})$ of permutations of
$V(\mathbb{T}_{d})$, and every time $t\geq 1$, we have that $|Z_{t}|+2$
stochastically dominates $|S_{t}|$. In particular,
$\mathbb{E}|Z_{t}|\geq\mathbb{E}|S_{t}|-2$ for all $t\geq 0$, and
$\liminf_{t\to\infty}t^{-1}|Z_{t}|\geq\frac{d-2}{d}$ almost surely.

For $d=2$, the bound $\frac{d-2}{d}$ on the lower speed of $(Z_{t})$ trivially
holds, but the stronger claim in the theorem is false. One way to see this is
to take $\pi_{t}$ to be the identity up to some large time $2T$, and then map
via $\pi_{2T}$ all even integers in the range $[-2T,2T]$ to all integers in
$[-T,T]$ so that $\mathbb{E}|Z_{2T}|=\tfrac{1}{2}\mathbb{E}|S_{2T}|$.

We shall deduce Theorem 1.5 from the following modification of Theorem 1.4
which takes into account the periodicity of the non-lazy walk. The vertex set
can be partitioned according to parity into $V_{0}=\\{v\in V:|v|=0\mod 2\\}$
and $V_{1}=V\setminus V_{0}$. A distribution $p$ is called half-greedily
arranged if it is supported on one of $V_{0}$ or $V_{1}$, and $p(v_{i})\geq
p(v_{j})$ for every $i<j$ for which $v_{i}$ and $v_{j}$ have the same parity
(using the same ordering of $V$ as above).

######  Theorem 1.6.

Let $p$ and $q$ be distributions on $V$, and let $p^{\prime}$ and $q^{\prime}$
be the corresponding distributions after a single step of a non-lazy random
walk started at $p$ and $q$, respectively. If $p$ is half-greedily arranged
and majorizes $q$, then $p^{\prime}$ is half-greedily arranged and majorizes
$q^{\prime}$.

Although the distribution of $S_{t}$ is not greedily arranged, it is half-
greedily arranged. The theorem thus implies that the distribution of $S_{t}$
majorizes that of $Z_{t}$ for every $t\geq 0$ (although the distribution of
$|S_{t}|$ does not necessarily majorizes that of $|Z_{t}|$).

### 1.3 The speed process

Theorems 1.1 and 1.5 establish stochastic domination of the distance of a
standard (lazy/simple) random walk over the distance of a permuted random walk
_at any particular time_. It is natural to wonder whether such stochastic
domination holds for the corresponding processes, i.e., whether the two
processes can be coupled so that the distance of the permuted walk is always
at least the distance of the standard walk. Somewhat surprisingly, it turns
out this is not always possible. We focus on lazy random walks for
concreteness. As an example, consider a sequence of permutations $\pi$ in
which $\pi_{1}$ and $\pi_{2}$ are the identity permutation and $\pi_{3}$ is an
automorphism of $T$ which maps a neighbor of $v_{0}$ to $v_{0}$. A direct
computation yields that

$\mathbb{P}[|X_{2}|+|X_{3}|\leq
2]=\tfrac{1}{d+1}+\tfrac{4d}{(d+1)^{3}}<\tfrac{1}{d+1}+\tfrac{5d-1}{(d+1)^{3}}=\mathbb{P}[|Y_{2}|+|Y_{3}|\leq
2],$

so that $(|Y_{2}|,|Y_{3}|)$ does not stochastically dominate
$(|X_{2}|,|X_{3}|)$.

When $d=2$, this effect can be repeated and magnified over time. The next
result shows that for certain choices of permutations, even translations,
there are infinitely many times at which the distance of the permuted random
walk is much smaller (no matter how the two processes are coupled).

######  Theorem 1.7.

Fix $d=2$. There exists a sequence of permutations $(\pi_{t})$ of
$V(\mathbb{T}_{2})\cong\mathbb{Z}$, all of which are translations, such that
in any coupling of the lazy random walk process $(X_{t})$ and the permuted
random walk process $(Y_{t})$, almost surely,

(1.2) $\limsup_{t\to\infty}\frac{|X_{t}|-|Y_{t}|}{\sqrt{t\log\log
t}}=\frac{\sqrt{3}}{2}.$

When $d>2$, on the other hand, we show that the above cannot occur (not even
nearly) when the permutations are required to be automorphisms of
$\mathbb{T}_{d}$. This is the content of the result below. We do not know how
strong this effect can be for general permutations. For instance, we do not
know whether it is always possible to couple the two processes so that, almost
surely, $|X_{t}|\leq|Y_{t}|$ for all large enough $t$.

######  Theorem 1.8.

For every $d>2$ and every sequence of automorphisms $(\pi_{t})$ of
$\mathbb{T}_{d}$, there exists a coupling of the lazy random walk process
$(X_{t})$ and the permuted random walk process $(Y_{t})$ such that, almost
surely,

$|Y_{t}|-|X_{t}|\geq t^{1/2-o(1)}\qquad\text{as }t\to\infty.$

The theorem is interesting even when each $\pi_{t}$ is the identity. It states
that there is a way to couple two lazy random walks so that one is
significantly more distant than the other. The result is tight is the sense
that the $o(1)$ term cannot be dropped entirely. Our proof gives a
quantitative estimate for this term and yields that $t^{1/2-o(1)}$ can be
replaced with $\sqrt{t}/(\log^{C}t)$ for some constant $C>0$. See Lemma 5.2
and the second remark following it.

### 1.4 A spectral argument

One natural approach towards proving the results above is using spectral
methods (see [7] and references within). Specifically, the transition kernel
on $\ell^{2}(V)$ is a contraction with norm $\rho<1$, and application of a
permutation is an isometry on $\ell^{2}(V)$. Thus $\|q_{t}\|_{2}\leq\rho^{t}$
decays exponentially. A positive lower bound on the lower speed of $Y_{t}$
follows easily. Moreover, this argument holds for any non-amenable graph.
However, the resulting bound on the speed is not sharp.

The proof of a spectral gap uses an isoperimetric inequality for the tree. Not
surprisingly, our proofs also use isoperimetric inequalities; see Propositions
2.3 and 2.2 below. Proposition 2.3 is a non-standard isoperimetric inequality,
which takes into account the amount of “isolated” points in the set of
interest. Proposition 2.1 is a significant generalization of the isoperimetric
inequality using the language of majorization.

## 2 Isoperimetry

As noted, our arguments rely on isoperimetric properties of the tree. However,
to get the strongest possible comparison between the permuted and regular
random walks we need sharp isoperimetric inequalities, which we now proceed to
prove.

Recall that $N(v)$ is the neighborhood of a vertex $v$, including $v$ itself.
For $J\subset V$, the neighborhood of $J$ is defined by

$N(J)=\bigcup_{v\in J}N(v).$

To analyze the behavior of the random walk, we need to understand the boundary
in more detail. For $J\subset V$ and $i\in[d+1]$, define

$K_{i}(J)=\\{v\in V:|N(v)\cap J|\geq i\\}.$

In particular, the set $K_{1}(J)$ is the neighborhood $N(J)$.

A partition is a sequence $\mu=(\mu_{1},\mu_{2},\dots,\mu_{\ell})$ with
$\mu_{1}\geq\mu_{2}\geq\dots\geq\mu_{\ell}\geq 0$. Note that usually trailing
0’s are omitted, but for us it is convenient to have the length of the
partitions be fixed, so we may include 0’s. The size of the partition is
defined by $|\mu|=\sum_{i}\mu_{i}$. The dominance order on partitions is
defined as follows. For partitions $\mu,\lambda$, we write $\lambda\prec\mu$
if $|\mu|=|\lambda|$ and

(2.1) $\lambda_{1}+\dots+\lambda_{r}\leq\mu_{1}+\dots+\mu_{r},\qquad\text{ for
all $r$}.$

The following majorization statement is an extension of the standard
isoperimetric inequality for the tree.

######  Proposition 2.1.

Let $J\subset V$ be finite and let $B$ be the quasi-ball with $|B|=|J|$. Let
$k_{i}=|K_{i}(J)|$ and $m_{i}=|K_{i}(B)|$. Then $(k_{i})$ dominates $(m_{i})$
as partitions: $(k_{1},\dots,k_{d+1})\succ(m_{1},\dots,m_{d+1})$.

To prove this result, we need a couple of lemmas on the isoperimetric behavior
of the tree. Let $\kappa_{1}(J)$ denote the number of connected components
induced by $J$. Let $\kappa_{2}(J)$ denote the number of connected components
induced by $J$ in the graph in which edges are added between all pairs of
vertices that are at distance 2 from each other in the tree. The first lemma
is a formula for $|N(J)|$ for general $J$:

######  Proposition 2.2.

For every finite $J\subset V$,

$|N(J)|=(d-1)|J|+\kappa_{1}(J)+\kappa_{2}(J).$

###### Proof.

We prove the claim by induction on $|J|$. The base case when $|J|=0$ is
trivial. Let $J$ be non-empty. Let $v\in J$ be a vertex of maximum depth in
$J$. Let $N_{1}=N(v)\cap(J\setminus\\{v\\})$ and
$N_{2}=N(N(v))\cap(J\setminus\\{v\\})$. The following two equalities hold:

$\kappa_{1}(J\setminus\\{v\\})=\kappa_{1}(J)-\mathbf{1}_{\\{N_{1}=\emptyset\\}}\qquad\text{and}\qquad\kappa_{2}(J\setminus\\{v\\})=\kappa_{2}(J)-\mathbf{1}_{\\{N_{2}=\emptyset\\}}.$

The induction hypothesis implies

$|N(J\setminus\\{v\\})|=(d-1)|J|+\kappa_{1}(J)+\kappa_{2}(J)-(d-1+\mathbf{1}_{\\{N_{1}=\emptyset\\}}+\mathbf{1}_{\\{N_{2}=\emptyset\\}}).$

It remains to show that

$|N(J)|-|N(J\setminus\\{v\\})|=d-1+\mathbf{1}_{\\{N_{1}=\emptyset\\}}+\mathbf{1}_{\\{N_{2}=\emptyset\\}}.$

The left-hand side equals

$|N(J)\setminus N(J\setminus\\{v\\})|=|N(v)\setminus
N(J\setminus\\{v\\})|=d+1-|N(v)\cap N(J\setminus\\{v\\})|.$

So we need to show that

$|N(v)\cap
N(J\setminus\\{v\\})|=2-\mathbf{1}_{\\{N_{1}=\emptyset\\}}+\mathbf{1}_{\\{N_{2}=\emptyset\\}}=\mathbf{1}_{\\{N_{1}\neq\emptyset\\}}+\mathbf{1}_{\\{N_{2}\neq\emptyset\\}}.$

By the choice of $v$, there are at most two vertices in $N(v)\cap
N(J\setminus\\{v\\})$; the vertex $v$ and its parent. The vertex $v$ is in
$N(J\setminus\\{v\\})$ iff $N_{1}\neq\emptyset$. Its parent is in
$N(J\setminus\\{v\\})$ iff $N_{2}\neq\emptyset$. ∎

For the next lemma, we also need the following definitions. The sets of
isolated points in $J$ and connected points in $J$ are defined by

$\displaystyle\mathsf{iso}(J)=\\{v\in J:N(v)\cap
J=\\{v\\}\\}\quad\text{and}\quad\mathsf{con}(J)=J\setminus\mathsf{iso}(J).$

######  Proposition 2.3.

For every non-empty $J\subset V$,

$|N(J)|\geq\begin{cases}1+d|J|&\mathsf{con}(J)=\emptyset\\\
2+d|\mathsf{iso}(J)|+(d-1)|\mathsf{con}(J)|&\mathsf{con}(J)\neq\emptyset.\end{cases}$

###### Proof.

Using Proposition 2.2,

$\displaystyle|N(J)|$
$\displaystyle=(d-1)(|\mathsf{iso}(J)|+|\mathsf{con}(J)|)+\kappa_{1}(J)+\kappa_{2}(J)$
$\displaystyle\geq(d-1)(|\mathsf{iso}(J)|+|\mathsf{con}(J)|)+(|\mathsf{iso}(J)|+\mathbf{1}_{\\{\mathsf{con}(J)\neq\emptyset\\}})+1.\qed$

###### Proof of Proposition 2.1.

The fact that $(k_{i})$ and $(m_{i})$ are decreasing is obvious. These are
partitions of the same size $s=(d+1)|J|$. If $|J|=1$ then the statement
trivially holds, so we can assume $|J|>1$. The choice of order on $V$ implies
there is $n\geq 0$ so that $B_{n}\subseteq B\subsetneq B_{n+1}$, where $B_{n}$
is the ball of radius $n$. We can write

$|J|=|B|=|B_{n}|+a(d-1)+c,$

where $a,c$ are non-negative integers so that $c<d-1$.

The tree is simple enough so that we can compute all the $m_{i}$’s in terms of
these:

$\displaystyle m_{1}$ $\displaystyle=(d-1)|J|+2,$ $\displaystyle m_{2}$
$\displaystyle=|J|,$ $\displaystyle\forall\ 3\leq i\leq c+2\qquad m_{i}$
$\displaystyle=|B_{n-1}|+a+1,$ $\displaystyle\forall\ c+3\leq i\leq d+1\qquad
m_{i}$ $\displaystyle=|B_{n-1}|+a.$

The case $r=1$ of (2.1) now holds by Proposition 2.2:

$k_{1}=|N(J)|\geq(d-1)|J|+2=m_{1}.$

The case $r=2$ is proved as follows. If $k_{2}=0$ then $k_{i}=0$ for all
$i\geq 2$ and the proof is complete. On the other hand, if $k_{2}\geq 1$ then
by Proposition 2.3, and because $\mathsf{con}(J)\subseteq K_{2}(J)$,

$k_{1}+k_{2}\geq(d-1)|J|+|\mathsf{iso}(J)|+\mathbf{1}_{\\{\mathsf{con}(J)\neq\emptyset\\}}+1+k_{2}\geq
d|J|+2=m_{1}+m_{2}.$

For $r\in\\{3,4,\ldots,d\\}$, proceed by induction. Because $k_{r}\geq
k_{r+1}\geq\ldots\geq k_{d+1}$, we have

$k_{r}\geq a_{r}:=\frac{s-\sum_{i\in[r-1]}k_{i}}{d-r+2}.$

By induction,

$\displaystyle\sum_{i\in[r]}k_{i}$ $\displaystyle\geq
a_{r}+\sum_{i\in[r-1]}k_{i}$
$\displaystyle=\frac{s}{d-r+2}+\frac{d-r+1}{d-r+2}\sum_{i\in[r-1]}k_{i}$
$\displaystyle\geq\frac{s}{d-r+2}+\frac{d-r+1}{d-r+2}\sum_{i\in[r-1]}m_{i}$
$\displaystyle=b_{r}+\sum_{i\in[r-1]}m_{i},$

where

$\displaystyle b_{r}:=\frac{s-\sum_{i\in[r-1]}m_{i}}{d-r+2}.$

If $r\leq c+2$, then

$\displaystyle b_{r}$
$\displaystyle=\frac{(c+2-r+1)(|B_{n-1}|+a+1)+(d+1-c-2)(|B_{n-1}|+a)}{d-r+2}$
$\displaystyle=\frac{(d-r+2)(|B_{n-1}|+a)+c+2-r}{d-r+2},$

and if $r>c+2$, then

$\displaystyle b_{r}=\frac{(d-r+2)(|B_{n-1}|+a)}{d-r+2}.$

It follows that $m_{r}=\lceil b_{r}\rceil$. All $k_{i}$’s and $m_{i}$’s are
integers, so the desired inequality follows. ∎

## 3 Lazy random walks

The following proposition presents the key link between the isoperimetric
inequality and the behavior of random walks.

######  Proposition 3.1.

Let $J\subset V$ be finite and let $B$ be the quasi-ball with $|B|=|J|$. Let
$k_{i}=|K_{i}(J)|$ and $m_{i}=|K_{i}(B)|$. For every distribution $q$,

$\sum_{i\in[d+1]}q^{*}(k_{i})\leq\sum_{i\in[d+1]}q^{*}(m_{i}).$

This may seem surprising until one realizes that $q^{*}$ can be any function
on $\mathbb{N}$ that is increasing from $0$ to $1$ and is concave. The proof
of Proposition 3.1 is based on the following majorization inequality, known as
the Hardy–Littlewood–Pólya inequality and Karamata’s inequality, a version of
which was first proved by Schur; see e.g. [6, Theorem 3.C.1]. Note that the
definition of the dominance order $\mu\succ\lambda$ extends verbatim to
partitions of a real number with real instead of integer parts, and so this
applies also for non-integer dominated sequences. In our setting, $k_{i}$ and
$m_{i}$ are integers.

######  Theorem 3.2.

Let $I\subset\mathbb{R}$ be an interval and let $f:I\to\mathbb{R}$ be concave.
If $\mu,\lambda\in I^{t}$ are two partitions such that $\mu\succ\lambda$, then

$\sum_{i\in[t]}f(\mu_{i})\leq\sum_{i\in[t]}f(\lambda_{i}).$

###### Proof of Proposition 3.1.

To apply Theorems 3.2 and 2.1 we need to extend $q^{*}$ to a concave function.
By construction, the function $q^{*}:\mathbb{N}\to[0,1]$ is increasing and can
be written as $q^{*}(j)=\sum_{i\in[j]}D(i)$ where $D:\mathbb{N}\to[0,1]$ is a
decreasing function. Thus extending $q^{*}$ to $\mathbb{R}_{+}$ by a piecewise
linear interpolation is increasing and concave. ∎

The following observation helps to establish the property that a distribution
is greedily arranged.

######  Observation 3.3.

Let $B$ be a quasi-ball and let $i\in[d+1]$. Then, $K_{i}(B)$ is a quasi-ball.

###### Proof.

Write $B$ as $B=\\{v_{0},v_{1},\ldots,v_{i}\\}$. The choice of order on $V$
implies there is $n\geq 0$ so that $B_{n}\subseteq B\subsetneq B_{n+1}$, and
we can write $|B|=|B_{n}|+a(d-1)+c$, where $a,c$ are non-negative integers so
that $c<d-1$. Analyze the different $K_{i}(B)$’s as follows. The set
$K_{1}(B)=N(B)$ contains $B_{n+1}$ and some of the smallest elements in
$\partial B_{n+2}$. The set $K_{2}(B)$ is equal to $B$. For
$i\in\\{3,\ldots,c+2\\}$, the set $K_{i}(B)$ contains $B_{n-1}$ and the $a+1$
smallest elements in $\partial B_{n}$. For $i\in\\{c+3,\ldots,d+1\\}$, the set
$K_{i}(B)$ contains $B_{n-1}$ and the $a$ smallest elements in $\partial
B_{n}$. ∎

We are now ready to complete the proof of our main results.

###### Proof of Theorem 1.4.

Let $J\subset V$ and let $B$ be a quasi-ball of the same size. For
$i\in[d+1]$, let $k_{i}=|K_{i}(J)|$ and $m_{i}=|K_{i}(B)|$. We have

$\displaystyle q^{\prime}(J)$
$\displaystyle=\frac{1}{d+1}\sum_{i\in[d+1]}q(K_{i}(J))$ (3.1)
$\displaystyle\leq\frac{1}{d+1}\sum_{i\in[d+1]}q^{*}(k_{i})$ (3.2)
$\displaystyle\leq\frac{1}{d+1}\sum_{i\in[d+1]}q^{*}(m_{i})$ (3.3)
$\displaystyle\leq\frac{1}{d+1}\sum_{i\in[d+1]}p^{*}(m_{i})$ (3.4)
$\displaystyle=\frac{1}{d+1}\sum_{i\in[d+1]}p(K_{i}(B))$
$\displaystyle=p^{\prime}(B).$

Here, the first and last equalities follow from the definition of the lazy
random walk; (3.1) follows from the definition of $q^{*}$; (3.2) follows from
Proposition 3.1; (3.3) holds because $p$ majorizes $q$; finally, (3.4) follows
from Observation 3.3 and the assumption that $p$ is greedily arranged.

For the set $J$ that achieves $q^{\prime*}(s)$, the above implies that
${q^{\prime}}^{*}(s)\leq p^{\prime}(B)={p^{\prime}}^{*}(s)$. The fact that
$p^{\prime}$ is greedily arranged follows from Observation 3.3. ∎

###### Proof of Theorem 1.1.

Theorem 1.4 implies (1.1) and in particular $p_{t}(B_{n})\geq q_{t}(B_{n})$
for all $n,t\geq 0$. In other words, $|Y_{t}|$ stochastically dominates
$|X_{t}|$ for every $t\geq 0$. This implies that
$\mathbb{E}|Y_{t}|\geq\mathbb{E}|X_{t}|$. It remains to show that
$\liminf_{t\to\infty}t^{-1}|Y_{t}|\geq\frac{d-2}{d+1}$ almost surely. For
every $\varepsilon>0$, standard concentration bounds show that for some
constants $c,C>0$,

$\mathbb{P}\big{[}t^{-1}|X_{t}|<\tfrac{d-2}{d+1}-\varepsilon\big{]}\leq
Ce^{-ct}.$

Since $|Y_{t}|$ stochastically dominates $|X_{t}|$ for every $t\geq 0$, the
same holds with $Y_{t}$ instead of $X_{t}$. The Borel–Cantelli lemma completes
the proof. ∎

######  Remark 3.4.

Theorem 1.4, and thus also Theorems 1.1 and 1.3, extends to the lazy random
walk in which the probability to stay put is any $\gamma\geq\frac{1}{d+1}$.
The idea is that if $q^{\prime}_{\gamma}$ is the result of a lazy random walk
step applied to a distribution $q$ with lazyness $\gamma$, then for any
$\gamma>\delta$,

$q^{\prime}_{\gamma}=\big{(}\gamma-\delta\big{)}q+\big{(}1-\gamma+\delta\big{)}q^{\prime}_{\delta}.$

We apply this with $\gamma>\delta=\frac{1}{d+1}$ to get

$\displaystyle q^{\prime}_{\gamma}(J)$
$\displaystyle=\Big{(}\gamma-\frac{1}{d+1}\Big{)}q(J)+\Big{(}1-\gamma+\frac{1}{d+1}\Big{)}\frac{1}{d+1}\sum_{i\in[d+1]}q(K_{i}(J))$
$\displaystyle\leq\Big{(}\gamma-\frac{1}{d+1}\Big{)}p(B)+\Big{(}1-\gamma+\frac{1}{d+1}\Big{)}\frac{1}{d+1}\sum_{i\in[d+1]}p(K_{i}(B))=p^{\prime}(B).$

## 4 Simple random walks

In this section, we consider simple (non-lazy) walks. The argument is similar
to the lazy case, and we omit some of the details that are unchanged. For
$J\subset V$, let

$N^{\prime}(J)=\bigcup_{v\in J}N^{\prime}(v).$

The main difficulty stems from the fact that the tree is bipartite. The half-
ball $B^{\prime}_{n}$ is the set of the form

$B^{\prime}_{n}=\\{v\in B_{n}:|v|\equiv n\mod 2\\}.$

A half-quasi-ball is the intersection of a quasi-ball with either $V_{0}$ or
with $V_{1}$. Half-qausi-balls have parities. A half-greedily arranged
distribution is a distribution supported on a quasi-ball.

######  Proposition 4.1.

For every non-empty $J\subset V$,

$|N^{\prime}(J)|\geq 1+(d-1)|J|.$

###### Proof.

First assume that $J$ is contained in either $V_{0}$ or $V_{1}=V\setminus
V_{0}$. In this case, $\kappa_{1}(J)=|J|$ so that Proposition 2.2 implies that

$|N^{\prime}(J)|=|N(J)|-|J|=(d-1)|J|+\kappa_{2}(J)\geq(d-1)|J|+1.$

Second, for arbitrary $J$, we have $N^{\prime}(v)\cap N^{\prime}(w)=\emptyset$
if $|v|\neq|w|\mod 2$. The result follows by applying the above to $J\cap
V_{0}$ and $J\cap V_{1}$ separately. ∎

For $J\subset V$ and $i\in[d]$, define

$K^{\prime}_{i}(J)=\\{v\in V:|N^{\prime}(v)\cap J|\geq i\\}.$

Fix $J$ and let $B$ be a half-quasi-ball of the same size. Let
$k_{i}=|K^{\prime}_{i}(J)|$ and $m_{i}=|K^{\prime}_{i}(B)|$.

######  Proposition 4.2.

For any distribution $q$ on $V$,

$\sum_{i\in[d]}q^{*}(k_{i})\leq\sum_{i\in[d]}q^{*}(m_{i}).$

###### Proof.

As before, the proposition follows from Theorem 3.2 once we show that
$(k_{1},\ldots,k_{d})\succ(m_{1},\ldots,m_{d})$. The fact that these are
partitions is obvious, and they have the same size since
$d|J|=\sum_{i\in[d]}k_{i}=\sum_{i\in[d]}m_{i}$. It remains to establish (2.1)
for these partitions. Write

$|J|=|B|=|B^{\prime}_{n}|+a(d-1)+c,$

where $B^{\prime}_{n}\subset B\subsetneq B^{\prime}_{n+2}$, and $a,c\geq 0$
are integers so that $c\leq d-2$. The values of the $m_{i}$’s are now as
follows: $m_{1}=(d-1)|J|+1$, for $2\leq i\leq c+1$, we have
$m_{i}=|B^{\prime}_{n-2}|+a+1$, and for $c+2\leq i\leq d$, we have
$m_{i}=|B^{\prime}_{n-2}|+a$. The inequality
$\sum_{i\in[r]}k_{i}\geq\sum_{i\in[r]}m_{i}$ for $r=1$ follows from
Proposition 4.1. For $r\geq 2$, one proceeds by induction in a similar manner
as in the proof of Proposition 2.1. ∎

######  Observation 4.3.

Let $B$ be a half-quasi-ball, and $i\in[d]$. Then, $K^{\prime}_{i}(B)$ is a
half-quasi-ball of opposite parity than $B$.

###### Proof of Theorem 1.6.

Let $J\subset V$ and let $B$ be the half-quasi-ball of the same size as $J$
and with opposite parity than $p$. Let $k_{i}=|K^{\prime}_{i}(J)|$ and
$m_{i}=|K^{\prime}_{i}(B)|$. We have

$\displaystyle q^{\prime}(J)$
$\displaystyle=\frac{1}{d}\sum_{i\in[d]}q(K^{\prime}_{i}(J))$ (4.1)
$\displaystyle\leq\frac{1}{d}\sum_{i\in[d]}q^{*}(k_{i})$ (4.2)
$\displaystyle\leq\frac{1}{d}\sum_{i\in[d]}q^{*}(m_{i})$ (4.3)
$\displaystyle\leq\frac{1}{d}\sum_{i\in[d]}p^{*}(m_{i})$ (4.4)
$\displaystyle=\frac{1}{d}\sum_{i\in[d]}p(K^{\prime}_{i}(B))$
$\displaystyle=p^{\prime}(B),$

where the first and last equalities follow from the definition of the non-lazy
random walk; (4.1) follows from the definition of $q^{*}$; (4.2) follows from
Proposition 4.2; (4.3) holds because $p$ majorizes $q$; and (4.4) follows from
Observation 4.3 and the assumption that $p$ is half-greedily arranged. The
result follows in the same way as in the proof of Theorem 1.4. ∎

###### Proof of Theorem 1.5.

Denote by $p_{t}$ the distribution of $S_{t}$, and denote by $q_{t}$ the
distribution of $Z_{t}$. Since $d>2$, we have $|B_{n}|\leq
1+d(d-1)^{n}\leq|B^{\prime}_{n+1}|$. We then have

(4.5) $\displaystyle q_{t}(B_{n})$ $\displaystyle\leq q^{*}_{t}(|B_{n}|)$
(4.6) $\displaystyle\leq p^{*}_{t}(|B_{n}|)$ (4.7) $\displaystyle\leq
p^{*}_{t}(|B^{\prime}_{n+1}|)$ (4.8) $\displaystyle\leq p_{t}(B_{n+2}),$

where (4.5) holds by definition of $q_{t}^{*}$; (4.6) holds by Theorem 1.6 and
induction on $t$; (4.7) holds because $|B_{n}|\leq|B^{\prime}_{n+1}|$; and
(4.8) holds because $p_{t}$ is half-greedily arranged, and because
$B^{\prime}_{n+1}\cup B^{\prime}_{n+2}\subseteq B_{n+2}$. The rest of the
proof proceeds in a similar manner as in the proof of Theorem 1.1. ∎

## 5 Exceptional times

In this section we consider the possible slow-down of a random walk on
$\mathbb{Z}\cong\mathbb{T}_{2}$ and on $\mathbb{T}_{d}$ for $d>2$. While the
domination of Theorem 1.1 still applies, we ask here whether $(\pi_{t})$ may
be chosen so that there are exceptional times where $|Y_{t}|$ is much smaller
than $|X_{t}|$. We prove Theorem 1.7 on the existence of exceptional times of
slowing down on $\mathbb{Z}$. In contrast, we prove Theorem 1.8 on the non-
existence of such times on $T_{d}$ when $d>2$ and the permutations are
restricted to automorphisms. This section is mostly independent of the
previous parts of the paper.

### 5.1 Exceptional times for $\mathbb{Z}$

###### Proof of Theorem 1.7.

The permutations $(\pi_{t})$ are all translations of $\mathbb{Z}$.
Consequently, the permutations commute not just with each other but with the
steps of the random walk. We shall define an integer sequence $\ell_{t}$, and
define the permutations $\pi_{t}$ by
$\pi_{t}\pi_{t-1}\cdots\pi_{1}(v)=v-\ell_{t}$. Thus the process
$(Y_{t}+\ell_{t})$ has the same law as the random walk $(X_{t})$. However, the
coupling between the processes may not be such that $Y_{t}=X_{t}-\ell_{t}$,
even though that is one possible coupling.

To define $(\ell_{t})$, let $\phi(t)$ denote the integer part of
$(\frac{4}{3}t\log\log t)^{1/2}$. Let $f(t)$ be a positive integer-valued non-
decreasing function growing to infinity slower than $\phi(t)$. Let
$(b_{j})_{j=0}^{\infty}$ be defined by $b_{0}=1$ and $b_{j+1}=b_{j}+f(b_{j})$
for all $j\geq 0$. Let $(\ell_{t})$ be defined by $\ell_{b_{j}+i}$ is the
integer part of $\phi(b_{j})\cdot(\frac{4i}{f(b_{j})}-2)$ for all $j\geq 0$
and $0\leq i<f(b_{j})$. Intuitively, for each $j$, the numbers of the form
$\ell_{b_{j}+i}$ are uniformly and densely placed in the interval between
$-2\phi(b_{j})$ and $2\phi(b_{j})$.

Fix $\varepsilon>0$ and consider the set $T_{\varepsilon}$ of times $t$ at
which $X_{t}\geq(1-\varepsilon)\phi(t)$. By the law of the iterated logarithm
for the lazy random walk $(X_{t})$, we have that $T_{\varepsilon}$ is almost
surely infinite. By the same law, almost surely, the set $T^{\prime}$ of times
$t$ at which $|Y_{t}+\ell_{t}|\leq 1.5\phi(t)$ contains all but finitely many
positive integers.

Fix $t\in T_{\varepsilon}\cap T^{\prime}$ sufficiently large. Let $j\geq 0$ be
such that $b_{j}\leq t<b_{j+1}$. Since $|Y_{t}+\ell_{t}|\leq
1.5\phi(t)<2\phi(b_{j})$, there exists $0\leq i<f(b_{j})$ such that

$|(Y_{t}+\ell_{t})-\ell_{b_{j}+i}|\leq\varepsilon\phi(t).$

At time $t^{\prime}=b_{j}+i$, we have

$X_{t^{\prime}}\geq
X_{t}-|t-t^{\prime}|\geq(1-\varepsilon)\phi(t)-f(b_{j})\geq(1-\varepsilon)\phi(t)-f(t)>0,$

and

$|Y_{t^{\prime}}|=|(Y_{t^{\prime}}+\ell_{t^{\prime}})-\ell_{t^{\prime}}|\leq|(Y_{t}+\ell_{t})-\ell_{t^{\prime}}|+|t-t^{\prime}|\leq\varepsilon\phi(t)+f(t).$

Thus,

$|X_{t^{\prime}}|-|Y_{t^{\prime}}|\geq(1-2\varepsilon)\phi(t)-2f(t)\geq(1-3\varepsilon)\phi(t^{\prime}).$

We conclude that almost surely,

$\limsup_{t\to\infty}\frac{|X_{t}|-|Y_{t}|}{\phi(t)}\geq 1.$

Since $\limsup_{t\to\infty}\frac{|X_{t}|}{\phi(t)}=1$ almost surely, we have
equality above. ∎

### 5.2 No exceptional times for $d>2$

We split the proof of Theorem 1.8 into two parts for readability, and in order
to emphasize the missing piece for lifting the automorphism restriction.

######  Lemma 5.1.

For every $d>2$ and every sequence of automorphisms $(\pi_{t})$ of $T_{d}$,
there exists a coupling of the lazy random walk process $(X_{t})$ and the
permuted random walk process $(Y_{t})$ such that, almost surely,

$|Y_{t}|\geq|X_{t}|-2\log t\qquad\text{for all $t$ large enough}.$

###### Proof.

Using that $(\pi_{t})$ consists only of automorphisms, it is not hard to check
that $(\pi_{t}\pi_{t-1}\cdots\pi_{1}X_{t})$ has the same distribution as the
permuted random walk process $(Y_{t})$. Thus, setting
$Y_{t}=\pi_{t}\pi_{t-1}\cdots\pi_{1}X_{t}$ describes a coupling between
$(X_{t})$ and $(Y_{t})$.

To see that this coupling satisfies the claimed property, note that
$|X_{t}|-|Y_{t}|>k$ implies that either $|X_{t}|<k$ or
$(\pi_{t}\pi_{t-1}\cdots\pi_{1})^{-1}v_{0}\in T_{k}(X_{t})$, where $T_{k}(x)$,
defined when $|x|\geq k$, is the connected component (subtree) of $\\{v\in
V(\mathbb{T}):|v|\geq k\\}$ containing $x$. Since $X_{t}$ is uniform given its
depth $|X_{t}|$, we see that

$\mathbb{P}(|X_{t}|-|Y_{t}|>k)\leq\mathbb{P}(|X_{t}|<k)+\frac{1}{|\partial
B_{k}|},$

where $\partial B_{k}=\\{v\in V(\mathbb{T}):|v|=k\\}$ and $|\partial
B_{k}|=d(d-1)^{k-1}$. Standard concentration bounds on the speed of $(X_{t})$
now imply that $\sum_{t=1}^{\infty}\mathbb{P}(|X_{t}|-|Y_{t}|>2\log
t)<\infty$, and the Borel–Cantelli lemma completes the proof. ∎

######  Lemma 5.2.

Let $(X_{t})$ be a non-trivial nearest-neighbor random walk on $\mathbb{Z}$
(possibly biased and with any laziness). There is a coupling of $(X_{t})$ with
another copy of itself $(X^{\prime}_{t})$ such that for some constant $C>0$,
almost surely,

$X^{\prime}_{t}-X_{t}\geq\frac{\sqrt{t}}{(\log t)^{C}}\qquad\text{for all $t$
large enough}.$

######  Remark 5.3.

For positively biased random walks, $X_{t}$ and $X^{\prime}_{t}$ are
eventually positive so that the conclusion is equivalent to
$|X^{\prime}_{t}|-|X_{t}|\geq\sqrt{t}/(\log t)^{C}$. By interchanging the
roles of $(X_{t})$ and $(X^{\prime}_{t})$, the same statement is seen to hold
also for negatively biased random walks. For unbiased random walks, on the
other hand, it holds that $X^{\prime}_{t}=0$ infinitely often.

######  Remark 5.4.

The term $\sqrt{t}/(\log t)^{C}$ is not optimal, but it cannot be improved to
$c\sqrt{t}$. Indeed, in any coupling, the probability of the event
$\\{X_{t}\geq 0,X^{\prime}_{t}<c\sqrt{t}\\}$ is bounded from below, so that
Fatou’s lemma gives that $X^{\prime}_{t}-X_{t}<c\sqrt{t}$ infinitely often
with positive probability.

###### Proof.

We may always couple $(X_{t})$ and $(X^{\prime}_{t})$ so that they stay put at
the same times (and this set of times has density less than 1). It therefore
suffices to handle the non-lazy case. We thus assume that
$\mathbb{P}(X_{1}-X_{0}=1)=p$ and $\mathbb{P}(X_{1}-X_{0}=-1)=1-p$ for some
$p\in(0,1)$.

The main step is to construct a coupling between two Binomial$(n,p)$ random
variables $B_{n}$ and $B^{\prime}_{n}$ such that

$\mathbb{P}\big{(}B^{\prime}_{n}-B_{n}\geq\tfrac{\sqrt{n}}{\log^{2}n}\big{)}\geq
c^{\prime}\qquad\text{and}\qquad\mathbb{P}(B^{\prime}_{n}<B_{n})\leq\tfrac{C^{\prime}}{\log^{2}n},$

where $c^{\prime},C^{\prime}>0$ are constants that depend on $p$ but not on
$n$. Let $m$ be the integer part of $\sqrt{n}/\log^{2}n$ and consider the two
intervals

$I_{n}=[pn-\sqrt{n},pn]\cap\mathbb{N}\qquad\text{and}\qquad
J_{n}=[pn-\sqrt{n},pn-m]\cap\mathbb{N}.$

Denote $f(i)=\mathbb{P}(B_{n}=i)$ and observe that
$\frac{f(i)}{f(i-1)}=\frac{p}{1-p}\cdot\frac{n-i+1}{i}\geq 1$ whenever $i\leq
p(n+1)$. Thus, $f(i)$ is increasing for $i\in I_{n}$, and $f(i)\leq f(i+m)$
for $i\in J_{n}$. It follows that there is a coupling such that

$\displaystyle B_{n}\notin I_{n}$ $\displaystyle\implies
B^{\prime}_{n}=B_{n},$ $\displaystyle B_{n}\in J_{n}$ $\displaystyle\implies
B^{\prime}_{n}=B_{n}+m,$ $\displaystyle B_{n}\in I_{n}\setminus J_{n}$
$\displaystyle\implies B^{\prime}_{n}\in I_{n}.$

The central limit theorem implies that $\mathbb{P}(B_{n}\in J_{n})$ converges
as $n\to\infty$ to some positive constant $c=c(p)$. Since $f$ is bounded from
above by $C/\sqrt{n}$ for some constant $C=C(p)$, we have that
$\mathbb{P}(B_{n}\in I_{n}\setminus J_{n})\leq Cm/\sqrt{n}\leq C/\log^{2}n$.
This completes the construction of a coupling between $B_{n}$ and
$B^{\prime}_{n}$ with the claimed properties.

The above coupling between $B_{n}$ and $B^{\prime}_{n}$ is relevant because
$X_{t}$ has the same law as $2B_{t}-t$. Consider the times $t_{n}=2^{n}$ for
$n\geq 1$. We construct the coupling between $(X_{t})$ and $(X^{\prime}_{t})$
so that it is Markovian at these times. Fix $n\geq 1$ and suppose we have
already coupled $(X_{t})_{t\leq t_{n}}$ and $(X^{\prime}_{t})_{t\leq t_{n}}$
in some manner (the coupling for $n=1$ can be done arbitrarily). We now
describe the (conditional) coupling between the processes in the time range
$(t_{n},t_{n+1}]$. This coupling only depends on $X_{t_{n}}$ and
$X^{\prime}_{t_{n}}$. The law of $(X_{t}-X_{t_{n}})_{t_{n}\leq t\leq t_{n+1}}$
and $(X^{\prime}_{t}-X^{\prime}_{t_{n}})_{t_{n}\leq t\leq t_{n+1}}$ is
entirely independent of the past (conditioned on time $t_{n}$). These are two
random walks of length $t_{n+1}-t_{n}=2^{n}$, which we denote by
$(S_{i})_{i=0}^{2^{n}}$ and $(S^{\prime}_{i})_{i=0}^{2^{n}}$. To couple these
walks, we first couple the endpoints $S_{2^{n}}$ and $S^{\prime}_{2^{n}}$
using the above coupling between $B_{2^{n}}$ and $B^{\prime}_{2^{n}}$ (pushed
forward by the map $x\mapsto 2x-2^{n}$). Given the endpoints, we couple the
walks so that $S^{\prime}_{i}\geq S_{i}$ for all $i$ when
$S^{\prime}_{2^{n}}\geq S_{2^{n}}$, and arbitrarily otherwise. The former can
be done by first sampling $(S_{i})$ and then uniformly choosing
$\frac{1}{2}(S^{\prime}_{2^{n}}-S_{2^{n}})$ coordinates $i$ among those where
the increment $S_{i}-S_{i+1}$ is $-1$ and setting the corresponding increments
$S^{\prime}_{i}-S^{\prime}_{i-1}$ to $+1$ there (with all other increments
remaining the same for both). This completes the description of the coupling
between $(X_{t})$ and $(X^{\prime}_{t})$.

It remains to check that the constructed coupling has the claimed property.
Let $\Delta_{n}=X_{t_{n+1}}-X_{t_{n}}$ and
$\Delta^{\prime}_{n}=X^{\prime}_{t_{n+1}}-X^{\prime}_{t_{n}}$. Define events

$E_{n}=\\{\Delta^{\prime}_{n}-\Delta_{n}\geq
2^{n/2}/n^{2}\\}\qquad\text{and}\qquad
F_{n}=\\{\Delta^{\prime}_{n}<\Delta_{n}\\}.$

Since $F_{n}$ has probability at most $C^{\prime}/n^{2}$, only finitely many
of the $F_{n}$ occur almost surely. Let $N_{1}$ be the smallest positive
integer such that $F_{n}$ does not occur for any $n\geq N_{1}$. Observe that
$X^{\prime}_{t}-X_{t}$ is non-decreasing for $t\geq t_{N_{1}}$. Since
$\\{E_{n}\\}_{n=1}^{\infty}$ are independent events, each of probability at
least $c^{\prime}$, infinitely many of them occur almost surely. Moreover,
almost surely, for any $n$ large enough, at least one of
$E_{n-1},E_{n-2},\dots,E_{n-C^{\prime\prime}\log n}$ occurs, where
$C^{\prime\prime}>0$ is some large constant. Let $N_{2}$ be the smallest
positive integer so that this holds for $n\geq N_{2}$. Observe that if
$n-C^{\prime\prime}\log n\geq\max\\{N_{1},N_{2}\\}$ and $t_{n}\leq t\leq
t_{n+1}$, then letting $n-C^{\prime\prime}\log n\leq m<n$ be such that $E_{m}$
occurs, we obtain that

$\displaystyle X^{\prime}_{t}-X_{t}$ $\displaystyle\geq
X^{\prime}_{t_{m+1}}-X_{t_{m+1}}$
$\displaystyle=\Delta^{\prime}_{m}-\Delta_{m}+X^{\prime}_{t_{m}}-X_{t_{m}}$
$\displaystyle\geq 2^{m/2}/m^{2}+X^{\prime}_{t_{N}}-X_{t_{N}}$
$\displaystyle\geq\sqrt{t}\cdot e^{-5C\log\log t},$

where the last inequality holds for $t$ large enough. ∎

###### Proof of Theorem 1.8.

Let $(X^{\prime}_{t})$ denote a copy of the lazy random walk $(X_{t})$. By the
first lemma, $(X^{\prime}_{t})$ and $(Y_{t})$ can be coupled so that
$|X^{\prime}_{t}|-|Y_{t}|\leq 2\log t$ eventually. By the second lemma (and
the first remark following it), the walks $(|X_{t}|)$ and $(|X^{\prime}_{t}|)$
can be coupled so that $|X^{\prime}_{t}|-|X_{t}|\geq\sqrt{t}/\log^{C}t$
eventually. Extend this coupling to a coupling of $(X_{t})$ and
$(X^{\prime}_{t})$. The processes $(X_{t})$ and $(Y_{t})$ are now coupled so
that $|Y_{t}|-|X_{t}|\geq\sqrt{t}/\log^{C}t-2\log t\geq\sqrt{t}/\log^{2C}t$
eventually. ∎

Removing the automorphism assumption in Lemma 5.1, even at the expense of
increasing the upper bound on $|X_{t}|-|Y_{t}|$ from $2\log t$ to
$\sqrt{t}/(\log t)^{C}$ for a sufficiently large constant $C$, would suffice
in order to lift the automorphism assumption in Theorem 1.8.

### Acknowledgements

OA would like to thank the American Institute of Math, where this project was
initiated, and the Technion, where the collaboration began. OA and YS are
supported in part by NSERC. AY is partially supported by the BSF.

## References

  * [1] S. Chatterjee and P. Diaconis.  Speeding up markov chains with deterministic jumps.  Probability Theory and Related Fields, 178(3-4), 2020.
  * [2] S. Chatterjee and P. Diaconis.  Correction to: Speeding up markov chains with deterministic jumps.  Probability Theory and Related Fields, 181(1-3):377–400, 2021.
  * [3] S. Ganguly and Y. Peres.  Permuted random walk exits typically in linear time.  In 2014 Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pages 74–81. SIAM, 2014.
  * [4] S. Gouëzel.  Exponential bounds for random walks on hyperbolic spaces without moment conditions.  Tunisian Journal of Mathematics, 4(4):635–671, 2023.
  * [5] R. Lyons and Y. Peres.  Probability on trees and networks.  Cambridge University Press, 2017.
  * [6] A. W. Marshall, I. Olkin, and B. C. Arnold.  Inequalities: theory of majorization and its applications, volume 143.  Springer, 1979.
  * [7] B. Morris and Y. Peres.  Evolving sets, mixing and heat kernel bounds.  Probability Theory and Related Fields, 133(2):245–266, 2005.
  * [8] R. Pymar and P. Sousi.  A permuted random walk exits faster.  arXiv preprint arXiv:1304.6704, 2013.
  * [9] B. Virág.  Anchored expansion and random walk.  GAFA, 10(6):1588–1605, 2000.