# Complexity of frustration: a new source of non-local non-stabilizerness

J. Odavić<EMAIL_ADDRESS>Ruđer Bošković Institute, Bijenička cesta 54, 10000
Zagreb, Croatia  T. Haug<EMAIL_ADDRESS>QOLS, Blackett Laboratory, Imperial
College London SW7 2AZ, UK  G. Torre<EMAIL_ADDRESS>Ruđer Bošković
Institute, Bijenička cesta 54, 10000 Zagreb, Croatia  A. Hamma
<EMAIL_ADDRESS>Dipartimento di Fisica Ettore Pancini, Università
degli Studi di Napoli Federico II, Via Cinthia, 80126 Fuorigrotta, Napoli NA
Physics Department, University of Massachusetts Boston, 02125, USA  INFN,
Sezione di Napoli, Italy  F. Franchini<EMAIL_ADDRESS>Ruđer Bošković
Institute, Bijenička cesta 54, 10000 Zagreb, Croatia  S. M. Giampaolo
<EMAIL_ADDRESS>Ruđer Bošković Institute, Bijenička cesta 54, 10000 Zagreb,
Croatia

###### Abstract

We advance the characterization of complexity in quantum many-body systems by
examining $W$-states embedded in a spin chain. Such states show an amount of
non-stabilizerness or “magic” (measured as the Stabilizer Rényi Entropy –SRE–)
that grows logarithmic with the number of qubits/spins. We focus on systems
whose Hamiltonian admits a classical point with an extensive degeneracy. Near
these points, a Clifford circuit can convert the ground state into a
$W$-state, while in the rest of the phase to which the classic point belongs,
it is dressed with local quantum correlations. Topological frustrated quantum
spin-chains host phases with the desired phenomenology, and we show that their
ground state’s SRE is the sum of that of the $W$-states plus an extensive
local contribution. Our work reveals that $W$-states/frustrated ground states
display a non-local degree of complexity that can be harvested as a quantum
resource and has no counterpart in GHZ states/non-frustrated systems.

The problem of simulating quantum states is, generally, intractable for
classical computers. For this reason, Feynman put forward the notion of a
quantum computer [1] as only a quantum device would be able to simulate a
generic quantum system efficiently. This necessity is of particular relevance
for states of quantum many-body systems that can be used to accommodate new
exotic phenomena of matter like quantum criticality [2], topological order [3,
4, 5], exotic metals without quasi-particle excitations [6, 7] quantum systems
away from equilibrium like systems of ultra-cold atomic gases [8, 9, 10], etc.

However, the picture that has emerged after years of research is much more
multifaceted than what Feynman weighed. Indeed, the large amounts of studies
of quantum properties, most notably entanglement, in quantum many-body systems
have fostered and given an impulse towards relevant progress in their
simulation. It is now well-known that states defined in one-dimensional
systems obeying area law [11, 12] can be efficiently represented and
manipulated using matrix-product states (MPS) techniques [13, 14], tensor-
networks [15, 16], entanglement renormalization schemes [17] and other
computational procedures. Hence, the complexity of quantum simulations does
not affect all quantum states and does not arise from entanglement alone.
Certain classes of states can be, at the same time, highly entangled and
efficiently simulated on a classical computer.

This is the case for stabilizer states [18], namely those states that can be
obtained from the computational basis using Pauli operations and their
centralizer, the so-called Clifford resources [19, 20]. Clifford resources are
very efficient in entangling [21, 22] but do not provide any quantum supremacy
[1, 23, 24, 25]. Since they can be efficiently represented (i.e. with a cost
that increases only polynomially with the size of the system) on a classical
computer, there is no information processing that a quantum computer could do
by Clifford resources that would not be efficiently performed by a classical
computer. On the other hand, as soon as such circuits get doped with non-
Clifford resources, their entanglement pattern becomes more complex, driving a
transition to universality and quantum chaos [26, 27, 28, 29].

In the context of quantum many-body systems, the study of non-stabilizerness
has been neglected, probably because of the hardness of computing the existing
measures for this resource, which has been dubbed magic in the folklore [30,
31, 32, 33]. One notable exception is [34], arguing how non-stabilizerness is
typical where the authors show the usefulness of quantum many-body states with
non-Clifford resources for quantum computation. Lately, however, a new measure
of non-stabilizerness has been introduced [35] as the Stabilizer Rényi Entropy
(SRE), which can be computed efficiently for MPSs [36] but is also amenable to
experimental measurement [38, 37].

In Ref. [39], by exploiting the computability of the SRE, it was shown that
the ground state of an Ising spin chain in a transverse field, despite obeying
entanglement area law [11], does possess an extensive amount of non-
stabilizerness. In the gapped phases, the SRE can be resolved by local
quantities, i.e. its value can be well approximated as the sum of the SRE of
its parts. This picture fails at the quantum critical point, where the
correlation length diverges [40, 41], and the entanglement shows a logarithmic
violation of the area law. Here, the local approximation fails with a large
offset error (i.e. due to entanglement and magic getting a diverging
logarithmic correction [36] which cannot be captured by local measures.
Therefore, one has to consider very large blocks to get a reasonable
approximation of the exact result. It is worth reminding that at critical
points decimation schemes like the MPS encounter a hurdle, because of the
logarithmic divergence of entanglement. The resulting picture is of a quantum
complexity emerging from a delocalization of non-stabilizerness, i. e, the
impossibility of resolving SRE in terms of local quantities.

In this paper, we explore the delocalization of SRE in quantum many-body
systems, by considering a class of states – the $W$-states [42] – which are a
global superposition of a macroscopical number of factorized states. By
embedding these states as the ground states of a quantum spin chain and adding
additional interactions to dress these states with local correlation, we
achieve a detailed characterization of various contributions to their SRE.

Notice that, although the results presented in [39] are associated with a
particular model, the picture there obtained is expected to be quite general.
Indeed, these results agree with the ones expected for ground states obtained
by exploiting quasi-adiabatic continuation [43] from a classical point with a
finite degeneracy. In this context, a classical point is meant as a point in
the phase diagram where the Hamiltonian reduces to a sum of terms that
commutes with each other and the SRE of the symmetric mixture of all its
elements vanishes. The deformations of the Hamiltonian associated with the
quasi-adiabatic continuation, induce the growth of local quantum correlations,
which explains both the extensivity and the local nature of the SRE [44].

Furthermore, different local and non-local features of magic have already been
investigated in several frameworks, see Refs. [45, 47, 46].

In this work, we consider a different situation, where quantum many-body
systems admit classical points with ground state manifolds whose number of
elements scale with $L$. These states can be grouped into a finite number of
families, each of which admits a base made of states that can be obtained from
each other by spatial translations. To provide an example, this is the case of
the spin one-half chains with topological frustration, which boils down to the
frustrated Ising model at the classical point [48, 49, 50]. This last system
admits a ground state manifold whose basis is the set of single kink states,
i.e. states with perfect Néel order except for a ferromagnetic defect (with
two parallely aligned neighboring spins) which constitute a domain wall
switching between Néel orders. The $2L$ kink states can be arranged in 2
different families of states (with different parities for the magnetization),
in which each element can be obtained from the others by spatial translations
(i.e., by shifting the kink).

Moving away from the classical point, generally the extensive degeneracy gets
lifted and, depending on the symmetry of the term competing with the Ising
one, the ground state can be represented by a symmetric coherent superposition
of the kink states. This happens, among other cases, when the competing term
commutes with the parity of the magnetization along a direction orthogonal to
that of the Ising interaction [51, 52, 53]. The symmetric linear superposition
of the kink states can be connected, through a Clifford circuit, with the
$W$-states, whose SRE will be shown to grow logarithmically in $L$. This non-
vanishing SRE of the $W$-states cannot be resolved in terms of local
quantities, since it comes from the delocalized nature of the linear
superposition. Therefore, in proximity of the classical point, we expect an
SRE that, instead of vanishing as in [39], depends logarithmically on $L$,
thus signaling that they belong to a different and inequivalent class of
states, compared to the usual case. Moving further away from the classical
point, a finite correlation length is developed which adds to this logarithmic
growth part and an extensive correction, similar in nature to the one
discussed above. In fact, in the case of topologically frustrated systems,
this second term can be traced back to the SRE of the corresponding
unfrustrated system.

The manuscript is organized as follows. First, in Sect. I we introduce the
$W$-states, and we evaluate analytically their SRE and its dependence on the
system size. Next, in Sect. II we show how the SRE of the $W$-states is
related to the symmetric linear superposition of magnetic defects (kinks)
states which, in the proximity of a classical point, well-describes the ground
state of a family of topologically frustrated one-dimensional spin-$1/2$
models. Next, in Sect. III we analyze in detail some examples of topologically
frustrated integrable models, and we underline differences and analogies with
the unfrustrated counterparts. Finally, in Sect. IV we draw our conclusion.

##  I W-states

Let us start by recalling that, to quantify the amount of non-stabilizerness
for a generic state defined on a one-dimensional system made of $L$ qubits, it
is possible to use the Stabilizer $2$-Rényi Entropy (SRE) [35] that is defined
as

$\mathcal{M}_{2}(\ket{\psi})=-\log_{2}{\left(\frac{1}{2^{L}}\sum_{P}\bra{\psi}P\ket{\psi}^{4}\right)},$
(1)

where the sum on the right-hand side runs over all possible Pauli strings
$P=\bigotimes_{j=1}^{L}P_{j}$ for
$P_{j}\in\\{\sigma^{0}_{j},\sigma_{k}^{x},\sigma_{j}^{y},\sigma_{j}^{z}\\}$
where $\sigma_{j}^{0}$ stands for the identity operator on the $j$-th qubit.

Let us now consider a set of $L$ states $\\{\ket{\psi_{j}}\\}$ in which each
element is a computational basis state and, defining $T$ the translation
operator, we have $\ket{\psi_{j+1}}=T\ket{\psi_{j}}$. Since any
$\ket{\psi_{j}}$ is fully separable, and hence can be written as a tensor
product of states defined on each single qubit, it results to be equivalent to
a classical state and its SRE vanishes identically111In fact, a factorized
state is an eigenstate of $2^{N}$ Pauli strings in which each element of the
string is either the identity or a Pauli matrix. Thus its SRE vanishes..
However, if instead of considering only one of the elements of the set, we
take into account the translational invariant linear combination of all of
them, i.e. the state $\ket{\chi}=L^{-1/2}\sum_{j}\ket{\psi_{j}}$ we obtain an
SRE different from zero. To evaluate the SRE of $\ket{\chi}$, let us observe
that regardless of the particular expression of $\ket{\psi_{j}}$, since it is
an eigenstate of a Pauli string, it is always possible, by exploiting only
local rotations, to map it into the state
$\ket{j}=\sigma^{z}_{j}\ket{-}^{\otimes L}$ where $\ket{\pm}$ stand for the
eigenstates of $\sigma^{x}$ with eigenvalues $\pm 1$. Hence, the symmetric
superpositions $\ket{\chi}$ are equivalent to the well-known $W$-states [42]
defined as

$\ket{W}=\frac{1}{\sqrt{L}}\sum_{j=1}^{L}\sigma^{z}_{j}\ket{-}^{\otimes L}.$
(2)

The $W$-states play a key role in the theory of quantum information since it
maximizes the multipartite entanglement [42] while retaining the maximum
amount of bipartite entanglement after local measurement on one of its part
[54]. As such, they are considered good candidates for realizing quantum
memories [55].

From the expression of $\ket{W}$ in (2) it is possible to evaluate
analytically the value of $\mathcal{M}_{2}(\ket{W})$ which turns out to be
equal to

$\mathcal{M}_{2}(\ket{W})=3\log_{2}(L)-\log_{2}(7L-6),$ (3)

(see Apprendix A for a detailed proof).

The result in (3) shows that there is a whole class of states, that is the
$W$-states and all other states that can be obtained from it with the help of
a stabilizer circuit, whose SRE displays a logarithmic dependence on the
system size. This class is different from the one obtained by using Clifford
circuits on a fully separable state, a class to which also the GHZ states [56]
belongs and which is characterized by a zero non-stabilizerness.

##  II Non-stabilizerness close to a classical point

Let us now turn back to consider a quantum many-body problem. If one of the
states of the set $\\{\ket{\psi_{j}}\\}$ is a ground state of an invariant
under spatial translation Hamiltonian at its classical point, then all the
elements of the set, as well as all the possible linear combinations of them,
are also ground states of the Hamiltonian. This implies that the Hamiltonian
holds, at its classical point, an extensive degeneracy. An example of a
situation like the one described can be found, for instance, in classical
(non-disordered) frustrated systems [57, 58, 59, 60].

By turning on a quantum (competing) interaction, in general the massive
degeneracy is, at least partially, lifted. In agreement with perturbation
theory, the ground state can be well approximated by a linear combination of
the elements in the set $\\{\ket{\psi_{j}}\\}$. It is not possible to make a
general statement about the particular linear combination that minimizes the
energy, since it strongly depends on both the expression of the classical
Hamiltonian and on the nature of the perturbation. To have a taste of the
richness of this phenomenology, see Ref. [61] for the case of one-dimensional
topologically frustrated models. Therefore, we are forced to choose a
particular family of models.

From now on, we focus on the translationally invariant one-dimensional model
whose Hamiltonian can be written in the form

$H=J\sum\limits_{j=1}^{L}\sigma_{j}^{x}\sigma_{j+1}^{x}-\lambda\sum\limits_{j=1}^{L}O_{j}.$
(4)

The parameter $\lambda$ allows for tuning the relative weight of the two
terms. At $\lambda=0$ (classical point), the Hamiltonian boils down to a
simple 1D Ising model that, in the presence of topological frustration, shows
the extensive degeneracy in the ground state manifold that we are looking for.
In a translationally invariant 1D system, topological frustration is induced
by choosing antiferromagnetic interactions $(J=1)$ and by enforcing the so-
called frustrated boundary conditions (FBC) that are imposed by setting: 1)
periodic boundary conditions ($\sigma^{\alpha}_{j}=\sigma^{\alpha}_{j+n}\
\forall\,j,\,\alpha$); 2) odd number of sites ($L=2M+1$ for any strictly
positive integer $M$).

The family of Hamiltonians in (4) features a second term in competition with
the Ising one which preserves translational invariance, but must violate
parity symmetry for the magnetization along the $x$-direction, namely the
direction of the Ising interaction. Moreover, to exploit the methods presented
in Ref. [39], we also require the resulting model to be mappable to a free
fermionic one, by making use of the Jordan-Wigner transformation [41]. This
family of Hamiltonians is extremely wide and includes, among others, the
transverse field Ising model (TFIM), obtained by setting
$O_{j}=\sigma^{z}_{j}$ and the Cluster-Ising model (CIM), which is recovered
for $O_{j}=\sigma^{x}_{j-1}\sigma^{z}_{j}\sigma^{x}_{j+1}$.

At the classical point $\lambda=0$, the Hamiltonian in (4) admits a ground
state manifold with a degeneracy equal to $2L$, as an effect of the Kramers’
degeneracy theorem. This manifold is described by a basis made of the union of
two extensive sets of states, which are
$\\{\ket{k}=T^{k-1}\bigotimes_{j=1}^{M}\sigma_{2j}^{z}\ket{-}^{\otimes L}\\}$
and
$\\{\ket{k^{\prime}}=T^{k-1}\bigotimes_{j=1}^{M}\sigma_{2j}^{z}\ket{+}^{\otimes
L}\\}$ for all $k$ and $k^{\prime}$ running from $1$ to $L=2M+1$ where
$\ket{\pm}$ are the eigenstates of $\sigma^{x}$ with eigenvalues $\pm 1$. The
elements of these two sets of states are known as kink states or domain-wall
states and are Néel’s states with a localized magnetic defect (two neighboring
spins parallelly oriented which interpolate between the two Néel orders) [61].

Depending on the choice of $O_{j}$, a finite $\lambda$ reduces the extensive
ground state degeneracy of the classical point to a finite odd number [51, 52,
53]. We have that, the degeneracy is equal to 1 regardless of $L$ for the
topologically frustrated TFIM while in the case of the CIM is equal to 1 (3)
if and only if $L$ is odd and is not (is) an integer multiple of 3. However,
independently of the degree of the ground state degeneracy, as the lowest
energy state we always find the symmetric superposition of kink states with
zero momentum that we can write as

$\ket{W_{k}}=\frac{1}{\sqrt{2L}}\sum_{k=1}^{L}(\ket{k}+\ket{k^{\prime}}).$ (5)

The $\ket{W_{k}}$ looks similar to $\ket{W}$ and can be obtained from it using
a simple stabilizer circuit. This means that we can write
$\ket{W_{k}}=\hat{\mathcal{S}}\ket{W}$ where $\hat{\mathcal{S}}$ is the
stabilizer circuit

$\\!\hat{\mathcal{S}}\\!=\\!\prod_{j=1}^{L-1}\\!\text{C}(L,L\\!-\\!j)\\!\\!\left(\prod_{j=1}^{M}\sigma^{z}_{2j-1}\\!\right)\\!\\!\text{H}(L)\sigma^{z}_{L}\prod_{j=1}^{L-1}\\!\\!\text{C}(j,j\\!+\\!1)\Pi^{z}.$
(6)

In (6) $\text{H}(j)=\frac{1}{\sqrt{2}}(\sigma^{x}_{j}+\sigma^{z}_{j})$ stands
for the Hadamard gate on the $j$-th qubit,
$\text{C}(j,l)=\exp\left[\frac{\pi}{4}(1-\sigma^{x}_{j})(1-\sigma^{z}_{l})\right]$
is the CNOT gate on the $l$-th qubit controlled by the value of the $j$-th one
and $\Pi^{z}=\bigotimes_{j=1}^{L}\sigma^{z}_{j}$ is the parity operator along
z. This circuit is depicted in Fig. 1 in the case of $L=5$. Since
$\mathcal{M}_{2}$ is invariant under stabilizer Clifford circuits, we have
$\mathcal{M}_{2}(\ket{W_{\text{K}}})=\mathcal{M}_{2}(\ket{W})$. Thus, for
systems that satisfy our hypothesis, in the proximity of the classical point,
the SRE does not vanish but scales logarithmically as in eq. (3).

Figure 1: Pictorial representation of the Clifford circuit $\hat{\mathcal{S}}$
in (6) for $L=5$. The H and Z boxes stand respectively for the Hadamard gate
and the $\sigma^{z}$ operator on the chosen qubit. The CNOT gates involve two
qubits and are represented by a line connecting a black dot, indicating the
qubit that acts as the controller, and a colored circle signaling the one that
can be flipped.

##  III Analysis of some Topologically frustrated models

Moving further away from the classical point with extensive degeneracy, the
perturbative approximation we used in the previous section ceases to be valid.
We must therefore determine the exact expression for the ground state, and
from it determine the value of the SRE. This procedure cannot be performed
with general arguments such as those used up to now, and the problem must be
analyzed case by case. In this paper, we will focus on two different models,
namely the topologically frustrated TFIM and the CIM, whose ground states have
been analyzed in previous works [51, 53] exploiting the Jordan-Wigner
transformations that allow mapping both spin chains in two different free-
fermionic systems. The results obtained are then compared with the
unfrustrated version of such models, which are recovered by tuning the value
of $J$ from 1 to $-1$ [51, 62, 63, 64, 65].

Figure 2: Comparison between the SRE for the unfrustrated (obtained setting
$J=-1$) and the topologically frustrated (obtained setting $J=1$) TFIM (left
column) and CIM (right column) for different values of $\lambda$ as a function
of the length of the system $L$. The different values of $\lambda$ are in the
legends.  Figure 3: Behavior of the function $\mathcal{R}(L,\lambda)$ in eq.
(8) as function of $L$ for different models and values of $\lambda$. In the
upper panel, we report the data obtained for the TFIM, while in the lower one
we show the results for the CIM. The different values of $\lambda$ are in the
legends.

In Fig. 2, we evaluate the SRE as a function of $L$ for the ground states of
the topologically frustrated TFIM (left column) and CIM (right column) for
several values of $\lambda$, and compare it with the corresponding results
obtained for the unfrustrated counterpart [40, 41]. In perfect agreement with
the results obtained in [39] for the TFIM, regardless of the value of
$\lambda$, the SRE for the unfrustrated models (upper row in Fig. 2) always
displays a linear dependence on $L$. Instead, the picture for the frustrated
models is much richer. The linear dependence on $L$ is preserved for both the
quantum phase transition $\lambda=1$, and for the gapped phase $\lambda>1$. On
the contrary, for $\lambda<1$ we see a clear absence of linear dependence on
$L$.

While it is easy to extrapolate the behavior of the SRE for systems with large
$L$, thanks to the linear trend visible even at small sizes, for the
frustrated models the situation is much more complex. Analyzing our data, we
recover that, at least in the limit of large $L$, the SRE in the topologically
frustrated phases can be seen as the sum of a local term equal to the one of
the corresponding unfrustrated model, and a second contribution coming from
the delocalized $\ket{W_{k}}$ state. This means that, at least for large $L$,
we expect that

$\mathcal{M}_{2}(J=1,L,\lambda)=\mathcal{M}_{2}(J=-1,L,\lambda)+\mathcal{M}_{2}^{W}(L),$
(7)

where $\mathcal{M}_{2}(J=1,L,\lambda)$ ($\mathcal{M}_{2}(J=-1,L,\lambda)$) is
the SRE for the frustrated (unfrustrated) model with length $L$ and parameter
$\lambda$ and $\mathcal{M}_{2}^{W}(L)$ is given in (3).

To test this picture, in Fig. 3 we plot the difference between the SRE for the
frustrated and the unfrustrated models, for fixed values of $\lambda$ and $L$,
normalized with $\mathcal{M}_{2}^{W}(L)$, i.e. the quantity

$\mathcal{R}(L,\lambda)=\frac{\mathcal{M}_{2}(J=1,L,\lambda)-\mathcal{M}_{2}(J=-1,L,\lambda)}{\mathcal{M}_{2}^{W}(L)}.$
(8)

In both models considered, the results shown in the graph are consistent with
the expression in (7). In fact, for $\lambda<1$ we have that the system is in
the frustrated phase and the quantity $\mathcal{R}(L,\lambda)$ tends
asymptotically to 1 for large chains, while it goes to zero in all other
cases. It is worth noting that the values of the ratio are not exactly $1$ or
$0$ but tend to these thresholds only for large $L$. Indeed, in the
thermodynamic limit quantities defined on finite supports converge to the same
value for a frustrated system and its unfrustrated counterpart, but when the
size is finite there are corrections scaling like $1/L$ [51]. We stress that
these corrections cannot explain the logarithmic dependence of the SRE on the
size of the chain, since it provides only a size-independent correction to the
extensive SRE of the frustrated model. Nevertheless, it allows quantifying the
finite size effects on $\mathcal{R}(L,\lambda)$.

In fact, in Ref. [39] the authors proved the local nature of the SRE for the
unfrustrated Ising model by showing how its behavior is well mimicked by the
SRE of the reduced density matrix of a single spin. In other words, labeled
$\alpha_{1}(\lambda)$ the SRE of the reduced density matrix of a single qubit

$\alpha_{1}(\lambda)=\log_{2}{\left(\frac{1+m_{z}^{2}}{1+m_{z}^{4}}\right)},$
(9)

where $m_{z}=\langle\sigma^{z}_{j}\rangle$ is the local magnetization obtained
by averaging $\sigma^{z}_{j}$ over the ground state of the unfrustrated model
(which is translationally invariant). Correspondingly, in Ref. [39] it was
shown that away from criticality we have $\mathcal{M}_{2}(J=-1,L,\lambda\neq
1)\simeq L\alpha_{1}(\lambda)$. In the frustrated case, the expectation value
of $\sigma^{z}_{j}$ acquires a correction proportional to $L^{-1}$
$(\langle\sigma^{z}_{j}\rangle=m_{z}+2/L)$, which, when plugged into (9),
gives

$\\!\\!\\!\\!\\!\mathcal{M}_{2}(\\!J\\!=\\!1\\!,L,\lambda\\!\neq\\!1){\simeq}L\alpha_{1}(\lambda)\\!+\\!4m_{z}\\!\left(\\!\dfrac{1}{1+m_{z}^{2}}\\!-\\!\dfrac{2m_{z}^{2}}{1+m_{z}^{4}}\\!\right).$
(10)

We see that even accounting for the correction, a local approximation for the
SRE fails to reproduce the non-local logarithmic growth coming from the
$W$-states. This feature can also be connected to MPS representations. States
that can be represented as translational invariant MPSs, such as the ground
state of the unfrustrated Ising model, have extensive SRE [36]. In contrast,
the $W$-state has no efficient representation as a translational invariant MPS
[66], thus a violation of the extensive property of SRE is possible.

Furthermore, we note that (10) is not valid for the CIM since $m_{z}=0$. This
fact implies that in order to mimic the SRE for the unfrustrated model, we
cannot limit the reduced density matrix of a single spin, but we have to take
larger partitions, where we can recover similar behaviors.

##  IV Conclusions

In conclusion, in our work, we have considered a well-known family of states
in the field of quantum information, namely the $W$-states. For this family,
we have calculated the value of the SRE, and we have highlighted the
logarithmic dependence of the latter on the size of the system. This non-zero
SRE does not come from the individual states whose combination gives life to
the $W$-states, but from the particular, non-local, superposition of them,
which produces a completely delocalized SRE. In fact, the $W$-states are
written in terms of states that are eigenstates of Pauli strings and
therefore, taken individually, they have a null non-stabilization value.

We have shown how these states are realized naturally in a quantum spin chain
close to its classical point, when the system is topologically frustrated. The
quantum term competing with the Ising interaction, but preserving the parity
of the magnetization in a transverse direction selects a superposition of
factorizable kink states which, through a Clifford circuit, can be exactly
mapped into the $W$-states. Since any measure of non-stabilization remains
unaffected by the application of a Clifford circuit, the ground state of the
(nearly classical) spin chain and the $W$-state share the same, non-vanishing
SRE which grows logarithmically with the number of qubits/spins. This behavior
should be contrasted to that of non-frustrated systems, which close to their
classical point approach GHZ-state and have zero SRE.

Moving away from the classic point, the competition between the quantum
interactions gives rise to an additional contribution that scales linearly
with $L$ in a way that is analogous to that of the unfrustrated counterparts.
Therefore, in a topologically frustrated system the SRE is the result of the
coexistence of a dominant local contribution and a subdominant one originating
from the delocalized nature of the $W$-states.

This work combines quantities and concepts from two different fields: quantum
computing and the theory of complex quantum systems and provides new insights
for both. From the many-body point of view, it offers further evidence on the
difference between the same model with and without topological frustration and
shows that the former has a much richer (non-local) complexity.

From quantum information theory perspective, the results presented in this
paper provide a new embedding of $W$-states in a physically realizable setting
and a generalization of these states to a finite correlation length.
Furthermore, the additional SRE of the frustrated systems, particularly
relevant for microscopic and mesoscopic systems, can be a valuable resource
for the design of devices based on topological frustrated models. To provide
an example, let us consider fault-tolerant quantum computations that are
commonly run by state synthesis protocols, where a resource state
$\ket{\phi}_{\text{ini}}$ combined with error-corrected Clifford operations is
transformed into a target state $\ket{\phi}_{\text{target}}$ [67]. Magic (SRE)
quantifies the non-stabilizer resources needed to synthesize a particular
state or unitary [31, 69, 68]. As the SRE is invariant under Clifford
unitaries, a necessary condition for state synthesis is that
$\mathcal{M}_{2}(\ket{\phi}_{\text{target}})\leq\mathcal{M}_{2}(\ket{\phi}_{\text{ini}})$.
Thus, it bounds the minimum amount of magic resource states needed to simulate
a state on a quantum computer.

For example, the commonly used magic state $\ket{T}$ defined as
$\ket{T}=\frac{1}{\sqrt{2}}(\ket{0}+e^{-i\pi/4}\ket{1})$, which can be used to
realize a single T-gate, has a magic equal to
$\mathcal{M}_{2}(\ket{T})=\log_{2}(4/3)$. But, even if we consider $L=3$,
which represents the minimum size for which we can distinguish among $W$ and
GHZ states, the SRE of a $W$-state is larger by $\log_{2}(4/3)$. Hence, a
single three qubit $W$-state, and therefore any topological frustrated one-
dimensional system, could provide an amount of non-stabilizer resources
sufficient for the realization of a T-gate.

###### Acknowledgements.

JO recognizes the support of the Croatian Science Foundation under grant
number HRZZ-UIP-2020-02-4559 and the European Regional Development Fund under
the grant KK.01.1.1.01.009 - DATACROSS. TH thanks L. Piroli for discussions,
AH acknowledges support from NSF award number 2014000. SMG, FF, and GT
acknowledge support from the QuantiXLie Center of Excellence, a project co-
financed by the Croatian Government and the European Union through the
European Regional Development Fund – the Competitiveness and Cohesion (Grant
KK.01.1.1.01.0004). FF and SMG also acknowledge support from the Croatian
Science Foundation (HrZZ) Projects No. IP–2019–4–3321.

##  Appendix A Analytic derivations of SRE

In this Appendix, we detail the analytical derivations of the SRE for a $W$
state. Let us start by recalling the definition of the $W$ state in the
$x$-basis (see (2)) as

$\ket{W}=\frac{1}{\sqrt{L}}\sum_{i=1}^{L}\sigma^{z}_{i}\ket{-}^{\otimes L}.$
(11)

Denoting with $P$ a generic Pauli string operator defined on the system of $L$
qubit, to determine the SRE given in (1), we have to evaluate the expectation
value of the $W$ state over $P$, i.e.

$\bra{W}P\ket{W}=\frac{1}{L}\sum_{i,j=1}^{L}\bra{-}^{\otimes
L}\sigma_{j}^{z}P\sigma_{i}^{z}\ket{-}^{\otimes L}.$ (12)

Let us consider separately the two different cases, $i=j$ and $i\neq j$, that
will provide two different kind of contribution to the SRE, i.e.

$\mathcal{M}_{2}^{W}(L)\equiv\mathcal{M}_{2}(\ket{W})=-\log_{2}\left[\frac{1}{2^{L}}\left(O_{i=j}+O_{i\neq
j}\right)\right].$ (13)

When $i=j$, we have that only the string in which there is no $\sigma_{k}^{y}$
either $\sigma_{k}^{z}$ give a non-zero expectation value. Hence, the non-
vanishing contribution will arrive only by $2^{L}$ strings that can be put in
the form $P^{\prime}=\bigotimes_{k=1}^{L}\sigma_{k}^{\alpha}$, where
$\alpha\in\\{0,x\\}$. The absolute value of each term defined in eq. (12)
depends on the number of $\sigma_{k}^{x}$ operators in the string
$P^{\prime}$. In fact, due to the fact that $\ket{-}$ is eigenstate of
$\sigma^{x}_{k}$ with eigenvalues $-1$ they provide a negative contribution
while the $\sigma_{k}^{0}$ provide a positive ones. Therefore, the absolute
value of the expectation value of $P^{\prime}$ is $\|\frac{L-2l}{L}\|$, where
$l=0,\ldots,L$ stands for the number of $\sigma^{x}_{k}$. Taking into account
all the possible combinations, the contributions of these terms is

$O_{i=j}=\sum_{l=0}^{L}\left(\frac{L-2l}{L}\right)^{4}\frac{L!}{l!(L-l)!}.$
(14)

On the other hand, when $i\neq j$ only string operators of the form
$P^{\prime\prime}=\bigotimes_{k=1,k\neq
i,j}^{L}\sigma_{k}^{\alpha}\otimes(\sigma^{\beta}_{i}\sigma^{\beta}_{j})$ with
$\alpha=0,x$ and $\beta=y,z$ has a non-vanishing contribution with absolute
value equal to $\frac{2}{L}$. From this, it is easy to write down

$O_{i\neq
j}\\!=\\!\sum_{l=0}^{L-2}2\left(\frac{2}{L}\right)^{4}\frac{L(L-1)}{2}\frac{(L-2)!}{l!(L-2-l)!}.$
(15)

Introducing both (14) and (15) in (13), and after a few simplifications we
obtain

$\displaystyle\mathcal{M}_{2}^{W}(L)=3\log_{2}(L)-\log_{2}(7L-6).$ (16)

## References

  * [1] R. P Feynman, "Simulating physics with computers", International Journal of Theoretical Physics, 21, 467 (1982).
  * [2] S. Sachdev, "Quantum Phase Transitions", Cambridge University Press (2000).
  * [3] X.-G. Wen, "Topological Orders in Rigid States", International Journal of Modern Physics B 4, 239 (1990).
  * [4] X.-G. Wen, and Q. Niu, "Ground state degeneracy of the FQH states in presence of random potential and on high genus Riemann surfaces", Physical Review B 41, 9377 (1990).
  * [5] X. Chen, Z.-C. Gu, and X.-G. Wen, "Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order" Physical Review B 82, 155138 (2010).
  * [6] T. Senthil, S. Sachdev, and M. Vojta, "Fractionalized Fermi Liquids", Physical Review Letters 90, 216403 (2003).
  * [7] T. Senthil, M. Vojta, and S. Sachdev, "Weak magnetism and non-Fermi liquids near heavy-fermion critical points", Physical Review B 69, 035111 (2004).
  * [8] D. Jaksch, C. Bruder, J. I. Cirac, C. W. Gardiner, and P. Zoller, "Cold bosonic atoms in optical lattices", Physical Review Letters 81, 3108 (1998).
  * [9] M. Greiner, O. Mandel, T. Esslinger, T. W. Hänsch, and I. Bloch, "Quantum phase transition from a superfluid to a Mott insulator in a gas of ultracold atoms", Nature 415, 39 (2002)
  * [10] I. Bloch, J. Dalibard, and W. Zwerger, "Many-body physics with ultracold gases", Review of Modern Physics 80, 885 (2008)
  * [11] G. Vidal, J. I. Latorre, E. Rico, and A. Kitaev, "Entanglement in Quantum Critical Phenomena", Physical Review Letters 90, 227902 (2003)
  * [12] J. Eisert, M. Cramer, and M. B. Plenio, "Colloquium: Area laws for the entanglement entropy", Review of Modern Physics 82, 277 (2010)
  * [13] D. Perez-Garcia, F. Verstraete, and M. M. Wolf, "Matrix product state representations", Quantum Information and Computation 7, 401 (2008).
  * [14] F. Verstraete, V. Murg, and J. I. Cirac, "Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems", Advances in Physics 57, 143 (2008).
  * [15] F. Verstraete, M. M. Wolf, D. Perez-Garcia, and J. I. Cirac, "Criticality, the Area Law, and the Computational Power of Projected Entangled Pair States". Physical Review Letters 96, 220601 (2006).
  * [16] O. Román, "Tensor networks for complex quantum systems". Nature Reviews Physics 1, 538 (2019)
  * [17] G. Vidal, "Entanglement Renormalization", Physical Review Letters 99, 220405 (2007)
  * [18] D. P. DiVincenzo, D. W. Leung, and B. M. Terhal, "Quantum Data Hiding", IEEE Transactions on Information Theory 48, 580 (2002)
  * [19] D. Gottesman, "Theory of fault-tolerant quantum computation" Physical Review A 57, 127 (1998)
  * [20] V. Veitch, S. A. Hamed Mousavian, D. Gottesman, and J. Emerson," The resource theory of stabilizer quantum computation", New Journal of Physics 16, 013009 (2014)
  * [21] G. Smith, and D. W. Leung, "Typical entanglement of stabilizer states" Physical Review A 74, 062314 (2006)
  * [22] J. Gütschow, "Entanglement generation of Clifford quantum cellular automata", Applied Physics B 98, 623 (2010)
  * [23] J. Preskill, "Quantum computing and the entanglement frontier - Rapporteur talk at the 25th Solvay Conference on Physics ("The Theory of the Quantum World"), 19-22 October 2011", arXiv:1203.5813
  * [24] A, W. Harrow, and A. Montanaro, "Quantum computational supremacy", Nature 549, 203 (2017)
  * [25] A. Nahum, J. Ruhman, S. Vijay, and J. Haah, "Quantum Entanglement Growth under Random Unitary Dynamics" Physical Review X 7, 031016 (2017)
  * [26] D. Shaffer, C. Chamon, A. Hamma, and E. R. Mucciolo Irreversibility and entanglement spectrum statistics in quantum circuits, Journal of Statistical Mechanics: Theory and Experiment 2014, P12007 (2014)
  * [27] C. Chamon, A. Hamma, and E. R. Mucciolo, "Emergent irreversibility and entanglement spectrum statistics", Physical Review Letters 112, 240501 (2014),
  * [28] S. Zhou, Z. Yang, A. Hamma, and C. Chamon, "Single T gate in a Clifford circuit drives transition to universal entanglement spectrum statistics", SciPost Phys. 9, 87 (2020)
  * [29] S. True1 and A. Hamma, "Transitions in Entanglement Complexity in Random Circuits", arXiv:2202.02648 (2022)
  * [30] M. Howard, J. Wallman, V. Veitch, and J. Emerson, "Contextuality supplies the ‘magic’ for quantum computation", Nature 510, 351 (2014)
  * [31] S. Bravyi, G. Smith, and J. A. Smolin, "Trading Classical and Quantum Computational Resources" Physical Review X 6, 021043 (2016)
  * [32] S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, "Simulation of quantum circuits by low-rank stabilizer decompositions", Quantum 3, 181 (2019).
  * [33] J. R. Seddon, B. Regula, H. Pashayan, Y. Ouyang, and E. T. Campbell, "Quantifying Quantum Speedups: Improved Classical Simulation From Tighter Magic Monotones", Physical Review X Quantum 2, 010345 (2021)
  * [34] Z.-W. Liu, and A. Winter, "Many-Body Quantum Magic", Physical Review X Quantum 3, 020333 (2022)
  * [35] L. Leone, S. F. E. Oliviero, and A. Hamma, "Stabilizer Rényi Entropy", Physical Review Letters 128, 050402 (2022)
  * [36] T. Haug, and L. Piroli, "Quantifying Nonstabilizerness of Matrix Product States", arXiv:2207.13076 (2022)
  * [37] T. Haug, M. S. Kim, "Scalable measures of magic for quantum computers", arXiv:2204.10061 (2022).
  * [38] S. F. E. Oliviero, L. Leone, A. Hamma, and S. Lloyd, "Measuring magic on a quantum processor", arXiv:2204.00015 (2022).
  * [39] S. F. E. Oliviero, L. Leone, and A. Hamma, "Magic of the ground state of the transverse field Ising model", arXiv:2205.02247 (2022).
  * [40] E. Barouch, and B. McCoy, "Statistical Mechanics of the XY Model. II. Spin-Correlation Functions", Physical Review A 3, 786 (1971).
  * [41] F. Franchini, An introduction to integrable techniques for one-dimensional quantum systems, Lecture Notes in Physics 940, Springer (2017).
  * [42] W. Dür, G. Vidal, and J. I. Cirac, "Three qubits can be entangled in two inequivalent ways", Physical Review A 62, 062314 (2000)
  * [43] M. B. Hastings, and X.-G. Wen, "Quasiadiabatic continuation of quantum states: The stability of topological ground-state degeneracy and emergent gauge invariance", Physical Review B 72, 045141 (2005)
  * [44] A. Hamma, S. M. Giampaolo, and F. Illuminati, "Mutual information and spontaneous symmetry breaking", Physical Review A 93, 0123030 (2016)
  * [45] S. Sarkar, C. Mukhopadhyay, and A. Bayat, "Characterization of an operational quantum resource in a critical many-body system", New Journal of Physics 22, 083077 (2020)
  * [46] T. J. Sewell, and C. D. White, "Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation", arXiv:2201.12367 (2022)
  * [47] C. D. White, C. Cao, and B. Swingle, "Conformal field theories are magical", Physical Review B 103, 075145 (2021)
  * [48] V. Marić, S. M. Giampaolo, and F. Franchini, "Quantum Phase Transition induced by topological frustration", Communications Physics 3, 220 (2020).
  * [49] V. Marić, S. M. Giampaolo, and F. Franchini, "The Frustration of being Odd: How Boundary Conditions can destroy Local Order", New Journal of Physics 22, 083024 (2020).
  * [50] V. Marić, G. Torre, F. Franchini, and S. M. Giampaolo "Topological Frustration can modify the nature of a Quantum Phase Transition", SciPost Physics 12, 075 (2022).
  * [51] J.-J. Dong, P. Li, and Q.-H. Chen, "The a-cycle problem for transverse Ising ring", Journal of Statistical Mechanics: Theory and Experiment 2016, 113102 (2016)
  * [52] S. M. Giampaolo, F. B. Ramos, and F. Franchini, "The frustration of being odd: universal area law violation in local systems", Journal of Physics Communications 3 081001 (2019)
  * [53] V. Marić, F. Franchini, D. Kuić, and S. M. Giampaolo, "Resilience of the topological phases to frustration", Scientific Reports 11, 6508 (2021)
  * [54] V. Coffman, J. Kundu, and W. K. Wootters, "Distributed entanglement", Physical Review A 61, 052306 (2000)
  * [55] M. Fleischhauer, and M. D. Lukin, "Quantum memory for photons: Dark-state polaritons", Physical Review A 65, 022314 (2002).
  * [56] D. M. Greenberger, M. A. Horne, and A. Zeilinger, "Going Beyond Bell’s Theorem"in: ’Bell’s Theorem, Quantum Theory, and Conceptions of the Universe’, M. Kafatos (Ed.), Kluwer, Dordrecht, 69-72 (1989)
  * [57] G. Toulouse, "Theory of the frustration effect in spin glasses: I", Communications on Physics 2, 115 (1977).
  * [58] J. Vannimenus, and G. Toulouse, "Theory of the frustration effect. II. Ising spins on a square lattice", Journal of Physics C: Solid State Physics 10, L537 (1977).
  * [59] M. J. Harris, S. T. Bramwell, D. F. McMorrow, T. Zeiske, and K. W. Godfrey, "Geometrical frustration in the ferromagnetic pyrochlore $\mathrm{Ho_{2}Ti_{2}O_{7}}$, Physical Review Letters 79, 2554 (1997).
  * [60] A. P. Ramirez, A. Hayashi, R. J. Cava, R. Siddharthan, and B. S. Shastry, "Zero-point entropy in ’spin ice’", Nature 399, 333 (1999).
  * [61] V. Marić, S. M. Giampaolo, and F. Franchini. "Fate of local order in topologically frustrated spin chains" Physical Review B 105, 064408 (2022).
  * [62] P. Smacchia, L. Amico, P. Facchi, R. Fazio, G. Florio, S. Pascazio, and V. Vedral, Statistical mechanics of the cluster Ising model, Phys. Rev. A 84, 022304 (2011)
  * [63] S. M. Giampaolo, and B. C. Hiesmayr, "Genuine multipartite entanglement in the cluster-Ising model", New Journal of Physics 16, 093033 (2014)
  * [64] S. M. Giampaolo, and B. C. Hiesmayr, "Topological and nematic ordered phases in many-body cluster-Ising models", Physical Review A 92, 012306
  * [65] G. Zonzo, and S. M. Giampaolo. "n-cluster models in a transverse magnetic field", Journal of Statistical Mechanics: Theory and Experiment 2018, 063103 (2018).
  * [66] D. Perez-Garcia, F. Verstraete, M. M. Wolf, and, J. I. Cirac, "Matrix product state representations" Quantum Information & Computation 7, 401 (2007).
  * [67] E. T. Campbell, B. M. Terhal, and C. Vuillot, "Roads towards fault-tolerant universal quantum computation" Nature 549, 172 (2017).
  * [68] M. Beverland, E. Campbell, M. Howard, and V. Kliuchnikov, "Lower bounds on the non-Clifford resources for quantum computations" Quantum Science and Technology 5, 035009 (2020).
  * [69] M. Howard, and E. Campbell, "Application of a Resource Theory for Magic States to Fault-Tolerant Quantum Computing", Physical Review Letters 118, 090501 (2017).


# On Multicolour Ramsey Numbers and Subset-Colouring of Hypergraphs

Bruno Jartoux  Department of Computer Science, Ben-Gurion University of the
Negev, Be’er-Sheva, Israel<EMAIL_ADDRESS>Chaya Keller  Department of
Computer Science, Ariel University, Ariel, Israel<EMAIL_ADDRESS>Shakhar
Smorodinsky  Department of Mathematics, Ben-Gurion University of the Negev,
Be’er-Sheva, Israel<EMAIL_ADDRESS>Yelena Yuditsky  Département de
Mathématique, Université libre de Bruxelles, Brussels, Belgium
<EMAIL_ADDRESS>
###### Abstract

For $n\geq s>r\geq 1$ and $k\geq 2$, write $n\rightarrow(s)_{k}^{r}$ if every
hyperedge colouring with $k$ colours of the complete $r$-uniform hypergraph on
$n$ vertices has a monochromatic subset of size $s$. Improving upon previous
results by [1] and [9] we show that

$\text{if }r\geq 3\text{ and }n\nrightarrow(s)_{k}^{r}\text{ then
}2^{n}\nrightarrow(s+1)_{k+3}^{r+1}.$

This yields an improvement for some of the known lower bounds on multicolour
hypergraph Ramsey numbers.

Given a hypergraph $H=(V,E)$, we consider the Ramsey-like problem of colouring
all $r$-subsets of $V$ such that no hyperedge of size $\geq r+1$ is
monochromatic. We provide upper and lower bounds on the number of colours
necessary in terms of the chromatic number $\chi(H)$. In particular we show
that this number is $O(\log^{(r-1)}(r\chi(H))+r)$.

Bruno Jartoux: Research supported by the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation programme (Grant
agreement No. 678765) and by Grant 1065/20 from the Israel Science Foundation.
Chaya Keller: Research supported by Grant 1065/20 from the Israel Science
Foundation.
Shakhar Smorodinsky: Research supported by Grant 1065/20 from the Israel
Science Foundation.
Yelena Yuditsky: Research supported by Belgian National Fund for Scientific
Research (FNRS), through PDR grant BD-OCP.

##  1 Introduction

Even though Ramsey theory has attracted much attention from its inception
almost a century ago, many questions remain elusive. This paper is primarily
concerned with lower bounds for (multicolour, hypergraph) Ramsey numbers and
the methods that yield them.

#### Notations.

For any natural number $n\in\mathbf{N}$, put $\llbracket
n\rrbracket=\\{0,\dots,n-1\\}$. For any set $S$ and $k\in\mathbf{N}$, the set
$[S]^{k}$ is $\\{T\subset S\colon|T|=k\\}$, i.e., the set of all $k$-subsets
of $S$. We write $\mathcal{P}(S)$ for the powerset of $S$. If $f\colon A\to B$
is a function and $X\subset A$, we write
$f\mathbin{\texttt{\textquotedbl}}X=\\{f(x)\colon x\in X\\}$ instead of the
more usual (outside set theory) but ambiguous $f(X)$. Throughout the paper,
$\log$ is the _binary_ logarithm (although the choice of base is
inconsequential in most places).

######  Definition 1.1 (Rado’s arrow notation).

Given $k\geq 2$, $n>r\geq 1$, _an $r$-subset $k$-colouring of $\llbracket
n\rrbracket$_ is a function $f\colon[\llbracket n\rrbracket]^{r}\to\llbracket
k\rrbracket$. A set $X\subset\llbracket n\rrbracket$ is _monochromatic (under
$f$, in the colour $i\in\llbracket k\rrbracket$)_ if $[X]^{r}\subset
f^{-1}(i)$, or equivalently
$f\mathbin{\texttt{\textquotedbl}}[X]^{r}=\\{i\\}$. For $k$ integers
$(s_{i})_{i\in\llbracket k\rrbracket}$ all satisfying $n\geq s_{i}>r$, we
write

$n\rightarrow(s_{0},\dots,s_{k-1})^{r},$

or more concisely $n\rightarrow(s_{i})_{i\in\llbracket k\rrbracket}^{r}$, to
mean that for every $f\colon[\llbracket n\rrbracket]^{r}\to\llbracket
k\rrbracket$ there is a colour $i\in\llbracket k\rrbracket$ in which a subset
of $\llbracket n\rrbracket$ of size $s_{i}$ is monochromatic. When
$s_{0}=s_{1}=\dots=s_{k-1}=s$ (the “diagonal case”) this is further
abbreviated to $n\rightarrow(s)_{k}^{r}$.

The logical negation of any arrow relation is written similarly, replacing
$\rightarrow$ with $\nrightarrow$.

Our main result is as follows.

######  Theorem 1.2.

Fix integers $k\geq 2$ and $n>r\geq 3$ and $k$ integers
$(s_{i})_{i\in\llbracket k\rrbracket}$ all satisfying $n\geq s_{i}\geq r+1$.

$\displaystyle\text{If }n\nrightarrow(s_{i})_{i\in\llbracket
k\rrbracket}^{r}\text{ then
}2^{n}\nrightarrow(s_{0}+1,\dots,s_{k-1}+1,\underbrace{r+2,\dots,r+2}_{\begin{subarray}{c}\eta(r)\text{
terms,}\\\ \text{each $r+2$}\end{subarray}})^{r+1},$

with the integer

$\eta(r)=\begin{cases}1&\text{if }r=3,\\\ 2&\text{if }r>3\text{ is even,}\\\
3&\text{if }r>3\text{ is odd. }\end{cases}$ (1)

This result extends to transfinite cardinals, strengthening results of Erdős
et al. [7, Chap. 24] in certain ranges of parameters (Appendix A).

Let $n\geq s>r\geq 1$ and $k\geq 2$. The _(multicolour, hypergraph, diagonal)
Ramsey number_ 111Different authors use different notations: cf.
$r_{k}(K_{s}^{r})$ [1], $r_{r}(s;k)$ [4], $R_{k}(s;r)$ [13]. $r_{k}(s;r)$ is
the smallest $n$ for which $n\rightarrow(s)_{k}^{r}$. The fact that these
numbers exist is Ramsey’s 1930 theorem [14].

As a corollary to Theorem 1.2, we obtain improved lower bounds for multicolour
Ramsey numbers. The _tower functions_ are defined by
$\operatorname{twr}_{1}(x)=x$ and
$\operatorname{twr}_{r+1}(x)=2^{\operatorname{twr}_{r}(x)}$.

######  Corollary 1.3.

There are absolute constants $\alpha\simeq 1.678$ and $\beta$ such that for
$r=3$ and any $k\geq 4$ or for $r\geq 4$ and $k\geq\lfloor 5r/2\rfloor-5$, we
have:

$r_{k}(r+1;r)>\operatorname{twr}_{r}\left(\frac{\alpha}{2}\cdot\left(k-\frac{5r}{2}\right)+\beta\right),$
(2)

and for $r=3$ and any $k\geq 2$ or for $r\geq 4$ and $k\geq\lfloor
5r/2\rfloor-7$,

$r_{k}(r+2;r)>\operatorname{twr}_{r}\left(\alpha\cdot\left(k-\frac{5r}{2}\right)+\beta\right).$
(3)

#### Subset colouring in hypergraphs.

Our second result addresses a hypergraph colouring problem. Given a hypergraph
$H$ and $r\in\mathbf{N}$, we are interested in the minimum number $k=k(H;r)$
for which there exists a $k$-colouring of all $r$-subsets of vertices without
any monochromatic hyperedge of size $\geq r+1$. Note that if all the
hyperedges in $H$ are of size at least $2$, then $k(H;1)=\chi(H)$, the
standard _vertex chromatic number_ of $H$ (i.e. the least number of colours in
a colouring of $V$ in which no hyperedge is monochromatic).

In a work on simplicial complexes, Sarkaria related this parameter (which he
called the _weak $r$-th chromatic number_), to embeddability properties [15,
16, 17].

We show (Theorem 4.2) that for any $H$, the number of colours $k(H;r)$ is not
much larger than the corresponding number of colours
$k(K_{r\chi(H)}^{(r+1)};r)$ where the hypergraph $K_{r\chi(H)}^{(r+1)}$ is the
complete $(r+1)$-uniform on $r\chi(H)$ vertices. Note that
$\chi(K_{r\chi(H)}^{(r+1)})=\chi(H)$. This resembles the Erdős–Stone theorem
[8] (the chromatic number of a graph essentially controls its Turán number).
Hence finding $k(n,r)=\max\\{k(H;r)\colon\chi(H)=n\\}$ for any $n,r$, is
essentially equivalent to the problem of finding the Ramsey number
$r_{k^{\prime}}(r+1;r)$ for an appropriate value of $k^{\prime}$.

With our lower bound on multicolour Ramsey numbers and the previously known
upper bound, we obtain (Corollary 4.7):

$\Omega\left(\frac{\log^{(r-1)}(rn)}{\log^{(r)}(rn)}\right)<k(n,r)<O\left(\log^{(r-1)}(rn)+r\right).$

###  1.1 Previous results

The values of $r_{k}(s;r)$ remain unknown except for several simple cases; in
fact, for $r\geq 3$ only $r_{2}(4;3)=13$ is known [12]. For general $r$ the
only known bounds are

$\operatorname{twr}_{r}(c^{\prime}k)\leq
r_{k}(s;r)\leq\operatorname{twr}_{r}(ck\log k)$ (4)

for sufficiently large $s$, with $c$ and $c^{\prime}$ functions of $s$ and $r$
[6, 7]. See the book by [11] for background on finite Ramsey theory and the
survey by [13] for recent bounds.

Some lower bounds on Ramsey numbers are obtained through _stepping-up
lemmata_. The following (negative) stepping-up lemma attributed is due Erdős
and Hajnal [11]. It transforms lower bounds on $r_{k}(\,\cdot\,;r)$ into lower
bounds on $r_{k}(\,\cdot\,;r+1)$, as follows:

$\displaystyle\text{if }r\geq 3\text{ and }n\nrightarrow(s)_{k}^{r}\text{ then
}2^{n}\nrightarrow(2s+r-4)_{k}^{r+1},$ (5) and, for stepping up from 2 to 3:
$\displaystyle\text{if }n\nrightarrow(s)_{k}^{2}\text{ then
}2^{n}\nrightarrow(s+1)_{2k}^{3},$ (6) where the number of colours doubles.
[4] improved (5): $\displaystyle\text{if }r\geq 4\text{ and
}n\nrightarrow(s)_{k}^{r}\text{ then }2^{n}\nrightarrow(s+3)_{k}^{r+1}.$ (7)
Furthermore for odd $r$ or for $k\geq 3$, they obtain $\displaystyle\text{if
}r\geq 4\text{ and }n\nrightarrow(s)_{k}^{r}\text{ then
}2^{n}\nrightarrow(s+2)_{k}^{r+1}.$ (8) Repeated application of this last
lemma alone will not guarantee the lower bound of (4) where $s$ and $r$ are
both large and $s<2r$. For example, it cannot deal with the case where the
size of the hyperedges grows by exactly $1$. This is why [1] implicitly
establish the following variant: $\displaystyle\text{if }r\geq 2\text{ and
}n\nrightarrow(s)_{k}^{r}\text{ then }2^{n}\nrightarrow(s+1)_{2k+2r-4}^{r+1},$
(9) which implies, in the left inequality of (4), that for any $s>r$ and any
$k>r2^{r}$, we have
$r_{k}(s;r)>\operatorname{twr}_{r}\left(\frac{k}{2^{r}}\right)$. We mention
one more earlier result by [9, Lemma 24.1]: $\displaystyle\text{if }r\geq
3\text{ and }n\nrightarrow(s)_{k}^{r}\text{ then
}2^{n}\nrightarrow(s+1)_{k+2^{r}+2^{r-1}-4}^{r+1}.$ (10)

###  1.2 Organization of the paper

Section 2 establishes our stepping-up lemma (Theorem 1.2). In Section 3 we
apply said lemma to improve the lower bounds for several multicolour
hypergraph Ramsey numbers. Section 4 deals with subset-colouring of
hypergraphs. Appendix A extends the stepping-up lemma to infinite cardinals.
Appendix B explains our starting bound on $r_{k}(3;2)$.

##  2 A stepping-up lemma

In this section we prove Theorem 1.2. To this end let $k$, $n$, $r$,
$(s_{i})_{i\in\llbracket k\rrbracket}$ be as in the hypotheses. In particular,
there exists $f_{r}:[\llbracket n\rrbracket]^{r}\to\llbracket k\rrbracket$
under which, for every $i\in\llbracket k\rrbracket$, no set of size $s_{i}$ is
monochromatic in colour $i$. We will use $f_{r}$ to construct
$f_{r+1}:[\llbracket 2^{n}\rrbracket]^{r+1}\to\llbracket k+\eta(r)\rrbracket$
under which, for every $i\in\llbracket k\rrbracket$, no set of size $s_{i}+1$
is monochromatic in colour $i$, and no set of size $r+2$ is monochromatic in
either of the additional colours $k$, $k+1$, …, $k+\eta(r)-1$.

###  2.1 Preliminary results and definitions

Before proceeding to the proof of the theorem, we need several definitions and
results.

#### Splitting indices.

For every natural number $n$, let $d(n)\subset\mathbf{N}$ be the unique finite
set of integers such that $n=\sum_{i\in d(n)}2^{i}$. In other words, $d(n)$ is
the set of non-zero indices in the binary representation of $n$. Given a
finite set $S$ of natural numbers, $|S|\geq 2$, its _first splitting index_ is

$s(S)=\max\\{i\in\mathbf{N}\colon\exists x,y\in S\colon i\in d(x)\setminus
d(y)\\}.$

That is, $s(S)$ is the index of the most significant bit where two elements in
$S$ differ in their binary representation.

The first splitting index partitions $S$ into two disjoint, non-empty subsets
$S_{0}=\\{x\in S\colon s(S)\notin d(x)\\}$ and $S_{1}=\\{x\in S\colon s(S)\in
d(x)\\}$ with $\max S_{0}<\min S_{1}$. This partition is unique and exists as
soon as $|S|\geq 2$; we use the notation $(S_{0}\mathbin{\mid}S_{1})$ to
denote the set $S$ where the partition $S_{0}\dot{\cup}S_{1}$ is the partition
obtained at the first splitting index.

######  Observation 2.1.

Let $S=(S_{0}\mathbin{\mid}S_{1})$ be a set of at least two natural numbers.
If $\emptyset\neq L\subset S_{0}$ and $\emptyset\neq R\subset S_{1}$ then
$s(L\cup R)=s(S)$ and $L\cup R=(L\mathbin{\mid}R)$.

#### Caterpillars.

We define a family $\mathcal{C}\subset\mathcal{P}(\mathbf{N})$, whose elements
we call _caterpillars_ (due to their resemblance with the caterpillar trees of
graph theory), as follows: The empty set and all singletons are caterpillars.
A finite set of 2 or more natural integers, with partition
$(S_{0}\mathbin{\mid}S_{1})$, is a caterpillar if and only if at least one of
$S_{0}$ and $S_{1}$ is a singleton and the other is a caterpillar.

For example, the reader may check that
$\\{0,1,2,4\\}=(((\\{0\\}\mathbin{\mid}\\{1\\})\mathbin{\mid}\\{2\\})\mathbin{\mid}\\{4\\})\in\mathcal{C}$
and $\\{0,1,2,3\\}=(\\{0,1\\}\mathbin{\mid}\\{2,3\\})\notin\mathcal{C}$, by
considering binary representations of the integers. One can depict the
sequence of splits introducing the partitions using a full binary tree (see
Figure 1). Caterpillars are those subsets whose binary tree possesses a
dominating root-to-leaf path, that is, the vertex set of the tree can be
partitioned into a path and a collection of vertices where each vertex has a
neighbour on the path.

Figure 1: The tree structures of two caterpillars (left) and a non-caterpillar
(right). The splitting indices are marked in red and circled.

The proofs by [9] or [1] use a smaller class of thin sets, namely, the
caterpillars whose binary tree representations only have leaves for their
proper left subtrees.

######  Observation 2.2.

Let $S\subset\mathbf{N}$ be a finite set. The following are equivalent:

  1. 1.

$S\notin\mathcal{C}$.

  2. 2.

There is a subset $(L\mathbin{\mid}R)\subset S$ with $|L|,|R|\geq 2$.

  3. 3.

There is a subset $(L\mathbin{\mid}R)\subset S$ with $|L|=|R|=2$.

As a simple consequence, $\mathcal{C}$ is transitive: if $S\in\mathcal{C}$
then $\mathcal{P}(S)\subset\mathcal{C}$.

###### Proof.

The implication $(1)\implies(2)$ can be easily proved by induction on $|S|$.
Indeed, if $(S_{0}\mathbin{\mid}S_{1})\notin\mathcal{C}$ then either
$S_{0}\notin\mathcal{C}$, or $S_{1}\notin\mathcal{C}$, or $|S_{0}|,|S_{1}|\geq
2$.

The implication $(2)\implies(3)$ holds by Observation 2.1.

To show $(3)\implies(1)$, assume that $(3)$ holds but $(1)$ does not. By
$(3)$, there are four integers $a<b<c<d$ such that
$(\\{a,b\\}\mathbin{\mid}\\{c,d\\})\subset S\in\mathcal{C}$. By the definition
of $\mathcal{C}$, $S=(S_{0}\mathbin{\mid}S_{1})$ where either $|S_{0}|=1$ or
$|S_{1}|=1$, without loss of generality, $|S_{0}|=1$. It must be the case that
$S_{0}\cap\\{a,b,c,d\\}=\emptyset$ as otherwise $|S_{0}|>1$. Indeed, assume
without loss of generality that $a\in S_{0}$, then $c\notin S_{0}$ but because
$(\\{a,b\\}\mathbin{\mid}\\{c,d\\})\subset S$ we get that $b\in S_{0}$. Hence
$\\{a,b,c,d\\}\subseteq S_{1}$ and by induction on the size of the set we
consider we get a contradiction to $(3)$. ∎

With each caterpillar $S\in\mathcal{C}$ we associate a subset of indices
$\delta(S)=\\{s(\\{x,y\\})\colon x,y\in S,x\neq y\\}$. For example, the reader
may check that $\delta(\\{1,3,6,31\\})=\\{1,2,4\\}$.

######  Observation 2.3.

If $S\in\mathcal{C}\setminus\\{\emptyset\\}$ then $|\delta(S)|=|S|-1$.

###### Proof.

Simple induction using Observation 2.1. ∎

######  Observation 2.4.

For every $S\in\mathcal{C}\setminus\\{\emptyset\\}$ and $r\in\mathbf{N}$, we
have $[\delta(S)]^{r}=\delta\mathbin{\texttt{\textquotedbl}}[S]^{r+1}$.

###### Proof.

Note that ${[S]^{r+1}}\subset\mathcal{C}$, so the right-hand term is well-
defined.

For $r=0$ or $|S|=1$ this is clear: the equality becomes
$\\{\emptyset\\}=\\{\emptyset\\}$ if $r=0$ or $\emptyset=\emptyset$ if $r>0$
and $|S|=1$. For larger $|S|$ and $r$, let $x\in S$ be such that
$S=(L\mathbin{\mid}\\{x\\})$, $L\in\mathcal{C}\setminus\\{\emptyset\\}$ and
$s(L)<s(S)$. Then $\delta(S)=\\{s(S)\\}\mathbin{\dot{\cup}}\delta(L)$, where
the union is disjoint. Thus

$\displaystyle[\delta(S)]^{r}$ $\displaystyle=\\{\\{s(S)\\}\cup D\colon
D\in[\delta(L)]^{r-1}\\}\mathbin{\dot{\cup}}[\delta(L)]^{r}.$ By induction on
$r$ and the size of the set considered this is equal to
$\displaystyle[\delta(S)]^{r}$ $\displaystyle=\\{\\{s(S)\\}\cup\delta(Y)\colon
Y\in[L]^{r}\\}\mathbin{\dot{\cup}}\\{\delta(Y)\colon Y\in[L]^{r+1}\\}$ Thus,
$\displaystyle[\delta(S)]^{r}$
$\displaystyle=\\{\delta(Y\mathbin{\dot{\cup}}\\{x\\})\colon
Y\in[L]^{r}\\}\mathbin{\dot{\cup}}\\{\delta(Y)\colon Y\in[L]^{r+1}\\}$
$\displaystyle=\\{\delta(Y)\colon
Y\in[S]^{r+1}\\}=\delta\mathbin{\texttt{\textquotedbl}}[S]^{r+1}.\qed$

Each finite set $S=(L\mathbin{\mid}R)$ of natural numbers that is not a
caterpillar has a _type_ $t(S)\in\mathbf{N}\times\mathbf{N}$, defined by
induction as follows:

$t((L\mathbin{\mid}R))=\begin{cases}(|L|,|R|)&\text{if $|L|,|R|\geq 2$,}\\\
t(L)&\text{if $|R|=1$,}\\\ t(R)&\text{if $|L|=1$.}\end{cases}$

For example, $t(\\{0,1,2,3,4,8\\})=t(\\{0,1,2,3\\})=(2,2)$.

######  Observation 2.5.

Let $S$ be a finite, nonempty set of integers.

  1. (1)

If $S$ has type $(p,q)$ with $p\geq 3$ then some subset of $S$ of cardinality
$|S|-1$ has type $(p-1,q)$ (respectively $q\geq 3$ and $(p,q-1)$).

  2. (2)

If $S$ has type $(2,q)$ then some subset of $S$ of cardinality $|S|-1$ is a
caterpillar or has type $(p^{\prime},q^{\prime})$ with
$p^{\prime}+q^{\prime}\leq q$ (respectively $(p,2)$ and
$p^{\prime}+q^{\prime}\leq p$).

  3. (3)

If $S$ has type $(p,q)$ with $p+q<|S|$ then some subset of $S$ of cardinality
$|S|-1$ also has type $(p,q)$.

  4. (4)

The caterpillars are exactly the finite subsets of $\mathbf{N}$ without
subsets of type $(2,2)$.

###### Proof.

  1. (1)

We prove by induction on $|S|$. If $|S|=p+q$ then $S=(L\mathbin{\mid}R)$ with
$|L|=p$ and $|R|=q$. Let $x$ be any element of $L$, then by Observation 2.1
the set $S\setminus\\{x\\}=(L\setminus\\{x\\},R)$ has type $(p-1,q)$.

If $|S|>p+q$, then without loss of generality $S=(L\mathbin{\mid}\\{x\\})$
with $t(L)=(p,q)$. By induction, there is $L^{\prime}\subset L$ with
$|L^{\prime}|=|L|-1=|S|-2$ and $t(L^{\prime})=(p-1,q)$. Then
$L^{\prime}\cup\\{x\\}\subset S$ with $|L^{\prime}\cup\\{x\\}|=|S|-1$, and
$t(L^{\prime}\cup\\{x\\})=t(L^{\prime})=(p-1,q)$.

  2. (2)

By the same induction argument as above, it suffices to consider the case
$|S|=2+q$. Then $S=(\\{x,y\\}\mathbin{\mid}R)$ with $x\neq y$ and $|R|=q$.
Hence by Observation 2.1, $S\setminus\\{x\\}=(\\{y\\}\mathbin{\mid}R)$. If $R$
is a caterpillar, then $S\setminus\\{x\\}$ is a caterpillar, otherwise
$S\setminus\\{x\\}$ has type $(p^{\prime},q^{\prime})$ with
$p^{\prime}+q^{\prime}\leq|R|=q$.

  3. (3)

In this case, w.l.o.g., $S=(\\{x\\}\mathbin{\mid}R)$ with $R$ of type $(p,q)$.
Then $S\setminus\\{x\\}$ is of type $(p,q)$.

  4. (4)

Direct reformulation of Observation 2.2 (1),(3).∎

###  2.2 Description and validity of the colouring.

#### Description.

We can now define our colouring $f_{r+1}\colon[\llbracket
2^{n}\rrbracket]^{r+1}\to\llbracket k+3\rrbracket$. Let $S\in[\llbracket
2^{n}\rrbracket]^{r+1}$.

If $S\in\mathcal{C}$ then $\delta(S)\in[\llbracket n\rrbracket]^{r}$, and we
let $f_{r+1}(S)=f_{r}(\delta(S))\in\llbracket k\rrbracket$. Otherwise
$S\notin\mathcal{C}$ has a type $t(S)=(p,q)$ with $p,q\geq 2$ and $p+q\leq
r+1$, and we let

$f_{r+1}(S)=\begin{cases}k&\text{ if }p+q=r+1,\ p\text{ even},\\\ k+1&\text{
if }p+q<r+1,\ p+q\text{ even},\\\ 0&\text{ if }p+q=r+1,\ p\text{ odd and $r$
odd},\\\ k+2&\text{ if }p+q=r+1,\ p\text{ odd and $r$ even},\\\ 1&\text{ if
}p+q<r+1,\ p+q\text{ odd.}\end{cases}$

#### Validity.

We detail the proof that this colouring has the expected properties for $r$
odd. The case of even $r$ is similar and easier. Let $X\subset\llbracket
2^{n}\rrbracket$ be monochromatic in colour $i$ under $f_{r+1}$. We will show
that $|X|\leq s_{i}$ (if $i\in\llbracket k\rrbracket$) or $|X|\leq r+1$ (for
$i\in\\{k,k+1,k+2\\}$). As $r+1\leq s_{i}$ we may already assume $|X|>r+1$.

First consider the case $X\in\mathcal{C}$. Then by Observation 2.2,
$[X]^{r+1}\subset\mathcal{C}$, and thus

$\\{i\\}=f_{r+1}\mathbin{\texttt{\textquotedbl}}[X]^{r+1}=f_{r}\mathbin{\texttt{\textquotedbl}}(\delta\mathbin{\texttt{\textquotedbl}}[X]^{r+1})\subset\llbracket
k\rrbracket,$

so we have to show $|X|\leq s_{i}$. By Observation 2.4, the set
$\delta(X)\subset\llbracket n\rrbracket$ is monochromatic in colour $i$ under
$f_{r}$, as

$f_{r}\mathbin{\texttt{\textquotedbl}}[\delta(X)]^{r}=f_{r}\mathbin{\texttt{\textquotedbl}}(\delta\mathbin{\texttt{\textquotedbl}}[X]^{r+1})=\\{i\\}.$

This implies by the hypothesis on $f_{r}$ and Observation 2.3 that
$|X|-1=|\delta(X)|<s_{i}$, as required.

Now consider the case $X\notin\mathcal{C}$. We can assume $|X|=r+2$. The set
$X$ has a type $(P,Q)$ with $P,Q\geq 2$ and $P+Q\leq r+2$. We consider several
cases covering all possible values of $P$ and $Q$, and we argue that in each
case two $(r+1)$-subsets of $X$ receive distinct colours under $f_{r+1}$, i.e.
$|f_{r+1}\mathbin{\texttt{\textquotedbl}}[X]^{r+1}|\geq 2$.

  * •

If $P+Q=r+2$ and $P,Q\geq 3$, then by Observation 2.5 (1), $X$ contains
$(r+1)$-subsets $S,S^{\prime}$ of types $(P-1,Q)$ and $(P,Q-1)$, respectively,
so also the pair of colours $\\{0,k\\}=\\{f_{r+1}(S),f_{r+1}(S^{\prime})\\}$.

  * •

If $(P,Q)=(2,r)$: on one hand, by Observation 2.5 (1), there is an
$(r+1)$-subset $S$ with the type $(2,r-1)$ and $f_{r+1}(S)=k$. On the other
hand, by Observation 2.5 (2), there is an $(r+1)$-subset $S^{\prime}$ which is
either a caterpillar, so $f_{r+1}(S^{\prime})\in\llbracket k\rrbracket$, or of
a type $(x,y)$ with $x+y\leq r$, so $f_{r+1}(S^{\prime})\in\\{1,k+1\\}$.

  * •

If $(P,Q)=(r,2)$: symmetric to the previous case, because $r-1$ is even.

  * •

If $P+Q\leq r+1$ and $P\geq 3$, then by Observation 2.5 (3), $X$ contains an
$(r+1)$-subset $S$ of type $(P,Q)$ and by Observation 2.5 (1) an
$(r+1)$-subset $S^{\prime}$ of type $(P-1,Q)$. Since $S^{\prime}$ is not a
caterpillar and $P-1+Q<r+1$, $f_{r+1}(S^{\prime})\in\\{1,k+1\\}$. If
$f_{r+1}(S)\in\\{0,k\\}$ then we are done. Otherwise,
$f_{r+1}(S)\in\\{1,k+1\\}$, and the distinct parities of $P+Q$ and $P-1+Q$
give $\\{f_{r+1}(S),f_{r+1}(S^{\prime})\\}=\\{1,k+1\\}$

  * •

If $P+Q\leq r+1$ with $Q\geq 3$, same argument as the previous case.

  * •

If $(P,Q)=(2,2)$: because $r+2\geq 5$, by Observation 2.5 (3), there is an
$(r+1)$-subset $S$ of type $(2,2)$, whose colour is either $k$ (if $r=3$) or
$k+1$. On the other hand, by Observation 2.5 (2), there is an $(r+1)$-subset
$S^{\prime}$ which is a caterpillar, and so is coloured with some colour
between 0 and $k-1$.

######  Observation 2.6.

For odd $r$ the function $f_{r+1}$ does not use the colour $k+2$, and in the
case of $r=3$ the function $f_{4}$ also does not use the colour $k+1$.

This completes the proof of Theorem 1.2. We conclude with an observation which
will be useful in Section 3.

######  Observation 2.7.

If $n\nrightarrow(3)_{k}^{2}$ then $2^{n}\nrightarrow(5)_{k}^{3}$.

###### Proof.

First observe that every set of five natural numbers includes a caterpillar of
size four. Let the elements of $S\in[\mathbf{N}]^{5}$ be $a,b,c,d,e$. If
$S=(\\{a\\}\mathbin{\mid}\\{b,c,d,e\\})$ then $\\{a,b,c,d\\}\in\mathcal{C}$.
(Note that any 3-subset of $\mathbf{N}$ is a caterpillar.) If
$S=(\\{a,b\\}\mathbin{\mid}\\{c,d,e\\})$ then $\\{a,c,d,e\\}\in\mathcal{C}$.
Other cases are symmetric.

As in the proof of Theorem 1.2, the colours in $\llbracket k\rrbracket$
suffice for colouring $[\llbracket 2^{n}\rrbracket]^{3}$ such that any
caterpillar $S\subset\llbracket 2^{n}\rrbracket$ with $|S|=4$ is not
monochromatic. Any 5-subset of $\llbracket 2^{n}\rrbracket$ contains such an
$S$, and thus is itself not monochromatic under the same colouring. ∎

##  3 Lower bounds on multicolour hypergraph Ramsey numbers

Erdős, Hajnal and Rado obtained the first bounds on $r_{k}(s;r)$ [6, 7]. Note
the following:

######  Observation 3.1.

The quantity $r_{k}(s;r)$ is nondecreasing in $s$ and in $k$. The quantity
$r_{k}(r+1;r)$ is nondecreasing in $r$.

######  Theorem 3.2 ([7][7], [6][6]).

Let $r\geq 2$. There exists $s_{0}(r)$ such that:

  * •

For any $s>s_{0}$, we have
$r_{k}(s;r)\geq\operatorname{twr}_{r}(c^{\prime}k)$,

  * •

For any $s>r$, we have $r_{k}(s;r)\leq\operatorname{twr}_{r}(ck\log k)$,

where $c^{\prime}=c^{\prime}(s,r)$ and $c=c(s,r)\leq 3(s-r)$.

Unlike the upper bound, the lower bound holds only for sufficiently large
values of $s$. Duffus, Leffman and Rödl [5] gave a tower-function lower bound
for all $s\geq r+1$, but said bound,
$\operatorname{twr}_{r-1}(c^{\prime\prime}k)$, is significantly weaker than
the bound of Theorem 3.2. Conlon, Fox, and Sudakov [4] proved that the lower
bound of Theorem 3.2 holds whenever $s\geq 3r$. Axenovich et al. [1] matched
the lower bound of Theorem 3.2 for all $s>r$, but only for sufficiently large
$k$.

######  Theorem 3.3 ([1]).

For any $s>r\geq 2$ and any $k>r2^{r}$, we have

$r_{k}(s;r)>\operatorname{twr}_{r}\left(\frac{k}{2^{r}}\right).$

In particular the results of [4] give $r_{k}(s;3)\geq 2^{2^{c^{\prime}k}}$ for
some constant $c^{\prime}$ whenever $s\geq 9$, and the results of [1] give
$r_{k}(4;3)>2^{2^{k/8}}$ for all $k>24$.

We prove that the lower bound of Theorem 3.2 holds for values of $k$ much
closer to $r$ than in Theorem 3.3, and also improve the constant inside the
tower function.

######  Corollary (1.3).

There are absolute constants $\alpha\simeq 1.678$ and $\beta$ such that for
$r=3$ and any $k\geq 4$ or for $r\geq 4$ and $k\geq\lfloor 5r/2\rfloor-5$, we
have:

$r_{k}(r+1;r)>\operatorname{twr}_{r}\left(\frac{\alpha}{2}\cdot\left(k-\frac{5r}{2}\right)+\beta\right),$
(11)

and for $r=3$ and any $k\geq 2$ or for $r\geq 4$ and $k\geq\lfloor
5r/2\rfloor-7$,

$r_{k}(r+2;r)>\operatorname{twr}_{r}\left(\alpha\cdot\left(k-\frac{5r}{2}\right)+\beta\right).$
(12)

###### Proof.

Fix some integers $K\geq 0$ and $n,s\geq 4$ such that
$n\nrightarrow(s)_{K+2}^{3}$. Through either $2t+1$ or $2t+2$ repeated
applications of Theorem 1.2 we get, for any $t\in\mathbf{N}$,

$\displaystyle\operatorname{twr}_{2t+2}n$
$\displaystyle\nrightarrow(s+2t+1)_{K+5t+3}^{4+2t}$ (13)
$\displaystyle\text{and }\operatorname{twr}_{2t+3}n$
$\displaystyle\nrightarrow(s+2t+2)_{K+5t+5}^{5+2t}.$ (14)

Equivalently, in terms of Ramsey numbers,

$\displaystyle r_{K+5t+3}(s+2t+1;4+2t)$
$\displaystyle>\operatorname{twr}_{2t+2}n$ (15) $\displaystyle\text{and
}r_{K+5t+5}(s+2t+2;5+2t)$ $\displaystyle>\operatorname{twr}_{2t+3}n.$ (16)

It is known (see Appendix B) that there are absolute constants $C_{0}>0$ and
$C_{1}=1073^{1/6}\simeq 3.199$ such that, for every integer $L\geq 0$,

$\lceil C_{0}\cdot C_{1}^{L+2}\rceil\nrightarrow(3)_{L+2}^{2}.$

From there we have both $2^{\lceil C_{0}\cdot
C_{1}^{L+2}\rceil}\nrightarrow(4)_{2L+4}^{3}$ and $2^{\lceil C_{0}\cdot
C_{1}^{L+2}\rceil}\nrightarrow(5)_{L+2}^{3}$, which establishes the Theorem
for $r=3$. The first relation follows from (6) and the second from Observation
2.7. Insert these parameters in (15) and (16) to obtain respectively

$\displaystyle\operatorname{twr}_{2t+4}(\log C_{0}+(L+2)\log C_{1})$
$\displaystyle<r_{2L+5t+5}(5+2t;4+2t),r_{L+5t+3}(6+2t;4+2t),$ (17)
$\displaystyle\operatorname{twr}_{2t+5}(\log C_{0}+(L+2)\log C_{1})$
$\displaystyle<r_{2L+5t+7}(6+2t;5+2t),r_{L+5t+5}(7+2t;5+2t).$ (18)

Any even $r\geq 4$ is of the form $r=2t+4$ (so $\lfloor 5r/2\rfloor=5t+10$)
and thus (17) yields:

$\displaystyle\operatorname{twr}_{r}(\log C_{0}+(L+2)\log C_{1})$
$\displaystyle<r_{2L+\lfloor 5r/2\rfloor-5}(r+1;r)\leq r_{(2L+1)+\lfloor
5r/2\rfloor-5}(r+1;r),$ $\displaystyle\operatorname{twr}_{r}(\log
C_{0}+(L+2)\log C_{1})$ $\displaystyle<r_{L+\lfloor 5r/2\rfloor-7}(r+2;r),$

where the rightmost inequality in the first line follows from Observation 3.1.
The same equations are also obtained for odd $r\geq 5$, this time by setting
$r=2t+5$ in $\eqref{eq:odd_r}$. This proves (2) for all values $k\geq\lfloor
5r/2\rfloor-5$ (respectively (3) and $\lfloor 5r/2\rfloor-7$). ∎

To the best of our knowledge, the current best lower bound for $r_{k}(5;3)$
(for large $k$) is $\operatorname{twr}_{3}(k+O(1))$ [2]. Compare with our
$r_{k}(5;3)>\operatorname{twr}_{3}(1.678k+O(1))$.

##  4 Subset-colouring of hypergraphs

Recall that, given a hypergraph $H=(V,E)$ and $r\in\mathbf{N}$, the integer
$k=k(H;r)$ is the least number of colours for which there is a colouring
$[V]^{r}\to\llbracket k\rrbracket$ without any monochromatic hyperedge $e\in
E$ of size $\geq r+1$, and $k(n,r)=\max\\{k(H;r)\colon\chi(H)=n\\}$. As noted
by Sarkaria [17], the problem of determining $k(n,r)$ is closely related to
the “classical” Ramsey problem discussed in previous sections. Indeed, for
$n\in\mathbf{N}$, consider the complete $(r+1)$-uniform hypergraph on $rn$
vertices $K_{rn}^{(r+1)}$. Clearly, $\chi(K_{rn}^{(r+1)})=n$, and we have

######  Observation 4.1.

For any $n,r\in\mathbf{N}$,

$k(K_{rn}^{(r+1)};r)=\min\\{k\colon r_{k}(r+1;r)>rn\\}.$ (19)

###### Proof.

By definition, $k(K_{rn}^{(r+1)};r)$ is the least $k$ for which there is a
colouring $[\llbracket rn\rrbracket]^{r}\to\llbracket k\rrbracket$ without any
monochromatic $(r+1)$-subset, i.e. such that $rn\nrightarrow(r+1)_{k}^{r}$, or
equivalently such that $rn<r_{k}(r+1;r)$. ∎

Our main result in this section is that the values $k(n,r)$ and
$k(K_{rn}^{(r+1)};r)$ are very close to each other:

######  Theorem 4.2.

For any positive integers $n$ and $r$,

$k(K_{rn}^{(r+1)};r)\leq k(n,r)\leq k(K_{rn}^{(r+1)};r)+5.$ (20)

Theorem 4.2 will follow from Theorem 4.3 below. From the above Observation and
Theorem we conclude that the problem of finding $k(n,r)$ is essentially
equivalent to the problem of finding the Ramsey number $r_{k^{\prime}}(r+1;r)$
for an appropriate value of $k^{\prime}$.

######  Theorem 4.3.

Let $r,k\geq 2$ and let $n$ be such that $n\nrightarrow(r+1)_{k}^{r}$. If the
hypergraph $(V,E)$ admits a vertex-colouring $V\to\llbracket n\rrbracket$
under which no hyperedge of size $\geq r+1$ is monochromatic, then there is an
$r$-subset colouring $[V]^{r}\to\llbracket k+f(r)\rrbracket$ such that no
hyperedge of size $\geq r+1$ is monochromatic. Here

$f(r)=\begin{cases}1&\text{if }r=2,\\\ 3&\text{if }r=3,\\\ 4&\text{if }r\geq
4\text{ and }r+1\text{ is prime,}\\\ 5&\text{otherwise.}\end{cases}$

######  Remark 4.4.

In Theorem 4.3 we require only hyperedges of size at least $(r+1)$ not to be
monochromatic. A stronger but more natural condition is for $(V,E)$ to have
_vertex chromatic number_ at most $n$.

###### Proof of Theorem 4.2.

Let $k=k(K_{rn}^{(r+1)};r)$, so that $rn\nrightarrow(r+1)_{k}^{r}$ and, by
monotony, $n\nrightarrow(r+1)_{k}^{r}$. Theorem 4.3 then states that any
hypergraph with vertex chromatic number $n$ has an $r$-subset colouring with
$k+5$ colours and no monochromatic hyperedge of size $r+1$, i.e. $k(n,r)\leq
k+5$. The left inequality of (20) is by definition. ∎

######  Remark 4.5.

The two-sided relation with Ramsey numbers in Theorem 4.2 holds only for
$k(n,r)$. For a specific hypergraph $H$, $k(H;r)$ may be much smaller than
$k(K_{r\chi(H)}^{(r+1)};r)$. For example, fix $r$ and let $H$ be the complete
$r$-uniform hypergraph on $\ell$ vertices $K_{\ell}^{(r)}$. We have $k(H;r)=1$
but $r\chi(H)>\ell$ so
$k(K_{r\chi(H)}^{(r+1)};r)\geq\min\\{k\colon\ell\nrightarrow(r+1)^{r}_{k}\\}\to\infty$
as $\ell$ increases.

###### Proof of Theorem 4.3..

Let $C_{1}:V\to\llbracket n\rrbracket$ be the given proper colouring of $V$.
Let $C_{2}:[\llbracket n\rrbracket]^{r}\to\llbracket k\rrbracket$ be an
$r$-subset colouring without monochromatic set in $[\llbracket
n\rrbracket]^{r+1}$.

In order to describe the colouring, we need some more definitions. An _(
$m$-part) partition_ of $r$ is a non-increasing sequence of positive integers
$(r_{0},\dots,r_{m-1})\in(\mathbf{N}\setminus\\{0\\})^{m}$ with
$\sum_{i\in\llbracket m\rrbracket}r_{i}=r$. When $m>1$, this partition is
_balanced_ if $r_{0}=\dots=r_{m-1}$, and _almost balanced_ if
$r_{0}=\dots=r_{m-2}$ and $r_{m-1}=r_{0}-1$.

To every partition $R=(r_{0},\dots,r_{m-1})$ we associate an ordered pair in
${\llbracket 2\rrbracket}^{2}$:

$C_{0}(R)=\left(\begin{cases}0&\text{if $m+r_{m-1}$ is even,}\\\
1&\text{otherwise}\end{cases},\begin{cases}0&\text{if }r_{m-1}=1,\\\
1&\text{otherwise}\end{cases}\right).$

In addition, given $C_{0}(R)=(a,b)$ we define
$\overline{C_{0}}(R)=k+2a+b\in\\{k,k+1,k+2,k+3\\}$.

Finally, the _histogram_ of a sequence $(x_{i})_{i\in[r]}$ is the unique
partition $(r_{0},\dots,r_{m-1})$ of $r$ such that $(x_{i})_{i\in[r]}$
contains exactly $m$ distinct values $y_{0},\dots y_{m-1}$, and $y_{i}$
appears exactly $r_{i}$ times. For example, the histogram of the $6$-sequence
$(9,7,7,7,15,15)$ is $(3,2,1)$, a partition of $6$.

We are ready to define the $r$-subset colouring $C\colon[V]^{r}\to\llbracket
k+5\rrbracket$. Given $\\{x_{1},\dots,x_{r}\\}\in[V]^{r}$, write
$c_{i}=C_{1}(x_{i})$ for every $i\in[r]$. Let $S=(r_{0},\dots,r_{m-1})$ be the
histogram of the sequence $(c_{i})_{i\in[r]}$. We let

$C(\\{x_{1},\dots,x_{r}\\})=\begin{cases}C_{2}(\\{c_{i}\colon i\in\llbracket
r\rrbracket\\})\in\llbracket k\rrbracket&\text{if $S=(1,1,\dots,1)$},\\\
k+4&\begin{aligned} &\text{if $S$ is almost balanced}\\\ &\text{and
}\min\\{c_{i}\colon i\in\llbracket r\rrbracket\\}\text{ appears}\\\
&\text{exactly }r_{m-1}\text{ times,}\end{aligned}\\\
\overline{C}_{0}(S)\in\\{k,k+1,k+2,k+3\\}&\text{otherwise.}\end{cases}$

For example, if $r=5,n>15,$ and some 5-subset $\\{x_{1},\dots,x_{5}\\}$ of $V$
gets in $C_{1}$ the colours $(2,3,3,3,15)$, then $S=(3,1,1)$, and so
$C(\\{x_{1},\dots,x_{5}\\})=k+2\cdot 0+0=k$, since $m+r_{m-1}=3+1$ is even,
and $r_{m-1}=r_{2}=1$.

#### Validity of the colouring.

Without loss of generality it suffices to prove that any hyperedge of size
$r+1$, that is $e=\\{x_{1},\dots,x_{r+1}\\}\in E$, contains two $r$-subsets
receiving distinct colours in the colouring $C$. Let $R$ be the histogram of
the sequence $(C_{1}(x_{i}))_{i\in[r+1]}$.

Let us first eliminate one of the possible cases in the colouring.

######  Observation 4.6.

The hyperedge $e$ is not monochromatic in the colour $k+4$.

###### Proof of Observation 4.6.

If $R$ is balanced, then clearly $e$ contains an $r$-subset that is not
coloured $k+4$. If $R$ is not balanced, assume to the contrary that all
$r$-subsets of $e$ are coloured $k+4$. In particular their histograms are all
almost balanced.

Let $(\underbrace{a,\dots,a,}_{\text{$m+1$ places}}a-1)$ be the almost
balanced histogram of some $r$-subset of $e$ with $m\geq 0$ and $a\geq 2$.
Then $R$ is either (I) $(a+1,\underbrace{a,\dots,a,}_{\text{$m$ places}}a-1)$
or (II) $(\underbrace{a,\dots,a,}_{\text{$m+1$ places}}a-1,1)$.

In case (I), we have $m>0$ as otherwise depending on whether $a>2$ some
$r$-subset has the histogram $(3)$ or $(a+1,a-2)$, and neither is almost
balanced. Then we must have $m=1$, $a=2$ and $R=(3,2,1)$, but in this case
$r=5$ and $e$ contains a 5-subset with histogram $(3,1,1)$, which is not
almost balanced either.

In case (II), as by assumption $(\underbrace{a,\dots,a,}_{\text{$m$
places}}a-1,a-1,1)$ is almost balanced,we have $m=0$ and $a=3$. Hence
$R=(3,2,1)$, still a contradiction. ∎

It follows from Observation 4.6 that whenever $e$ contains an $r$-subset
coloured with $k+4$, $e$ is not monochromatic in the colouring $C$. Hence, in
the analysis below (specifically, in cases 3-5), no $r$-subset of $e$ is ever
monochromatic in colour $k+4$.

As $e$ is not monochromatic under $C_{1}$ we have $m\geq 2$. Five cases cover
all remaining possible values of $R=(r_{0},\dots,r_{m-1})$. Let $\delta_{ij}$
be $1$ if $i=j$ and $0$ otherwise.

  * •

Case 1: $r_{0}=r_{m-1}=1$, i.e. the $C_{1}(x_{i})$ are all distinct. Then, by
the definition of $C_{2}$, $\\{C_{1}(x_{i})\colon i\in[r+1]\\}$ contains two
$r$-subsets that admit two distinct colours in $C_{2}$, and therefore also in
$C$.

  * •

Case 2: $r_{0}=r_{m-1}>1$. In this case, some $r$-subset of $e$ is coloured in
$C$ with $k+4$, and by Observation 4.6 we are done.

  * •

Case 3: $r_{0}>r_{m-1}>1$. In this case, some $r$-subset of $e$ has the
histogram $R_{1}=(r_{0},\dots,r_{m-2},r_{m-1}-1)$, while another $r$-subset of
$e$ has the histogram $R_{2}=(r_{i}-\delta_{ij})_{i\in\llbracket m\rrbracket}$
for some $j<m-1$. Since $C_{0}(R_{1})$ and $C_{0}(R_{2})$ differ in the first
coordinate, $\overline{C}_{0}(R_{1})\neq\overline{C}_{0}(R_{2})$ hence these
two $r$-subsets admit two distinct colours in $C$.

  * •

Case 4: $r_{m-2}>r_{m-1}=1$. In this case, some $r$-subset of $e$ has the
histogram $R_{1}=(r_{0},\dots,r_{m-2})$, while another $r$-subset of $e$ has
the histogram $R_{2}=(r_{0},r_{1},\dots,r_{m-2}-1,1)$. Since $C_{0}(R_{1})$
and $C_{0}(R_{2})$ differ in the second coordinate,
$\overline{C}_{0}(R_{1})\neq\overline{C}_{0}(R_{2})$ hence these two
$r$-subsets admit two distinct colours in $C$.

  * •

Case 5: $r_{0}>r_{m-2}=r_{m-1}=1$. In this case, some $r$-subset of $e$ has
the histogram $R_{1}=(r_{0},\dots,r_{m-2})$, while another $r$-subset of $e$
has the histogram $R_{2}=(r_{i}-\delta_{ij})_{i\in\llbracket m\rrbracket}$ for
some $j<m-2$. Since $C_{0}(R_{1})$ and $C_{0}(R_{2})$ differ in the first
coordinate (note that $r_{m-1}=r_{m-2}=1$),
$\overline{C}_{0}(R_{1})\neq\overline{C}_{0}(R_{2})$ hence these two
$r$-subsets admit two distinct colours in $C$.

Finally, note that for specific values of $r$, some colours are left unused:
For $r=2$, the colours used are in $\llbracket k\rrbracket\cup\\{k+2\\}$. For
$r=3$, they are in $\llbracket k\rrbracket\cup\\{k+1,k+2,k+4\\}$. Finally, if
$r+1$ is prime then $R$ cannot be balanced without being $(1,1,\dots,1)$. In
this case we can define $C$ without using the colour $k+4$ (whose role in the
proof is to handle balanced partitions of $r+1$). This justifies having the
number of colours $f(r)$ as in the statement of the theorem. ∎

For the next result, let $\operatorname{Log}x=\max\\{1,\log x\\}$.

######  Corollary 4.7.

For $n\geq r\geq 2$, we have

$\frac{1}{3}\cdot\frac{\operatorname{Log}^{(r-1)}(rn)}{\operatorname{Log}^{(r)}(rn)}+o(1)\leq
k(n,r)\leq\frac{2}{\alpha}\operatorname{Log}^{(r-1)}(rn)+\frac{5r}{2}+O(1).$
(21)

###### Proof.

Combining Observation 4.1 and Theorem 4.2, we have

$\min\\{k\colon r_{k}(r+1;r)>rn\\}\leq k(n,r)\leq\min\\{k\colon
r_{k}(r+1;r)>rn\\}+5.$

For $rn$ large enough, let
$k_{0}=\lceil\frac{2}{\alpha}(\log^{(r-1)}(rn)-\beta)+\frac{5r}{2}\rceil\geq\lceil
5r/2\rceil$. By Corollary 1.3, we have

$r_{k_{0}}(r+1;r)>\operatorname{twr}_{r}\left(\frac{\alpha}{2}\cdot\left(k_{0}-\frac{5r}{2}\right)+\beta\right)\geq
rn,$

thus $k(n,r)\leq k_{0}+5$.

Similarly, also for large $rn$, let
$k_{1}=\lfloor\frac{1}{3}\cdot\frac{\log^{(r-1)}(rn)}{\log^{(r)}(rn)}\rfloor$.
By Theorem 3.2, we have $r_{k_{1}}(r+1;r)<\operatorname{twr}_{r}(3k_{1}\log
k_{1})\leq rn$. By the monotony of $r_{k}(r+1;r)$ in $k$ (Observation 3.1), we
conclude $k(n,r)>k_{1}$. ∎

## References

  * [1] Maria Axenovich, András Gyárfás, Hong Liu and Dhruv Mubayi  “Multicolor Ramsey numbers for triple systems”  In _Discrete Mathematics_ 322, 2014, pp. 69–77  DOI: 10.1016/j.disc.2014.01.004
  * [2] Melody Bruce, Mark Budden and Josh Hiller  “Lexicographic products of $r$-uniform hypergraphs and some applications to hypergraph Ramsey theory”  In _Australasian journal of combinatorics_ 70.3, 2018, pp. 390–401  URL: https://ajc.maths.uq.edu.au/pdf/70/ajc_v70_p390.pdf
  * [3] F… Chung and C.. Grinstead  “A survey of bounds for classical Ramsey numbers”  In _Journal of Graph Theory_ 7.1, 1983, pp. 25–37  DOI: 10.1002/jgt.3190070105
  * [4] David Conlon, Jacob Fox and Benny Sudakov  “An improved bound for the stepping-up lemma” Jubilee Conference on Discrete Mathematics  In _Discrete Applied Mathematics_ 161.9, 2013, pp. 1191–1196  DOI: 10.1016/j.dam.2010.10.013
  * [5] Dwight Duffus, Hannon Lefmann and Vojtěch Rödl  “Shift graphs and lower bounds on Ramsey numbers $r_{k}(l;r)$”  In _Discrete Mathematics_ 137.1, 1995, pp. 177–187  DOI: 10.1016/0012-365X(93)E0139-U
  * [6] P. Erdős, A. Hajnal and R. Rado  “Partition relations for cardinal numbers”  In _Acta Mathematica Academiae Scientiarum Hungaricae_ 16, 1965, pp. 93–196  DOI: 10.1007/BF01886396
  * [7] P. Erdős and R. Rado  “Combinatorial theorems on classifications of subsets of a given set”  In _Proceedings of the London Mathematical Society_ 2.3, 1952, pp. 417–439
  * [8] P. Erdős and A.. Stone  “On the structure of linear graphs”  In _Bulletin of the American Mathematical Society_ 52.12 American Mathematical Society, 1946, pp. 1087–1091  DOI: bams/1183510246
  * [9] Paul Erdős, András Hajnal, Attila Máté and Richard Rado  “Combinatorial set theory: partition relations for cardinals”, Studies in logic and the foundations of mathematics 106  North-HollandAkadémiai Kiadó, 1984
  * [10] Harold Fredricksen and Melvin M. Sweet  “Symmetric Sum-Free Partitions and Lower Bounds for Schur Numbers”  In _The Electronic Journal of Combinatorics_ 7, 2000  DOI: 10.37236/1510
  * [11] Ronald L. Graham, Bruce L. Rothschild and Joel H. Spencer  “Ramsey Theory”, Wiley-Interscience Series in Discrete Mathematics  John Wiley & Sons, Inc., 1990
  * [12] Brendan D. McKay and Stanisław P. Radziszowski  “The First Classical Ramsey Number for Hypergraphs is Computed”  In _Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’91  San Francisco, California, USA: Society for IndustrialApplied Mathematics, 1991, pp. 304–308  DOI: 10.5555/127787.127844
  * [13] Stanisław Radziszowski  “Small Ramsey Numbers”  In _The Electronic Journal of Combinatorics_ , 2021  DOI: 10.37236/21
  * [14] F.. Ramsey  “On a Problem of Formal Logic”  In _Proceedings of the London Mathematical Society_ s2-30.1, 1930, pp. 264–286  DOI: 10.1112/plms/s2-30.1.264
  * [15] K.. Sarkaria  “Heawood inequalities”  In _Journal of Combinatorial Theory, Series A_ 46, 1987, pp. 50–78
  * [16] K.. Sarkaria  “On coloring manifolds”  In _Illinois Journal of Mathematics_ 25.3, 1981, pp. 464–469
  * [17] K.. Sarkaria  “On neighbourly triangulations”  In _Transactions of the American Mathematical Society_ 277.1, 1983, pp. 213–239

##  Appendix A Infinitary Ramsey combinatorics

In this section we sketch the modifications needed to extend our stepping-up
lemma to infinite cardinals.

We work in Zermelo–Fraenkel set theory with choice (ZFC), and we use von
Neumann ordinals (so for integers we have $n=\llbracket n\rrbracket$, more
generally any ordinal $\alpha=\\{\beta\colon\beta<\alpha\\}$, and the cardinal
of any set $S$ is $|S|=\min\\{\alpha\text{ ordinal}\colon\alpha\simeq S\\}$).
As usual we also let $\omega=|\mathbf{N}|=\mathbf{N}$. We write ${+}$ and
${\mathbin{\dot{+}}}$ for cardinal and ordinal addition respectively.

Let $r\geq 2$ be an integer, let $\tau>0$ be an ordinal, $\kappa>0$ and
$\lambda_{\xi}\geq r+1$ (for every $\xi<\tau$) be cardinals. Extend the
relation $\nrightarrow$ previously defined for integers by calling
$X\subset\kappa$ is monochromatic in colour $\xi<\tau$ under
$f\colon[\kappa]^{r}\to\tau$ if
$f\mathbin{\texttt{\textquotedbl}}[X]^{r}\subset\\{\xi\\}$ and writing

$\kappa\nrightarrow(\lambda_{\xi})_{\xi<\tau}^{r}$

if for some $f\colon[\kappa]^{r}\to\tau$ there does not exist $\xi<\tau$ and a
subset $X\subset\kappa$ monochromatic in $\xi$ such that $|X|=\lambda_{\xi}$.

Assuming the above relation holds and $r\geq 3$, [9, chap. 24] prove

$2^{\kappa}\nrightarrow((\lambda_{\xi}+1)_{\xi<\tau},(r+2)_{2^{r}+2^{r-1}-4})^{r+1},$

which is shorthand for
$2^{\kappa}\nrightarrow(\lambda^{\prime}_{\xi}+1)^{r+1}_{\xi<\tau\mathbin{\dot{+}}(2^{r}+2^{r-1}-4)}$
where $\lambda^{\prime}_{\xi}$ is $\lambda_{\xi}$ for $\xi<\tau$ and otherwise
$r+1$. We can strengthen this result somewhat:

######  Theorem A.1.

Let $r\geq 3$ be an integer, let $\kappa>0$ be a cardinal, $\tau>0$ an ordinal
and $\lambda_{\xi}\geq r+1$ ($\xi<\tau$) cardinals.

$\displaystyle\text{If }\kappa\nrightarrow(\lambda_{\xi})_{\xi<\tau}^{r}\text{
then
}2^{\kappa}\nrightarrow((\lambda_{\xi}+1)_{\xi<\tau},\underbrace{r+2,\dots,r+2}_{\begin{subarray}{c}\eta(r)\text{
terms,}\\\ \text{each $r+2$}\end{subarray}})^{r+1},$

with the integer $\eta(r)\leq 3$ defined above in (1).

To the best of our knowledge, this improves upon known results in two cases:
when $\kappa$ and all $\lambda_{\xi}$ are finite (corresponding to our
previous finite results), and when $r=3$, $\kappa$ is infinite, $\lambda_{0}$
is infinite and singular and all other $\lambda_{\xi}$ are finite. In all
other cases, the book by [9] contains stronger statements.

###### Proof sketch.

The hypothesis means that there exists $f_{r}\colon[\kappa]^{r}\to\tau$ for
which none of the colour classes has a monochromatic set of cardinality
$\lambda_{\xi}$. Due to the bijection $2^{\kappa}\simeq|\mathcal{P}(\kappa)|$
it suffices to exhibit
$f_{r+1}\colon[\mathcal{P}(\kappa)]^{r+1}\to\tau\mathbin{\dot{+}}\eta(r)$ for
which none of the first $\tau$ colour classes has a monochromatic set of
cardinality $\lambda_{\xi}+1$, and none of the subsequent ones has a
monochromatic set of cardinality $r+2$.

To do so define the first discrepancy between two sets of ordinals $x$ and $y$
with $x\neq y$ as

$\displaystyle s(x,y)=\min((x\cup y)\setminus(x\cap y)),$

which is the well-defined minimum of a non-empty set of ordinals. From there
if $\sigma\subset\mathcal{P}(\kappa)$ is a set of subsets of $\kappa$ and
$|\sigma|\geq 2$ we define its first splitting index as
$s(\sigma)=\min(s\mathbin{\texttt{\textquotedbl}}[\sigma]^{2})$, a well-
defined ordinal in $\kappa$.

This gives _essentially_ the same partition as before with
$\sigma=(\sigma_{0}\mathbin{\mid}\sigma_{1})$ where
$\sigma_{0}=\\{S\in\sigma\colon s(\sigma)\notin S\\}$ and
$\sigma_{1}=\sigma\setminus\sigma_{0}$. It admittedly differs from the
previous finitary construction in a minor way, as we now compare _least_
significant bits, but when restricted to finite sets it is functionally
equivalent. This small modification is necessary; using maxima in the
definitions above would make these quantities ill-defined.

A caterpillar is a set of any size without a four-subset of the form
$(L\mathbin{\mid}R)$ with $|L|=|R|=2$. If
$\sigma=(\sigma_{0}\mathbin{\mid}\sigma_{1})$ is a caterpillar then at least
one of $\sigma_{0}$ and $\sigma_{1}$ is a singleton.

For any caterpillar $T\subset\mathcal{P}(\kappa)$ let
$\delta(T)=\\{s(x,y)\colon\\{x,y\\}\in[T]^{2}\\}=s\mathbin{\texttt{\textquotedbl}}[T]^{2}$.

We (still) have
$[\delta(T)]^{r}=\delta\mathbin{\texttt{\textquotedbl}}[T]^{r+1}$, extending
Observation 2.4. This infinite case is not harder to prove since

$[\delta(T)]^{r}=\bigcup_{\begin{subarray}{c}Y\subset T\\\
|Y|<\omega\end{subarray}}[\delta(Y)]^{r}=\bigcup_{\begin{subarray}{c}Y\subset
T\\\
|Y|<\omega\end{subarray}}\delta\mathbin{\texttt{\textquotedbl}}[Y]^{r+1}=\delta\mathbin{\texttt{\textquotedbl}}\Big{(}\bigcup_{\begin{subarray}{c}Y\subset
T\\\
|Y|<\omega\end{subarray}}{[Y]^{r+1}}\Big{)}=\delta\mathbin{\texttt{\textquotedbl}}[T]^{r+1}.$

Similarly, the equality $|T|=|\delta(T)|+1$ still holds for every caterpillar
$T$ by transfinite induction.

We re-use the same colouring scheme. Let $S\in[\mathcal{P}(\kappa)]^{r+1}$. If
$S\in\mathcal{C}$ then $\delta(S)\in[\kappa]^{r}$, and we let
$f_{r+1}(S)=f_{r}(\delta(S))<\tau$. If $S\notin\mathcal{C}$, then $S$, being
finite, has a type, so we simply colour it as before.

As before, let us check the validity of this colouring only for odd $r$.

Let $X\subset\mathcal{P}(\kappa)$ be monochromatic in colour $\xi$ under
$f_{r+1}$. We will show that $|X|\leq\lambda_{\xi}$ (if $\xi<\tau$) or
$|X|\leq r+1$ (for $\xi\in\\{\tau,\tau+1\\}$). As $r+1\leq\lambda_{\xi}$ we
may already assume $|X|>r+1$.

First consider the case when $X\in\mathcal{C}$. Then
$[X]^{r+1}\subset\mathcal{C}$, and thus
$\\{\xi\\}=f_{r+1}\mathbin{\texttt{\textquotedbl}}[X]^{r+1}=f_{r}\mathbin{\texttt{\textquotedbl}}(\delta\mathbin{\texttt{\textquotedbl}}[X]^{r+1})<\tau$,
so we have to show $|X|\leq\lambda_{\xi}$.

The set $\delta(X)\subset\kappa$ is monochromatic in colour $\xi$ under
$f_{r}$, as

$f_{r}\mathbin{\texttt{\textquotedbl}}[\delta(X)]^{r}=f_{r}\mathbin{\texttt{\textquotedbl}}(\delta\mathbin{\texttt{\textquotedbl}}[X]^{r+1})=\\{\xi\\}.$

This fact implies that $|X|=|\delta(X)|+1<\lambda_{\xi}+1$.

The other case to consider is when $X\notin\mathcal{C}$. We show that then
$|X|\leq r+1$ regardless of $i$. (Recall that $r+1\leq s_{i}$ always.) Suppose
to the contrary that $|X|\geq r+2$, and we can assume $|X|=r+2$. Now
everything is finite, and works as before. ∎

##  Appendix B Lower bounds on $r_{k}(3;2)$

Here is the justification for the lower bounds on $r_{k}(3;2)$ used in the
proof of Corollary 1.3.

######  Theorem B.1.

There is an absolute constant $C>0$ such that for all $k\geq 2$ we have

$\lceil C\cdot 1073^{k/6}\rceil\nrightarrow(3)_{k}^{2}.$

###### Proof.

A set of integers $S$ is sum-free if $(S+S)\cap S$ is empty. The Schur number
$s_{k}$ is the largest number for which $\\{1,2,\dots,s_{k}\\}$ has a
partition into $k$ sum-free subsets. By Schur’s Ramsey theorem,
$s_{k}\nrightarrow(3)_{k}^{2}$ (see e.g. [11, chap. 4.5]). For any fixed
positive integer $l$ and $k\geq l$ we have [3]

$s_{k}\geq C_{l}\cdot(2s_{l}+1)^{k/l}.$

Finally, $s_{6}\geq 536$ [10]. ∎