# On quantitative aspects of a canonisation theorem for edge-orderings

Christian Reiher  Fachbereich Mathematik, Universität Hamburg, Hamburg,
Germany<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>,  Vojtěch Rödl  Department of Mathematics, Emory
University, Atlanta, USA<EMAIL_ADDRESS><EMAIL_ADDRESS>,
Marcelo Sales  ,  Kevin Sames  and  Mathias Schacht

###### Abstract.

For integers $k\geq 2$ and $N\geq 2k+1$ there are $k!2^{k}$ canonical
orderings of the edges of the complete $k$-uniform hypergraph with vertex set
$[N]=\\{1,2,\dots,N\\}$. These are exactly the orderings with the property
that any two subsets $A,B\subseteq[N]$ of the same size induce isomorphic
suborderings. We study the associated canonisation problem to estimate, given
$k$ and $n$, the least integer $N$ such that no matter how the $k$-subsets of
$[N]$ are ordered there always exists an $n$-element set $X\subseteq[N]$ whose
$k$-subsets are ordered canonically. For fixed $k$ we prove lower and upper
bounds on these numbers that are $k$ times iterated exponential in a
polynomial of $n$.

The second author is supported by NSF grant DMS 1764385.

The third author is partially supported by NSF grant DMS 1764385.

The fifth author is supported by the ERC (PEPCo 724903)

##  1\. Introduction

We consider numerical aspects of an unpublished result of Klaus Leeb from the
early seventies (see [NPRV85, NR17]). For a natural number $N$ we set
$[N]=\\{1,2,\dots,N\\}$. Given a set $X$ and a nonnegative integer $k$ we
write $X^{(k)}=\\{e\subseteq X\colon|e|=k\\}$ for the set of all $k$-element
subsets of $X$.

###  1.1. Ramsey theory

Recall that for any integers $k,n,r\geq 1$, Ramsey’s theorem [Ramsey30]
informs us that every sufficiently large integer $N$ satisfies the partition
relation

$N\longrightarrow(n)^{k}_{r}\,,$ (1.1)

meaning that for every colouring of $[N]^{(k)}$ with $r$ colours there exists
a set $X\subseteq[N]$ of size $n$ such that $X^{(k)}$ is monochromatic. The
least number $N$ validating (1.1) is denoted by $\mathrm{R}^{(k)}(n,r)$. The
negative partition relation $N\mathrel{\mkern
5.5mu\arrownot\mkern-5.5mu}\longrightarrow(n)^{k}_{r}$ expresses the fact that
(1.1) fails.

For colourings $f\colon[N]^{(k)}\longrightarrow{\mathds{N}}$ with infinitely
many colours, however, one can, in general, not even hope to obtain a
monochromatic set of size $k+1$. For instance, it may happen that every
$k$-element subset of $[N]$ has its own private colour. Nevertheless, Erdős
and Rado [ER52, ER50] established a meaningful generalisation of Ramsey’s
theorem to colourings with infinitely many colours, even if the ground sets
stay finite. In this context it is convenient to regard such colourings as
equivalence relations, two $k$-sets being in the same equivalence class if and
only if they are of the same colour. Now Erdős and Rado [ER52, ER50] call an
equivalence relation on $[N]^{(k)}$ canonical if for any two subsets
$A,B\subseteq[N]$ of the same size the equivalence relations induced on
$A^{(k)}$ and $B^{(k)}$ correspond to each other via the order preserving map
between $A$ and $B$. So, roughly speaking, an equivalence relation is
canonical if you cannot change its essential properties by restricting your
attention to a subset. It turns out that for $N\geq 2k+1$ there are always
exactly $2^{k}$ canonical equivalence relations on $[N]^{(k)}$ that can be
parametrised by subsets $I\subseteq[k]$ in the following natural way. Let
$x,y\in[N]^{(k)}$ be two $k$-sets and let $x=\\{x_{1},\dots,x_{k}\\}$ as well
as $y=\\{y_{1},\dots,y_{k}\\}$ enumerate their elements in increasing order.
We write $x\equiv_{I}y$ if and only if $x_{i}=y_{i}$ holds for all $i\in I$.
Now $\\{\equiv_{I}\colon I\subseteq[k]\\}$ is the collection of all canonical
equivalence relations on $[N]^{(k)}$. The canonical Ramsey theorem of Erdős
and Rado asserts that given two integers $k$ and $n$ there exists an integer
$\operatorname{ER}^{(k)}(n)$ such that for every
$N\geq\operatorname{ER}^{(k)}(n)$ and every equivalence relation $\equiv$ on
$[N]^{(k)}$ there exists a set $X\subseteq[N]$ of size $n$ with the property
that $\equiv$ is canonical on $X^{(k)}$.

This result sparked the development of canonical Ramsey theory in the
seventies. Let us commemorate some contributions to the area due to Ronald
Graham, who was among the main protagonists of Ramsey theory in the
$20^{\mathrm{th}}$ century: Together with Erdős [EG80], he established a
canonical version of van der Waerden’s theorem, stating that if for
$N\geq\mathrm{EG}(k)$ we colour $[N]$ with arbitrarily many colours, then
there exists an arithmetic progression of length $k$ which is either
monochromatic or receives $k$ distinct colours. With Deuber, Prömel, and Voigt
[DGPV] he later obtained a canonical version of the Gallai-Witt theorem, which
is more difficult to state — in $d$ dimensions the canonical colourings for a
given configuration $F\subseteq{\mathds{Z}}^{d}$ are now parametrised by
vector subspaces $U\subseteq{\mathds{Q}}^{d}$ having a basis of vectors of the
form $x-y$ with $x,y\in F$. Interestingly, Ronald Graham was also among the
small number of co-authors of Klaus Leeb [GLR, GLK2] and in joint work with
Rothschild they settled a famous conjecture of Rota on Ramsey properties of
finite vector spaces.

The canonisation discussed here concerns linear orderings. We say that a
linear order $([N]^{(k)},\strictif)$ is canonical if for any two sets
$A,B\subseteq[N]$ of the same size the order preserving map from $A$ to $B$
induces an order preserving map from $(A^{(k)},\strictif)$ to
$(B^{(k)},\strictif)$. It turns out that for $N\geq 2k+1$ there are exactly
$k!2^{k}$ canonical orderings of $[N]^{(k)}$ that can uniformly be
parametrised by pairs $(\varepsilon,\sigma)$ consisting of a sign vector
$\varepsilon\in\\{-1,+1\\}^{k}$ and a permutation $\sigma\in\mathfrak{S}_{k}$,
i.e., a bijective map $\sigma\colon[k]\longrightarrow[k]$.

######  Definition 1.1.

Let $N,k\geq 1$ be integers, and let
$(\varepsilon,\sigma)\in\\{+1,-1\\}^{k}\times\mathfrak{S}_{k}$ be a pair
consisting of a sign vector
$\varepsilon=(\varepsilon_{1},\dots,\varepsilon_{k})$ and a permutation
$\sigma$ of $[k]$. The ordering on $[N]^{(k)}$ associated with
$(\varepsilon,\sigma)$ is the unique ordering with the property that if

$1\leq a_{1}<\dots<a_{k}\leq N\quad\text{ and }\quad 1\leq
b_{1}<\dots<b_{k}\leq N\,,$

then

$\\{a_{1},\dots,a_{k}\\}\strictif\\{b_{1},\dots,b_{k}\\}\,\,\,\Longleftrightarrow\,\,\,(\varepsilon_{\sigma(1)}a_{\sigma(1)},\dots,\varepsilon_{\sigma(k)}a_{\sigma(k)})<_{\mathrm{lex}}(\varepsilon_{\sigma(1)}b_{\sigma(1)},\dots,\varepsilon_{\sigma(k)}b_{\sigma(k)})\,,$

where $<_{\mathrm{lex}}$ denotes the lexicographic order on
${\mathds{Z}}^{k}$.

It is readily seen that such an ordering associated with
$(\varepsilon,\sigma)$ does indeed exist, that it is uniquely determined, and,
moreover, canonical. Conversely, for $N\geq 2k+1$ every canonical ordering is
of this form (see Lemma 3.8 below). We proceed by stating the aforementioned
unpublished theorem due to Klaus Leeb.

######  Theorem 1.2 (Leeb).

For all positive integers $k$ and $n$ there exists an integer
$\mathrm{L}^{(k)}(n)$ such that for every $N\geq\mathrm{L}^{(k)}(n)$ and every
ordering $([N]^{(k)},\strictif)$ there is a set $X\subseteq[N]$ of size $n$
such that $(X^{(k)},\strictif)$ is canonical.

In the sequel, $\mathrm{L}^{(k)}(n)$ will always refer to the least number
with this property. As we shall prove, for fixed $k\geq 2$ the dependence of
$\mathrm{L}^{(k)}(n)$ on $n$ is $k$ times exponential in a polynomial of $n$.

###  1.2. Bounds

The study of the Ramsey numbers $\mathrm{R}^{(k)}(n,r)$ has received extensive
interest (see e.g. [EHR65, CFS10, GRS90, EH72]). To state some of the
currently known bounds, one recursively defines tower functions
$t_{k}\colon{\mathds{N}}\longrightarrow{\mathds{N}}$ by

$t_{0}(x)=x\quad\text{ and }\quad t_{i+1}(x)=2^{t_{i}(x)}\,.$

Arguing probabilistically Erdős [Er47] showed that $\mathrm{R}^{(2)}(n,2)\geq
2^{(n+1)/2}$ and Erdős, Hajnal, and Rado [EHR65] proved later that
$\mathrm{R}^{(k)}(n,2)\geq t_{k-2}(cn^{2})$ for $k>2$, where $c$ is a positive
constant. They also proved $\mathrm{R}^{(k)}(n,4)\geq t_{k-1}(c_{k}n)$ for all
$k\geq 2$, where $c_{k}>0$ is an absolute constant. In the other direction, it
is known that $\mathrm{R}^{(k)}(n,r)\leq t_{k-1}(C_{k,r}n)$.

Estimates on the canonical Ramsey numbers $\operatorname{ER}^{(k)}(n)$ were
studied in [LR95, Sh96]. Notably, Lefmann and Rödl proved the lower bound
$\operatorname{ER}^{(k)}(n)\geq t_{k-1}(c_{k}n^{2})$, while Shelah obtained
the complementary upper bound $\operatorname{ER}^{(k)}(n)\leq
t_{k-1}(C_{k}n^{8(2k-1)})$.

Let us now turn our attention to the Leeb numbers $\mathrm{L}^{(k)}(n)$. For
$k=1$, there exist only two canonical orderings of $[N]^{(1)}$, namely the
“increasing” and the “decreasing” one corresponding to the sign vectors
$\varepsilon=(+1)$ and $\varepsilon=(-1)$, respectively. Thus the well-known
Erdős-Szekeres theorem [ES35] yields the exact value
$\mathrm{L}^{(1)}(n)=(n-1)^{2}+1$. Accordingly, Leeb’s theorem can be viewed
as a multidimensional version of the Erdős-Szekeres theorem and we refer to
[Lang] for further variations on this theme. Our own results can be summarised
as follows.

######  Theorem 1.3.

If $n\geq 4$ and $R\mathrel{\mkern
5.5mu\arrownot\mkern-5.5mu}\longrightarrow(n-1)^{2}_{2}$, then
$\mathrm{L}^{(2)}(n)>2^{R}$. Moreover, if $n\geq k\geq 3$, then
$\mathrm{L}^{(k)}(4n+k)>2^{\mathrm{L}^{(k-1)}(n)-1}$.

Due to the known lower bounds on diagonal Ramsey numbers this implies

$\mathrm{L}^{(2)}(n)\geq t_{2}(n/2)\quad\text{as well as
}\quad\mathrm{L}^{(k)}(n)\geq t_{k}(c_{k}n)\text{ for }k\geq 3\,.$

We offer an upper bound with the same number of exponentiations.

######  Theorem 1.4.

For every $k\geq 2$ there exists a constant $C_{k}$ such that
$\mathrm{L}^{(k)}(n)\leq t_{k}(n^{C_{k}})$ holds for every $n\geq 2k$.

The case $k=2$ of Theorems 1.3 and 1.4 was obtained independently by Conlon,
Fox, and Sudakov in unpublished work [Fox].

### Organisation

We prove Theorem 1.3 in Section 2. The upper bound, Theorem 1.4, is
established in Section 3. Lemma 3.3 from this proof turns out to be applicable
to Erdős-Rado numbers as well and Section 4 illustrates this by showing a
variant of Shelah’s result, namely $\operatorname{ER}^{(k)}(n)\leq
t_{k-1}(C_{k}n^{6k})$.

##  2\. Lower bounds: Constructions

###  2.1. Trees and combs

Our lower bound constructions take inspiration from the negative stepping-up
lemma due to Erdős, Hajnal, and Rado [EHR65]. Notice that in order to prove an
inequality of the form $\mathrm{L}^{(k)}(n)>N$ one needs to exhibit a special
ordering $([N]^{(k)},\strictif)$ for which there is no set $Z\subseteq[N]$ of
size $n$ such that orders $Z^{(k)}$ canonically. For us, $N=2^{m}$ will always
be a power of two and for reasons of visualisability we identify the numbers
in $[N]$ with the leaves of a binary tree of height $m$. We label the levels
of our tree from the bottom to the top with the numbers in $[m]$. So the root
is at level $1$ and the leaves are immediately above level $m$ (see Figure
2.1).

$1$$2$$3$$4$$5$$6$$7$$8$$1$$2$$3$ Figure 2.1. The binary tree and its levels
for $m=3$.

Alternatively, we can identify $[N]$ with the set $\\{+1,-1\\}^{m}$ of all
$\pm 1$-vectors of length $m$ such that the standard ordering on $[N]$
corresponds to the lexicographic one on $\\{+1,-1\\}^{m}$. The literature
often works with the number $0$ instead of $-1$ here, but for the application
we have in mind our choice turns out to be advantageous.

Now every set $X\subseteq[N]$ generates a tree $T_{X}$, which is the subtree
of our binary tree given by the union of the paths from the leaves in $X$ to
the root (see Figure 2.2).

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

An essential observation on which both the double-exponential lower bound
construction for the four-colour Ramsey number of triples and our lower bound
on $\mathrm{L}^{(2)}(n)$ rely is that there are two essentially different
kinds of triples: those engendering a “left tree” and those engendering a
“right tree”. Roughly speaking the difference is that when descending from the
leaves to the root, the two elements concurring first are the two smaller ones
for left trees and the two larger ones for right trees. For instance, Figure
2.2 displays a left tree.

To make these notions more precise we introduce the following notation. Given
at least two distinct vectors $x_{1},\dots,x_{t}\in\\{-1,+1\\}^{m}$ with
coordinates $x_{i}=(x_{i1},\dots,x_{im})$ we write

$\delta(x_{1},\dots,x_{t})=\min\\{\mu\in[m]\colon
x_{1\mu}=\dots=x_{t\mu}\text{ is not the case}\\}\,.$

for the first level where two of them differ.

Now let $xyz\in[N]^{(3)}$ be an arbitrary triple with $x<y<z$ and set
$\delta=\delta(x,y,z)$. This means that $x$, $y$, and $z$ agree in the first
$\delta-1$ coordinates, while their entries in the $\delta^{\mathrm{th}}$
coordinate, which we denote by $x_{\delta}$, $y_{\delta}$, $z_{\delta}$, fail
to coincide. As a consequence of $x<y<z$ we know $x_{\delta}\leq
y_{\delta}\leq z_{\delta}$. Thus $x_{\delta}=-1$, $z_{\delta}=+1$, and there
remain two possibilities: Depending on whether $y_{\delta}=-1$ or
$y_{\delta}=+1$ we say that $xyz$ forms a left tree or a right tree,
respectively. Equivalently, $xyz$ yields a left tree whenever
$\delta(x,y)>\delta(y,z)$ and a right tree whenever $\delta(x,y)<\delta(y,z)$.

When the triples are coloured with $\\{\mathrm{left},\mathrm{right}\\}$
depending on whether they form left trees or right trees, the monochromatic
sets are called combs. More explicitly, for

$1\leq x_{1}<\dots<x_{t}\leq N$

the set $X=\\{x_{1},\dots,x_{t}\\}$ is a left comb if
$\delta(x_{1},x_{2})>\delta(x_{2},x_{3})>\dots>\delta(x_{t-1},x_{t})$ and a
right comb if
$\delta(x_{1},x_{2})<\delta(x_{2},x_{3})<\dots<\delta(x_{t-1},x_{t})$ (see
Figure 2.3). For instance, the empty set, every singleton, and every pair are
both a left comb and a right comb. Since every triple is either a left tree or
a right tree, triples are combs in exactly one of the two directions. Some
quadruples fail to be combs.

Figure 2.3. A left comb and a right comb.

###  2.2. Ordering pairs

Let us recall that for Ramsey numbers the negative stepping-up lemma shows,
e.g., that if $m\mathrel{\mkern
5.5mu\arrownot\mkern-5.5mu}\longrightarrow(n-1)^{2}_{2}$, then
$2^{m}\mathrel{\mkern 5.5mu\arrownot\mkern-5.5mu}\longrightarrow(n)^{3}_{4}$.
As we shall reuse the argument, we provide a brief sketch. Let
$f\colon[2^{m}]^{(3)}\longrightarrow\\{\mathrm{left},\mathrm{right}\\}$ be the
colouring telling us whether a triple generates a left tree or a right tree
and let $g\colon[m]^{(2)}\longrightarrow\\{+1,-1\\}$ be a colouring
exemplifying the negative partition relation $m\mathrel{\mkern
5.5mu\arrownot\mkern-5.5mu}\longrightarrow(n-1)^{2}_{2}$. Define a colouring

$h\colon[2^{m}]^{(3)}\longrightarrow\\{\mathrm{left},\mathrm{right}\\}\times\\{+1,-1\\}$

of the triples with four colours by

$h(xyz)=\bigl{(}f(xyz),g\bigl{(}\delta(xy),\delta(yz)\bigr{)}\bigr{)}$

whenever $1\leq x<y<z\leq 2^{m}$. If $Z\subseteq[2^{m}]$ is monochromatic with
respect to $h$, then, in particular, it needs to be monochromatic for $f$,
i.e., $Z$ is a comb. Thus, if $Z=\\{z_{1},\dots,z_{|Z|}\\}$ with
$z_{1}<z_{2}<\dots<z_{|Z|}$, then $\\{\delta(z_{i},z_{i+1})\colon i<|Z|\\}$ is
a set of size $|Z|-1$ whose pairs are monochromatic with respect to $g$, for
which reason $|Z|-1<n-1$. In other words, $h$ establishes the desired negative
partition relation $2^{m}\mathrel{\mkern
5.5mu\arrownot\mkern-5.5mu}\longrightarrow(n)^{3}_{4}$.

In the light of this reasoning it suffices to construct, in the same setup, an
ordering $([2^{m}]^{(2)},\strictif)$ such that for every triple
$e\in[2^{m}]^{(3)}$ the colour $h(e)$ from the foregoing paragraph determines
the “isomorphism type” of $(e^{(2)},\strictif)$ and vice versa. Let $xyz$ with
$1\leq x<y<z\leq 2^{m}$ be an arbitrary triple and set $\xi=\delta(xy)$ as
well as $\eta=\delta(yz)$. Our goal when constructing is that

if $xyz$ is a | and | then
---|---|---
left tree | $g(\eta,\xi)=+1$ |  $xy\strictif xz\strictif yz$,
left tree | $g(\eta,\xi)=-1$ |  $xy\strictif yz\strictif xz$,
right tree | $g(\xi,\eta)=+1$ |  $yz\strictif xy\strictif xz$,
right tree | $g(\xi,\eta)=-1$ |  $yz\strictif xz\strictif xy$.

If this can be accomplished, then every set $Z\subseteq[2^{m}]$, for which
$(Z^{(2)},\strictif)$ is ordered canonically, is monochromatic with respect to
the colouring $h$ and, therefore, the proof of $\mathrm{L}^{(2)}(n)>2^{m}$
will be complete.

Let us introduce one final piece of notation. Given a vector
$x=(x_{1},\dots,x_{m})\in\\{-1,+1\\}^{m}$ and $\delta\in[m]$ we define the
vector $x\ltimes\delta\in\\{-1,+1\\}^{m-\delta}$ by

$x\ltimes\delta=\bigl{(}x_{\delta+1}g(\delta,\delta+1),\dots,x_{m}g(\delta,m)\bigr{)}\,.$

Now let be an arbitrary ordering with the property that for any two distinct
pairs $xy$ and $x^{\prime}y^{\prime}$ with $x<y$ and $x^{\prime}<y^{\prime}$
the following statements hold.

  1. (0 )

If $\delta(xy)\neq\delta(x^{\prime}y^{\prime})$, then

$xy\strictif
x^{\prime}y^{\prime}\,\,\,\Longleftrightarrow\,\,\,\delta(x^{\prime}y^{\prime})<\delta(xy)\,.$

  2. (0 )

If $\delta=\delta(xy)=\delta(x^{\prime}y^{\prime})$ and at least one of
$x\ltimes\delta\neq x^{\prime}\ltimes\delta$ or $y\ltimes\delta\neq
y^{\prime}\ltimes\delta$ holds, then

$xy\strictif
x^{\prime}y^{\prime}\,\,\,\Longleftrightarrow\,\,\,(x\ltimes\delta)\circ(y\ltimes\delta)<_{\mathrm{lex}}(x^{\prime}\ltimes\delta)\circ(y^{\prime}\ltimes\delta)\,,$

where $\circ$ indicates concatenation, i.e., that we are comparing
$(2m-2\delta)$-tuples lexicographically.

It remains to show that these two properties of imply the four statements in
the above table. Let us return to this end to our triple $xyz$ with $1\leq
x<y<z\leq 2^{m}$ and $\xi=\delta(xy)$, $\eta=\delta(yz)$. If $xyz$ is a left
tree, then $\delta(xz)=\delta(yz)<\delta(xy)$, for which reason (0 ) implies
$xy\strictif xz,yz$ and it remains to compare the latter two pairs. Since
$x\ltimes\eta\neq y\ltimes\eta$, the second rule declares that $xz\strictif
yz$ holds if and only if $x\ltimes\eta<_{\mathrm{lex}}y\ltimes\eta$. Now $x$
and $y$ agree in the first $\xi-1$ coordinates and continue with $x_{\xi}=-1$,
$y_{\xi}=+1$. Thus $x\ltimes\eta$ and $y\ltimes\eta$ agree in their first
$\xi-\eta-1$ coordinates and proceed with $x_{\xi}g(\eta,\xi)$,
$y_{\xi}g(\eta,\xi)$, respectively. So altogether $xz\strictif yz$ is
equivalent to $g(\eta,\xi)=+1$ and we have confirmed the two upper rows of the
table. The case where $xyz$ is a right tree is discussed similarly.
Summarising, we have thereby proved the first assertion in Theorem 1.3.

###  2.3. Negative stepping-up lemma for Leeb numbers

Throughout this subsection we fix two integers $k\geq 3$ and $n\geq k$. We set
$m=\mathrm{L}^{(k-1)}(n)-1$ and study orderings on $[2^{m}]^{(k)}$, where
$2^{m}$ is again identified with $\\{+1,-1\\}^{m}$. We are to exhibit an
ordering $([2^{m}]^{(k)},\strictif)$ without canonically ordered subsets of
size $4n+k$. Preparing ourselves we consider the following concept.

######  Definition 2.1.

A set $Z\subseteq[2^{m}]$ is said to be impeded (see Figure 2.4) if there
exist two elements $x<y$ in $Z$ with the following properties.

  1. ( )

At least $k$ members of $Z$ lie between $x$ and $y$.

  2. ( )

Setting $\delta=\delta(x,y)$ there exist
$x^{\prime},x^{\prime\prime},y^{\prime},y^{\prime\prime}\in Z$ such that
$x<x^{\prime}<x^{\prime\prime}<y^{\prime\prime}<y^{\prime}<y$ and
$x^{\prime\prime}_{\delta}=-1$ while $y^{\prime\prime}_{\delta}=+1$.

$x$$x^{\prime}$$x^{\prime\prime}$$y$$y^{\prime}$$y^{\prime\prime}$$\delta+1$$\delta$$Z$
Figure 2.4. An impeded set $Z$.

Roughly speaking, every unimpeded set contains a large comb.

######  Lemma 2.2.

Every set $Z\subseteq[2^{m}]$ is either impeded or possesses two subsets
$L,R\subseteq Z$ with $|L|+|R|\geq\tfrac{1}{2}(|Z|-k+1)$ forming a left comb
and a right comb, respectively.

###### Proof.

Otherwise let $Z$ be a minimal counterexample. Since every set with at most
two elements is a two-sided comb, we have $|Z|\geq k+2$. Now the vectors
$x=\min(Z)$ and $y=\max(Z)$ satisfy part ( ) ‣ 2.1 of Definition 2.1. Let
$x^{\prime}$, $x^{\prime\prime}$ be the second and third-smallest vector in
$Z$ and, similarly, let $y^{\prime}$ and $y^{\prime\prime}$ be the second and
third largest one. If both $x^{\prime\prime}_{\delta}=-1$ and
$y^{\prime\prime}_{\delta}=+1$ would hold, where $\delta=\delta(x,y)$, then
the set $Z$ were impeded, contrary to its choice.

Thus at least one of the cases $x^{\prime\prime}_{\delta}=+1$ and
$y^{\prime\prime}_{\delta}=-1$ occurs and for reasons of symmetry we may
suppose that $x^{\prime\prime}_{\delta}=+1$. The set
$Z_{\star}=Z\smallsetminus\\{x,x^{\prime}\\}$ cannot be impeded for then $Z$
was impeded as well. So by the minimality of $Z$ there exist sets
$L,R_{\star}\subseteq Z_{\star}$ forming a left comb and a right comb,
respectively, and satisfying
$|L|+|R_{\star}|\geq\tfrac{1}{2}(|Z_{\star}|-k+1)$. For any two elements
$r<r^{\prime}$ from $R_{\star}$ we have
$\delta(x,r)=\delta<\delta(r,r^{\prime})$ and, consequently, $R=\\{x\\}\cup
R_{\star}$ is a right comb. But now
$|L|+|R|=|L|+|R_{\star}|+1\geq\tfrac{1}{2}(|Z|-k+1)$ yields a final
contradiction. ∎

We proceed with some further notation. Let $<_{\mathrm{lex}}$ denote the
lexicographic ordering on $[2^{m}]^{(k)}$. So explicitly for
$X,Y\in[2^{m}]^{(k)}$ we have $X<_{\mathrm{lex}}Y$ if and only if $\sum_{x\in
X}2^{-x}$ is larger than $\sum_{y\in Y}2^{-y}$.

For every set $X\in[2^{m}]^{(k)}$ we determine a natural number $\varphi(X)$
according to the following rule: Consider $x^{-}=\min(X)$, $x^{+}=\max(X)$ and
compute $\delta=\delta(x^{-},x^{+})$. Notice that all elements of $X$ agree in
their first $\delta-1$ coordinates, while in the $\delta^{\mathrm{th}}$
coordinate $x^{-}_{\delta}=-1$ and $x^{+}_{\delta}=+1$. Let $\varphi(X)$ count
the number of members of $X$ having a $-1$ as their $\delta^{\mathrm{th}}$
coordinate. Notice that if $X$ is a left comb, then $\varphi(X)=|X|-1$, while
right combs satisfy $\varphi(X)=1$.

Next, if $B$ is either a left or a right comb, we know that
$\pi(B)=\bigl{\\{}\delta(xy)\colon xy\in B^{(2)}\bigr{\\}}\subseteq[m]$ is a
set of size $|B|-1$ whose elements can be found by applying $\delta$ to the
$|B|-1$ pairs of consecutive members of $B$. We call $\pi(B)$ the projection
of $B$.

Finally, instead of a colouring we shall apply an appropriate ordering
$([m]^{(k-1)},\YY)$ senkrecht. Because of $m<\mathrm{L}^{(k-1)}(n)$ this
ordering can be chosen without canonical subsets of size $n$.

We now state four desirable properties we would like an ordering
$([2^{m}]^{(k)},\strictif)$ to satisfy for any two distinct sets
$X,Y\in[2^{m}]^{(k)}$.

  1. (0 )

If $\varphi(X)$ is odd and $\varphi(Y)$ is even, then $X\strictif Y$.

  2. (0 )

If $X$ and $Y$ are two combs in the same direction having different
projections, then $X\strictif Y\Longleftrightarrow\pi(X)\YY\pi(Y)$.

  3. (0 )

If $X$ and $Y$ are left combs with $\pi(X)=\pi(Y)$, then $X\strictif
Y\Longleftrightarrow Y<_{\mathrm{lex}}X$.

  4. (0 )

If $X$ and $Y$ are right combs with $\pi(X)=\pi(Y)$, then $X\strictif
Y\Longleftrightarrow X<_{\mathrm{lex}}Y$.

It is not hard to see that these properties do not contradict each other.
Indeed, in order to satisfy (0 ) one partitions $[2^{m}]^{(k)}$ into two sets
depending on the parity of $\varphi$ and puts the odd class before the even
class. The remaining rules (0 ) – (0 ) only concern the internal orderings
within these two classes. Similarly, (0 ) tells us to sub-partition the combs
within both classes according to their projections and (0 ), (0 ) only give
further instructions how to compare combs within the same sub-class.

Now it suffices to show for no ordering $([2^{m}]^{(k)},\strictif)$ satisfying
(0 ) – (0 ) there is a set $Z\subseteq[2^{m}]$ of size $4n+k$ such that
$(Z^{(k)},\strictif)$ is ordered canonically. Assume contrariwise that and $Z$
have these properties. If $L\subseteq Z$ is a left comb, then so is every
$X\in L^{(k)}$ and by (0 ) it follows that $\pi(L)^{(k-1)}$ is ordered
canonically by . So our choice of yields $|\pi(L)|\leq n-1$ and, consequently,
$|L|\leq n$. For the same reason, every right comb $R\subseteq Z$ has at most
the size $n$. But now Lemma 2.2 tells us that $Z$ is impeded. Pick
$x,x^{\prime},x^{\prime\prime},y^{\prime\prime},y^{\prime},y\in Z$ as in
Definition 2.1.

Special case: $k=3$

Recall that every triple is either a left tree or a right tree. Owing to (0 )
the right trees precede the left trees with respect to .

$x$$x^{\prime}$$x^{\prime\prime}$$y$$y^{\prime}$$y^{\prime\prime}$$\delta(x,y)$$\delta(x,y)+1$$\delta(y^{\prime\prime},y)$$\delta(y^{\prime\prime},y^{\prime})$
Figure 2.5. The case $k=3$.

Now consider the quintuples
$A=\\{x,x^{\prime},x^{\prime\prime},y^{\prime},y\\}$ and
$B=\\{x,x^{\prime},y^{\prime\prime},y^{\prime},y\\}$, whose elements have just
been listed in increasing order. By canonicity we know that
$(A^{(3)},\strictif)$ and $(B^{(3)},\strictif)$ are isomorphic via the map
that sends $x^{\prime\prime}$ to $y^{\prime\prime}$ and keeps the four other
elements fixed. Since $xx^{\prime\prime}y^{\prime}$ and $xx^{\prime\prime}y$
are left trees with the same projection, (0 ) yields
$xx^{\prime\prime}y\strictif xx^{\prime\prime}y^{\prime}$. This statement in
$(A^{(3)},\strictif)$ translates to $xy^{\prime\prime}y\strictif
xy^{\prime\prime}y^{\prime}$. As we are now comparing right trees, (0 )
discloses that $xy^{\prime\prime}y$ and $xy^{\prime\prime}y^{\prime}$ cannot
have the same projection, for which reason
$\delta(y^{\prime\prime}y)\neq\delta(y^{\prime\prime}y^{\prime})$. In other
words, $y^{\prime\prime}y^{\prime}y$ is a left tree and
$\delta(y^{\prime\prime}y)=\delta(y^{\prime}y)$. It follows that the right
trees $xy^{\prime\prime}y$ and $xy^{\prime}y$ have the same projection, so
another application of (0 ) leads to $xy^{\prime\prime}y\strictif
xy^{\prime}y$. When transferred back to $A$ this statement becomes
$xx^{\prime\prime}y\strictif xy^{\prime}y$, so we have found a left tree
coming before a right tree, contrary to (0 ). This concludes the discussion of
the case $k=3$.

General case: $k\geq 4$

We may assume that $x^{\prime}$, $x^{\prime\prime}$ are the elements of $Z$
immediately succeeding $x$ and, similarly, that $y^{\prime\prime}$,
$y^{\prime}$ are immediately preceeding $y$. According to part ( ) ‣ 2.1 of
Definition 2.1 there is a set $W\subseteq Z$ with $|W|=k-2$,
$\min(W)=x^{\prime\prime}$, and $\max(W)=y^{\prime\prime}$. Consider the sets
$A=W\cup\\{x,x^{\prime},y\\}$ and $B=W\cup\\{x,y^{\prime},y\\}$ of size $k+1$.
By canonicity we know that the orderings $(A^{(k)},\strictif)$ and
$(B^{(k)},\strictif)$ are in the following sense essentially the same. For
$i\in[k+1]$ let $A_{i}$ and $B_{i}$ denote the sets of size $k$ arising from
$A$ and $B$ by removing their $i^{\mathrm{th}}$ elements, respectively. Now if
$A_{i}\strictif A_{j}$ holds for some $i,j\in[k+1]$, then $B_{i}\strictif
B_{j}$ follows. Set $\varphi=\varphi(A)$ and observe that $3\leq\varphi\leq
k-1$ due to the presence of $x$, $x^{\prime}$, $x^{\prime\prime}$, $y$, and
$y^{\prime\prime}$. Moreover

$\displaystyle\varphi(A_{1})=\dots=\varphi(A_{\varphi})=\varphi-1,\qquad\varphi(A_{\varphi+1})=\dots=\varphi(A_{k+1})=\varphi,$
$\displaystyle\varphi(B_{1})=\dots=\varphi(B_{\varphi-1})=\varphi-2,\quad\varphi(B_{\varphi})=\dots=\varphi(B_{k+1})=\varphi-1\,.$

In view of (0 ), this leads to the equivalences

$A_{1}\strictif A_{k+1}\,\,\,\Longleftrightarrow\,\,\,\varphi\text{ is even
}\,\,\,\Longleftrightarrow\,\,\,B_{k+1}\strictif B_{1}\,,$

which contradict the canonicity of . Altogether, this completes the proof of
Theorem 1.3.

##  3\. Upper bounds: the canonisation procedure

###  3.1. Preparation

The proof of Theorem 1.4 starts with some synchronisation principles for
colourings $f\colon X^{(r)}\longrightarrow\Gamma$, where
$X\subseteq{\mathds{N}}$, $r\geq 2$, and $\Gamma$ denotes a finite set of
colours. A special rôle will be played by the set of colours

$\Phi=\\{-1,+1\\}\,.$ (3.1)

Given a colouring $f\colon X^{(r)}\longrightarrow\Phi$ we define the opposite
colouring $(-f)\colon X^{(r)}\longrightarrow\Phi$ by $(-f)(x)=-(f(x))$ for all
$x\in X^{(r)}$. For simplicity we call a colouring $f\colon
X^{(r)}\longrightarrow\Phi$, where $r\geq 1$ and $X\subseteq{\mathds{N}}$,
increasing if $f(x_{1},\dots,x_{r-1},y)\leq f(x_{1},\dots,x_{r-1},y^{\prime})$
holds for all $x_{1}<\dots<x_{r-1}<y<y^{\prime}$ from $X$ and decreasing if
its opposite colouring is increasing. We refer to $f$ as monotone if it is
either increasing or decreasing. Two colourings $f\colon
X^{(r)}\longrightarrow\Phi$ and $g\colon Y^{(s)}\longrightarrow\Phi$ are said
to be monotone in the same direction if either both are increasing or both are
decreasing. Similarly, $f$ and $g$ are monotone in opposite directions if $f$
and $-g$ are monotone in the same direction.

######  Lemma 3.1.

Suppose that $s,t\geq 1$ are positive integers and that
$X\subseteq{\mathds{N}}$ is a set of size $|X|\geq(s-1)(t-1)+1$. If the
colouring $f\colon X^{(2)}\longrightarrow\Phi$ is monotone, then either there
is a monochromatic set $A\in X^{(s)}$ for the colour $-1$ or a monochromatic
set $B\in X^{(t)}$ for the colour $+1$.

###### Proof.

Due to the symmetry between $f$ and $-f$ we may suppose that $f$ is
increasing. We argue by induction on $t$. The base case $t=1$ offers no
difficulty, for every set of size one is monochromatic in both colours. Now
suppose that our claim is already known to be true for $t-1$ in place of $t$,
where $t\geq 2$. Set $z=\max(X)$ and consider the set $N=\\{x\in X\colon
f(xz)=-1\\}$.

First Case: $|N|\geq s-1$

Now it suffices to prove that $A=N\cup\\{z\\}$ is monochromatic in colour
$-1$. So let $x<y$ from $A$ be arbitrary and observe that $x\in N$. If $y=z$,
then $f(xy)=-1$ follows from the definition of $N$. Otherwise we have $y<z$
and the assumption that $f$ is increasing implies $f(xy)\leq f(xz)=-1$, whence
$f(xy)=-1$.

Second Case: $|N|<s-1$

Now the set $X_{\star}=X\smallsetminus(N\cup\\{z\\})$ satisfies
$|X_{\star}|\geq|X|-(s-1)\geq(s-1)(t-2)+1$. Thus the induction hypothesis
applies to $X_{\star}$ and yields either a monochromatic set $A$ of size $s$
for $-1$ or a monochromatic set $B^{\prime}$ of size $t-1$ for $+1$. In the
former case we are done immediately and in the latter case the definition of
$N$ entails that $B=B^{\prime}\cup\\{z\\}$ is monochromatic for the colour
$+1$. ∎

This iterates as follows.

######  Lemma 3.2.

Given a natural number $n$ and a nonempty finite index set $I$ let
$X\subseteq{\mathds{N}}$ be a set with $|X|\geq|I|!n^{|I|+1}$. If
$(f_{i})_{i\in I}$ denotes a family of monotone colourings $f_{i}\colon
X^{(2)}\longrightarrow\Phi$, then there is a set $Z\subseteq X$ of size $n$
which is monochromatic with respect to every $f_{i}$.

###### Proof.

Replacing some of the colourings $f_{i}$ by their opposites, if necessary, we
may assume that all of them are increasing. We argue by induction on $|I|$,
the base case $|I|=1$ being dealt with in the foregoing lemma. Now suppose
that $|I|\geq 2$ and that the lemma has already been established for every set
$I^{\prime}\subsetneq I$ instead of $I$. Given a set $X$ and a family of
increasing colourings $(f_{i})_{i\in I}$ of the pairs of elements from $X$ we
define an auxiliary colouring $f\colon X^{(2)}\longrightarrow\Phi$ by
$f=\min\\{f_{i}\colon i\in I\\}$, i.e.,

$f(xy)=+1\,\,\,\Longleftrightarrow\,\,\,\forall i\in I\,\,f_{i}(xy)=+1\,.$

Evidently, $f$ is increasing as well. So by Lemma 3.1 there either exists a
set $A\subseteq X$ with $|A|\geq|I|!n^{|I|}$ that is monochromatic for $f$ in
colour $-1$ or there is a set $Z\subseteq X$ of size $n$ that is monochromatic
for $f$ in colour $+1$. In the latter case $Z$ monochromatically has colour
$+1$ with respect to every $f_{i}$ and thus it possesses the desired property.

So suppose from now on that the former case occurs, i.e., that we have
obtained a set $A$ of size $|A|\geq|I|!n^{|I|}$ that is monochromatic with
respect to $f$ in colour $-1$. Put $z=\max(A)$ and $X_{i}=\\{a\in A\colon
f_{i}(az)=-1\\}$ for every $i\in I$. Since $f(az)=-1$ holds for all $a\in
A\smallsetminus\\{z\\}$, we know that $\bigcup_{i\in
I}X_{i}=A\smallsetminus\\{z\\}$. Owing to the Schubfachprinzip this implies
$|X_{i(\star)}|\geq(|I|-1)!n^{|I|}$ for some $i(\star)\in I$. As in the first
case of the proof of Lemma 3.1 one can show that the set
$X_{i(\star)}\cup\\{z\\}$ monochromatically receives the colour $-1$ with
respect to $f_{i(\star)}$. It remains to apply the induction hypothesis to
this set and to $I^{\prime}=I\smallsetminus\\{i(\star)\\}$. ∎

Let us now return to an arbitrary colouring $f\colon
X^{(r)}\longrightarrow\Gamma$, where $X\subseteq{\mathds{N}}$, $r\geq 2$, and
$\Gamma$ denotes a set of colours. We say that $f$ is governed by another
colouring $f^{\prime}\colon X^{(\ell)}\longrightarrow\Gamma$, where
$\ell\in[r-1]$, if $f(x_{1},\dots,x_{r})=f^{\prime}(x_{1},\dots,x_{\ell})$
holds for all $x_{1}<\dots<x_{r}$ from $X$. Standard references call $f$ end-
homogeneous if it is governed by some $(r-1)$-ary function $f^{\prime}$ in
this sense, but for us it will be useful to have words expressing the
relationship between $f$ and $f^{\prime}$.

######  Lemma 3.3.

Given integers $n\geq r\geq 2$ and $s\geq 3$, a set of colours $\Gamma$, and a
nonempty finite index set $I$ let $X\subseteq{\mathds{N}}$ be a set of size
$|X|\geq(2|\Gamma|)^{n^{r-1}}\cdot(2|I|n^{s-2})^{|I|n^{s-2}}$. If $f\colon
X^{(r)}\longrightarrow\Gamma$ is an arbitrary colouring and $(g_{i})_{i\in I}$
with $g_{i}\colon X^{(s)}\longrightarrow\Phi$ is a family of monotone
colourings, then there exist a set $Z\subseteq X$ of size $n$, a colouring
$f^{\prime}\colon Z^{(r-1)}\longrightarrow\Gamma$ and a family
$(g^{\prime}_{i})_{i\in I}$ of monotone colourings $g^{\prime}_{i}\colon
Z^{(s-1)}\longrightarrow\Phi$ such that

  1. ( )

$f^{\prime}$ governs the restriction of $f$ to $Z^{(r)}$,

  2. ( )

for every $i\in I$ the colouring $g^{\prime}_{i}$ governs the restriction of
$g_{i}$ to $Z^{(s)}$,

  3. ( )

and for every $i\in I$ the colourings $g_{i}$, $g^{\prime}_{i}$ are monotone
in opposite directions.

###### Proof.

As usual, we may suppose that every $g_{i}$ is increasing. An integer
$\nu\in[n]$ is said to be secure if there exist sets $Z_{\nu},A_{\nu}\subseteq
X$ with $|Z_{\nu}|=\nu$ and $\max(Z_{\nu})<\min(A_{\nu})$, a function
$f^{\prime}\colon Z_{\nu}^{(r-1)}\longrightarrow\Gamma$, and a family
$(g^{\prime}_{i})_{i\in I}$ of decreasing colourings $g^{\prime}_{i}\colon
Z_{\nu}^{(s-1)}\longrightarrow\Phi$ with the following properties.

  1. ( )

If the numbers $z_{1}<\dots<z_{r-1}$ are in $Z_{\nu}$ and $z_{r}>z_{r-1}$ is
in $Z_{\nu}\cup A_{\nu}$, then
$f(z_{1},\dots,z_{r})=f^{\prime}(z_{1},\dots,z_{r-1})$.

  2. ( )

If $i\in I$, the numbers $z_{1}<\dots<z_{s-1}$ are in $Z_{\nu}$, and
$z_{s}>z_{s-1}$ is in $Z_{\nu}\cup A_{\nu}$, then
$g_{i}(z_{1},\dots,z_{s})=g^{\prime}_{i}(z_{1},\dots,z_{s-1})$.

  3. ( )

If $i\in I$, the numbers $z_{1}<\dots<z_{s-1}$ are in $Z_{\nu}$, and
$g^{\prime}_{i}(z_{1},\dots,z_{s-1})=-1$, then
$g_{i}(z_{1},\dots,z_{s-2},y,y^{\prime})=-1$ holds for all $y,y^{\prime}\in
A_{\nu}$.

  4. ( )

Finally,
$|A_{\nu}|\geq(2|\Gamma|)^{n^{r-2}(n-\nu)}\cdot(2|I|n^{s-2})^{|I|n^{s-2}-\Omega}$,
where $\Omega$ denotes the number of pairs $(i,Z)$ such that $i\in I$,
$\max(Z_{\nu})\in Z\in Z_{\nu}^{(s-1)}$, and $g^{\prime}_{i}(Z)=-1$.

Observe that ( ) ‣ 3.1 and ( ) ‣ 3.1 are fairly standard conditions in
arguments concerning end-homogeneity. Except for the presence of $\Omega$ so
is ( ) ‣ 3.1. Clause ( ) ‣ 3.1 interacts well with the demand that the
functions $g^{\prime}_{i}$ be decreasing.

We contend that $1$ is secure. If $r\geq 3$ this can be seen by taking
$Z_{1}=\\{\min(X)\\}$ and $A_{1}=X\smallsetminus Z_{1}$. In the special case
$r=2$ we still set $Z_{1}=\\{\min(X)\\}$ but now we need to pay some attention
to condition ( ) ‣ 3.1. The Schubfachprinzip yields a colour $\gamma\in\Gamma$
and a set $A_{1}\subseteq X\smallsetminus Z_{1}$ of size
$|A_{1}|\geq(|X|-1)/r$ such that $f(\min(X),a_{1})=\gamma$ holds for all
$a_{1}\in A_{1}$. Since $A_{1}$ is at least as large as ( ) ‣ 3.1 demands, $1$
is indeed secure.

Notice that if $n$ turns out to be secure, then any set $Z_{n}$ exemplifying
this will have the desired properties. So it suffices to prove that the
largest secure number, denoted by $\nu(\star)$ in the sequel, is equal to $n$.

Assume for the sake of contradiction that $\nu(\star)<n$ and let the sets
$Z_{\nu(\star)}$, $A_{\nu(\star)}$, the function $f^{\prime}\colon
Z_{\nu(\star)}^{(r-1)}\longrightarrow\Gamma$, and the family
$(g^{\prime}_{i})_{i\in I}$ of decreasing colourings $g^{\prime}_{i}\colon
Z_{\nu(\star)}^{(s-1)}\longrightarrow\Phi$ witness the security of
$\nu(\star)$. Due to $\Omega\leq|I|\binom{\nu(\star)-1}{s-2}<|I|n^{s-2}$ the
second factor in ( ) ‣ 3.1 is integral and we may assume without loss of
generality that

$|A_{\nu(\star)}|=(2|\Gamma|)^{n^{r-2}(n-\nu(\star))}\cdot(2|I|n^{s-2})^{|I|n^{s-2}-\Omega}\,.$

Now the plan is to reach a contradiction by establishing the security of
$\nu(\star)+1$. To this end we shall add a new element to $Z_{\nu(\star)}$ and
extend the functions $f^{\prime}$ and $g^{\prime}_{i}$ appropriately. The
conditions that seems hardest to maintain is ( ) ‣ 3.1. In fact, this task
requires some preparations that have to be carried out before one decides
which element gets added to $Z_{\nu(\star)}$.

Set $z_{\nu(\star)}=\max(Z_{\nu(\star)})$ and define

$L=\bigl{\\{}(i,Z)\in I\times Z_{\nu(\star)}^{(s-2)}\colon\text{ If
}z_{\nu(\star)}\not\in Z,\text{ then
}g^{\prime}_{i}(Z\cup\\{z_{\nu(\star)}\\})=+1\bigr{\\}}\,.$

A pair of sets $(W,D)$ with $W\subseteq L$ and $D\subseteq A_{\nu(\star)}$ is
said to be a candidate if

  1. $\bullet$

for all $(i,Z)\in W$ and all $dd^{\prime}\in D^{(2)}$ we have
$g_{i}(Z\cup\\{d,d^{\prime}\\})=-1$,

  2. $\bullet$

and $|D|\geq(2|I|n^{s-2})^{-|W|}|A_{\nu(\star)}|$.

For instance, $(\varnothing,A_{\nu(\star)})$ is a candidate and, consequently,
we can pick a candidate $(W_{\star},D_{\star})$ for which $|W_{\star}|$ is
maximal. Since
$\Omega+|W_{\star}|\leq|I|\binom{\nu(\star)}{s-2}\leq|I|n^{s-2}$, we may again
assume that

$|D_{\star}|=(2|I|n^{s-2})^{-|W_{\star}|}|A_{\nu(\star)}|=(2|\Gamma|)^{n^{r-2}(n-\nu(\star))}\cdot(2|I|n^{s-2})^{|I|n^{s-2}-\Omega-|W_{\star}|}\,.$

Now we partition $D_{\star}$ into two consecutive halves, i.e., we write
$D_{\star}=D^{\prime}\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}D^{\prime\prime}$
such that $|D^{\prime}|=|D^{\prime\prime}|=\frac{1}{2}|D_{\star}|$ and
$D^{\prime}<D^{\prime\prime}$. Put
$d^{\prime\prime}_{\star}=\min(D^{\prime\prime})$ and consider for every pair
$(i,Z)\in L\smallsetminus W_{\star}$ the set

$X(i,Z)=\bigl{\\{}d^{\prime}\in D^{\prime}\colon
g_{i}(Z\cup\\{d^{\prime},d^{\prime\prime}_{\star}\\})=-1\bigr{\\}}\,.$

Assume for the sake of contradiction that there exists a pair $(i,Z)\in
L\smallsetminus W_{\star}$ such that
$|X(i,Z)|\geq(2|I|n^{s-2})^{-1}|D_{\star}|$. Now for all $y<y^{\prime}$ from
$X(i,Z)$ the assumption that $g_{i}$ be increasing yields
$g_{i}(Z\cup\\{y,y^{\prime}\\})\leq
g_{i}(Z\cup\\{y,d^{\prime\prime}_{\star}\\})=-1$, whence
$g_{i}(Z\cup\\{y,y^{\prime}\\})=-1$. In other words,
$\bigl{(}W_{\star}\cup\\{(i,Z)\\},X(i,Z)\bigr{)}$ is a candidate contradicting
the maximality of $|W_{\star}|$.

We have thereby proved $|X(i,Z)|<(2|I|n^{s-2})^{-1}|D_{\star}|$ for all pairs
$(i,Z)\in L\smallsetminus W_{\star}$. Since $|L\smallsetminus
W_{\star}|\leq|L|\leq|I|n^{s-2}$, this implies

$\bigg{|}\bigcup_{(i,Z)\in L\smallsetminus
W_{\star}}X(i,Z)\bigg{|}<\tfrac{1}{2}|D_{\star}|=|D^{\prime}|\,.$

Therefore, we can pick an element

$z_{\nu(\star)+1}\in D^{\prime}\smallsetminus\bigcup_{(i,Z)\in L\smallsetminus
W_{\star}}X(i,Z)$

and set $Z_{\nu(\star)+1}=Z_{\nu(\star)}\cup\\{z_{\nu(\star)+1}\\}$.

With the help of this set we intend to convince ourselves that $\nu(\star)+1$
is secure, which will contradict our maximal choice of $\nu(\star)$ and thus
conclude the proof of Lemma 3.3. Towards this goal, we need to specify an
appropriate set $A_{\nu(\star)+1}$, a function $f^{\prime\prime}\colon
Z_{\nu(\star)+1}^{(r-1)}\longrightarrow\Gamma$, and a family
$(g^{\prime\prime}_{i})_{i\in I}$ of decreasing colourings
$g^{\prime\prime}_{i}\colon Z_{\nu(\star)+1}^{(s-1)}\longrightarrow\Phi$ such
that the conditions ( ) ‣ 3.1 – ( ) ‣ 3.1 hold in this setting. These choices
will be made in such a way that $A_{\nu(\star)+1}\subseteq D^{\prime\prime}$,
the function $f^{\prime\prime}$ extends $f^{\prime}$, and for every $i\in I$
the colouring $g^{\prime\prime}_{i}$ extends $g^{\prime}_{i}$.

Our first step consists in determining $A_{\nu(\star)+1}$ and
$f^{\prime\prime}$. To this end, we define for every $d^{\prime\prime}\in
D^{\prime\prime}$ the function $h_{d^{\prime\prime}}\colon
Z_{\nu(\star)}^{(r-2)}\longrightarrow\Gamma$ by

$h_{d^{\prime\prime}}(Z)=f(Z\cup\\{z_{\nu(\star)+1},d^{\prime\prime}\\})\quad\text{
for all }Z\in Z_{\nu(\star)}^{(r-2)}\,.$

Since $|Z_{\nu(\star)}^{(r-2)}|\leq n^{r-2}$, there are at most
$|\Gamma|^{n^{r-2}}$ possible functions from $Z_{\nu(\star)}^{(r-2)}$ to
$\Gamma$ and the Schubfachprinzip yields a function $h_{\star}\colon
Z_{\nu(\star)}^{(r-2)}\longrightarrow\Gamma$ together with a set
$A_{\nu(\star)+1}\subseteq D^{\prime\prime}$ satisfying
$h_{d^{\prime\prime}}=h_{\star}$ for all $d^{\prime\prime}\in
A_{\nu(\star)+1}$ and
$|A_{\nu(\star)+1}|\geq|\Gamma|^{-n^{r-2}}|D^{\prime\prime}|$. For later use
we remark that

$|A_{\nu(\star)+1}|\geq\frac{|D^{\prime\prime}|}{|\Gamma|^{n^{r-2}}}=\frac{|D_{\star}|}{2|\Gamma|^{n^{r-2}}}\geq(2|\Gamma|)^{n^{r-2}(n-\nu(\star)-1)}\cdot(2|I|n^{s-2})^{|I|n^{s-2}-\Omega-|W_{\star}|}\,.$

Now we define the extension $f^{\prime\prime}\supseteq f^{\prime}$ by
$f^{\prime\prime}(Z\cup\\{z_{\nu(\star)+1}\\})=h_{\star}(Z)$ for all $Z\in
Z_{\nu(\star)}^{(r-2)}$ and observe that ( ) ‣ 3.1 clearly remains valid.

Proceeding with the extensions $g^{\prime\prime}_{i}\supseteq g^{\prime}_{i}$
for $i\in I$ we set

$g^{\prime\prime}_{i}(Z\cup\\{z_{\nu(\star)+1}\\})=\begin{cases}+1&\text{if
}(i,Z)\in L\smallsetminus W_{\star}\\\ -1&\text{otherwise }\end{cases}$

for all $i\in I$ and $Z\in Z_{\nu(\star)}^{(s-2)}$. Let us start the
discussion of these colourings by verifying that they are indeed decreasing.
In other words, we want to check that if $i\in I$ and
$Z\in(Z_{\nu(\star)}\smallsetminus\\{z_{\nu(\star)}\\})^{(s-2)}$ satisfy
$g^{\prime\prime}(Z\cup\\{z_{\nu(\star)}\\})=-1$, then
$g^{\prime\prime}(Z\cup\\{z_{\nu(\star)+1}\\})=-1$ follows. To this end we
just need to observe that $g^{\prime\prime}(Z\cup\\{z_{\nu(\star)}\\})=-1$
implies $(i,Z)\not\in L$.

For the confirmation of ( ) ‣ 3.1 it suffices to argue that if $i\in I$, $Z\in
Z_{\nu(\star)}^{(s-2)}$, and $d^{\prime\prime}\in D^{\prime\prime}$, then
$g_{i}(Z\cup\\{z_{\nu(\star)+1},d^{\prime\prime}\\})=g^{\prime\prime}_{i}(Z\cup\\{z_{\nu(\star)+1}\\})$.
If $(i,Z)\in W_{\star}$, then the first bullet in the definition of
$(W_{\star},D_{\star})$ being a candidate yields indeed
$g_{i}(Z\cup\\{z_{\nu(\star)+1},d^{\prime\prime}\\})=-1$. Next, if $(i,Z)\in
L\smallsetminus W_{\star}$, then $z_{\nu(\star)+1}\not\in X(i,Z)$ entails
$g_{i}(Z\cup\\{z_{\nu(\star)+1},d^{\prime\prime}_{\star}\\})=+1$ and thus the
assumption that $g_{i}$ be increasing and
$d^{\prime\prime}_{\star}=\min(D^{\prime\prime})\leq d^{\prime\prime}$ reveal
$g_{i}(Z\cup\\{z_{\nu(\star)+1},d^{\prime\prime}\\})=+1$, as desired. Finally,
suppose that $(i,Z)\not\in L$, whence $z_{\nu(\star)}\not\in Z$ and
$g^{\prime}_{i}(Z\cup\\{z_{\nu(\star)}\\})=-1$. Since $g^{\prime}_{i}$
satisfies ( ) ‣ 3.1 and $z_{\nu(\star)+1},d^{\prime\prime}\in A_{\nu(\star)}$,
we have indeed $g_{i}(Z\cup\\{z_{\nu(\star)+1},d^{\prime\prime}\\})=-1$.
Altogether, we have thereby proved that the colourings $g^{\prime\prime}_{i}$
still obey condition ( ) ‣ 3.1.

To handle the new cases of ( ) ‣ 3.1 we show that if $Z\in
Z_{\nu(\star)}^{(s-2)}$ and either $(i,Z)\in W_{\star}$ or $(i,Z)\not\in L$,
then $g_{i}(Z\cup\\{y,y^{\prime}\\})=-1$ holds for all $yy^{\prime}\in
D_{\star}^{(2)}$. For $(i,Z)\in W_{\star}$ this is a direct consequence of
$(W_{\star},D_{\star})$ being a candidate, so we may suppose $(i,Z)\not\in L$
from now on, which, let us recall, means $z_{\nu(\star)}\not\in Z$ and
$g^{\prime}_{i}(Z\cup\\{z_{\nu(\star)}\\})=-1$. So the desired conclusion is
already covered by $g^{\prime}_{i}$ satisfying ( ) ‣ 3.1.

Finally, we need to verify the lower bound on $|A_{\nu(\star)+1}|$ promised by
( ) ‣ 3.1. Denoting the number of pairs $(i,Z)$ such that $i\in I$,
$z_{\nu(\star)+1}\in Z\in Z_{\nu(\star)+1}^{(s-1)}$, and
$g^{\prime\prime}_{i}(Z)=-1$ by $\Omega^{\prime}$ it suffices to check that
$\Omega^{\prime}=\Omega+|W_{\star}|$. Since $\Omega^{\prime}$ counts the
number of pairs $(i,Z)\in I\times Z_{\nu(\star)}^{(s-2)}$ satisfying
$g^{\prime\prime}_{i}(Z\cup\\{z_{\nu(\star)+1}\\})=-1$, or in other words
$Z\not\in L\smallsetminus W_{\star}$, we have indeed

$\displaystyle\Omega^{\prime}$ $\displaystyle=|I\times
Z_{\nu(\star)}^{(s-2)}\smallsetminus(L\smallsetminus W_{\star})|$
$\displaystyle=|I\times Z_{\nu(\star)}^{(s-2)}\smallsetminus L|+|W_{\star}|$
$\displaystyle=\big{|}\bigl{\\{}(i,Z)\in I\times Z_{\nu(\star)}^{(s-2)}\colon
z_{\nu(\star)}\not\in Z\text{ and
}g^{\prime}_{i}(Z\cup\\{z_{\nu(\star)}\\})=-1\bigr{\\}}\big{|}+|W_{\star}|$
$\displaystyle=\Omega+|W_{\star}|\,.$

This concludes the proof that $\nu(\star)+1$ is secure and, as we said before,
this contradiction to the choice of $\nu(\star)$ establishes Lemma 3.3. ∎

We remark that the case $I=\varnothing$ can be handled similarly but much
easier. In this case one can ignore all parts of the proof addressing $I$ and,
moreover, there is no need to divide the set $D_{\star}=A_{\nu(\star)}$ into
two halves. Therefore, one obtains the following well-known statement.

######  Corollary 3.4.

If $n\geq r\geq 2$ and $N\geq|\Gamma|^{n^{r-1}}$, then for every colouring
$f\colon[N]^{(r)}\longrightarrow\Gamma$ there are a set $X\subseteq[N]$ of
size $n$ and a function $f^{\prime}\colon X^{(r-1)}\longrightarrow\Gamma$
governing the restriction of $f$ to $X^{(r)}$. $\Box$

###  3.2. Definite orderings

Resuming the task of proving Theorem 1.4 we shall now study orderings
$([N]^{(k)},\strictif)$ that are “almost canonical” in the sense that we can
easily extract a sign vector
$\varepsilon=(\varepsilon_{1},\dots,\varepsilon_{k})\in\\{+1,-1\\}^{k}$ and a
permutation $\sigma\in\mathfrak{S}_{k}$ from them such that behaves in some
important ways like the canonical ordering associated with
$(\varepsilon,\sigma)$. For transparency we shall assume $N\geq 2k+1$
throughout this investigation.

Observe that in the canonical case, an entry $\varepsilon_{i}=+1$ in the sign
vector indicates that we can increase a set $x\in[N]^{(k)}$ with respect to by
increasing its element in the $i^{\mathrm{th}}$ position, whereas an entry
$\varepsilon_{i}=-1$ signifies that it is the other way around. When is
arbitrary and $i\in[k]$ we call a triple
$S=(X,A,Y)\in[N]^{(i-1)}\times[N]^{(2)}\times[N]^{(k-i)}$ with $X<A<Y$ an
$i$-decider. Notice that $i$-deciders are in natural bijective correspondence
with $(k+1)$-subsets of $[N]$. If $S=(X,A,Y)$ is such an $i$-decider and
$A=\\{c,d\\}$ with $c<d$ we may compare the sets $S(c)=X\cup\\{c\\}\cup Y$ and
$S(d)=X\cup\\{d\\}\cup Y$ with respect to . If $S(c)\strictif S(d)$ we set
$\varepsilon_{i}(S)=+1$ and in case $S(d)\strictif S(c)$ we put
$\varepsilon_{i}(S)=-1$. So roughly speaking, $\varepsilon_{i}(S)=+1$ means
that the $i$-decider $S$ “thinks” that $\varepsilon_{i}$ should have the value
$+1$. If all $i$-deciders $S$ agree and yield the same sign
$\varepsilon_{i}(S)$ we say that is $i$-definite and denote the common value
of all $\varepsilon_{i}(S)$ by $\varepsilon_{i}$. It may happen that is
$i$-definite for every $i\in[k]$ and in this case we call the ordering sign-
definite and $\varepsilon=(\varepsilon_{1},\dots,\varepsilon_{k})$ is referred
to as its sign-vector. Clearly, the canonical ordering associated with a pair
$(\varepsilon,\sigma)\in\\{+1,-1\\}^{k}\times\mathfrak{S}_{k}$ is sign-
definite and has sign-vector $\varepsilon$ in this sense.

Next we explain the extraction of a permutation from an “almost canonical”
ordering. Let $ij\in[k]^{(2)}$ with $i<j$ be an arbitrary pair of indices.
Observe that for a permutation $\sigma\in\mathfrak{S}_{k}$, the number $i$
occurs before $j$ in the list $\sigma(1),\dots,\sigma(k)$ if and only if
$\sigma^{-1}(i)<\sigma^{-1}(j)$. So for the canonical ordering considered in
Definition 1.1 $\sigma^{-1}(i)<\sigma^{-1}(j)$ indicates that $i$ has in the
following sense higher priority than $j$. If we take a set $x\in[N]^{(k)}$ and
change both its $i^{\mathrm{th}}$ and its $j^{\mathrm{th}}$ element, while
keeping the relative positions of the elements fixed, then whether we increase
or decrease $x$ with respect to is decided by $\varepsilon_{i}$ and the
direction in which we move the $i^{\mathrm{th}}$ element alone. Similarly
$\sigma^{-1}(j)<\sigma^{-1}(i)$ means that $j$ has higher priority than $i$.
Now suppose that the ordering is not necessarily canonical but still sign-
definite with sign vector
$\varepsilon=(\varepsilon_{1},\dots,\varepsilon_{k})$. By an $ij$-decider we
mean a quintuple

$P=(X,A,Y,B,Z)\in[N]^{(i-1)}\times[N]^{(2)}\times[N]^{(j-i-1)}\times[N]^{(2)}\times[N]^{(k-j)}$

with $X<A<Y<B<Z$. So $ij$-deciders are in natural bijective correspondence
with $(k+2)$-subsets of $[N]$. Given such an $ij$-decider $P=(X,A,Y,B,Z)$ and
two elements $a\in A$, $b\in B$ we set $P(a,b)=X\cup\\{a\\}\cup
Y\cup\\{b\\}\cup Z$. The restriction of to the four-element set

$\langle P\rangle=\bigl{\\{}P(a,b)\colon(a,b)\in A\times B\bigr{\\}}$

is largely determined by $\varepsilon_{i}$ and $\varepsilon_{j}$. Notably, if
we write $A=\\{c_{i},d_{i}\\}$ and $B=\\{c_{j},d_{j}\\}$ such that
$\varepsilon_{i}c_{i}<\varepsilon_{i}d_{i}$ and
$\varepsilon_{j}c_{j}<\varepsilon_{j}d_{j}$, then the -minimum of $\langle
P\rangle$ is $P(c_{i},c_{j})$ and the -maximum is $P(d_{i},d_{j})$. So the
only piece of information we are lacking is how $P(c_{i},d_{j})$ compares to
$P(d_{i},c_{j})$. We let $\sigma_{ij}(P)$ denote

the number | provided that
---|---
$+1$ |  $P(c_{i},d_{j})\strictif P(d_{i},c_{j})$,
$-1$ |  $P(d_{i},c_{j})\strictif P(c_{i},d_{j})$.

So intuitively $\sigma_{ij}(P)=+1$ means that $P$ “believes” $i$ to have
higher priority than $j$, while in the opposite case it is the other way
around. If $\sigma_{ij}(P)$ stays constant as $P$ varies over all
$ij$-deciders we say that is $ij$-definite and denote the common value of all
$\sigma_{ij}(P)$ by $\sigma_{ij}$. Finally, if is $ij$-definite for all pairs
$ij\in[k]^{(2)}$ we call a permutation-definite ordering. We remark that in
the canonical case $\sigma_{ij}=+1$ is equivalent to
$\sigma^{-1}(i)<\sigma^{-1}(j)$ meaning that the statement
$\sigma_{ij}\cdot\bigl{(}\sigma^{-1}(j)-\sigma^{-1}(i)\bigr{)}>0$ is always
valid. Let us check that, conversely, in the permutation-definite case we can
define a permutation $\sigma$ having this property.

######  Lemma 3.5.

Suppose that $N\geq 2k$. If the ordering $([N]^{(k)},\strictif)$ is both sign-
definite and permutation-definite, then there exists a permutation
$\sigma\in\mathfrak{S}_{k}$ such that

$\sigma_{ij}\cdot\bigl{(}\sigma^{-1}(j)-\sigma^{-1}(i)\bigr{)}>0$

holds whenever $1\leq i<j\leq k$.

###### Proof.

Let $\varepsilon=(\varepsilon_{1},\dots,\varepsilon_{k})$ be the sign-vector
of and write $\\{2i-1,2i\\}=\\{c_{i},d_{i}\\}$ such that
$\varepsilon_{i}c_{i}<\varepsilon_{i}d_{i}$ holds for every $i\in[k]$.
Consider the sets

$x_{i}=\\{c_{i}\\}\cup\\{d_{j}\colon j\neq i\\}$

and let $\sigma\in\mathfrak{S}_{k}$ be the permutation satisfying

$x_{\sigma(1)}\strictif\dots\strictif x_{\sigma(k)}\,.$

Whenever $1\leq i<j\leq k$ the quintuple

$P_{ij}=\bigl{(}\\{d_{r}\colon 1\leq r<i\\},\\{2i-1,2i\\},\\{d_{s}\colon
i<s<j\\},\\{2j-1,2j\\},\\{d_{t}\colon j<t\leq k\\}\bigr{)}$

is an $ij$-decider and $\sigma_{ij}$ is the sign $+1$ if and only if
$x_{i}\strictif x_{j}$, which is in turn equivalent to
$\sigma^{-1}(i)<\sigma^{-1}(j)$. In other words, irrespective of whether
$\sigma_{ij}$ is positive or negative the statement
$\sigma_{ij}\cdot\bigl{(}\sigma^{-1}(j)-\sigma^{-1}(i)\bigr{)}>0$ holds. ∎

The remainder of this section deals with the question how much a sign-definite
and permutation-definite ordering $([N]^{(k)},\strictif)$ with sign-vector
$\varepsilon$ and permutation $\sigma$ (obtained by means of Lemma 3.5) needs
to have in common with the canonical ordering associated with
$(\varepsilon,\sigma)$ in the sense of Definition 1.1. For instance, Lemma 3.7
below asserts that under these circumstances there exists a dense subset
$W\subseteq[N]$ such that $(W^{(k)},\strictif)$ is ordered in this canonical
way.

The strategy we use for this purpose is the following. Suppose that
$x,y\in[N]^{(k)}$ are written in the form $x=\\{x_{1},\dots,x_{k}\\}$ and
$y=\\{y_{1},\dots,y_{k}\\}$, where $x_{1}<\dots<x_{k}$ and
$y_{1}<\dots<y_{k}$. Our goal is to prove that in many cases we have

$x\strictif
y\,\,\,\Longleftrightarrow\,\,\,(\varepsilon_{\sigma(1)}x_{\sigma(1)},\dots,\varepsilon_{\sigma(k)}x_{\sigma(k)})<_{\mathrm{lex}}(\varepsilon_{\sigma(1)}y_{\sigma(1)},\dots,\varepsilon_{\sigma(1)}y_{\sigma(k)})\,.$
(3.2)

We shall say that a pair of $k$-sets $(x,y)$ is $(\varepsilon,\sigma)$-sound
if it satisfies the equivalence (3.2). Moreover, we set
$\Delta(x,y)=\\{i\in[k]\colon x_{i}\neq y_{i}\\}$. The plan towards Lemma 3.7
is to construct a sequence of sets $[N]=W_{1}\supseteq\dots\supseteq W_{k}$
such that every pair $(x,y)$ of $k$-sets with $x,y\subseteq W_{t}$ and
$|\Delta(x,y)|\leq t$ is $(\varepsilon,\sigma)$-sound. The statement that
follows will assist us in the step of an induction on $t$.

######  Lemma 3.6.

For $L\subseteq{\mathds{Z}}$ let $(L^{(k)},\strictif)$ be an ordering that is
sign-definite with sign-vector $\varepsilon$ and permutation-definite with
permutation $\sigma$. Suppose $t\in[k-1]$ has the property that every pair
$(x,y)$ of $k$-sets with $x,y\subseteq L$ and $|\Delta(x,y)|\leq t$ is
$(\varepsilon,\sigma)$-sound.

Let $I\subseteq[k]$ be a set of $t+1$ indices and let $i\in[k]$ be the least
index with $\sigma(i)\in I$. Further, let $x=\\{x_{1},\dots,x_{k}\\}$ and
$y=\\{y_{1},\dots,y_{k}\\}$ be two $k$-element subsets of $L$ such that
$\Delta(x,y)=I$ and $x_{\sigma(i)}<y_{\sigma(i)}$. If $a$ denotes the least
member of $L$ larger than $x_{\sigma(i)}$ and the conditions

  1. $\bullet$

$a<y_{\sigma(i)}$,

  2. $\bullet$

$\sigma(i)=\min(I)\Longrightarrow
a<\min\\{x_{\sigma(i)+1},y_{\sigma(i)+1}\\}$,

  3. $\bullet$

and $\sigma(i)=\max(I)\Longrightarrow
a>\max\\{x_{\sigma(i)-1},y_{\sigma(i)-1}\\}$

hold, then the pair $(x,y)$ is $(\varepsilon,\sigma)$-sound.

###### Proof.

Without loss of generality we may assume $\varepsilon_{\sigma(i)}=+1$. We are
to prove that $x\strictif y$ and in all cases this will be accomplished by
finding a $k$-set $z\subseteq L$ such that the pairs $(x,z)$ and $(z,y)$ are
$(\varepsilon,\sigma)$-sound and $x\strictif z\strictif y$ holds.

Suppose first that $\min(I)<\sigma(i)<\max(I)$. Due to
$a\in(x_{\sigma(i)},y_{\sigma(i)})\subseteq(x_{\sigma(i)-1},y_{\sigma(i)+1})$
the set $z=\\{x_{1},\dots,x_{\sigma(i)-1},a,y_{\sigma(i)+1},\dots,y_{k}\\}$
has $k$ elements that have just been enumerated in increasing order. Moreover
$\sigma(i)\neq\min(I)$ yields $|\Delta(x,z)|\leq t$ and, therefore, $(x,z)$ is
indeed $(\varepsilon,\sigma)$-sound, which implies $x\strictif z$. Similarly,
$\sigma(i)\neq\max(I)$ leads to $z\strictif y$.

Next we suppose that $\sigma(i)=\min(I)$, which owing to the second bullet
entails

$a<\min\\{x_{\sigma(i)+1},y_{\sigma(i)+1}\\}\,.$

Let $j\in[k]$ be the second smallest index with $\sigma(j)\in I$.

If | and | then we set $z=$
---|---|---
$x_{\sigma(j)}<y_{\sigma(j)}$ | $\sigma(j)<\max(I)$ |  $\\{x_{1},\dots,x_{\sigma(i)-1},a,x_{\sigma(i)+1},\dots,x_{\sigma(j)},y_{\sigma(j)+1},\dots,y_{k}\\}$,
$x_{\sigma(j)}<y_{\sigma(j)}$ | $\sigma(j)=\max(I)$ |  $\\{x_{1},\dots,x_{\sigma(i)-1},a,x_{\sigma(i)+1},\dots,x_{\sigma(j)-1},y_{\sigma(j)},\dots,y_{k}\\}$,
$x_{\sigma(j)}>y_{\sigma(j)}$ | $\sigma(j)<\max(I)$ |  $\\{x_{1},\dots,x_{\sigma(i)-1},a,y_{\sigma(i)+1},\dots,y_{\sigma(j)},x_{\sigma(j)+1},\dots,x_{k}\\}$,
$x_{\sigma(j)}>y_{\sigma(j)}$ | $\sigma(j)=\max(I)$ |  $\\{x_{1},\dots,x_{\sigma(i)-1},a,y_{\sigma(i)+1},\dots,y_{\sigma(j)-1},x_{\sigma(j)},\dots,x_{k}\\}$.

In all four cases we have listed the elements of $z$ in increasing order.
Furthermore, in almost all cases we have $|\Delta(x,z)|\leq t$ and,
consequently, $x\strictif z$. In fact, the only exception occurs if we are in
the second case and $t=2$. But if this happens, then

$P=\bigl{(}\\{x_{1},\dots,x_{\sigma(i)-1}\\},\\{x_{\sigma(i)},a\\},\\{x_{\sigma(i)+1},\dots,x_{\sigma(j)-1}\\},\\{x_{\sigma(j)},y_{\sigma(j)}\\},\\{y_{\sigma(j)+1},\dots,y_{k}\\}\bigr{)}$

is an $\sigma(i)\sigma(j)$-decider. Since the ordering is permutation-
definite, we know that it orders the four-element set $\langle P\rangle$
“correctly” and, as $x$, $z$ belong to this set, $x\strictif z$ holds in this
case as well.

Similarly, in almost all cases we have $\Delta(y,z)\leq t$ and $y\strictif z$,
the only exception occurring if we are in the fourth case and $t=2$. Under
these circumstances

$Q=\bigl{(}\\{x_{1},\dots,x_{\sigma(i)-1}\\},\\{a,y_{\sigma(i)}\\},\\{y_{\sigma(i)+1},\dots,y_{\sigma(j)-1}\\},\\{x_{\sigma(j)},y_{\sigma(j)}\\},\\{x_{\sigma(j)+1},\dots,x_{k}\\}\bigr{)}$

is an $\sigma(i)\sigma(j)$-decider and, as before, $y,z\in\langle Q\rangle$
implies $y\strictif z$.

This concludes our discussion of the case $\sigma(i)=\min(I)$ and it remains
to deal with the case $\sigma(i)=\max(I)$. Here one can either perform a
similar argument, or one argues that this case reduces to the previous one by
reversion the ordering of the ground set. That is, one considers the ordering
$\bigl{(}(-L)^{(k)},{}^{\star}\bigr{)}$ defined by

$x{}^{\star}y\,\,\,\Longleftrightarrow\,\,\,(-x)\strictif(-y)\,,$

where $-L$ means $\\{-\ell\colon\ell\in L\\}$ and $-x$, $-y$ are defined
similarly. If one replaces by ⋆, then $I^{\star}=(k+1)-I$ assumes the rôle of
$I$, minima correspond to maxima and the second and third bullet in the
assumption of our lemma are exchanged. ∎

We proceed with the existence of “dense” canonical subsets promised earlier.

######  Lemma 3.7.

If $N\geq 2k$ and the ordering $([N]^{(k)},\strictif)$ is both sign-definite
and permutation-definite, then there exists a set $W\subseteq[N]$ of size
$|W|\geq 2^{1-k}N$ such that is canonical on $W^{(k)}$.

###### Proof.

For every $t\in[k]$ we set

$W_{t}=\bigl{\\{}n\in[N]\colon n\equiv 1\pmod{2^{t-1}}\bigr{\\}}\,.$

Clearly $|W_{k}|\geq 2^{1-k}N$, so it suffices to prove that is canonical on
$W_{k}^{(k)}$.

Denote the sign-vector of by
$\varepsilon=(\varepsilon_{1},\dots,\varepsilon_{k})$ and let
$\sigma\in\mathfrak{S}_{k}$ be the permutation obtained from by means of Lemma
3.5. Let us prove by induction on $t\in[k]$ that if two $k$-element subsets
$x,y\subseteq W_{t}$ satisfy $|\Delta(x,y)|\leq t$, then $(x,y)$ is
$(\varepsilon,\sigma)$-sound.

In the base case $t=1$ we have $W_{1}=[N]$ and everything follows from our
assumption that be sign-definite. In the induction step from $t\in[k-1]$ to
$t+1$ we appeal to Lemma 3.6. Since no two elements of $W_{t+1}$ occur in
consecutive positions of $W_{t}$, the bulleted assumptions are satisfied and
thus there are no problems with the induction step.

Since $|\Delta(x,y)|\leq k$ holds for all $k$-element subsets of $W_{k}$, the
case $t=k$ of our claim proves the lemma. ∎

Next we characterise the canonical orderings on $([N]^{(k)},\strictif)$ for
$N\geq 2k+1$.

######  Lemma 3.8.

If $N\geq 2k+1$ and the ordering $([N]^{(k)},\strictif)$ is canonical, then
there exists a pair
$(\varepsilon,\sigma)\in\\{-1,+1\\}^{k}\times\mathfrak{S}_{k}$ such that is
the ordering associated with $(\varepsilon,\sigma)$.

###### Proof.

Let $\varepsilon$ and $\sigma$ denote the sign vector and the permutation of
as introduced in §3.2. We shall show that coincides with the canonical
ordering associated to $(\varepsilon,\sigma)$.

Otherwise there exists a pair $(x,y)$ of subsets of $[N]$ that fails to be
$(\varepsilon,\sigma)$-sound. Assume that such a pair $(x,y)$ is chosen with
$t+1=|\Delta(x,y)|$ minimum. Since is sign-definite we know that $t\in[k-1]$.
Set $I=\Delta(x,y)$ and let $i\in[k]$ be the smallest index with $\sigma(i)\in
I$. By symmetry we may assume that $x_{\sigma(i)}<y_{\sigma(i)}$. Due to
$|I|\geq 2$ it cannot be the case that $\sigma(i)$ is both the minimum and the
maximum of $I$ and as in the proof of Lemma 3.6 it suffices to study the case
$\sigma(i)\neq\max(I)$.

First Case: $\max(x\cup y)<N$

Define a strictly increasing map $\varphi\colon x\cup y\longrightarrow[N]$ by
$\varphi(z)=z$ for $z\leq x_{\sigma(i)}$ and $\varphi(z)=z+1$ for
$z>x_{\sigma(i)}$. Now by Lemma 3.6 the pair
$\bigl{(}\varphi[x],\varphi[y]\bigr{)}$ is $(\varepsilon,\sigma)$-sound.
Moreover, the canonicity of tells us that $\big{(}(x\cup
y)^{(k)},\strictif\bigr{)}$ and $\big{(}\varphi[x\cup
y]^{(k)},\strictif\bigr{)}$ are isomorphic via $\varphi$. For these reasons,
the pair $(x,y)$ is $(\varepsilon,\sigma)$-sound as well.

Second Case: $\max(x\cup y)=N$

Let $\eta\colon x\cup y\longrightarrow[|x\cup y|]$ be order-preserving. In
view of $|x\cup y|\leq 2k<N$ we know from the first case that the pair
$\bigl{(}\eta[x],\eta[y]\bigr{)}$ is $(\varepsilon,\sigma)$-sound and by
canonicity so is $(x,y)$. ∎

######  Remark 3.9.

The results of this subsection easily yield the weaker upper bound

$\mathrm{L}^{(k)}(n)\leq\mathrm{R}^{(k+2)}\left(2^{k-1}n,\tbinom{k+2}{2}!\right)\leq
t_{k+1}(C_{k}n)\,.$

To see this, let $([N]^{(k)},\strictif)$ be any ordering, where
$N=\mathrm{R}^{(k+2)}(2^{k-1}n,\binom{k+2}{2}!)$. For a set $A\in[N]^{(k+2)}$
there are $\binom{k+2}{2}!$ possibilities how the restriction of to
$A^{(k+2)}$ can look. So by the definition of Ramsey numbers there is a set
$Z\subseteq[N]$ with $|Z|=2^{k-1}n$ such that for all $A,B\subseteq Z$ with
$|A|=|B|=k+2$ the order-preserving map $\eta\colon A\longrightarrow B$ induces
an order preserving map from $(A^{(k)},\strictif)$ to $(B^{(k)},\strictif)$.
This implies, in particular, that is sign-definite and permutation-definite on
$Z^{(k)}$. Thus by Lemma 3.7 there exists a set $X\subseteq Z$ with $|X|\geq
2^{1-k}|Z|=n$ such that orders $X^{(k)}$ canonically.

Now it remains to save one exponentiation, which requires a more careful
reasoning.

###  3.3. Further concepts

Throughout this subsection, we fix a natural number $k\geq 2$. Let $\Gamma$
denote the set of all orderings that can be imposed on $[k+2]^{(k)}$. We
regard $\Gamma$ as a set of colours having the size
$|\Gamma|=\binom{k+2}{2}!$. As in Remark 3.9 we associate with every ordering
$([N]^{(k)},\strictif)$ the colouring
$f\colon[N]^{(k+2)}\longrightarrow\Gamma$ mapping every $A\in[N]^{(k+2)}$ to
the unique ordering $\YY\in\Gamma$ with the property that
$(A^{(k)},\strictif)$ and $([k+2]^{(k)},\YY)$ are isomorphic via the order-
preserving map from $A$ to $[k+2]$. Roughly speaking, what Theorem 1.4 asserts
is that colourings of this form are so special that one can prove a Ramsey
theorem for them that requires just $k$ exponentiations rather than the
expected $k+1$ exponentiations.

For an integer $m\in[k+1]$ we shall say that an ordering
$([N]^{(k)},\strictif)$ is governed by $m$-sets if there exists a function
$f^{m}\colon[N]^{(m)}\longrightarrow\Gamma$ governing the function
$f\colon[N]^{(k+2)}\longrightarrow\Gamma$ associated with .

######  Definition 3.10.

If $([N]^{(k)},\strictif)$ is an ordering, $i,m\in[k]$, and $W\subseteq[N]$ we
say that $\varepsilon_{i}^{m}\colon W^{(m)}\longrightarrow\Phi$ is an $m$-ary
sign function for $(W^{(k)},\strictif)$ provided the following holds: If
$S=(X,A,Y)$ is an $i$-decider with $X\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}A\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}Y\subseteq
W$ and $M$ denotes the set consisting of the $m$ smallest elements of
$X\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}A\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}Y$, then
$\varepsilon_{i}(S)=\varepsilon^{m}_{i}(M)$.

In other words, the existence of an $m$-ary sign function
$\varepsilon_{i}^{m}\colon W^{(m)}\longrightarrow\Phi$ means that for
$i$-deciders $S=(X,A,Y)$ with $X\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}A\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}Y\subseteq
W$ the value of $\varepsilon_{i}(S)$ only depends on the first $m$ elements of
$X\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}A\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}Y$, while
the remaining $k+1-m$ elements of $X\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}A\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}Y$ are
destitute of any effect.

We shall frequently utilise the fact that if $m\in[2,k+1]$ and
$([N]^{(k)},\strictif)$ is governed by $m$-sets, then for every $i\in[k]$
there exists an $(m-1)$-ary sign function
$\varepsilon^{m-1}_{i}\colon[2,N]^{(m-1)}\longrightarrow\Phi$. This is because
for an $i$-decider $S=(X,A,Y)$ with $X\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}A\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}Y\subseteq[2,N]$
the value of $\varepsilon_{i}(S)$ can be inferred from the colour
$f(\\{1\\}\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}X\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}A\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}Y)$, where
$f\colon[N]^{(k+2)}\longrightarrow\Gamma$ denotes the function associated with
.

Suppose that $m\in[2,k+1]$, $W\subseteq{\mathds{Z}}$ and that
$(W^{(k)},\strictif)$ denotes an ordering possessing for every $i\in[k]$ an
$(m-1)$-ary sign function $\varepsilon^{m-1}_{i}\colon
W^{(m-1)}\longrightarrow\Phi$. If $i<j$ from $[k]$ are two indices and
$P=(X,A,Y,B,Z)$ is an $ij$-decider, we determine the colour
$\sigma^{m}_{ij}(P)$ as follows: Let $M$ denote the set consisting of the
$m-1$ smallest elements of $X\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}A\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}Y\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}B\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}Z$,
enumerate $A=\\{c_{i},d_{i}\\}$ as well as $B=\\{c_{j},d_{j}\\}$ in such a way
that $\varepsilon^{m-1}_{i}(M)c_{i}<\varepsilon^{m-1}_{i}(M)d_{i}$ and
$\varepsilon^{m-1}_{j}(M)c_{j}<\varepsilon^{m-1}_{j}(M)d_{j}$, and set

$\sigma^{m}_{ij}(P)=$ | provided that
---|---
$+1$ |  $P(c_{i},d_{j})\strictif P(d_{i},c_{j})$,
$-1$ |  $P(d_{i},c_{j})\strictif P(c_{i},d_{j})$.

######  Definition 3.11.

If $m\in[2,k+1]$, $ij\in[k]^{(2)}$, and the ordering $(W^{(k)},\strictif)$
possesses $(m-1)$-ary sign functions
$\varepsilon^{m-1}_{1},\dots,\varepsilon^{m-1}_{k}$, then we say that
$\sigma^{m}_{ij}\colon W^{(m)}\longrightarrow\Phi$ is an $m$-ary permutation
colouring if $\sigma^{m}_{ij}(P)=\sigma^{m}_{ij}(M)$ holds, whenever
$P=(X,A,Y,B,Z)$ is an $ij$-decider and $M$ denotes the set of the $m$ smallest
elements of $X\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}A\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}Y\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}B\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}Z$.

It should be clear that if in addition to possessing the $(m-1)$-ary sign
functions $\varepsilon^{m-1}_{1},\dots,\varepsilon^{m-1}_{k}$ the ordering
$(W^{(k)},\strictif)$ is governed by $m$-sets, then all $m$-ary permutation
colourings $(\sigma^{m}_{ij})$ with $ij\in[k]^{(2)}$ exist. Consequently, if
$([N]^{(k)},\strictif)$ is governed by $m$-sets, then for every pair
$ij\in[k]^{(2)}$ there exists a permutation colouring
$\sigma^{m}_{ij}\colon[2,N]^{(m)}\longrightarrow\Phi$.

###  3.4. Plan

Let us now pause to explain our strategy for proving Theorem 1.4. Given an
arbitrary ordering $([N]^{(k)},\strictif)$ with $N=t_{k}(n^{C_{k}})$ we need
to find a set $X\subseteq[N]$ of size $n$ such that $(X^{(k)},\strictif)$ is
ordered canonically. Following the same strategy as in Remark 3.9 it would
suffice to find a set $Y\subseteq[N]$ of size $2^{k-1}n$ which is
monochromatic with respect to the colouring
$f\colon[N]^{(k+2)}\longrightarrow\Gamma$ associated with . So the problem is
that we have only $k$ exponentiations available but hope to synchronise sets
of size $k+2$. What happens when we nevertheless perform the standard argument
producing upper bounds on Ramsey numbers is that we obtain sets
$[N]=Z_{k}\supseteq Z_{k-1}\supseteq\dots\supseteq Z_{0}$ such that for every
$m\in[0,k]$ the ordering $(Z_{m}^{(k)},\strictif)$ is governed by $(m+2)$-sets
and the size of $Z_{m}$ is, roughly, $m$ times exponential. In particular,
$Z_{0}$ has roughly the size $n^{C_{k}/2}$ and $(Z_{0}^{(k)},\strictif)$ is
governed by pairs. We may assume further that for every pair $ij\in[k]^{(2)}$
a permutation colouring $\sigma^{2}_{ij}\colon Z_{0}^{(2)}\longrightarrow\Phi$
exists. Moreover, it would suffice to find a set $Y\subseteq Z_{0}$ that is
monochromatic with respect to each $\sigma^{2}_{ij}$. This problem still
sounds like we need an exponential rather than a polynomial dependence between
$|Y|$ and $|Z_{0}|$, but Lemma 3.2 suggests the following alternative: if it
turns out that the colourings $\sigma^{2}_{ij}$ are monotone, then we are done
(for reasons explained in Lemma 3.14).

Now for some of the permutation colourings, like $\sigma^{2}_{1j}$ with
$j\in[2,k]$, one can indeed prove that they are always monotone (see Lemma
3.12 below), but it seems unlikely that in the setting we have described so
far one can prove that, for instance, $\sigma^{2}_{57}$ is always monotone. To
address this issue we exploit that the colourings $\sigma^{2}_{ij}$ become
known “gradually” in the course of the argument. When we have just constructed
a set $Z_{m}$ we already know a colouring $\sigma^{m+2}_{ij}$ of its
$(m+2)$-subsets such that, later, $\sigma^{2}_{ij}$ will govern its
restriction to $Z_{0}^{(m+2)}$. Suppose that in the sequence of colourings
$\sigma^{k}_{57},\sigma^{k-1}_{57},\dots,\sigma^{2}_{57}$ there is at least
one that is monotone, say $\sigma^{m+2}_{57}$, where $m\geq 1$. What Lemma 3.3
tells us is that when selecting $Z_{m-1}\subseteq Z_{m}$ we can not only
ensure that $(Z_{m-1}^{(k)},\strictif)$ is governed by $(m+1)$-sets, but also
that $\sigma^{m+1}_{57}$ is still monotone. Iterating this observation we see
that if some $\sigma^{m}_{57}$ is monotone, then we can protect ourselves
against ever loosing the monotonicity. Rather, we can arrange that all of
$\sigma^{m}_{57},\sigma^{m-1}_{57},\dots,\sigma^{2}_{57}$ are monotone. We
shall see in Lemma 3.13 that for $i\geq 2$ the permutation colouring
$\sigma^{i}_{ij}$ is automatically monotone. For these reasons, we can indeed
find a set $Z_{0}$ of polynomial size on which all pair colourings
$\sigma^{2}_{ij}$ are monotone, which essentially proves Theorem 1.4.

###  3.5. Canonisation

Coming to the details we begin by establishing the monotonicity of
$\sigma^{2}_{1j}$ for $j\in[2,k]$.

######  Lemma 3.12.

If the ordering $([N]^{(k)},\strictif)$ is sign-definite and governed by
pairs, then for every $j\in[2,k]$ the colouring $\sigma^{2}_{1j}$ is
increasing on $[2,N-k]^{(2)}$.

###### Proof.

Given three numbers $r<s<t$ from $[2,N-k]$ satisfying $\sigma_{1j}^{2}(rs)=+1$
we are to prove that $\sigma_{1j}^{2}(rt)=+1$. Let
$\varepsilon=(\varepsilon_{1},\dots,\varepsilon_{k})$ be the sign vector of .
We partition

$[N-k+1,N]=Y\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}B\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}Z\quad\text{
such that }Y<B<Z$

and $|Y|=j-2$, $|B|=2$, $|Z|=k-j$ and we enumerate $B=\\{c_{j},d_{j}\\}$ such
that $\varepsilon_{j}c_{j}<\varepsilon_{j}d_{j}$. Notice that
$P=(\varnothing,\\{r,s\\},Y,B,Z)$ and $Q=(\varnothing,\\{r,t\\},Y,B,Z)$ are
$1j$-deciders, whence $\sigma^{2}_{1j}(rs)=\sigma_{1j}(P)$ and
$\sigma^{2}_{1j}(rt)=\sigma_{1j}(Q)$. Thus our task is to derive
$\sigma_{1j}(Q)=+1$ from $\sigma_{1j}(P)=+1$.

First Case: $\varepsilon_{1}=+1$

Now $\sigma_{1j}(P)=+1$ is defined to mean $rYd_{j}Z\strictif sYc_{j}Z$, where
$rYd_{j}Z$ abbreviates $\\{r\\}\cup Y\cup\\{d_{j}\\}\cup Z$ and $sYc_{j}Z$ is
defined similarly. Moreover, $S=(\\{s,t\\},Yc_{j}Z)$ is a $1$-decider and
$\varepsilon_{1}(S)=\varepsilon_{1}=+1$ implies $sYc_{j}Z\strictif tYc_{j}Z$.
So the transitivity of leads to $rYd_{j}Z\strictif tYc_{j}Z$, for which reason
we have indeed $\sigma_{1j}(Q)=+1$.

Second Case: $\varepsilon_{1}=-1$

This time $\sigma_{ij}(P)=+1$ translates into $sYd_{j}Z\strictif rYc_{j}Z$ and
working with the $1$-decider $(\\{s,t\\},Yd_{j}Z)$ we infer $tYd_{j}Z\strictif
sYd_{j}Z$. Hence $tYd_{j}Z\strictif rYc_{j}Z$ and $\sigma_{1j}(Q)=+1$. ∎

Virtually the same proof also yields the following result.

######  Lemma 3.13.

If $2\leq i<j\leq k$ and the ordering $([N]^{(k)},\strictif)$ is governed by
$i$-sets, then the restriction of $\sigma^{i}_{ij}$ to $[2,N-k]^{(i)}$ is
decreasing.

###### Proof.

Suppose that $X\subseteq[2,N-k]$ and $r,s\in[2,N-k]$ satisfy $|X|=i-1$,
$X<r<s$, as well as $\sigma^{i}_{ij}(Xr)=-1$. We are to prove that
$\sigma^{i}_{ij}(Xs)=-1$. To this end we set $t=N-k+1$ and take three sets
$Y,Z,B\subseteq[N-k+2,N]$ with $Y<B<Z$ of the sizes $|Y|=j-i-1$, $|B|=2$, and
$|Z|=k-j$. Now $P=(X,\\{r,t\\},Y,B,Z)$ and $Q=(X,\\{s,t\\},Y,B,Z)$ are two
$ij$-deciders, we have $\sigma_{ij}(P)=\sigma^{i}_{ij}(Xr)=-1$, and it remains
to show $\sigma_{ij}(Q)=-1$. Recall that being governed by $i$-sets implies,
in particular, that there are $(i-1)$-ary sign functions
$\varepsilon^{i-1}_{i}$ and $\varepsilon^{i-1}_{j}$ defined on
$[2,N]^{(k-1)}$. So we can enumerate $B=\\{c_{j},d_{j}\\}$ in such a way that
$\varepsilon^{i-1}_{j}(X)c_{j}<\varepsilon^{i-1}_{j}(X)d_{j}$.

First Case: $\varepsilon^{i-1}_{i}(X)=+1$

Our assumption $\sigma^{i}_{ij}(P)=-1$ is defined to mean $XtYc_{j}Z\strictif
XrYd_{j}Z$. Furthermore, the triple $S=(X,\\{r,s\\},Yd_{j}Z)$ is an
$i$-decider and $\varepsilon_{i}(S)=\varepsilon^{i-1}_{i}(X)=+1$ implies that
$XrYd_{j}Z\strictif XsYd_{j}Z$. So altogether we have $XtYc_{j}Z\strictif
XsYd_{j}Z$ or, in other words, $\sigma^{i}_{ij}(Q)=-1$.

Second Case: $\varepsilon^{i-1}_{i}(X)=-1$

This time $\sigma^{i}_{ij}(P)=-1$ abbreviates the statement
$XrYc_{j}Z\strictif XtYd_{j}Z$ and the case hypothesis
$\varepsilon^{i-1}_{i}(X)=-1$ implies $XsYc_{j}Z\strictif XrYc_{j}Z$. For
these reasons we have $XsYc_{j}Z\strictif XtYd_{j}Z$, i.e.,
$\sigma^{i}_{ij}(Q)=-1$. ∎

Next we elaborate on the reason why we care about the monotonicity of the
permutation colourings.

######  Lemma 3.14.

There exists an absolute constant $C^{\prime}_{k}$ such that if $n\geq 2k$,
$N\geq C^{\prime}_{k}n^{k^{2}}$, the ordering $([N]^{(k)},\strictif)$ is
governed by pairs, and all permutation colourings $\sigma^{2}_{ij}$ with
$i\geq 2$ are monotone, then there is a set $Z\subseteq[N]$ of size $n$ such
that $(Z^{(k)},\strictif)$ is ordered canonically.

###### Proof.

Since the ordering is governed by pairs, it has unary sign functions
$\varepsilon_{1},\dots,\varepsilon_{k}$ defined on $[2,N]^{(1)}$. In other
words, every $x\in[2,N]$ has its own “opinion”

$\varepsilon(x)=\bigl{(}\varepsilon_{1}(x),\dots,\varepsilon_{k}(x)\bigr{)}\in\Phi^{k}$

what the sign vector should be, where $\Phi=\\{-1,+1\\}$ was introduced in
(3.1). Due to the Schubfachprinzip, there are a set $Y\subseteq[2,N]$ of size
$|Y|\geq 2^{-k}N$ as well as a vector $\varepsilon\in\Phi^{k}$ such that
$\varepsilon(y)=\varepsilon$ holds for every $y\in Y$. Now
$(Y^{(k)},\strictif)$ is sign-definite and by Lemma 3.12 the set
$Y_{\star}\subseteq Y$ obtained from $Y$ by deleting the smallest and the $k$
largest elements has the following property: for every pair $ij\in[k]^{(2)}$
the restriction of $\sigma^{2}_{ij}$ to $Y_{\star}^{(2)}$ is monotone. Notice
that $|Y_{\star}|\geq 2^{-k-1}N$.

Now Lemma 3.2 applied to $I=[k]^{(2)}$ and the family
$(\sigma^{2}_{ij})_{ij\in I}$ yields a set $Z_{\star}\subseteq Y_{\star}$ of
size $|Z_{\star}|=2^{k-1}n$ that is monochromatic with respect to every
$\sigma^{2}_{ij}$. This means that $(Z_{\star}^{(k)},\strictif)$ is not only
sign-definite but also permutation-definite, and Lemma 3.7 leads to the
desired set $Z$. ∎

It remains to execute the plan laid out in §3.4.

###### Proof of Theorem 1.4.

Given $k\geq 2$ we let $C^{\prime}_{k}$ denote the constant delivered by the
previous lemma. Recall that $\Gamma$ denotes the set of linear orderings of
$[k+2]^{(k)}$. Now for an arbitrary number $n\geq 2k$ we define recursively

$\displaystyle N_{0}$ $\displaystyle=C^{\prime}_{k}n^{k^{2}}+k+1\,,$
$\displaystyle N_{m}$
$\displaystyle=(2|\Gamma|)^{N_{m-1}^{m+1}}\cdot(2k^{2}N_{m-1}^{m})^{k^{2}N_{m-1}^{m}}+k+1\text{
for }m\in[k-2]\,,$ $\displaystyle N_{k-1}$
$\displaystyle=|\Gamma|^{N_{k-2}^{k-2}}\,,$ $\displaystyle\text{ and finally
}N_{k}$ $\displaystyle=|\Gamma|^{N_{k-1}^{k-1}}\,.$

An easy induction on $m$ discloses that for every $m\in[0,k]$ there exists an
absolute constant $C_{k,m}$ such that $N_{m}\leq
t_{m}\bigl{(}C_{k,m}n^{2k^{2}}\bigr{)}$ holds for all $n\geq 2k$. In
particular, there exists an absolute constant $C_{k}$ such that independently
of $n$ we have $N_{k}\leq t_{k}(n^{C_{k}})$. So it suffices to show that for
every ordering $([N_{k}]^{(k)},\strictif)$ there exists a set
$Z\subseteq[N_{k}]$ of size $n$ such that orders $Z^{(k)}$ canonically. Two
successive applications of Corollary 3.4 yield a set $Z_{k-2}\subseteq[N]$ of
size $|Z_{k-2}|=N_{k-2}$ such that $({Z}_{k-2}^{(k)},\strictif)$ is governed
by $k$-sets.

######  Claim 3.15.

For every $m\in[0,k-2]$ there exists a set $Z_{m}\subseteq[N_{k}]$ of size
$|Z_{m}|=N_{m}-k-1$ such that $(Z_{m}^{(k)},\strictif)$ is governed by
$(m+2)$-sets and for every $ij\in[m+2,k]^{(2)}$ there is a monotone
permutation colouring $\sigma^{m+2}_{ij}\colon
Z_{m}^{(m+2)}\longrightarrow\Phi$.

###### Proof of Claim 3.15.

We argue by decreasing induction on $m$, the base case $m=k-2$ already being
known. Now suppose that $m\in[k-2]$ and that we already have obtained a set
$Z_{m}\subseteq[N_{k}]$ with the desired property.

We plan to apply Lemma 3.3 to $N_{m-1}$, $m+2$, $m+2$, and $Z_{m}$ here in
place of $n$, $r$, $s$, and $X$ there. Instead of $f$ there we take the
function $f^{m+2}\colon Z_{m}^{(m+2)}\longrightarrow\Gamma$ governing the
function $f\colon[N_{k}]^{(k+2)}\longrightarrow\Gamma$ associated with .
Finally, we take the index set $I=[m+2,k]^{(2)}$, which clearly satisfies
$|I|\leq k^{2}$, and the family $(\sigma^{m+2}_{ij})_{ij\in I}$ of monotone
permutation colourings $\sigma^{m+2}_{ij}\colon
Z_{m}^{(m+2)}\longrightarrow\Phi$ provided by the induction hypothesis. Since

$N_{m}-k-1\geq(2|\Gamma|)^{N_{m-1}^{m+1}}\cdot(2|I|N_{m-1}^{m})^{|I|N_{m-1}^{m}}\,,$

the intended application of Lemma 3.3 is justified and we can obtain a set
$Z^{\prime}_{m-1}\subseteq Z_{m}$ of size $|Z^{\prime}_{m-1}|=N_{m-1}$ such
that $\bigl{(}{Z^{\prime}}_{m-1}^{(k)},\strictif\bigr{)}$ is governed by
$(m+1)$-sets and the permutation colourings $(\sigma^{m+1}_{ij})_{ij\in I}$
are monotone. The set $Z_{m-1}$ arising from $Z^{\prime}_{m-1}$ by cutting off
the smallest and the $k$ largest elements has all desired properties, because
by Lemma 3.13 the permutation colourings $\sigma^{m+1}_{m+1,j}$ with
$j\in[m+2,k]$ are monotone as well. ∎

Observe that the case $m=0$ yields a set $Z_{0}$ of size
$|Z_{0}|=N_{0}-(k+1)=C^{\prime}_{k}n^{k^{2}}$. By our choice of
$C^{\prime}_{k}$ according to Lemma 3.14 there exists a set $Z\subseteq Z_{0}$
of size $|Z|=n$ such that $(Z^{(k)},\strictif)$ is ordered canonically. This
concludes the proof of Theorem 1.4. ∎

##  4\. Shelah’s upper bound on Erdős-Rado numbers

In this section we show that the results in §3.1 can also be used for
reproving Shelah’s theorem that $k$-uniform Erdős-Rado numbers grow (at most)
$k-1$ times exponentially. More precisely, we shall show
$\operatorname{ER}^{(k)}(n)\leq t_{k-1}(C_{k}n^{6k})$, where, let us recall,
an estimate of the form $\operatorname{ER}^{(k)}(n)\leq N$ means that for
every equivalence relation $\equiv$ on $[N]^{(k)}$ there exist an $n$-element
subset $X\subseteq[N]$ and a set $I\subseteq[k]$ such that $\equiv$ and
$\equiv_{I}$ agree on $X^{(k)}$. Here, for two sets of positive integers
$x=\\{x_{1},\dots,x_{k}\\}$ and $y=\\{y_{1},\dots,y_{k}\\}$ with
$x_{1}<\dots<x_{k}$ and $y_{1}<\dots<y_{k}$ and for a subset $I\subseteq[k]$
the statement $x\equiv_{I}y$ is defined to mean that $x_{i}=y_{i}$ holds for
all $i\in I$. Throughout the entire section we fix an integer $k\geq 2$.
Moreover, $\Gamma$ will always denote the set of all equivalence relations on
$[k+2]^{(k)}$.

###  4.1. Preparation

Beginning as in Remark 3.9 we associate with every equivalence relation
$([N]^{(k)},\equiv)$ the colouring $f\colon[N]^{(k+2)}\longrightarrow\Gamma$
mapping every set $A\in[N]^{(k+2)}$ to the unique equivalence relation
$\sim\in\Gamma$ with the property that $(A^{(k)},\equiv)$ and
$([k+2]^{(k)},\sim)$ are isomorphic via the order-preserving map from $A$ to
$[k+2]$. For $m\in[k+2]$ we say that $([N]^{(k)},\equiv)$ is governed by
$m$-sets if there exists a function
$f^{m}\colon[N]^{(m)}\longrightarrow\Gamma$ which governs $f$. For instance,
every equivalence relation is governed by $(k+2)$-sets. Next we associate with
every equivalence relation some auxiliary colourings $g_{i}$ using the set of
colours $\Phi=\\{-1,+1\\}$ introduced in (3.1).

######  Definition 4.1.

Let $N\geq k+1$ be an integer and let $i\in[k]$ be an index. The
$i^{\mathrm{th}}$ auxiliary function
$g_{i}\colon[N]^{(k+1)}\longrightarrow\Phi$ of an equivalence relation
$([N]^{(k)},\equiv)$ is defined by

$g_{i}(z_{1},\dots,z_{k+1})=1\,\,\,\Longleftrightarrow\,\,\,\\{z_{1},\dots,z_{i-1},z_{i+1},\dots,z_{k+1}\\}\equiv\\{z_{1},\dots,z_{i},z_{i+2},\dots,z_{k+1}\\}$

whenever $1\leq z_{1}<\dots<z_{k+1}\leq N$.

Like the permutation colourings in the previous section, these functions will
later be synchronised by means of an iterative application of Lemma 3.3.
Notice that if an equivalence relation $([N]^{(k)},\equiv)$ is governed by
$m$-sets, then there exists a function
$g^{m-1}_{i}\colon[2,N]^{(m-1)}\longrightarrow\Phi$ governing the restriction
of $g_{i}$ to $[2,N]^{(k+1)}$. Our next result asserts that at some stage of
our argument these functions will automatically become monotone.

######  Lemma 4.2.

If $N\geq 2k$, $m\in[k]$, and $([N]^{(k)},\equiv)$ is governed by
$(m+1)$-sets, then the function
$g_{m}^{m}\colon[2,N]^{(m)}\longrightarrow\Phi$ is increasing on
$[2,N-k]^{(m)}$.

###### Proof.

Let some integers $2\leq a_{1}<\dots<a_{m}<a^{\prime}_{m}\leq N-k$ satisfying
$g_{m}^{m}(a_{1},\dots,a_{m})=1$ be given. We are to prove that
$g_{m}^{m}(a_{1},\dots,a_{m-1},a^{\prime}_{m})=1$ holds as well. Set $a_{0}=1$
and $a_{m+i}=N-k+i$ for every $i\in[k+1-m]$. Our assumption yields
$g_{m}({a_{1}},\dots,a_{k+1})=1$, whence

$\\{a_{1},\dots,a_{m},a_{m+2},\dots,a_{k+1}\\}\equiv\\{a_{1},\dots,a_{m-1},a_{m+1},\dots,a_{k+1}\\}\,.$

This piece of information is among the facts encoded in
$f(a_{0},\dots,a_{k+1})$ and, as $([N]^{(k)},\equiv)$ is governed by
$(m+1)$-sets, the same information is known to

$f(a_{0},\dots,a_{m},a^{\prime}_{m},a_{m+2},\dots,a_{k+1})\,.$

Consequently, we also have

$\\{a_{1},\dots,a_{m},a_{m+2},\dots,a_{k+1}\\}\equiv\\{a_{1},\dots,a_{m-1},a^{\prime}_{m},a_{m+2},\dots,a_{k+1}\\}\,.$

Both displayed equivalences have the same left side, so the transitivity of
$\equiv$ leads to

$\\{a_{1},\dots,a_{m-1},a^{\prime}_{m},a_{m+2},\dots,a_{k+1}\\}\equiv\\{a_{1},\dots,a_{m-1},a_{m+1},\dots,a_{k+1}\\}\,,$

for which reason

$g_{m}^{m}(a_{1},\dots,a_{m-1},a^{\prime}_{m})=g_{m}(a_{1},\dots,a_{m-1},a^{\prime}_{m},a_{m+1},\dots,a_{k+1})=1\,.\qed$

Let us observe that for canonical equivalence relations $\equiv_{I}$ with
$I\subseteq[k]$ the auxiliary functions $g_{1},\dots,g_{k}$ are constant.
Moreover, if $\varepsilon_{1},\dots,\varepsilon_{k}\in\Phi$ denote the values
these functions always attain, then $I=\\{i\in[k]\colon\varepsilon_{i}=-1\\}$.
In the converse direction, if we have an equivalence relation
$([N]^{(k)},\equiv)$ with the property that such colours
$\varepsilon_{1},\dots,\varepsilon_{k}\in\Phi$ exist, then we may define
$I=\\{i\in[k]\colon\varepsilon_{i}=-1\\}$, but it does not follow immediately
that $\equiv$ coincides with the canonical equivalence relation $\equiv_{I}$.
This is why we require an additional purging argument.

######  Definition 4.3.

For $i\in[k]$ an equivalence relation $([N]^{(k)},\equiv)$ is said to be
$i$-purged if for all integers
$a_{1},\dots,a_{i},b_{1},\dots,b_{i},c_{i+1},\dots,c_{k+1}$ satisfying

  1. ( )

$1\leq a_{1}<\dots<a_{i}$ and $1\leq b_{1}<\dots<b_{i}$,

  2. ( )

$\max(a_{i},b_{i})<c_{i+1}<\dots<c_{k+1}\leq N$,

  3. ( )

$g_{i}(a_{1},\dots,a_{i},c_{i+1},\dots,c_{k+1})=g_{i}(b_{1},\dots,b_{i},c_{i+1},\dots,c_{k+1})=-1$,

  4. ( )

and
$\\{a_{1},\dots,a_{i},c_{i+1},\dots,c_{k}\\}\equiv\\{b_{1},\dots,b_{i},c_{i+1},\dots,c_{k}\\}$

we have $a_{i}=b_{i}$.

######  Lemma 4.4.

Suppose that the equivalence relation $([N]^{(k)},\equiv)$ is $i$-purged for
every $i\in[k]$. If the auxiliary functions $g_{1},\dots,g_{k}$ are constant,
then $([N-1]^{(k)},\equiv)$ is canonical.

###### Proof.

Let $\varepsilon_{1},\dots,\varepsilon_{k}\in\Phi$ be the values which
$g_{1},\dots,g_{k}$ always attain and set

$I=\big{\\{}i\in[k]\colon\varepsilon_{i}=-1\big{\\}}\,.$

It suffices to prove that for any two sets $a=\\{a_{1},\dots,a_{k}\\}$ and
$b=\\{b_{1},\dots,b_{k}\\}$ from $[N-1]^{(k)}$ whose elements have just been
enumerated in increasing order the statement

$\\{a_{1},\dots,a_{k}\\}\equiv\\{b_{1},\dots,b_{k}\\}\,\,\,\Longleftrightarrow\,\,\,\forall
i\in I\,\,\,a_{i}=b_{i}$ (4.1)

is valid. To this end we argue by induction on the number
$\mu=|\\{i\in[k]\colon a_{i}\neq b_{i}\\}|$ counting the indices where $a$ and
$b$ disagree. In the base case $\mu=0$ we have $a=b$ and both sides of the
equivalence (4.1) are true. Now suppose that $\mu\in[k]$ has the property that
(4.1) holds for all pairs of sets from $[N]^{(k)}$ disagreeing less than $\mu$
times. For the induction step we assume that $a,b\in[N]^{(k)}$ disagree with
respect to exactly $\mu$ indices.

Beginning with the backwards implication we assume $a_{i}=b_{i}$ for all $i\in
I$ and intend to derive $a\equiv b$. Notice that the smallest index
$i(\star)\in[k]$ satisfying $a_{i(\star)}\neq b_{i(\star)}$ belongs to
${[k]\smallsetminus I}$, whence $\varepsilon_{i(\star)}=1$. By symmetry we may
suppose that $a_{i(\star)}<b_{i(\star)}$. The induction hypothesis implies
that the set $c=b\cup\\{a_{i(\star)}\\}\smallsetminus\\{b_{i(\star)}\\}$ is
equivalent to $a$ with respect to $\equiv$. Moreover, the definition of

$g_{i(\star)}(b_{1},\dots,b_{i(\star)-1},a_{i(\star)},b_{i(\star)},\dots,b_{k})=\varepsilon_{i(\star)}=1$

yields $b\equiv c$, so altogether we have indeed $a\equiv c\equiv b$.

Now suppose conversely that $a\equiv b$, where $a,b\in[N-1]^{(k)}$. Due to
$\mu>0$ there exists a largest integer $i(\star)\in[k]$ such that
$a_{i(\star)}\neq b_{i(\star)}$. Applying the assumption that $\equiv$ be
$i(\star)$-purged to

  1. $\bullet$

$a_{1}<\dots<a_{i(\star)}$, $b_{1}<\dots<b_{i(\star)}$,

  2. $\bullet$

and $a_{i(\star)+1}=b_{i(\star)+1},\dots,a_{k}=b_{k},N$ playing the rôles of
$c_{i(\star)+1},\dots,c_{k+1}$

we infer $\varepsilon_{i(\star)}=+1$, i.e., $i(\star)\notin I$. By symmetry we
may again assume $a_{i(\star)}<b_{i(\star)}$. Now

$g_{i(\star)}(a_{1},\dots,a_{i(\star)},b_{i(\star)},a_{i(\star)+1},\dots,a_{k})=\varepsilon_{i(\star)}=1$

implies that the set
$c=a\cup\\{b_{i(\star)}\\}\smallsetminus\\{a_{i(\star)}\\}$ is equivalent to
$a$ with respect to $\equiv$. Since $b$ and $c$ disagree only $\mu-1$ times,
the induction hypothesis yields $b_{i}=c_{i}$ for all $i\in I$. Together with
$i(\star)\not\in I$ this shows that we have indeed $a_{i}=b_{i}$ for all $i\in
I$. This completes the induction step and, therefore, the proof of (4.1). In
particular, $\equiv$ is canonical. ∎

The next result shows that from a quantitative point of view purging is
accompanied by a polynomial dependence of the involved constants.

######  Lemma 4.5.

Let $m\in[k]$, $n\geq k$, and $N\geq(2kn)^{2k}$. If an equivalence relation
$([N]^{(k)},\equiv)$ is governed by $(m+1)$-sets, then there exists a set
$Z\subseteq[N]$ of size $n$ such that $(Z^{(k)},\equiv)$ is $m$-purged.

###### Proof.

The potential counterexamples to $([2,N]^{(k)},\equiv)$ being $m$-purged can
be regarded as $(k+m+1)$-tuples of integers satisfying the conditions ( ) ‣
4.3 – ( ) ‣ 4.3 from Definition 4.3 and $a_{m}\neq b_{m}$. By symmetry it
suffices to worry about those counterexamples for which $a_{m}<b_{m}$. Bearing
this in mind we define $\Psi$ to be the set of all $(k+m)$-tuples

$(a_{1},\dots,a_{m},b_{1},\dots,b_{m},c_{m+1},\dots,c_{k})\in[2,N]^{k+m}$

such that

  1. $\bullet$

$a_{1}<\dots<a_{m}$, $b_{1}<\dots<b_{m}$,

  2. $\bullet$

$a_{m}<b_{m}$,

  3. $\bullet$

$\max(a_{m},b_{m})<c_{m+1}<\dots<c_{k}$,

  4. $\bullet$

$g_{m}^{m}(b_{1},\dots,b_{m})=-1$,

  5. $\bullet$

and
$\\{a_{1},\dots,a_{m},c_{m+1},\dots,c_{k}\\}\equiv\\{b_{1},\dots,b_{m},c_{m+1},\dots,c_{k}\\}$.

The key observation is that two members of $\Psi$ cannot differ in their
$(2m)^{\mathrm{th}}$ entry alone.

######  Claim 4.6.

If $(a_{1},\dots,a_{m},b_{1},\dots,b_{m},c_{m+1},\dots,c_{k})$ and
$(a_{1},\dots,a_{m},b_{1},\dots,b^{\prime}_{m},c_{m+1},\dots,c_{k})$ belong to
$\Psi$, then $b_{m}=b^{\prime}_{m}$.

###### Proof.

Assume contrariwise that $b_{m}<b^{\prime}_{m}$. Due to

$\\{b_{1},\dots,b^{\prime}_{m},c_{m+1},\dots,c_{k}\\}\equiv\\{a_{1},\dots,a_{m},c_{m+1},\dots,c_{k}\\}\equiv\\{b_{1},\dots,b_{m},c_{m+1},\dots,c_{k}\\}$

we know $g_{m}(b_{1},\dots,b_{m},b_{m}^{\prime},c_{m+1},\dots,c_{k})=1$, which
contradicts $g_{m}^{m}(b_{1},\dots,b_{m})=-1$. ∎

Now we consider the partition

$\Psi=\Psi_{0}\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}\dots\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}\Psi_{m-1}$

defined by

$\Psi_{i}=\bigl{\\{}(a_{1},\dots,a_{m},b_{1},\dots,b_{m},c_{m+1},\dots,c_{k})\in\Psi\colon|\\{a_{1},\dots,a_{m},b_{1},\dots,b_{m-1}\\}|=m+i\bigr{\\}}$

for every $i\in[0,m-1]$. As a consequence of Claim 4.6 every
$(a_{1},\dots,c_{k})\in\Psi_{i}$ can be described uniquely by specifying

  1. (0 )

the $(k+i)$-element subset
$X=\\{a_{1},\dots,a_{m},b_{1},\dots,b_{m-1},c_{m+1},\dots,c_{k}\\}$ of $[2,N]$

  2. (0 )

and telling for each of $a_{1},\dots,a_{m},b_{1},\dots,b_{m-1}$ to which of
the $m+i$ members of $Y=\\{a_{1},\dots,a_{m},b_{1},\dots,b_{m-1}\\}$ they are
equal.

There are $\binom{N-1}{k+i}$ possibilities for the first decision. The set $Y$
can be obtained from $X$ by removing the $k-m$ largest elements and, in
particular, $Y$ is definable from $X$. Thus there are at most $(m+i)^{2m-1}$
possibilities for (0 ). Altogether, theses considerations establish

$|\Psi_{i}|\leq\binom{N-1}{k+i}(m+i)^{2m-1}\leq(N-1)^{k+i}(2m)^{2m-1}$

In combination with

$\displaystyle\sum_{Z\in[2,N]^{(n)}}|\Psi\cap Z^{k+m}|$
$\displaystyle=\sum_{i=0}^{m-1}\binom{(N-1)-(k+i+1)}{n-(k+i+1)}|\Psi_{i}|$
$\displaystyle\leq\binom{N-1}{n}\sum_{i=0}^{m-1}\Big{(}\frac{n}{N-1}\Big{)}^{k+i+1}|\Psi_{i}|$

this implies

$\displaystyle\sum_{Z\in[2,N]^{(n)}}|\Psi\cap Z^{k+m}|$
$\displaystyle\leq\binom{N-1}{n}\sum_{i=0}^{m-1}\frac{n^{k+i+1}}{N-1}(2m)^{2m-1}$
$\displaystyle\leq\frac{(2mn)^{2k}}{2(N-1)}\binom{N-1}{n}<\binom{N-1}{n}\,.$

Consequently some set $Z\in[2,N]^{(n)}$ satisfies $\Psi\cap
Z^{k+m}=\varnothing$. Due to the definition of $\Psi$ every such set $Z$ is
$m$-purged. ∎

###  4.2. Plan

Suppose that we have an equivalence relation $([N]^{(k)},\equiv)$, where $N$
is, roughly speaking, $k-1$ times exponential in $n$, and that we want to find
a subset $X\subseteq[N]$ of size $n$ such that $(X^{(k)},\equiv)$ is
canonical. The material in the previous subsection suggests the following
strategy. Letting $f\colon[N]^{(k+2)}\longrightarrow\Gamma$ denote the
function associated with $\equiv$ we want to select appropriate subsets
$[N]=Z_{k-1}\supseteq\dots\supseteq Z_{0}$ such that for each $m\in[0,k-1]$
the size of $Z_{m}$ is, roughly, $m$ times exponential in $n$ and the
restriction of $f$ to $Z_{m}^{(k+2)}$ is governed by $(m+3)$-sets. Lemma 4.2
tells us that if we construct such a sequence of sets $(Z_{m})_{0\leq m\leq
k-1}$ by means of an iterative applications of Lemma 3.3, then we can achieve
that the restrictions of $g^{2}_{2},\dots,g^{2}_{k}$ to $Z_{0}^{(2)}$ are
monotone. Now $|Z_{0}|$ depends polynomially on $n$, which severely restricts
our possibilities as to how the argument can be continued. Certainly Lemma 3.2
allows us to synchronise $g_{2},\dots,g_{k}$. Moreover, synchronising $g_{1}$
will only cost an additional square root; essentially this is due to the
formula $\operatorname{ER}^{(1)}(n)\leq n^{2}$. Finally $k$ successive
applications of Lemma 4.5 allow us to perform a complete purging, and by Lemma
4.4 we will thereby be done.

Now if one completely ignores the last exponent $C_{k}$ for which one will end
up proving $\operatorname{ER}^{(k)}(n)\leq t_{k-1}(n^{C_{k}})$, then it is
entirely immaterial in which order one carries the various steps of the
argument out. But from a quantitative point of view it seems recommendable to
perform each purging step as early as possible. Illustrating this point by
means of an example we give a brief sketch as to how one can prove
$\operatorname{ER}^{(4)}(n)\leq t_{3}(Cn^{24})$.

  1. $\bullet$

Start with an arbitrary equivalence relation $([N]^{(4)},\equiv)$, where
$N=t_{3}(Cn^{24})$, and let $f\colon[N]^{(6)}\longrightarrow\Gamma$ be its
associated function.

  2. $\bullet$

By Corollary 3.4 there is a set $Z_{2}\subseteq Z_{3}=[N]$ of size
$t_{2}(C^{\prime}n^{24})$ on which $f$ is governed by quintuples. Now
$g^{4}_{4}$ is monotone by Lemma 4.2.

  3. $\bullet$

Before doing anything else we appeal to Lemma 4.5 and get a $4$-purged set
$P_{2}\subseteq Z_{2}$ of size $t_{2}(C^{\prime\prime}n^{24})$, where
$C^{\prime\prime}$ is extremely close to $C^{\prime}$.

  4. $\bullet$

Next we apply Lemma 3.3 and obtain $Z_{1}\subseteq P_{2}$ of size
$t_{1}(C^{\prime\prime\prime}n^{24})$ such that $g^{3}_{3}$, $g^{3}_{4}$ are
monotone and $f$ is governed by quadruples.

  5. $\bullet$

Now Lemma 4.5 leads us to a $3$-purged set $P_{1}\subseteq Z_{1}$ of size
$t_{1}(C^{\prime\prime\prime\prime}n^{24})$.

  6. $\bullet$

Only now we appeal to Lemma 3.3 again and take $Z_{0}\subseteq P_{1}$ of size
$C^{\prime\prime\prime\prime\prime}n^{8}$ such that $g^{2}_{2}$, $g^{2}_{3}$,
$g^{2}_{4}$ are monotone and $f$ is governed by triples.

The next lemma tells us how to complete the argument once $Z_{0}$ is found.

######  Lemma 4.7.

Let $n\geq k$, $N\geq(k-1)!(2n)^{2k}$, and let $([N]^{(k)},\equiv)$ be an
equivalence relation which is governed by triples and $i$-purged for every
$i\in[3,k]$. If the functions $g_{2}^{2},\dots,g_{k}^{2}$ defined on
$[2,N]^{(2)}$ are monotone, then there exists a set $X\subseteq[N]$ of size
$n$ such that $(X^{(k)},\equiv)$ is canonical.

###### Proof.

Due to the monotonicity of $g_{2}^{2},\dots,g_{k}^{2}$ and
$N-1\geq(k-1)!(4n^{2}-1)^{k}$ Lemma 3.2 yields a subset $Y\subseteq[2,N]$ of
size $|Y|=4n^{2}-1$ such that the functions $g_{2}^{2},\dots,g_{k}^{2}$ are
constant on $Y^{(2)}$. Denote the $k-1$ largest elements of $Y$ by
$y_{1}<\dots<y_{k-1}$ and define an equivalence relation $\sim$ on
$Y\smallsetminus\\{y_{1},\dots,y_{k-1}\\}$ by

$a\sim
b\,\,\,\Longleftrightarrow\,\,\,\\{a,y_{1},\dots,y_{k-1}\\}\equiv\\{b,y_{1},\dots,y_{k-1}\\}\,.$

In view of $n\geq k\geq 2$ we have
$|Y\smallsetminus\\{y_{1},\dots,y_{k-1}\\}|=4n^{2}-k\geq(2n-k+1)^{2}+1$ and,
consequently, there exists a set $Z^{-}\subseteq
Y\smallsetminus\\{y_{1},\dots,y_{k-1}\\}$ of size $2n-k+2$ which is either
contained in an equivalence class of $\sim$ or consists of numbers that are
mutually non-equivalent with respect to $\sim$. In both cases the set
$Z=Z^{-}\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}\\{y_{1},\dots,y_{k-1}\\}$
has the property that the restriction of $g^{2}_{1}$ to $Z^{(2)}$ is constant.
Notice that the cardinality of $Z$ is $2n+1$. Enumerating the elements of $Z$
in increasing order we write $Z=\\{z_{1},\dots,z_{2n+1}\\}$.

The remainder of the proof we shall show that

$X_{\star}=\bigl{\\{}z_{1},z_{3},\dots,z_{2n+1}\bigr{\\}}$

has the property that $(X_{\star}^{(k)},\equiv)$ is $1$-purged and $2$-purged.
In the light of Lemma 4.4 this will imply that the $n$-element set
$X=X_{\star}\smallsetminus\\{z_{2n+1}\\}$ is as desired.

Starting with the former goal we let $\varepsilon_{1}\in\Phi$ be the constant
value that $g^{2}_{1}$ attains on $X_{\star}^{(2)}$. Because of Definition 4.3
( ) ‣ 4.3 we may suppose that $\varepsilon_{1}=-1$. Now let

$a_{1}\leq b_{1}<c_{2}<\dots<c_{k+1}$

be $k+2$ members of $X_{\star}$ satisfying
$\\{a_{1},c_{2},\dots,c_{k}\\}\equiv\\{b_{1},c_{2},\dots,c_{k}\\}$. As the
assumption $a_{1}<b_{1}$ would yield
$\varepsilon_{1}=g_{1}(a_{1},b_{1},c_{2},\dots,c_{k})=1$, we have indeed
$a_{1}=b_{1}$, as required.

It remains to show that $(X_{\star}^{(k)},\equiv)$ is $2$-purged as well. As
before, we may suppose that the constant value $\varepsilon_{2}$ attained by
$g_{2}$ on $X_{\star}^{(k+1)}$ is $-1$. Assume for the sake of contradiction
that there exist $k+3$ members $a_{1}<a_{2}<b_{2}$ and
$b_{1}<b_{2}<c_{3}<\dots<c_{k+1}$ of $X$ such that

$\\{a_{1},a_{2},c_{3},\dots,c_{k}\\}\equiv\\{b_{1},b_{2},c_{3},\dots,c_{k}\\}\,.$
(4.2)

Pick a number $q\in Z$ such that $b_{2}<q<c_{3}$. Since $f$ is governed by
triples, we have

$f(a_{1},a_{2},b_{1},b_{2},c_{3},\dots,c_{k})=f(a_{1},a_{2},b_{1},q,c_{3},\dots,c_{k})\,.$

So (4.2) entails

$\\{a_{1},a_{2},c_{3},\dots,c_{k}\\}\equiv\\{b_{1},q,c_{3},\dots,c_{k}\\}$

and altogether we obtain

$\\{b_{1},b_{2},c_{3},\dots,c_{k}\\}\equiv\\{b_{1},q,c_{3},\dots,c_{k}\\}\,,$

which leads us to the contradiction

$\varepsilon_{2}=g_{2}(b_{1},b_{2},q,c_{3},\dots,c_{k})=1\,.\qed$

###  4.3. Canonisation

It remains to execute the plan discussed in the foregoing subsection. Given
$n\geq k\geq 2$ we define positive integers
$N_{0},P_{1},N_{1},\dots,P_{k-2},N_{k-2},N_{k-1}$ according to the following
recursive rules.

$\displaystyle N_{0}$ $\displaystyle=(k-1)!(2n)^{2k}+(k+1)\,,$ $\displaystyle
P_{m}$
$\displaystyle=(2|\Gamma|)^{N_{m-1}^{m+2}}\cdot(2kN_{m-1}^{m})^{kN_{m-1}^{m}}\quad\text{
for }m\in[k-2]\,,$ $\displaystyle N_{m}$
$\displaystyle=(2kP_{m})^{2k}+(k+1)\quad\text{ for }m\in[k-2]\,,$
$\displaystyle N_{k-1}$ $\displaystyle=|\Gamma|^{N_{k-2}^{k+1}}\,.$

We want to prove that if $N\geq N_{k-1}$ then for every equivalence relation
$([N]^{(k)},\equiv)$ there exists a set $X\subseteq[N]$ of size $n$ such that
$(X^{(k)},\equiv)$ is canonical. This will imply

$\operatorname{ER}^{(k)}(n)\leq N_{k-1}\leq t_{k-1}(C_{k}n^{6k})\,,$ (4.3)

where $C_{k}$ depends only on $k$.

Let $f\colon[N]^{k+2}\longrightarrow\Gamma$ be the function associated to a
given equivalence relation $([N]^{(k)},\equiv)$, where $N\geq N_{k-1}$. An
initial application of Corollary 3.4 leads to a set
$Z^{\prime}_{k-2}\subseteq[N]$ such that $({Z^{\prime}}^{(k)}_{k-2},\equiv)$
is governed by $(k+1)$-sets and $|Z^{\prime}_{k-2}|=N_{k-2}$. According to
Lemma 4.2 the set $Z_{k-2}\subseteq Z^{\prime}_{k-2}$ that arises when one
removes the smallest and the $k$ largest elements of $Z_{k-2}^{\prime}$ has
the property that $g^{k}_{k}\colon{Z}^{(k)}_{k-2}\longrightarrow\Phi$ is
monotone. Notice that $|Z_{k-2}|=N_{k-2}-(k+1)$.

######  Claim 4.8.

For every $m\in[0,k-2]$ there exists a set $Z_{m}\subseteq[N]$ of size
$|Z_{m}|=N_{m}-(k+1)$ with the following properties:

  1. ( )

$(Z_{m}^{(k)},\equiv)$ is governed by $(m+3)$-sets.

  2. ( )

For every $i\in[m+2,k]$ the function $g_{i}^{m+2}$ is monotone.

  3. ( )

If $i\in[m+3,k]$, then $(Z_{m}^{(k)},\equiv)$ is $i$-purged.

Observe that the case $m=0$ yields a set $Z_{0}$ of size
$|Z_{0}|=(k-1)!(2n)^{2k}$. Thus Lemma 4.7 shows that Claim 4.8 implies (4.3).

###### Proof of Claim 4.8.

We argue by decreasing induction on $m$. In the base case $m=k-2$ clause ( ) ‣
4.8 holds vacuously and the set $Z_{k-2}$ defined above has the desired
properties.

Now suppose that for some $m\in[k-2]$ we have already found a subset
$Z_{m}\subseteq[N]$ of size $N_{m}-(k+1)=(2kP_{m})^{2k}$ fulfilling ( ) ‣ 4.8,
( ) ‣ 4.8, and ( ) ‣ 4.8. Owing to Lemma 4.5 there exists a set
$Q_{m}\subseteq Z_{m}$ of size $|Q_{m}|=P_{m}$ such that
$(P_{m}^{(k)},\equiv)$ is $(m+2)$-purged. Next we apply Lemma 3.3 to
$f^{m+3}\colon P_{m}^{(m+3)}\longrightarrow\Gamma$ and the family
$(g_{i}^{m+2})_{m+2\leq i\leq k}$ of monotone colourings. This yields a set
$Z^{\prime}_{m-1}\subseteq P_{m}$ of size $N_{m-1}$ such that
$({Z^{\prime}}_{m}^{(k)},\equiv)$ is governed by $(m+2)$-sets and for every
$i\in[m+2,k]$ the function $g_{i}^{m+1}$ is monotone. Finally Lemma 4.2 tells
us that the set $Z_{m-1}\subseteq Z^{\prime}_{m-1}$ obtained by removing the
smallest and the $k$ largest elements from $Z^{\prime}_{m-1}$ has the desired
properties. ∎

## References