$(a_1, \dots, a_k)$ such that $\forall i, (x_i^1, \dots, x_i^k), (a_1, \dots, a_k) \in E'$. Let $1 \le j \le k$ then by the fact that $G$ is $k$-to-1 we have that there exists $a_j$ such that $\forall i \le k, (x_i^j, a_1) \in E$. This in turns proves $\forall i, (x_i^1, \dots, x_i^k), (a_1, \dots, a_k) \in E'$. $\square$

The second lemma is bit more technical. It shows how to define from a set $V$ a graph on $V^k$ which has the $k$-to-1 property. This construction generalizes the definition of the third colour in the example above: we define edges between two $k$-tuples if and only if they are different but coincide on at least one coordinate.

**LEMMA 7.** Let $V$ be a set of size at least $k+1$. Define $G = (V^k, E)$ a graph where $(x_1, \dots, x_k) \to (y_1, \dots, y_k)$ if and only if $\exists j, x_j = y_j$ and $(x_1, \dots, x_k) \ne (y_1, \dots, y_k)$. Then $G$ is $k$-to-1.

**PROOF.** Let $(x_1^1, \dots, x_k^1)_{1 \le i \le k}$ be a family of $k$ vertices of $G$. the superscript $j$ denotes the $j$-th coordinate and the subscript $i$ the vertex number $i$. We distinguish two cases:

* For all coordinates $1 \le j \le k$ the $x_i^j$ are pairwise different. Formally this is written as $\forall j \in [1; k], \forall p, q \in [1; k], x_p^j \ne x_q^j$. In that case call $y$ the vertex $(x_1^1, x_2^2, \dots, x_k^k)$. We have that $\forall i, (x_i^1, \dots, x_i^k) \to y$. Indeed the $i$-th coordinate of $y$ is equal to that of $(x_i^1, \dots, x_i^k)$, and $y$ is different from $(x_i^1, \dots, x_i^k)$ because (for instance) the first coordinate of $y$ is different from $x_i^1$, this is by assumption.

* There is a coordinate where two vertices are equal. Let us assume WLOG that $x_1^1 = x_2^1$. Set $y = (x_1^1, x_2^2, x_3^4, x_5^4, \dots, x_k^{k-1}, r)$ where $r$ is a number different from all $x_i^k$ for all $1 \le i \le k$, such a $r$ exists because $|V| \ge k+1$. Then by construction $y$ shares at least one common coordinates with all vertices $(x_i^1, \dots, x_i^k)$, and $y$ is different from all such vertices because of the last coordinate. Thus $\forall i, (x_i^1, \dots, x_i^k) \to y$.

We have therefore proven that $G$ is $k$-to-1. $\square$

We will now use these two technical results to define a construction which produces a $(p+1, k)$-good coloured graph from a $(p, k)$-good coloured graph. This construction mimicks the simple example above, and consists in considering the $k$-th product of the graph $G$, and introducing a new set of edges defined as in 7 for an additional colour. From the two previous lemmas and the fact that $G$ was winning, this new graph has the $k$-to-1 property for all its $k+1$ colours. We will then have to check that it has the non-cyclic property as well.

Let us define this new graph more formally to establish notations.

**Definition C.5** (Construction of $G^{(p+1)}$). Let $G^{(p)} = (V, E)$ be a $p$-coloured directed graph, we define $G^{(p+1)}$ as follows:

* the set of vertices is $V^k$, where $V$ is the set of vertices of $G$;

* for $i \le p$, edges coloured $i$ are given by $(x_1, \dots, x_k) \xrightarrow{i} (y_1, \dots, y_k)$ iff $\forall j \le k, x_j \xrightarrow{i} y_j$ in graph $G^{(p)}$

* edges coloured $p+1$ are given by $(x_1, \dots, x_k) \xrightarrow{p+1} (y_1, \dots, y_k)$ if and only if $\exists j, x_j = y_j$ and $(x_1, \dots, x_k) \ne (y_1, \dots, y_k)$.

Now, we can show the main result which shows that if the graph $G^{(p)}$ was providing winning strategies for the game $G^N(p, k)$, then the new graph $G^{(p+1)}$ we defined provides winning strategies for the game $G^N(p+1, k)$.

**THEOREM 35.** If $G^{(p)} = (V, E)$ is a $(p, k)$-good coloured graph, then $G^{(p+1)}$ is a $(p+1, k)$-good coloured graph.
PROOF. By theorem 30, this amounts to showing that $G^{(p+1)}$ has the following properties.

* The edges coloured $i \le p$ have the $k$-to-1 property: this is a consequence of lemma 6 and the fact that $G^{(p)}$ had the $k$-to-1 property for all its colours.

* The edges coloured $p+1$ satisfy the $k$-to-1 property: this is a direct consequence of lemma 7.

* There are no polychromatic cycles of length 1: this is clear from the definitions.

* There are no polychromatic cycles of length $l \in \mathbb{N}$ when $2 \le l \le p+1$. Suppose there exists such a polychromatic cycle

$$ (x_1^1, \dots, x_k^1) \xrightarrow{c_1} (x_1^2, \dots, x_k^2) \xrightarrow{c_2} \dots \xrightarrow{c_{l-1}} (x_1^l, \dots, x_k^l) \xrightarrow{c_l} (x_1^1, \dots, x_k^1). $$

Then since the cycle is polychromatic then the colours $c_i$ are pairwise disjoint. We have two possibilities:

(1) All colours involved are $< p+1$. That is: $\forall i, c_i \neq p+1$. Then $l \le p$, and for each different coordinate we have a polychromatic cycle of length $\le l$ in $G^{(p)}$, which contradicts that $G^{(p)}$ was $(p, k)$-good.

(2) One of the edges in the cycle is coloured $p+1$, i.e. $\exists i, c_i = p+1$. We can then suppose without loss of generality that $c_l = p+1$ and that $x_1^l = x_1^1$. Then this implies that the following cycle exists in $G^{(p)}$:

$$ (x_1^1) \xrightarrow{c_1} (x_1^2) \xrightarrow{c_2} \dots \xrightarrow{c_{l-1}} (x_1^l). $$

This cycle is polychromatic cycle and of length $\le p$, contradicting the fact that $G^{(p)}$ is $(p, k)$-good. $\square$

From this result, we get a new bound on $\mathfrak{B}(p, k, 1)$. This bound is better than the one in section 5 but uses non-oblivious strategies, hence does not provide an answer to the existence of $k$-paradoxical tournaments without cycles of length $\le p$.

THEOREM 36 (BOUND ON $\mathfrak{B}(p, k, 1)$). $\forall p, k \in \mathbb{N}, \mathfrak{B}(p, k, 1) \le 2^{5k^{p-1}}$

PROOF. From a winning graph for $G^N(p, k)$ we can construct a winning graph for $G^{Nk}(p+1, k)$, thus $\mathfrak{B}(p+1, k, 1) \le (\mathfrak{B}(p, k, 1))^k$. Moreover $\mathfrak{B}(2, k, 1) \le 13k^3 2^k$ (see corollary 3). By direct induction we can establish $\mathfrak{B}(p, k, 1) \le (13k^2 2^k)^{k^{p-2}}$, basic arithmetic shows that this is less than $2^{5k^{p-1}}$ for all $p$ and $k$. $\square$

Note that this bound is better than the one of corollary 1. However despite appearances it is only marginally better for the purpose of establishing a hierarchy for $K^t$. Moreover the complexity of constructing a winning graph strategy of size $N$ following the construction of C.5 seems to be in $O(N^2)$, but remember that $N = 2^n$ where $n$ is the bitsize of the outants. To have efficient graph strategies for the purpose of establishing a hierarchy for $K^t$ we would like to be able to determine if two vertices of $G^{(p)}$ are neighbor in time $O(n)$. This is unclear to us for the moment. At any rate, we will use in section 7 the strategy from section 5 for establishing the main theorem of this paper.

## D REASONABLE FUNCTIONS

In this appendix we study reasonable functions. We first recall the definition of reasonable functions as stated in chapter 3, the notion of reasonability is meant to capture functions which grow to infinity not slower than $n \mapsto K^{2n}(n)$. On its own would be interesting to
establish that the composition of two reasonable functions is a reasonable function. We leave it as an open question for now.

**Definition D.1 (Very-time-computable functions).** Let $f$ be a function from $N \mapsto N$, $f$ is very-time-computable (VTC) if there exists a machine $M$ in $\text{DTIME}(f(n) + n)$ such that $\forall n, M(n) = f(n)$.

**Definition D.2 (d-reasonable function).** Let $d \in N$, and $f: N \mapsto N$ be an increasing function, it is d-reasonable if $\forall c, \exists_{\infty} n, cK^{dn}(n) \le f(n)$

This is not the same definition as in chapter , but it is equivalent to it by theorem 37.

**Definition D.3 (Reasonable functions).** A function $f: N \mapsto N$ is reasonable if there exist $d \in N$ such that $f$ is d-reasonable.

One can notice in the definition of reasonable functions that there is an exponential discrepancy between the size of $n$ which is $\log(n)$ and the running time which is $dn$. This discrepancy was all we needed in the paper but may seem a bit arbitrary in general, in the following definition we define a more natural notion, this notion may be more deserving of the epithet "reasonable". In any case theorem 37 states that all of these notions are actually equivalent.

**Definition D.4 (Ultra-reasonable functions).** Let $f \in N \mapsto N$, $f$ is said to be ultra-reasonable if $f$ is increasing and such that $\forall \epsilon \in \mathbb{R}^{+}, \forall c, \exists_{\infty} n, cK^{(1+\epsilon)\log(n)}(n) \le f(n)$

**Fact.** Any ultra-reasonable function is 1-reasonable

**Definition D.5 (Iterated logarithm $\log^{(k)}(n)$).** Let $k \in N$. The $k$-iterated logarithm, denoted by $\log^{(k)}(n) : N \mapsto N$, is defined recursively as follows:

* $\log^{(1)}(n) = [\log(n)]$, where $\log(n)$ is the logarithm of $n$ in base 2.

* For $k > 1$, $\log^{(k)}(n) = [\log(\log^{(k-1)}(n))]$.

Next we define the arrow operation in a slightly unusual way

**Definition D.6 ($\uparrow_k$ (Arrow Operation)).** For natural numbers $a$ and $k$, $a \uparrow_k: N \mapsto$ is defined recursively as:

$$a \uparrow_1 (n) = a^n,$$

$$a \uparrow_{k+1} (n) = a^{(a^{\uparrow_k(n)})}.$$

Noted differently:

$$a \uparrow_k (n) = \underbrace{a^{a^{\cdot \cdot \cdot a^n}}}_{k \text{ times}}.$$

2 $\uparrow_k$ is easily computable. For any $k \in N$, $n \mapsto 2 \uparrow_k(n)$ can be computed in less than $1.1 \cdot 2 \uparrow_{k-1}(n)$ steps

**PROOF.** This is entailed by the fact that for $k = 1, n \mapsto 2^n$ is computed in time $n+O(\log(n))$ (reminder that the bitsize of $2^n$ is $n$). $\square$

**LEMMA 8.** Let $f$ be $d$-reasonable, then $f(\log \log)$ is ultrareasonable.
PROOF. Let $c \in \mathbb{N}$, Take $n$ such that $\#^d n$ is a description of $n$ of size $f(n)/c$ decodable in $dn$ steps, infinitely many such $n$ must exist by reasonability of $f$. Consider program $p$ which takes as input $\#^d n$, decodes it, and outputs $2^{2^n}$. Note that program $p$ runs in time $dn + 2 \cdot 2^n$ (by fact D) and the size of $p$ is $\le \frac{f(n)}{2c} + O(1) \le \frac{f(n)}{c}$ for $n$ big enough.

We thus have that:

$$ \exists_{\infty} n, K^{dn+2^n} (2^{2^n}) \le \frac{f(n)}{c}, \\ \Rightarrow \exists_{\infty} m, K^{d \log \log m + \log m} (m) \le \frac{f(\log \log(m))}{c} $$

Hence $f(\log \log)$ is ultrareasonable.

COROLLARY 5. Let $f$ be reasonable, $k \in \mathbb{N}$ then $f(\log^{(k)})$ is reasonable.

**Fact.** Let $f, g$ be two functions such that $f \le g$, if $f$ is reasonable then $g$ is reasonable.

As a direct corollary of fact D and lemma 8 we have that:

THEOREM 37 (EQUIVALENCE BETWEEN $d$-REASONABILITY AND ULTRAREASONABILITY).
Let $f$ be a reasonable function then it is $1$-reasonable and ultrareasonable.

LEMMA 9. Let $f$ be reasonable, let $h: \mathbb{N} \mapsto \mathbb{N}$ be the function $h(n) \stackrel{def}{=} \min(f(n), n)$, then $h$ is reasonable

PROOF. We have two possibilities:

Either we have $\forall_{\infty} n, h(n) = f(n)$ and then $h$ is reasonable.

Or $\exists_{\infty} n, h(n) = n$, but for all of these $n$ we have a program $p$ of size $\log(n)$ which prints $n$ in $\log(n) + O(1)$ steps thus $\exists_{\infty} n, K^{2\log(n)}(n) \le h(n)$ □

THEOREM 38. Let $f$ be $d$-reasonable, $k \in \mathbb{N}$, let $h: \mathbb{N} \mapsto \mathbb{N}$ be the function $h(n) \stackrel{def}{=} \min(f(n), \log^{(k)}(n))$, then $h$ is reasonable.

PROOF.

$$ \begin{array}{l} f \text{ reasonable} \\ \Rightarrow \min(f, n \mapsto n) \text{ reasonable} \\ \text{corollary 5} \\ \Rightarrow (\min(f, n \mapsto n)) \circ \log^{(k)} \text{ reasonable} \\ \text{log is increasing} \\ \Rightarrow \min(f \circ \log^{(k)}, \log^{(k)}) \text{ reasonable} \\ \text{fact D} \\ \Rightarrow \min(f, \log^{(k)}) \text{ reasonable} \end{array} $$

**Definition D.7** (Inverse of a function in $\mathbb{N} \mapsto \mathbb{N}$). Let $f \in \mathbb{N} \mapsto \mathbb{N}$, its inverse noted $f^{-1}$ is defined as $f^{-1}(n) = \min\{m; f(m) \ge n\}$

The following theorem is used liberally throughout the article

THEOREM 39. If $f$ is VTC and increasing and going to infinity then $f$ is ultrareasonable
PROOF. We define first define program $p$ which is meant to compute $f^{-1}$.

<caption>**Algorithm 3 Program $p(n)$ to compute $f^{-1}(n)$**</caption>

1: **Input:** $n$
2: **Initialize:** $i \leftarrow 0$
3: **while** True **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;**if** $f(i) \ge n$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** $i$
6: &nbsp;&nbsp;&nbsp;&nbsp;**else**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $i \leftarrow i + 1$
8: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
9: **end while**

Given that $h(n) \stackrel{\text{def}}{=} \min(f(n), \log(n))$ is VTC and less than $f$, $h$ being reasonable entails reasonability of $f$, we may thus WLOG consider in the following that $f \le \log(n)$.

It's routine to check that $p$ computes $f^{-1}$. The running time of $p$ is $\le \log(n) + \sum_{i=0}^{f^{-1}(n)} f(i) + i \le 2(f^{-1}(n))^2$ (we read $n$ and then execute the program, moreover $f^{-1}(n) \ge n$). The function $n \mapsto 2f^{-1}(n)$ is computed in less than $3(f^{-1}(n))^2 + \log(n)$ steps which is less than $2f^{-1}(n)$ steps hence:

$$ \begin{array}{l} \forall n, K^{2f^{-1}(n)} (2f^{-1}(n)) \le n \\ \text{Using the fact that } f \text{ grows to infinity} \\ \Rightarrow \exists \infty n, K^n(n) \le f(\log(n)) \le f(n) \end{array} $$

□

**THEOREM 40.** If $f$ is VTC and increasing and going to infinity then $\log(f)$ is VTC and increasing and going to infinity and reasonable.

PROOF. The fact that $\log(f)$ is increasing and going to infinity is obvious. Moreover if one can compute $f(n)$ in $T$ steps then $\log(f(n))$ can be computed in $T+O(\log(f(n))) \le O(f(n)+n)$. Hence $\log(f)$ is VTC. Reasonability comes from theorem 39. □

We leave the two following questions unanswered. We believe them to be of interest on their own and tractable.

**Question 7.** • If $f$ is reasonable then its inverse $f^{-1}$ is reasonable ?

• Let $f$ and $g$ be two reasonable functions then $f \circ g$ is reasonable ?