ampmtime

# On the Ramsey numbers of daisies II

Marcelo Sales  Department of Mathematics, Emory University, Atlanta, GA, USA
<EMAIL_ADDRESS>
###### Abstract.

A $(k+r)$-uniform hypergraph $H$ on $(k+m)$ vertices is an $(r,m,k)$-daisy if
there exists a partition of the vertices $V(H)=K\cup M$ with $|K|=k$, $|M|=m$
such that the set of edges of $H$ is all the $(k+r)$-tuples $K\cup P$, where
$P$ is an $r$-tuple of $M$. Complementing results in [PRS], we obtain an
$(r-2)$-iterated exponential lower bound to the Ramsey number of an
$(r,m,k)$-daisy for $2$-colors. This matches the order of magnitude of the
best lower bounds for the Ramsey number of a complete $r$-graph.

The author was partially supported by NSF grant DMS 1764385

##  1\. Introduction

For a natural number $N$, we set $[N]=\\{1,\ldots,N\\}$. Given a set $X$, we
denote by $X^{(r)}$ the set of $r$-tuples of $X$. For two sets $X$, $Y$ we say
that $X<Y$ if $\max(X)<\min(Y)$. Unless stated otherwise, the elements of a
set $X$ will be always displayed in increasing order. That is, if
$X=\\{x_{1},\ldots,x_{t}\\}$, then $x_{1}<\ldots<x_{t}$.

A $(k+r)$-uniform hypergraph $H$ on $k+m$ vertices is an $(r,m,k)$-daisy if
there exists a partition of the vertices $V(H)=K\cup M$ with $|K|=k$ and
$|M|=m$ such that

$\displaystyle H=\\{K\cup P:P\in M^{(r)}\\}$

We say that the set $K$ is the kernel of $H$, the elements of $M^{(r)}$ are
the petals of $H$ and $M$ is the universe of petals. We will often refer to an
edge of $H$ by $X$ and its correspondent petal by $P$.

Daisies were first introduced by Bollobás, Leader and Malvenuto in [BLM11].
They were interested in Turán-type questions related to $(r,m,k)$-daisies,
i.e., the maximum number of edges that an $(r+k)$-graph has with no copy of an
$(r,m,k)$-daisy. In this paper we will study the Ramsey number $D_{r}(m,k)$ of
an $(r,m,k)$-daisy. The number $D_{r}(m,k)$ is defined as the minimum integer
$N$ such that any $2$-coloring of the complete hypergraph $[N]^{(k+r)}$
contains a monochromatic $(r,m,k)$-daisy.

Those numbers were already studied in [PRS]. Although the main focus of their
paper is on daisies with kernel of non fixed size, they noted that

$\displaystyle R_{r-k}(\lceil m/(k+1)\rceil-k)\leqslant D_{r}(m,k)\leqslant
R_{r}(m)+k,$ (1)

where $R_{r}(m)$ is the Ramsey number of the complete graph $K_{m}^{(r)}$,
i.e., the minimum integer $N$ such that any $2$-coloring of $[N]^{(r)}$
contains a monochromatic set $X$ of size $m$.

A natural question raised in [PRS] is whether $D_{r}(m,k)$ behaves similarly
$R_{r}(m)$. Erdős, Hajnal and Rado (see [EHR65, GRS13]) and Conlon, Fox and
Sudakov [CFS13] showed that there exists absolute constants $c_{1},c_{2}$ such
that for sufficiently large $m$,

$\displaystyle t_{r-2}(c_{1}m^{2})\leqslant R_{r}(m)\leqslant
t_{r-1}(c_{2}m),$ (2)

where $t_{i}(x)$ is the tower function defined by $t_{0}(x)=x$ and
$t_{i+1}(x)=2^{t_{i}(x)}$. In this paper we provide for $k\geqslant 1$ a lower
bound of $D_{r}(m,k)$ in the same order of magnitude as the best current
bounds of the Ramsey number $R_{r}(m)$ for sufficiently large $m$. We remark
here that for $k=0$, the problem is equivalent to the Ramsey number, since an
$(r,m,0)$-dais is just the complete graph $K_{m}^{(r)}$.

######  Theorem 1.1.

Let $r\geqslant 3$ and $k\geqslant 1$ be integers. There exist integer
$m_{0}=m_{0}(r,k)$ and absolute constant $c$ such that

$\displaystyle D_{r}(m,k)\geqslant t_{r-2}(ck^{-2}m^{2^{4-r}})$

holds for $m\geqslant m_{0}$.

In order to prove Theorem 1.1 we will actually study the Ramsey number of a
subfamily of daisies. We say that a hypergraph $H$ is a simple $(r,m,k)$-daisy
if $H$ is an $(r,m,k)$-daisy and its kernel $K$ can be partitioned into
$K=K_{0}\cup K_{1}$ such that $K_{0}<M<K_{1}$. We define the Ramsey number of
simple $(r,m,k)$-daisies $D_{r}^{\operatorname{smp}}(m,k)$ as the minimum
integer $N$ such that any $2$-coloring of the complete hypergraph
$[N]^{(k+r)}$ yields a monochromatic copy of a simple $(r,m,k)$-daisy.

In [PRS], the authors observed that the Ramsey number of daisies can be
bounded from below by the Ramsey number of simple daisies.

######  Proposition 1.2 ([PRS], Proposition 5.3).

$D_{r}(m,k)\geqslant D_{r}^{\operatorname{smp}}\left(\lceil
m/(k+1)\rceil,k\right)$.

Our main technical result is an $(r-2)$-iterated exponential lower bound for
the Ramsey number of simple $(r,m,k)$-daisies. Note that Theorem 1.1 is a
corollary from Proposition 1.2 and Theorem 1.3.

######  Theorem 1.3.

Let $r\geqslant 3$ and $k\geqslant 1$ be integers. There exist integer
$m_{0}=m_{0}(r,k)$ and absolute positive constant $c$ such that

$\displaystyle D_{r}^{\operatorname{smp}}(m,k)\geqslant
t_{r-2}(ck^{2^{4-r}-2}m^{2^{4-r}})$

holds for $m\geqslant m_{0}$.

Our proof is a variant of the stepping-up lemma of Erdős, Hajnal and Rado
[EHR65, GRS13]. There are $k+1$ distinct simple $(r,m,k)$-daisies depending on
the sizes of $K_{0}$ and $K_{1}$. While it is not hard to construct a coloring
avoiding a monochromatic copy of one of these simple daisies, the main
challenge is to define a coloring that avoids all $k+1$ simple
$(r,m,k)$-daisies simultaneously. To this end, we will introduce in Section 2
some auxiliary trees using the vertices of our ground set. A big portion of
the paper consists on the study of those trees and how to use them to obtain a
stepping-up lemma.

The paper is organized as follows. We introduce some auxiliary trees and most
of the terminology in Section 2. Section 3 is devoted to give a general
overview of the proof. We briefly describe the stepping-up lemma in [EHR65,
GRS13] with our setup and later describe the coloring of the variant. Sections
4 and 5 are the heart of the proof. We prove a key lemma (Lemma 5.1) that
allows us to identify an important auxiliary tree containing the petal of an
edge and then show how to reduce the stepping-up argument to this tree. We
finish the proof of the stepping-up lemma and Theorem 1.3 in Section 6.

##  2\. Auxiliary trees

Given an integer $N$, we construct a binary tree $T_{[2^{N}]}$ of height $N$
with $2^{N+1}-1$ vertices and identify its leaves with the set $[2^{N}]$. We
also identify each level of the tree with the set $[N+1]$, where the root is
at level $1$, while the leaves are at level $N+1$. For a vertex $u\in
T_{[2^{N}]}$ we denote its level by $\pi(u)$.

$1$$2$$3$$4$$5$$6$$7$$8$$1$$2$$3$$4$ Figure 1. An example of a binary tree
$T_{[2^{3}]}$ with its $4$ levels

Given two vertices $u,v$ in $T_{[2^{N}]}$, we say that $u$ is an ancestor of
$v$ if $\pi(u)<\pi(v)$ and there is a path $u=x_{1},x_{2},\ldots,x_{\ell}=v$
in $T_{[2^{N}]}$ such that $\pi(x_{i})\neq\pi(x_{j})$ for every $1\leqslant
i,j\leqslant\ell$. For two vertices $x,y\in[2^{N}]$ we define the greatest
common ancestor $a(x,y)$ of $x$ and $y$ as the vertex of $T_{[2^{N}]}$ of
highest level that is an ancestor of both $x$ and $y$. Also define

$\displaystyle\delta(x,y)=\pi(a(x,y)).$

Let $X=\\{x_{1},\ldots,x_{t}\\}\subseteq[2^{N}]$ with $x_{1}<\ldots<x_{t}$ be
a subset of the leaves of our binary tree. We define the auxiliary tree
$T_{X}$ of $X$ as the subtree of $T_{[2^{N}]}$ whose vertices are $X$ and all
their common ancestors. That is,

$\displaystyle T_{X}=X\cup\\{a(x_{i},x_{i+1}):\>1\leqslant i\leqslant t-1\\}.$

$1$$2$$3$$4$$5$$6$$7$$8$ Figure 2. The auxiliary tree $T_{X}$ for
$X=\\{2,3,7\\}$.

Note that $T_{X}$ is a tree of $2t-1$ vertices. Moreover, we denote the set of
non-leaves by $a(X)$ and its projection by $\delta(X)$, i.e.,

$\displaystyle a(X)$ $\displaystyle=\\{a(x_{i},x_{i+1}):\>1\leqslant
i\leqslant t-1\\}$ $\displaystyle\delta(X)$
$\displaystyle=\\{\delta(x_{i},x_{i+1}):\>1\leqslant i\leqslant t-1\\}.$

Since the auxiliary tree $T_{X}$ is uniquely determined by its ground set $X$,
sometimes we will denote $T_{X}$ by $X$.

Given a vertex $u\in a(X)$, we can define the set $X(u)$ of descendants of $u$
as the leaves of $T_{X}$ that have $u$ as an ancestor. That is,

$\displaystyle X(u)=\\{x\in X:\>\text{$u$ is an ancestor of $x$}\\}.$

The set of descendants of $u$ can be partitioned into the left descendants and
right descendants as follows: Since $T_{X}$ is a binary tree, the vertex $u$
has two children $v$ and $w$. Let $v$ be the left children of $u$ and $w$ be
the right children of $u$. Then we define the left descendants of $u$ by

$\displaystyle X_{L}(u)=X(v)$

and the right descendants of $u$ by

$\displaystyle X_{R}(u)=X(w).$

Note that by this definition $\max X_{L}(u)<\min X_{R}(u)$.

Although an auxiliary tree is not uniquely determined by its ancestors, we can
at least determine the “shape” of the tree $T_{X}$ by looking at $a(X)$. In a
more precise way, the following can be proved by a simple induction.

######  Fact 2.1.

If $X$ and $Y$ are subsets of $[2^{N}]$ such that $a(X)=a(Y)$, then $|X|=|Y|$.
Moreover, if $X=\\{x_{1},\ldots,x_{t}\\}$ and $Y=\\{y_{1},\ldots,y_{t}\\}$,
then $a(x_{i},x_{i+1})=a(y_{i},y_{i+1})$ for every $1\leqslant i\leqslant
t-1$.

Now we devote the rest of the section on classifying our auxiliary trees.

######  Definition 2.2.

Given $X=\\{x_{1},\ldots,x_{t}\\}\subseteq[2^{N}]$. We say that $I\subseteq X$
is a closed interval in $X$ if the following two conditions holds:

  1. (i)

$I=\\{x_{p},x_{p+1},\ldots,x_{q}\\}$ for some $1\leqslant p\leqslant
q\leqslant t$.

  2. (ii)

$I=X(a(x_{p},x_{q}))$.

$u$$1$$2$$3$$4$$5$$v$$1$$2$$3$$4$$5$ Figure 3. The interval $\\{2,3,4\\}$ is
closed, since $X(u)=\\{2,3,4\\}$ for $u=a(2,4)$. The interval $\\{4,5\\}$ is
not closed, since $X(v)=\\{1,2,3,4,5\\}\neq\\{4,5\\}$ for $v=a(4,5)$.

Alternatively, one can replace (ii) by the following useful equivalent
condition:

  1. (ii*)

For every vertex $y\in X\setminus I$, the vertex $a(x_{p},x_{q})$ is not an
ancestor of $y$.

The following proposition shows that closed intervals cannot have proper
intersections.

######  Proposition 2.3.

Let $I_{1}$, $I_{2}$ be two intervals in $X$ with $|I_{1}|\leqslant|I_{2}|$.
If $I_{1}$ and $I_{2}$ are closed, then either $I_{1}\cap I_{2}=\emptyset$ or
$I_{1}\subseteq I_{2}$.

###### Proof.

Suppose that $I_{1}\cap I_{2}$ is a proper intersection. That is, $I_{1}\cap
I_{2}\neq\emptyset$, $I_{1}\setminus I_{2}\neq\emptyset$ and $I_{2}\setminus
I_{1}\neq\emptyset$. Write $X=\\{x_{1},\ldots,x_{t}\\}$ and
$I_{1}=\\{x_{p_{1}},x_{p_{1}+1},\ldots,x_{q_{1}}\\}$,
$I_{2}=\\{x_{p_{2}},x_{p_{2}+1},\ldots,x_{q_{2}}\\}$ for $1\leqslant
p_{1}<p_{2}\leqslant q_{1}<q_{2}\leqslant t$. Let $u=a(x_{p_{1}},x_{q_{1}})$
and $v=a(x_{p_{2}},x_{q_{2}})$. We claim that either $u$ is an ancestor of $v$
or $v$ is an ancestor of $u$. Let $z\in I_{1}\cap I_{2}$. By definition, both
$u$ and $v$ are ancestors of $z$. This means that there exists descending
paths connecting $z$ to $u$ and $z$ to $v$ in $T_{X}$ with vertices in
different levels. However, every vertex in $T_{X}$ has at most one father.
Therefore, either the path $z$ to $u$ contains the path $z$ to $v$ or vice-
versa. If the path $z$ to $u$ contains the path $z$ to $v$, then $u$ is an
ancestor of $v$. Hence $u$ is an ancestor of $I_{2}\setminus I_{1}$, which
contradicts the fact that $I_{1}$ is closed (condition (ii*) of Definition
2.2). The other case is analogous. ∎

We classify the closed intervals of $X$ by three types: left combs, right
combs and broken combs.

######  Definition 2.4.

Given a closed interval $I$ in $X$ we say that

  1. (a)

$I$ is a $\ell$-left comb if $\ell$ is the least positive integer such that
there exists a partition $I=A\cup B$ with $|A|=\ell$ and $B\neq\emptyset$ and

    1. (a1)

$A<B$.

    2. (a2)

$A$ is a closed interval in $X$

    3. (a3)

If $z=\max(A)$ and $B=\\{b_{1},\ldots,b_{s}\\}$, then
$\delta(z,b_{1})>\delta(b_{1},b_{2})>\ldots>\delta(b_{s-1},b_{s})$.

  2. (b)

$I$ is a $\ell$-right comb if $\ell$ is the least positive integer such that
there exists a partition $I=A\cup B$ with $|A|=\ell$ and $B\neq\emptyset$ and

    1. (b1)

$B<A$.

    2. (b2)

$A$ is a closed interval in $X$

    3. (b3)

If $z=\min(A)$ and $B=\\{b_{1},\ldots,b_{s}\\}$, then
$\delta(b_{1},b_{2})<\ldots<\delta(b_{s-1},b_{s})<\delta(b_{t},z)$.

  3. (c)

$I$ is a broken comb if it is neither a left or right comb.

$A$$B$$A$$B$$A$ Figure 4. An example of a left, right and broken comb,
respectively.

We will use the convention that an $\ell$-left/right comb will be described by
its partition $I=A\cup B$ with $|A|=\ell$ that verifies the condition on
Definition 2.4. As we can see in the picture above, the set $A$ should be
thought as the “handle” of the comb, while the set $B$ should be thought as
the “teeth” of the comb. For broken combs we will adopt the same convention by
assuming that $B=\emptyset$.

One may remove the use of the projection $\delta(b_{i},b_{i+1})$ in conditions
(a3) and (b3) of the right/left comb by using the following equivalent
alternative conditions:

  1. (a3*)

If $B=\\{b_{1},\ldots,b_{s}\\}$, then the intervals
$A\cup\\{b_{1},\ldots,b_{i}\\}$ are closed in $X$ for every $1\leqslant
i\leqslant s$

  2. (b3*)

If $B=\\{b_{1},\ldots,b_{s}\\}$, then the intervals
$\\{b_{i},\ldots,b_{s}\\}\cup A$ are closed in $X$ for every $1\leqslant
i\leqslant s$.

Those conditions have the advantage of describing a comb only using closed
intervals. This will be useful later in the proof.

######  Example 2.5.

A important type of comb in the stepping-up lemma [EHR65, GRS13] is the
$1$-left/right comb. Those are the combs $I=\\{y_{1},\ldots,y_{t}\\}$
satisfying that the sequence $\\{\delta(y_{i},y_{i+1})\\}_{1\leqslant
i\leqslant t}$ is monotone. Indeed, the interval $I$ is a $1$-left comb if
$\delta(y_{1},y_{2})>\ldots>\delta(y_{t-1},y_{t})$, while it is a $1$-right
comb if $\delta(y_{1},y_{2})<\ldots<\delta(y_{t-1},y_{t})$.

Figure 5. A left and right $1$-comb

For the proof of Theorem 1.3 we will be interested in maximal comb structures
inside our auxiliary trees.

######  Definition 2.6.

Given $X=\\{x_{1},\ldots,x_{t}\\}\subseteq[2^{N}]$, a interval
$I=\\{x_{p},\ldots,x_{q}\\}$ is a

  1. (a)

Maximal left comb in $X$ if $I$ is a left comb and $I\cup\\{x_{q+1}\\}$ is not
a closed interval in $X$.

  2. (b)

Maximal right comb in $X$ if $I$ is a right comb and $I\cup\\{x_{p-1}\\}$ is
not a closed interval in $X$.

  3. (c)

Maximal broken comb in $X$ if $I$ is a broken comb and neither
$I\cup\\{x_{p-1}\\}$ or $I\cup\\{x_{q+1}\\}$ are closed.

Figure 6. An example of a maximal left, right and broken comb, respectively.

The next proposition shows that given two maximal combs they are either
disjoint or one is contained in the “handle” of the other.

######  Proposition 2.7.

Given a closed inteval $I_{1}$ and a maximal comb $I_{2}=A_{2}\cup B_{2}$ with
$|I_{1}|\leqslant|I_{2}|$ in a set $X\subseteq[2^{N}]$, then one of the
following holds:

  1. (1)

$I_{1}\cap I_{2}=\emptyset$

  2. (2)

$I_{1}\subseteq A_{2}$.

  3. (3)

$I_{1}=A_{2}\cup B_{1}$ for some initial segment $B_{1}\subseteq B_{2}$

Moreover, condition (3) only holds if $I_{1}$ is not a maximal comb.

###### Proof.

By Proposition 2.3 we obtain that either $I_{1}\cap I_{2}=\emptyset$ or
$I_{1}\subseteq I_{2}$. If the first case happens, then $I_{1}$ and $I_{2}$
satisfy condition (1) and we are done. Hence, we may assume that
$I_{1}\subseteq I_{2}$. If $I_{2}$ is a broken comb, then by definition
$A_{2}=I_{2}$. Thus in this case $I_{1}\subseteq A_{2}$, satsifying condition
(2). Now suppose without loss of generality that $I_{2}=A_{2}\cup B_{2}$ is a
left maximal comb and write $A_{2}=\\{x_{1},\ldots,x_{\ell}\\}$,
$B_{2}=\\{y_{1},\ldots,y_{s}\\}$. If $I_{1}\cap B_{2}=\emptyset$, then
$I_{1}\subseteq A_{2}$ and again condition (2) holds.

At last, it remains to deal with the case that $I_{1}\cap B_{2}\neq\emptyset$.
Since $I_{1}$ is an interval of $X$ and $I_{1}\subseteq I_{2}$, then in
particular $I_{1}$ is an interval of $I_{2}$. Write
$I_{1}=\\{x_{p},\ldots,x_{\ell}\\}\cup\\{y_{1},\ldots,y_{q}\\}$ for
$1\leqslant p\leqslant\ell$ and $1\leqslant q\leqslant s$. By condition (a3*)
of Definition 2.4, the set $A_{2}\cup\\{y_{1},\ldots,y_{q-1}\\}$ is closed.
Therefore for any $z\in A_{2}\cup\\{y_{1},\ldots,y_{q-1}\\}$ the greatest
ancestor $a(z,y_{q})$ of $z$ and $y_{q}$ is the same as the greatest ancestor
of $a(x_{1},y_{q})$. In particular, this implies that $a(x_{p},y_{q})$ is an
ancestor for the entire set $A_{2}$. Hence $A_{2}\subseteq I_{1}$ and
consequently $I_{1}=A_{1}\cup B_{1}$ is a left comb satisfying condition (3),
because $A_{1}=A_{2}$ and $B_{1}$ is an initial segment of $B_{2}$. Note that
$I_{1}$ is not maximal in this case, since the set $I_{1}\cup\\{y_{q+1}\\}$ is
also a left comb. Thus if $I_{1}$ is a maximal comb, then it either satisfies
(1) or (2). ∎

##  3\. Stepping-up lemma and our coloring

###  3.1. Erdős–Hajnal–Rado stepping-up lemma

For instructional purposes, we will briefly go over the stepping-up lemma in
[EHR65, GRS13] using our notation. For $k\geqslant 4$, let
$N=R_{k-1}((n-k+4)/2)-1$ and $\varphi:[N]^{(k-1)}\rightarrow\\{0,1\\}$ be a
coloring of the $(k-1)$-tuples in $[N]$ with no monochromatic subset of size
$(n-k+4)/2$. Our goal is to find a coloring
$\psi:[2^{N}]^{(k)}\rightarrow\\{0,1\\}$ with no monochromatic subset of size
$n$. This will give us that $R_{k}(n)>2^{N}=2^{R_{k-1}((n-k+4)/2)-1}$.

Fix an edge $X=\\{x_{1},\ldots,x_{k}\\}\in[2^{N}]^{(k)}$ and let
$\delta_{i}=\delta(x_{i},x_{i+1})$. We describe the coloring $\psi$ by the
structure of $T_{X}$ and the coloring of the vertical projection $\varphi$ of
$[N]$ in the following way

$\displaystyle\psi(X)=\begin{cases}0,&\quad\text{if
}\delta_{k-3}>\delta_{k-2}<\delta_{k-1}\\\ 1,&\quad\text{if
}\delta_{k-3}<\delta_{k-2}>\delta_{k-1}\\\
\varphi(\\{\delta_{1},\ldots,\delta_{k-1}\\}),&\quad\text{otherwise if
$|\delta(X)|=k-1$}\\\ 0,&\quad\text{otherwise if
$|\delta(X)|<k-1$.}\end{cases}$

Suppose by contradiction that $\psi$ contains a monochromatic subset
$Y\subset[2^{N}]$ of size $n$. We can use the structure of $Y$ to find a large
$1$-comb.

######  Proposition 3.1.

There exists an interval $I$ of $Y$ with $|I|\geqslant(n-k+6)/2$ such that $I$
is a $1$-comb

###### Proof.

We may assume without loss of generality that $Y$ is monochromatic of color
$0$. Write $Y=\\{y_{1},\ldots,y_{n}\\}$ and let
$\delta^{Y}_{i}=\delta(y_{i},y_{i+1})$ for $1\leqslant i\leqslant n-1$. Since
all edges in $Y$ are of color $0$, then for any edge
$X=\\{x_{1},\ldots,x_{k}\\}\in Y^{(k)}$ we do not have that

$\displaystyle\delta(x_{k-3},x_{k-2})<\delta(x_{k-2},x_{k-1})>\delta(x_{k-1},x_{k}).$

In particular, this implies that there is no indices $k-3\leqslant
i<j<\ell\leqslant n-1$ such that
$\delta^{Y}_{i}<\delta^{Y}_{j}>\delta^{Y}_{\ell}$. That is, the sequence
$\\{\delta^{Y}_{i}\\}_{i=k-3}^{n-1}$ has no local maximum.

A standard calculus argument says that between two local minimums there is
always a local maximum. Therefore, the sequence
$\\{\delta^{Y}_{i}\\}_{i=k-3}^{n-1}$ has at most one local minimum, which
means that there exists an interval $[p,q]$ of size $(n-k+4)/2$ such that
$\\{\delta^{Y}_{i}\\}_{i\in[p,q]}$ is monotone. Thus by definition the
interval $I=\\{x_{p},x_{p+1},\ldots,x_{q+1}\\}$ is a $1$-comb of size
$(n-k+6)/2$. ∎

Let $I=\\{z_{1},\ldots,z_{t}\\}$ be the $1$-comb of $Y$ obtained by
Proposition 3.1 and denote $\delta_{i}^{I}=\delta(z_{i},z_{i+1})$ for
$1\leqslant i\leqslant i-1$. Note that because
$\\{\delta_{i}^{I}\\}_{i=1}^{t-1}$ is a monotone sequence, every edge $X\in
I^{(k)}$ will be also a $1$-comb. Moreover, for every $(k-1)$-tuple
$Z\in\delta(I)$ there exists an edge $X\in I^{(k)}$ such that $\delta(X)=Z$.

Finally, by the definition of the coloring $\psi$, if $X$ is a $1$-comb, then
$\psi(X)=\varphi(\delta(X))$. Thus if $I^{(k)}$ colored by $\psi$ is
monochromatic, then $\delta(I)^{(k-1)}$ colored by $\varphi$ is also
monochromatic. This implies that $[N]$ has a monochromatic set of size
$(n-k+4)/2$, which contradicts our assumption on $\varphi$.

###  3.2. Overview of the proof

In order to obtain a lower bound for simple daisies, we will define a variant
of the stepping-up lemma described in the previous subsection. Suppose for a
moment that our goal is to avoid a monochromatic simple $(r,m,k)$-daisy with
in $[2^{N}]$ with $|K_{0}|=k_{0}$ and $|K_{1}|=k_{1}$ fixed. Then for every
edge $X=\\{x_{1},\ldots,x_{k+r}\\}$ of the daisy, we know that the petal of
size $r$ of $X$ is $P=\\{x_{k_{0}+1},\ldots,x_{k_{1}}\\}$. That is, we know
the exact location of the petal prior defining the coloring in our stepping-up
lemma. In this case a natural way to define the coloring would be to just
assign for every edge $X$ with petal $P\subseteq X$ the color
$\chi(X)=\psi(P)$, where $\psi(P)$ is exactly the stepping-up coloring defined
in the previous subsection. Since the petal is the only part of the edge
changing when we run through all edges, a similar proof as in the previous
subsection works.

Unfortunately, in the original problem we want to avoid all possible
monochromatic simple $(r,m,k)$-daisies, which means that we need to avoid
simple daisies for all the values of $|K_{0}|$ and $|K_{1}|$. The obstruction
now is that the location of the petal within the edge is no longer clear to
us. To fix that we are going to pre-process our monochromatic simple daisy
(Lemma 5.1) to satisfy the following property: Every petal $P$ of an edge $X$
is either a closed interval in $X$ or is in the “teeth” of a maximal comb in
$X$. This gives us partial information about the location of the petal. A good
strategy then is to define an auxiliary coloring $\chi_{0}$ for every maximal
comb in $X$ and use those colorings to define a coloring for $X$. This is the
content of Section 3.3.

Some technical challenges remain. By Proposition 2.7, the maximal combs in $X$
do not need to be disjoint. Therefore, it might happen that for the coloring
$\chi$ different maximal combs interfere with each other. To solve that we
need to construct a careful coloring taking the issue into consideration. In
Section 4 we provide an analysis showing that distinct maximal combs do not
interfere with each other in our coloring. Section 5 is devoted to the pre-
processing described in the last paragraph. One of the consequences of the
section is that for an edge $X$ the coloring $\chi(X)$ is essentially
determined by a unique maximal comb inside of it. Finally, we finish the proof
in Section 6, by showing, similarly as in Subsection 3.1, that a monochromatic
simple daisy in $[2^{N}]$ corresponds to a monochromatic simple daisy in the
vertical coloring of $[N]$.

###  3.3. A variant of the stepping-up lemma

Let $N=\min_{0\leqslant t\leqslant
k-1}\left\\{D_{r-1}^{\operatorname{smp}}(c_{k}\sqrt{m},t)-1\right\\}$ for
$r\geqslant 4$ and $c_{k}$ some constant depending on $k$ to be defined later
and let $\\{\varphi_{i}\\}_{r-1\leqslant i\leqslant k+r-1}$ be a family of
colorings such that $\varphi_{i}:[N]^{(i)}\rightarrow\\{0,1\\}$ is a
$2$-coloring of the $i$-tuples without a monochromatic simple
$(r-1,c_{k}\sqrt{m},i-r+1)$-daisy. Note that by the choice of $N$ is always
possible to find such a family.

Given an $(k+r)$-tuple $X\in[2^{N}]^{(k+r)}$ we define

$\displaystyle\mathcal{I}_{X}=\\{I\subseteq X:\>\text{$I$ is a maximal comb in
$X$}\\}$

as the set of maximal combs of $X$. We will construct now an auxiliary
coloring $\chi_{0}:\mathcal{I}_{X}\rightarrow\\{0,1\\}$ depending on the
structure of $T_{X}$ and in the family of colorings
$\\{\varphi_{t}\\}_{0\leqslant t\leqslant k}$. The coloring is divided in
several cases depending on the type of the maximal comb $I$.

Remember that a maximal $\ell$-comb is always identified with the partition
$I=A\cup B$, where $|A|=\ell$ is the handle and $B$ is the set of teeth of the
comb. Also write $I=\\{x_{1},\ldots,x_{s}\\}$ and let
$\delta_{i}^{I}=\delta(x_{i},x_{i+1})$ for $1\leqslant i\leqslant s-1$. Aiming
to simplify the discussion, we will only describe $\chi_{0}$ for left and
broken maximal combs. We define $\chi_{0}$ for right combs by symmetry.

Type 1: $I$ is broken or left comb, $|I|=r$ and there is no maximal comb
$I^{\prime}=A^{\prime}\cup B^{\prime}$ such that $I=A^{\prime}$.

$\displaystyle\chi_{0}(I)=\begin{cases}0,&\quad\text{if
}\delta^{I}_{r-3}>\delta^{I}_{r-2}<\delta^{I}_{r-1}\\\ 1,&\quad\text{if
}\delta^{I}_{r-3}<\delta^{I}_{r-2}>\delta^{I}_{r-1}\\\
\varphi_{|\delta(I)|}(\\{\delta^{I}_{1},\ldots,\delta^{I}_{r-1}\\}),&\quad\text{otherwise
if $|\delta(I)|=r-1$}\\\ 0,&\quad\text{otherwise if
$|\delta(I)|<r-1$}\end{cases}$

Type 2: $I$ is left comb, $|I|=r$ and there exists a maximal comb
$I^{\prime}=A^{\prime}\cup B^{\prime}$ such that $I=A^{\prime}$

$\displaystyle\chi_{0}(I)=0$

$B^{\prime}$$A^{\prime}=I$ Figure 7. An example of left comb of type 2.

Type 3: $I$ is left comb, $\ell=|A|\leqslant r$ and $r+1\leqslant|I|\leqslant
2r-2$.

$\displaystyle\chi_{0}(I)=\begin{cases}0,&\quad\text{if
}\delta^{I}_{r-3}>\delta^{I}_{r-2}<\delta^{I}_{r-1}\\\ 1,&\quad\text{if
}\delta^{I}_{r-3}<\delta^{I}_{r-2}>\delta^{I}_{r-1}\\\
\varphi_{|\delta(I)|}(\\{\delta^{I}_{1},\ldots,\delta^{I}_{s-1}\\}),&\quad\text{otherwise
if $|\delta(I)|\geqslant r-1$}\\\ 0,&\quad\text{otherwise if
$|\delta(I)|<r-1$}\end{cases}$

Type 4: $I$ is left comb, $\ell=|A|\leqslant r$ and $|I|\geqslant 2r-1$.

$\displaystyle\chi_{0}(I)=\begin{cases}\varphi_{s-r}(\\{\delta_{r}^{I},\ldots,\delta_{s-1}^{I}\\}),&\quad\text{if
}\delta^{I}_{r-3}>\delta^{I}_{r-2}<\delta^{I}_{r-1}\\\
\varphi_{s-r}(\\{\delta_{r}^{I},\ldots,\delta_{s-1}^{I}\\})+1,&\quad\text{if
}\delta^{I}_{r-3}<\delta^{I}_{r-2}>\delta^{I}_{r-1}\\\
\varphi_{|\delta(I)|}(\\{\delta^{I}_{1},\ldots,\delta^{I}_{s-1}\\}),&\quad\text{otherwise}\end{cases}$

$A$$\\{x_{1},\ldots,x_{r}\\}$$\\{x_{r+1},\ldots,x_{s}\\}$$\\{\delta_{1}^{I},\ldots,\delta_{s-1}^{I}\\}$$\\{\delta_{r}^{I},\ldots,\delta_{s-1}^{I}\\}$
Figure 8. A left comb of Type $4$ and its projections.

Type 5: $I$ is left comb, $\ell=|A|>r$ and $|B|\geqslant r$.

$\displaystyle\chi_{0}(I)=\varphi_{|B|}(\delta_{\ell}^{I},\ldots,\delta_{s-1}^{I})$

$A$$B=\\{x_{\ell+1},\ldots,x_{s}\\}$$\\{\delta_{\ell}^{I},\ldots,\delta_{s-1}^{I}\\}$
Figure 9. A left comb of Type $5$ and its projections.

Type 6: All other broken or left maximal combs.

$\displaystyle\chi_{0}(I)=0$

Finally, the auxiliary coloring $\chi_{0}$ define a coloring
$\chi:[2^{N}]^{(k+r)}\rightarrow\\{0,1\\}$ as follows:

$\displaystyle\chi(X)=\sum_{I\in\mathcal{I}_{X}}\chi_{0}(I)\pmod{2}$

##  4\. Coloring data

Given an edge $X$ and a maximal comb $I\subseteq X$, one can determine the
color $\chi_{0}(I)$ by looking at the type of the maximal comb $I$. Some of
the types do not use information on the ancestors to determine its coloring.
For instance, if $I$ is of type $2$, then its color will be always $0$. The
projection of the ancestors $\delta_{i}^{I}$ has no influence in defining
$\chi_{0}(I)$. However, if $I$ is of type $1$, then the color crucially
depends on the projection of the ancestors.

This observation suggests the following definition. Given an edge
$X\in[2^{N}]^{(k+r)}$ and a maximal comb $I\subseteq X$, let the coloring data
$F(I)$ of $I$ be defined as the ordered set of ancestors whose projection
determine the coloring $\chi_{0}(I)$. More explicitly, we can define directly
the coloring data of $I$ by looking its types. We may assume here that
$I=\\{x_{1},\ldots,x_{s}\\}$ is a broken or left maximal comb.

  * $\bullet$

Type 1,3 and 4: $F(I)=\\{a(x_{i},x_{i+1})\\}_{1\leqslant i\leqslant s-1}$

  * $\bullet$

Type 2 and 6: $F(I)=\emptyset$

  * $\bullet$

Type 5: $F(I)=\\{a(x_{i},x_{i+1})\\}_{\ell\leqslant i\leqslant s-1}$

Our first observation is that maximal combs with same data have same color.

######  Proposition 4.1.

Let $X$, $X^{\prime}\in[2^{N}]^{(k+r)}$ be two edges. If $I$ and $I^{\prime}$
are maximal combs of same type in $X$ and $X^{\prime}$, respectively, such
that $F(I)=F(I^{\prime})$, then $\chi_{0}(I)=\chi_{0}(I^{\prime})$.

###### Proof.

The proof basically consists of checking the consistency of our definition. If
$F(I)=F(I^{\prime})=\emptyset$, then $I$ and $I^{\prime}$ are either of type
$2$ or $6$. In both cases $\chi_{0}(I)=\chi_{0}(I^{\prime})=0$.

If $I=\\{x_{1},\ldots,x_{s}\\}$ and
$I^{\prime}=\\{x^{\prime}_{1},\ldots,x^{\prime}_{s^{\prime}}\\}$ are of type
$1$, $3$ or $4$, then since $a(I)=F(I)=F(I^{\prime})=a(I^{\prime})$ we obtain
by Fact 2.1 that $s=s^{\prime}$ and
$a(x_{i},x_{i+1})=a(x^{\prime}_{i},x^{\prime}_{i+1})$ for every $1\leqslant
i\leqslant s$. Therefore
$\delta(x_{i},x_{i+1})=\delta(x^{\prime}_{i},x^{\prime}_{i+1})$ for every
$1\leqslant i\leqslant s$ and by the coloring defined in Section 3.3, it
follows that $\chi_{0}(I)=\chi_{0}(I^{\prime})$.

The last case that we need to check is when $I=A\cup
B=\\{x_{1},\ldots,x_{s}\\}$ and $I^{\prime}=A^{\prime}\cup
B^{\prime}=\\{x^{\prime}_{1},\ldots,x^{\prime}_{s^{\prime}}\\}$ are of type
$5$, where $|A|=\ell$ and $|A^{\prime}|=\ell^{\prime}$. As usual, we assume
that $I$ and $I^{\prime}$ are left combs. Since
$a(\\{x_{\ell},\ldots,x_{s}\\})=F(I)=F(I^{\prime})=a(\\{x^{\prime}_{\ell^{\prime}},\ldots,x^{\prime}_{s^{\prime}}\\})$,
it follows again by Fact 2.1 that
$s-\ell=|B|=|B^{\prime}|=s^{\prime}-\ell^{\prime}$ and
$a(x_{i},x_{i+1})=a(x^{\prime}_{i},x^{\prime}_{i+1})$ for $\ell\leqslant
i\leqslant s-1$. Thus
$\delta(x_{i},x_{i+1})=\delta(x^{\prime}_{i},x^{\prime}_{i+1})$ for
$\ell\leqslant i\leqslant s-1$ and by the coloring of type 5 we obtain that
$\chi_{0}(I)=\chi_{0}(I^{\prime})$. ∎

Although maximal combs in the same edge do not need to be disjoint, the next
result shows that they do not share the same coloring data.

######  Proposition 4.2.

Let $X\in[2^{N}]^{(k+r)}$ be an edge. If $I=A\cup B$ and
$I^{\prime}=A^{\prime}\cup B^{\prime}$ are maximal combs in $X$, then
$F(I)\cap F(I^{\prime})=\emptyset$.

###### Proof.

Suppose without loss of generality that $|I|\leqslant|I^{\prime}|$. By
Proposition 2.7 either $I\cap I^{\prime}=\emptyset$ or $I\subseteq
A^{\prime}$. If $I\cap I^{\prime}=\emptyset$, then by the fact that
$I,I^{\prime}$ are closed we obtain that $a(I)\cap a(I^{\prime})=\emptyset$.
Since $F(I)\subseteq a(I)$ by definition, it follows that $F(I)\cap
F(I^{\prime})=\emptyset$.

Now suppose that $I\subseteq A^{\prime}$. We may assume that
$F(I),F(I^{\prime})\neq\emptyset$ and consequently that $I,I^{\prime}$ are of
type $1$, $3$, $4$ or $5$. Since maximal combs of types $1$, $3$, $4$ and $5$
have size at least $r$, our assumption implies that
$|I^{\prime}|\geqslant|I|\geqslant r$.

We claim that $|A^{\prime}|>r$. Suppose that $|A^{\prime}|=r$. Since
$r\leqslant|I|\leqslant|A^{\prime}|$ we obtain that $I=A^{\prime}$ and
$|I|=r$. The maximality of $I$ implies that it is either a left or right
maximal comb (otherwise we could extend the comb to $I\cup B$). However, in
this case $I$ is of type $2$. Thus $F(I)=\emptyset$, which contradicts our
assumption on $I$. Therefore $|A^{\prime}|>r$ and consequently $I^{\prime}$ is
of type $5$. Write
$I^{\prime}=\\{x^{\prime}_{1},\ldots,x^{\prime}_{s^{\prime}}\\}$ with
$|A^{\prime}|=\ell^{\prime}$ and assume that $I^{\prime}$ is a left comb. Then
by definition

$\displaystyle
F(I^{\prime})=\\{a(x^{\prime}_{i},x^{\prime}_{i+1})\\}_{\ell^{\prime}\leqslant
i\leqslant s^{\prime}-1}.$

Since $I\subseteq A^{\prime}$ we obtain that $F(I)\subseteq a(A^{\prime})$. By
the structure of a left comb we have that

$\displaystyle\delta(x^{\prime}_{1},x^{\prime}_{\ell^{\prime}})>\delta(x^{\prime}_{\ell^{\prime}},x^{\prime}_{\ell^{\prime}+1})>\delta(x^{\prime}_{\ell^{\prime}+1},x^{\prime}_{\ell^{\prime}+2})>\ldots>\delta(x^{\prime}_{s^{\prime}-1},x^{\prime}_{s^{\prime}}).$

$A$$B$$a(I)$$\\{a(x_{i},x_{i+1})\\}_{\ell^{\prime}\leqslant i\leqslant s-1}$
Figure 10. A picture of $I$ and
$\\{a(x_{i},x_{i+1})\\}_{\ell^{\prime}\leqslant i\leqslant s-1}$

Thus $a(I)\cap\\{a(x^{\prime}_{i},x^{\prime}_{i+1})\\}_{\ell^{\prime}\leqslant
i\leqslant s^{\prime}-1}=\emptyset$ and consequently $F(I)\cap
F(I^{\prime})=\emptyset$. ∎

##  5\. Pre-processing

As discussed in Subsection 3.2, we now turn our focus to show that a simple
daisy $H$ can be pre-processed in a smaller simple subdaisy $H^{\prime}$ with
the property that for every edge $X$ its petal $P$ is either a closed interval
in $X$ or is part of the “teeth” of a maximal comb in $X$.

######  Lemma 5.1.

For any simple $(r,m,k)$-daisy $H$ with vertex set $V(H)\subseteq[2^{N}]$,
$K_{0}<M<K_{1}$, $|K_{0}\cup K_{1}|=k$ and $|M|=m$, there exists a subset
$M^{\prime}\subseteq M$ of size $|M^{\prime}|=\frac{1}{2}k^{-1/2}m^{1/2}$ such
that the simple $(r,\frac{1}{2}k^{-1/2}m^{1/2},k)$-daisy
$H^{\prime}=H[K_{0}\cup M^{\prime}\cup K_{1}]$ satisfies one of the following:

  1. (1)

$M^{\prime}$ is a closed interval in $V(H^{\prime})$.

  2. (2)

There exists a maximal comb $I=A\cup B$ in $V(H^{\prime})$ such that
$M^{\prime}\subseteq B$.

$K_{0}$$M^{\prime}$$K_{1}$$K_{0}$$M^{\prime}$$K_{1}$ Figure 11. An example of
$H^{\prime}$ satisfying statement (1) and (2).

###### Proof.

Let $V:=V(H)$. Given a closed interval $I\subseteq V$, by condition (ii) of
Definition 2.2 there exists a vertex $u\in a(I)$ such that $I=V(u)$. Consider
the partition of $I$ given by $I=I^{L}\cup I^{R}$, where $I^{L}=V_{L}(u)$ are
the left descendants of $u$ and $I^{R}=V_{R}(u)$ are the right descendants of
$u$. Let $v$ be the left child of $u$ and $w$ be the right child. Hence,
$I^{L}=V(v)$ and $I^{R}=V(w)$ and consequently $I=I^{L}\cup I^{R}$ is a
partition of a closed interval in $V$ into two closed intervals in $V$.

$u$$w$$v$$V$$I^{L}$$I^{R}$$I=V(u)$ Figure 12. Partition of a closed interval
into two other closed intervals.

We will construct our set $M^{\prime}$ iteratively. This is done in two
stages. In the first stage we start with the closed interval $Y_{0}=V$ and
proceed recursively as follows: For a closed interval $Y_{i}\subseteq V$, let
$Y_{i}=Y_{i}^{L}\cup Y_{i}^{R}$ be the partition described above in two closed
intervals. The choice of $Y_{i+1}$ is determined by the conditions below

  1. (P1)

Set $Y_{i+1}:=Y_{i}^{L}$ if $|Y_{i}^{L}\cap M|\geqslant|Y_{i}^{R}\cap M|$.

  2. (P2)

Set $Y_{i+1}:=Y_{i}^{R}$ if $|Y_{i}^{L}\cap M|<|Y_{i}^{R}\cap M|$.

We stop the process whenever $Y_{i}\cap K_{0}=\emptyset$ or $Y_{i}\cap
K_{1}=\emptyset$. Note that at each iteration of the process the size of
$|(K_{0}\cup K_{1})\cap Y_{i}|$ reduces at least by one. Thus, in a finite
amount of time the process terminates. Let $Y$ be the closed interval obtained
in the end. We may assume without loss of generality that $Y\cap
K_{1}=\emptyset$. Write $Y=K_{Y}\cup M_{Y}$, where $K_{Y}\subseteq K_{0}$ and
$M_{Y}\subseteq M$. It is not hard to check by the construction that
$|M_{Y}|\geqslant m/2$.

For the second stage, let $Z_{0}=Y$. Given a closed interval $Z_{i}\subseteq
V$, let $Z_{i}=Z_{i}^{L}\cup Z_{i}^{R}$ be the partition into two closed
intervals. By definition we have that $Z_{i}^{L}<Z_{i}^{R}$. We say that a
partition $Z_{i}^{L}\cup Z_{i}^{R}$ is of type $A$ if $Z_{i}^{R}\cap
K_{0}=\emptyset$ and of type $B$ if $Z_{i}^{R}\cap K_{0}\neq\emptyset$. The
choice of $Z_{i+1}$ will depend on the type of partition as follows:

Type A: $Z_{i}^{R}\cap K_{0}=\emptyset$.

  1. (A1)

Set $Z_{i+1}:=Z_{i}^{L}$ if $|Z_{i}^{R}|<\frac{1}{2}k^{-1/2}m^{1/2}$.

  2. (A2)

Set $Z_{i+1}:=Z_{I}^{R}$ if $|Z_{i}^{R}|\geqslant\frac{1}{2}k^{-1/2}m^{1/2}$
and stop the process.

Type B: $Z_{i}^{R}\cap K_{0}\neq\emptyset$.

  1. (B)

Set $Z_{i+1}:=Z_{i}^{R}$.

We terminate the process if we either reach condition (A2) or if $Z_{i+1}$ is
a singleton. Since $|Z_{i+1}|<|Z_{i}|$, the process is finite. Let $Z$ be the
closed interval obtained at the end. We split into two cases.

If the process terminates after some instance of condition (A2), then it means
that $Z=Z_{i}^{R}$ is a closed interval in $V$ with
$|Z|\geqslant\frac{1}{2}k^{-1/2}m^{1/2}$ for some index $i$. Because we are in
a partition of type $A$ we also obtain that $Z\subseteq M$. Thus, if we set
$M^{\prime}=Z$ the simple subdaisy $H[K_{0}\cup M^{\prime}\cup K_{1}]$
satisfies condition (1) of the statement.

Now suppose that the process terminates with $|Z|=1$. Then it means that for
every partition of type A we had an instance of condition (A1). If $Z_{i+1}$
is a set obtained after condition (A1), then $|Z_{i+1}\cap M|>|Z_{i}\cap
M|-\frac{1}{2}k^{-1/2}m^{1/2}$ and $|Z_{i+1}\cap K_{0}|=|Z_{i+1}\cap K_{0}|$.
That is, condition (A1) removes less than $\frac{1}{2}k^{-1/2}m^{1/2}$ element
of $M$ from $Z_{i}$ and no elements of $K_{0}$ from it. Moreover, if $Z_{i+1}$
is obtained after condition (B), then $|Z_{i+1}\cap M|=|Z_{i}\cap M|$ and
$|Z_{i+1}\cap K_{0}|<|Z_{i}\cap K_{0}|$. That is, $M$ remains unaffected, but
$K_{0}$ loses at least one element from $K_{i}$ to $K_{i+1}$.

Consider the sequence of operations applied to $Z_{0}$ in order to obtain $Z$.
Since we start with a set $Z_{0}=Y$ with $|Z_{0}\cap M|=|M_{Y}|\geqslant m/2$,
we obtain that during our process we had at least

$\displaystyle\frac{\frac{m}{2}}{\frac{1}{2}k^{-1/2}m^{1/2}}=k^{1/2}m^{1/2}$

instances of condition (A1) in the sequence. Similarly, since $|Z_{0}\cap
K_{0}|=|K_{Y}|\leqslant k$, we obtain that we had at most $k$ instances of
condition (B) in the sequence. Hence, by the pigeonhole principle there exists
a sequence of consecutive applications of condition (A1) of length at least
$m^{\prime}=k^{1/2}m^{1/2}/(k+1)\geqslant\frac{1}{2}k^{-1/2}m^{1/2}$.

$\dots$$\dots$$Z_{j}^{R}$$Z_{j+1}^{R}$$Z_{j+m^{\prime}-1}^{R}$$Z_{j+m^{\prime}}$$M^{\prime}$$K_{1}$$K_{0}$
Figure 13. Sequence of closed intervals
$Z_{j}^{R},\ldots,Z_{j+m^{\prime}-1}^{R}$.

Let $Z_{j},Z_{j+1},\ldots,Z_{j+m^{\prime}}$ be the closed intervals involved
in the sequence. That is, $Z_{i+1}$ is obtained from $Z_{i}$ by a condition
(A1) for every $j\leqslant i\leqslant j+m^{\prime}-1$. By the algorithm, we
obtain closed intervals $Z_{j}^{R},\ldots,Z_{j+m^{\prime}-1}^{R}\subseteq M$
all of them with size less than $\frac{1}{2}k^{-1/2}m^{1/2}$. For every
$j\leqslant i\leqslant j+m^{\prime}-1$, choose a point $z_{i}\in Z_{i}^{R}$.

Set $M^{\prime}=\\{z_{j},\ldots,z_{j+m^{\prime}-1}\\}$. We claim that
$M^{\prime}$ is a set satisfying condition (2) of the statement. Let
$H^{\prime}=H[K_{0}\cup M^{\prime}\cup K_{1}]$ and $V^{\prime}=V(H^{\prime})$.
To see that condition (2) is satisfied we just need to find a maximal comb
$I=A\cup B\subseteq V^{\prime}$ such that $M^{\prime}\subseteq B$. Let
$K^{\prime}=K_{0}\cap Z_{j+m^{\prime}}$ and consider the interval
$I^{\prime}=K^{\prime}\cup M^{\prime}$ in $V^{\prime}$. By construction, the
intervals $K^{\prime}$ and
$K^{\prime}\cup\\{z_{j+i},\ldots,z_{j+m^{\prime}-1}\\}$ are closed in
$V^{\prime}$ for every $0\leqslant i\leqslant m^{\prime}-1$. Therefore, by
condition (a3*) of Definition 2.4, the interval $I^{\prime}=A^{\prime}\cup
B^{\prime}$ is a left comb and $M^{\prime}\subseteq B^{\prime}$. Since every
comb can be extended to a maximal one, there exists a maximal left comb
$I=A\cup B$ with $A=A^{\prime}$ and $B^{\prime}\subseteq B$ such that
$M^{\prime}\subseteq B$ and we are done. ∎

One of the main consequences of our pre-processing is that it allows us to
identify certain closed and non-closed intervals in an arbitrary edge of
$H^{\prime}$. To be more precise, given an edge $X\in E(H^{\prime})$ with
petal $P$ and $V^{\prime}=V(H^{\prime})$, let

$\displaystyle\mathcal{C}_{V^{\prime},M^{\prime}}$
$\displaystyle=\\{I:\>\text{$I$ is an interval in $V^{\prime}$ and either
$M^{\prime}\subseteq I$ or $M^{\prime}\cap I=\emptyset$}\\}$
$\displaystyle\mathcal{C}_{X,P}$ $\displaystyle=\\{I:\>\text{$I$ is an
interval in $X$ and either $P\subseteq I$ or $P\cap I=\emptyset$}\\}$

be the set of intervals in $V^{\prime}$ and $X$ such that the intervals either
contain or are disjoint of $M^{\prime}$ and $P$, respectively. The next
proposition shows that there is a one-to-one correspondence between
$\mathcal{C}_{V^{\prime},M^{\prime}}$ and $\mathcal{C}_{X,P}$ preserving the
property of being closed.

######  Proposition 5.2.

For a given edge $X\in E(H^{\prime})$ with petal $P$, there exists a bijection
$\Psi:\mathcal{C}_{V^{\prime},M^{\prime}}\rightarrow\mathcal{C}_{X,P}$ given
by

$\displaystyle\Psi(I)=I\cap X$

such that $I$ is a closed interval in $V^{\prime}$ if and only if $\Psi(I)$ is
a closed interval in $X$.

###### Proof.

If $I\in\mathcal{C}_{V^{\prime},M^{\prime}}$ is such that $I\cap
M^{\prime}=\emptyset$, then either $I\subseteq K_{0}$ or $I\subseteq K_{1}$.
Since $X=K_{0}\cup P\cup K_{1}$ for some $P\in M^{\prime(r)}$, we obtain that
$\Psi(I)=I\cap X=I$. This shows that $\Psi$ is a bijection from the intervals
of $V^{\prime}$ disjoint of $M^{\prime}$ to the intervals of $X$ disjoint of
$P$.

Now suppose that $I\in\mathcal{C}_{V^{\prime},M^{\prime}}$ is such that
$M^{\prime}\subseteq I$. Then $I$ can be written as $I=K_{I}\cup M^{\prime}$
with $K_{I}\subseteq K_{0}\cup K_{1}$. Thus $\Psi(I)=I\cap X=K_{I}\cup P$.
Since $K_{I}\neq K_{I^{\prime}}$ for $I\neq I^{\prime}$, we obtain that $\Psi$
is an injection from the intervals of $V^{\prime}$ containing $M^{\prime}$ to
the intervals of $X$ containing $P$. To check surjectivity, just notice that
$K_{I}\cup P$ is an interval if and only if $K_{I}\cup M^{\prime}$ is an
interval.

It remains to prove that $I$ is closed if and only if $\Psi(I)$ is closed. We
split the proof into cases depending on the structure of $H^{\prime}$ given by
Lemma 5.1.

Case 1: $M^{\prime}$ is a closed interval in $V^{\prime}$.

Let $u=a(\min(M^{\prime}),\max(M^{\prime}))$ and $v=a(\min(P),\max(P))$ be the
common ancestors of $M^{\prime}$ and $P$, respectively. The following
observation will be useful in the paper.

######  Fact 5.3.

Let $W=V(p)$ be a closed interval in $V$. If $x$ and $y$ are two vertices such
that $x\in W$ and $y\notin W$, then $a(x,y)=a(y,p)$.

In particular, Fact 5.3 applied to $W=M^{\prime}$ says that an element
$y\notin M^{\prime}$ have the same common ancestor with any $x\in M^{\prime}$.
The proof of Case 1 is slightly different depending on the location of the
interval $I$ in $V^{\prime}$.

$x$$y$$p$$a(x,y)=a(y,p)$$W$ Figure 14. A picture of Fact 5.3

Case 1.1: $I\in\mathcal{C}_{V^{\prime},M^{\prime}}$ such that $I\cap
M^{\prime}=\emptyset$.

As seen before, we have that $\Psi(I)=I$. Thus, we just need to prove that $I$
is closed in $V^{\prime}$ if and only if $I$ is closed in $X$. Let
$z=a(\min(I),\max(I))$ be the common ancestor of the interval $I$. If $I$ is a
closed interval in $V^{\prime}$, then by condition (ii*) of Definition 2.2 we
have that $z$ is not an ancestor of any $x\in V^{\prime}\setminus I$. In
particular, $z$ is not an ancestor of any $x\in X\setminus I$. Therefore, $I$
is also closed in $X$.

Now suppose that $I$ is a closed interval in $X$. Hence, there is no vertex
$x\in X\setminus I$ such that $z$ is an ancestor of $x$. If there is a
descendant of $z$ in $V^{\prime}\setminus I$, then the descendant is in the
set $V^{\prime}\setminus X=M^{\prime}\setminus P$. Since $I\cap
M^{\prime}=\emptyset$, Fact 5.3, applied to the closed interval $M^{\prime}$,
implies that for every $y\in I^{\prime}$ and $x\in M^{\prime}$ we have
$a(x,y)=a(y,u)$. Thus, if $z$ is an ancestor of some $x\in M^{\prime}$, then
$z$ is an ancestor of $u$. This implies that $z$ is an ancestor for the entire
set $M^{\prime}$ and in particular of $P$, which contradicts the fact that $I$
is closed in $X$. Therefore, $I$ is a closed interval in $V^{\prime}$.

Case 1.2: $I\in\mathcal{C}_{V^{\prime},M^{\prime}}$ such that
$M^{\prime}\subseteq I$.

Suppose that $I=K_{I}\cup M^{\prime}$ is a interval in $V^{\prime}$ containing
$M^{\prime}$. We need to prove that $I=K_{I}\cup M^{\prime}$ is closed if and
only if $\Psi(I)=K_{I}\cup P$ is closed. If $K_{I}=\emptyset$, then
$I=M^{\prime}$ and $\Psi(I)=P$. By assumption $M^{\prime}$ is closed in
$V^{\prime}$. We need to prove that $P$ is closed in $X$. By condition (ii*)
of Definition 2.2, we have that $u$ is not an ancestor of any element in
$V^{\prime}\setminus M^{\prime}=X\setminus P$. Since $P\subseteq M^{\prime}$,
we obtain that $u$ is an ancestor of $v=a(\min(P),\max(P))$. Hence, $v$ is not
an ancestor of any element in $X\setminus P$ and consequently $P$ is a closed
interval in $X$.

Now suppose that $K_{I}\neq\emptyset$. We claim that $I$ and $\Psi(I)$ have
the same common ancestor. Indeed, let $x_{1}=\min(I)$, $y_{1}=\max(I)$,
$x_{2}=\min(\Psi(I))$ and $y_{2}=\min(\Psi(I))$. The assumption that
$K_{I}\neq\emptyset$ gives us that either $x_{1}<\min(M^{\prime})$ or
$y_{1}>\max(M^{\prime})$. Assume without loss of generality that
$y_{1}>\max(M^{\prime})$. Thus, $y_{1}\in K_{I}$ and we have that
$y_{1}=y_{2}=\max(K_{I})$. If $x_{1}\notin M^{\prime}$, then similarly we have
$x_{1}=x_{2}$ and consequently $a(x_{1},y_{1})=a(x_{2},y_{2})$. Now if
$x_{1}\in M^{\prime}$, then $x_{1}\notin K_{I}$. This implies that $x_{2}\in
P\subseteq M^{\prime}$. Since both $x_{1},x_{2}\in M^{\prime}$ and
$y_{1}=y_{2}\notin M^{\prime}$, by Fact 5.3 we obtain that
$a(x_{1},y_{1})=a(u,y_{1})=a(u,y_{2})=a(x_{2},y_{2})$. Hence, $I=K_{I}\cup
M^{\prime}$ and $\Psi(I)=K_{I}\cup P$ have the same common ancestor.

Let $z=a(x_{1},y_{1})=a(x_{2},y_{2})$ be the common ancestor of both
intervals. Since $V^{\prime}\setminus I=X\setminus\Psi(I)=K\setminus K_{I}$,
we know that $z$ has a descendant outside $I$ in $V^{\prime}$ if and only if
$z$ has a descendant outside $\Psi(I)$ in $X$. Thus $I$ is closed in
$V^{\prime}$ if and only if $\Psi(I)$ is closed in $X$.

Case 2: $M^{\prime}\subseteq Q$ for some maximal comb $Q=A^{Q}\cup B^{Q}$ in
$V^{\prime}$.

We may assume without loss of generality that $Q$ is a maximal left comb. Let
$K_{0}^{Q}=K_{0}\cap Q$ and $K_{1}^{Q}=K_{1}\cap Q$. Clearly $Q=K_{0}^{Q}\cup
M^{\prime}\cup K_{1}^{Q}$ with $K_{0}^{Q}<M^{\prime}<K_{1}^{Q}$. Moreover,
$Q=A^{Q}\cup B^{Q}$ with $A^{Q}<B^{Q}$ and $M^{\prime}\subseteq B^{Q}$. Thus,
$A^{Q}\subseteq K_{0}^{Q}$ and by condition (a3*) of Definition 2.4, we obtain
that $K_{0}^{Q}$ is closed in $V^{\prime}$. As in the first case, we split
into two cases depending on the type of the interval.

Case 2.1: $I\in\mathcal{C}_{V^{\prime},M^{\prime}}$ such that $I\cap
M^{\prime}=\emptyset$.

If $I$ is a closed interval in $V^{\prime}$, then by the same argument as in
Case 1.1 we have that $I$ is closed in $X$. Suppose now that $I$ is a closed
interval in $X$. Let $z=a(\min(I),\max(I))$ be the common ancestor of $I$. We
claim that $V^{\prime}(z)\cap M^{\prime}=\emptyset$. Applying Proposition 2.3
to the closed interval $V^{\prime}(z)$ and maximal comb $Q$ gives us that
either $V^{\prime}(z)\cap Q=\emptyset$, $V^{\prime}(z)\subseteq Q$ or
$Q\subseteq V^{\prime}(z)$. If $V^{\prime}(z)\cap Q=\emptyset$, then we
immediately obtain that $V^{\prime}(z)\cap M^{\prime}=\emptyset$, since
$M^{\prime}\subseteq Q$. Now suppose that $V^{\prime}(z)\subseteq Q$. Then, by
Proposition 2.7, we have that $V^{\prime}(z)=K^{0}\cup M^{\prime\prime}$ for
some (maybe empty) $M^{\prime\prime}\subseteq M^{\prime}$. In particular,
together with the fact that $I\cap M^{\prime}=\emptyset$ and $I\subseteq
V^{\prime}(z)$, this implies that $I\subseteq K^{0}$. Since $K_{0}^{Q}$ is
closed in $V^{\prime}$, we have that the common ancestor
$a(\min(K_{0}^{Q}),\max(K_{0}^{Q}))$ is an ancestor of the entire $I$ and
therefore of $z$. Hence, $V^{\prime}(z)\subseteq K_{0}^{Q}$, which implies
that $V^{\prime}(z)\cap M^{\prime}=\emptyset$. Finally, if $Q\subseteq
V^{\prime}(z)$, then $M^{\prime}\subseteq V^{\prime}(z)$ and consequently
$P\subseteq X(z)$. This implies that $X(z)\neq I$, which contradicts $I$ being
closed in $X$. Thus, we conclude the proof that $V^{\prime}(z)\cap
M^{\prime}=\emptyset$. The fact that $I$ is closed in $V^{\prime}$ now follows
because $V^{\prime}(z)=X(z)=I$.

$K_{0}^{Q}$$M^{\prime}$$K_{1}^{Q}$$K_{0}$$K_{1}$ Figure 15. Maximal comb $Q$
and sets $K_{0}^{Q}$ and $K_{1}^{Q}$.

Case 2.2: $I\in\mathcal{C}_{V^{\prime},M^{\prime}}$ such that
$M^{\prime}\subseteq I$.

Let $I=K_{0}^{I}\cup M^{\prime}\cup K_{1}^{I}$ be an interval in $V^{\prime}$
containing $M^{\prime}$ with $K_{0}^{I}\subseteq K_{0}$ and
$K_{1}^{I}\subseteq K_{1}$. Our goal is to prove that $I=K_{0}^{I}\cup
M^{\prime}\cup K_{1}^{I}$ is closed in $V^{\prime}$ if and only if
$\Psi(I)=K_{0}^{I}\cup P\cup K_{1}^{I}$ is closed in $X$. Let $x_{1}=\min(I)$,
$y_{1}=\max(I)$, $x_{2}=\min(\Psi(I))$ and $y_{2}=\max(\Psi(I))$. Since
$K_{0}^{Q}\cup M^{\prime}$ is closed, by the same argument of Case 1.2 (by
considering $K_{0}^{Q}\cup M^{\prime}$ instead of $M^{\prime}$), we can show
that if $x_{1}<\min(K_{0}^{Q})$ or $y_{1}>\max(M^{\prime})$, then
$a(x_{1},y_{1})=a(x_{2},y_{2})$ and consequently $I$ is closed in $V^{\prime}$
if and only if $\Psi(I)$ is closed in $X$.

Now suppose that $x_{1}=\min(K_{0}^{Q})$ and $y_{1}=\max(M^{\prime})$. Then
$x_{1}=x_{2}$ and $y_{2}=\max(P)$. In this case, $K_{0}^{I}=K_{0}^{Q}$ and
$K_{1}^{I}=\emptyset$, which implies that $I=K_{0}^{Q}\cup M^{\prime}$ and
$\Psi(I)=K_{0}^{Q}\cup P$. We claim that both intervals $I$ and $\Psi(I)$ are
closed intervals in their respective ground sets. Write
$M^{\prime}=\\{z_{1},\ldots,z_{m^{\prime}}\\}$ and let $w=a(x_{2},y_{2})$ be
the common ancestor of $\Psi(I)$. By the assumption, the interval
$I=K_{0}^{Q}\cup M^{\prime}$ is a left comb with $M^{\prime}$ on its “teeth”.
Thus, by condition (a3*) of Definition 2.4, the interval
$K_{0}^{Q}\cup\\{z_{1},\ldots,z_{i}\\}$ is closed in $V^{\prime}$ for every
$1\leqslant i\leqslant m^{\prime}$. This implies that $I=K_{0}^{Q}\cup
M^{\prime}$ is closed in $V^{\prime}$. Moreover, since
$y_{2}=\max(P)\leqslant\max(M^{\prime})=z_{m^{\prime}}$ we have that
$V^{\prime}(w)$ is a closed interval in $V^{\prime}$. Because $K_{0}^{Q}\cup
P=V^{\prime}(w)\cap X$, we obtain that $\Psi(I)=K_{0}^{Q}\cup P$ is a closed
interval in $X$. Therefore, both intervals are closed in their respective
ground sets.

Finally, consider the case that
$\min(K_{0}^{Q})<x_{1}\leqslant\min(M^{\prime})$ and $y_{1}=\max(M^{\prime})$.
Then $x_{2}=x_{1}$ and $y_{2}=\max(P)$. Hence, in this case
$K_{0}^{I}\subseteq K_{0}^{Q}$ and $K_{1}^{I}=\emptyset$, which implies that
$I=K_{0}^{I}\cup M^{\prime}$ and $\Psi(I)=K_{0}^{I}\cup P$. We claim that both
intervals $I$ and $\Psi(I)$ are not closed in their respective ground sets.
Since $K_{0}^{Q}$ is closed and $y_{1}\notin K_{0}^{Q}$, by Fact 5.3 we have
that $a(x,y_{1})=a(x^{\prime},y_{1})$ for every $x,x^{\prime}\in K_{0}^{Q}$.
This implies that $a(x_{1},y_{1})=a(\min(K_{0}^{Q}),y_{1})$, i.e.,
$K_{0}^{Q}\cup M^{\prime}$ and $K_{0}^{I}\cup M^{\prime}$ have the same common
ancestor. Let $r=a(x_{1},y_{1})$. As noted in the last paragraph,
$K_{0}^{Q}\cup M^{\prime}$ is closed in $V^{\prime}$ and hence $K_{0}^{Q}\cup
M^{\prime}=V^{\prime}(r)$. Since $K_{0}^{Q}\neq K_{0}^{I}$, we have that
$I=K_{0}^{I}\cup M^{\prime}\neq V^{\prime}(r)$ and by condition (ii) of
Definition 2.2 we conclude that $I$ is not closed in $V^{\prime}$. The proof
for $\Psi(I)$ is analogous. ∎

The next result shows that we can always find in an edge the location of the
maximal comb with coloring data containing $a(P)$. This will be extremely
important, since the comb will be the only maximal comb such that coloring
data changes while we run through different edges of $H^{\prime}$.

######  Proposition 5.4.

There exists a unique interval $J\subseteq[k+r]$ such that for every edge
$X=K_{0}\cup P\cup K_{1}=\\{x_{1},\ldots,x_{k+r}\\}$ in $H^{\prime}$, the
interval $X_{J}=\\{x_{j}\\}_{j\in J}$ is a maximal comb of type depending only
on $H^{\prime}$ with

$\displaystyle a(P)\subseteq F(X_{J}).$

Moreover, writing $X_{J}=A^{X_{J}}\cup B^{X_{J}}$ we have one of the
following:

  1. (1)

If $H^{\prime}$ satisfies statement $(1)$ of Lemma 5.1, then
$A^{X_{J}}\subseteq P$ and $X_{J}$ is the smallest maximal comb containing $P$
with non-empty coloring data.

  2. (2)

If $H^{\prime}$ satisfies statement $(2)$ of Lemma 5.1, then $X_{J}=I\cap X$,
where $I=A\cup B$ is the maximal comb in $V^{\prime}$ such that
$M^{\prime}\subseteq V^{\prime}$, and $X_{J}$ satisfies $P\subseteq
B^{X_{J}}$.

###### Proof.

The idea of the proof is to identify certain maximal combs in $V^{\prime}$
with maximal combs in an edge $X$. Because the structure of those maximal
combs in $V^{\prime}$ only depends on $H^{\prime}$, we will obtain the same
for the corresponding combs in $X$. Proposition 5.2 will be useful here, since
by condition (a3*) and (b3*) of Definition 2.4 a comb can be defined by
looking at certain closed subintervals. The proof is split into cases
depending on the structure of the tree $T_{V^{\prime}}$

Case 1: $M^{\prime}$ is a closed interval in $V^{\prime}$.

We will construct a maximal comb in $X$ by looking at a maximal comb in
$V^{\prime}$ containing $M^{\prime}$. Write
$K_{0}=\\{x_{1},\ldots,x_{k_{0}}\\}$,
$M^{\prime}=\\{y_{1},\ldots,y_{m^{\prime}}\\}$ and
$K_{1}=\\{z_{1},\ldots,z_{k_{1}}\\}$. There are two possibilities here:

Case 1.1: Either $M^{\prime}\cup\\{z_{1}\\}$ is a closed interval in
$V^{\prime}$ or $M^{\prime}\cup\\{x_{k_{0}}\\}$ is a closed interval in
$V^{\prime}$.

Suppose without loss of generality that $M^{\prime}\cup\\{z_{1}\\}$ is closed
in $V^{\prime}$. In this case $M^{\prime}\cup\\{z_{1}\\}$ is a left comb. Let
$M^{\prime}\cup\\{z_{1},\ldots,z_{t}\\}$ be the maximal left comb obtained by
extending $M^{\prime}\cup\\{z_{1}\\}$. We will assume during the entire proof
that $t<k_{1}$. For $t=k_{1}$, the same proof work by removing any claims and
sets involving $z_{t+1}$. By condition (a3*) of Definition 2.4 and Definition
2.6, $M^{\prime}\cup\\{z_{1},\ldots,z_{t}\\}$ being a maximal left comb is the
same as saying that the intervals $M^{\prime}$ and
$M^{\prime}\cup\\{z_{1},\ldots,z_{i}\\}$ are closed for every $1\leqslant
i\leqslant t$, but the interval $M^{\prime}\cup\\{z_{1},\ldots,z_{t+1}\\}$ is
not closed.

Set $J=\\{k_{0}+1,\ldots,k_{0}+r+t\\}$. Let $X$ be an edge of $H^{\prime}$
with petal $P$. We claim that $X_{J}$ is a maximal left comb in $X$ with
$A^{X_{J}}\subseteq P$. To see that consider the intervals

$\displaystyle J_{i}=\\{k_{0}+1,\ldots,k+r+i\\},\quad 0\leqslant i\leqslant
t+1.$

In particular $J_{t}=J$. Note that $X_{J_{0}}=M^{\prime}\cap X=P$ and
$X_{J_{i}}=(M^{\prime}\cap\\{z_{1},\ldots,z_{i}\\})\cap X$ for $1\leqslant
i\leqslant t+1$. Thus, by applying Proposition 5.2 with $I=M^{\prime}$ and
$I=M^{\prime}\cup\\{z_{1},\ldots,z_{i}\\}$, we obtain that $X_{J_{i}}$ is
closed in $X$ for $0\leqslant i\leqslant t$ and $X_{J_{t+1}}$ is not closed in
$X$. Hence, by condition (a3*) of Definition 2.4 and Definition 2.6, we have
that $X_{J}=X_{J_{t}}$ is a maximal left comb. Since $P=X_{J_{0}}\subseteq
X_{J_{1}}\subseteq\ldots\subseteq X_{J_{t}}=X_{J}$ are all closed intervals,
we have that $A^{X_{J}}\subseteq P$. Thus, $|A^{X_{J}}|\leqslant|P|=r$ and we
have that either $X_{J}$ is a maximal comb of type 3 or type 4 depending on
the size of $|X_{J}|=r+t$. Because $t$ is a parameter that depends on the size
of the maximal comb in $V^{\prime}$, i.e., on the structure of $H^{\prime}$,
we conclude that the type of $X_{J}$ is independent of our choice of edge $X$.

It remains to show that $a(P)\subseteq F(X_{J})$ and $X_{J}$ is the smallest
maximal comb containing $P$ with non-empty data coloring. For the first, note
that $F(X_{J})=a(X_{J})$ because $X_{J}$ is of type $3$ or $4$. Thus,
$a(P)\subseteq a(X_{J})=F(X_{J})$. For the latter, note that the only
potential maximal comb smaller than $X_{J}$ containing $P$ is $P$ itself.
However, if $P$ is a maximal comb, then it is a comb of type $2$ and therefore
$F(P)=\emptyset$. Hence, $X_{J}$ is the smallest maximal comb containing $P$
with non-empty coloring data.

Case 1.2: Both $M^{\prime}\cup\\{z_{1}\\}$ and $M^{\prime}\cup\\{x_{k_{0}}\\}$
are not closed in $V^{\prime}$.

By Definition 2.6, $M^{\prime}$ is a maximal comb. Set
$J=\\{k_{0}+1,\ldots,k_{0}+r\\}$. Note that $X_{J}=P$. By Proposition 5.2, the
set $P=M^{\prime}\cap X$ is closed in $X$ and
$P\cup\\{z_{1}\\}=(M^{\prime}\cup\\{z_{1}\\})\cap X$ and
$P\cup\\{x_{k_{0}}\\}=(M^{\prime}\cup\\{x_{k_{0}}\\})\cap X$ are not closed in
$X$. Thus, $P$ is a maximal comb in $X$. It is clear that $A^{X_{J}}\subseteq
X_{J}=P$. Since $|P|=r$ and $P\cup\\{z_{1}\\}$, $P\cup\\{x_{k_{0}}\\}$ are not
closed, we have that $X_{J}=P$ is of type $1$. Therefore, the type of $X_{J}$
does not depend on $X$. Moreover, the fact that $X_{J}$ is of type 1 gives us
that $a(P)=a(X_{J})=F(X_{J})$. The minimality of $X_{J}$ is immediate from the
fact that all combs with non-empty data has size at least $r$.

Case 2: $M^{\prime}\subseteq B$ for a maximal comb $I=A\cup B$ in
$V^{\prime}$.

Suppose without loss of generality that $I=A\cup B$ is a maximal left comb.
Let $A=\\{x_{k_{0}-p-\ell+1},\ldots,x_{k_{0}-p}\\}$, $B\cap
K_{0}=\\{x_{k_{0}-p+1},\ldots,x_{k_{0}}\\}$ and $B\cap
K_{1}=\\{z_{1},\ldots,z_{t}\\}$. Set
$J=\\{k_{0}-p-\ell+1,\ldots,k_{0}+r+t\\}$. Let $X$ be an edge of $H^{\prime}$
with petal $P$. Clearly, $X_{J}=I\cap X$. We claim that $X_{J}$ is a maximal
left comb with $P\subseteq B^{X_{J}}$. By Definition 2.4 and 2.6 we have that
$A$ is a closed interval in $V^{\prime}$, $A\setminus\\{x_{k_{0}-p}\\}$ and
$I\cup\\{z_{t+1}\\}$ are not closed in $V^{\prime}$ and

$\displaystyle\delta(x_{k_{0}-p},x_{k_{0}-p+1})$
$\displaystyle>\ldots>\delta(x_{k_{0}-1},x_{k_{0}})>\delta(x_{k_{0}},y_{1})>\delta(y_{1},y_{2})>\ldots>\delta(y_{m^{\prime}-1},y_{m^{\prime}})$
$\displaystyle>\delta(y_{m^{\prime}},z_{1})>\delta(z_{1},z_{2})>\ldots>\delta(z_{t-1},z_{t}).$

$A$$B\cap K_{0}$$P$$B\cap K_{1}$$K_{0}$$K_{1}$ Figure 16. Case $2$ of
Proposition 5.4

Let $P=\\{y_{i_{1}},\ldots,y_{i_{r}}\\}$. By Proposition 5.2, the set $A=A\cap
X$ is closed in $X$ and the sets
$A\setminus\\{x_{k_{0}-p}\\}=(A\setminus\\{x_{k_{0}-p}\\})\cap X$ and
$X_{J}\cup\\{z_{t_{1}}\\}=(I\cup\\{z_{t+1}\\})\cap X$ are not closed in $X$.
Moreover, since $P\subseteq M^{\prime}$, we have that

$\displaystyle\delta(x_{k_{0}-p},x_{k_{0}-p+1})$
$\displaystyle>\ldots>\delta(x_{k_{0}-1},x_{k_{0}})>\delta(x_{k_{0}},y_{i_{1}})>\delta(y_{i_{1}},y_{i_{2}})>\ldots>\delta(y_{i_{r-1}},y_{i_{r}})$
$\displaystyle>\delta(y_{i_{r}},z_{1})>\delta(z_{1},z_{2})>\ldots>\delta(z_{t-1},z_{t}).$

Thus, by Definition 2.4 and Definition 2.6, the interval $X_{J}$ is a maximal
left comb in $X$ with $A^{X_{J}}=A$ and $|B^{X_{J}}|=k+r-\ell$. Since
$A\subseteq K_{0}$, we obtain that $P\subseteq B^{X_{J}}$. Note that to
determine the type of $X_{J}$ we need to know the sizes of $X_{J}$,
$A^{X_{J}}$ and $B^{X_{J}}$. None of this parameters depends on the choice of
$X$. Hence, the type of $X_{J}$ is independent of $X$. Finally, because
$|B^{X_{J}}|\geqslant|P|\geqslant r$, the comb $X_{J}$ is of type $3$, $4$ or
$5$. If it is of type $3$ or $4$, then $a(P)\subseteq a(X_{J})=F(X_{J})$. If
it is of type $5$, then $a(P)\subseteq a(\max(A^{X_{J}})\cup
B^{X_{J}})=F(X_{J})$. ∎

To finish the section we prove that the maximal comb determined by the set $J$
is the comb that essentially determines the color of the entire edge.

######  Proposition 5.5.

Let $X=\\{x_{1},\ldots,x_{k+r}\\}$,
$X^{\prime}=\\{x^{\prime}_{1},\ldots,x^{\prime}_{k+r}\\}$ be two edges in
$H^{\prime}$ and let $X_{J}=\\{x_{j}\\}_{j\in J}$,
$X^{\prime}_{J}=\\{x^{\prime}_{j}\\}_{j\in J}$. If $\chi(X)=\chi(X^{\prime})$,
then $\chi_{0}(X_{J})=\chi_{0}(X^{\prime}_{J})$.

###### Proof.

Let $P,P^{\prime}\subseteq M^{\prime}$ be the petals of $X$ and $X^{\prime}$,
respectively. By definition, $\chi(X)=\chi(X^{\prime})$ implies that

$\displaystyle\sum_{I\in\mathcal{I}_{X}}\chi_{0}(I)=\sum_{I^{\prime}\in\mathcal{I}_{X^{\prime}}}\chi_{0}(I^{\prime})\pmod{2}.$

By the definition of coloring data, if $F(I)=\emptyset$, then $\chi_{0}(I)=0$.
Thus, we may rewrite the equality above as

$\displaystyle\sum_{\begin{subarray}{c}I\in\mathcal{I}_{X}\\\
F(I)\neq\emptyset\end{subarray}}\chi_{0}(I)=\sum_{\begin{subarray}{c}I^{\prime}\in\mathcal{I}_{X^{\prime}}\\\
F(I^{\prime})\neq\emptyset\end{subarray}}\chi_{0}(I)\pmod{2}.$ (3)

We claim that if $I=A\cup B$ is a maximal comb of $X$ with
$F(I)\neq\emptyset$, then either $I\cap P=\emptyset$ or $P\subseteq I$. Note
that, in the coloring defined in Subsection 3.3, whenever $F(I)=\emptyset$, we
have that $|I|\geqslant|P|=r$. By Lemma 5.1, the daisy $H^{\prime}$ satisfies
one of the following conditions: Either $M^{\prime}$ is a closed interval in
$V^{\prime}:=V(H^{\prime})$ or there exists a maximal comb $Q=A^{Q}\cup B^{Q}$
such that $M^{\prime}\subseteq B^{Q}$. If $M^{\prime}$ is closed in
$V^{\prime}$, then by Proposition 5.2 the petal $P=M^{\prime}\cap X$ is a
closed interval in $X$. Thus, Proposition 2.3 applied to the closed intervals
$I$ and $P$ gives the desired result that either $I\cap P=\emptyset$ or
$P\subseteq I$. Now suppose that we are in Condition (2) of Lemma 5.1. By
Proposition 5.4, we have that $P\subseteq B^{X_{J}}$, where $B^{X_{J}}$ is the
“teeth” part of the comb $X_{J}=A^{X_{J}}\cup B^{X_{J}}$. Thus, Proposition
2.7 applied to the maximal combs $I$ and $X_{J}$ implies that $I\cap
X_{J}=\emptyset$, $I\subseteq A^{X_{J}}$ or $X_{J}\subseteq A\subseteq I$. In
the first two cases we obtain $I\cap P=\emptyset$, while in the latter we have
$P\subseteq I$.

The idea of the proof of Proposition 5.5 is to show that there exists a
bijection between $\\{I\in\mathcal{I}_{X}:\>F(I)\neq\emptyset\\}$ and
$\\{I^{\prime}\in\mathcal{I}_{X^{\prime}}:\>F(I^{\prime})\neq\emptyset\\}$
such that $X_{J}$ is sent to $X^{\prime}_{J}$ and every $I\neq X_{J}$ is sent
to an $I^{\prime}\neq X^{\prime}_{J}$ with $\chi_{0}(I)=\chi_{0}(I^{\prime})$.
Hence, after some cancellation, we obtain from equation (3) that
$\chi_{0}(X_{J})=\chi_{0}(X^{\prime}_{J})$. Based on the last paragraph, we
construct such a bijection by splitting
$\\{I\in\mathcal{I}_{X}:\>F(I)\neq\emptyset\\}$ into two parts:

Case 1: $I\in\mathcal{I}_{X}$ is a maximal comb of $X$ with
$F(I)\neq\emptyset$ and $I\cap P=\emptyset$.

We claim that $I\in\mathcal{I}_{X^{\prime}}$ is a maximal comb in $X^{\prime}$
of the same type and consequently $\chi_{0}(X)$ is the same in $X$ and
$X^{\prime}$. Assume without loss of generality that $I\subseteq K_{0}$. Let
$x$ be the element preceding $\min(I)$ in $X$ (In the case that such $x$ does
not exists, we simply take $x=\min(I)$). Let $y$ be the element after
$\max(I)$ in $X$. Similarly, define $x^{\prime}$ as the element before
$\min(I)$ in $X^{\prime}$ and $y^{\prime}$ as the element after $\max(I)$ in
$X^{\prime}$. Since $I\subseteq K_{0}$, clearly $x=x^{\prime}$. However, $y$
and $y^{\prime}$ are not necessarily the same. By conditions (a3*) and (b3*)
of Definition 2.4 and Definition 2.6, to prove that
$I\in\mathcal{I}_{X^{\prime}}$ is enough to check that $I\cup\\{x\\}$,
$L\subseteq I$, $I\cup\\{y\\}$ are closed intervals in $X$ if and only if
$I\cup\\{x^{\prime}\\}$, $L\subseteq I$ and $I\cup\\{y^{\prime}\\}$ are closed
intervals in $X^{\prime}$, respectively. Since the type of a comb only depends
on the size of its “handle” and ‘teeth”, by checking the properties above, we
also obtain that $I$ have the same type in $X$ and $X^{\prime}$.

For an interval $L\subseteq I$, by Proposition 5.2 we have that $L=L\cap X$ is
a closed interval in $X$ if and only if it is a closed interval in
$V^{\prime}$. Another application of Proposition 5.2 gives us that $L=L\cap
X^{\prime}$ is a closed interval if it is closed in $V^{\prime}$. Hence, $L$
is closed in $X$ if and only if it is closed in $X^{\prime}$. Similarly, the
same argument works for $I\cup\\{x\\}$ and $I\cup\\{x^{\prime}\\}$, because
$x=x^{\prime}\notin M^{\prime}$. Moreover, if $y\in K_{0}$, then
$y^{\prime}=y\notin M^{\prime}$ and we also obtain that $I\cup\\{y\\}$ is
closed in $X$ if and only if $I\cup\\{y^{\prime}\\}$ is closed in
$X^{\prime}$. Hence, the only case remaining is when $y\notin K_{0}$, i,e,
$y=\min(P)$ and $y^{\prime}=\min(P^{\prime})$.

We split the argument into two cases depending on the structure given by Lemma
5.1. Suppose that $M^{\prime}$ is closed in $V^{\prime}$ and let
$u=a(\min(M^{\prime}),\max(M^{\prime}))$ be the common ancestor of
$M^{\prime}$. By Fact 5.3, we have that $a(z,y)=a(z,y^{\prime})=a(x,u)$ for
every $z\in I$. Therefore, the entire set $M^{\prime}$ is descendant of the
common ancestors of $I\cup\\{y\\}$ and $I\cup\\{y^{\prime}\\}$, which by
condition (ii*) of Definition 2.2 implies that both sets are not closed. Now
suppose that $M^{\prime}\subseteq B^{Q}$ for some maximal comb $Q=A^{Q}\cup
B^{Q}$. Since $I$ is a closed interval in $X$, then by Proposition 5.2 it is a
closed interval in $V^{\prime}$. Thus, by Proposition 2.3, applied to $I$ and
the maximal comb $Q$, one of the following three possibilities holds: $I\cap
Q=\emptyset$, $I\subseteq Q$ or $Q\subseteq I$. Clearly, the last possibility
cannot hold, since $P\subseteq Q$ and $I\cap P=\emptyset$. Suppose that $I\cap
Q=\emptyset$. By Proposition 5.2, the interval $Q\cap X$ is a closed interval
in $X$. Since $(I\cup\\{y\\})\cap(Q\cap X)=\\{y\\}\neq\emptyset$ and
$\\{y\\}\neq Q\cap X$, we obtain by Proposition 2.3 that $I\cup\\{y\\}$ is not
closed in $X$. Similarly, $I\cup\\{y^{\prime}\\}$ is not closed in
$X^{\prime}$.

Now we handle with the case that $I\subseteq Q$. By Proposition 2.7, either
$I\subseteq A^{Q}$ or $I=A\cup B$ is a comb with $A=A^{Q}$ and $B\subseteq
B^{Q}$. Since $I\subseteq K_{0}$, we have that $Q$ is a maximal left comb. Let
$K_{0}^{Q}=K_{0}\cap Q$, $B^{Q}=\\{z_{1},\ldots,z_{b}\\}$ and let
$Q_{z_{i}}=A^{Q}\cup\\{z_{1},\ldots,z_{i}\\}$ be the subcomb of $Q$ ending in
$z_{i}$. By condition (a3*) of Definition 2.4, we have that $A^{Q}$ and
$Q_{z}$ are closed in $V^{\prime}$ for every $z\in B^{Q}$. Moreover, note that
$\min(I)\in A^{Q}$. Let $v=a(\min(A^{Q}),\max(A^{Q})$ and $w=a(\min(I),y)$ be
the common ancestor of $A^{Q}$ and $I\cup\\{y\\}$, respectively. By Fact 5.3
applied to $A^{Q}$, we have that $a(\min(I),x)=a(v,x)=a(\min(A^{Q}),x)$ for
every $x\in M^{\prime}$. Thus, $X(w)=V^{\prime}(w)\cap X=Q_{y}\cap
X=K_{0}^{Q}\cup\\{y\\}$, which implies that $I\cup\\{y\\}$ is a closed
interval in $X$ if and only if $I=K_{0}^{Q}$. Similarly,
$I\cup\\{y^{\prime}\\}$ is a closed interval in $X^{\prime}$ if and only if
$I=K_{0}^{Q}$. Hence, $I\cup\\{y\\}$ is closed in $X$ if and only if
$I\cup\\{y^{\prime}\\}$ is closed in $X^{\prime}$.

Case 2: $I\in\mathcal{I}_{X}$ is a maximal comb of $X$ with
$F(I)\neq\emptyset$, $P\subseteq I$ and $I\neq X_{J}$.

In this case, by Proposition 4.2 and Proposition 5.4, we have that $F(I)\cap
a(P)=\emptyset$ and consequently $F(I)\neq a(I)$. Thus, by our coloring, we
obtain that $I$ is of type $5$, i.e., $I=A\cup B$ is a maximal left/right comb
with $|A|>r$ and $|B|\geqslant r$. We may assume that $I$ is a maximal left
comb. Hence, $F(I)=a(\\{\max(A)\\}\cup B)$ and the fact that $F(I)\cap
a(P)=\emptyset$ implies that $P\subseteq A$. Write $A=K_{A}\cup P$ with
$K_{A}\subseteq K_{0}\cup K_{1}$. We claim that $I^{\prime}=K_{A}\cup
P^{\prime}\cup B$ is a maximal comb of type $5$ with set of “teeth”
$B^{\prime}=B$ and “handle” $A^{\prime}=K_{A}\cup P^{\prime}$.

Write $B=\\{y_{1},\ldots,y_{t}\\}$. Let $x=\max(A)$,
$x^{\prime}=\max(A^{\prime})$ and let $z$ be the element coming after $B$ in
$V^{\prime}$ (In case that such element does note exist, we take $z=\max(B)$).
By condition (a3*) of Definition 2.4 and Definition 2.6 to prove that
$I=A^{\prime}\cup B^{\prime}$ is a maximal comb of type $5$ with
$A^{\prime}=K_{A}\cup P$ and $B^{\prime}=B$ it is enough to prove that
$A^{\prime}$ and $A^{\prime}\cup\\{y_{1},\ldots,y_{i}\\}$ are closed in
$X^{\prime}$ for every $1\leqslant i\leqslant t$,
$A^{\prime}\setminus\\{x^{\prime}\\}$ is not closed in $X^{\prime}$ and
$A^{\prime}\cup\\{y_{1},\ldots,y_{t},z\\}$ is closed if and only if
$A\cup\\{y_{1},\ldots,y_{t},z\\}$ is closed in $X$. Applying Proposition 5.2
with $X$ and $V^{\prime}$ and then $V^{\prime}$ and $X^{\prime}$ gives us that
$A$, $A\cup\\{y_{1},\ldots,y_{i}\\}$ and $A\cup\\{y_{1},\ldots,y_{t},z\\}$ are
closed in $X$ if and only if $A^{\prime}$,
$A^{\prime}\cup\\{y_{1},\ldots,y_{i}\\}$ and
$A^{\prime}\cup\\{y_{1},\ldots,y_{t},z\\}$ are closed in $X^{\prime}$,
respectively. Since $I$ is a maximal comb in $X$, this implies that
$A^{\prime}$, $A^{\prime}\cup\\{y_{1},\ldots,y_{i}\\}$ are closed in
$X^{\prime}$ for $1\leqslant i\leqslant t$. If $x\notin P$, then
$x=x^{\prime}$ and by the same argument $A^{\prime}\setminus\\{x^{\prime}\\}$
is not closed in $X^{\prime}$.

It remains to deal with the case that $x\in P$, i.e., $x=\max(P)$ and
$x^{\prime}=\max(P^{\prime})$. The proof is split into two cases depending on
the structure of $H^{\prime}$ given by Lemma 5.1. If $M^{\prime}$ is a closed
interval in $V^{\prime}$, then by Proposition 5.2 the interval $P^{\prime}$ is
closed in $X^{\prime}$. The intersection $A^{\prime}\setminus\\{x^{\prime}\\}$
is proper since $|A^{\prime}|=|A|>r=|P^{\prime}|$ and $x^{\prime}\in
P^{\prime}$. Therefore, by Proposition 2.3, we have that
$A^{\prime}\setminus\\{x^{\prime}\\}$ is not closed in $X^{\prime}$.

Now suppose that $M^{\prime}\subseteq B^{Q}$ for some maximal comb
$Q=A^{Q}\cup B^{Q}$. By Proposition 5.4, the maximal combs $X_{J}$ and
$X^{\prime}_{J}$ satisfies $P\subseteq B^{X_{J}}$ and $P^{\prime}\subseteq
B^{X^{\prime}_{J}}$. Applying Proposition 2.7 to the maximal combs $I$ and
$X_{J}$ gives us that either $I\subseteq A^{X_{J}}$ or $X_{J}\subseteq A$.
Since $P\cap A^{X_{J}}=\emptyset$, it follows that $X_{J}\subseteq A$. Because
$x=\max(A)\in P$, we have that $\max(K_{A})<\min(P)$. This implies that
$X_{J}$ is a maximal left comb. Hence, by Proposition 5.4 both $Q$ and
$X^{\prime}_{J}$ are maximal left combs.

We claim that $A^{\prime}\setminus\\{x^{\prime}\\}\cap X^{\prime}_{J}$ is a
proper intersection. Since
$|X^{\prime}_{J}|=|X_{J}|\leqslant|A|=|A^{\prime}|$, by Proposition 2.3
applied to $A^{\prime}$ and $X^{\prime}_{J}$, we have that
$X^{\prime}_{J}\subseteq A^{\prime}$. Note that we already proved for
$1\leqslant i\leqslant t$ that $A^{\prime}$ and
$A^{\prime}\cup\\{y_{1},\ldots,y_{t}\\}$ are closed in $X^{\prime}$. Hence, by
the maximality of $X^{\prime}_{J}$ we have that $A^{\prime}\neq
X^{\prime}_{J}$ (otherwise we could extend to the left comb $X_{J}\cup B$).
Thus, $X^{\prime}_{J}$ is strictly contained in $A^{\prime}$, which implies
that $K_{A}\setminus X^{\prime}_{J}\neq\emptyset$. This concludes that
$A^{\prime}\setminus\\{x^{\prime}\\}\cap X^{\prime}_{J}$ is proper and by
Proposition 2.3 the interval $A\setminus\\{x\\}$ is not closed in
$X^{\prime}$.

Therefore, the interval $I^{\prime}=A^{\prime}\cup B^{\prime}$ is a maximal
left comb in $X^{\prime}$ of type $5$ with $A^{\prime}=K_{A}\cup P^{\prime}$
and $B^{\prime}=B$. It is not difficult to check that the correspondence
between $I$ and $I^{\prime}$ is a bijection. Moreover, since $A=K_{A}\cup P$
is closed in $X$, we obtain by Proposition 5.2 that $K_{A}\cup M^{\prime}$ is
closed in $V^{\prime}$. It follows by Fact 5.3 that
$a(x,y_{1})=a(x^{\prime},y_{1})$ and consequently thar
$F(I)=a(B\cup\\{x\\})=a(B^{\prime}\cup\\{x^{\prime}\\})=F(I^{\prime})$. Hence,
by Proposition 4.1 we have $\chi_{0}(I)=\chi_{0}(I^{\prime})$. ∎

##  6\. Main proof

The proof of Theorem 1.3 follows by a simple induction of the following
stepping up theorem.

######  Theorem 6.1.

Let $m\geqslant 100kr^{2}$, $N=\min_{0\leqslant j\leqslant
k}\\{D_{r-1}^{\operatorname{smp}}(\frac{1}{5}k^{-1/2}m^{1/2},j)\\}$ be
integers and let $\\{\varphi_{i}\\}_{r-1\leqslant i\leqslant k+r-1}$ be a
family of colorings $\varphi_{i}:[N]^{(i)}\rightarrow\\{0,1\\}$ without a
monochromatic copy of a simple $(r-1,\frac{1}{5}k^{-1/2}m^{1/2},i-r+1)$-daisy.
Then, the coloring $\chi:[2^{N}]^{(k+r)}\rightarrow\\{0,1\\}$ described in
Subsection 3.3 does not contain a monochromatic simple $(r,m,k)$-daisy.

###### Proof.

Suppose by contradiction that there exists a monochromatic simple
$(r,m,k)$-daisy $H$ in $[2^{N}]^{(k+r)}$ with kernel $K=K_{0}\cup K_{1}$ of
size $k$, universe of petals $M$ of size $m$ and $K_{0}<M<K_{1}$. By Lemma
5.1, we obtain a monochromatic simple $(r,\frac{1}{2}k^{-1/2}m^{1/2},k)$-daisy
$H^{\prime}$ with same kernel and universe of petals
$M^{\prime}=\\{y_{1},\ldots,y_{m^{\prime}}\\}\subseteq M$ of size
$m^{\prime}=\frac{1}{2}k^{-1/2}m^{1/2}$ satisfying that either $M^{\prime}$ is
a closed interval in $V^{\prime}=V(H^{\prime})$ or $M^{\prime}$ is part of the
“teeth” of a maximal comb $I=A\cup B$, i.e., $M^{\prime}\subseteq B$.

Note that every edge $X\in H^{\prime}$ can be written in the form $X=K_{0}\cup
P\cup K_{1}$ where $P\in(M^{\prime})^{(r)}$ is a petal of $H^{\prime}$. Since
$H^{\prime}$ is monochromatic, we have that

$\displaystyle\chi(X)=\sum_{I\subseteq\mathcal{I}_{X}}\chi_{0}(I)\pmod{2}$

is constant, for every $X\in H^{\prime}$. Thus, by Propositions 5.4 and 5.5,
there exists a unique interval $J\subseteq[k+r]$ such that for every $X\in
E(H^{\prime})$ the interval $X_{J}=\\{x_{j}\\}_{j\in J}$ is maximal comb with
color $\chi_{0}(X_{J})$ constant.

As in the proof give in Subsection 3.1, our goal is to use the fact that the
combs $X_{J}$ are monochromatic with respect to $\chi_{0}$ to find a large
$1$-comb. Let $t=|J|-r$ and let $G$ be the simple
$(r,\frac{1}{2}k^{-1/2}m^{1/2},t)$-daisy constructed by taking as edges the
combs $X_{J}$ for every edge $X\in H^{\prime}$. To be more precise, let
$K_{J}$ be the subset of $t$ vertices of $K_{0}\cup K_{1}$ in the interval
$J$. Note that every comb $X_{J}$ can be partitioned into $X_{J}=K_{J}\cup P$,
where $P\subseteq M^{\prime}$ is the petal of $X$. We define $G$ as the simple
$(r,\frac{1}{2}k^{-1/2}m^{1/2},t)$-daisy given by

$\displaystyle V(G)$ $\displaystyle=K_{J}\cup M^{\prime}$ $\displaystyle G$
$\displaystyle=\\{X_{J}:\>X\in H^{\prime}\\}$

As discussed in the last paragraph the $(t+r)$-graph $G$ is monochromatic
under the coloring $\chi_{0}$. The following lemma is a variant of Proposition
3.1 for simple daisies.

######  Proposition 6.2.

If $M^{\prime}$ is a closed interval in $V(H^{\prime})$ and $G$ is
monochromatic with respect to the coloring $\chi_{0}$, then there exists an
interval $M^{\prime\prime}\subseteq M^{\prime}$ of size
$|M^{\prime\prime}|\geqslant(|M^{\prime}|-r+6)/2$ such that $M^{\prime\prime}$
is a $1$-comb in $V^{\prime}$.

###### Proof.

By Proposition 5.4, all the edges $X_{J}$ of $G$ are combs of the same type.
Thus we may assume without loss of generality that $X_{J}$ is either a broken
comb or a $\ell$-left comb in $X$. Since $M^{\prime}$ is closed, by the same
proposition we obtain that $A^{X_{J}}\subseteq P$ and consequently
$K_{J}\subseteq B^{X_{J}}$ for every edge $X\in H^{\prime}$. Therefore, we
either have $K_{J}=\emptyset$ (and $X_{J}$ is a broken comb) or $P<K_{J}$ for
every $X$, which implies that $K_{J}\subseteq K_{1}$, i.e.,
$M^{\prime}<K_{J}$. Moreover, if $X_{J}$ is an $\ell$-left comb, then
$A^{X_{J}}\subseteq P$ implies that $\ell\leqslant r$. This implies that
$X_{J}$ is either of type $1$, $3$ or $4$.

We split the proof into two cases according to the size of $t=|K_{J}|$. Write
$M^{\prime}=\\{y_{1},\ldots,y_{m^{\prime}}\\}$,
$K_{J}=\\{y_{m^{\prime}+1},\ldots,y_{m^{\prime}+t}\\}$ (if
$K_{J}\neq\emptyset$) and $\delta_{i}^{G}=\delta(y_{i},y_{i+1})$ for
$1\leqslant i\leqslant m^{\prime}+t-1$.

Case 1: $0\leqslant t\leqslant r-2$.

Since $|X_{J}|=r+t\leqslant 2r-2$, we obtain that $X_{J}$ is either of type
$1$ or $3$. The proof follow the same lines of the proof of Proposition 3.1.
Write $P=\\{y_{i_{1}},\ldots,y_{i_{r}}\\}\subseteq M^{\prime}$ for indices
$1\leqslant i_{1}<\ldots<i_{r}\leqslant m^{\prime}$. Suppose without loss of
generality that $G$ is monochromatic of color $0$, i.e., $\chi_{0}(X_{J})=0$
for every $X_{J}\in G$. Thus, by the definition of $\chi_{0}$ for combs of
type $1$ and $3$, we do not have that
$\delta_{i_{r-3}}^{G}<\delta_{i_{r-2}}^{G}>\delta_{i_{r-1}}^{G}$. In
particular, because $X_{J}$ is arbitrary, this implies that there are no
indices $r-3\leqslant p<q<s\leqslant m^{\prime}-1$ such that
$\delta_{p}^{G}<\delta_{q}^{G}>\delta_{s}^{G}$. That is, the sequence
$\\{\delta_{i}^{G}\\}_{i=r-3}^{m^{\prime}-1}$ has no local maximum.

Now the same argument as in Proposition 3.1 gives that there exists an
interval $M^{\prime\prime}=\\{y_{p},\ldots,y_{q}\\}\subseteq M^{\prime}$ such
that $\\{\delta_{i}^{G}\\}_{i=p}^{q-1}$ is monotone and
$|M^{\prime\prime}|\geqslant(|M^{\prime}|-r+6)/2$. By the definition given in
Example 2.5, it follows that $M^{\prime\prime}$ is a $1$-comb.

Case 2: $t\geqslant r-1$.

In this case $X_{J}$ is a left comb of type 4 for every $X_{J}\in G$, since
$|X_{J}|=|P|+|K_{J}|=r+t\geqslant 2r-1$. Suppose without loss of generality
that $G$ is monochromatic of color $0$ and that
$\varphi_{t}(\\{\delta_{m^{\prime}}^{G},\ldots,\delta_{m^{\prime}+t-1}^{G}\\})=0$.
Let $u=a(\min(M^{\prime}),\max(M^{\prime}))$. Fact 5.3 applied to $M^{\prime}$
gives us that $\delta(z,y_{m^{\prime}+1})=\delta(u,y_{m^{\prime}+1})$ for
every $z\in M^{\prime}$. In particular, this implies that
$\delta(z,y_{m^{\prime}+1})=\delta_{m^{\prime}}^{G}$ for every $z\in
M^{\prime}$.

Write $P=\\{y_{i_{1}},\ldots,y_{i_{r}}\\}\subseteq M^{\prime}$ with
$1\leqslant i_{1}<\ldots<i_{r}\leqslant m^{\prime}$ and $X_{J}=P\cup
K_{J}=\\{y_{i_{1}},\ldots,y_{i_{r}},y_{m^{\prime}},\ldots,y_{m^{\prime}+t-1}\\}$.
Since $\chi_{0}(X_{J})=0$,
$\delta(y_{i_{j}},y_{m^{\prime}+1})=\delta_{m^{\prime}}^{G}$ for every
$1\leqslant j\leqslant r$ and
$\varphi_{t}(\\{\delta_{m^{\prime}}^{G},\ldots,\delta_{m^{\prime}+t-1}^{G}\\})+1=1$
we obtain by the definition of $\chi_{0}$ for combs of type $4$ that the
inequality $\delta_{i_{r-3}}^{G}<\delta_{i_{r-2}}^{G}>\delta_{i_{r-1}}^{G}$
cannot hold. Because $X_{J}$ is arbitrary, we have that there are no indices
$r-3\leqslant p<q<s\leqslant m^{\prime}-1$ such that
$\delta_{p}^{G}<\delta_{q}^{G}>\delta_{s}^{G}$. Hence, similarly as in Case
$1$ we find an interval $M^{\prime\prime}\subseteq M^{\prime}$ of size at
least $(|M^{\prime}|-r+6)/2$ such that $M^{\prime\prime}$ is a $1$-comb in
$V^{\prime}$. ∎

To finish the proof of Theorem 1.3 we are going to show now that if $G$ is
monochromatic with respect to $\chi_{0}$, then there exists a monochromatic
simple $(r-1,\frac{1}{5}k^{-1/2}m^{1/2},j)$-daisy in $\delta(G)\subseteq[N]$
with respect to some coloring $\varphi_{j+r-1}$. The proof is split into
several cases depending on the structure of $H^{\prime}$ given by Lemma 5.1
and on the possible types of $X_{J}$.

Case 1: $M^{\prime}$ is a closed interval in $V^{\prime}$.

As usual, we may assume that an edge of $G$ is either a broken comb or a left
comb. By Proposition 6.2, there exists an interval $M^{\prime\prime}\subseteq
M^{\prime}$ of size $h=(|M^{\prime}|-r+6)/2$ such that $M^{\prime\prime}$ is a
$1$-comb. Consider the coloring $\chi_{0}$ over the monochromatic subdaisy
$G^{\prime}:=G[K_{J}\cup M^{\prime\prime}]\subseteq G$. As in the proof of
Proposition 6.2, we have that either $X_{J}$ is a broken comb and
$t=|K_{J}|=0$ or $X_{J}$ is an $\ell$-left comb with $\ell\leqslant r$ and
$M^{\prime}<K_{J}$. Write $M^{\prime\prime}=\\{y_{i_{1}},\ldots,y_{i_{h}}\\}$
with $1\leqslant i_{1}<\ldots<i_{h}<m^{\prime}$,
$K_{J}=\\{y_{m^{\prime}+1},\ldots,y_{m^{\prime}+t}\\}$ (if
$K_{J}\neq\emptyset$) and $\delta_{i}^{G}=\delta(y_{i},y_{i+1})$.

$P$$\delta(P)$$\delta(M^{\prime\prime})$$K_{D}$$M^{\prime\prime}$$K_{J}$
Figure 17. Case 1 of Theorem 6.1.

Let $X_{J}=P\cup
K_{J}=\\{x_{1},\ldots,x_{r}\\}\cup\\{y_{m^{\prime}+1},\ldots,y_{m^{\prime}+t}\\}$
be an arbitrary edge from $G^{\prime}$ with
$P\subseteq(M^{\prime\prime})^{(r)}$. Note that since $M^{\prime\prime}$ is a
$1$-comb, then $\delta(x_{r-3},x_{r-2})$, $\delta(x_{r-2},x_{r-1})$,
$\delta(x_{r-1},x_{r})$ forms a monotone sequence. Moreover, as discussed in
Proposition 6.2, the comb $X_{J}$ is of type $1$, $3$ or $4$. Thus, by the
coloring defined in Subsection 3.3, we have
$\chi_{0}(X_{J})=\varphi_{r+t-1}(\delta(X_{J}))$, i.e., the color of $X_{J}$
is determined by its full projection on the the levels $[N]$.

Note that
$\delta(X_{J})=\\{\delta(x_{1},x_{2}),\ldots,\delta(x_{r-1},x_{r})\\}\cup\\{\delta_{m^{\prime}}^{G},\ldots,\delta_{m^{\prime}+t-1}^{G}\\}$.
Therefore the projection of all the edges of $X_{J}$ forms a simple
$(r-1,h-1,t)$-daisy $D\subseteq[N]$ with universe of petals
$\delta(M^{\prime\prime})$ an kernel
$K_{D}=\\{\delta_{m^{\prime}}^{G},\ldots,\delta_{m^{\prime}+t-1}^{G}\\}$
satisfying $K_{D}<\delta(M^{\prime\prime})$. By the fact that $G^{\prime}$ is
monochromatic with respect to $\chi_{0}$, we have that $D$ is a monochromatic
simple $(r-1,h-1,t)$-daisy with respect to the coloring $\varphi_{r+t-1}$.
This leads to a contradiction since
$h-1\geqslant(m^{\prime}-r+4)/2\geqslant\frac{1}{5}k^{-1/2}m^{1/2}$ for
$m\geqslant 100kr^{2}$ and $\varphi_{r+t-1}$ has no monochromatic simple
$(r-1,\frac{1}{5}k^{-1/2}m^{1/2},t)$-daisy.

Case 2: There exists a maximal comb $I=A\cup B$ in $V(H^{\prime})$ such that
$M^{\prime}\subseteq B$

We may assume without loss of generality that $I=A\cup B$ is a left comb.
Write $A=\\{y_{1},\ldots,y_{\ell}\\}$, $B_{0}=B\cap
K_{0}=\\{y_{\ell+1},\ldots,y_{\ell+p}\\}$,
$M^{\prime}=\\{y_{\ell+p+1},\ldots,y_{\ell+p+m^{\prime}}\\}$ and $B_{1}=B\cap
K_{1}=\\{y_{\ell+p+m^{\prime}+1},\ldots,y_{\ell+p+m^{\prime}+t}\\}$. By
Proposition 5.4, $V(G)=I$ and all the edges $X_{J}=A^{X_{J}}\cup B^{X_{J}}\in
G$ are maximal left comb of same type with $A^{X_{J}}=A$, $B^{X_{J}}=B_{0}\cup
P\cup B_{1}$ and $A<B_{0}<P<B_{1}$. In particular, this implies that
$|B^{X_{J}}|\geqslant r$ and $X_{J}$ is of type $3$, $4$ or $5$. We split the
cases depending on the type of $X_{J}$. Let
$\delta_{i}^{G}=\delta(y_{i},y_{i+1})$ for $1\leqslant
i\leqslant\ell+p+m^{\prime}+t-1$. For an arbitrary edge $X_{J}\in G$, write
$X_{J}=\\{x_{1},\ldots,x_{\ell+p+r+t}\\}$ with $x_{i}=y_{i}$ for $1\leqslant
i\leqslant\ell+p$, $P=\\{x_{\ell+p+1},\ldots,x_{\ell+p+r}\\}\subseteq
M^{\prime}$ and $x_{\ell+p+r+i}=y_{\ell+p+m^{\prime}+i}$ for $1\leqslant
i\leqslant t$ and let $\delta_{i}^{X_{J}}=\delta(x_{i},x_{i+1})$ for
$1\leqslant i\leqslant\ell+p+r+t-1$.

$A$$B_{0}$$M^{\prime}$$B_{1}$ Figure 18. Auxiliary tree of $G$ in Case $2$.

Case 2.1: $X_{J}$ is of type $3$.

Recall that if $X_{J}$ is of type $3$, then $|A^{X_{J}}|\leqslant r$ and
$r\leqslant|X_{J}|=|A^{X_{J}}|+|B^{X_{J}}|\leqslant 2r-2$. Because
$|B^{X_{J}}|\geqslant r$, we obtain that $|A^{X_{J}}|\leqslant r-2$. This
implies that $\\{x_{r-1},x_{r}\\}\subseteq B^{X_{J}}$ and consequently
$\delta_{r-3}^{X_{J}}>\delta_{r-2}^{X_{J}}>\delta_{r-1}^{X_{J}}$. Therefore,
by the fact that
$|\delta(X_{J})|\geqslant|\delta(\\{x_{\ell},\ldots,x_{\ell+p+r+t}\\})|=p+r+t\geqslant
r$, we obtain that $\chi_{0}(X_{J})=\varphi_{|\delta(X_{J})|}(\delta(X_{J}))$.

Note that

$\displaystyle\delta(X_{J})$
$\displaystyle=\\{\delta_{1}^{G},\ldots,\delta_{\ell+p-1}^{G}\\}\cup\\{\delta_{\ell+p}^{X_{J}},\ldots,\delta_{\ell+p+r-1}^{X_{J}}\\}\cup\\{\delta_{\ell+p+m^{\prime}}^{G},\ldots,\delta_{\ell+p+m^{\prime}+t-1}^{G}\\}$
$\displaystyle=\delta(A\cup
B_{0})\cup\\{\delta_{\ell+p}^{X_{J}},\ldots,\delta_{\ell+p+r-1}^{X_{J}}\\}\cup\delta(\\{y_{\ell+p+m^{\prime}}\\}\cup
B_{1}).$

Hence, the projection of the edges of $G$ is a simple
$(r,m^{\prime},|\delta(A\cup B_{0})|+t)$-daisy with kernel $\delta(A\cup
B_{0})\cup\delta(\\{y_{\ell+p+m^{\prime}}\\}\cup B_{1})$. Since $G$ is
monochromatic with respect to $\chi_{0}$, we obtain that
$\delta(G)\subseteq[N]$ is monochromatic with respect to the projection
coloring, which is a contradiction because any simple
$(r,m^{\prime},|\delta(A\cup B_{0})|+t)$-daisy contains a simple
$(r-1,m^{\prime}-1,|\delta(A\cup B_{0})|+t+1)$-subdaisy and
$m^{\prime}-1\geqslant\frac{1}{5}k^{-1/2}m^{1/2}$.

$A$$B_{0}$$M^{\prime}$$B_{1}$$P$$\delta(\\{y_{\ell+p+m^{\prime}}\\}\cup
B_{1})$$\delta(A\cup B_{0})$ Figure 19. Case $2.1$ of Theorem 6.1

Case 2.2: $X_{J}$ is of type $4$.

If $X_{J}$ is of type 4, then $|A^{X_{J}}|\leqslant r$ and
$|X_{J}|=|A^{X_{J}}|+|B^{X_{J}}|\geqslant 2r-1$. We split the proof into two
subcases depending on the sequence formed by
$\\{\delta_{r-3}^{X_{J}},\delta_{r-2}^{X_{J}},\delta_{r-1}^{X_{J}}\\}$:

Case 2.2.a: Either
$\delta_{r-3}^{X_{J}}>\delta_{r-2}^{X_{J}}<\delta_{r-1}^{X_{J}}$ or
$\delta_{r-3}^{X_{J}}<\delta_{r-2}^{X_{J}}>\delta_{r-1}^{X_{J}}$.

Suppose without loss of generality that
$\delta_{r-3}^{X_{J}}>\delta_{r-2}^{X_{J}}<\delta_{r-1}^{X_{J}}$. Hence, by
the coloring definition, we have
$\chi_{0}(X_{J})=\varphi_{\ell+p+t}(\\{\delta_{r}^{X_{J}},\ldots,\delta_{\ell+p+r+t-1}^{X_{J}}\\})$.
Thus, we just need to look at the projection
$\\{\delta_{r}^{X_{J}},\ldots,\delta_{\ell+p+r+t-1}^{X_{J}}\\}$ for every
$X_{J}\in G$. Note that
$\delta_{r-3}^{X_{J}}>\delta_{r-2}^{X_{J}}<\delta_{r-1}^{X_{J}}$ implies that
$|A^{X_{J}}|\geqslant r-1$. Indeed, by the same argument made in Case 2.1, if
$|A^{X_{J}}|\leqslant r-2$, then
$\delta_{r-3}^{X_{J}}>\delta_{r-2}^{X_{J}}>\delta_{r-1}^{X_{J}}$, which is a
contradiction. So, it follows that $r-1\leqslant|A^{X_{J}}|=\ell\leqslant r$.

$A$$r$$M^{\prime}$$B_{1}$$P$$\delta(M^{\prime})$$\\{\delta_{r+m^{\prime}-1}^{G},\ldots,\delta_{r+m^{\prime}+t-2}^{G}\\}$$\delta(P)$
Figure 20. Case $2.2$ of Theorem 6.1 when $|A|=r-1$.

Suppose that $|A^{X_{J}}|=r-1$ and $B_{0}=\emptyset$, i.e., $l=r-1$, $p=0$ and
$M^{\prime}=\\{y_{r},\ldots,y_{r+m^{\prime}}\\}$. Then the projection of the
relevant part of an edge $X_{J}$ can be written as

$\displaystyle\\{\delta_{r}^{X_{J}},\ldots,\delta_{\ell+p+r+t-1}^{X_{J}}\\}$
$\displaystyle=\\{\delta_{r}^{X_{J}}.\ldots,\delta_{2r-2}^{X_{J}}\\}\cup\\{\delta_{r+m^{\prime}-1}^{G},\ldots,\delta_{r+m^{\prime}+t-2}^{G}\\}$
$\displaystyle=\delta(P)\cup\\{\delta_{r+m^{\prime}-1}^{G},\ldots,\delta_{r+m^{\prime}+t-2}^{G}\\},$

since
$\delta_{2r-1+i}^{X_{J}}=\delta_{\ell+p+r+i}^{X_{J}}=\delta_{\ell+p+m^{\prime}+i}^{G}=\delta_{2r+m^{\prime}-1+i}^{G}$
for $0\leqslant i\leqslant t-1$. Therefore, the projection of the edges
$X_{J}$ is a simple $(r-1,m^{\prime}-1,t)$-daisy with kernel
$\\{\delta_{r+m^{\prime}-1}^{G},\ldots,\delta_{r+m^{\prime}+t-2}^{G}\\}$.
Because $G$ is monochromatic under $\chi_{0}$, the projection is also
monochromatic under $\varphi_{r+t-1}$, which is a contradiction.

Now suppose that $|A^{X_{J}}\cup B_{0}|=\ell+p\geqslant r$. The relevant
projection of $X_{J}$ in this case would be

$\displaystyle\\{\delta_{r}^{X_{J}},\ldots,\delta_{\ell+p+r+t-1}^{X_{J}}\\}=\\{\delta_{r}^{G},\ldots,\delta_{\ell+p-1}^{G}\\}$
$\displaystyle\cup\\{\delta_{\ell+p}^{X_{J}},\ldots,\delta_{\ell+p+r-1}^{X_{J}}\\}$
$\displaystyle\cup\\{\delta_{\ell+p+m^{\prime}}^{G},\ldots,\delta_{\ell+p+r+m^{\prime}-1}^{G}\\},$

where the set $\\{\delta_{r}^{G},\ldots,\delta_{\ell+p-1}^{G}\\}$ is empty for
$\ell+p=r$. Since
$\\{\delta_{\ell+p}^{X_{J}},\ldots,\delta_{\ell+p+r-1}^{X_{J}}\\}=\delta(\\{y_{\ell+p}\\}\cup
P)$, we obtain that the projection of all edges $X_{J}$ is a simple
$(r,m^{\prime},\ell+p+t-r)$-daisy with kernel
$\\{\delta_{r}^{G},\ldots,\delta_{\ell+p-1}^{G}\\}\cup\\{\delta_{\ell+p+r}^{G},\ldots,\delta_{\ell+p+r+t-1}^{G}\\}$.
Because every simple $(r,m^{\prime},\ell+p+t-r)$-daisy contains an
$(r-1,m^{\prime}-1,\ell+p+t-r+1)$-daisy and the projection is monochromatic
with respect to $\varphi_{\ell+p+t-1}$, we obtain a monochromatic simple
$(r-1,\frac{1}{5}k^{-1/2}m^{1/2},\ell+p+t-r+1)$-daisy, which is a
contradiction.

Case 2.2.b: Either
$\delta_{r-3}^{X_{J}}<\delta_{r-2}^{X_{J}}<\delta_{r-1}^{X_{J}}$ or
$\delta_{r-3}^{X_{J}}>\delta_{r-2}^{X_{J}}>\delta_{r-1}^{X_{J}}$.

In this case we obtain that
$\chi_{0}(X_{J})=\varphi_{|\delta(X_{J})|}(\delta(X_{J}))$, i.e., the coloring
of $\chi_{0}$ is just the coloring of the projection of $X_{J}$. The proof now
follows similarly as in Case 2.1.

Case 2.3: $X_{J}$ is of type $5$.

$A$$B_{0}$$M^{\prime}$$B_{1}$$P$$\\{\delta_{\ell}^{G},\ldots,\delta_{\ell+p-1}^{G}\\}$$\\{\delta_{\ell+p+m^{\prime}}^{G},\ldots,\delta_{\ell+p+m^{\prime}+t-1}^{G}\\}$$\delta(\\{y_{\ell+p}\\}\cup
P)$$\delta(\\{y_{\ell+p}\\}\cup M^{\prime})$ Figure 21. Case $2.3$ of Theorem
6.1

If $X_{J}$ is of type $5$, then $|A^{X_{J}}|>r$ and
$|B^{X_{J}}|=p+r+t\geqslant r$. By the coloring definition, we have
$\chi_{0}(X_{J})=\varphi_{p+r+t}(\\{\delta_{\ell}^{X_{J}},\ldots,\delta_{\ell+p+r+t-1}^{X_{J}}\\})$.
The projection here can be rewritten as

$\displaystyle\\{\delta_{\ell}^{X_{J}},\ldots,\delta_{\ell+p+r+t-1}^{X_{J}}\\}=\\{\delta_{\ell}^{G},\ldots,\delta_{\ell+p-1}^{G}\\}$
$\displaystyle\cup\\{\delta(\\{y_{\ell+p}\\}\cup P)$
$\displaystyle\cup\\{\delta_{\ell+p+m^{\prime}}^{G},\ldots,\delta_{\ell+p+m^{\prime}+t-1}^{G}\\}.$

Thus, the relevant projection over all edges $X_{J}$ is a simple
$(r,m^{\prime},p+t)$-daisy with kernel
$\\{\delta_{\ell}^{G},\ldots,\delta_{\ell+p-1}^{G}\\}\cup\\{\delta_{\ell+p+m^{\prime}}^{G},\ldots,\delta_{\ell+p+m^{\prime}+t-1}^{G}\\}$.
Therefore, by the same argument did in the previous cases, we reach a
contradiction since there is no monochromatic simple
$(r-1,\frac{1}{5}k^{-1/2}m^{1/2},p+t+1)$-daisy in the coloring
$\varphi_{p+r+t}$. ∎

###### Proof of Theorem 1.3.

We will prove by induction on the size of $r$ that there exists an absolute
positive constants $c$ and $c^{\prime}$ not depending on $k$ and $r$ such that

$\displaystyle
D_{r}^{\operatorname{smp}}(m,k)=t_{r-2}(c^{\prime}(5\sqrt{k})^{2^{5-r}-4}m^{2^{4-r}})\geqslant
t_{r-2}(ck^{2^{4-r}-2}m^{2^{4-r}})$

holds for $k\geqslant 1$ and $m\geqslant(25k)^{2^{r}-1}$. For $r=3$, the
result follows by the next proposition given in [PRS].

######  Proposition 6.3 ([PRS], Proposition 1.2).

There exists a positive constant $c^{\prime}$ not depending on $k$ such that

$\displaystyle D_{3}(m,k)\geqslant 2^{c^{\prime}m^{2}}$

holds for $m>3$.

Now suppose that $r\geqslant 4$ and that for any integer $\ell<r$ the
induction hypothesis is satisfied, i.e.,

$\displaystyle D_{\ell}^{\operatorname{smp}}(m,k)\geqslant
t_{\ell-2}(c^{\prime}(5\sqrt{k})^{2^{5-\ell}-4}m^{2^{4-\ell}})$

for $m\geqslant(25k)^{2^{\ell}-1}$ and $k\geqslant 1$. Let $N=\min_{0\leqslant
i\leqslant k-1}{D_{r-1}^{\operatorname{smp}}(\frac{1}{5}k^{-1/2}m^{1/2},i)}$.
For $i=0$, by equation (2) we have that

$\displaystyle
D_{r-1}^{\operatorname{smp}}\left(\frac{1}{5}k^{-1/2}m^{1/2},0\right)\geqslant
R_{r-1}\left(\frac{1}{5}k^{-1/2}m^{1/2}\right)\geqslant t_{r-2}(c_{1}k^{-1}m)$

for a positive constant $c_{1}$. Since $m\geqslant(25k)^{2^{r}-1}$, we obtain
that $\frac{1}{5}k^{-1/2}m^{1/2}\geqslant(25k)^{2^{r-1}-1}$. Thus, by
induction hypothesis we also have that

$\displaystyle
D_{r-1}^{\operatorname{smp}}\left(\frac{1}{5}k^{-1/2}m^{1/2},i\right)\geqslant
t_{r-3}\left(c^{\prime}(5\sqrt{i})^{2^{6-r}}\left(\frac{1}{5}k^{-1/2}m^{1/2}\right)^{2^{5-r}}\right),$

for $i\geqslant 1$. Therefore,

$\displaystyle N$
$\displaystyle\geqslant\min\left\\{t_{r-2}(c_{1}k^{-1}m),\min_{1\leqslant
i\leqslant
k}\left\\{t_{r-3}\left(c^{\prime}(5\sqrt{i})^{2^{6-r}-4}\left(\frac{1}{5}k^{-1/2}m^{1/2}\right)^{2^{5-r}}\right)\right\\}\right\\}$
$\displaystyle\geqslant
t_{r-3}(c^{\prime}(5\sqrt{k})^{2^{5-r}-4}m^{2^{4-r}}).$

Finally, Theorem 6.1, applied to $m\geqslant(25k)^{2^{r}-1}\geqslant
100kr^{2}$, gives us that

$\displaystyle D_{r}^{\operatorname{smp}}(m,k)\geqslant 2^{N}\geqslant
t^{r-2}(c^{\prime}(5\sqrt{k})^{2^{5-r}-4}m^{2^{4-r}}).$

∎

## Acknowledgments

The author thanks Pavel Pudlák and Vojtech Rödl for their comments on earlier
versions of the manuscript.

## References