# Flashes and rainbows in tournaments

António Girão222Mathematical Institute, University of Oxford, United Kingdom
({girao,illingworth,michel,savery,scott}@maths.ox.ac.uk). Research of AG, FI,
and AS supported by EPSRC grant EP/V007327/1. Freddie
Illingworth222Mathematical Institute, University of Oxford, United Kingdom
({girao,illingworth,michel,savery,scott}@maths.ox.ac.uk). Research of AG, FI,
and AS supported by EPSRC grant EP/V007327/1. Lukas Michel222Mathematical
Institute, University of Oxford, United Kingdom
({girao,illingworth,michel,savery,scott}@maths.ox.ac.uk). Research of AG, FI,
and AS supported by EPSRC grant EP/V007327/1.
Michael Savery222Mathematical Institute, University of Oxford, United Kingdom
({girao,illingworth,michel,savery,scott}@maths.ox.ac.uk). Research of AG, FI,
and AS supported by EPSRC grant EP/V007327/1. 333Heilbronn Institute for
Mathematical Research, Bristol, UK. Alex Scott222Mathematical Institute,
University of Oxford, United Kingdom
({girao,illingworth,michel,savery,scott}@maths.ox.ac.uk). Research of AG, FI,
and AS supported by EPSRC grant EP/V007327/1.

(1 June 2023)

###### Abstract

Colour the edges of the complete graph with vertex set $\\{1,2,\dotsc,n\\}$
with an arbitrary number of colours. What is the smallest integer $f(l,k)$
such that if $n>f(l,k)$ then there must exist a monotone monochromatic path of
length $l$ or a monotone rainbow path of length $k$? Lefmann, Rödl, and Thomas
conjectured in 1992 that $f(l,k)=l^{k-1}$ and proved this for
$l\geqslant(3k)^{2k}$. We prove the conjecture for $l\geqslant k^{3}(\log
k)^{1+o(1)}$ and establish the general upper bound $f(l,k)\leqslant k(\log
k)^{1+o(1)}\cdot l^{k-1}$. This reduces the gap between the best lower and
upper bounds from exponential to polynomial in $k$. We also generalise some of
these results to the tournament setting.

00footnotetext: _2020 MSC_ : 05C55 (generalised Ramsey theory), 05C35
(extremal problems), 05C38 (paths and cycles).

##  1 Introduction

In 1930, Ramsey [Ram30] showed that every $k$-colouring of the edges of a very
large clique contains a large monochromatic sub-clique. This classical theorem
was the starting seed for Ramsey theory, and there have been numerous
extensions and generalisations of it since then. One of the most important is
the canonical Ramsey theorem of Erdős and Rado [ER50], which considers
colourings that allow an arbitrary number of colours. It states that every
colouring of the edges of a very large clique with an arbitrary number of
colours contains a large sub-clique with one of four types of colourings.

######  Theorem 1.1 (Erdős, Rado).

There is a function $f(k)$ such that every colouring of the edges of the
complete graph on $\\{1,2,\ldots,f(k)\\}$ contains a complete $k$-vertex
subgraph whose colouring is of one of the following four canonical types:

  * •

rainbow — no two edges have the same colour;

  * •

monochromatic — all edges have the same colour;

  * •

upper lexical — two edges have the same colour if and only if they end at the
same vertex;

  * •

lower lexical — two edges have the same colour if and only if they start at
the same vertex.

Lefmann and Rödl [LR95] gave the best current bounds for this result, showing
that we can take $f(k)=k^{Ck^{2}}$ for some constant $C$. The canonical Ramsey
theorem has an immediate corollary for monotone paths. It implies that there
is an integer $f(l,k)$ such that if $n>f(l,k)$ then every colouring
$c\colon\tbinom{[n]}{2}\to\mathnormal{\mathbb{N}}$ yields either:

  * •

$x_{0}<\dotsb<x_{l}$ with $c(x_{0}x_{1}),c(x_{1}x_{2}),\dotsc,c(x_{l-1}x_{l})$
all the same (an _$l$ -flash_), or

  * •

$y_{0}<\dotsb<y_{k}$ with $c(y_{0}y_{1}),c(y_{1}y_{2}),\dotsc,c(y_{k-1}y_{k})$
all distinct (a _$k$ -rainbow_).

Lefmann and Rödl’s bound implies that $f(k,k)\leqslant k^{Ck^{2}}$.

In 1992, Lefmann, Rödl, and Thomas [LRT92] gave better bounds on $f(l,k)$.
From below, they provided a nice construction showing that $f(l,k)\geqslant
l^{k-1}$: label the vertices with strings from $\\{1,2,\dotsc,l\\}^{k-1}$ in
lexicographic order and, for a pair of vertices $u<v$, let $c(uv)$ be any
index at which $u$ has a smaller value than $v$. It is not difficult to see
that this construction contains no $l$-flash or $k$-rainbow, and in fact it is
best possible if only $k-1$ colours are used. They made the attractive
conjecture that this lower bound is tight in general.

######  Conjecture 1.2 (Lefmann, Rödl, Thomas).

For all positive integers $l$ and $k$, $f(l,k)=l^{k-1}$.

Lefmann, Rödl, and Thomas gave support for their conjecture by proving that it
is true for the small cases $l\leqslant 2$ or $k\leqslant 4$ as well as when
$l$ is at least factorial in $k$ (specifically, when $l\geqslant(3k)^{2k}$).
Our first result proves Conjecture 1.2 provided $l$ is at least polynomial in
$k$ (specifically, when $l\geqslant k^{3}(\log k)^{1+o(1)}$).

######  Theorem 1.3.

For all $\varepsilon>0$, there is $C_{\varepsilon}$ such that if $l\geqslant
C_{\varepsilon}k^{3}(\log k)^{1+\varepsilon}$, then $f(l,k)=l^{k-1}$.

The best general upper bound on $f(l,k)$ was given by Jiang and Mubayi [JM00].

######  Theorem 1.4 (Jiang, Mubayi).

For all integers $l\geqslant 1$ and $k\geqslant 4$,

$f(l,k)\leqslant\biggl{(}1+\frac{1}{\sqrt{l}}\biggr{)}^{k-4}\cdot l^{k-1}.$

This confirms Conjecture 1.2 asymptotically when $l=\omega(k^{2})$. However,
for $l$ fixed and $k$ large this differs from the lower bound by a factor
exponential in $k$. We provide an upper bound in which this factor is only
polynomial in $k$.

######  Theorem 1.5.

For all $\varepsilon>0$, there is $D_{\varepsilon}$ such that for all positive
integers $l$ and $k$,

$f(l,k)\leqslant D_{\varepsilon}k(\log k)^{1+\varepsilon}\cdot l^{k-1}.$

Theorems 1.3, 1.4 and 1.5 are each best in different ranges of values of $l$
and $k$. For $l\geqslant k^{3}(\log k)^{1+o(1)}$, Theorem 1.3 is best
possible, for $l=\mathnormal{\mathcal{O}}((k/\log k)^{2})$, Theorem 1.5
provides the best bound known, and Theorem 1.4 is best in the intermediate
regime.

Flashes and rainbows generalise very naturally to tournaments, where a
_tournament_ is an orientation of a complete graph. A _directed walk_ in a
tournament is a sequence of vertices $x_{0},\dots,x_{l}$ such that
$x_{i-1}x_{i}$ is a directed edge for all $1\leqslant i\leqslant l$ (note that
walks are allowed to repeat vertices and edges).

######  Definition 1.6.

Let $l$ and $k$ be non-negative integers. An _$l$ -flash_ in a tournament is a
directed walk $x_{0},\dotsc,x_{l}$ with $c(x_{0}x_{1}),\dotsc,c(x_{l-1}x_{l})$
all the same. A _$k$ -rainbow_ is a directed walk $y_{0},\dotsc,y_{k}$ with
$c(y_{0}y_{1}),\dotsc,c(y_{k-1}y_{k})$ all distinct.

Let $t(l,k)$ denote the smallest integer such that every colouring of the
edges of any tournament with more than $t(l,k)$ vertices contains an $l$-flash
or a $k$-rainbow. Conjecture 1.2 can now be viewed as the restriction of this
problem to _transitive_ tournaments and thus we have

$t(l,k)\geqslant f(l,k)\geqslant l^{k-1}.$

We conjecture that the tournament strengthening of Conjecture 1.2 holds.

######  Conjecture 1.7.

For all positive integers $l$ and $k$, $t(l,k)=l^{k-1}$.

We prove two upper bounds on $t(l,k)$. The first, Theorem 1.8, is better when
$l$ is large compared to $k$ and confirms Conjecture 1.7 asymptotically for
$l=\omega(k^{2})$. Although the bound looks very similar to Theorem 1.4, the
proof is quite different and uses a probabilistic argument.

######  Theorem 1.8.

For all positive integers $l$ and $k$,
$t(l,k)\leqslant\bigl{(}1+\frac{2}{\sqrt{l}}\bigr{)}^{k}\cdot l^{k-1}$.

Our second upper bound, Theorem 1.9, is better when $k$ is large compared to
$l$ and, in particular, improves upon Theorem 1.8 for
$l=\mathnormal{\mathcal{O}}((k/\log k)^{2})$. Note that it implies Theorem
1.5.

######  Theorem 1.9.

For every $\varepsilon>0$, there is $D_{\varepsilon}$ such that for all
positive integers $l$ and $k$,

$t(l,k)\leqslant D_{\varepsilon}k(\log k)^{1+\varepsilon}\cdot l^{k-1}.$

Conjecture 1.7 posits that if one wants to colour the edges of a large
tournament while avoiding $l$-flashes and $k$-rainbows, then transitive
tournaments are best in the sense of having the most vertices. The following
result shows that there are tournaments that are strictly worse than
transitive tournaments.

######  Theorem 1.10.

For all $l\geqslant 2$ and $k\geqslant 3$, there is a tournament with
$f(l,k)-1$ vertices such that every colouring of its edges contains an
$l$-flash or a $k$-rainbow.

Finally, it is interesting to ask how bad a tournament can be: how few
vertices can a tournament have if every colouring of its edges contains an
$l$-flash or a $k$-rainbow? The following provides a general lower bound
showing that the number of vertices in such a tournament must be within a
factor $l\sqrt{k}$ of $l^{k-1}$.

######  Theorem 1.11.

There is a constant $C>0$ such that every tournament with at most
$Cl^{k-2}/\sqrt{k}$ vertices has an edge colouring with neither $l$-flashes
nor $k$-rainbows.

The rest of the paper is structured as follows. In Section 2 we consider
arbitrary tournaments and prove Theorems 1.8 and 1.9. We then specialise to
transitive tournaments in Section 3 and provide a proof of Theorem 1.3. In
Section 4 we explore the differences between these two settings, proving
Theorems 1.10 and 1.11, and we close by stating some open problems in Section
5. Throughout this paper, $l$ and $k$ are positive integers.

##  2 Upper bounds for arbitrary tournaments

In this section, we prove Theorems 1.8 and 1.9. For both, we rely on the
following observation: if a tournament contains no $k$-rainbow and a
$(k-1)$-rainbow ends at some vertex $v$, then $v$ has at most $k-1$ outgoing
colours. Indeed, otherwise any $(k-1)$-rainbow ending at $v$ could be extended
to a $k$-rainbow. This will allow us to restrict ourselves to tournaments
where each vertex only has few outgoing (and incoming) colours. In this
setting, we show that the following lemma holds.

######  Lemma 2.1.

Let $T=(V,E)$ be an edge-coloured tournament containing no $l$-flash, and
assume that every vertex has at most $c$ incoming colours and at most $c$
outgoing colours. Then,

$\lvert
V\rvert\leqslant\mathopen{}\mathclose{{}\left(1+\frac{2}{\sqrt{l}}}\right)^{c}\cdot
l^{c}.$

We prove this result with a probabilistic argument. We will use the following
definitions. For a vertex $v$, we write $c^{-}(v)=\\{c(uv)\mathrel{|}uv\in
E\\}$ for the set of incoming colours of $v$,
$c^{+}(v)=\\{c(vu)\mathrel{|}vu\in E\\}$ for the set of outgoing colours of
$v$, and $c(v)=c^{-}(v)\cup c^{+}(v)$ for the set of colours incident to $v$.
Moreover, for every vertex $v$ and colour $a$, let

$l_{a}(v)=\begin{cases}l-1&\text{if }a\in c^{-}(v)\setminus c^{+}(v),\\\
\text{length of the longest flash of colour $a$ ending at
$v$}&\text{otherwise}.\end{cases}$

This is defined for every colour $a$ in our colouring; however $l_{a}(v)$ is
only non-zero for incoming colours of $v$. Note also that if an edge $uv$ has
colour $a$, then $l_{a}(u)<l_{a}(v)$.

###### Proof of Lemma 2.1.

Let $p\geqslant 0$ be the root of $(l-2)p^{2}+2p=1$, so $p=1/(1+\sqrt{l-1})$.
For every colour $a$, choose $l_{a}\in\\{0,\dots,l-1\\}$ independently at
random such that
$\operatorname{\mathbb{P}}(l_{a}=0)=\operatorname{\mathbb{P}}(l_{a}=l-1)=p$
and $\operatorname{\mathbb{P}}(l_{a}=i)=p^{2}$ for every $i\in[l-2]$. Define

$U=\\{v\in V\mathrel{|}\forall a\in c(v),\ l_{a}(v)=l_{a}\\}.$

If $T[U]$ contains an edge $uv$, say of colour $a$, then $a\in c(u)\cap c(v)$
and $l_{a}(u)<l_{a}(v)$, contradicting the definition of $U$. Thus, $\lvert
U\rvert\leqslant 1$. Moreover, for every vertex $v$ and every colour $a\in
c(v)$ it holds that $l_{a}(v)\in\\{0,l-1\\}$ if and only if $a\in
c^{-}(v)\bigtriangleup c^{+}(v)$, and so

$\operatorname{\mathbb{P}}(v\in U)=p^{\lvert c^{-}(v)\bigtriangleup
c^{+}(v)\rvert}p^{2\lvert c^{-}(v)\cap c^{+}(v)\rvert}=p^{\lvert
c^{-}(v)\rvert+\lvert c^{+}(v)\rvert}\geqslant p^{2c}.$

It follows that the expected size of $U$ is at least $p^{2c}\lvert V\rvert$,
and since $\lvert U\rvert\leqslant 1$ we have

$\displaystyle\lvert V\rvert$ $\displaystyle\leqslant
p^{-2c}=\mathopen{}\mathclose{{}\left(1+\sqrt{l-1}}\right)^{2c}=\mathopen{}\mathclose{{}\left(l+2\sqrt{l-1}}\right)^{c}\leqslant\mathopen{}\mathclose{{}\left(1+\frac{2}{\sqrt{l}}}\right)^{c}\cdot
l^{c}.\qed$

To obtain Theorem 1.8, we will use induction to bound the number of vertices
where no $(k-1)$-rainbow starts and no $(k-1)$-rainbow ends. By the
observation from the beginning of this section, the number of remaining
vertices can then be bounded via the preceding lemma.

###### Proof of Theorem 1.8.

For $k\geqslant 2$, we claim that $t(l,k)\leqslant 2\cdot
t(l,k-1)+(l+2\sqrt{l})^{k-1}$. Indeed, let $T=(V,E)$ be a tournament
containing no $l$-flash and no $k$-rainbow. Define

$\displaystyle R=\\{v\in V\mathrel{|}\text{no $(k-1)$-rainbow ends at
$v$}\\}\text{ and}$ $\displaystyle S=\\{v\in V\mathrel{|}\text{no
$(k-1)$-rainbow starts at $v$}\\}.$

Clearly $\lvert R\rvert,\lvert S\rvert\leqslant t(l,k-1)$. Every vertex $v\in
V\setminus R$ has at most $k-1$ outgoing colours (or else any $(k-1)$-rainbow
ending at $v$ could be extended to a $k$-rainbow), and similarly every vertex
in $V\setminus S$ has at most $k-1$ incoming colours. By Lemma 2.1, it follows
that $\lvert V\setminus(R\cup S)\rvert\leqslant(1+2/\sqrt{l})^{k-1}\cdot
l^{k-1}$ and therefore

$\lvert V\rvert\leqslant\lvert R\rvert+\lvert S\rvert+\lvert V\setminus(R\cup
S)\rvert\leqslant 2\cdot t(l,k-1)+(l+2\sqrt{l})^{k-1}.$

This proves the claim. A straightforward induction on $k$ with base case
$t(l,1)=1$ yields

$\displaystyle t(l,k)$
$\displaystyle\leqslant\sum_{i=0}^{k-1}\mathopen{}\mathclose{{}\left(\frac{2}{l+2\sqrt{l}}}\right)^{i}(l+2\sqrt{l})^{k-1}\leqslant\frac{1}{1-\frac{2}{l+2\sqrt{l}}}(l+2\sqrt{l})^{k-1}$
$\displaystyle=\frac{l+2\sqrt{l}}{l+2\sqrt{l}-2}\mathopen{}\mathclose{{}\left(1+\frac{2}{\sqrt{l}}}\right)^{k-1}\cdot
l^{k-1}\leqslant\mathopen{}\mathclose{{}\left(1+\frac{2}{\sqrt{l}}}\right)^{k}\cdot
l^{k-1}.\qed$

Next, we prove Theorem 1.9. To this end, we will consider so-called ‘robust’
vertices, which were introduced by Lefmann, Rödl, and Thomas [LRT92] under a
different name. Loosely, we call a vertex $v$ _robust_ if we can find long
rainbows ending and/or starting at $v$ that avoid any given colour.

######  Definition 2.2.

Let $r$ be a non-negative integer. A vertex $v$ is _$r$ -in-robust_ if, for
every colour $a$, some $r$-rainbow without colour $a$ ends at $v$.

In-robust vertices are very useful for constructing long rainbows. Indeed,
assume that $u$ is an in-robust vertex with an edge of colour $a$ to some
other vertex $v$. Then, we can pick a long rainbow without colour $a$ ending
at $u$ and try to connect this rainbow to some rainbow starting at $v$. Since
the edge $uv$ cannot interfere with the rainbow ending at $u$, choosing an
appropriate rainbow starting at $v$ might result in a long rainbow.

Of course, in-robust vertices are only useful if they are forced to occur in
large enough tournaments. As above, it will suffice to consider tournaments
with few incoming and outgoing colours at each vertex. Therefore, let
$g(l,k,r)$ denote the smallest integer such that if $T$ is a tournament with
more than $g(l,k,r)$ vertices, then every edge colouring of $T$ with at most
$k-1$ outgoing colours at each vertex contains an $l$-flash, a $k$-rainbow, or
an $r$-in-robust vertex.

It turns out that $g(l,k,r)$ is not much larger than $t(l,r)$. Therefore, in
large tournaments we will be able to find $r$-in-robust vertices for large
$r$, which we can then use to find $k$-rainbows as outlined above. This
strategy yields the following bound on $t(l,k)$.

######  Lemma 2.3.

For every $k\geqslant 2$ and $1\leqslant r<k$,

$t(l,k)\leqslant t(l,k-1)+g(l,k,r-1)+1+2(k-1)l^{r}\cdot t(l,k-r).$

###### Proof.

Let $T=(V,E)$ be an edge-coloured tournament with no $l$-flash or $k$-rainbow.
Let

$R=\\{v\in V\mathrel{|}\text{no $(k-1)$-rainbow ends at $v$}\\}.$

Then $\lvert R\rvert\leqslant t(l,k-1)$, and every vertex in $V\setminus R$
has at most $k-1$ outgoing colours.

Order the vertices in $V\setminus R$ in a way that maximises the number of
forward edges of $T[V\setminus R]$, and pick a minimal initial segment
$P\subseteq V\setminus R$ of this ordering such that $T[P]$ contains an
$(r-1)$-in-robust vertex $v$ (if no such vertex exists, then we already have
$\lvert V\rvert\leqslant\lvert R\rvert+\lvert V\setminus R\rvert\leqslant
t(l,k-1)+g(l,k,r-1)$). Note that $\lvert P\rvert\leqslant g(l,k,r-1)+1$. By
our choice of ordering on $V\setminus R$, $v$ must have outgoing edges to at
least half of the vertices following it, so if $U=\\{u\in V\mathrel{|}vu\in
E\\}$ denotes the out-neighbourhood of $v$, then $\lvert V\setminus(R\cup
P)\rvert\leqslant 2\lvert U\rvert$.

For every colour $a\in c^{+}(v)$, let $U_{a}=\\{u\in U\mathrel{|}c(vu)=a\\}$.
Since $v$ is $(r-1)$-in-robust, we can choose an $(r-1)$-rainbow $W_{a}$
without colour $a$ that ends at $v$, and extend it to each of the vertices in
$U_{a}$ by the edges of colour $a$. Let $C_{a}$ be the set containing $a$ and
the $r-1$ colours appearing in $W_{a}$.

Next, for every $m\in\\{0,\dots,l-1\\}^{C_{a}}$ define

$U_{a}^{m}=\\{u\in U_{a}\mathrel{|}\forall b\in C_{a},\ l_{b}(u)=m_{b}\\}.$

If the colour of an edge $uw$ in $T[U_{a}^{m}]$ is $b$, then
$l_{b}(u)<l_{b}(w)$, and so $b\notin C_{a}$. Thus, if $T[U_{a}^{m}]$ contained
a $(k-r)$-rainbow starting at some vertex $u$, then this rainbow would use no
colour from $C_{a}$ and could therefore be extended by the $r$-rainbow ending
at $u$ to a $k$-rainbow. It follows that $T[U_{a}^{m}]$ contains no
$(k-r)$-rainbow, so $\lvert U_{a}^{m}\rvert\leqslant t(l,k-r)$ and

$\lvert U_{a}\rvert=\sum_{m\in\\{0,\dots,l-1\\}^{C_{a}}}\lvert
U_{a}^{m}\rvert\leqslant\sum_{m\in\\{0,\dots,l-1\\}^{C_{a}}}t(l,k-r)\leqslant
l^{r}\cdot t(l,k-r).$

Since $v$ has at most $k-1$ outgoing colours, this implies that

$\lvert U\rvert=\sum_{a\in c^{+}(v)}\lvert U_{a}\rvert\leqslant\sum_{a\in
c^{+}(v)}l^{r}\cdot t(l,k-r)\leqslant(k-1)l^{r}\cdot t(l,k-r).$

Putting everything together, we get

$\displaystyle\lvert V\rvert$ $\displaystyle=\lvert R\rvert+\lvert
P\rvert+\lvert V\setminus(R\cup P)\rvert$ $\displaystyle\leqslant\lvert
R\rvert+\lvert P\rvert+2\lvert U\rvert$ $\displaystyle\leqslant
t(l,k-1)+g(l,k,r-1)+1+2(k-1)l^{r}\cdot t(l,k-r).\qed$

To apply this lemma, we need a good bound on $g(l,k,r)$. Fortunately, we can
use a strategy similar to that used the preceding proof to obtain the
following result.

######  Lemma 2.4.

For every $r\geqslant 1$, it holds that

$g(l,k,r)\leqslant g(l,k,r-1)+1+2(k-1)rl\cdot t(l,r).$

###### Proof.

Let $T=(V,E)$ be an edge-coloured tournament with no $l$-flash, no
$k$-rainbow, no $r$-in-robust vertex, and at most $k-1$ outgoing colours at
each vertex. Order the vertices of $T$ in a way that maximises the number of
forward edges, and pick a minimal initial segment $P\subseteq V$ of this
ordering such that $T[P]$ contains an $(r-1)$-in-robust vertex $v$. As before,
$\lvert P\rvert\leqslant g(l,k,r-1)+1$ and if $U=\\{u\in V\mathrel{|}vu\in
E\\}$ denotes the out-neighbourhood of $v$, then $\lvert V\setminus
P\rvert\leqslant 2\lvert U\rvert$. For each $a\in c^{+}(v)$, define $U_{a}$,
$W_{a}$, and $C_{a}$ as in the previous proof.

Next, for every colour $b\in C_{a}$, define

$U_{a,b}=\\{u\in U_{a}\mathrel{|}\text{every $r$-rainbow ending at $u$
contains colour $b$}\\}.$

By assumption, no vertex is $r$-in-robust, but for each $u\in U_{a}$ there is
an $r$-rainbow using only the colours of $C_{a}$ ending at $u$. It follows
that $U_{a}=\bigcup_{b\in C_{a}}U_{a,b}$. Finally, for every
$m\in\\{0,\dots,l-1\\}$, let

$U_{a,b}^{m}=\\{u\in U_{a,b}\mathrel{|}l_{b}(u)=m\\}.$

Now, if an edge $uw$ in $T[U_{a,b}^{m}]$ has colour $b$, then
$l_{b}(u)<l_{b}(w)$ which gives a contradiction. Thus, if $T[U_{a,b}^{m}]$
contained an $r$-rainbow ending at some vertex $u$, then this rainbow would
not use the colour $b$, contradicting $u\in U_{a,b}$. It follows that
$T[U_{a,b}^{m}]$ contains no $r$-rainbow, so $\lvert
U_{a,b}^{m}\rvert\leqslant t(l,r)$ and

$\lvert U_{a}\rvert\leqslant\sum_{b\in C_{a}}\lvert U_{a,b}\rvert=\sum_{b\in
C_{a}}\sum_{m\in\\{0,\dots,l-1\\}}\lvert U_{a,b}^{m}\rvert\leqslant\sum_{b\in
C_{a}}\sum_{m\in\\{0,\dots,l-1\\}}t(l,r)=rl\cdot t(l,r).$

Since $v$ has at most $k-1$ outgoing colours, this implies $\lvert
U\rvert\leqslant(k-1)rl\cdot t(l,r)$, and so

$\lvert V\rvert=\lvert P\rvert+\lvert V\setminus P\rvert\leqslant\lvert
P\rvert+2\lvert U\rvert\leqslant g(l,k,r-1)+1+2(k-1)rl\cdot t(l,r).\qed$

Finally, to obtain numerical bounds on $t(l,k)$ and $g(l,k,r)$, we apply these
recursive bounds repeatedly. This is handled by the following corollary, which
proves Theorem 1.9 and gives an upper bound on $g(l,k,r)$ that will be useful
in Section 3.

######  Corollary 2.5.

For every $\varepsilon>0$, there is $D_{\varepsilon}$ such that for $r<k$

$t(l,k)\leqslant D_{\varepsilon}k(\log k)^{1+\varepsilon}\cdot
l^{k-1}\quad\text{and}\quad g(l,k,r)\leqslant 4D_{\varepsilon}k^{3}(\log
k)^{1+\varepsilon}\cdot l^{r}.$

###### Proof.

From Lemma 2.3 and Lemma 2.4, we can obtain the inequalities

$\displaystyle t(l,k)$ $\displaystyle\leqslant
t(l,k-1)+g(l,k,r-1)+2kl^{r}\cdot t(l,k-r)\text{ and}$ $\displaystyle g(l,k,r)$
$\displaystyle\leqslant g(l,k,r-1)+2k^{2}l\cdot t(l,r)$

for $k\geqslant 2$ and $1\leqslant r<k$.

Let $k_{0}\geqslant 2$ be such that $8(3\log k+5)(\log(3\log
k+5))^{1+\varepsilon}\leqslant(\log k)^{1+\varepsilon}$ for all $k\geqslant
k_{0}$. By Theorem 1.8, there is $D_{\varepsilon}$ such that $t(l,k)\leqslant
D_{\varepsilon}k(\log k)^{1+\varepsilon}\cdot l^{k-1}$ for all $k<k_{0}$.

We prove the corollary by induction on $k$. Assume that we have already proved
it for all $k^{\prime}<k$. We may also assume that $l\geqslant 2$ since the
claim is trivial for $l=1$. Then, for $r<k$, a simple induction on $r$ with
base case $g(l,k,0)=0$ yields

$\displaystyle g(l,k,r)$ $\displaystyle\leqslant g(l,k,r-1)+2k^{2}l\cdot
t(l,r)$ $\displaystyle\leqslant 4D_{\varepsilon}k^{3}(\log
k)^{1+\varepsilon}\cdot l^{r-1}+2D_{\varepsilon}k^{3}(\log
k)^{1+\varepsilon}\cdot l^{r}\stackrel{{\scriptstyle l\geqslant
2}}{{\leqslant}}4D_{\varepsilon}k^{3}(\log k)^{1+\varepsilon}\cdot l^{r}.$

To bound $t(l,k)$, we may assume that $k\geqslant k_{0}$ by our choice of
$D_{\varepsilon}$. Note that

$t(l,k-1)\leqslant D_{\varepsilon}k(\log k)^{1+\varepsilon}\cdot
l^{k-2}\stackrel{{\scriptstyle l\geqslant
2}}{{\leqslant}}\frac{D_{\varepsilon}k(\log k)^{1+\varepsilon}\cdot
l^{k-1}}{2}.$

Choose

$r=\mathopen{}\mathclose{{}\left\lfloor k-\frac{2\log k+\log 16}{\log
l}}\right\rfloor,$

then

$g(l,k,r-1)\leqslant 4D_{\varepsilon}k^{3}(\log k)^{1+\varepsilon}\cdot
l^{k-1-\frac{2\log k+\log 16}{\log l}}=\frac{D_{\varepsilon}k(\log
k)^{1+\varepsilon}\cdot l^{k-1}}{4}.$

Also,

$\displaystyle r$ $\displaystyle\geqslant k-\frac{2\log k+\log 16}{\log
l}-1\geqslant k-\frac{2\log k+\log 16}{\log 2}-1\geqslant k-(3\log k+5)$

and so, using the fact that $k\geqslant k_{0}$, we have

$\displaystyle 8(k-r)(\log(k-r))^{1+\varepsilon}\leqslant 8(3\log
k+5)(\log(3\log k+5))^{1+\varepsilon}\leqslant(\log k)^{1+\varepsilon}.$

It follows by induction that

$2kl^{r}\cdot t(l,k-r)\leqslant
2kD_{\varepsilon}(k-r)(\log(k-r))^{1+\varepsilon}\cdot
l^{k-1}\leqslant\frac{D_{\varepsilon}k(\log k)^{1+\varepsilon}\cdot
l^{k-1}}{4}.$

Combining, we obtain

$\displaystyle t(l,k)$ $\displaystyle\leqslant
t(l,k-1)+g(l,k,r-1)+2kl^{r}\cdot t(l,k-r)$
$\displaystyle\leqslant\mathopen{}\mathclose{{}\left(\frac{1}{2}+\frac{1}{4}+\frac{1}{4}}\right)D_{\varepsilon}k(\log
k)^{1+\varepsilon}\cdot l^{k-1}$ $\displaystyle=D_{\varepsilon}k(\log
k)^{1+\varepsilon}\cdot l^{k-1}.\qed$

##  3 Upper bounds for transitive tournaments

In this section we prove Theorem 1.3, that is, we show that $f(l,k)=l^{k-1}$
if $l$ is sufficiently large in terms of $k$. We will follow a similar
strategy to that used by Lefmann, Rödl, and Thomas [LRT92] when they showed
this equality for $l\geqslant(3k)^{2k}$, but our bounds and arguments from the
previous section will allow us to improve the dependence on $k$.

The idea of the proof is to find a _strongly $(k-2)$-robust vertex_, that is,
a vertex $v$ such that there exists a set $C$ of $k-1$ colours which contains
all colours incident to $v$ and which has the property that for all $a\in C$,
there is a $(k-2)$-rainbow with colour set $C\setminus\\{a\\}$ that ends at
$v$, and also one that starts at $v$. The existence of such a vertex will
allow us to show that every $2$-flash in the entire tournament takes its
colour from $C$, which will in turn allow us to reduce the problem to the
$l=2$ case, for which Lefmann, Rödl, and Thomas [LRT92] have already shown
that the result holds.

######  Theorem 3.1 (Lefmann, Rödl, Thomas).

For all positive integers $k$, $f(2,k)=2^{k-1}$.

This final ingredient, Theorem 3.1, is the only part of the proof where we
need our tournament to be transitive: our arguments will show that if
$t(2,k)=2^{k-1}$ for all $k$, then Theorem 1.3 holds with $t(l,k)$ in place of
$f(l,k)$. For this reason, we will state and prove most of the results in this
section for arbitrary tournaments.

We begin by explaining how the fact that few colours appear in $2$-flashes
allows us to reduce the problem to the $l=2$ case.

######  Lemma 3.2.

Let $1\leqslant m\leqslant l$, let $T=(V,E)$ be an edge-coloured tournament
containing no $l$-flash or $k$-rainbow, and assume that for every vertex $v$
the number of colours used by $m$-flashes containing $v$ is at most $c$. Then,

$\lvert V\rvert\leqslant
t(m,k)\mathopen{}\mathclose{{}\left(\frac{l}{m}}\right)^{c}.$

We will use a probabilistic argument similar to that used to prove Lemma 2.1.
Write $c^{m\text{-flash}}(v)$ for the set of colours $a$ such that there
exists an $m$-flash of colour $a$ containing $v$.

###### Proof.

For every colour $a$, choose a subset $L_{a}\subseteq\\{0,\dots,l-1\\}$ of
size $m$ uniformly and independently at random. Define

$U=\mathopen{}\mathclose{{}\left\\{v\in V\mathrel{|}\forall a\in
c^{m\text{-flash}}(v),\ l_{a}(v)\in L_{a}}\right\\},$

and note that $T[U]$ contains no $m$-flash $v_{0},\dots,v_{m}$ in any colour
$a$. Indeed, otherwise $l_{a}(v_{0})<\dots<l_{a}(v_{m})$ with $a\in
c^{m\text{-flash}}(v_{i})$ for every $i$, so $L_{a}$ has size at least $m+1$,
which is a contradiction. Hence, $\lvert U\rvert\leqslant t(m,k)$. On the
other hand, for every vertex $v$ we have $\operatorname{\mathbb{P}}(v\in
U)=(m/l)^{\lvert c^{m\text{-flash}}(v)\rvert}\geqslant(m/l)^{c}$, and so

$\lvert
V\rvert\mathopen{}\mathclose{{}\left(\frac{m}{l}}\right)^{c}\leqslant\sum_{v\in
V}\operatorname{\mathbb{P}}(v\in U)=\operatorname{\mathbb{E}}(\lvert
U\rvert)\leqslant t(m,k),$

which implies that $\lvert V\rvert\leqslant
t(m,k)\mathopen{}\mathclose{{}\left({l}/{m}}\right)^{c}$. ∎

Next, we show how the existence of a strongly $(k-2)$-robust vertex implies
that few colours occur in 2-flashes.

######  Lemma 3.3.

Let $k\geqslant 2$ and let $T=(V,E)$ be an edge-coloured tournament containing
no $k$-rainbow. Suppose that $T$ contains a strongly $(k-2)$-robust vertex.
Then at most $k-1$ colours occur in $2$-flashes.

###### Proof.

Let $u$ be a strongly $(k-2)$-robust vertex in $T$, and let $C$ be the
corresponding set of $k-1$ colours. Suppose for a contradiction that there
exists a $2$-flash $v_{0},v_{1},v_{2}$ of some colour $b\notin C$ in $T$.
Consider the case that the edge between $u$ and $v_{1}$ is directed towards
$v_{1}$, and let $a\in C$ be the colour of that edge. Since $u$ is strongly
$(k-2)$-robust, some $(k-2)$-rainbow with colour set $C\setminus\\{a\\}$ ends
at $u$. Extending this $(k-2)$-rainbow to $v_{1}$ and $v_{2}$ yields a
$k$-rainbow in $T$, which is a contradiction. The case that the edge between
$u$ and $v_{1}$ is directed towards $u$ is similar. Hence, no $2$-flash of a
colour not in $C$ can exist in $T$. Since $\lvert C\rvert=k-1$, the result
follows. ∎

The last step will be to show that every sufficiently large tournament with no
$l$-flash or $k$-rainbow contains a strongly $(k-2)$-robust vertex. The proof
of this result is similar to the proofs of Lemmas 2.3 and 2.4.

######  Lemma 3.4.

Let $k\geqslant 2$ and let $T=(V,E)$ be an edge-coloured tournament containing
no $l$-flash and no $k$-rainbow with

$\lvert V\rvert\geqslant t(l,k-1)+g(l,k,k-2)+2(k-1)(t(l,k-1)+2(k-1)l\cdot
t(l,k-2))+2.$

Then $T$ contains a strongly $(k-2)$-robust vertex.

###### Proof.

Define

$R=\\{v\in V\mathrel{|}\text{no $(k-1)$-rainbow ends at $v$}\\}.$

Then $\lvert R\rvert\leqslant t(l,k-1)$, and every vertex in $V\setminus R$
has at most $k-1$ outgoing colours.

Order the vertices in $V\setminus R$ in a way that maximises the number of
forward edges of $T[V\setminus R]$, and pick a minimal initial segment
$P\subseteq V\setminus R$ of this ordering such that $T[P]$ contains a
$(k-2)$-in-robust vertex $v$. Then $\lvert P\rvert\leqslant g(l,k,k-2)+1$, and
if $U=\\{u\in V\mathrel{|}vu\in E\\}$ denotes the out-neighbourhood of $v$, we
have $2\lvert U\rvert\geqslant\lvert V\setminus(R\cup P)\rvert$ and so

$2\lvert U\rvert\geqslant\lvert V\rvert-\lvert R\rvert-\lvert P\rvert\geqslant
2(k-1)(t(l,k-1)+2(k-1)l\cdot t(l,k-2))+1$

which implies that

$\lvert U\rvert\geqslant(k-1)(t(l,k-1)+2(k-1)l\cdot t(l,k-2))+1.$

For every colour $a\in c^{+}(v)$, let $U_{a}=\\{u\in U\mathrel{|}c(vu)=a\\}$.
Since $v$ has at most $k-1$ outgoing colours, there must exist a colour $a$
such that $\lvert U_{a}\rvert\geqslant{\lvert U\rvert}/{(k-1)}$ and so

$\lvert U_{a}\rvert\geqslant t(l,k-1)+2(k-1)l\cdot t(l,k-2)+1.$

Since $v$ is $(k-2)$-in-robust, we can choose a $(k-2)$-rainbow $W$ without
colour $a$ that ends at $v$, and extend it to each of the vertices in $U_{a}$
by the edges of colour $a$. Let $C$ be the set containing $a$ and the $k-2$
colours appearing in $W$. Then, every outgoing colour of every vertex $u\in
U_{a}$ must be a colour from $C$. In particular, all edges in $T[U_{a}]$ have
one of these $k-1$ colours.

Define

$S=\\{u\in U_{a}\mathrel{|}\text{no $(k-1)$-rainbow in $T[U_{a}]$ starts at
$u$}\\}.$

Then $\lvert S\rvert\leqslant t(l,k-1)$. For every vertex $u\in U_{a}\setminus
S$, some $(k-1)$-rainbow in $T[U_{a}]$ starts at $u$. Since every edge in
$T[U_{a}]$ has a colour from $C$, this $(k-1)$-rainbow uses only colours from
$C$, and so every incoming colour of $u$ in $T$ must be a colour from $C$.

Next, for every colour $b\in C$, define

$\displaystyle U_{a,b}=\\{u\in U_{a}\mathrel{|}\text{every $(k-2)$-rainbow in
$T[U_{a}]$ ending at $u$ contains colour $b$}\\}\text{ and}$ $\displaystyle
V_{a,b}=\\{u\in U_{a}\mathrel{|}\text{every $(k-2)$-rainbow in $T[U_{a}]$
starting at $u$ contains colour $b$}\\}.$

For every $m\in\\{0,\dots,l-1\\}$, let

$U_{a,b}^{m}=\\{u\in U_{a,b}\mathrel{|}l_{b}(u)=m\\}.$

If an edge $uw$ in $T[U_{a,b}^{m}]$ has colour $b$, then $l_{b}(u)<l_{b}(w)$
which gives a contradiction. Thus, $T[U_{a,b}^{m}]$ contains no
$(k-2)$-rainbow, so $\lvert U_{a,b}^{m}\rvert\leqslant t(l,k-2)$ and $\lvert
U_{a,b}\rvert\leqslant l\cdot t(l,k-2)$. Similarly, $\lvert
V_{a,b}\rvert\leqslant l\cdot t(l,k-2)$.

Finally, consider $U_{a}^{\prime}=U_{a}\setminus(S\cup\bigcup_{b\in
C}(U_{a,b}\cup V_{a,b}))$, so

$\lvert U_{a}^{\prime}\rvert\geqslant\lvert U_{a}\rvert-\lvert
S\rvert-\sum_{b\in C}(\lvert U_{a,b}\rvert+\lvert V_{a,b}\rvert)\geqslant 1.$

Let $u\in U_{a}^{\prime}$ be arbitrary. For every colour $b\in C$, there is a
$(k-2)$-rainbow in $T[U_{a}]$ without colour $b$ that ends at $u$, and also
one that starts at $u$. Since every edge in $T[U_{a}]$ has a colour from $C$,
the colour set of these $(k-2)$-rainbows is $C\setminus\\{b\\}$. This shows
that $u$ is strongly $(k-2)$-robust in $T$. ∎

We can now combine the preceding three lemmas and insert the bounds from the
previous section to prove the following.

######  Corollary 3.5.

For every $\varepsilon>0$, there is $C_{\varepsilon}$ such that for all
$k\geqslant 2$,

$t(l,k)\leqslant\max\mathopen{}\mathclose{{}\left\\{C_{\varepsilon}k^{3}(\log
k)^{1+\varepsilon}\cdot
l^{k-2},t(2,k)\mathopen{}\mathclose{{}\left(\frac{l}{2}}\right)^{k-1}}\right\\}.$

###### Proof.

Let $D_{\varepsilon}$ be given by Corollary 2.5, and let
$C_{\varepsilon}=12D_{\varepsilon}$. Suppose that $T=(V,E)$ is an edge-
coloured tournament containing no $l$-flash and no $k$-rainbow with $\lvert
V\rvert\geqslant C_{\varepsilon}k^{3}(\log k)^{1+\varepsilon}\cdot l^{k-2}$.
Then, we have

$\displaystyle\lvert V\rvert\geqslant{}$ $\displaystyle
12D_{\varepsilon}k^{3}(\log k)^{1+\varepsilon}\cdot l^{k-2}$
$\displaystyle\geqslant{}$ $\displaystyle 4D_{\varepsilon}k^{3}(\log
k)^{1+\varepsilon}\cdot l^{k-2}+2k\cdot D_{\varepsilon}k(\log
k)^{1+\varepsilon}\cdot l^{k-2}+4k^{2}l\cdot D_{\varepsilon}k(\log
k)^{1+\varepsilon}\cdot l^{k-3}+2$ $\displaystyle\geqslant{}$ $\displaystyle
g(l,k,k-2)+(2(k-1)+1)t(l,k-1)+4(k-1)^{2}l\cdot t(l,k-2)+2$ $\displaystyle={}$
$\displaystyle t(l,k-1)+g(l,k,k-2)+2(k-1)(t(l,k-1)+2(k-1)l\cdot t(l,k-2))+2.$

Hence, by Lemma 3.4, $T$ contains a strongly $(k-2)$-robust vertex. Applying
Lemma 3.3 yields that at most $k-1$ colours appear in $2$-flashes in $T$, and
the result now follows from Lemma 3.2. ∎

In particular, for transitive tournaments, the preceding corollary tells us
that $f(l,k)\leqslant\max\\{C_{\varepsilon}k^{3}(\log k)^{1+\varepsilon}\cdot
l^{k-2},f(2,k)(l/2)^{k-1}\\}$. We can now prove Theorem 1.3.

###### Proof of Theorem 1.3.

Let $C_{\varepsilon}$ be given by Corollary 3.5. The result is trivial for
$k=1$ so assume that $k\geqslant 2$. If $l\geqslant C_{\varepsilon}k^{3}(\log
k)^{1+\varepsilon}$, then $C_{\varepsilon}k^{3}(\log k)^{1+\varepsilon}\cdot
l^{k-2}\leqslant l^{k-1}$, and by Theorem 3.1 we know that
$f(2,k)(l/2)^{k-1}=l^{k-1}$. Therefore, Corollary 3.5 implies that
$f(l,k)\leqslant l^{k-1}$. ∎

##  4 Colourings of arbitrary tournaments

In this section, we ask how small a tournament can be while still having the
property that every colouring of its edges contains an $l$-flash or a
$k$-rainbow. For $k=2$, any non-transitive tournament is an example of this:
if the tournament has a cycle, this cycle either contains two consecutive
edges with different colours, creating a $2$-rainbow, or the cycle is
monochromatic, creating flashes of arbitrary lengths. For $l\geqslant 2$ and
$k\geqslant 3$, we show that there are tournaments on fewer than $f(l,k)$
vertices with the desired property.

###### Proof of Theorem 1.10.

Set $n=f(l,k)$ and let $T$ be the “increasing” transitive tournament on
$[n-1]$ with the edge from $1$ to $n-1$ reversed, that is,

$T=([n-1],\\{uv\mathrel{|}1\leqslant u<v\leqslant n-1,\
uv\neq(1,n-1)\\}\cup\\{(n-1,1)\\}).$

Suppose that $T$ has an edge colouring $c$ with neither $l$-flashes nor
$k$-rainbows. Define an edge colouring $c^{\prime}$ of the “increasing”
transitive tournament $T^{\prime}$ on the vertex set $\\{0\\}\cup[n]$ as
follows. For any edge $uv$ of $T$ with $uv\neq(n-1,1)$, let
$c^{\prime}(uv)=c(uv)$. Next, for any $v\in[n-1]$, let $c^{\prime}(0,v)$ be
the colour of any incoming edge of $v$ in $T$, and let $c^{\prime}(v,n)$ be
the colour of any outgoing edge of $v$ in $T$. Finally, let
$c^{\prime}(1,n-1)$ and $c^{\prime}(0,n)$ be distinct and entirely new
colours.

Note first that the edge $(0,n)$ is not contained in an $l$-flash or
$k$-rainbow since it is in no walk of length greater than $1$. Next, the edge
$(1,n-1)$ is not contained in an $l$-flash in $T^{\prime}$ since there are no
other edges with the same colour. It is also not contained in a $k$-rainbow
since the only $3$-walk containing that edge is $0,1,n-1,n$, but
$c^{\prime}(0,1)=c(n-1,1)=c^{\prime}(n-1,n)$. On the other hand, for every
walk $w$ in $T^{\prime}$ containing neither $(0,n)$ nor $(1,n-1)$, there is a
walk in $T$ with the same colours. Indeed, if $w$ uses the edge $(0,v)$ for
$v\in[n-1]$, then by the construction of $c^{\prime}$ this can be replaced by
an edge of $T$ incident to $v$ of the same colour, and the same holds for
edges $(v,n)$. Since $T$ contains no $l$-flash and no $k$-rainbow, it follows
that $T^{\prime}$ also contains no $l$-flash and no $k$-rainbow. However,
$T^{\prime}$ is a transitive tournament with $n+1=f(l,k)+1$ vertices,
contradicting the definition of $f(l,k)$. ∎

In the positive direction, we prove that all tournaments with
$\mathnormal{\mathcal{O}}(l^{k-2}/\sqrt{k})$ vertices can be coloured in a way
that avoids $l$-flashes and $k$-rainbows. Our construction is very similar to
the construction from the introduction which showed that $f(l,k)\geqslant
l^{k-1}$. However, it only uses those strings whose entries sum to a fixed
value. This ensures that no matter how an edge is directed, we can always pick
an index where the first string has a smaller value than the second string.

###### Proof of Theorem 1.11.

Let

$X=\mathopen{}\mathclose{{}\left\\{x\in[l]^{k-1}\mathrel{|}\sum_{i=1}^{k-1}x_{i}=\mathopen{}\mathclose{{}\left\lfloor\frac{l(k-1)}{2}}\right\rfloor}\right\\}$

which is the largest antichain in the grid poset [BETK51]. A result of
Anderson [And69] says that there is a constant $C>0$ (independent of $l$ and
$k$) such that $\lvert X\rvert\geqslant Cl^{k-2}/\sqrt{k}$. Let $T=(V,E)$ be a
tournament with at most $Cl^{k-2}/\sqrt{k}$ vertices.

As $\lvert V\rvert\leqslant\lvert X\rvert$, we can assign to every vertex $v$
a unique $x(v)\in X$. Define an edge colouring of $T$ by picking, for an edge
$uv\in E$, a colour $c(uv)\in[k-1]$ such that $x(u)_{c(uv)}<x(v)_{c(uv)}$. By
the construction of $X$, this is always possible.

Since this edge colouring uses at most $k-1$ colours, there is no $k$-rainbow.
If there were an $l$-flash $v_{0},\dots,v_{l}$ of colour $a$, then
$x(v_{0})_{a}<x(v_{1})_{a}<\dots<x(v_{l})_{a}$, implying $x(v_{l})_{a}>l$,
which is a contradiction. Thus this gives an edge colouring of $T$ without
$l$-flashes and $k$-rainbows. ∎

With additional work, it is possible to slightly strengthen Theorem 1.11. We
sketch the argument, which combines our proof with an argument from Bucić,
Letzter, and Sudakov [BLS19] and improves the bound to $Cl^{k-2}(\log
l)^{1/(k-1)}/\sqrt{k}$. The idea is to partition a tournament of size $n$ into
$\mathnormal{\mathcal{O}}(n/\log l)$ transitive tournaments of size
$\mathnormal{\mathcal{O}}(\log l)$ each. From the introduction, we know that
each of the transitive tournaments can be coloured with $k-1$ colours and no
$a$-flash if $a^{k-1}=\Omega(\log l)$. Moreover, the previous proof provides a
way to colour the edges between the transitive tournaments with $k-1$ colours
and no $b$-flash provided $b^{k-2}/\sqrt{k}=\Omega(n/\log l)$. The tournament
will then contain no $(ab)$-flash, so we need $ab\leqslant l$, and this is
satisfied if $n=\mathnormal{\mathcal{O}}(l^{k-2}(\log l)^{1/(k-1)}/\sqrt{k})$.

##  5 Open problems

We have proved that Lefmann, Rödl, and Thomas’s conjecture, Conjecture 1.2,
holds for $l\geqslant k^{3}(\log k)^{1+o(1)}$, but the conjecture remains open
when $l$ is small compared to $k$. The case $l=3$ (that is, proving
$f(3,k)=3^{k-1}$) is already of significant interest. In this setting, there
are edge-coloured transitive tournaments with more than $l^{k-1}$ vertices
that contain no $l$-flash and no $k$-rainbow starting at the first vertex. The
existence of $k$-rainbows starting at the first vertex was a crucial
ingredient in Lefmann, Rödl, and Thomas’s proof that $f(2,k)=2^{k-1}$.

Conjecture 1.7 remains wide open for any $l\geqslant 2$ and $k\geqslant 3$.
Establishing this conjecture for $l=2$ would be very useful as our results
would then imply that the conjecture also holds for $l\geqslant k^{3}(\log
k)^{1+o(1)}$.

In terms of general upper bounds on $f(l,k)$ and $t(l,k)$, an interesting next
step would be to reduce the gap between the upper and the lower bounds to a
multiplicative factor that is sublinear in $k$. All of our arguments relied on
certain vertices having at most $k-1$ outgoing colours, which always added a
factor of at least $k$ to our upper bounds.

######  Problem 5.1.

For positive integers $l$ and $k$, is it true that $f(l,k)=o(k)\cdot l^{k-1}$?

We have also constructed a tournament with $f(l,k)-1$ vertices, every edge
colouring of which contains an $l$-flash or a $k$-rainbow. Are there
tournaments with $o(f(l,k))$ vertices that satisfy this? We believe random
tournaments are good candidates.

######  Problem 5.2.

What is the minimal $n$ such that, for a uniformly random tournament on $n$
vertices, with high probability every edge colouring contains an $l$-flash or
a $k$-rainbow?

Finally, we defined flashes and rainbows in tournaments to be walks, but it is
possible to consider the same problem with paths instead. This adds some
technical difficulties. For example, when we split a set of vertices according
to the longest flash of colour $a$ ending in those vertices, it is no longer
guaranteed that each resulting set contains no edge of colour $a$: the
vertices in a directed cycle of colour $a$ could all end up in the same set.
However, Conjecture 1.7 could still hold in this more restrictive setting.

######  Conjecture 5.3.

Let $l$ and $k$ be positive integers and let $T$ be a tournament with
$l^{k-1}+1$ vertices. Then every edge colouring of $T$ contains a directed
monochromatic path of length $l$ or a directed rainbow path of length $k$.

## References

  * [And69] Ian Anderson (1969).  A variance method in combinatorial number theory.  _Glasgow Mathematical Journal_ 10, 126–129.
  * [BETK51] N. G. de Bruijn, Ca. van Ebbenhorst Tengbergen, and D. Kruyswijk (1951).  On the set of divisors of a number.  _Nieuw Archief voor Wiskunde (2)_ 23, 191–193.
  * [BLS19] Matija Bucić, Shoham Letzter, and Benny Sudakov (2019).  Monochromatic paths in random tournaments.  _Random Structures & Algorithms_ 54(1), 69–81.
  * [ER50] Paul Erdős and Richard Rado (1950).  A combinatorial theorem.  _Journal of the London Mathematical Society_ s1-25(4), 249–255.
  * [JM00] Tao Jiang and Dhruv Mubayi (2000).  New upper bounds for a canonical Ramsey problem.  _Combinatorica_ 20(1), 141–146.
  * [LR95] Hanno Lefmann and Vojtěch Rödl (1995).  On Erdős-Rado numbers.  _Combinatorica_ 15(1), 85–104.
  * [LRT92] Hanno Lefmann, Vojtěch Rödl, and Robin Thomas (1992).  Monochromatic vs multicolored paths.  _Graphs and Combinatorics_ 8(4), 323–332.
  * [Ram30] Frank P. Ramsey (1930).  On a problem of formal logic.  _Proceedings of the London Mathematical Society_ s2-30(1), 264–286.


* [134] Inkyu Sa et al.  “weednet: Dense semantic weed classification using multispectral images and mav for smart farming”  In _IEEE Robotics and Automation Letters_ 3.1 IEEE, 2017, pp. 588–595
  * [135] Inkyu Sa et al.  “Weedmap: a large-scale semantic weed mapping framework using aerial multispectral imaging and deep neural network for precision farming”  In _Remote Sensing_ 10.9 Multidisciplinary Digital Publishing Institute, 2018, pp. 1423
  * [136] Sajad Sabzi, Yousef Abbaspour-Gilandeh and Juan Ignacio Arribas  “An automatic visible-range video weed detection, segmentation and classification prototype in potato field”  In _Heliyon_ 6.5 Elsevier, 2020, pp. e03685
  * [137] Linda Sakyi  “Linda Sakyi”  In _Greenroot Limited_ , 2019  URL: https://greenrootltd.com/2019/02/19/five-general-categories-of-weed-control-methods/
  * [138] T Sarvini et al.  “Performance Comparison of Weed Detection Algorithms”  In _2019 International Conference on Communication and Signal Processing (ICCSP)_ , 2019, pp. 0843–0847  IEEE
  * [139] Santhosh K Seelan, Soizik Laguette, Grant M Casady and George A Seielstad  “Remote sensing applications for precision agriculture: A learning community approach”  In _Remote sensing of environment_ 88.1-2 Elsevier, 2003, pp. 157–169
  * [140] Saraswathi Shanmugam et al.  “Automated Weed Detection Systems: A Review”  In _KnE Engineering_ , 2020, pp. 271–284
  * [141] Shaun M Sharpe, Arnold W Schumann and Nathan S Boyd  “Detection of Carolina geranium (Geranium carolinianum) growing in competition with strawberry using convolutional neural networks”  In _Weed Science_ 67.2 BioOne, 2019, pp. 239–245
  * [142] Shaun M Sharpe, Arnold W Schumann and Nathan S Boyd  “Goosegrass Detection in Strawberry and Tomato Using a Convolutional Neural Network”  In _Scientific Reports_ 10.1 Nature Publishing Group, 2020, pp. 1–8
  * [143] Evan Shelhamer, Jonathan Long and Trevor Darrell  “Fully convolutional networks for semantic segmentation”  In _IEEE transactions on pattern analysis and machine intelligence_ 39.4, 2017, pp. 640–651
  * [144] Connor Shorten and Taghi M Khoshgoftaar  “A survey on image data augmentation for deep learning”  In _Journal of Big Data_ 6.1 Springer, 2019, pp. 60
  * [145] Karen Simonyan and Andrew Zisserman  “Very deep convolutional networks for large-scale image recognition”  In _arXiv preprint arXiv:1409.1556_ , 2014
  * [146] Arun Narenthiran Veeranampalayam Sivakumar et al.  “Comparison of Object Detection and Patch-Based Classification Deep Learning Models on Mid-to Late-Season Weed Detection in UAV Imagery”  In _Remote Sensing_ 12.13 Multidisciplinary Digital Publishing Institute, 2020, pp. 2136
  * [147] Soren Skovsen et al.  “The GrassClover Image Dataset for Semantic and Hierarchical Species Understanding in Agriculture”  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_ , 2019
  * [148] Russell Stewart, Mykhaylo Andriluka and Andrew Y Ng  “End-to-end people detection in crowded scenes”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 2325–2333
  * [149] Wen-Hao Su  “Advanced Machine Learning in Point Spectroscopy, RGB-and Hyperspectral-Imaging for Automatic Discriminations of Crops and Weeds: A Review”  In _Smart Cities_ 3.3 Multidisciplinary Digital Publishing Institute, 2020, pp. 767–792
  * [150] Kaspars Sudars et al.  “Dataset of annotated food crops and weed images for robotic computer vision control”  In _Data in Brief_ Elsevier, 2020, pp. 105833
  * [151] Hyun K Suh, Joris Ijsselmuiden, Jan Willem Hofstee and Eldert J Henten  “Transfer learning for the classification of sugar beet and volunteer potato under field conditions”  In _Biosystems engineering_ 174 Elsevier, 2018, pp. 50–65
  * [152] Christian Szegedy et al.  “Going deeper with convolutions”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 1–9
  * [153] Aboozar Taherkhani, Georgina Cosma and T Martin McGinnity  “AdaBoost-CNN: An adaptive boosting algorithm for convolutional neural networks to classify multi-class imbalanced datasets using transfer learning”  In _Neurocomputing_ 404 Elsevier, 2020, pp. 351–366
  * [154] Ryo Takahashi, Takashi Matsubara and Kuniaki Uehara  “Ricap: Random image cropping and patching data augmentation for deep cnns”  In _Asian Conference on Machine Learning_ , 2018, pp. 786–798
  * [155] JingLei Tang et al.  “Weed identification based on K-means feature learning combined with convolutional neural network”  In _Computers and electronics in agriculture_ 135 Elsevier, 2017, pp. 63–70
  * [156] Andrew Tao, Jon Barker and Sriya Sarathy  “Detectnet: Deep neural network for object detection in digits”  In _Parallel Forall_ 4, 2016
  * [157] Nima Teimouri et al.  “Weed growth stage estimator using deep convolutional neural networks”  In _Sensors_ 18.5 Multidisciplinary Digital Publishing Institute, 2018, pp. 1580
  * [158] L Tian, DC Slaughter and RF Norris  “Machine vision identification of tomato seedlings for automated weed control”  In _Transactions of ASAE_ 40.6 Citeseer, 2000, pp. 1761–1768
  * [159] Vo Hoang Trong, Yu Gwang-hyun, Dang Thanh Vu and Kim Jin-young  “Late fusion of multimodal deep neural networks for weeds classification”  In _Computers and Electronics in Agriculture_ 175 Elsevier, 2020, pp. 105506
  * [160] S Umamaheswari, R Arjun and D Meganathan  “Weed Detection in Farm Crops using Parallel Image Processing”  In _2018 Conference on Information and Communication Technology (CICT)_ , 2018, pp. 1–4  IEEE
  * [161] S Umamaheswari and Ashvini V Jain  “Encoder–Decoder Architecture for Crop-Weed Classification Using Pixel-Wise Labelling”  In _2020 International Conference on Artificial Intelligence and Signal Processing (AISP)_ , 2020, pp. 1–6  IEEE
  * [162] J Valente, M Doldersum, C Roers and L Kooistra  “DETECTING RUMEX OBTUSIFOLIUS WEED PLANTS IN GRASSLANDS FROM UAV RGB IMAGERY USING DEEP LEARNING.”  In _ISPRS Annals of Photogrammetry, Remote Sensing & Spatial Information Sciences_ 4, 2019
  * [163] Viraf  “Create A Synthetic Image Dataset - The ”What”, The ”Why” and The ”How””  In _Medium_ Towards Data Science, 2020  URL: https://towardsdatascience.com/create-a-synthetic-image-dataset-the-what-the-why-and-the-how-f820e6b6f718
  * [164] Aichen Wang, Yifei Xu, Xinhua Wei and Bingbo Cui  “Semantic Segmentation of Crop and Weed using an Encoder-Decoder Network and Image Enhancement Method under Uncontrolled Outdoor Illumination”  In _IEEE Access_ 8 IEEE, 2020, pp. 81724–81734
  * [165] Aichen Wang, Wen Zhang and Xinhua Wei  “A review on weed detection using ground-based machine vision and image processing techniques”  In _Computers and electronics in agriculture_ 158 Elsevier, 2019, pp. 226–240
  * [166] Alexander Wendel and James Underwood  “Self-supervised weed detection in vegetable crops using ground based hyperspectral imaging”  In _2016 IEEE international conference on robotics and automation (ICRA)_ , 2016, pp. 5128–5135  IEEE
  * [167] DM Woebbecke, GE Meyer, K Von Bargen and DA Mortensen  “Shape features for identifying young weeds using image analysis”  In _Transactions of the ASAE_ 38.1 American Society of AgriculturalBiological Engineers, 1995, pp. 271–281
  * [168] Xue Yan, Xiangwu Deng and Jing Jin  “Classification of weed species in the paddy field with DCNN-Learned features”  In _2020 IEEE 5th Information Technology and Mechatronics Engineering Conference (ITOEC)_ , 2020, pp. 336–340  IEEE
  * [169] Zhang Yi, Shen Yongliang and Zhang Jun  “An improved tiny-yolov3 pedestrian detection algorithm”  In _Optik_ 183 Elsevier, 2019, pp. 17–23
  * [170] Jialin Yu et al.  “Weed Detection in Perennial Ryegrass With Deep Learning Convolutional Neural Network”  In _Frontiers in plant science_ 10 Frontiers Media SA, 2019
  * [171] Jialin Yu, Shaun M Sharpe, Arnold W Schumann and Nathan S Boyd  “Deep learning for image-based weed detection in turfgrass”  In _European journal of agronomy_ 104 Elsevier, 2019, pp. 78–84
  * [172] Rufei Zhang et al.  “Weed location and recognition based on UAV imaging and deep learning”  In _International Journal of Precision Agricultural Aviation_ 3.1, 2020
  * [173] Wenhao Zhang et al.  “Broad-leaf weed detection in pasture”  In _2018 IEEE 3rd International Conference on Image, Vision and Computing (ICIVC)_ , 2018, pp. 101–105  IEEE
  * [174] Xiao-Yu Zhang, Haichao Shi, Xiaobin Zhu and Peng Li  “Active semi-supervised learning based on self-expressive correlation with generative adversarial networks”  In _Neurocomputing_ 345 Elsevier, 2019, pp. 103–113
  * [175] Yang Zheng et al.  “Maize and weed classification using color indices with support vector data description in outdoor fields”  In _Computers and Electronics in Agriculture_ 141 Elsevier, 2017, pp. 215–222
  * [176] Zhi-Hua Zhou  “A brief introduction to weakly supervised learning”  In _National Science Review_ 5.1 Oxford University Press, 2018, pp. 44–53