# Ramsey upper density of infinite graphs

Ander Lamaison
Freie Universität Berlin Funded by the Deutsche Forschungsgemeinschaft (DFG,
German Research Foundation) under Germany’s Excellence Strategy - The Berlin
Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).

###### Abstract

For a fixed infinite graph $H$, we study the largest density of a
monochromatic subgraph isomorphic to $H$ that can be found in every two-
coloring of the edges of $K_{\mathbb{N}}$. This is called the Ramsey upper
density of $H$, and was introduced by Erdős and Galvin. Recently [3], the
Ramsey upper density of the infinite path was determined. Here, we find the
value of this density for all locally finite graphs $H$ up to a factor of 2,
answering a question of DeBiasio and McKenney.

We also find the exact density for a wide class of bipartite graphs, including
all locally finite forests. Our approach relates this problem to the solution
of an optimization problem for continuous functions. We show that, under
certain conditions, the density depends only on the chromatic number of $H$,
the number of components of $H$, and the expansion ratio $|N(I)|/|I|$ of the
independent sets of $H$.

##  1 Introduction

Let $K_{\mathbb{N}}$ be the complete graph on the natural numbers. Let $H$ be
a countably infinite graph (meaning that the vertex set has the same
cardinality as $\mathbb{N}$). Suppose that the edges of $K_{\mathbb{N}}$ are
colored red or blue. We can find a monochromatic subgraph $H^{\prime}\subseteq
K_{\mathbb{N}}$ isomorphic to $H$. For example, using Ramsey’s Theorem, we can
produce $H^{\prime}$ by finding a bijection between $V(H)$ and the vertices of
a monochromatic infinite clique. Out of all possible subgraphs $H^{\prime}$,
we want to find one which maximizes its density. To measure the density, we
use the following definition:

######  Definition 1.

Let $S\subseteq\mathbb{N}$. We define the upper density of $S$ (in this paper
shortened to density) as

$\bar{d}(S)=\limsup\limits_{n\rightarrow\infty}\frac{|S\cap[n]|}{n}.$

If $H^{\prime}\subseteq K_{\mathbb{N}}$, we define
$\bar{d}(H^{\prime})=\bar{d}(V(H^{\prime}))$.

We are interested in an extremal question: if $H$ is a fixed graph, what is
the maximum density of $H^{\prime}$ that we can find in every red-blue
coloring of $K_{\mathbb{N}}$? We call this value the Ramsey upper density of
$H$.

######  Definition 2.

Let $H$ be a countably infinite graph. We define its Ramsey upper density
$\rho(H)$ as the supremum of the values of $\lambda$ for which, for every two-
coloring of $E(K_{\mathbb{N}})$, there exists a monochromatic subgraph
$H^{\prime}\subseteq K_{\mathbb{N}}$, isomorphic to $H$, with
$\bar{d}(H^{\prime})\geq\lambda$.

The study of this parameter was initiated by Erdős and Galvin [6] for the
particular case $H=P_{\infty}$, the one-way infinite path. They proved that
$2/3\leq\rho(P_{\infty})\leq 8/9$. After some improvements on these bounds in
[4, 8], the exact value of $P_{\infty}$ was determined by Corsten, DeBiasio,
Lang and the author [3] as $\rho(P_{\infty})=(12+\sqrt{8})/17\approx 0.87226$.
The parameter $\rho(H)$ for general $H$ was first introduced by DeBiasio and
McKenney [4].

Our aim in this paper is to give bounds on $\rho(H)$ for a wider family of
graphs $H$. These results can be found futher down in the introduction,
although some of the more general bounds, with a more involved statement, are
left for later. As it will turn out, three parameters play an important role
in the value of $\rho(H)$: its chromatic number, the number of components and
the expansion properties of its independent sets.

###  1.1 Notation

An infinite graph is locally finite if every vertex has finite degree. The
bounds that we will show in this paper apply only to locally finite graphs
$H$.

Given $S\subseteq V(H)$, we will denote by $N(S)=\left(\cup_{v\in
S}N(v)\right)\setminus S$ the set of vertices outside $S$ with a neighbor in
$S$. We let $\mu(H,n)$ be the minimum value of $|N(I)|$, where $I$ is an
independent set in $H$ of size $n$. We say that a set $I$ is doubly
independent if both $I$ and $N(I)$ are independent.

We say that a family $\\{S_{1},S_{2},\dots\\}$ of subsets of $V(H)$ is
concentrated in at most $k$ components if there are components
$C_{1},C_{2},\dots,C_{s}$ of $H$, with $s\leq k$, such that all but finitely
many sets $S_{i}$ intersect some component $C_{j}$. We say that $V(H)$ is
concentrated in at most $k$ components if $\\{\\{v\\}:v\in V(H)\\}$ is
concentrated in at most $k$ components.

On some occasions we will use $C\in\\{R,B\\}$ to designate a color (red or
blue). When this happens, $\bar{C}$ will denote the other color. In a graph
$G$ with colored vertices, we will use $C_{G}$ to refer to the set of vertices
of color $C$. If there is no ambiguity, we will omit the subindex $G$.

If $F$ is a finite graph, we denote by $\omega\cdot F$ the graph obtained by
taking the disjoint union of a countably infinite number of copies of $F$.

Finally, we define a function $f(x)$ which will be crucial in relating the
values of $\rho(H)$ and $|N(I)|/|I|$, where $I$ is an independent or a doubly
independent set of $H$. Unfortunately, there is no satisfying intuition for
why this particular choice of $f(x)$, and not another, is behind the relation
between these two parameters. It is interesting however that the same function
$f(x)$ arises from the study of upper bounds and lower bounds for $\rho(H)$.

Since the definition of $f(x)$ is quite complicated and its comprehension is
not essential to the appreciation of our results, we encourage the reader to
skip it for now. For the reading of the introduction, knowing that such a
function exists is enough. Of course, for the reading of the proofs, the
precise definition becomes necessary.

######  Definition 3.

Let $\gamma\in(-1,1)$. For a continuous function
$g(x):[0,+\infty)\rightarrow\mathbb{R}$, define

$\Gamma^{+}_{\gamma}(g,t)=\min\\{x:\gamma x+g(x)\geq t\\}\hskip
28.45274pt\Gamma^{-}_{\gamma}(g,t)=\min\\{x:\gamma x-g(x)\geq t\\},$

where we take the minimum of the empty set to be $+\infty$. We define
$h(\gamma)$ to be the infimum, over all 1-Lipschitz111A 1-Lipschitz function
is a function satisfying $|f(x)-f(y)|\leq|x-y|$ for every $x,y$ in the domain.
functions $g$ with $g(0)=0$, of

$h(\gamma)=\inf\limits_{g}\limsup\limits_{t\rightarrow\infty}\frac{\Gamma^{+}_{\gamma}(g,t)+\Gamma^{-}_{\gamma}(g,t)}{t}.$
(1)

Define $f:(0,+\infty)\rightarrow\mathbb{R}$ as

$f(\lambda)=1-\frac{1}{\frac{2\lambda}{(1+\lambda)^{2}}h\left(\frac{\lambda-1}{\lambda+1}\right)+\frac{2\lambda}{1+\lambda}}.$

We define $f(0)=1$ and $f(+\infty)=1/2$ (by (2) below, we have
$\lim\limits_{t\rightarrow 0}f(t)=1$ and
$\lim\limits_{t\rightarrow+\infty}f(t)=1/2$.)

In Appendix B we prove some properties of $f(x)$, including the following
bounds:

$\frac{x+1}{2x+1}\leq
f(x)\leq\left\\{\begin{array}[]{ccc}\frac{2x^{2}+3x+7+2\sqrt{x+1}}{4x^{2}+4x+9}&\text{for}&0\leq
x<3,\\\ &&\\\ \frac{x+1}{2x}&\text{for}&x\geq 3.\end{array}\right.$ (2)

The upper bound is tight for $x\in[0,1]$, and we conjecture222An extended
abstract for this paper, published in Acta Math. Univ. Comenianae for EUROCOMB
2019, stated this as proved. Since then, a mistake in the proof has been
found. that it is tight everywhere. Observe that
$f(1)=(12+\sqrt{8})/17=\rho(P_{\infty})$.

Figure 1: Plot of the function $f(x)$ on the interval $[0,1]$, and the upper
and lower bounds elsewhere. The conjectured value is given in blue.

###  1.2 Results

We will now give a few bounds on $\rho(H)$, some of which apply for all
locally finite graphs and some of which apply only for particular families. In
many cases the specific results follow from other results which are more
general, but which have more involved statements. These will be stated in
later sections.

For locally finite graphs, knowing the chromatic number and the number of
components is enough to determine $\rho(H)$ up to a factor of 2.

######  Theorem 1.

Let $H$ be a locally finite graph.

  1. (i)

If $H$ has infinitely many components, then $\rho(H)\geq 1/2$.

  2. (ii)

If $H$ has finitely many components:

    1. (a)

If $H$ has infinite chromatic number, then $\rho(H)=0$.

    2. (b)

If $H$ has finite chromatic number, then

$\min\left\\{\frac{b}{2(\chi(H)-1)},\frac{1}{2}\right\\}\leq\rho(H)\leq\min\left\\{\frac{b}{\chi(H)-1},1\right\\},$

where $b$ is the number of infinite components of $H$.

This theorem answers a question in [4], which asks whether for every $\Delta$
there exists a constant $c>0$ such that every graph with maximum degree at
most $\Delta$ has Ramsey upper density at least $c$:

######  Corollary 2.

If $H$ has maximum degree at most $\Delta$, then $\rho(H)\geq 1/(2\Delta)$.

Let $P_{\infty}^{k}$ be the $k$-th power of the infinite path, that is, the
graph on $\mathbb{N}$ in which $x$ and $y$ are connected if $|x-y|\leq k$.
Elekes et al. [5] showed that, in every two-coloring of $K_{\mathbb{N}}$, the
vertex set can be partitioned into at most $2^{2k-1}$ monocromatic copies of
$P_{\infty}^{k}$ plus a finite set, and the number of copies can be reduced to
four for $P_{\infty}^{2}$. DeBiasio and McKenney [4] pointed out that this
implies $\rho(P_{\infty}^{2})\geq 1/4$ and $\rho(P_{\infty}^{k})\geq
2^{1-2k}$. Theorem 1 improves the bound for $k\geq 3$ to
$\rho(P_{\infty}^{k})\geq 1/(2k)$.

While no graph $H$ is known for which the lower bound in (ii)b is tight and
not equal to $1/2$, the upper bound is tight in the following example. Let $T$
be the tree formed by an infinite path $v_{1}v_{2}v_{3}\dots$, in which we
attach $i$ leaves to $v_{i}$ for every $i\in\mathbb{N}$. Then $\rho(b\cdot
T+K_{a})=b/(a-1)$ for every $1\leq b<a$, where $b\cdot T+K_{a}$ denotes the
disjoint union of $b$ copies of $T$ and an $a$-clique. The lower bound will
follow from Theorem 11.

Another upper bound that applies to all locally finite graphs is related to
the expansion of its independent sets:

######  Theorem 3.

Let $H$ be a locally finite graph. Then

$\rho(H)\leq
f\left(\liminf\limits_{n\rightarrow\infty}\frac{\mu(H,n)}{n}\right)$

.

There are many graphs for which the bound in Theorem 3 is tight. The following
theorem captures some of them.

######  Theorem 4.

Let $H$ be a locally finite forest, or a locally finite bipartite graph in
which every orbit of the automorphism group acting on $V(H)$ has infinite
size. Then

$\rho(H)=f\left(\liminf\limits_{n\rightarrow\infty}\frac{\mu(H,n)}{n}\right)$

.

This is a particular case of a more general condition on bipartite graphs that
is sufficient for Theorem 3 to be tight. That condition is stated later as
Theorem 12. The following corollaries illustrate some examples of graphs for
which Theorem 4 applies:

######  Corollary 5.

Let $T_{k}$ be the infinite $k$-ary tree, that is, the rooted tree in which
every vertex has $k$ children. Then $\rho(T_{k})=f(k)$.

######  Corollary 6.

Let $\mathrm{Grid}_{d}$ be the infinite $d$-dimensional grid, that is, the
graph on $\mathbb{Z}^{d}$ where two vertices are connected if they are at
Euclidean distance 1. Then
$\rho(\mathrm{Grid}_{d})=f(1)=(12+\sqrt{8})/17\approx 0.87226$.

######  Corollary 7.

Let $F$ be a finite bipartite graph. Then

$\rho(\omega\cdot F)=f\left(\min\limits_{\begin{subarray}{c}I\text{ indep. in
}F\\\ I\neq\emptyset\end{subarray}}\frac{|N(I)|}{|I|}\right).$

In particular, for every $1\leq a\leq b$ we have

$\rho(\omega\cdot
K_{a,b})=f\left(\frac{a}{b}\right)=\frac{2\left(\frac{a}{b}\right)^{2}+3\left(\frac{a}{b}\right)+7+2\sqrt{\frac{a}{b}+1}}{4\left(\frac{a}{b}\right)^{2}+4\left(\frac{a}{b}\right)+9}.$

In a finite bipartite graph $F$, there is always an independent set satisfyng
$|N(I)|\leq|I|$ (one of the two partition classes has this), so the value of
$\rho(\omega\cdot F)$ always falls on the range in which $f(x)$ is known
explicitly.

Finally, we will give two more lower bound in the particular case of infinite
factors $\omega\cdot F$. The first one is analogous to Corollary 7:

######  Theorem 8.

Let $F$ be a finite connected graph, and let $I\subseteq V(F)$ be a non-empty
doubly independent set. Then $\rho(\omega\cdot F)\geq
f\left(\frac{|N(I)|}{|I|}\right)$.

If the independent set $I\subseteq V(F)$ that minimizes $|N(I)|/|I|$ is doubly
independent, then Theorem 3 and Theorem 8 together give the exact value for
$\rho(\omega\cdot F)$. This is always true in bipartite graphs, giving another
reason why Corollary 7 holds. Figure 2 shows four non-bipartite graphs $F$ for
which this holds. If the graph $F$ does not contain any non-empty doubly
independent sets (such as $K_{3}$), the following lower bound can be used:

Figure 2: Four non-bipartite graphs $F$ for which $\rho(\omega\cdot F)$ equals
$f(1)$, $f(1)$, $f(2)$ and $f(3/2)$ respectively, with their doubly
independent sets indicated.

######  Theorem 9.

For every finite graph $F$, we have

$\rho(\omega\cdot F)\geq\frac{|V(F)|}{2|V(F)|-\alpha(F)}.$

This theorem gives the best known lower bound for $\rho(\omega\cdot K_{3})$.
Combining Theorem 9 with Theorem 3 and (2) we obtain

$3/5\leq\rho(\omega\cdot K_{3})\leq f(2)\leq\frac{21+\sqrt{12}}{33}\approx
0.74133.$

This paper is organized as follows: we prove the general upper bounds in
Section 2, and the general lower bounds in Section 3, besides a lemma that is
left for Appendix A (the bulk of this proof is a rather long series of
calculations without any interesting ideas behind). In Section 4 we discuss
the application of the general bounds to particular families of graphs, and
obtain the remaining results above. In Section 5 we state some open questions,
and in Appendix B we will prove some properties of $f(x)$.

##  2 General upper bounds

We will prove two upper bounds in this section: the first one implies the
upper bound from items (ii)a and (ii)b from Theorem 1, while the second one is
Theorem 3. In both cases we will construct a coloring of $E(K_{\mathbb{N}})$
in which no dense monochromatic copy of $H$ exists.

######  Theorem 10.

Let $H$ be a locally finite graph with chromatic number at least $a$, such
that $V(H)$ is concentrated in at most $b$ components. Then $\rho(H)\leq
b/(a-1)$.

###### Proof.

Consider the coloring of $K_{\mathbb{N}}$ in which the edge $uv$ is red iff
$a-1$ divides $v-u$. The graph formed by the blue edges has chromatic number
$a-1$, and thus does not contain $H$ as a subgraph. Every monochromatic copy
of $H$ in this coloring is red.

The red graph consists of $a-1$ cliques $C_{1},\dots,C_{a-1}$, each with
$\bar{d}(C_{i})=1/(a-1)$. The $b$ components that concentrate $V(H^{\prime})$
must be each contained in a clique $C_{i}$. Because modifying finitely many
elements does not affect the density of a set, we have
$\bar{d}(H^{\prime})\leq\bar{d}(C_{1}\cup\dots\cup C_{b})=b/(a-1)$. We
conclude that $\rho(H)\leq b/(a-1)$. ∎

Next we will prove Theorem 3. The intuition behind the construction to prove
Theorem 3 is as follows: suppose that we are trying to find a red copy of $H$.
If we have a blue clique $K$ which has fewer than $k$ vertices neighboring $K$
through some red edge, and $\mu(H,t)=k$, then we know that fewer than $t$
vertices from $K$ can be in $H^{\prime}$, because those vertices correspond to
an independent set in $H$. Our goal is to find a construction that maximizes
the number of vertices from $[n]$ that can be excluded from a potential red or
blue $H^{\prime}$ using this method.

###### Proof of Theorem 3.

Denote $\lambda=\liminf\limits_{n\rightarrow\infty}\frac{\mu(H,n)}{n}$. Let
$\epsilon>0$. Let $g$ be a 1-Lipschitz function such that the upper limit in
(1) is less than $h(\gamma)+\epsilon$, for
$\gamma=\frac{\lambda-1}{\lambda+1}$. Take an infinite set of vertices
$v_{1},v_{2},\dots$, and arrange them from left to right in this order. Color
these vertices red and blue, in such a way that among the $n$ leftmost
vertices there are exactly $\lfloor(n+g(n))/2\rfloor$ red vertices (this is
possible because $g$ is 1-Lipschitz). Form a two-colored complete graph by
giving each edge the color of its leftmost endpoint.

There must be infinitely many vertices of each color. This is because
otherwise one of the non-decreasing functions $\frac{x+g(x)}{2}$ or
$\frac{x-g(x)}{2}$ is bounded, giving an absolute upper bound on $x\pm g(x)$.
Then $\max\\{\ell^{+}_{\gamma}(g,n),\ell^{-}_{\gamma}(g,n)\\}=+\infty$ for
every $n$ large enough.

Let the red vertices be $r_{1},r_{2},r_{3},\dots$ and the blue vertices be
$b_{1},b_{2},b_{3},\dots$, according to the left-to-right order. Let
$\alpha_{i}$ be the smallest value such that $r_{\alpha_{i}}$ has at most
$\lambda(\alpha_{i}-i)$ blue vertices to its left, and $\beta_{i}$ the
smallest value such that $b_{\beta_{i}}$ has at most $\lambda(\beta_{i}-i)$
red vertices to its left. The following discussion will not only prove the
existence of $\alpha_{i}$ and $\beta_{i}$, but also give a bound on them.

Let $w=\frac{2}{1+\lambda}(\lambda i+2\lambda+2)$. Let
$z^{+}=\Gamma^{+}_{\gamma}(g,w)$ and $z^{-}=\Gamma^{-}_{\gamma}(g,w)$. By
continuity of $g$ and definition of $\Gamma^{+}_{\gamma}$ and
$\Gamma^{-}_{\gamma}$, we have

$g(z^{+})=w-\gamma z^{+},\hskip 28.45274ptg(z^{-})=\gamma z^{-}-w.$

One can check that the following identity holds by substution of $g(z^{-})$:

$\frac{z^{-}+g(z^{-})}{2}+2=\lambda\left(\frac{z^{-}-g(z^{-})}{2}-i-2\right).$

Among the $\lfloor z^{-}\rfloor$ leftmost vertices there are
$\left\lfloor\frac{\lfloor z^{-}\rfloor+g(\lfloor
z^{-}\rfloor)}{2}\right\rfloor$ red vertices and $\lfloor
z^{-}\rfloor-\left\lfloor\frac{\lfloor z^{-}\rfloor+g(\lfloor
z^{-}\rfloor)}{2}\right\rfloor$ blue vertices. Observe that

$\displaystyle\left\lfloor\frac{\lfloor z^{-}\rfloor+g(\lfloor
z^{-}\rfloor)}{2}\right\rfloor\leq$ $\displaystyle\frac{\lfloor
z^{-}\rfloor+g(\lfloor
z^{-}\rfloor)}{2}\leq\frac{z^{-}+g(z^{-})}{2}<\lambda\left(\frac{z^{-}-g(z^{-})}{2}-i-2\right)$
$\displaystyle\leq$ $\displaystyle\lambda\left(\lfloor
z^{-}\rfloor-\left\lfloor\frac{\lfloor z^{-}\rfloor+g(\lfloor
z^{-}\rfloor)}{2}\right\rfloor-i\right).$

If the last blue vertex among those $\lfloor z^{-}\rfloor$ is $b_{\tau}$, then
the number of red vertices to its left is less than $\lambda(\tau-i)$, meaning
that $\beta_{i}\leq\tau$. Hence

$\beta_{i}\leq\lfloor z^{-}\rfloor-\left\lfloor\frac{\lfloor
z^{-}\rfloor+g(\lfloor
z^{-}\rfloor)}{2}\right\rfloor\leq\frac{z^{-}-g(z^{-})}{2}+2=\frac{1-\gamma}{2}z^{-}+\frac{w}{2}+2.$

Analogously, one has the identity

$\frac{z^{+}-g(z^{+})}{2}+2=\lambda\left(\frac{z^{+}+g(z^{+})}{2}-i-2\right)$

and the inequality

$\lfloor z^{+}\rfloor-\left\lfloor\frac{\lfloor z^{+}\rfloor+g(\lfloor
z^{+}\rfloor)}{2}\right\rfloor\leq\lambda\left(\left\lfloor\frac{\lfloor
z^{+}\rfloor+g(\lfloor z^{+}\rfloor)}{2}\right\rfloor-i\right).$

Hence we find

$\alpha_{i}\leq\left\lfloor\frac{\lfloor z^{+}\rfloor+g(\lfloor
z^{+}\rfloor)}{2}\right\rfloor\leq\frac{z^{+}+g(z^{+})}{2}=\frac{1-\gamma}{2}z^{+}+\frac{w}{2}.$

Adding the two values together, for $i$ large enough we have

$\alpha_{i}+\beta_{i}\leq\frac{1-\gamma}{2}(z^{+}+z^{-})+w+2\leq\left(\frac{1-\gamma}{2}h(\gamma)+\epsilon+1\right)\frac{2\lambda}{1+\lambda}i+o(i).$

Let $\phi:\mathbb{N}\rightarrow\\{v_{1},v_{2},\dots\\}$ be an arbitrary
bijection satisfying
$\phi([\alpha_{j}+\beta_{j}])=\\{r_{1},r_{2},\dots,r_{\alpha_{j}},b_{1},b_{2},\dots,b_{\beta_{j}}\\}$
for every $j$. The function $\phi$ defines a coloring of $K_{\mathbb{N}}$,
where the color of the edge $ij$ is the color of the edge $\phi(i)\phi(j)$.

Let $R$ and $B$ be the sets of positive integers $i$ whose image $\phi(i)$ is
red or blue, respectively. Let $H^{\prime}\subseteq K_{\mathbb{N}}$ be a
monochromatic copy of $H$ in this coloring. Suppose that $H^{\prime}$ is red.
Let $n$ be a positive integer, and let $B_{n}=V(H^{\prime})\cap[n]\cap B$.
Because the vertices of $B_{n}$ form a monochromatic blue clique in our
coloring of $K_{\mathbb{N}}$, the set $B_{n}$ must be independent in
$H^{\prime}$.

Let $j$ be the minimum value such that
$\phi(B\cap[n])\subseteq\\{b_{1},b_{2},\dots,b_{\beta_{j}}\\}$. We claim first
that there are at least $(1-O(\epsilon))j$ vertices in $[n]$ which do not
belong to $H^{\prime}$. Indeed, let
$B^{\prime}_{n}=V(H^{\prime})\cap\\{b_{1},b_{2},\dots,b_{\beta_{j-1}}\\}\subseteq
B_{n}$. From the construction of the coloring, the vertices that are connected
to a vertex of $\\{b_{1},b_{2},\dots,b_{\beta_{j-1}}\\}$ through a red edge
are precisely the red vertices to the left of $b_{\beta_{j-1}}$, of which
there are at most $\lambda(\beta_{j-1}-(j-1))$. This means that
$\mu(H,|B^{\prime}_{n}|)\leq\lambda(\beta_{j-1}-(j-1))$. For $j$ large enough,
this implies $|B^{\prime}_{n}|\leq(1+o(1))(\beta_{j-1}-(j-1))$, and

$|[n]\setminus
V(H^{\prime})|\geq\beta_{j-1}-|B^{\prime}_{n}|\geq(1+o(1))(j-1)-o(1)\beta_{j-1}.$

Observe next that we cannot have $\beta_{j}=\beta_{j+1}$. This is because
$b_{\beta_{j}-1}$, which is to the left333We cannot have $\beta_{j}=1$ for
$j\geq 2$, because then $b_{1}$ would have at most $\lambda(1-j)<0$ red
vertices to its left. of $b_{\beta_{j}}$, has more than
$\lambda((\beta_{j}-1)-j)=\lambda(\beta_{j}-(j+1))$ red vertices to its left.
We thus have, by minimality of $j$, that $b_{\beta_{j+1}}\notin\phi([n])$, and
by construction of $\phi$ we have
$\phi([n])\subset\\{r_{1},r_{2},\dots,r_{\alpha_{j+1}},b_{1},b_{2},\dots,b_{\beta_{j+1}}\\}$.
This leads to the desired bound:

$\frac{|V(H^{\prime})\cap[n]|}{n}\leq 1-\frac{(1-o(1))j}{n}\leq
1-\frac{(1-o(1))j}{\alpha_{j+1}+\beta_{j+1}}\leq
1-\frac{1-o(1)}{\left(\frac{1-\gamma}{2}h(\gamma)+\epsilon+1\right)\frac{2\lambda}{1+\lambda}}$

which for $\epsilon$ small enough and $n$ large enough can take values
arbitrarily close to $f(\lambda)$.

The case in which $H^{\prime}$ is monochromatic blue is analogous. Indeed,
besides the direction of the rounding, it is equivalent to taking the function
$-g(x)$ instead of $g(x)$. ∎

##  3 General lower bounds

In this section we will prove three lower bounds. One is item (i) from Theorem
1, another is the lower bound of item (ii)b in the same theorem, and the final
one is the following, which will be used in the proof of Theorem 12 and
Theorem 8:

######  Theorem 11.

Let $H$ be a locally finite graph, $a,b,r,s$ be positive integers with $a>b$,
and $\Psi:V(H)\rightarrow[a]$ be a proper coloring. Suppose that there exist
infinitely many pairwise disjoint doubly independent sets $I_{1},I_{2},\dots$
in $H$, each contained in some component of $H$ and not concentrated in fewer
than $b$ components, such that $|I_{i}|=r$, $|N(I_{i})|\leq s$, and
$\Psi(N(I_{i}))=a$. Then

$\rho(H)\geq\frac{b}{a-1}f\left(\frac{s}{r}\right).$

###### Proof of Theorem 1(i).

Let $\chi:E(K_{\mathbb{N}})\rightarrow\\{R,B\\}$ be an edge-coloring. Let
$\mathcal{F}$ be an inclusion-maximal family of pairwise disjoint
monochromatic infinite cliques in $\chi$. Then $\mathbb{N}\setminus
V(\mathcal{F})$ is finite, because otherwise by Ramsey’s theorem there would
be an infinite monochromatic clique in $\chi$ restricted to
$\mathbb{N}\setminus V(\mathcal{F})$, contradicting the maximality of
$\mathcal{F}$. Let $\mathcal{F}_{R}$ and $\mathcal{F}_{B}$ be the families of
red and blue cliques in $\mathcal{F}$. Since $\bar{d}(V(\mathcal{F}_{R})\cup
V(\mathcal{F}_{B}))=1$, we have
$\max\\{\bar{d}(V(\mathcal{F}_{R})),\bar{d}(V(\mathcal{F}_{B}))\\}\geq 1/2$.
Wlog assume $\bar{d}(\mathcal{F}_{R}))\geq 1/2$. We can suppose that
$\mathcal{F}_{R}$ contains infinitely many cliques, because otherwise we can
take one clique $K\in\mathcal{F}_{R}$ and divide it into infinitely many
infinite cliques. Let $K_{1},K_{2},\dots$, be the cliques in
$\mathcal{F}_{R}$. We can partition the vertex set of $H$ into infinitely many
parts $S_{1},S_{2},\dots$, each of which is made up of infinitely many
components of $H$. Now take any $\Phi:V(H)\rightarrow V(K_{\mathbb{N}})$ which
is a bijection from each $S_{i}$ to each $K_{i}$. The image of $H$ is a
monochromatic graph $H^{\prime}$ and
$\bar{d}(V(H^{\prime}))=\bar{d}(\mathcal{F}_{R})\geq 1/2$.∎

The proof of Theorem 1(ii)b and Theorem 11 will both be (partially)
algorithmic: given a coloring $\chi:E(K_{\mathbb{N}})\rightarrow\\{R,B\\}$, we
will define an algorithm that constructs a dense monochromatic copy of $H$.
The algorithms will be similar, so we will first prove Theorem 11 and then
explain how to adapt the proof to Theorem 1(ii)b.

Let $H$ be as in Theorem 11, and let
$\chi:E(K_{\mathbb{N}})\rightarrow\\{R,B\\}$. Our goal is to find a copy of
$H$ in $K_{\mathbb{N}}$ with density at least $b/(a-1)f(s/r)$. In order to
find such a copy of $H$, it will be helpful to also color the vertices of
$K_{\mathbb{N}}$, in a way that encodes information about how the vertices are
connected through red or blue edges. The following coloring is a variant of
one due to Elekes et al. [5]. We denote by $N_{C}(v)$ the set of vertices
connected to $v$ through an edge of color $C$.

######  Definition 4.

Let $\chi:E(K_{\mathbb{N}})\rightarrow\\{R,B\\}$ be a coloring, and let $a$ be
a positive integer. An $a$-good coloring of $V(K_{\mathbb{N}})$ is a partition
$\mathbb{N}=\cup_{i=1}^{a}(R_{i}\cup B_{i})\cup X$ into $2a+1$ classes (some
of which might be empty), where $X$ is finite, with the following properties:

  * •

For every color $C\in\\{R,B\\}$, every $1\leq i\leq a-1$ and every nonempty
finite subet $S\subseteq C_{i}$, the set $\left(\cap_{v\in
S}N_{C}(v)\right)\cap C_{i}$ is infinite.

  * •

For every color $C\in\\{R,B\\}$, every $1\leq i\leq a-1$ and every nonempty
finite subet $S\subseteq C_{a}\cup\left(\cup_{j=i+1}^{a-1}\bar{C}_{j}\right)$,
the set $\left(\cap_{v\in S}N_{C}(v)\right)\cap C_{i}$ is infinite.

We call each class $R_{i}$ a shade of red and each class $B_{i}$ a shade of
blue. $X$ can be seen as a residual set, which can be removed without
affecting the density of the graph. The choice of $a$ is related to the
chromatic number of the monochromatic subgraphs that we can find in this
graph. Indeed, say that we want to find a red clique of size $a$ containing
$v\in R_{i}$. If $i\leq a-1$, then we can set $v=v_{1}$, and then greedily
select $v_{2},v_{3},\dots,v_{a}\in R_{i}$, each adjacent to the previous ones
through a red edge. If $i=a$, we can set $v=v_{a}$, and then greedily select
$v_{a-1},v_{a-2},\dots,v_{1}$, with $v_{j}\in B_{j}$, each adjacent to the
previous ones through a red edge.

We denote by $K_{r,s}^{C}$ a complete bipartite graph in which all edges have
color $C$, all vertices in the part of size $s$ have color $C$ and all
vertices in the part of size $r$ have color $\bar{C}$. These subgraphs will be
used to embed the sets $I_{i}\cup N(I_{i})$ in our colored graph.

The proof of Theorem 11 will have three main steps, which are captured by
these lemmas:

######  Lemma 1.

Let $\chi:E(K_{\mathbb{N}})\rightarrow\\{R,B\\}$ be a coloring, and let $a$ be
a positive integer. There exists an $a$-good coloring in which at least two of
$(R_{a}\cup B_{a-1})$, $(B_{a}\cup R_{a-1})$ and $X$ are empty.

######  Lemma 2.

Let $\chi:E(K_{\mathbb{N}})\cup V(K_{\mathbb{N}})$ be a coloring, and let
$r,s$ be positive integers. There exists a color $C$ and a subgraph
$W\subseteq K_{\mathbb{N}}$, with $\bar{d}(W)\geq f(s/r)$, in which every
component is either an isolated vertex with color $C$, or a $K_{r,s}^{C}$.
Furthermore, if $V(K_{\mathbb{N}})$ is further subdivided into finitely many
shades, then $W$ can be taken in a way that each $K_{r,s}^{C}$ only uses one
shade of each color.

######  Lemma 3.

Let $\chi:E(K_{\mathbb{N}})\rightarrow\\{R,B\\}$ be an edge-coloring, let
$a\geq a^{\prime}\geq b$ be positive integers. Let
$\mathbb{N}\rightarrow\\{R_{1},\dots,R_{a},B_{1},\dots,B_{a},X\\}$ be an
$a$-good coloring in which at most $a^{\prime}$ shades of each color are non-
empty. Let $W\subseteq K_{\mathbb{N}}$ be a subgraph in which every component
is either an isolated vertex with color $C$, or a $K_{r,s}^{C}$ which uses
only one shade of each color. Under the conditions of Theorem 11, there exists
a monochromatic $H^{\prime}\subseteq K_{\mathbb{N}}$ of color $C$,
$H^{\prime}\simeq H$, with $\bar{d}(H^{\prime})\geq b/a^{\prime}\bar{d}(W)$.

It is straightforward to combine these three lemmas to deduce Theorem 11:

###### Proof of Theorem 11.

Let $\chi:E(K_{\mathbb{N}})$ be given. Apply Lemma 1 to this edge-coloring to
obtain an $a$-good coloring with at most $a-1$ shades of each color are non-
empty. Assign the color red to the vertices in $X$. Apply Lemma 2 to obtain
$C$ and $W$. Remove from $W$ every component which uses a vertex of $X$ (this
does not affect $\bar{d}(W)$ because it only removes finitely many vertices).
By Lemma 3, we can find a monochromatic $H^{\prime}\subseteq K_{\mathbb{N}}$
with $\bar{d}(H^{\prime})\geq b/(a-1)\bar{d}(W)\geq b/(a-1)f(s/r)$.∎

###### Proof of Lemma 1.

For each vertex $v$, we will denote by $c(v)$ and $s(v)$ the color that we
assign to it, respectively. The color assigned to a vertex might change while
the algorithm is running, but the shade of each vertex is final once assigned
and it will match the color that the vertex has at that time.

At some points, the shade assigning algorithm will call the basic coloring
algorithm to color an infinite set $V=\\{v_{1},v_{2},\dots\\}$ of vertices. We
will first describe this algorithm. First, the color $c(v_{1})$ is assigned so
that $N_{c(v_{1})}(v_{1})\cap V$ is infinite. Once the colors of
$v_{1},\dots,v_{i-1}$ have been assigned, assuming that
$\left(\cap_{i=1}^{n-1}N_{c(v_{i})}(v_{i})\right)\cap V$ is infinite, the
color $c(v_{n})$ is chosen so that
$\left(\cap_{i=1}^{n}N_{c(v_{i})}(v_{i})\right)\cap V$ is infinite.

The coloring produced satisfies that
$\left(\cap_{i=1}^{n}N_{c(v_{i})}(v_{i})\right)\cap V$ is infinite for every
$n$. We say that a color $C$ is dominant in this coloring if, for every $n$,
$\left(\cap_{i=1}^{n}N_{c(v_{i})}(v_{i})\right)\cap V$ contains infinitely
many vertices $v$ with $c(v)=C$. Observe that at least one of the colors is
dominant.

Now we define the shade assigning algorithm:

  1. 1.

For every $v\in\mathbb{N}$, start with $c(v)$ and $s(v)$ unassigned.

  2. 2.

If finitely many vertices $v$ remain with $s(v)$ unassigned, assign $s(v)=X$,
and END.

  3. 3.

Let $V$ be the set of vertices without a shade. Color $V$ with the basic
coloring algorithm. Choose a color $C$ that is dominant. Let $i$ be the
minimum value such that $C_{i}$ is empty. For every $v\in V$ with $c(v)=C$,
set $s(v)=C_{i}$.

  4. 4.

If $i=a-1$, set $s(v)=\bar{C}_{a}$ for every $v\in V$ with $c(v)=\bar{C}$, and
END. If $i\neq a-1$, return to Step 2.

The algorithm runs the loop $2-4$ at most $2a-3$ times before ending. Whenever
a set $C_{i}$ with $i\leq a-1$ is defined, the color $C$ is dominant in the
corresponding coloring, meaning that in particular $\left(\cap_{v\in
S}N_{C}(v)\right)\cap C_{i}$ is infinite for every finite non-empty
$S\subseteq C_{i}$, as it is a superset of the color $C$ vertices of
$\left(\cap_{i=1}^{n}N_{c(v_{i})}(v_{i})\right)\cap V$ for $n$ large enough.
For the same reason, for any finite subset $S$ of vertices whose shade is not
assigned when $C_{i}$ is defined, we have that $\left(\cap_{v\in
S}N_{\bar{C}}(v)\right)\cap C_{i}$ is infinite. If $C_{a}$ is defined at some
point in the algorithm (namely at the end), then
$\bar{C}_{1},\bar{C}_{2},\dots,\bar{C}_{a-1},C_{a}$ are defined in this order.
This proves that the coloring that we obtained is $a$-good.

To conclude the proof of Lemma 1, simply observe that $X$ is nonempty only if
the algorithm terminates at Step 2, the set $(R_{a}\cup B_{a-1})$ is nonempty
only if the algorithm terminates at Step 4 with $C=B$ and $(B_{a}\cup
R_{a-1})$ is nonempty only if the algorithm terminates at Step 4 with $C=R$.∎

The proof of Lemma 2 divides $K_{\mathbb{N}}$ into infinitely many finite
graphs, and then combines the regularity lemma and a max flow/min cut
argument, to reduce the problem to an optimization problem equivalent to (1).
We will now state the lemmas that we will need for this:

######  Lemma 4 (Regularity Lemma [7]).

For every $\epsilon>0$ and $m_{0},\ell\geq 1$ there exists
$M=M(\epsilon,m_{0},\ell)$ such that the following holds. Let $G$ be a graph
on $n\geq M$ vertices whose edges are coloured in red and blue and let $d>0$.
Let $\\{W_{i}\\}_{i\in[\ell]}$ be a partition of $V(G)$. Then there exists a
partition $\\{V_{0},\dots,V_{m}\\}$ of $V(G)$ and a subgraph $H$ of $G$ with
vertex set $V(G)\setminus V_{0}$ such that the following holds:

  1. 1.

$m_{0}\leq m\leq M$;

  2. 2.

$\\{V_{i}\\}_{i\in[m]}$ refines $\\{W_{i}\cap V(H)\\}_{i\in[\ell]}$;

  3. 3.

$|V_{0}|\leq\epsilon n$ and $|V_{1}|=\dots=|V_{m}|\leq\lceil\epsilon n\rceil$;

  4. 4.

$\deg_{H}(v)\geq\deg_{G}(v)-(d+\epsilon)n$ for each $v\in V(G)\setminus
V_{0}$;

  5. 5.

$H[V_{i}]$ has no edges for $i\in[m]$;

  6. 6.

all pairs $(V_{i},V_{j})$ are $\epsilon$-regular and with density either 0 or
at least $d$ in each colour in $H$.

The max flow-min cut result that we will use can be seen as a weighted version
of König’s Theorem:

######  Lemma 5.

Let $G$ be a finite bipartite graph on $V=(X,Y)$, and let $r,s$ be positive
integers. There exists a unique value of $D$ for which both of these exist:

  * •

A function $h:E(G)\rightarrow\mathbb{N}\cup\\{0\\}$ such that $\sum_{e\ni
v}h(e)\leq r$ if $v\in X$, $\sum_{e\ni v}h(e)\leq s$ if $v\in Y$ and
$\sum_{e\in E(G)}h(e)=D$.

  * •

A vertex cover $Z$ of $G$ such that $r|Z\cap X|+s|Z\cap Y|=D$.

###### Proof.

Take an orientation of every edge in $G$ from $X$ to $Y$, and give it an
infinite capacity. Connect every vertex in $X$ to a source $\sigma$ through an
edge with capacity $r$, and every vertex in $y$ to a sink $\tau$ through an
edge with capacity $s$. Let $D$ be the maximum flow in this network. $D$ is
the maximum value for which a function $h$ as in the statement exists (by the
integrality theorem, there exists a maximum flow in which the flow of every
edge is an integer). $D$ is also the minimum value for which a cut
$(C_{1},C_{2})$ with $\sigma\in C_{1}$ and $\tau\in C_{2}$ exists. Observe
that $(C_{1},C_{2})$ is a cut with finite capacity iff $(C_{2}\cap
X)\cup(C_{1}\cap Y)$ is a vertex cover of $G$, in which case the capacity of
the cut is $r|C_{2}\cap X|+s|C_{1}\cap Y|$. Our lemma follows from the Ford-
Fulkerson theorem. ∎

The next lemma that we will introduce requires the definition of two
parameters, which up to a change of coordinates are equivalent to
$\Gamma^{+}_{\gamma}$ and $\Gamma^{-}_{\gamma}$.

######  Definition 5.

Let $g:[0,+\infty)\rightarrow[0,+\infty)$ be a continuous, non-decreasing
function. Let $\lambda,t$ be positive real numbers. We define the following
two parameters:

$\ell_{\lambda}^{+}(g,t)=\min\left\\{x:g(\lambda x)-x\geq t\right\\}\hskip
28.45274pt\ell_{\lambda}^{-}(g,t)=\min\left\\{x:x-\frac{g(x)}{\lambda}\geq
t\right\\},$

where we take the minimum of the empty set to be $+\infty$.

######  Lemma 6.

For $\lambda,\epsilon>0$ there exists $\gamma>0$ with the following property:
for every non-decreasing continuous function
$g:[0,+\infty)\rightarrow[0,+\infty)$ with $g(0)=0$ and every $m>0$ there
exists $t\in[\gamma m,m]$ such that

$\frac{\ell_{\lambda}^{+}(g,t)+\ell_{\lambda}^{-}(g,t)}{t}\geq\frac{f(\lambda)}{1-f(\lambda)}-\epsilon.$

The proof of Lemma 6 can be found in the Appendix. Combining Lemma 5 and Lemma
6, we can obtain the following:

######  Lemma 7.

For every $\epsilon,r,s>0$ there exists $\gamma,\eta>0$ and $N$ for which the
following hold: for every graph $G$ on $[n]$, with $n>N$ and
$\delta(G)\geq(1-\eta)n$, and for every total coloring $\chi:V(G)\cup
E(G)\rightarrow\\{R,B\\}$, there exists $t\in[\gamma n,n]$, a color $C$, and
$h:E(G)\rightarrow\mathbb{N}\cup\\{0\\}$, such that the following hold:

  * •

For every edge $e=uv$, if $g(e)>0$ then $\chi(e)=C$ and $\chi(u)\neq\chi(v)$.

  * •

$\sum\limits_{e\ni v}h(e)\leq r$ for every $v$ with $\chi(v)=C$ and
$\sum\limits_{e\ni v}h(e)\leq s$ for every $v$ with $\chi(v)=\bar{C}$.

  * •

$\frac{|C\cap[t]|}{t}+\frac{\sum_{v\in(\bar{C}\cap[t])}\sum_{e\ni
v}h(e)}{st}\geq f(s/r)-\epsilon$

###### Proof.

Let $\lambda=s/r$. For every red vertex $v$, we define its blue degree
$d_{B}(v)$ as the number of blue vertices $w$ such that $vw$ is blue. Let
$v_{1},v_{2},\dots,v_{|R|}$ be the set of red vertices, sorted from smallest
to largest blue degree, and let $d_{i}=d_{B}(v_{i})$. Define additionally
$d_{0}=0$ and $d_{k}=d_{|R|}$ for $k>|R|$. Let
$g:[0,+\infty)\rightarrow[0,+\infty)$ be the function that satisfies
$g(k)=d_{k}$ for every integer $k$ and which is linear between every pair of
consecutive integers.

From Lemma 6, we can find $\gamma_{1}$, depending only on $\lambda$ and
$\epsilon$, such that there exists
$\tau\in\left[\gamma_{1}\frac{1-f(\lambda)}{1+\frac{\lambda}{1-f(\lambda)}}n,\frac{1-f(\lambda)}{1+\frac{\lambda}{1-f(\lambda)}}n\right]$
for which
$\frac{\ell^{+}_{\lambda}(g,\tau)+\ell^{-}_{\lambda}(g,\tau)}{\tau}\geq\frac{f(\lambda)}{1-f(\lambda)}-\epsilon$.
Let $t=\left(\frac{1}{1-f(\lambda)}-\epsilon\right)\tau$. Then either
$|R\cap[t]|<\ell^{-}_{\lambda}(g,\tau)$ or
$|B\cap[t]|\leq\ell^{+}_{\lambda}(g,\tau)+\tau$. We consider both cases:

Case 1: $|R\cap[t]|<\ell^{-}(g,\tau)$. Let $R^{\prime}=R\cap[t]$. Let
$G^{\prime}$ be the graph of blue edges in $G$ between $R^{\prime}$ and $B$.
Let $h$, $Z$ and $D$ be as in Lemma 5 applied to $G^{\prime}$, with $X=B$ and
$Y=R^{\prime}$. Suppose that $D\leq s(|R^{\prime}|-\tau)$. Every vertex $v\in
R^{\prime}\setminus Z$ must have all its blue neighbors in $B\cap Z$, and so
$d_{B}(v)\leq|B\cap Z|$. Therefore

$d_{|R^{\prime}|-|Z\cap R^{\prime}|}\leq|Z\cap B|=\frac{D-s|Z\cap
R^{\prime}|}{r}\leq\frac{s}{r}(|R^{\prime}|-|Z\cap R^{\prime}|-\tau).$

Setting $x=|R^{\prime}|-|Z\cap R^{\prime}|$, this expression rearranges to
$x-\frac{g(x)}{\lambda}\leq\tau$, so by definition of $\ell^{-}_{\lambda}$
this means that $x\geq\ell^{-}_{\lambda}(g,\tau)$. But this is a
contradiction, because $x\leq|R^{\prime}|<\ell^{-}_{\lambda}(g,\tau)$. This
means that we have $D>s(|R^{\prime}|-\tau)$, and

$\frac{|B\cap[t]|}{t}+\frac{D}{st}\geq\frac{t-|R^{\prime}|}{t}+\frac{s(|R^{\prime}|-\tau)}{st}=1-\frac{\tau}{t}=1-\frac{1}{\frac{1}{1-f(\lambda)}-\epsilon}\geq
f(\lambda)-\epsilon.$

Case 2: $|B\cap[t]|\leq\ell^{+}(g,\tau)+\tau$. Let $B^{\prime}=B\cap[t]$. Let
$G^{\prime}$ be the graph of red edges between $R$ and $B^{\prime}$. Let $h$,
$Z$ and $D$ be as in Lemma 5 applied to $G^{\prime}$, with $X=R$ and
$Y=B^{\prime}$. Suppose that $D<s(|B^{\prime}|-\tau-\eta
n-\frac{1}{\lambda})$. Every edge between $R\setminus Z$ and
$B^{\prime}\setminus Z$ is blue. Every vertex $v$ has at most $\eta n$
vertices to which it is not connected, and so
$d_{B}(v)\geq|B^{\prime}\setminus Z|-\eta n$ for all444What if $R\setminus
Z=\emptyset$ (if this happens we cannot guarantee $d_{|R\cap
Z|+1}\geq|B^{\prime}\setminus Z|$)? Then $r|R|\leq D\leq s|B^{\prime}|\leq
st\leq s\frac{\tau}{1-f(\lambda)}\leq
s\frac{1-f(\lambda)}{\lambda}n\Rightarrow|R|\leq(1-f(\lambda))n\Rightarrow|B|\geq
f(\lambda)n$, and thus taking $t^{\prime}=n$, $h=0$ and $C=B$ is enough for
Lemma 7. $v\in R\setminus Z$.

$\displaystyle d_{|R\cap Z|+1}\geq$ $\displaystyle|B^{\prime}|-|B^{\prime}\cap
Z|-\eta n\geq|B^{\prime}|-\frac{D-r|R\cap Z|}{s}-\eta n$ $\displaystyle=$
$\displaystyle\frac{s|B^{\prime}|-D}{s}+\frac{1}{\lambda}|R\cap Z|-\eta
n\geq\tau+\eta n+\frac{1}{\lambda}+\frac{1}{\lambda}|R\cap Z|-\eta n$
$\displaystyle\geq$ $\displaystyle\tau+\frac{1}{\lambda}(|R\cap Z|+1).$

Setting $x=\frac{1}{\lambda}(|R\cap Z|+1)$, this expression rearranges to
$g(\lambda x)-x\geq\tau$, so by definition of $\ell^{+}_{\lambda}$ this means
that $x\geq\ell^{+}_{\lambda}(g,\tau)$. On the other hand, $x=\frac{|R\cap
Z|+1}{\lambda}\leq\frac{D}{s}+\frac{1}{\lambda}<|B^{\prime}|-\tau-\eta
n-\frac{1}{\lambda}+\frac{1}{\lambda}<|B^{\prime}|-\tau\leq\ell^{+}_{\lambda}(g,\tau)$,
which is a contradiction. This means that we have $D\geq
s(|B^{\prime}|-\tau-\eta n-\frac{1}{\lambda})$, and

$\frac{|R\cap[t]|}{t}+\frac{D}{st}\geq\frac{t-|B^{\prime}|}{t}+\frac{s(|B^{\prime}|-\tau-\eta
n-\frac{1}{\lambda})}{st}\geq
1-\frac{\tau}{t}-\frac{\eta}{\gamma}-\frac{1}{\lambda\gamma n}\geq
f(\lambda)-\epsilon$

for $\gamma=\gamma_{1}\frac{1-f(\lambda)}{1+\frac{\lambda}{1-f(\lambda)}}$,
$\eta<<\gamma\epsilon$ and $n>N>>\frac{1}{\gamma\lambda\epsilon}$.∎

To prove Lemma 2, we apply the regularity lemma to the graph and use Lemma 7.
We also use the fact that, by the Kővári-Sós-Turán theorem, every large enough
dense bipartite graph contains a large complete bipartite subgraph:

###### Proof of Lemma 2.

We first claim that, for every $\epsilon>0$, there exists $\gamma(\epsilon)>0$
and $N(\epsilon)$ such that, for every $n>N$, there exist $t\in[\gamma n,n]$,
a color $C$ and a subgraph $\mathcal{F}\subseteq K_{\mathbb{N}}$ contained in
$[n]$ in which every component is either an isolated vertex of color $C$ or a
$K_{r,s}^{C}$ using only a shade of each color, with

$\frac{|V(\mathcal{F})\cap[t]|}{t}\geq f\left(\frac{s}{r}\right)-\epsilon.$

Fix $\epsilon>0$. Let $G$ be the restriction of our coloring to
$K_{\mathbb{N}}$. Let $a$ be the total number of shades (from both colors).
Let $\rho,\delta>0$ be very small real numbers, whose value we will define
later. Take a partition of $[n]$ into $\ell=a\lceil\rho^{-1}\rceil$ parts
$\\{Z_{1},\dots,Z_{\ell}\\}$, such that each $Z_{i}$ is contained in one
shade, and $\max Z_{i}-\min Z_{i}<\rho n$. Applying Lemma 4 to $G$ with
$d=2\delta$, we find $M(\delta,\ell,\ell)$, a subgraph $H\subseteq G$ and a
partition $[n]=\\{V_{0},V_{1},\dots,V_{m}\\}$, with $\ell\leq m\leq M$, as in
the statement of Lemma 4, replacing $\epsilon$ with $\delta$.

We suppose that the labeling of the parts is such that $\min V_{1}<\min
V_{2}<\dots<\min V_{m}$. We define an auxilliary graph $H^{\prime}$ as
follows: the vertex set is $[m]$. The color of every vertex $i$ is the same as
the color of each of its vertices in $G$. Between any two vertices $ij$, we
draw an edge if the bipartite graph $V_{i}V_{j}$ is nonempty in $H$, and we
color it in the most dense color in $V_{i}V_{j}$.

Let $y=|V_{1}|=\dots=|V_{m}|$. Then $\frac{(1-\delta)n}{m}\leq
y\leq\frac{n}{m}$. The minimum degree in $H^{\prime}$ is at least
$(1-\frac{4\delta}{1-\delta})m$. Indeed, given $i$ and $v\in V_{i}$, we have
$d_{H^{\prime}}(i)\geq\frac{d_{H}(v)-\delta n}{y}\geq\frac{d_{G}(v)-4\delta
n}{y}\geq(1-\frac{4\delta}{1-\delta})m$.

Apply Lemma 7 to $H^{\prime}$, with parameters $\epsilon/2,r,s$ to obtain
$\gamma,\eta>0$, $N^{\prime}$, $\tau\in[\gamma m,m]$, a color $C$ and a
function $h:E(H^{\prime})\rightarrow\mathbb{N}$ as in the statement of Lemma
7, replacing $t$ with $\tau$. Our value of $\rho$ will be chosen so that
$\ell>N^{\prime}$, and $\delta$ will be chosen so that
$\frac{4\delta}{1-\delta}<\eta$ (note that the values of $\eta$ and $\gamma$
depend only on $\epsilon,r$ and $s$). Subdivide each $V_{i}$ with color $C$
into $r$ parts $V_{i,1},\dots,V_{i,r}$, each of size at least $\lfloor
y/r\rfloor$, and each $V_{i}$ with color $\bar{C}$ into $s$ parts
$V_{i,1},\dots,V_{i,s}$, each of size at least $\lfloor y/s\rfloor$. Construct
a matching $\mathcal{M}$ of pairs $(V_{i,k},V_{j,k^{\prime}})$, where for any
fixed values of $i$ and $j$, the number of pairs $(V_{i,k},V_{j,k^{\prime}})$
in $\mathcal{M}$ is $h(ij)$.

Within each pair $(V_{i,k},V_{j,k^{\prime}})$, where $V_{i}$ has color $C$ and
$V_{j}$ has color $\bar{C}$, find a maximum family
$\mathcal{F}_{i,k,j,k^{\prime}}$ of disjoint copies of $K_{r,s}^{C}$. If $N$
is large enough compared to $\delta^{-1}$ and $M$, and therefore $\delta y$ is
large enough, then $\min\\{|V_{i,k}\setminus
V(\mathcal{F}_{i,k,j,k^{\prime}})|,|V_{j,k^{\prime}}\setminus
V(\mathcal{F}_{i,k,j,k^{\prime}})|\\}<\delta y$. That is because otherwise the
bipartite graph between $V_{i,k}\setminus V(\mathcal{F}_{i,k,j,k^{\prime}})$
and $V_{j,k^{\prime}}\setminus V(\mathcal{F}_{i,k,j,k^{\prime}})$ would have
density at least $\delta$ in the edges of color $C$, and for $\delta y$ large
enough this implies the existence of a copy of $K_{r,s}^{C}$, which would
contradict the maximality of $\mathcal{F}_{i,k,j,k^{\prime}}$.

Let $\mathcal{F}$ be the union of all families
$\mathcal{F}_{i,k,j,k^{\prime}}$. Let $t=\min V_{\tau}$. We will now bound
$\frac{|(V(\mathcal{F})\cup C)\cap[t]|}{[t]}$. If $v\geq t+\rho n$, and $v\in
V_{i}$ with $i\neq 0$, then $\min V_{i}>\max V_{i}-\rho n\geq v-\rho n\geq
t=\min V_{\tau}$, and thus $i>\tau$. This means that
$|(\cup_{i=1}^{\tau}V_{i})\setminus[t]|\leq\rho n$, and $t\geq\tau y-\rho
n\geq\frac{(1-\delta)\tau n}{m}-\rho n$. On the other hand, if $v\leq t$ then
either $v\in V_{0}$ or $v\in V_{i}$ with $\min V_{i}\leq v\leq t=\min
V_{\tau}$, and thus $i\leq\tau$. This implies that
$t\leq\sum_{i=0}^{\tau}|V_{i}|\leq\delta n+\tau y\leq\delta n+\frac{\tau
n}{m}$.

Every $V_{i}$ with color $C$ and $i\in[\tau]$ will trivially be contained in
$(V(\mathcal{F})\cup C)\cap(\cup_{i=1}^{\tau}V_{i})$. For any $V_{i}$ with
color $\bar{C}$ and $i\in[\tau]$, there are $\sum_{e\ni i}h(e)$ parts
$V_{i,k}$ which are paired up with a different part $V_{j,k^{\prime}}$. We
either have $|V_{i,k}\setminus V(\mathcal{F})|\leq\delta y$ or
$|V_{j,k^{\prime}}\setminus V(\mathcal{F})|\leq\delta y$. In the first case,
$|V_{i,k}\cap V(\mathcal{F})|\geq\lfloor y/s\rfloor-\delta
y\geq(1/s-1/y-\delta)y$. In the second case, $|V_{j,k^{\prime}}\cap
V(\mathcal{F})|\geq\lfloor y/r\rfloor-\delta y\geq(1/r-1/y-\delta)y$. But
$\mathcal{F}$ is a family of copies of $K_{r,s}$, so $|V_{i,k}\cap
V(\mathcal{F})|=\frac{r}{s}|V_{j,k^{\prime}}\cap
V(\mathcal{F})|\geq(1/s-\lambda^{-1}(1/y+\delta))y$. In either case we have
$|V_{i,k}\cap V(\mathcal{F})|\geq(1-\sigma(1/y+\delta))y/s$, for
$\sigma=\max\\{r,s\\}$.

Putting our bounds together:

$\displaystyle\frac{|(V(\mathcal{F})\cup C_{G})\cap[t]|}{t}\geq$
$\displaystyle\frac{|(V(\mathcal{F})\cup
C_{G})\cap(\cup_{i=1}^{\tau}V_{i})|-\rho n}{t}$ $\displaystyle\geq$
$\displaystyle\frac{y|C_{H^{\prime}}\cap[\tau]|}{t}+\left(1-\sigma\left(\frac{1}{y}+\delta\right)\right)\frac{y}{s}\frac{\sum_{v\in(\bar{C}_{H^{\prime}}\cap[\tau])}\sum_{e\ni
v}h(e)}{t}-\frac{\rho n}{t}$ $\displaystyle\geq$
$\displaystyle\left(1-\sigma\left(\frac{1}{y}+\delta\right)\right)\frac{\tau
y}{t}\left(\frac{|C_{H^{\prime}}\cap[\tau]|}{\tau}+\frac{\sum_{v\in(\bar{C}_{H^{\prime}}\cap[\tau])}\sum_{e\ni
v}h(e)}{s\tau}\right)-\frac{\rho n}{t}$ $\displaystyle\geq$
$\displaystyle\left(1-\sigma\left(\frac{1}{y}+\delta\right)\right)\frac{\tau
y}{t}\left(f(\lambda)-\frac{\epsilon}{2}\right)-\frac{\rho}{\frac{\tau(1-\delta)}{m}-\rho}$
$\displaystyle\geq$
$\displaystyle\left(1-\sigma\left(\frac{1}{y}+\delta\right)\right)\frac{\tau
y}{\delta n+\tau
y}\left(f(\lambda)-\frac{\epsilon}{2}\right)-\frac{\rho}{\gamma(1-\delta)-\rho}$
$\displaystyle\geq$
$\displaystyle\left(1-\sigma\left(\frac{m}{(1-\delta)n}+\delta\right)\right)\frac{1}{1+\delta\frac{n}{my}\frac{m}{\tau}}\left(f(\lambda)-\frac{\epsilon}{2}\right)-\frac{\rho}{\gamma(1-\delta)-\rho}$
$\displaystyle\geq$
$\displaystyle\left(1-\sigma\left(\frac{M}{(1-\delta)N}+\delta\right)\right)\frac{1}{1+\frac{\delta}{(1-\delta)\gamma}}\left(f(\lambda)-\frac{\epsilon}{2}\right)-\frac{\rho}{\gamma(1-\delta)-\rho}$
$\displaystyle\geq$ $\displaystyle f(\lambda)-\epsilon$

if $\rho,\delta<<\epsilon,r,s$ and $N>>M$. To conclude the proof of our
initial claim, notice that
$t\geq\left(\frac{\tau}{m}-\rho\right)n\geq(\gamma-\rho)n\geq\gamma^{\prime}n$
for a constant $\gamma^{\prime}>0$.

We are now ready to construct $W$. Take a sequence
$f(s/r)>\epsilon_{1}>\epsilon_{2}>\dots>0$ with $\epsilon_{i}\rightarrow 0$.
Start by applying the claim with $\epsilon=\epsilon_{1}$ and
$n_{1}=N(\epsilon)$ to obtain a subgraph $\mathcal{F}_{1}$ with color $C_{1}$
with density at least $f(s/r)-\epsilon_{1}$ in $[t_{1}]$. Now proceed by
induction, and set
$n_{i}=\max\\{N(\epsilon_{i}/2),2n_{i-1}(r+s)/(\epsilon_{i}\gamma(\epsilon_{i}/2))\\}$.
Applying the claim with $\epsilon=\epsilon_{i}/2$ we find a subgraph
$\mathcal{F}_{i}^{\prime}$ with color $C_{i}$ contained in $[n_{i}]$ and with
density at least $f(s/r)-\epsilon_{i}/2$ in $[t_{i}]$, for some
$t_{i}\in[\gamma(\epsilon)n,n]$. Remove from $\mathcal{F}_{i}^{\prime}$ all
components that intersect $[n_{i-1}]$ (this represents at most $n_{i-1}(r+s)$
vertices) to obtain $\mathcal{F}_{i}$. Then $\mathcal{F}_{i}$ is disjoint from
all previous $\mathcal{F}_{j}$, and by the choice of $n_{i}$, it still has
density at least $f(s_{r})-\epsilon_{i}$ in $[t_{i}]$.

Select a color $C$ such that $C_{i}=C$ for infinitely many $i$. Let
$W=\cup_{C_{i}=C}\mathcal{F}_{i}$. Then by construction $\bar{d}(W)\geq
f(s/r)$, since the $t_{i}$ tend to infinity, and the components of $W$ are
isolated vertices of color $C$ or $K_{r,s}^{C}$. This concludes the proof of
Lemma 2. ∎

Finally, we prove Lemma 3 by defining an algorithm that constructs a
monochromatic $H^{\prime}$. This algorithm uses enough components from $W$
(mapping to them either single vertices of $H$ or sets $I_{i}\cup N(I_{i})$)
to keep a fraction of its density, and takes advantage of the properties of
the $a$-good coloring to map the remaining vertices of $H$.

###### Proof of Lemma 3.

Without loss of generality, assume that $C$ is red, let $S_{j}$ denote the
vertices in $W$ of shade $R_{j}$, plus the blue vertices contained in a copy
of $K_{r,s}^{R}$ in $W$ in which the red side has shade $R_{j}$. Removing from
$W$ the finite sets $S_{j}$ does not affect its density, so suppose that each
$S_{j}$ is either empty or infinite. We will show that there exists a set $J$,
of size $b$, such that $\bar{d}(\cup_{j\in J}S_{j})\geq
b/a^{\prime}\bar{d}(W)$.

By definition of density, there exists a sequence $n_{1}<n_{2}<\dots$ of
positive integers such that $|V(W)\cap[n_{i}]|/n_{i}\rightarrow\bar{d}(W)$.
For each $i$ there exists a subset $J_{i}\subseteq[a]$ of $b$ indices such
that

$\frac{|(\cup_{j\in
J_{i}}S_{j})\cap[n_{i}]|}{n_{i}}\geq\frac{b}{a^{\prime}}\frac{|V(W)\cap[n_{i}]|}{n_{i}}.$

For infinitely many $i$, the set $J_{i}$ is the same, which we denote $J$. By
taking an appropriate subsequence of $n_{1},n_{2},\dots$, we can suppose
without loss of generality that $J_{i}=J$ for all $i$ and that
$n_{i+1}/n_{i}\rightarrow\infty$. Let $\mathcal{F}_{j}$ is the union of
components from $W$ contained in some $S_{j}$ with $j\in J$, which contain a
vertex from $[n_{i}]$ but no vertex from $[n_{i-1}]$. Let
$\mathcal{I}=\\{I_{i},I_{2},\dots\\}$ be the family of doubly independent
sets. We can suppose that the elements in $\mathcal{I}$ are such that the sets
$I_{i}\cup N(I_{i})$ are pairwise disjoint. Indeed, because $H$ is locally
finite, each $I_{i}\cup N(I_{i})$ intersects finitely many sets $I_{j}\cup
N(I_{j})$, so we can find an infinite subfamily $\mathcal{I}^{\prime}$ by
including into it only the sets $I_{i}$ such that $I_{i}\cup N(I_{i})$ does
not intersect a set $I_{j}\cup N(I_{j})$ for some $j<i$ with
$I_{j}\in\mathcal{I^{\prime}}$. This does not change the components in which
$\mathcal{I}$ is concentrated.

Let $J^{\prime}\subseteq J$ be the set of indices in $j$ for which $S_{j}$ is
non-empty. We assign to each component $\mathcal{C}\subseteq H$ a number
$\kappa(\mathcal{C})\in J^{\prime}$, in such a way that for every $j\in
J^{\prime}$ there are infinitely many sets $I_{i}$ in components with
$\kappa(\mathcal{C})=j$. Indeed, if finitely many components intersect
$\mathcal{I}$, there are at least $b$ components that contain infinitely many
elements of $\mathcal{I}$, so give different values of $\kappa(\mathcal{C})$
to $|J^{\prime}|\leq b$ of them, whereas if there are infinitely many
components that intersect $\mathcal{I}$, we can assign each value of
$J^{\prime}$ to infinitely many of them. The purpose of $\kappa(\mathcal{C})$
will be to identify the shade of red to be used in the vertices while
embedding $\mathcal{C}$ in the red edges of $\chi$.

We will define an injective graph homomorphism $\Phi:H\rightarrow
K_{\mathbb{N}}$ which maps edges to red edges, whose image contains
$\mathcal{F}_{i}$ for infinitely many $i$. This is enough to prove Theorem 11,
because for infinitely many large enough values of $i$ we have

$\displaystyle\frac{|\Phi(V(H))\cap[n_{i}]|}{n_{i}}\geq$
$\displaystyle\frac{|V(\mathcal{F}_{i})\cap[n_{i}]|}{n_{i}}\geq\frac{b}{a^{\prime}}\frac{|V(W)\cap[n_{i}]|}{n_{i}}-\frac{(r+s)n_{i-1}}{n_{i}}$
$\displaystyle\geq$ $\displaystyle\frac{b}{a^{\prime}}\bar{d}(W)-o(1).$

We will define $\Phi$ in steps. On every step, we will define the image of
finitely many vertices of $H$. After every step, the following conditions must
hold. Let $u,v$ be two adjacent vertices in some component $\mathcal{C}$ of
$H$, such that $\Phi(v)$ is defined and $\Phi(u)$ is not. Then:

  * •

If $\kappa(\mathcal{C})\neq a$, then $\Phi(v)\in R_{\kappa(\mathcal{C})}$.

  * •

If $\kappa(\mathcal{C})=a$ and $\Psi(v)=a$, then $\Phi(v)\in R_{a}$.

  * •

If $\kappa(\mathcal{C})=a$ and $\Psi(v)\neq a$, then $\Phi(v)\in B_{\Psi(v)}$
and $\Psi(u)<\Psi(v)$.

The algorithm will consist of two operations that alternate: defining the
image of a vertex $v\in V(H)$ and adding some $\mathcal{F}_{i}$ to the image
of $\Phi$. If we identify $V(H)$ with $\mathbb{N}$, and always apply the first
operation to the least vertex $v$ with undefined $\Phi(v)$, at the end of the
algorithm $\Phi(v)$ will be defined for every vertex in $V(H)$.

Define the image of a vertex $v\in V(H)$: Suppose first that $v\in\mathcal{C}$
and $\kappa(\mathcal{C})=k\neq a$. Let $w_{1},\dots,w_{q}$ be the neighbors of
$v$ which have $\Phi(w_{i})$ defined. By our invariant, the vertices
$\Phi(w_{i})$ all have shade $R_{k}$, and therefore there are infinitely many
vertices $x$ in shade $R_{k}$ which are connected to every $\Phi(w_{i})$
through a red edge. Select one such $x$ which is not yet in the image of
$\Phi$, and set $\Phi(v)=x$.

Now suppose that $\kappa(\mathcal{C})=a$. Let $\Psi(v)=k$. For every edge $uw$
of $H$, define an orientation $\overrightarrow{uw}$ such that
$\Psi(u)<\Psi(w)$. Let $T$ be the set of vertices that can be reached from $v$
in this orientation. Because $T$ is connected, does not contain a path of
length greater than $a$, and the degree of every vertex is finite, by König’s
lemma $T$ is finite. Also, $T$ does not have an oriented cycle. Observe that,
by our invariant, if $\overrightarrow{uw}$ is an edge and $\Phi(u)$ is
defined, then $\Phi(w)$ is defined.

Now define $\Phi(w)$ for every $w\in T$ for which the image is still
undefined, in decreasing order of $\Psi(w)$. If $\Psi(w)=a$, choose an
arbitrary vertex $x\in R_{a}$ which is not yet the image of any vertex and set
$\Phi(w)=x$. If $\Psi(w)=k<a$, then for every $w^{\prime}\in N^{+}(w)$ the
image $\Phi(w^{\prime})$ is defined and in $B_{k+1}\cup\dots\cup B_{a-1}\cup
R_{a}$. By the properties of $a$-good colorings, there are infinitely many
vertices555If $N^{+}(w)$ is empty, how do we know that $B_{k}$ is infinite?
Because $\kappa(\mathcal{C})=a$, we know that $R_{a}$ is not empty. By the
properties of $a$-good colorings, every vertex $y\in R_{a}$ has infinitely
many red neighbors in $B_{k}$, and in particular $B_{k}$ is infinite. $x\in
B_{k}$ which are connected to every $\Phi(w^{\prime})$ through a red edge.
Choose one which is not yet in the image of $\Phi$, and set $\Phi(w)=x$.

Add some set $\mathcal{F}_{i}$ to the image: Select some $\mathcal{F}_{i}$
which is so far disjoint with the image of $\Phi$. For each $K_{r,s}^{R}$
component $Z\subseteq\mathcal{F}_{i}\cap S_{j}$, choose a doubly independent
set $I\subseteq V(H)$ in a component $\mathcal{C}$ with
$\kappa(\mathcal{C})=j$, such that no vertex from $I\cup N(I)$ has a defined
image. If $V(Z)=X\cup Y$ with $|X|=r$ blue and $|Y|=s$ red, then set $\Phi$ to
be bijective from $I$ to $X$, and injective from $N(I)$ to $Y$. The vertices
$v$ of $\mathcal{F}_{i}\cap S_{j}$ that remain outside of the image at this
point all have shade $R_{j}$. For each of them, choose a vertex $w$ with
$\Psi(w)=a$ in a component $\mathcal{C}$ with $\kappa(\mathcal{C})=j$ (there
are infinitely many of these vertices), whose image is not yet defined, and
set $\Phi(w)=v$. After doing this for every vertex in $\mathcal{F}_{i}\cap
S_{j}$ for every $j\in J^{\prime}$, the set $\mathcal{F}_{i}$ is contained in
the image.

After both steps are applied alternatingly infinitely many times, the image of
$\Phi$ is a monochromatic red graph $H^{\prime}\subseteq K_{\mathbb{N}}$ which
contains infinitely many sets $\mathcal{F}_{i}$, and therefore
$\bar{d}(H^{\prime})\geq b/a^{\prime}\bar{d}(W)$.∎

To prove the upper bound of Theorem 1(ii)b, we just need the following variant
of Lemma 3. The proof is then analogous to the proof of Theorem 11, except we
bypass completely the use of Lemma 2, and we only need that in the $a$-good
coloring we have $\max\\{\bar{d}(R),\bar{d}(B)\\}\geq 1/2$.

######  Lemma 8.

Let $\chi:E(K_{\mathbb{N}})\rightarrow\\{R,B\\}$ be an edge-coloring, let
$a\geq a^{\prime}\geq b$ be positive integers. Let
$\mathbb{N}\rightarrow\\{R_{1},\dots,R_{a},B_{1},\dots,B_{a},X\\}$ be an
$a$-good coloring in which at most $a^{\prime}$ shades of each color are non-
empty. Let $C\in\\{R,B\\}$. Let $H$ be a graph with chromatic number $a$ and
at least $b$ infinite components. Then there exists a monochromatic
$H^{\prime}\subseteq K_{\mathbb{N}}$ of color $C$, $H^{\prime}\simeq H$, with
$\bar{d}(H^{\prime})\geq b/a^{\prime}\bar{d}(C)$.

###### Proof.

Let $\Psi:V(H)\rightarrow[a]$ be a proper coloring, in which in every
component of $H$ the most common color is $a$. Without loss of generality
suppose that $C$ is red. As in the proof of Lemma 3, there exists $J^{\prime}$
with $|J^{\prime}|\leq b$, such that $\bar{d}(\cup_{j\in J^{\prime}}R_{j})\geq
b/a^{\prime}$, and all $R_{j}$ with $J\in J^{\prime}$ are infinite. Let
$\mathcal{F}=\cup_{j\in J^{\prime}}R_{j}$. Define a function $\kappa$ from the
components of $H$ to $J^{\prime}$ for which the pre-image of every value
contains infinitely many vertices. The algorithm now alternates between define
the image of a vertex $v\in V(H)$, as above, and add a vertex of $\mathcal{F}$
to the image. At the end of the procedure, we obtain a red
$H^{\prime}\subseteq K_{\mathbb{N}}$ isomorphic to $H$ which contains
$\mathcal{F}$, and thus has density at least $\bar{d}(\mathcal{F})\geq
b/a^{\prime}\bar{d}(R)$.

Add a vertex of $\mathcal{F}$ to the image: Let $v\in\mathcal{F}$ be a vertex
in $R_{j}$. Choose a vertex $w$ in a component $\mathcal{C}$ with
$\kappa(\mathcal{C})=j$, such that no vertex in $w\cup N(w)$ has a defined
image and with $\Psi(w)=a$, and set $\Phi(w)=v$.∎

##  4 Bounds for particular families of graphs

The goal of this section is to prove the remaining results from Section 1. We
will start stating and proving the more general result for bipartite graphs,
which implies Theorem 4.

######  Theorem 12.

Let $H$ be a locally finite bipartite graph, and let
$\lambda=\liminf_{n\rightarrow\infty}\frac{\mu(H,n)}{n}$. Suppose that for
every $\lambda^{\prime}>\lambda$ there exist infinitely many pairwise disjoint
independent sets $I_{1},I_{2},\dots$, all of the same size, with
$\frac{|N(I_{i})|}{|I_{i}|}\leq\lambda^{\prime}$. Then $\rho(H)=f(\lambda)$.

###### Proof.

The upper bound follows from Theorem 3. We will show that, for every
$\epsilon>0$, we have $\rho(H)\geq f(\lambda)-\epsilon$. Our goal is to show
that $H$ satisfies the condition of Theorem 11 for $a=2$, $b=1$, a certain
coloring $\Psi$ and some doubly independent sets $I^{\prime}_{i}$. Let
$\Psi:V(H)\rightarrow\\{1,2\\}$ be a proper coloring. Choose
$\lambda^{\prime}>\lambda$ such that $f(\lambda^{\prime})>f(\lambda)-\epsilon$
(it exists by continuity of $f$). There exist infinitely many pairwise
disjoint independent sets $I_{i}$, all with the same size, such that
$\frac{|N(I_{i})|}{|I_{i}|}\leq\lambda^{\prime}$ (by the condition from the
statement). Partition each set $I_{i}$ into non-empty sets
$I_{i,1},\dots,I_{i,k_{i}}$, where each vertex $v$ is classified according to
its color by $\Psi$ and the component it belongs to. If two vertices $v,w$
have a common neighbor, then they are in the same component and
$\Psi(u)=\Psi(v)$. For this reason,
$|N(I_{i})|=\sum_{j=1}^{k_{i}}|N(I_{i,j})|$. There exists some $\tau_{i}$ such
that

$\frac{|N(I_{i,\tau_{i}})|}{|I_{i,\tau_{i}}|}\leq\frac{\sum_{j=1}^{k_{i}}|N(I_{i,j})|}{\sum_{j=1}^{k_{i}}|I_{i,j}|}=\frac{|N(I_{i})|}{|I_{i}|}\leq\lambda^{\prime}$

Set $I^{\prime}_{i}=I_{i,\tau_{i}}$. Set $r_{i}=|I^{\prime}_{i}|$ and
$s_{i}=|N(I^{\prime}_{i})|$. There is a pair $(r,s)$ satisfying
$(r,s)=(r_{i},s_{i})$ for infinitely many values of $i$. Considering only the
values of $i$ for which this equality holds, we have our set of independent
sets. Note that, because $H$ is bipartite, $N(I^{\prime}_{i})$ is
monochromatic and thus independent, meaning that $I^{\prime}_{i}$ is doubly
independent. If $\Psi(I^{\prime}_{i})=2$ does not hold for infinitely many
$i$, replace $\Psi$ with $\bar{\Psi}=3-\Psi$. We can now apply Theorem 11 to
obtain $\rho(H)\geq f(s/r)\geq f(\lambda^{\prime})$. ∎

To deduce Theorem 4 from Theorem 12, we need to show that, in both graphs with
infinite orbits and forests, the condition in the statement of Theorem 12
holds.

###### Proof of Theorem 4.

Let $\lambda=\liminf\limits_{n\rightarrow\infty}\frac{\mu(H,n)}{n}$. Fix
$\lambda^{\prime}>\lambda$. We will show that, in both cases, there exist
infinitely many pairwise disjoint independent sets $I_{1},I_{2},\dots$, all
with the same size, with $\frac{|N(I_{i})|}{|I_{i}|}\leq\lambda^{\prime}$.

For graphs with infinite orbits: Choose $n$ such that
$\frac{\mu(H,n)}{n}<\lambda^{\prime}$. Let $I$ be an independent set of size
$n$ with $|N(I)|=\mu(H,n)$. We will show that there are infinitely many
automorphisms $\sigma_{i}\in{\rm Aut}(H)$ such that the sets $\sigma_{i}(I)$
are pairwise disjoint. Then we can take $I_{i}=\sigma_{i}(I)$ to conlude the
proof. We proceed by induction on $n$. For $n=1$, if $I=\\{v\\}$, this is
equivalent to the orbit of $v$ being infinite.

Suppose that the result is true for $n-1$. Suppose that we have already found
$\sigma_{1},\sigma_{2},\dots,\sigma_{k}$ such that the sets $\sigma_{i}(I)$
are pairwise disjoint. Let $X=\cup_{i=1}^{k}\sigma_{i}(I)$. We will construct
$\sigma_{k+1}\in{\rm Aut}(H)$ such that $\sigma_{k+1}(I)$ is disjoint from
$X$. Choose $v\in I$. By the induction hypothesis, there is an infinite family
$\\{\tau_{i}\\}_{i=1}^{\infty}\subseteq{\rm Aut}(H)$ such that the sets
$\tau_{i}(I-v)$ are pairwise disjoint. If $\tau_{i}(v)\not\in X$ for some $i$,
then we can take $\sigma_{k+1}=\tau_{i}$, and we are done. Therefore, assume
that $\tau_{i}(v)\in X$ for every $i$. By pigeonhole principle, there exists
$w$ such that $\tau_{i}(v)=w$ for infinitely many $i$. Choose $\phi\in{\rm
Aut(H)}$ such that $\phi(w)\not\in X$ (it exists because the orbit of $w$ is
infinite). The set $\phi^{-1}(X)$ intersects finitely many sets
$\tau_{i}(I-v)$, therefore there exists some $i$ with $\tau_{i}(I-v)$ disjoint
from $\phi^{-1}(X)$ and $\tau_{i}(v)=w$. Putting this together,
$\phi(\tau_{i}(I))$ is disjoint from $X$, as we wanted.

For forests: The following lemma will be used to find independent sets of
bounded size with bounded expansion within larger independent sets:

######  Lemma 9.

For every $\lambda^{\prime}>\lambda$ there exists
$M=M(\lambda,\lambda^{\prime})$ such that, for every independent set $I$ in a
forest with $|N(I)|\leq\lambda|I|$, there exists $I^{\prime}\subseteq I$ with
$|N(I^{\prime})|\leq\lambda^{\prime}|I^{\prime}|$ and $|I^{\prime}|\leq M$.

Knowing this lemma, choose
$\lambda^{\prime\prime}<\lambda^{\prime\prime\prime}\in(\lambda,\lambda^{\prime})$,
and set $M=M(\lambda^{\prime\prime\prime},\lambda^{\prime})$. Suppose that we
have already constructed pairwise disjoint independent sets
$I_{1},I_{2},\dots,I_{k}$ with $|I_{i}|\leq M$ and
$|N(I_{i})|\leq\lambda^{\prime}|I_{i}|$. We will find a new set $I_{k+1}$,
disjoint from the others. Let $S=\cup_{i=1}^{k}I_{i}$. There exists $n$ large
enough such that
$\frac{n}{n-|S|}\leq\frac{\lambda^{\prime\prime\prime}}{\lambda^{\prime\prime}}$.
By definition of $\liminf$ and $\mu(H,n)$, there exists an independent set $I$
with $|I|\geq n$ and $|N(I)|\leq\lambda^{\prime\prime}|I|$. Then

$|N(I\setminus
S)|\leq|N(I)|\leq\lambda^{\prime\prime}|I|\leq\lambda^{\prime\prime}(|I\setminus
S|+|S|)\leq\lambda^{\prime\prime\prime}|I\setminus S|$

By our claim, there exists $I_{i+1}\subseteq I\setminus S$ such that
$|I_{k+1}|\leq M$ and $|N(I_{k+1})|\leq\lambda^{\prime}|I_{k+1}|$. Once we
have constructed an infinite family of independent sets $I_{1},I_{2},\dots$,
simply take a pair $(r,s)$ which is equal to $(|I_{i}|,|N(I_{i})|)$ for
infinitely many $i$ (which is possible because this pair can only take
finitely many values), and we are done.∎

###### Proof of Lemma 9.

Let $\delta=\delta(\lambda,\lambda^{\prime})>0$ be small enough, which we will
fix later. Let $F$ be the forest with vertex set $I\cup N(I)$ and containing
only the edges between $I$ and $N(I)$ in our original graph. It is enough to
prove our result in $F$. Denote $J=N(I)$. For every component of $F$ take a
vertex of $I$ as the root.

There exists a set $S\subseteq V(F)$ with $|S|\leq\delta|V(F)|$, satisfying
that every component of $F\setminus S$ has size at most $\delta^{-1}$. Indeed,
start with $S=\emptyset$ and consider the set $U$ of vertices whose component
in $F\setminus S$ contains at least $\delta^{-1}$ vertices. The rooted forest
structure in $F$ induces a rooted forest structure in $F\setminus S$. Let
$U^{\prime}$ be the set of vertices in $V\setminus F$ which have at least
$\delta^{-1}-1$ descendants. If $U\neq\emptyset$ then
$U^{\prime}\neq\emptyset$, because the root of the largest component will be
in $U^{\prime}$. Select a minimal vertex $v$ in $U^{\prime}$, and add it to
$S$. This removes $v$ and all its descendants from $U$, and thus reduces the
size of $U$ by at least $\delta^{-1}$. After at most $\delta|V(F)|$ steps, $U$
will be empty.

Let $X$ be the union of $S$ and the parents of the vertices of $S\cap J$. This
set has $|X|\leq 2|S|\leq 2\delta|V(F)|$, and every component of $F\setminus
X$ is adjacent to at most one vertex in $X\cap J$, in which case it is the
parent of the root. As a consequence, every component of $F\setminus(X\cap I)$
contains at most one vertex from $X\cap J$.

Let $\mathcal{C}=\\{C_{1},\dots,C_{k}\\}$ be the components of
$F\setminus(X\cap I)$. Then

$\frac{\sum_{j=1}^{k}|C_{i}\cap J|}{\sum_{j=1}^{k}|C_{i}\cap
I|}=\frac{|J|}{|I|-|X\cap
I|}\leq\frac{|N(I)|}{|I|-2\delta(|I|+|N(I)|)}\leq\frac{\lambda}{1-2\delta(1+\lambda)}=:\lambda^{\prime\prime}.$

There exists some component $C_{i}$ such that $|C_{i}\cap
J|\leq\lambda^{\prime\prime}|C_{i}\cap I|$. If $C_{i}\cap I$ has size not
greater than $M:=2\delta^{-1}$, then set $I^{\prime}=C_{i}\cap I$ and we are
done, because $N(I^{\prime})\subseteq C_{i}\cap J$. Otherwise $C_{i}$ has size
greater than $2\delta^{-1}$, hence it must contain a (unique) vertex $v\in
X\cap J$. Let $C^{\prime}_{1},C^{\prime}_{2},\dots,C^{\prime}_{r}$ be the
components obtained from $C_{i}$ by removing $v$, labeled in decreasing order
of $|C^{\prime}_{j}\cap J|/|C^{\prime}_{j}\cap I|$. Consider the minimum
integer $t$ such that $\sum_{j=1}^{t}|C^{\prime}_{j}\cap I|\geq\delta^{-1}$.
Because every component in $F\setminus X$ has size at most $\delta^{-1}$, we
have $\sum_{j=1}^{t}|C^{\prime}_{j}\cap
I|\leq\sum_{j=1}^{t-1}|C^{\prime}_{j}\cap I|+\delta^{-1}\leq 2\delta^{-1}=M$.
Set $I^{\prime}=\cup_{j=1}^{t}(C^{\prime}_{i}\cap I)$. Then

$\frac{|N(I^{\prime})|}{|I^{\prime}|}=\frac{1+\sum_{j=1}^{t}|C^{\prime}_{j}\cap
J|}{\sum_{j=1}^{t}|C^{\prime}_{j}\cap
I|}\leq\delta+\frac{\sum_{j=1}^{r}|C^{\prime}_{j}\cap
J|}{\sum_{j=1}^{r}|C^{\prime}_{j}\cap I|}\leq\delta+\lambda^{\prime\prime}.$

This proves Lemma 9, for $\delta>0$ small enough such that
$\delta+\lambda^{\prime\prime}<\lambda^{\prime}$.∎

Next we will prove Corollaries 5 to 7 as direct applications of Theorem 4:

###### Proof of Corollary 5.

We will show that $\mu(T_{k},n)=kn$. For every independent set $I$ of size
$n$, the set of children of the vertices of $I$ has size $kn$ and is contained
in $N(I)$, thus $|N(I)|\geq kn$. Equality can hold, for example for
$I=\\{v_{1},\dots,v_{n}\\}$ where $v_{1}$ is the root of $T_{k}$ and $v_{i+1}$
is a grandchild of $v_{i}$. We therefore have $\mu(T_{k},n)=kn$. Since $T_{k}$
is a forest, Theorem 4 applies and $\rho(T_{k})=f(k)$.∎

###### Proof of Corollary 6.

Let $I$ be an independent set. The set $I+(0,1)$ is contained in $N(I)$, so
$|N(I)|\geq|I|$ and $\mu(\mathrm{Grid}_{d},n)\geq n$ for all $n$. On the other
hand, let $I_{k}$ be the set of vertices in $[2k]^{d}$ with odd sum of
coordinates. $I_{k}$ is an independent set of size $(2k)^{d}/2$, and $I\cup
N(I)$ is contained in $[2k+2]^{d}$. Since $I$ and $N(I)$ are disjoint,

$\frac{|N(I)|}{|I|}=\frac{|I\cup
N(I)|}{|I|}-1\leq\frac{(2k+2)^{d}}{(2k)^{d}/2}-1,$

which tends to 1 as $k\rightarrow\infty$. We have
$\liminf\limits_{n\rightarrow\infty}\frac{\mu(\mathrm{Grid_{d}},n)}{n}=1$. The
graph $\mathrm{Grid}_{d}$ is vertex-transitive, so by Theorem 4 we have
$\rho(\mathrm{Grid}_{d})=f(1)$.∎

Next we will deduce Theorem 8 from Theorem 11:

###### Proof of Theorem 8.

Let $a=|V(F)|$, and let $b=a-1$. Let $\Psi:V(F)\rightarrow[a]$ be a coloring
that assigns the value $a$ to every vertex in $N(I)$, and where the remaining
vertices in $F$ all get different values in $[a-1]$. Because $I$ is doubly
independent, this is a proper coloring. $\Psi$ extends to a coloring of
$\omega\cdot F$, by coloring all copies of $F$ equally.

Let $I_{1},I_{2},\dots$ be the sets $I$ of all copies of $F$. Each $I_{i}$ is
contained in a component of $F$, $\Psi(N(I_{i}))=a$ and the family of sets
$I_{i}$ is not concentrated in fewer than $b$ components. Thus, by Theorem 11,
setting $r=|I|$ and $s=|N(I)|$, we have $\rho(\omega\cdot F)\geq
f\left(\frac{|N(I)|}{|I|}\right)$. ∎

Finally, we will prove Theorem 9 using a result of Burr, Erdős and Spencer [2]
for the Ramsey number of $n\cdot F$:

######  Theorem 13.

Let $F_{1},F_{2}$ be two finite graphs without isolated vertices. The two-
color Ramsey number $R(n\cdot F_{1},n\cdot F_{2})$ satisfies

$R(n\cdot F_{1},n\cdot
F_{2})=(|V(F_{1})|+|V(F_{2})|-\min\\{\alpha(F_{1}),\alpha(F_{2})\\})n+O(1),$

where $\alpha(G)$ is the size of the largest independent set in $G$. In
particular, $R(n\cdot F,n\cdot F)=(2|V(F)|-\alpha(F))n+O(1)$.

###### Proof of Theorem 9.

Let $\chi:E(K_{\mathbb{N}})\rightarrow\\{R.B\\}$ be a coloring. Let
$n_{1},n_{2},\dots$ be an increasing sequence of positive integers with
$n_{i+1}/n_{i}\rightarrow\infty$. Let $k_{i}$ be the maximum value such that
$R(k_{i}\cdot F,k_{i}\cdot F)\leq n_{i+1}-n_{i}$. By Theorem 13, we have

$k_{i}=\left(\frac{1}{2|V(F)|-\alpha(F)}+o(1)\right)(n_{i+1}-n_{i})=\left(\frac{1}{2|V(F)|-\alpha(F)}+o(1)\right)n_{i+1}.$

There exist a family $\mathcal{F}_{i}$ of $k_{i}$ monochromatic disjoint
copies of $F$ with vertices in $[n_{i}+1,n_{n+1}]$, all with the same color
$C_{i}$. Choose a color $C$ which is equal to $C_{i}$ for infinitely many $i$.
Then $H^{\prime}=\cup_{C_{i}=C}\mathcal{F}_{i}$ is a copy of $\omega\cdot F$
with

$\limsup_{n\rightarrow\infty}\frac{|V(H)\cap[n]|}{n}\geq\limsup_{i:C_{i}=C}\frac{k_{i}|V(F)|}{n_{i+1}}=\frac{|V(F)|}{2|V(F)|-\alpha(F)}.\qed$

##  5 Open problems and questions

Out of all the graphs $H$ for which the value of $\rho(H)$ is not known, the
graph $\omega\cdot K_{3}$ presents an interesting challenge. A priori, the
problem does not seem all that different from that of bounding $R(n\cdot
K_{3},n\cdot K_{3})$, using the same finite-to-infinite trick that we used for
Theorem 9. However, the coloring of the complete graph that achieves the
finite bound does not extend naturally to a coloring of $K_{\mathbb{N}}$
without a dense $\omega\cdot K_{3}$. Additionally, it is hard to find
triangles using the techniques of Theorem 11, which look for structure in
bipartite graphs.

######  Problem 1.

Improve either bound in $3/5\leq\rho(\omega\cdot
K_{3})\leq(21+\sqrt{12})/33\approx 0.74133$.

As noted in the introduction, $f$ depends on the solution of a certain
optimization problem of Lipschitz functions. It would be helpful to remove
such dependency, and obtain a closed formula for $f$ (perhaps the upper bound
of (2)). In particular, if the upper bound of (2) is tight then we can observe
that the behavior of $f$ changes at the value 3, which corresponds to
$\limsup\mu(H,n)/H=3$ (the independent sets have similar expansion ratio as in
the infinite ternary graph). The cause of this is that the optimal coloring of
$K_{\mathbb{N}}$ changes.

######  Problem 2.

Find a closed formula for $f(x)$. In particular, prove or disprove that it
matches the upper bound from (2).

## References

  * [1] J. R. Burke and W. A. Webb.  Asymptotic behavior of linear recurrences.  Fibonacci Quarterly, 19(4):318–321, 1981.
  * [2] S. A. Burr, P. Erdős, and J. H. Spencer.  Ramsey theorems for multiple copies of graphs.  Transactions of the American Mathematical Society, 209, 1975.
  * [3] J. Corsten, L. DeBiasio, A. Lamaison, and R. Lang.  Upper density of monochromatic infinite paths.  Advances in Combinatorics, 2019.
  * [4] L. DeBiasio and P. McKenney.  Density of monochromatic infinite subgraphs.  Combinatorica, 39, 2019.
  * [5] M. Elekes, D. T. Soukup, L. Soukup, and Z. Szentmiklóssy.  Decompositions of edge-colored infinite complete graphs into monochromatic paths.  Discrete Mathematics, 340, 2017.
  * [6] P. Erdős and F. Galvin.  Monochromatic infinite paths.  Discrete Mathematics, 113, 1993.
  * [7] J. Komlós and M. Simonovits.  Szemerédi’s Regularity Lemma and its applications in graph theory.  In D. Miklós, V. T. Sós, and T. Szőnyi, editors, Combinatorics, Paul Erdős is Eighty, volume 2, pages 295–352. Bolyai Society Mathematical Studies, 1996.
  * [8] A. Lo, N. Sanhueza-Matamala, and G. Wang.  Density of monochromatic infinite paths.  Electronic Journal of Combinatorics, 25, 2018.

##  Appendix A Proof of Lemma 6

We will show that the parameters from Lemma 6 are essentially the same as
$\Gamma^{+}$ and $\Gamma^{-}$, except the axes are rotated by 45 degrees. Thus
we get that Lemma 6 is equivalent to the following lemma, which is just a
compacity argument away from completing the proof:

######  Lemma 10.

Let $\lambda\in(-1,1)$ and $\epsilon>0$. There exists $\gamma>0$ with the
following property. For every 1-Lipschitz function
$g:[0,+\infty)\rightarrow\mathbb{R}$ with $g(0)=0$, and every $m>0$, there
exists $t\in[\gamma m,m]$ such that

$\Gamma^{+}_{\lambda}(g,t)+\Gamma^{-}_{\lambda}(g,t)\geq(h(\lambda)-\epsilon)t=\frac{2}{1-\lambda^{2}}\left(\frac{f\left(\frac{1+\lambda}{1-\lambda}\right)}{1-f\left(\frac{1+\lambda}{1-\lambda}\right)}-\lambda\right)t-\epsilon
t.$

###### Proof of Lemma 6.

Define the function $z:[0,+\infty)\rightarrow\mathbb{R}$ as follows: for every
$x$, let $z(x)=g(y)-y$, where $y$ is the unique value such that $x=g(y)+y$.
This function is 1-Lipschitz: if $x_{1},x_{2}$ are non-negative, and
$y_{1},y_{2}$ are the corresponding values of $y$, then

$\displaystyle|z(x_{1})-z(x_{2})|$
$\displaystyle=\left|\left(g(y_{1})-g(y_{2})\right)-\left(y_{1}-y_{2}\right)\right|$
$\displaystyle\leq\left|\left(g(y_{1})-g(y_{2})\right)+\left(y_{1}-y_{2}\right)\right|$
$\displaystyle=|x_{1}-x_{2}|,$

since $y_{1}-y_{2}$ and $g(y_{1})-g(y_{2})$ do not have opposite signs.

For every $t>0$, let $y_{t}=\ell^{+}_{\lambda}(g,t)$. By continuity of $g$, we
have $g(\lambda y_{t})-y_{t}=t$. Let $x_{t}=g(\lambda y_{t})+\lambda y_{t}$.
Then

$\displaystyle z(x_{t})=$ $\displaystyle g(\lambda y_{t})-\lambda y_{t}$
$\displaystyle=$ $\displaystyle g(\lambda y_{t})-\lambda
y_{t}-\frac{2\lambda}{1+\lambda}\left(g(\lambda y_{t})-y_{t}-t\right)$
$\displaystyle=$ $\displaystyle\frac{1-\lambda}{1+\lambda}\left(g(\lambda
y_{t})+\lambda y_{t}\right)+\frac{2\lambda}{1+\lambda}t$ $\displaystyle=$
$\displaystyle\frac{1-\lambda}{1+\lambda}x_{t}+\frac{2\lambda}{1+\lambda}t,$

which rearranges to
$\frac{\lambda-1}{\lambda+1}x_{t}+z(x_{t})=\frac{2\lambda}{1+\lambda}t$. Thus,
$x_{t}\geq\Gamma^{+}_{\frac{\lambda-1}{\lambda+1}}(z,\frac{2\lambda}{1+\lambda}t)$.
On the other hand, let $y^{\prime}_{t}=\ell^{-}_{\lambda}(g,t)$. We have
$y^{\prime}_{t}-\frac{g(y^{\prime}_{t})}{\lambda}=t$. Let
$x^{\prime}_{t}=g(y^{\prime}_{t})+y^{\prime}_{t}$. Then

$\displaystyle z(x^{\prime}_{t})=$ $\displaystyle
g(y^{\prime}_{t})-y^{\prime}_{t}$ $\displaystyle=$ $\displaystyle
g(y^{\prime}_{t})-y^{\prime}_{t}+\frac{2\lambda}{1+\lambda}\left(y^{\prime}_{t}-\frac{g(y^{\prime}_{t})}{\lambda}-t\right)$
$\displaystyle=$
$\displaystyle\frac{\lambda-1}{\lambda+1}\left(g(y^{\prime}_{t})+y^{\prime}_{t}\right)-\frac{2\lambda}{1+\lambda}t$
$\displaystyle=$
$\displaystyle\frac{\lambda-1}{\lambda+1}x^{\prime}_{t}-\frac{2\lambda}{1+\lambda}t,$

which rearranges to
$\frac{\lambda-1}{\lambda+1}x^{\prime}_{t}-z(x^{\prime}_{t})=\frac{2\lambda}{1+\lambda}t$.
Thus,
$x^{\prime}_{t}\geq\Gamma^{-}_{\frac{\lambda-1}{\lambda+1}}\left(z,\frac{2\lambda}{1+\lambda}t\right)$.
By Lemma 10, for every $m$ there exists a value $t\in[\gamma m,m]$, where
$\gamma$ depends only on $\lambda$ and $\delta$, such that

$\displaystyle\left(h\left(\frac{\lambda-1}{\lambda+1}\right)-\delta\right)\frac{2\lambda}{1+\lambda}t\leq$
$\displaystyle x_{t}+x^{\prime}_{t}$ $\displaystyle=$ $\displaystyle g(\lambda
y_{t})+\lambda y_{t}+g(y^{\prime}_{t})+y^{\prime}_{t}$ $\displaystyle=$
$\displaystyle(y_{t}+t)+\lambda
y_{t}+\lambda(y^{\prime}_{t}-t)+y^{\prime}_{t}$ $\displaystyle=$
$\displaystyle(\lambda+1)(y_{t}+y^{\prime}_{t})+(1-\lambda)t.$

Rearranging this inequality, substituting $h$ and taking $\delta$ small enough
we obtain $y_{t}+y^{\prime}_{t}\geq(f(\lambda)-\epsilon)t$.∎

Finally, Lemma 10 can easily be proved by showing that the restriction
$t\in[\gamma m,m]$ is unnecessary:

###### Proof of Lemma 10.

Suppose that Lemma 10 is false. For some $\lambda\in(-1,1)$ there are
1-Lipschitz functions $g_{1},g_{2},\dots$ with $g_{i}(0)=0$ such that
$\frac{\Gamma^{+}_{\lambda}(g_{i},t)+\Gamma^{-}(g_{i},t)}{t}<h(\lambda)-\epsilon$
for every $t\in[\frac{m_{i}}{i},m_{i}]$. By scaling each fraction as
$\bar{g}_{i}(x)=\frac{\sqrt{i}}{m_{i}}g_{i}\left(\frac{m_{i}}{\sqrt{i}}x\right)$,
we can assume that $m_{i}=\sqrt{i}$ for every $i\in\mathbb{N}$.

Because the sequence $g_{i}(x)$ is bounded for every $x$, there is a
subsequence $g_{i_{1}},g_{i_{2}},\dots$ which is uniformly convergent on every
compact subset of $[0,+\infty)$, and has limit $g(x)$. This function is also
1-Lipschitz and has $g(0)=0$, so by definition there exists $t>1$ such that
$\Gamma^{+}_{\lambda}(g,t)+\Gamma^{-}_{\lambda}(g,t)\geq(h(\lambda)-\epsilon/2)t$.

Let $q=\Gamma^{+}_{\lambda}(g,t)$. Since $g$ satisfies that $\lambda x+g(x)<t$
for every $0\leq x\leq q$, we also have $\lambda x+g_{i_{j}}(x)<(1-\delta)t$
for all $x\in[0,q]$, all $\delta>0$ and all $j>J(\delta)$ large enough,
therefore $\Gamma^{+}_{\lambda}(g_{i_{j}},(1-\delta)t)>q$. For the same
reason,
$\Gamma^{+}_{\lambda}(g_{i_{j}},(1-\epsilon/4)t)>\Gamma^{-}_{\lambda}(g_{i_{j}},(1-\delta)t)>\Gamma^{-}_{\lambda}(g,t)$.
We obtain the inequality

$\frac{\Gamma^{+}_{\lambda}(g_{i_{j}},(1-\delta)t)+\Gamma^{-}_{\lambda}(g_{i_{j}},(1-\delta)t)}{(1-\delta)t}>\frac{\Gamma^{+}_{\lambda}(g,t)+\Gamma^{-}_{\lambda}(g,t)}{(1-\delta)t}\geq\frac{h(\lambda)-\epsilon/2}{1-\delta}>h(\lambda)-\epsilon$

for $\delta$ small enough. To reach a contradiction, simply observe that
$(1-\delta)t\in\left[\frac{1}{\sqrt{i_{j}}},\sqrt{i_{j}}\right]=\left[\frac{m_{i_{j}}}{i_{j}},m_{i_{j}}\right]$
for all $j$ large enough.∎

##  Appendix B Properties of $f(\lambda)$

We will prove four propositions regarding $f(x)$. Propositions 2 and 4
together imply (2), while Proposition 3 means that the upper bound is tight
for $x\in[0,1]$.

######  Proposition 1.

$f$ is non-increasing and continuous.

###### Proof.

Let $-1<\gamma<\tau<1$. Let $\epsilon>0$. Choose $g$ such that
$\limsup\frac{\Gamma^{+}_{\gamma}(g,t)+\Gamma^{-}_{\gamma}(g,t)}{t}\leq
h(\gamma)+\epsilon$. Let $z(t)=\Gamma^{+}_{\gamma}(g,t)$ and
$\bar{z}(t)=\Gamma^{+}_{\tau}(g,t)$. We have $\gamma
z(t)+g(z(t))=t=\tau\bar{z}(t)+g(\bar{z}(t))$. Because $\tau
z(t)+g(z(t))>\gamma z(t)+g(z(t))=t$, by definition of $\Gamma^{+}_{\tau}$ we
have $\bar{z}(t)\leq z(t)$. Thus

$z(t)-\bar{z}(t)\geq g(z(t))-g(\bar{z}(t))=\tau\bar{z}(t)-\gamma z(t)$

which rearranges to $(\tau+1)\bar{z}(t)\leq(\gamma+1)z(t)$. Similarly, if
$z^{\prime}(t)=\Gamma^{-}_{\gamma}(g,t)$ and
$\bar{z}^{\prime}(t)=\Gamma^{-}_{\tau}(g,t)$, then
$(\tau+1)z^{\prime}(t)\leq(\gamma+1)z^{\prime}(t)$. We take upper limits.

$\displaystyle(\tau+1)h(\tau)\leq$
$\displaystyle(\tau+1)\limsup\limits_{t\rightarrow\infty}\frac{\bar{z}(t)+\bar{z}^{\prime}(t)}{t}$
$\displaystyle\leq$
$\displaystyle(\gamma+1)\limsup\limits_{t\rightarrow\infty}\frac{z(t)+z^{\prime}(t)}{t}$
$\displaystyle\leq$ $\displaystyle(\gamma+1)h(\gamma)+\epsilon$

Since this inequality is valid for every $\epsilon>0$, we find that the
function $(\gamma+1)h(\gamma)$ is non-increasing on $\gamma$. On the other
hand, we have $t=\gamma z(t)+g(z(t))\leq(\gamma+1)z(t)$, or equivalently
$z(t)\geq\frac{t}{\gamma+1}$. Similarly $z^{\prime}(t)\geq\frac{t}{\gamma+1}$.
This leads to $h(\gamma)\geq\frac{2}{\gamma+1}$. We conclude that the function
$\frac{1-\gamma^{2}}{2}h(\gamma)+(\gamma+1)$ is non-increasing, because

$\displaystyle\frac{1-\tau}{2}(\tau+1)h(\tau)+(\tau+1)\leq$
$\displaystyle\frac{1-\tau}{2}(\gamma+1)h(\gamma)+(\tau+1)$
$\displaystyle\leq$
$\displaystyle\frac{1-\tau}{2}(\gamma+1)h(\gamma)+(\tau+1)-\left(\frac{(\gamma+1)h(\gamma)}{2}-1\right)(\tau-\gamma)$
$\displaystyle=$
$\displaystyle\frac{1-\gamma}{2}(\gamma+1)h(\gamma)+(\gamma+1).$

After the change of variables, $\gamma=\frac{\lambda-1}{\lambda+1}$, this is
equivalent to $f(\lambda)$ being non-decreasing.

To show that $f$ is continuous, we will show that $h$ is continuous. We will
show that, for every $-1<\gamma<1$ and every $\epsilon>0$ there exists
$\delta>0$ such that $h(\gamma-\delta)-h(\gamma)>\epsilon$. Because $h$ is
non-increasing, this implies continuity.

Choose $\xi>0$ very small, and choose $g$ such that
$\frac{\Gamma^{+}_{\gamma}(g,t)+\Gamma^{-}_{\gamma}(g,t)}{t}\leq
h(\gamma)+\xi$ for $t$ large enough. Let $z(t)=\Gamma^{+}_{\gamma}(g,t)$. We
have $\gamma z(t)+g(z(t))=t$. If $t$ is large enough, then
$(\gamma-\delta)z(t)+g(z(t))\geq t-\delta z(t)\geq(1-h(\gamma)+\xi)t$. If
$\bar{z}(t)=\Gamma^{+}_{\gamma-\delta}(g,t)$, then for $t$ large enough we
have $\bar{z}(t)\leq z\left(\frac{t}{1-(h(\gamma)+\xi)\delta}\right)$. As
before, the same argument works for $\Gamma^{-}$, and produces (taking
$\xi\rightarrow 0$)

$h(\gamma-\delta)\leq\frac{h(\gamma)}{1-\delta h(\gamma)},$

which is smaller than $h(\gamma)+\epsilon$ for $\delta$ small enough.∎

######  Proposition 2.

$f(\lambda)\leq\left\\{\begin{array}[]{ccc}\frac{2\lambda^{2}+3\lambda+7+2\sqrt{\lambda+1}}{4\lambda^{2}+4\lambda+9}&\text{for}&0\leq\lambda<3,\\\
&&\\\ \frac{\lambda+1}{2\lambda}&\text{for}&x\geq 3.\end{array}\right.$

###### Proof.

Let $\gamma=\frac{\lambda-1}{\lambda+1}$. All we need to do is find a function
$g(x)$ for which

$\limsup_{t\rightarrow\infty}\frac{\Gamma^{+}_{\gamma}(g,t)+\Gamma^{-}_{\gamma}(g,t)}{t}\leq\left\\{\begin{array}[]{ccc}\frac{2\gamma^{2}+2\gamma+8+\sqrt{32(1-\gamma)}}{(\gamma+1)^{3}}&\text{for}&\gamma\in\left(-1,\frac{1}{2}\right)\\\
&&\\\
\frac{2}{\gamma}&\text{for}&\gamma\in\left[\frac{1}{2},1\right),\end{array}\right.$

to show an upper bound on $h(\gamma)$, and consequently on $f(\lambda)$.

For $\gamma\in[\frac{1}{2},1)$, take $g(x)=0$. Then
$\Gamma^{+}_{\gamma}(g,t)=\Gamma^{-}_{\gamma}(g,t)=\frac{t}{\gamma}$.

For $\gamma\in(-1,\frac{1}{2})$, let
$\sigma=\frac{1-\gamma+\sqrt{2(1-\gamma)}}{1+\gamma}$. We define $g$ as
follows: for every $x>0$, we have
$|g(x)|=\min\\{|x-\sigma^{i}|:i\in\mathbb{Z}\\}$. $g(x)$ is non-negative if
$x\in[\sigma^{i},\sigma^{i+1})$ for some odd $i$ and non-positive otherwise.
This creates a 1-Lipschitz function in which the derivative is always $\pm 1$,
and changes sign precisely at the values
$x=\frac{\sigma^{i}+\sigma^{i+1}}{2}$.

This function $g$ satisfies that $\Gamma^{+}_{\gamma}(g,t)$ and
$\Gamma^{-}_{\gamma}(g,t)$ are piecewise linear, with sudden increases at the
points at which the respective functions take value
$\frac{\sigma^{i}+\sigma^{i+1}}{2}$. By symmetry, it is at these points that
$\frac{\Gamma^{+}_{\gamma}+\Gamma^{-}_{\gamma}}{2}$ is maximized, and one can
check that the value is

$\lim\limits_{t\rightarrow(t^{*})^{+}}\frac{\Gamma^{+}_{\gamma}(g,t)+\Gamma^{-}_{\gamma}(g,t)}{t}=\frac{2(\gamma(\sigma+1)+\sigma^{2}+2\sigma-1)}{(\gamma+1)((\gamma+1)\sigma+\gamma-1)}=\frac{2\gamma^{2}+2\gamma+8+\sqrt{32(1-\gamma)}}{(\gamma+1)^{3}},$

where
$t^{*}=\gamma\frac{\sigma^{i}+\sigma^{i+1}}{2}+\frac{\sigma^{i+1}-\sigma^{i}}{2}$.∎

######  Proposition 3.

$f(\lambda)=\frac{2\lambda^{2}+3\lambda+7+2\sqrt{\lambda+1}}{4\lambda^{2}+4\lambda+9}\hskip
28.45274pt\forall 0\leq\lambda\leq 1$

###### Proof.

Let $\gamma=\frac{\lambda-1}{\lambda+1}$. If two 1-Lipschitz functions with
$g_{1}(0)=g_{2}(0)=0$ satisfy $|g_{1}(x)-g_{2}(x)|\leq 1$ for every $x$, then
$\Gamma^{+}_{\gamma}(g_{1},t)=\min\\{x:\gamma x+g_{1}(x)\geq
t\\}\geq\min\\{x:\gamma x+g_{2}(x)\geq t-1\\}=\Gamma^{+}_{\gamma}(g_{2},t-1)$.
Similarly, $\Gamma^{-}_{\gamma}(g_{1},t)\geq\Gamma^{-}_{\gamma}(g_{2},t-1)$.
This implies that

$\limsup_{t\rightarrow\infty}\frac{\Gamma^{+}_{\gamma}(g_{1},t)+\Gamma^{-}_{\gamma}(g_{2},t)}{t}=\limsup_{t\rightarrow\infty}\frac{\Gamma^{+}_{\gamma}(g_{1},t)+\Gamma^{-}_{\gamma}(g_{2},t)}{t}$

For this reason, we can focus our attention on continuous functions $g$ which
are piecewise linear, the slope of each piece is 1 or -1 and the length of
each piece is at least $\frac{1}{2}$. Indeed, let $g_{1}$ be a 1-Lipschitz
function with $g_{1}(0)=0$. Define $g_{2}$ by starting at $g_{2}(0)=0$. Take
$g_{2}(x)$ in $[0,x_{1}]$, where $x_{1}$ is the minimum value for which
$g_{1}(x_{1})=x_{1}-1$. Then continue with slope -1 in the interval
$[x_{1},x_{2}]$ until the minimum value of $x_{2}$ for which we would have
$g_{2}(x_{2})=g_{1}(x_{2})-1$. Proceed alternating the sign of the slope every
time $g_{2}$ reaches distance 1 from $g_{1}$. Clearly we always have
$|g_{1}(x)-g_{2}(x)|\leq 1$, and it is easy to check that each piece has
length at least $\frac{1}{2}$ (it could be that some piece has infinite
length).

We can further suppose that the first piece has slope 1. Let
$\ell_{1},\ell_{2},\dots$ be the length of the pieces, and $x_{i}$ be the end
of the $i$-th piece. The points $x_{i}$ are local maxima if $i$ is odd and
minima if $i$ is even. If for some odd $i$ we have $\gamma
x_{i}+g(x_{i})\leq\gamma x_{i-2}+g(x_{i-2})$ (which means that $x_{i}$ does
not equal $\Gamma^{+}_{\gamma}(g,t)$ for any $t$), we can “remove the peak” by
extending the intervals $[x_{i-2},x_{i-1}]$ and $[x_{i+1},x_{i+2}]$ until they
intersect. The new function $\bar{g}$ satisfies
$\Gamma^{+}_{\gamma}(\bar{g},t)\leq\Gamma^{+}_{\gamma}(g,t)$ and
$\Gamma^{-}_{\gamma}(\bar{g},t)=\Gamma^{-}_{\gamma}(g,t)$, because
$\Gamma^{+}_{\gamma}(g,t)$ will always lie on an increasing piece and
$\Gamma^{-}_{\gamma}(g,t)$ lies on a decreasing piece.

We can similarly “remove a valley”, if for some even $i$ the value $x_{i}$
does not equal $\Gamma^{-}_{\gamma}(g,t)$ for any $t$. Applying these two
procedures repeatedly, always to the first peak or valley that can be removed,
we produce a function in which every $x_{i}$ is either
$\Gamma^{+}_{\gamma}(g,t_{i})$ for odd $i$ or $\Gamma^{-}_{\gamma}(g,t_{i})$
for even $i$. The function must still have infinitely many peaks and valleys,
otherwise we have $\Gamma^{+}_{\gamma}(g,t)=\infty$ or
$\Gamma^{-}_{\gamma}(g,t)=\infty$ for large enough $t$.

Let
$\mu>\limsup_{t\rightarrow\infty}\frac{\Gamma^{+}_{\gamma}(g,t)+\Gamma^{-}_{\gamma}(g,t)}{t}$.
After scaling, we can suppose that
$\frac{\Gamma^{+}_{\gamma}(g,t)+\Gamma^{-}_{\gamma}(g,t)}{t}\leq\mu$ for every
$t\geq 1$ (because of the scaling, we might lose the property that every
interval has length larger than $\frac{1}{2}$, but it will still be larger
than some constant). Let us see the relation that the $t_{i}$ must satisfy. We
have

$x_{i}=\sum\limits_{j=1}^{i}\ell_{i}\hskip
28.45274ptg(x_{i})=\sum\limits_{j=1}^{i}(-1)^{j+1}\ell_{i}\hskip
28.45274ptt_{i}=\gamma x_{i}+(-1)^{i+1}g(x_{i}).$

We can express $x_{i}$ in terms of $t_{1},t_{2},\dots,t_{i}$. Combining the
identities above we have $t_{i}=\sum_{j=1}^{i}(\gamma+(-1)^{j-i})\ell_{j}$,
and therefore
$t_{i}+t_{i-1}=(\gamma+1)\ell_{i}+2\gamma\sum_{j=1}^{i-1}\ell_{j}=(\gamma+1)x_{i}+(\gamma-1)x_{i-1}$,
which produces the recursion
$x_{i}=\frac{1-\gamma}{1+\gamma}x_{i-1}+\frac{1}{1+\gamma}(t_{i}+t_{i-1})$.
Together with $x_{1}=\frac{1}{1+\gamma}t_{1}$, the solution is

$x_{i}=\frac{1}{1+\gamma}t_{i}+\sum\limits_{j=1}^{i-1}\frac{2}{1-\gamma^{2}}\left(\frac{1-\gamma}{1+\gamma}\right)^{i-j}t_{j}.$

Based on these values, we can compute $\Gamma^{+}_{\gamma}(g,t)$ and
$\Gamma^{-}_{\gamma}(g,t)$. The former must lie in the interval
$[x_{i-1},x_{i}]$, where $i$ is the smallest odd value for which $t_{i}\geq
t$. Moreover, it is the unique value $x\in[x_{i-1},x_{i}]$ for which $t=\gamma
x+g(x)=\gamma x+(g(x_{i})+x-x_{i})=t_{i}-(\gamma+1)(x_{i}-x)$. If
$m_{o}=m_{o}(\\{t_{i}\\}_{i=1}^{\infty},t)$ is the smallest odd $i$ such that
$t_{i}\geq t$, then

$\Gamma^{+}_{\gamma}(g,t)=t_{m_{o}}-(\gamma+1)(x_{m_{0}}-x)=\frac{1}{1+\gamma}t+\sum\limits_{j=1}^{m_{o}-1}\frac{2}{1-\gamma^{2}}\left(\frac{1-\gamma}{1+\gamma}\right)^{m_{o}-j}t_{j}.$

Similarly, if $m_{e}=m_{e}(\\{t_{i}\\}_{i=1}^{\infty},t)$ is the smallest even
$i$ such that $t_{i}\geq t$, then

$\Gamma^{-}_{\gamma}(g,t)=\frac{1}{1+\gamma}t+\sum\limits_{j=1}^{m_{e}-1}\frac{2}{1-\gamma^{2}}\left(\frac{1-\gamma}{1+\gamma}\right)^{m_{e}-j}t_{j}.$

Define

$s(\\{t_{i}\\}_{i=1}^{\infty},t)=\frac{2}{1+\gamma}t+\sum\limits_{j=1}^{m_{o}-1}\frac{2}{1-\gamma^{2}}\left(\frac{1-\gamma}{1+\gamma}\right)^{m_{o}-j}t_{j}+\sum\limits_{j=1}^{m_{e}-1}\frac{2}{1-\gamma^{2}}\left(\frac{1-\gamma}{1+\gamma}\right)^{m_{e}-j}t_{j}.$

We are then interested in the lowest value that $\sup_{t\geq
1}\frac{s(\\{t_{i}\\}_{i=1}^{\infty},t)}{t}$ can take. Given a non-negative
unbounded sequence $\\{t_{i}\\}_{i=1}^{\infty}$, let $i_{1}<i_{2}<\dots$ be
the set of indices $i$ for which $t_{i}\geq 1$ and $t_{i}>t_{j}$ for every
$j<i$. One can check that $s(\\{t_{i_{j}}\\}_{j=1}^{\infty},t)\leq
s(\\{t_{i}\\}_{i=1}^{\infty},t)$ for every $t\geq 1$ (this is because
$\frac{1-\gamma}{1+\gamma}>1$). Therefore, we can assume that $t_{i}$ is
increasing and $t_{1}\geq 1$. In this case, and setting $t_{0}=0$,

$\sup\limits_{t\geq
1}\frac{s(\\{t_{i}\\}_{i=1}^{\infty},t)}{t}\geq\sup\limits_{i\geq
1}\frac{2}{1+\gamma}+\sum\limits_{j=1}^{i+1}\frac{2}{1-\gamma^{2}}\left(\frac{1-\gamma}{1+\gamma}\right)^{i-j+2}\frac{t_{j}+t_{j-1}}{t_{i}},$

since
$\\{m_{o}(\\{t_{i}\\}_{i=1}^{\infty},t_{i}+\epsilon),m_{e}(\\{t_{i}\\}_{i=1}^{\infty},t_{i}+\epsilon)\\}=\\{i+1,i+2\\}$
for $\epsilon>0$ small enough.

A sequence is called $S$-good if it satisfies

$St_{i}\geq\frac{2}{1+\gamma}t_{i}+\sum\limits_{j=1}^{i+1}\frac{2}{1-\gamma^{2}}\left(\frac{1-\gamma}{1+\gamma}\right)^{i-j+2}(t_{j}+t_{j-1})\hskip
28.45274pt\forall i\geq 1,$ (3)

which is a necessary condition for $\sup_{t\geq
1}\frac{s(\\{t_{i}\\}_{i=1}^{\infty},t)}{t}\geq S$. Suppose that a sequence is
$S$-good. Consider the recurring sequence where $T_{1}=t_{1}$ and

$ST_{i}=\frac{2}{1+\gamma}T_{i}+\sum\limits_{j=1}^{i+1}\frac{2}{1-\gamma^{2}}\left(\frac{1-\gamma}{1+\gamma}\right)^{i-j+2}(T_{j}+T_{j-1}).$
(4)

Observe that (4) is used to define $T_{i+1}$ from the previous entries, rather
than $T_{i}$.

######  Claim 1.

If $\\{t_{i}\\}_{i=1}^{\infty}$ is $S$-good, we have $t_{i}\leq T_{i}$ for
every $i\geq 1$.

###### Proof of Claim.

Suppose that there exists an index $i$ for which $t_{i}>T_{i}$. Let $u$ and
$v$ be the smallest indices such that $t_{u}\neq T_{u}$ and $t_{v}>T_{v}$,
respectively. Clearly we have $u\geq 2$. We will prove our claim by induction
on $v-u$. By definition of $T_{i}$ we have $u,v>1$. Combining (3) and (4) for
$i=u-1$ we see that we cannot have $v-u=0$.

Let $\alpha=\frac{T_{u}-t_{u}}{t_{1}}>0$. Consider the sequence
$\\{t^{\prime}_{i}\\}_{i=1}^{\infty}$, where $t^{\prime}_{i}=t_{i}$ for $i<u$
and $t^{\prime}_{i}=t_{i}+\alpha t_{i-u+1}$ for $i\geq u$. This sequence is
still increasing. We have $t^{\prime}_{1}=t_{1}$ and, by the choice of
$\alpha$ we have $t_{u}=T_{u}$. Additionally, $t^{\prime}_{v}\geq
t_{v}>T_{v}$. This means that, if we define $u^{\prime}$ and $v^{\prime}$
analogously to $u$ and $v$, then $u^{\prime}>u$ and $v^{\prime}\leq v$, which
leads to $v^{\prime}-u^{\prime}<v-u$. Finally, observe that
$\\{t^{\prime}_{i}\\}$ is still good, since (3) is satisfied for $i<u$ (the
equation becomes (4)) and for $i\geq u$ we have

$\displaystyle St^{\prime}_{i}=$ $\displaystyle St_{i}+St_{i-u+1}$
$\displaystyle=$
$\displaystyle\frac{2}{1+\gamma}(t_{i}+t_{i-u+1})+\sum\limits_{j=1}^{i+1}\frac{2}{1-\gamma^{2}}\left(\frac{1-\gamma}{1+\gamma}\right)^{i-j+2}(t_{j}+t_{j-1}+t_{j-u+1}+t_{j-u})$
$\displaystyle=$
$\displaystyle\frac{2}{1+\gamma}t^{\prime}_{i}+\sum\limits_{j=1}^{i+1}\frac{2}{1-\gamma^{2}}\left(\frac{1-\gamma}{1+\gamma}\right)^{i-j+2}(t^{\prime}_{j}+t^{\prime}_{j-1})$

taking $t_{i}=0$ for $i\leq 0$. This completes the induction step.∎

To complete the proof of Theorem 3, we show that $T_{i}\leq 0$ for some $i$ if
$S<\frac{2\gamma^{2}+2\gamma+8+\sqrt{32(1-\gamma)}}{(\gamma+1)^{3}}$. The
reason is that the sequence $T_{i}$ also satisfies the recursion

$ST_{i}-\frac{1-\gamma}{1+\gamma}ST_{i-1}=\frac{2}{1+\gamma}\left(T_{i}-\frac{1-\gamma}{1+\gamma}T_{i-1}\right)+\frac{2}{1-\gamma^{2}}\frac{1-\gamma}{1+\gamma}(T_{i+1}-T_{i}).$

which can be rewritten as $T_{i+1}+\alpha T_{i}+\beta T_{i-1}=0$. If $S$ is
smaller than the claimed bound, then the roots of the polynomial $x^{2}+\alpha
x+\beta$ are not real. This implies that $T_{i}\leq 0$ for some $i$ (see for
example [1]). This proves that
$S\geq\frac{2\gamma^{2}+2\gamma+8+\sqrt{32(1-\gamma)}}{(\gamma+1)^{3}}$, which
produces the desired value of $f(\lambda)$.∎

######  Proposition 4.

For $x>1$ we have $f(x)\geq\frac{x+1}{2x+1}$.

###### Proof.

We will prove this statement for rational values of $x$, and it will follow
for irrational values because $f$ is continuous (Proposition 1).

Let $x=s/r$. Let $F$ be the graph on $r+s$ vertices whose complement is a
clique on $r$ vertices (hence $\alpha(F)=r$). We have $\mu(\omega\cdot
F,n)=s\lceil n/r\rceil$, because an independent set $I$ intersects at least
$\lceil n/r\rceil$ components and has at least $s$ neighbors in each.
Combining Theorem 3 and Theorem 9 we find $f(s/r)\geq\rho(\omega\cdot
F)\geq\frac{r+s}{r+2s}$, or $f(x)\geq\frac{x+1}{2x+1}$. ∎

Ander Lamaison

<EMAIL_ADDRESS>
Institut für Mathematik, Freie Universität Berlin and Berlin Mathematical
School, Berlin, Germany.