# On-device Real-time Hand Gesture Recognition

George Sung Kanstantsin Sokal Esha Uboweja Valentin Bazarevsky Jonathan
Baccash
Eduard Gabriel Bazavan Chuo-Ling Chang Matthias Grundmann
Google Research
1600 Amphitheatre Pkwy, Mountain View, CA 94043, USA
{gsung, kanstantsin, eshauboweja, bazarevsky, jbaccash, egbazavan, chuoling,
<EMAIL_ADDRESS>

###### Abstract

We present an on-device real-time hand gesture recognition (HGR) system, which
detects a set of predefined static gestures from a single RGB camera. The
system consists of two parts: a hand skeleton tracker and a gesture
classifier. We use MediaPipe Hands [14, 2] as the basis of the hand skeleton
tracker, improve the keypoint accuracy, and add the estimation of 3D keypoints
in a world metric space. We create two different gesture classifiers, one
based on heuristics and the other using neural networks (NN).

##  1 Introduction

Hand gesture recognition (HGR) is a natural and intuitive method for human-
computer interaction (HCI), and has been an active research area [11, 10]. A
wide variety of input devices and techniques have been investigated, and
skeleton-based HGR is a popular choice due to its robustness to background and
light variations [7, 6]. Many skeleton-based HGR systems rely on depth
sensors, such as RGBD cameras, which are not nearly as common as RGB cameras
on mobile devices. Our HGR, on the other hand, requires only a single RGB
camera. It does so by first predicting 3D skeleton keypoints from a camera
image, then running a gesture classifier on the keypoints.

We design two gesture classifiers with different use cases in mind. The
heuristics-based classifier is easier to create and extend, without the need
for training data, and more intuitive to develop and troubleshoot. The NN-
based classifier is more accurate and precise, especially for borderline
cases. It’s also more forgiving of errors in skeleton keypoints.

Our HGR runs real-time at 30fps on mainstream mobile devices.

##  2 Architecture

Our HGR consists of two parts: a hand skeleton tracker improved from MediaPipe
Hands and a gesture classifier, as shown on Figure 1. The two-step approach
has a few advantages:

  * •

Reduced engineering effort by leveraging the hand tracker which is already
real-time, robust, and fair [4].

  * •

Simpler gesture classifier design which processes skeleton keypoints instead
of raw pixels.

  * •

Optimized complexity by running the gesture classifier only when hands are
tracked.

Figure 1: Our hand gesture recognition system

###  2.1 Hand Skeleton Tracker

Both our gesture classifiers operate on a keypoint level (not with RGB data),
therefore accurate hand keypoint estimation is a key prerequisite for gesture
classification. As a basis for our gesture recognition pipeline, we improve
MediaPipe Hands [2] by training with a new sophisticated hand poses data (like
American Sign Language). Analysis of various gestures indicates that robust
estimation of hand rotation angle and normalization distance is key to an
accurate hand tracker. The original hand rotation and scale estimation is
based on the 2D vector from the wrist to the middle finger knuckle. For
various cases (like frontal view) such normalization becomes very unstable as
the normalization distance approaches zero, which results in a significant
degradation in tracking quality. To overcome this problem, we introduce a new
algorithm similar to the approach taken by BlazePose [5].

Figure 2: Hands rotation angle derived from the sum of two vectors: index to
pinky base knuckle (in green) and middle base knuckle to wrist (in red).

For our case, we define two virtual keypoints to describe hand center, scale
and rotation angle: a center keypoint and an alignment keypoint. The center
keypoint is estimated as the average of the index, middle and pinky knuckles.
The alignment keypoint location is estimated so it forms the rotation/scale
vector with the center keypoint. The rotation angle is estimated from a sum of
two vectors: from the middle base knuckle to the wrist, and from the index to
the pinky base knuckle. As the component vectors tend to be orthogonal in the
majority of cases; the resulting sum vector changes smoothly for any hand
pose, and never degrades to zero, as shown on Figure 2. This increases overall
hand tracking quality for frontal hand cases. The scalar value of the
alignment vector is estimated as the distance from the center keypoint to the
farthest knuckle of the same hand. The new rotation and scale normalization
results in a significant quality boost for the whole hand pose estimation
pipeline: 71.3 mAP vs 66.5 mAP (for the original MediaPipe Hands [2] pipeline)
on our validation dataset with complex ASL hand poses.

Accurate hand pose estimation in the 3D space is a vital component for both
angle based and few-shot learning gesture classification. It minimizes the
ambiguity among projections of the same hand pose from different observer
positions in space, and allows the gesture classification to be invariant to
rotation. Therefore, in addition to predicting the hand pose in the screen
“pixel” space, we also estimate the pose in a world metric space relatively to
the hand wrist. To obtain a 3D hand pose ground truth in a metric space, we
fit our 2D hand annotation with a statistical and highly realistic GHUM [12,
13] hand model as shown in Figure 3. Due to the nature of perspective
projection, objects of different sizes may have the same projection on the
image plane: two objects with the same shape (bigger and smaller) will have
the same projection if placed respectively further and closer to the camera.
Therefore we have to make the following assumptions when we perform the hand
fitting from 2D keypoints: human hands have minor variations in size, those
variations are always reflected in hand shapes, and thus covered by the
statistical GHUM hand model. For images with unknown camera intrinsic
parameters, we assume the focal length is the maximum of the image width and
height, and the optical center is the center of the image. Since both the
model training and inference operate on a cropped image, we normalize the
absolute world coordinates such that the origin is at the middle finger
knuckle, while the scale remains the same. We also normalize 3D coordinates in
a roll plane using virtual keypoints to be consistent with input image
transformations.

Figure 3: Sample images with overlaid 2D annotations and the corresponding
GHUM [12] hand models fitted and rendered on top.

Overall, our hand tracking model achieves a mean average prediction error of
1.5cm, and provides 21 hand keypoints in a metric 3D space to the gesture
classfier.

###  2.2 Heuristics Gesture Classifier

Based on the hand skeleton tracker, we build a single-shot, heuristics-based
classifier for a small set of static gestures. We start with the simple
gesture classification approach described in [14], which first derives a set
of angles between various 2D hand keypoints, then applies thresholds to the
derived angles to define a discrete state for each finger (e.g. bent or
straight), and finally defines a static gesture as a logic expression based on
the finger states. To get a more accurate set of underlying angles, we replace
features based on the 2D hand keypoints with features based on the 3D world
metric hand keypoints. In order to de-correlate the gesture classifier
features and make manual threshold picking easier, we distinguish between
extrinsic and intrinsic features with respect to the palm pose in the 3D world
metric space during the preprocessing stage:

  * •

The extrinsic features are composed of palm pose components such as rotation,
scale and translation. For classification purposes, we only use the rotation
pose component of the palm represented by its three Euler angles.

  * •

The intrinsic features are angles between various hand keypoints. For
classification purposes, we derive a single feature angle for each finger with
a goal of thresholding them to define a discrete state (e.g. fully bent, fully
straight or neither). In accordance with the underlying hand skeleton
topology, each finger is represented by a base joint keypoint, two
intermediate joint keypoints and a tip keypoint. To define an individual
finger feature angle, we first introduce a 3D polygonal chain: starting from
the wrist keypoint, to the finger’s base joint keypoint, the first
intermediate joint keypoint, the second intermediate joint keypoint, and
finishing at the tip keypoint. Then, we define the feature angle as the
maximum angle between the first chain segment and each of the remaining chain
segments. Additionally, we derive a feature angle for each adjacent pair of
fingers with the same goal of thresholding them to define a discrete state
(e.g. fingers crossed, apart or neither).

Figure 4: 3D hand keypoints decoupled from the palm pose during the
preprocessing stage. The blue hand skeleton is based on the 2D hand keypoints.
The green hand skeleton is based on the preprocessed 3D hand keypoints.

As shown on Figure 4, removing the influence of the extrinsic features from
the the intrinsic features produces a consistent 3D hand keypoint set for a
fixed hand shape configuration, regardless of its position on the input
frames. In turn, this significantly de-correlates features and makes it
manageable to manually pick thresholds on a larger feature set in order to
define a more complex static gesture.

As the final stage of the heuristics-based classifier, we establish a system
of 6 gesture definitions based on the features derived from the pre-processed
3D world metric hand keypoints. Figure 5 showcases the supported gestures.
This particular gesture set is chosen so that it covers some of the most
recognizable and common static hand gestures.

Figure 5: Visualization of gestures supported by the heuristic-based
classifier. Left-to-right: OpenPalm, Victory, ClosedFist, PointingUp, ThumbUp,
ThumbDown.

To evaluate our approach, we collect and annotate an in-house gesture dataset.
The dataset contains 1882 short video clips that cover various angles and
lighting conditions for 21 static hand gestures (for the full list of
gestures, please see Appendix A). The dataset contains all 6 gestures
supported by the heuristics-based classifier (see Figure 5) and those are used
as positive samples. The remaining 15 gestures are used as negative samples.
The presence of a diverse negative sample collection allows us to evaluate how
often the classifier recognizes an unknown gesture as a known one. The
limitation of this dataset is that it’s collected from only 18 users with
limited variation in background. The classifier achieves 0.86% false positive
rate and 44.4% recall rate on the dataset.

###  2.3 NN Gesture Classifier

The dataset used in Section 2.2 is for evaluation only and too small for
training NN models. We collect and mine another in-house dataset containing
$7307$ images from $6478$ users, representing a rich variety of hand shapes of
both gestures and non-gestures in the wild. In addition to regular positive
samples we collect easy and hard Negative samples. Please see Figure 6 for
some example images.

We train an NN classifier to distinguish among six static hand gestures,
namely, OpenPalm, ClosedFist, PointingUp, Victory, ThumbUp, ThumbDown and a
background Negative class. The NN model consists of $3$ fully connected layers
of $50$ neurons each. The model inputs are the intrinsic and extrinsic
features computed in Section 2.2. We use focal loss [8] to deal with the class
imbalance, where there are a lot more negative samples than positive samples
in our dataset.

The NN classifier achieves an average recall rate of $87.9\%$ across the $6$
static gesture classes at a false positive rate of $1\%$.

Figure 6: Some examples of true positive samples for gesture classes, easy
samples for Negative hand shapes and subtle variations of hand shapes that
should not be confused with the gesture class.

##  3 MediaPipe Implementation

The proposed HGR system is implemented using the open source MediaPipe
framework [1]. The system adds to MediaPipe Hands, primarily consisting of a
hand-detection and a hand-keypoint component [14, 2], an additional gesture-
classification component as discussed in Section 2.2 and 2.3.

In many applications, such as remote control, the user gestures only once in a
while but the HGR is always running in the background. In order to reduce
average computation requirement and maintain real-time performance across a
wide range of devices, the HGR system hand detection is configured to run only
as needed, capped at a maximum frequency lower than the frequency of hand
keypoint generation and gesture classification, by utilizing the flow-control
and stream-synchronization support in MediaPipe [9] similar to [14]. When
there’s no hand in the camera view, the HGR runs hand detection at a lower
frequency to save computation and power. As soon as a hand is detected, it’s
tracked at a higher frequency for better accuracy and temporal resolution.
Furthermore, GPU acceleration is heavily exploited end-to-end, covering tasks
like ML model inference as well as image and tensor processing, via
OpenGL/OpenCL/Metal on mobile devices and WebGL locally in Web browsers
(similar to the Web ML effort enabling background blur/replace in Google Meet
[3]).

##  4 Applications

Our HGR can be used as an HCI mechanism for various applications, such as a
virtual touchscreen for desktop computers, sending visual commands for robots,
a controller for virtual reality gaming systems, and a remote control for
large screen displays [11].

## References

  * [1] MediaPipe.  https://mediapipe.dev/, 2019.
  * [2] MediaPipe Hands.  https://solutions.mediapipe.dev/hands, 2019.
  * [3] Background Features in Google Meet, Powered by Web ML.  https://ai.googleblog.com/2020/10/background-features-in-google-meet.html, 2020\.
  * [4] MediaPipe Hands Model Card.  https://mediapipe.page.link/handmc, 2020.
  * [5] Valentin Bazarevsky, Ivan Grishchenko, Karthik Raveendran, Tyler Zhu, Fan Zhang, and Matthias Grundmann.  BlazePose: On-device Real-time Body Pose Tracking, 2020.
  * [6] Quentin De Smedt, Hazem Wannous, and Jean-Philippe Vandeborre.  Skeleton-based dynamic hand gesture recognition.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 1–9, 2016.
  * [7] Guillaume Devineau, Fabien Moutarde, Wang Xi, and Jie Yang.  Deep learning for hand gesture recognition on skeletal data.  In 2018 13th IEEE International Conference on Automatic Face & Gesture Recognition (FG 2018), pages 106–113. IEEE, 2018.
  * [8] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In Proceedings of the IEEE international conference on computer vision, pages 2980–2988, 2017.
  * [9] Camillo Lugaresi, Jiuqiang Tang, Hadon Nash, Chris McClanahan, Esha Uboweja, Michael Hays, Fan Zhang, Chuo-Ling Chang, Ming Guang Yong, Juhyun Lee, Wan-Teh Chang, Wei Hua, Manfred Georg, and Matthias Grundmann.  MediaPipe: A Framework for Building Perception Pipelines.  In CVPR Workshop on Computer Vision for AR/VR, 2019.
  * [10] Munir Oudah, Ali Al-Naji, and Javaan Chahl.  Hand gesture recognition based on computer vision: a review of techniques.  journal of Imaging, 6(8):73, 2020.
  * [11] Siddharth S Rautaray and Anupam Agrawal.  Vision based hand gesture recognition for human computer interaction: a survey.  Artificial intelligence review, 43(1):1–54, 2015.
  * [12] Hongyi Xu, Eduard Gabriel Bazavan, Andrei Zanfir, William T Freeman, Rahul Sukthankar, and Cristian Sminchisescu.  GHUM & GHUML: Generative 3D Human Shape and Articulated Pose Models.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6184–6193, 2020.
  * [13] Andrei Zanfir, Eduard Gabriel Bazavan, Hongyi Xu, William T. Freeman, Rahul Sukthankar, and Cristian Sminchisescu.  Weakly Supervised 3D Human Pose and Shape Reconstruction with Normalizing Flows.  In Computer Vision – ECCV 2020, pages 465–481, 2020.
  * [14] Fan Zhang, Valentin Bazarevsky, Andrey Vakunov, George Sung, Chuo-Ling Chang, Matthias Grundmann, and Andrei Tkachenka.  MediaPipe Hands: On-device Real-time Hand Tracking.  In CVPR Workshop on Computer Vision for Augmented and Virtual Reality, Seattle, WA, 2020.

## Appendix A. In-house static gesture dataset: gesture code names

  1. 1.

OpenPalm

  2. 2.

Victory

  3. 3.

ClosedFist

  4. 4.

PointingUp

  5. 5.

ThumbUp

  6. 6.

ThumbDown

  7. 7.

OK

  8. 8.

CallMe

  9. 9.

IndexMiddlePointingUp

  10. 10.

Three

  11. 11.

Four

  12. 12.

ILoveYou

  13. 13.

FingerHeart

  14. 14.

HandHeart

  15. 15.

IndexMiddlePointingUpWithClosedThumb

  16. 16.

IndexMiddlePointingUpWithOpenThumb

  17. 17.

IndexPointingToCamera

  18. 18.

Loser

  19. 19.

PinchedFingers

  20. 20.

VulcanSalute

  21. 21.

SignOfTheHorns


# New Stepping-Up Constructions for Multicoloured Hypergraphs

Quentin Dubroff  Department of Mathematics, Rutgers University, Piscataway,
NJ, 08854, USA<EMAIL_ADDRESS>,  António Girão  Mathematical
Institute, University of Oxford, Oxford OX2 6GG, UK
<EMAIL_ADDRESS>,  Eoin Hurley  Institute for Computer Science,
Heidelberg University, 69120 Heidelberg, Germany<EMAIL_ADDRESS>heidelberg.de and  Corrine Yap  Department of Mathematics, Rutgers University,
Piscataway, NJ, 08854, USA<EMAIL_ADDRESS>
###### Abstract.

Generalizing the classical Ramsey numbers, $r_{k}(t;q,p)$ is the smallest
integer $n$ such that every $q$-colouring of the $k$-sets on $n$ vertices
contains a set of $t$ vertices spanning fewer than $p$ colours. We prove the
first tower-type lower bounds on these numbers via two new stepping-up
constructions, both variants of the original stepping-up lemma due to Erdős
and Hajnal. We use these to resolve a problem of Conlon, Fox, and Rödl. More
precisely, we construct a family of hypergraphs with arbitrarily large tower
height separation between their $2$-colour and $q$-colour Ramsey numbers.

##  1\. Introduction

We denote by $r_{k}(G;q,p)$, for $q\geq p$, the smallest integer $n$ such that
in every $q$-colouring of $K_{n}^{(k)}$, there is a copy of the hypergraph $G$
whose edges span fewer than $p$ colours. For simplicity when $G$ is
$K_{t}^{(k)}$, we write $r_{k}(G;q,p)=r_{k}(t;q,p)$. Observe that when
$q=p=2$, $r_{k}(G;2,2)$ and $r_{k}(t;2,2)$ coincide with the classical Ramsey
numbers $r_{k}(G)$ and $r_{k}(t)$, and we will denote them as such. One of the
most central open problems in Ramsey theory is determining the growth rate of
the 3-uniform Ramsey number $r_{3}(t)$. A famous result of Erdős, Hajnal, and
Rado [7] from the 60’s shows that there exist constants $c$ and $c^{\prime}$
such that

$2^{ct^{2}}\leq r_{3}(t)\leq 2^{2^{c^{\prime}t}}.$

Note that the upper bound is essentially exponential in the lower bound, and
that despite much attention, this remains the state of the art. Perhaps
surprisingly, if we allow four colours instead of two, Erdős and Hajnal (see
e.g. [9]) showed that the double exponential upper bound is essentially
correct, i.e. there is a $c>0$ such that $r_{3}(t;4,2)\geq 2^{2^{ct}}$. More
recently Conlon, Fox, and Sudakov [4] proved a super-exponential bound with
three colours, that is, that there exists $c>0$ such that $r_{3}(t;3,2)\geq
2^{t^{c\log t}}$. Erdős conjectured that the double exponential bound should
hold without using extra colours, offering $500 dollars for a proof that
$r_{3}(t)\geq 2^{2^{ct}}$ for some constant $c>0$. Raising the stakes for this
conjecture is the ingenious stepping-up construction of Erdős and Hajnal (see
e.g. [9]), which shows that for all $q$ and $k\geq 3$,

(1) $r_{k+1}(2t+k-4;q,2)>2^{r_{k}(t;q,2)-1}.$

For the past 60 years, we have used (1) to stack our lower bounds for
$r_{k}(t;q,2)$ upon that of $r_{3}(t;q,2)$, yielding that $r_{k}(t)\geq
T_{k-1}(ct^{2})$, where _$T_{k}(x)$ , the tower of height $k$ in $x$,_ is
defined by $T_{1}(x)=x,\,T_{i+1}(x)=2^{T_{i}(x)}$. The corresponding upper
bounds of $r_{k}(t)\leq T_{k}(O(t))$ (see [5, 6, 7]) are once again
exponential in the lower bounds, and thus a positive resolution of Erdős’s
Conjecture would be the decisive step in showing that
$r_{k}(t)=T_{k}(\Theta(t))$ for all $k\geq 3$.

Due to the lack of progress on this central conjecture, it is natural to try
to understand just how significant a role the number of colours can play in
hypergraph Ramsey numbers and whether or not there could really be such a
large difference between $r_{3}(t;2,2)$ and $r_{3}(t;4,2)$. To this end,
Conlon, Fox, and Rödl [3] asked if there exist an integer $q$ and number $c>0$
such that $r_{3}(t;q,3)\geq 2^{2^{ct}}$. This question gets to the heart of
our ignorance of $r_{k}(t;q,p)$ for any $k,q,p\geq 3$, which is caused by the
absence of a stepping-up construction for any $p>2$. A standard application of
the first moment method (see e.g. [1]) shows that for any $k,q\in\mathbb{N}$
there exists $c>0$ such that $r_{k}(t;q,q)\geq 2^{ct^{k-1}}$ for all
$t\in\mathbb{N}$. The only nontrivial improvement to date on this bound has
been made by Mubayi and Suk [13] who proved there exists $c>0$ such that for
$q\geq 9$, $r_{3}(t;q,3)\geq 2^{t^{2+cq}}$ for $t\in\mathbb{N}$ sufficiently
large; for all other values of $k,q,p\geq 3$, the random construction is
essentially the state of the art. Our knowledge (or lack thereof) is thus
summarised by the following bounds for $k,q,p\geq 3$ and sufficiently large
$t\in\mathbb{N}$,

$2^{t^{c}}\leq r_{k}(t;q,p)\leq T_{k}(O(t)),$

where $c\geq 1$ is allowed to depend on $k,q$ and $p$. Note that in this case
our upper bounds are a staggering tower of height $k-2$ in the lower bounds.
Our first contribution is the development of two new stepping-up constructions
captured by Theorems 1.1 and 1.4. Both borrow key ideas from the original, and
each of them is relevant for different values of $k,q$ and $p$. They yield the
first tower-type results of their kind.

######  Theorem 1.1.

Let $k,q,p\geq 3$ be such that $p\leq C_{k}$, the $k^{\text{th}}$ Catalan
number. There exist $c\geq 1$ and $t_{0}$ such that for all $t>t_{0}$

$r_{k+1}(t^{c};q,p-2)>2^{r_{k}(t;q,p-2)-1},\quad
r_{k+1}(t^{c};2q+p,p)>2^{r_{k}(t;q,p)-1}.$

Unfortunately, this does not allow us to answer the question of Conlon, Fox,
and Rödl on $r_{3}(t;q,3)$, since $C_{2}=2$, but already for $k\geq 4$ we have
the following two corollaries:

######  Corollary 1.2.

For all $k\geq 4$, there is $q\in\mathbb{N}$ and $c>0$ such that
$r_{k}(t;q,5)\geq T_{k-1}(t^{c})$.

######  Corollary 1.3.

For all $k\geq 4$, there is $c>0$ such that $r_{k}(t;3,3)\geq T_{k-1}(t^{c})$.

Observe that by the second corollary the growth rate of $r_{k}(t;3,3)$ matches
the current best lower bounds for $r_{k}(t;2,2)$ up to a polynomial in $t$.
The reason we have an absolute constant $c$ in the exponent is due to the use
of an Erdős-Hajnal type result on sequences (see Section 2). Our second
stepping-up construction yields the following.

######  Theorem 1.4.

Let $k,q,p\geq 3$ be such that $p\leq k!$. There exist $c\geq 1$ and $t_{0}$
such that for all $t>t_{0}$

$r_{2k}(t^{c};qp,p)>2^{r_{k}(t;q,p)-1}.$

Note that the growth rate in $k$ which is implied by Theorem 1.4
(approximately a tower of height $\log_{2}k$) is much less than that of
Theorem 1.1 because we can only step up at the cost of doubling the uniformity
size. Despite this, it allow us to answer a question of Conlon, Fox, and Rödl
which relates to the aforementioned conjecture of Erdős. Recall the conjecture
claimed that the Ramsey numbers of $3$-uniform hypergraphs with $2$ colours
should behave as a double exponential function; and that we know that this is
the case when we allow four colours. One argument in favour of the conjecture
is that the reliance on extra colours to prove a double exponential lower
bound may be a technical limitation of the stepping-up construction. This is
challenged by a stunning discovery of Conlon, Fox, and Rödl [3] who exhibited
an infinite family of $3$-uniform hypergraphs called hedgehogs, whose Ramsey
numbers display strong dependence on the number of colours. Namely, they
showed that $2$-colour Ramsey number of hedgehogs is polynomial in their
order, while the $4$-colour Ramsey number is at least exponential. To
understand just how significant a role the number of colours could play they
asked the following:

######  Question 1.5.

For any integer $h\geq 3$, do there exist integers $k$ and $q$ and a family of
$k$-uniform hypergraphs for which the $2$-colour Ramsey number grows as a
polynomial in the number of vertices, while the $q$-colour Ramsey number grows
as a tower of height $h$?

Our second contribution is to answer this in the affirmative. Define the _$k$
-uniform balanced hedgehog_ $\hat{H}^{(k)}_{t}$ with body of order $t$ to be
the graph constructed as follows: take a set $S$ of $t$ vertices, called the
body, and for each subset $X\subset S$ of order $\lceil\frac{k}{2}\rceil$ add
a $k$-edge $e$ with $e\cap S=X$ such that for all $e,f\in
E(\hat{H}^{(k)}_{t})$ we have $e\cap f\subset S$. The hedgehog $H_{t}^{(k)}$
as defined by Conlon, Fox, and Rödl differs only in that they consider every
$X\subset S$ of order $k-1$ rather than $\lceil\frac{k}{2}\rceil$. We observe
that for $k=3$ both definitions coincide. When the uniformity is clear from
the context we shall drop the superscript.

######  Theorem 1.6.

There exist $c>0$ and $q:\mathbb{N}\rightarrow\mathbb{N}$ such that for all
$k\in\mathbb{N}$ and sufficiently large $t$, we have

  1. (a)

$r_{2k+1}(\hat{H}_{t};2,2)\leq t^{k+3}$, and

  2. (b)

$r_{2k+1}(\hat{H}_{t};q(k),2)\geq T_{\lfloor c\log_{2}\log_{2}k\rfloor}(t)$ .

The following result connects the problem of avoiding monochromatic balanced
hedgehogs to that of avoiding cliques that span few colours. It is a
straightforward adaptation of ideas from Conlon, Fox, and Rödl [3].

######  Lemma 1.7.

Given $k,q,t\in\mathbb{N}$, let $p={2k+1\choose k+1}$ and
$q^{\prime}={q\choose p}$. Then

$r_{2k+1}(\hat{H}_{t};q^{\prime},2)>r_{k+1}\mathopen{}\mathclose{{}\left(t;q,p+1}\right)-1.$

Using this result along with Theorem 1.4 yields the lower bound in Theorem
1.6, b. It is natural to ask whether one can combine the growth rate in $k$
given by Theorem 1.1 with the ability to impose as many colours as in Theorem
1.4. Unfortunately, the condition $p\leq C_{k}$ prevents us from using Theorem
1.1 as the right-hand side because $C_{k}=\frac{1}{k+1}{2k\choose
k}<{2k+1\choose k+1}$. This is tantalisingly close, if not a little curious,
as the dependence on $C_{k}$ comes from our exact solution to a subsequence
avoidance problem (Corollary 2.4). We show that $C_{k}$ presents a natural
barrier in this endeavour. This barrier is made concrete by some new and tight
results on the Ramsey theory of sequences, including an Erdős-Hajnal-type
result in Section 2.

The outline of the paper is as follows: in Section 2 we introduce and prove
results on the Ramsey theory of sequences; in Section 3 we use these to prove
our stepping up constructions, namely, Theorem 1.1 and 1.4; and in Section 4
we prove our hedgehog-related results, including Theorem 1.6 and Lemma 1.7,
and provide a construction of a degenerate hypergraph that relates to the
Burr-Erdős Conjecture. To finish, we pose some questions and problems
highlighted by our results.

##  2\. Ramsey Theory of Sequences

Let $V=\\{0,1\\}^{m}$ and given vectors $v,w\in V$, define

$\delta(v,w)=\max\\{i:v_{i}\neq w_{i}\\}.$

We say $v<w$ if $v_{\delta}<w_{\delta}$. For every set of vertices
$v_{1}<v_{2}<\dots<v_{k+1}$ in $V$ there is a corresponding sequence
$(\delta_{1},\delta_{2},\ldots,\delta_{k})$ given by
$\delta_{i}=\delta(v_{i},v_{i+1})$. In this section, we introduce some
definitions that will be useful in order to analyse the structure of these
$\delta$-sequences.

We say a sequence $S=(a_{1},a_{2},\dots,a_{m})$ is homogeneous if $a_{1}\leq
a_{2}\leq\dots\leq a_{m}$ or $a_{1}\geq a_{2}\geq\dots\geq a_{m}$. Two
sequences $(a_{1},a_{2},\ldots,a_{t})$ and $(b_{1},b_{2},\ldots,b_{t})$ have
the same pattern if the relative ordering of every pair of elements is the
same, i.e. $a_{i}>a_{j}$, $a_{i}=a_{j}$, or $a_{i}<a_{j}$ if and only if
$b_{i}>b_{j}$, $b_{i}=b_{j}$, or $b_{i}<b_{j}$ respectively for all $1\leq
i<j\leq t$. A _pattern_ is then the equivalence class of sequences with
respect to this relative ordering. Given sequences $S$ and $P$, we say $S$
contains the pattern $P$ if we can find a subsequence of $S$ which has the
same pattern as $P$; otherwise, we say $S$ avoids $P$. A pattern is a
permutation pattern if there is a permutation in the equivalence class, and we
often use this permutation as a representative for the pattern.

With the aforementioned applications to hypergraph Ramsey theory in mind, we
introduce “max-induced” subsequences. We say
$(a_{i_{1}},a_{i_{2}},\ldots,a_{i_{t}})$ with $i_{1}<i_{2}<\dots<i_{t}$ is a
max-induced subsequence of $(a_{1},a_{2},\ldots,a_{m})$ if the maximum of
$(a_{i_{j}},a_{i_{j}+1},\ldots,a_{i_{j+1}})$ is attained at $a_{i_{j}}$ or
$a_{i_{j+1}}$, i.e. at the left or right extreme, for all $1\leq j<t$. We say
a sequence $S$ contains a max-induced pattern $P$ if there is a max-induced
subsequence of $S$ which has pattern $P$, and a family of sequences
$\mathcal{F}$ has the max-induced Erdős-Hajnal property with exponent
$c(\mathcal{F})$ if every sequence $S$ that avoids all members of
$\mathcal{F}$ as a max-induced subsequence has a homogeneous max-induced
subsequence of order $|S|^{c(\mathcal{F})}$, where $|S|$ denotes the length of
the sequence. We are able to characterize the families with this property.

The following fact, whose short proof can be found in Section 3, relates the
max-induced property to our original motivation:

######  Claim 2.1.

Suppose $v_{1}<v_{2}<\dots<v_{\ell+1}$ are vectors in $\\{0,1\\}^{m}$ and let
$\delta_{i}=\delta(v_{i},v_{i+1})$. If
$(\delta_{i_{1}},\ldots,\delta_{i_{k}})$ is a max-induced subsequence of
$(\delta_{1},\ldots,\delta_{\ell})$, then there are
$v_{j_{1}},\ldots,v_{j_{k+1}}$ such that
$\delta(v_{j_{s}},v_{j_{s+1}})=\delta_{i_{s}}$ for each $s\in[k]$.

Define an interval in a sequence to be a subsequence of consecutive elements.
We say a pattern $P=(a_{1},a_{2},\ldots,a_{n})$ has the left property if the
following holds: for each interval $I\subset P$ with maximum element $a_{m}$,
all elements to the left of $a_{m}$ in $I$ — meaning the elements $a_{i}\in I$
such that $i<m$ — are greater than or equal to all elements to the right of
$a_{m}$ in $I$. We similarly say a pattern has the right property if within
each interval, every element to the left of the maximum is smaller than every
element to the right of the maximum. The following theorem is our core result
on max-induced patterns:

######  Theorem 2.2.

A finite family of patterns $\mathcal{F}$ has the max-induced Erdős-Hajnal
property if and only if $\mathcal{F}$ contains a permutation pattern with the
left property and a permutation pattern with the right property.

Observe that if a permutation has both the left and the right property, it
must be decreasing up to some element and increasing for the rest of the
permutation. We say such a permutation has a unique local minimum, and we
immediately get the following corollary of Theorem 2.2:

######  Corollary 2.3.

A permutation $P$ has the max-induced Erdős-Hajnal property (with exponent
$c(P)=16^{-|P|}$) if and only if it has a unique local minimum.

An old result of Shelah [14] states that any graph which does not have large
cliques or large independent sets must contain exponentially many non-
isomorphic induced subgraphs. Taking inspiration from this, we may ask: given
$k\in\mathbb{N}$, what is the largest integer $f(k)$ for which there is
$\varepsilon>0$ such that every sequence of length $n$ either contains at
least $f(k)$ distinct max-induced patterns on $k$ elements or a max-induced
homogeneous subsequence of length $n^{\varepsilon}$? Theorem 2.2 allows us to
answer this question exactly and is the origin of the Catalan number that
appears in Theorem 1.1.

######  Corollary 2.4.

The value of $f(k)$ is the number of permutations of $[k]$ with the right
property (equivalently, the left property), which is equal to the Catalan
number $C_{k}$.

Up to this point, our sequence results do not use a useful fact about the
$\delta$-sequences which features often in stepping-up. A sequence
$(a_{1},a_{2},\ldots,a_{k})$ has the _unique maximum property_ if for any
interval $I$, $|\\{i\in I:a_{i}=\max(a_{i})_{i\in I}\\}|=1$. We capitalize on
this useful property in Lemma 2.5, which studies a second notion of
subsequence that is used in our proof of Theorem 1.4. Call
$(a_{i_{1}},a_{i_{2}},\ldots,a_{i_{t}})$ with $0<i_{1}<\dots<i_{t}\leq m$ a
_separated subsequence_ of $(a_{1},a_{2},\ldots,a_{m})$ if $i_{j+1}>i_{j}+1$
for all $j\in[t]$. Similar to max-inducedness, the following simple fact
captures the usefulness of this definition for stepping up: suppose
$v_{1}<v_{2}<\dots<v_{\ell+1}$ are vectors in $\\{0,1\\}^{m}$ and let
$\delta_{i}=\delta(v_{i},v_{i+1})$. If
$(\delta_{i_{1}},\ldots,\delta_{i_{k}})$ is a separated subsequence of
$(\delta_{1},\ldots,\delta_{\ell})$, then there are
$v_{j_{1}},\ldots,v_{j_{2k}}$ such that
$\delta(v_{j_{2s-1}},v_{j_{2s}})=\delta_{i_{s}}$ for each $s\in[k]$. Given a
sequence $S=(s_{1},\ldots,s_{n})$, define $\|S\|:=|\\{s_{1},\ldots,s_{n}\\}|$,
that is, the number of distinct values in the sequence. We can now state our
key result on separated subsequences.

######  Lemma 2.5.

Let $A=(a_{r})_{r=1}^{n}$ be a sequence with the unique maximum property and
$k\in\mathbb{N}$. If $\|A\|<n^{1/(k+1)}$ then $A$ contains every permutation
on $[k]$ as a separated subsequence.

We defer the proof of this lemma to the end of the section and first proceed
to prove Theorem 2.2 and Corollary 2.4.

###  2.1. Max-induced Subsequences

Recall that a family of patterns $\mathcal{F}$ has the max-induced Erdős-
Hajnal property with exponent $c=c(\mathcal{F})$ if every sequence $S$ that
avoids all patterns in $\mathcal{F}$ as a max-induced subsequence must have a
max-induced homogeneous subsequence of length $|S|^{c(\mathcal{F})}$. To
characterize the families with this property, we require the following lemma:

######  Lemma 2.6.

For every $k\geq 1$, there is a permutation $S_{k}$ of length $2^{k+1}-1$ that
contains neither a max-induced copy of $(2,3,1)$ nor a max-induced homogeneous
subsequence of length greater than $k+1$.

###### Proof.

We proceed by induction on $k$. Note that for $k=1$, the permutation $(1,3,2)$
works. Let $S_{k-1}=(a_{1},a_{2},\dots,a_{m_{k-1}})$ be a permutation of
length $2^{k}-1$ with no max-induced 231 and no max-induced homogeneous
subsequence of length greater than $k$. Define the sequence
$S_{k}=(b_{1},\dots,b_{2^{k+1}-1})$ by

$b_{i}=\begin{cases}a_{i}&\text{if }i<2^{k};\\\ 2^{k+1}-1&\text{if
}i=2^{k};\\\ a_{i-2^{k}}+2^{k}-1&\text{if }i>2^{k}.\\\ \end{cases}$

If $(b_{i_{1}},\ldots,b_{i_{\ell}})$ is a max-induced homogeneous subsequence
of $S_{k}$, then either $i_{\ell}\leq 2^{k}$ or $i_{1}\geq 2^{k}$. Thus, by
our choice of $S_{k-1}$, there is no max-induced homogeneous component of
length greater than $k+1$ in $S_{k}$. Similarly, every max-induced 231 pattern
$(b_{i_{1}},b_{i_{2}},b_{i_{3}})$ has either $i_{3}<2^{k}$ or $i_{1}>2^{k}$,
which shows $S_{k}$ avoids a max-induced 231. ∎

###### Proof of Theorem 2.2.

For the forward direction, suppose (without loss of generality) that
$\mathcal{F}$ contains no permutation with the right property. Observe that
every permutation without the right property must contain the pattern $231$.
Therefore, each sequence in $\mathcal{F}$ contains either two elements which
are equal or a copy of $231$, so the sequence $S_{k}$ defined in Lemma 2.6 is
an $\mathcal{F}$-avoiding sequence of length at least $2^{k}$ containing no
max-induced homogeneous subsequence of length greater than $k+1$.

For the backwards direction, let $L$ and $R$ be two permutations such that $L$
has the left property and $R$ has the right property, and suppose $S$ is a
sequence of length $n$. We prove by induction on $t:=|L|+|R|$ that $S$
contains at least one of $L$, $R$, or a max-induced homogeneous sequence of
length at least $n^{\varepsilon}/2$, where $\varepsilon=4^{-t}$. If $t\leq 4$,
then one of $L$ or $R$ has at most two elements, so the statement is clear. We
therefore assume $t>4$, in which case we may assume also that $n$ is large
enough for the inequalities below.

We first describe an algorithm that shows either $S$ contains a max-induced
homogeneous sequence of length at least $n^{-t}$ or there is an index $i$ such
that $a_{i}$ is the maximum in a substantial interval, i.e. $a_{j}\leq a_{i}$
for $i-n^{1-\varepsilon}\leq j\leq i+n^{1-\varepsilon}$. Initialize index sets
$S^{\prime}=[n]$ and $F_{\ell}=F_{r}=\varnothing$. In the $k^{\text{th}}$
iteration of the algorithm, suppose the index $j_{k}\in S^{\prime}$ is such
that $a_{j_{k}}=\max_{i\in S^{\prime}}a_{i}$. Let $\ell=\max F_{\ell}$ and
$r=\min F_{r}$. For $k=1$, we set $\ell=0$ and $r=n+1$. Then

  * •

if $j_{k}-\ell<n^{1-\varepsilon}$, add $j_{k}$ to $F_{\ell}$, delete all $i\in
S^{\prime}$ such that $i\leq j_{k}$, and proceed to the next iteration;

  * •

if $r-j_{k}<n^{1-\varepsilon}$, add $j_{k}$ to $F_{r}$, delete all $i\in
S^{\prime}$ such that $i\geq j_{k}$, and proceed to the next iteration;

  * •

otherwise, the algorithm terminates.

Observe that $(a_{i})_{i\in F_{\ell}}$ and $(a_{i})_{i\in F_{r}}$ are max-
induced sequences in $S$, so if either $|F_{\ell}|\geq n^{\varepsilon}/2$ or
$|F_{r}|\geq n^{\varepsilon}/2$, then we have constructed a max-induced
homogeneous subsequence of length $n^{\varepsilon}/2$. This must be the case
if the algorithm terminates due to deleting all of $S^{\prime}$. Otherwise,
suppose the algorithm terminates on the $k^{\text{th}}$ iteration. Then
$j_{k}$ satisfies $a_{i}\leq a_{j_{k}}$ for $j_{k}-n^{1-\varepsilon}\leq i\leq
j_{k}+n^{1-\varepsilon}$ as desired. Furthermore, for $F_{m}:=\\{i\in
S^{\prime}:a_{i}=a_{j_{k}}\\}$, the sequence $(a_{i})_{i\in F_{m}}$ is a max-
induced sequence in $S$, so we may assume $|F_{m}|<n^{\varepsilon}/2$.

Now let $S_{\ell}^{\prime}=\\{i\in S^{\prime}:i<j_{k}\\}$ and
$S_{r}^{\prime}=\\{i\in S^{\prime}:i>j_{k}\\}$. Let $M\,(\supset F_{m})$ be
the indices of the largest $n^{(1-\varepsilon)/2}$ elements in $(a_{i})_{i\in
S^{\prime}}$, breaking ties arbitrarily. Either $M_{\ell}:=M\cap
S_{\ell}^{\prime}$ or $M_{r}:=M\setminus M_{\ell}$ has at least
$\frac{1}{2}n^{(1-\varepsilon)/2}$ elements. Suppose the former (the argument
for the latter is similar). Since $|S_{r}^{\prime}|\geq n^{1-\varepsilon}$
there must be an interval $I\subset S_{r}^{\prime}$ of length at least
$n^{(1-\varepsilon)/2}/2$ such that $I\cap M_{r}=\varnothing$. If
$I_{m}:=\\{i\in I:a_{i}=\max_{j\in I}a_{j}\\}$ then $(a_{i})_{i\in I_{m}}$ is
a max-induced sequence in $S$, so we may assume $|I_{m}|<n^{\varepsilon}/2$.

Now $|M_{\ell}|\geq n^{(1-\varepsilon)/2}/2$ and $|F_{m}|\leq
n^{\varepsilon}/2$ so there is an interval $J$ such that $|J\cap M_{\ell}|\geq
n^{(1-3\varepsilon)/2}$ and $J\cap F_{m}=\varnothing$. Similarly, there is a
subinterval $I^{\prime}\subseteq I$ such that $|I^{\prime}\cap
I_{m}|=\varnothing$. Let $A=J\cap M_{\ell}$ and $B=I^{\prime}$ so that any
max-induced subsequence in $A$ or $B$ is a max-induced subsequence of $S$.
Also if $i\in A,\,j\in B$ then $a_{j}<a_{i}<a_{j_{k}}$. Recall that the
permutation $L=(l_{i})_{i=1}^{|L|}$ has the left property. Let $k$ be the
index of the maximum of $L$, and define $L_{\ell}=(l_{i})_{i<k}$ and
$L_{r}=(l_{i})_{i>k}$, i.e. $L_{\ell}$ is the subpermutation preceding $\max
L$ and $L_{r}$ is the subpermutation following $\max L$. Observe that
$L_{\ell}$ and $L_{r}$ both have the left property.

Apply the inductive hypothesis to $S_{A}:=(a_{i})_{i\in A}$ with the
permutations $L_{\ell}$ and $R$, and to $S_{B}:=(a_{i})_{i\in B}$ with the
permutations $L_{r}$ and $R$. If we find a max-induced copy of $R$ in $S_{A}$
or $S_{B}$ we are done. If $S_{A}$ contains a max-induced homogeneous
subsequence of length at least

$\frac{1}{2}|A|^{4^{-(|L_{\ell}|+|R|)}}\geq\frac{1}{2}(n^{(1-3\varepsilon)/2})^{4^{-(t-1)}}=\frac{1}{2}(n^{(1-3\varepsilon)/2})^{4\varepsilon}\geq\frac{n^{\varepsilon}}{2}$

or $S_{B}$ contains a max-induced homogeneous subsequence of length at least

$\frac{1}{2}|B|^{4^{-(|L_{r}|+|R|)}}\geq\frac{1}{2}(n^{(1-3\varepsilon)/2})^{4^{-(t-1)}}=\frac{1}{2}(n^{(1-3\varepsilon)/2})^{4\varepsilon}\geq\frac{n^{\varepsilon}}{2}$

we are finished. Otherwise, there is a max-induced copy of $L_{\ell}$ in
$S_{A}$ and $L_{r}$ in $S_{B}$, which along with $a_{j_{k}}$ forms a max-
induced copy of $L$ in $S$. ∎

Given $n,k\in\mathbb{N}$, recall $f(k)$ is the largest integer for which there
exists some $\varepsilon>0$ such that every sequence of length $n$ contains
either at least $f(k)$ distinct max-induced patterns on $k$ elements or a
homogeneous subsequence of length $n^{\varepsilon}$.

###### Proof of Corollary 2.4.

Let $\Pi_{k}$ be the set of permutations of $[k]$ with the right property, and
let $r_{k}:=|\Pi_{k}|$. Let $S$ be a sequence of length $n$. If $S$ contains
fewer than $r_{k}$ max-induced patterns, then $S$ must avoid at least one
left-property permutation and at least one right-property permutation, which
implies $S$ contains a long max-induced homogeneous subsequence by Theorem
2.2. So $f(k)\geq r_{k}$.

To see $f(k)\leq r_{k}$, observe that the only max-induced patterns in the
construction $S_{k}$ from Lemma 2.6 are permutations with the right property.

It remains to show $f(k)=C_{k}$. Let $\pi\in\Pi_{k}$ and suppose $\pi(i)=k$.
The sequence $\\{\pi(1),\dots,\pi(i-1)\\}$, must be a permutation—call it
$\pi_{\ell}$—of $[i-1]$ and $\\{\pi(i+1),\dots,\pi(k)\\}$ must be a
permutation $\pi_{r}$ of $\\{i+1,\dots,k-1\\}$. Both $\pi_{\ell}$ and
$\pi_{r}$ have the right property, so $r_{k}=\sum_{i=1}^{k}r_{i-1}r_{k-i}$,
which is the Catalan recurrence. The initial terms of $(r_{k})_{k=0}^{\infty}$
coincide with the Catalan numbers (take $r_{0}=1$), so they must define the
same sequence. ∎

By symmetry $C_{k}$ is also the number of permutations of $[k]$ with the left
property.

###  2.2. Separated Subsequences

We now prove a result on separated subsequences. The proof relies on a simple
density argument to find a very rich substructure that contains within it all
possible small structures.

###### Proof of Lemma 2.5.

We first find constant subsequences $A_{1},\ldots,A_{k}$ such that

  * •

$|A_{i}|\geq n^{1-i/(k+1)}$ for each $i\in[k]$,

  * •

if $a\in A_{i}$ (meaning $a$ is equal to some element of $A_{i}$) and
$a^{\prime}\in A_{j}$ with $i<j$, then $|a|<|a^{\prime}|$, and

  * •

(interlacing property) if $a_{j},a_{\ell}\in A_{i}$ such that $j<\ell$, then
there is some $a_{m}\in A_{i+1}$ such that $j<m<\ell$

As $\|A\|<n^{\frac{1}{k+1}}$, by the pigeonhole principle there is a constant
subsequence $A_{1}$ such that $|A_{1}|\geq n^{1-1/(k+1)}$. Note that by the
unique maximum property, $A_{1}$ must be a separated subsequence. For $i\geq
1$, given a constant separated subsequence $A_{i}=(a_{i_{j}})_{j}$ satisfying
the above properties, we construct $A_{i+1}$ as follows:

Let $A_{i}^{\prime}=(a_{i_{j}}^{\prime})_{j}$ be the subsequence of $A$
consisting of the maximum values between the elements of $A_{i}$, meaning if
$a_{i_{j}},a_{i_{j+1}}\in A_{i}$, then
$a_{i_{j}}^{\prime}=\max\\{a_{\ell}:i_{j}\leq\ell\leq i_{j+1}\\}$. By the
unique maximum property of $A$, $a_{i_{j}}^{\prime}$ is well-defined and is
strictly greater than $a_{i_{j}}$ and $a_{i_{j+1}}$. Then
$|A_{i}^{\prime}|=|A_{i}|-1\geq n^{1-i/(k+1)}-1$, and $\|A_{i}^{\prime}\|\leq
n^{1/(k+1)}-1$ from the assumption that $\|A\|\leq n^{1/(k+1)}$. By the
pigeonhole principle, there is a constant subsequence of $A_{i}^{\prime}$ with
length at least

$\frac{|A_{i}^{\prime}|}{\|A_{i}^{\prime}\|}\geq n^{1-(i+1)/(k+1)}.$

Let $A_{i+1}$ be this subsequence. It is clear from the construction that the
three desired properties are satisfied.

Now suppose $\sigma$ is a permutation of $[k]$. We use the interlacing
property to find a subsequence of $A$ with the pattern $\sigma$. Let the
elements of $A_{1}$ be indexed by $(i_{1},i_{2},\dots,i_{m})$. For $j\in[k]$,
the interlacing property shows there is $a_{s_{j}}\in A_{\sigma(j)}$ such that
$s_{j}\in\\{i_{j2^{k}}+1,\dots,i_{(j+1)2^{k}-1}\\}$. The subsequence
$(a_{s_{1}},a_{s_{2}},\dots,a_{s_{k}})$ is separated by construction, and
$\sigma(i)<\sigma(j)$ if and only if $a_{s_{i}}<a_{s_{j}}$ by the second
property. Thus, $(a_{s_{i}})_{i}$ has pattern $\sigma$. ∎

We are now ready to employ these results in our stepping-up constructions.

##  3\. Imposing many colours in hypergraph Ramsey theory

In this section, we explain how the results on max-induced and separated
patterns in sequences allow us to step-up colourings in which all large sets
of vertices span many colours. We prove Theorems 1.1 and 1.4 as well as
Corollary 1.2. Throughout, all colourings discussed will be (hyper)edge-
colourings. We say a colouring of a complete hypergraph with $q$ colours is
_$(t;q,p)$ -rainbow_ if every set of $t$ vertices spans at least $p$ colours.
In this language $r_{k}(t;q,p)-1$ is the largest integer $n$ for which there
exists a $(t;q,p)$-rainbow colouring of $K_{n}^{(k)}$. Let $V=\\{0,1\\}^{m}$
and given $v,w\in V$, recall that

$\delta(v,w):=\max\\{i:v_{i}\neq w_{i}\\},$

and that $v<w$ if and only if $v_{\delta}<w_{\delta}$. To each set of vertices
$v_{1}<v_{2}<\dots<v_{k+1}$ in $K_{n}^{(r+1)}$ corresponds a sequence
$(\delta_{1},\delta_{2},\ldots,\delta_{k})$ given by
$\delta_{i}=\delta(v_{i},v_{i+1})$, which we refer to as the corresponding
$\delta$-sequence. The crucial properties for our application of the results
of Section 2 to hypergraph Ramsey theory are

(2) $\text{For an interval $I$, let }\delta_{I}=\max(\delta_{i})_{i\in
I}.\text{ Then }|\\{i\in I:\delta_{i}=\delta_{I}\\}|=1.$ (3) $\text{For any
}v_{1}<v_{2}<\dots<v_{k+1},\,\delta(v_{1},v_{k+1})=\max\\{\delta_{1},\delta_{2},\ldots,\delta_{k}\\}.$

See e.g. [9] for proofs. A useful perspective is gained by viewing $[2^{n}]$
as the leaves of a binary tree of depth $n$, ordered from left to right as you
would draw them. Given two leaves $v,w\in[2^{n}]$, the number $2\delta(v,w)$
is simply the length of the unique path between them.

Recall that Corollary 2.4 shows that a sequence
$(\delta_{1},\delta_{2},\ldots,\delta_{\ell})$ either contains many distinct
max-induced subsequences or a long homogeneous max-induced subsequence. In
order to make use of this fact, we recall Claim 2.1, which simply says the
following: suppose $v_{1}<v_{2}<\dots<v_{\ell+1}$ are vectors in
$\\{0,1\\}^{m}$ and let $\delta_{i}=\delta(v_{i},v_{i+1})$. If
$(\delta_{i_{1}},\ldots,\delta_{i_{k}})$ is a max-induced subsequence of
$(\delta_{1},\ldots,\delta_{\ell})$, then there are
$v_{j_{1}},\ldots,v_{j_{k+1}}$ such that
$\delta(v_{j_{s}},v_{j_{s+1}})=\delta_{i_{s}}$.

###### Proof of Claim 2.1.

Let $v_{j_{1}}=v_{i_{1}}$ and $v_{j_{k+1}}=v_{i_{k}+1}$. Then for $s>1$,
define $v_{j_{s}}=v_{i_{s-1}+1}$ if $\delta_{i_{s-1}}<\delta_{i_{s}}$ and
$v_{j_{s}}=v_{i_{s}}$ otherwise. It is straightforward to check, using
property (3), that $\delta(v_{j_{s}},v_{j_{s+1}})=\delta_{i_{s}}$ for each
$s$. ∎

We are ready to use Theorem 2.2 to prove Theorem 1.1.

###### Proof of Theorem 1.1.

Let $k,p,q\geq 3$ be such that $p\leq C_{k}$, the $k^{\text{th}}$ Catalan
number, and let $c:=16^{k}+1$. We first prove the inequality
$r_{k+1}(t^{c};2q+p,p)>2^{r_{k}(t;q,p)-1}$ by showing such that we can
construct a $(t^{c};2q+p,p)$-rainbow colouring $\chi^{\prime}$ of
$K_{2^{n}}^{(k+1)}$ from any $(t;q,p)$-rainbow colouring $\chi$ of
$K_{n}^{(k)}$. Let $\chi$ be such a rainbow colouring.

We identify $V(K_{2^{n}}^{(k+1)})$ and $V(K_{n}^{(k)})$ with $\\{0,1\\}^{n}$
and $[n]$, respectively. Partition the set of patterns of $[k]$, excluding the
two homogeneous permutations, into $p-2$ classes
$\mathcal{C}_{1},\ldots,\mathcal{C}_{p-2}$ such that each class contains at
least one permutation with the left property and one permutation with the
right property. Let $\mathcal{C}_{p-1}$ be the family of patterns containing
only the strictly increasing permutation and $\mathcal{C}_{p}$ the family
containing the strictly decreasing permutation. Observe that such a partition
is guaranteed to exist by Corollary 2.4 and the assumption that $C_{k}\geq p$
(note that a permutation may have both the left and right property). For a
sequence $S$, we say $S\in\mathcal{C}_{i}$ if the pattern of $S$ is in
$\mathcal{C}_{i}$. Assign to each class $\mathcal{C}_{i}$ a distinct colour
$c_{i}$. Then, for an edge $e=\\{v_{1},\ldots,v_{k+1}\\}$ of
$K_{2^{n}}^{(k+1)}$, with corresponding $\delta$-sequence
$(\delta_{1},\ldots,\delta_{k})$, let

$\chi^{\prime}(e)=\begin{cases}\chi(\\{\delta_{1},\ldots,\delta_{k}\\})\times
1&\text{if }\delta_{1}<\delta_{2}<\dots<\delta_{k};\\\
\chi(\\{\delta_{1},\ldots,\delta_{k}\\})\times 2&\text{if
}\delta_{1}>\delta_{2}>\dots>\delta_{k};\\\ c_{i}&\text{if
}(\delta_{1},\ldots,\delta_{k})\in\mathcal{C}_{i},\ i\leq p-2.\end{cases}$

We claim $\chi^{\prime}$ is the desired colouring. Consider a set of $t^{c}$
vertices $\\{v_{1},\ldots,v_{t^{c}}\\}\subset V(K_{2^{n}}^{(k+1)})$ and its
corresponding $\delta$-sequence $(\delta_{1},\ldots,\delta_{t^{c}-1})$. For
each colour $c_{1},\ldots,c_{p-2}$ or the set of colours $(\,\cdot\,,1)$ and
$(\,\cdot\,,2)$, the corresponding sets of patterns contain a permutation with
the left and a permutation with the right property. Theorem 2.2 thus tells us
that $(\delta_{1},\ldots,\delta_{t^{c}-1})$ either contains a max-induced
pattern from each of $\mathcal{C}_{1},\dots,\mathcal{C}_{p}$ or a max-induced
homogeneous sequence of length $t$ (the value of $c$ was chosen for this
purpose). Claim 2.1 shows that for every max-induced sequence
$S\subset(\delta_{1},\ldots,\delta_{t^{c}-1})$ of length $k$ we can find
$\\{v_{i_{1}},\dots,v_{i_{k+1}}\\}\subset\\{v_{1},\ldots,v_{t^{c}}\\}$ whose
corresponding sequence is $S$. In other words, we have that
$\chi^{\prime}(\\{v_{i_{1}},\dots,v_{i_{k+1}}\\})=c_{i}$ if
$S\in\mathcal{C}_{i}$. Therefore, $(\delta_{1},\ldots,\delta_{t^{c}-1})$
containing a max-induced pattern from each of
$\mathcal{C}_{1},\dots,\mathcal{C}_{p}$ implies that
$\\{v_{1},\ldots,v_{t^{c}}\\}$ spans at least $p$ colours.

If instead $(\delta_{1},\ldots,\delta_{t^{c}-1})$ contains a max-induced
homogeneous subsequence, say $(\delta_{1},\ldots,\delta_{t})$, then by Claim
2.1 we can find
$\\{v_{i_{1}},\dots,v_{i_{t+1}}\\}\subset\\{v_{1},\dots,v_{t^{c}}\\}$ whose
corresponding pattern is $(\delta_{1},\dots,\delta_{t})$. We may assume
without loss of generality that $(\delta_{1},\ldots,\delta_{t})$ is
increasing, and by property (2), $\delta_{1}<\dots<\delta_{t}$. Every
subsequence of a strictly increasing sequence is a max-induced strictly
increasing subsquence. Thus, again by Claim 2.1, for every subsequence
$S\subset(\delta_{1},\ldots,\delta_{t})$ of length $k$ we can find a
subsequence $S^{\prime}\subset(v_{i_{1}},\dots,v_{i_{t+1}})$ of length $k+1$
whose corresponding $\delta$-sequence is $S$. Observe that
$\chi^{\prime}(S^{\prime})=(\chi(S),1)$, so the set of $(k+1)$-edges on
$\\{v_{i_{1}},\dots,v_{i_{t+1}}\\}$ spans at least as many colours as the set
of $k$-edges on $\\{\delta_{1},\ldots,\delta_{t}\\}$. By assumption, this is
at least $p$.

All that remains is to count the number of colours used by $\chi^{\prime}$ .
This is at most $2$ colours for each of the $q$ colours used by $\chi$ plus an
extra $p-2$ for the $c_{i}$’s. Combined with the above arguments, this shows
that $\chi^{\prime}$ is a $(t^{c};2q+p-2,p)$-rainbow colouring and in
particular a $(t^{c};2q+p,p)$-rainbow colouring.

We now describe the construction of the $(t^{c};q,p-2)$-rainbow colouring, say
$\chi^{\prime\prime}$, which shows that
$r_{k+1}(t^{c};q,p-2)>2^{r_{k}(t;q,p-2)-1}$. Let a $(t;q,p-2)$-rainbow
colouring $\chi$ of $K_{n}^{(k)}$ be given. As before, assign to each class
$\mathcal{C}_{i}$ a distinct colour $c_{i}$ for $i\in[p-2]$, only this time
identify these colours with the first $[p-2]$ colours used by $\chi$
(trivially we have $q\geq p-2$). For an edge $e=\\{v_{1},\ldots,v_{k+1}\\}$
with corresponding $\delta$-sequence $(\delta_{1},\ldots,\delta_{k})$, let

$\chi^{\prime\prime}(e)=\begin{cases}\chi(\\{\delta_{1},\ldots,\delta_{k}\\})&\text{if
}\delta_{1}<\delta_{2}<\dots<\delta_{k}\text{ or
}\delta_{1}>\delta_{2}>\dots>\delta_{k};\\\ c_{i}&\text{if
}(\delta_{1},\ldots,\delta_{k})\in\mathcal{C}_{i}.\end{cases}$

We omit the proof that $\chi^{\prime\prime}$ is in fact the desired colouring,
as it is almost identical to the proof for $\chi^{\prime}$. We simply note
that now we can only force $p-2$ colours in any set of $t^{c}$ vertices, as an
edge with a homogeneous pattern may receive any one of the colours $c_{i}$ for
$i\in[p-2]$. ∎

In applying our stepping-up results, we will need the following result on
rainbow colorings which is proven by a standard use of the first moment method
(see e.g. [1]).

######  Proposition 3.1.

For every $k$ and $q$, there exists $\varepsilon>0$ and $t_{0}$ so that for
$t>t_{0}$ there is a $(t;q,q)$-rainbow colouring of $K_{n}^{(k)}$ with
$n=2^{\varepsilon t^{k-1}}$.

###### Proof.

Set $\varepsilon=1/(qk!)$ and $t_{0}=eq$. Consider a uniformly random
$q$-colouring of $K_{n}^{(k)}$ with $n=2^{\varepsilon t^{k-1}}$. The
probability a given $t$-set contains fewer than $q$ colours is at most
$q(1-1/q)^{t\choose k}$. Therefore the expected number of $t$ sets with fewer
than $q$ colours is at most

${n\choose t}q(1-1/q)^{t\choose
k}<\mathopen{}\mathclose{{}\left(\frac{en}{t}}\right)^{t}qe^{-{t\choose
k}/q}<\mathopen{}\mathclose{{}\left(\frac{q^{1/t}en}{te^{-{t\choose
k}/(tq)}}}\right)^{t}<1.$

As the expectation is strictly less than one, there must exist some
$(t;q,q)$-rainbow colouring. ∎

###### Proof of Corollary 1.2.

Proposition 3.1 shows that there is an $\varepsilon>0$ such that, with
$n=2^{\varepsilon t}$, a uniformly random colouring of the edges of
$K_{n}^{(3)}$ is $(t;q,q)$-rainbow with high probability. Thus
$r_{3}(t;q,q)>2^{\varepsilon t}$. Since the Catalan number $C_{i}\geq 5$ for
$i\geq 3$, we may apply the inequality
$r_{i+1}(t^{c};2q+5,5)>2^{r_{i}(t;q,5)-1}$ from Theorem 1.1, once for each
$i\in\\{3,\dots,k-1\\}$ and with a different $c\geq 1$ each round. This
ultimately yields a lower bound of $r_{k}(t^{c^{\prime}};q^{\prime},5)\geq
T_{k-1}(t)$ where $q^{\prime}=3^{k}q$ and $c^{\prime}\geq 1$. ∎

The proof of Corollary 1.3 follows the exact same procedure as the proof of
Corollary 1.2, simply using the bound $r_{k+1}(t^{c};3,3)>2^{r_{k}(t;3,3)-1}$
in place of the bound $r_{k+1}(t^{c};2q+5,3)>2^{r_{k}(t;q,5)-1}$. We thus omit
it. We now prove Theorem 1.4, which combines Lemma 2.5 with a slightly
different stepping-up technique.

###### Proof of Theorem 1.4.

Let $k,p,q\geq 3$ be such that $p\leq k!$ and let $c:=k+2$. We prove the
inequality $r_{2k}(t^{c};pq,p)>2^{r_{k}(t;q,p)-1}$ by showing such that we can
construct a $(t^{c};pq,p)$-rainbow colouring $\chi^{\prime}$ of
$K_{2^{n}}^{(2k)}$ from any $(t;q,p)$-rainbow colouring $\chi$ of
$K_{n}^{(k)}$. Let such a $\chi$ be given.

We identify $V(K_{2^{n}}^{(2k)})$ and $V(K_{n}^{(k)})$ with $\\{0,1\\}^{n}$
and $[n]$ respectively. Order the $k!$ permutations of $[k]$ and let $P_{i}$
be the set of sequences whose pattern is the $i^{\text{th}}$ permutation for
$i\in[p]$. Then, for an edge $e=\\{v_{1},\ldots,v_{2k}\\}$ with corresponding
$\delta$-sequence $(\delta_{1},\ldots,\delta_{2k-1})$ we set

$\chi^{\prime}(e)=\chi(\\{\delta_{1},\delta_{3},\ldots,\delta_{2k-1}\\})\times
i$

if $(\delta_{1},\delta_{3},\ldots,\delta_{2k-1})\in P_{i}$ for some $i\in[p]$
and we let $\chi^{\prime}(e)$ be arbitrary otherwise.

We now check that this is the desired colouring. It is clear that it uses at
most $pq$ colours. Suppose $v_{1}<\dots<v_{t^{c}}$ are vertices of
$K_{2^{n}}^{(2k)}$ and let $(\delta_{1},\dots,\delta_{t^{c}-1})$ be the
corresponding $\delta$-sequence. If $\|(\delta_{i})_{i=1}^{t^{c}-1}\|\geq 2t$
then we can find an index set $I\subset[t^{c}-1]$ such that
$(\delta_{i})_{i\in I}$ is a separated subsequence with $\|(\delta_{i})_{i\in
I}\|\geq t$. Let
$f=\\{\delta_{i_{1}},\dots,\delta_{i_{k}}\\}\subset(\delta_{i})_{i\in I}$
where $i_{1}<i_{2}<\dots<i_{k}$. Then the edge
$e=\\{v_{i_{1}},v_{i_{1}+1},v_{i_{2}},v_{i_{2}+1},\dots,v_{i_{k}},v_{i_{k}+1}\\}$
has colour $\chi^{\prime}(e)=(\chi(f),\cdot)$. As $f$ was arbitrary we have
that $\\{v_{1},\dots,v_{t^{c}}\\}$ spans at least as many colours as
$\\{\delta_{i}\\}_{i\in I}$. But $\|(\delta_{i})_{i\in I}\|\geq t$ and so
$(\delta_{i})_{i\in I}$ spans at least $p$ colours by assumption.

Now suppose that $\|(\delta_{i})_{i=1}^{t^{c}-1}\|<2t$. By (2),
$(\delta_{i})_{i=1}^{t^{c}-1}$ satisfies the unique maximum property.
Therefore, by our choice of $c$, we can apply Lemma 2.5 with
$A=(\delta_{i})_{i=1}^{t^{c}-1}$ to conclude that $A$ contains every
permutation of $[k]$ as a separated subsequence. Suppose we have a separated
subsequence $S\subset A$ whose pattern is the $i^{\text{th}}$ permutation for
some $i\in[p]$. As before we can find a $(2k)$-edge
$e\subseteq\\{v_{1},\dots,v_{t^{c}}\\}$ for whom the corresponding
$\delta$-pattern is $S$. Thus $\chi^{\prime}(e)=(\cdot,i)$. Repeating this for
the first $p$ permutations implies that $\\{v_{1},\dots,v_{t^{c}}\\}$ spans at
least $p$ colours. ∎

Both of our stepping-up constructions (like the original) rely on breaking the
stepping-up into two parts: a lifted colouring from a lower uniformity graph
and a new colouring. The constructions have the property that every large set
of vertices satisfies one of the following: either it spans a colouring that
is lifted from a large clique on the lower graph or it sees many distinct new
colours. The number of new colours one can guarantee using this approach
depends strongly on the uniformity of the hypergraphs in question. We ask a
question in the concluding remarks concerning this.

##  4\. Hedgehogs

In this section, we relate our results on many-coloured Ramsey numbers of
complete hypergraphs to a Ramsey problem on a certain class of hypergraphs
which we call generalized hedgehogs. We note our idea is very much inspired by
the Conlon-Fox-Rödl construction described in the introduction. The main
result is Theorem 1.6, a and we also prove Lemma 1.7 for a more general family
of hedgehogs.

We define the _generalized hedgehog_ $\text{H}_{t}^{(k)}(s)$ for
$s,k,t\in\mathbb{N}$ with $k>s$ and $t\geq s$ to be the following $k$-uniform
hypergraph: fix a set of $t$ vertices called the _body_. The edge set of
$\text{H}_{t}^{(k)}(s)$ consists of the following edges: for every $s$-subset
$S$ of the body, we add a $k$-edge $e$ containing $S$ along with $k-s$
additional vertices that are contained in no other edge of
$\text{H}_{t}^{(k)}(s)$.

The $k$-uniform balanced hedgehog $\hat{H}_{t}^{(k)}$ is
$\text{H}_{t}^{(k)}(\lceil\frac{k}{2}\rceil)$ and the hedgehog introduced by
Conlon, Fox, and Rödl is $\text{H}_{t}^{(k)}(k-1)$. We note that
$\text{H}_{t}^{(k)}(s)$ has ${t\choose s}$ edges and $t+(k-s){t\choose s}$
vertices.

Lemma 1.7 is a corollary of the following result, which we state in its full
generality.

######  Lemma 4.1.

Given $k,q,p^{\prime},t\in\mathbb{N}$, let $p={k\choose s}$ and
$q^{\prime}={q\choose p}$. Then

$r_{k}(\text{H}_{t}^{(k)}(s);q^{\prime},p^{\prime}+1)>r_{s}(t;q,p^{\prime}p+1)-1.$

###### Proof of Lemma 1.7.

Apply Lemma 4.1 with $2k+1,k+1$ and $1$ playing the role of $k,s$ and
$p^{\prime}$ respectively. ∎

###### Proof of Lemma 4.1.

We prove
$r_{k}(\text{H}_{t}^{(k)}(s);q^{\prime},p^{\prime}+1)>r_{s}(t;q,p^{\prime}p+1)-1$
by showing that given a $(t;q,p^{\prime}p+1)$-rainbow colouring of
$K_{n}^{(s)}$, we can construct a $q^{\prime}$-colouring $\chi^{\prime}$ of
$K_{n}^{(k)}$ in which every copy of $\text{H}_{t}^{(k)}(s)$ spans at least
$p^{\prime}+1$ colours. Let such a $\chi$ be given. Identify the vertex sets
of $K_{n}^{(k)}$ and $K_{n}^{(s)}$. We colour $e^{\prime}\in E(K_{n}^{(k)})$
by $\chi^{\prime}(e^{\prime})=\\{\chi(e):e\in E(K_{n}^{(s)}[e^{\prime}])\\}$,
that is, the union of the colours of the $s$-edges contained in $e^{\prime}$.
The number of $s$-edges contained in $e^{\prime}$ is exactly $p={k\choose s}$,
so $\chi^{\prime}(e^{\prime})$ will be the union of at most that many colours.
If $|\chi^{\prime}(e^{\prime})|<p$ then we add arbitrary colours to the set
until $|\chi^{\prime}(e^{\prime})|=p$. Thus the new colouring uses at most
$q^{\prime}={q\choose p}$ colours.

Now consider a copy $H\subset K_{n}^{(k)}$ of $\text{H}_{t}^{(k)}(s)$. As the
body contains $t$ vertices, by assumption it spans at least $p^{\prime}p+1$
colours under $\chi$. Each of these colours appears as an element of
$\chi^{\prime}(e^{\prime})$ for some $e^{\prime}\in E(H)$, i.e.
$|\cup_{e^{\prime}\in E(H)}\chi^{\prime}(e^{\prime})|\geq p^{\prime}p+1$.
However, $p$ colours appear in $\chi^{\prime}(e^{\prime})$ for a given
$e^{\prime}$, so by pigeonhole there must be more than $p^{\prime}$ edges
$e^{\prime}\in E(H)$ with distinct colours in $\chi^{\prime}(H)$. ∎

We now derive Theorem 1.6, b.

###### Proof of Theorem 1.6, b.

Throughout the proof we assume $t\in\mathbb{N}$ is sufficiently large. Let
$m=\lceil\frac{e(k+1)}{\log_{2}(k+1)}\rceil$, which is chosen so that
$m!>\mathopen{}\mathclose{{}\left(\frac{m}{\mathrm{e}}}\right)^{m}>2^{2k}>{2k+1\choose
k+1}$ for $k$ sufficiently large. Recall that by Proposition 3.1,
$r_{m}(t;m!,m!)\geq T_{2}(\varepsilon t)$ for some $\varepsilon>0$. We now use
the inequality $r_{2k}(t^{c};pq,p)\geq 2^{r_{k}(t;q,p)}$ from Theorem 1.4
exactly $\lfloor\log_{2}\frac{k+1}{m}\rfloor>\log_{2}\log_{2}k-3$ times, to
obtain that there exists $q^{\prime}$ and $c^{\prime}\geq 1$ such that
$r_{k+1}(t^{c^{\prime}};q^{\prime},m!)\geq T_{\log_{2}\log_{2}k-1}(t)$ (if
$k+1>2^{j}m$ with $j=\lfloor\log_{2}\frac{k+1}{m}\rfloor$ we use the simple
observation $r_{i+1}(t;q,p)>r_{i}(t;q^{\prime},p)$ for some $q^{\prime}>q$).
This is possible because the uniformity increases at each step while the
number of colours imposed remains at $m!$. Since $m!>{2k+1\choose k+1}$, we
can apply Lemma 1.7 to get that for some $q^{\prime\prime}$,
$r_{2k+1}(\hat{H}_{t};q^{\prime\prime},2)\geq T_{\log_{2}\log_{2}k-2}(t)$,
where we removed the exponent $c^{\prime}$ at the cost of a tower height. We
choose $c>0$ such that if $m!\leq{2k+1\choose k+1}$ then
$c\log_{2}\log_{2}k\leq 1$.

Thus, for all $k$, $r_{2k+1}(\hat{H}_{t};q^{\prime\prime},2)\geq
T_{c\log_{2}\log_{2}k}(t)$. Furthermore, it is clear that $q^{\prime\prime}$
is only a function of $k$ and of $m$, which is itself a function of $k$, as
required. ∎

Conlon, Fox, and Rödl showed the following using a similar argument to Theorem
1.6, a:

######  Theorem 4.2 ([3]).

For all $k\geq 4$ there exists $c>0$ such that

$r_{k}(H_{t}^{(k)};2,2)\leq T_{k-2}(ct).$

For the case $k=4$, a construction of Kostochka and Rödl [10] shows this is
approximately sharp, i.e. that
$r_{4}(\text{H}_{t}^{(4)}(3);2,2)=T_{2}(\Omega(t))$. We cannot prove a
matching lower bound for $k=5$ as when we attempt to apply Lemma 1.7 we need
to impose $6$ colours on $4$-uniform graphs. When stepping up to uniformity
$4$, Theorem 1.1 allows us to impose at most $C_{3}=5$ colours, so we cannot
beat the random argument here. We do, however, obtain the following:

######  Lemma 4.3.

For $5\leq k\leq 13$, there exist $c>0$ and $q\in\mathbb{N}$ such that for all
$t$

$r_{k}(H_{t}^{(k)};q,2)\geq T_{k-3}(t^{c}).$

###### Proof.

The proof mimics that of Theorem 1.6, b, but now we start from the fact that
$r_{4}(t;14,14)\geq T_{2}(ct)$ (using Proposition 3.1) and leverage that
$C_{4}=14$. Starting from $\ell=4$, we apply the relation
$r_{\ell+1}(t^{C};2q+p,p)\geq 2^{r_{\ell}(t;q,p)}$ from Theorem 1.1 $k-5$
times. This gives us $r_{k-1}(t;q^{\prime},14)\geq T_{k-3}(t^{c^{\prime}})$
for some $q^{\prime}\in\mathbb{N}$ and $c^{\prime}\geq 1$. Applying Lemma 1.7
then gives the result using $q^{\prime\prime}$ colours and with $c^{\prime}$
as $c$. ∎

We now prepare to prove our upper bounds on the Ramsey numbers of balanced
hedgehogs, Theorem 1.6, a. Let $H$ be an $r$-uniform hypergraph and $A\subset
V(H)$ with $|A|<r$. The _piercing number_ of $A$ (denoted $\tau_{H}(A)$) is
the size of the smallest set of vertices from $V(H)\backslash A$ that
intersects every edge of $H$ containing $A$. Equivalently it is the minimum
number of vertices that must be deleted from $V(H)\backslash A$ to delete all
edges containing $A$.

######  Proposition 4.4.

Suppose $H$ is an $r$-uniform hypergraph and $v\in V(H)$ has
$\tau(v)\geq(r-1)m$. Then there exist $m$ edges whose pairwise intersections
are all precisely $v$.

###### Proof of Proposition 4.4.

Let $X\subset V(H)$ be a witness to $\tau(v)$. It is clear the set of edges
incident to $v$ has order at least $(r-1)m$. As each such edge $e$ contains at
most $r-1$ elements of $X$, and $|X|$ is minimal with respect to intersecting
all edges incident to $v$, we can greedily find the desired $m$ edges. ∎

###### Proof of Theorem 1.6, a.

Let $G=K_{n}^{(2k+1)}$ where $n\geq t^{k+3}$ and let $\chi$ be an arbitrary
red/blue colouring of the edges of $G$. We will show that there exists a
monochromatic copy of $H_{t}^{(2k+1)}(k+1)$ in $G$, and thus that
$\text{r}_{2k+1}(\text{H}_{t}^{(2k+1)}(k+1);2,2)\leq n$. We will do so by
using $\chi$ to define a partial edge $2$-colouring $\chi^{\prime}$ of
$G^{\prime}:=K_{n}^{(k+1)}$ and in turn using $\chi^{\prime}$ to define a
$2$-colouring $\chi^{\prime\prime}$ of $V(G)$. We will then find a large
monochromatic set of vertices in $\chi^{\prime\prime}$, use this to find a
large (red or blue) independent set in $G^{\prime}$, and finally use this to
find our monochromatic $\text{H}_{t}^{(2k+1)}(k+1)$ in $G$.

Throughout the proof let $H_{t}:=\text{H}_{t}^{(2k+1)}(k+1)$. We say a set of
vertices is in red danger if its red piercing number (its piercing number in
the subgraph of red edges) is less than $t^{k+1}$ and similarly define blue
danger. Then for $e\in G^{\prime}:=K_{n}^{(k+1)}$, let $\chi^{\prime}(e)$ be
red if $e$ is in red danger and blue if $e$ is in blue danger. As
$\tau_{G}(e)>2t^{k+1}$, we have that this partial colouring $\chi^{\prime}$ is
well defined.

Now say a vertex $v$ is in red peril if its red piercing number in
$G^{\prime}$ (under $\chi^{\prime}$) is at most $2kt^{k+1}$ and similarly
define blue peril. Let $\chi^{\prime\prime}(v)$ be red if $v$ is in red peril
and blue if $v$ is in blue peril, with ties broken arbitrarily. We claim that
$\chi^{\prime\prime}$ assigns a colour to every vertex. Indeed suppose that
some vertex $v$ has red piercing number and blue piercing number at least
$2kt^{k+1}$ under $\chi^{\prime}$.

By Proposition 4.4, there exist $(k+1)$-edges
$e_{1},\dots,e_{s},f_{1},\dots,f_{s}\in G^{\prime}$ where $s=2t^{k+1}$ such
that

  * •

$e_{i}\cap e_{j}=f_{i}\cap f_{j}=\\{v\\}$ for all $i\neq j$,

  * •

$\chi^{\prime}(e_{i})$ is red for all $i\in[s]$, and

  * •

$\chi^{\prime}(f_{j})$ is blue for all $j\in[s]$

Let $A_{1},A_{2},\dots,A_{s}$ be disjoint subsets each of size $k-1$ in
$V(G)\setminus\mathopen{}\mathclose{{}\left(\bigcup_{i=1}^{s}(e_{i}\cup
f_{i})}\right)$. For each $i,j\in[s]$, define a $(2k+1)$-edge $g_{ij}$ to be
$e_{i}\cup f_{j}$ along with an arbitrary choice of $(2k+1)-|e_{i}\cup f_{j}|$
vertices from $A_{(i+j-1)\mathrm{mod}\ s}$. Observe that $e_{i}\cup f_{j}\neq
e_{i^{\prime}}\cup f_{j^{\prime}}$ for $(i,j)\neq(i^{\prime},j^{\prime})$, so
in particular, these edges are all distinct.

At least half of these edges must have been, without loss of generality, red
under the colouring $\chi$ of $G$. Therefore, there is some $i\in[s]$ such
that $e_{i}$ is contained in at least $\frac{s^{2}}{2s}=\frac{s}{2}>t^{k+1}$
red $(2k+1)$-edges under $\chi$. But since $g_{ij}\cap g_{ij^{\prime}}=e_{i}$
for $j\neq j^{\prime}$, this contradicts the fact that $e_{i}$ was a red-
danger edge of $G^{\prime}$. Thus, the colouring $\chi^{\prime\prime}$ of
$V(G)$ colours every vertex.

We now choose a set $X$ of red vertices (without loss of generality) which has
order $\frac{n}{2}$. By the definition of $\chi^{\prime\prime}$, we have that
the red piercing number under $\chi^{\prime}$ of each $v\in X$ is at most
$2kt^{k+1}$. Therefore we can greedily find a set $Y$ of order
$\frac{n}{2\cdot 2kt^{k+1}}\geq t$ which contains no red edges of $G^{\prime}$
(here we use that $t$ is large relative to $k$).

All edges of $G^{\prime}$ in $Y$ are not in red danger and thus have red
piercing number at least $t^{k+1}$ under $\chi$. By the definition of piercing
number and as $t^{k+1}>t+k{t\choose k+1}=|V(\text{H}_{t}^{(2k+1)}(k+1))|$, we
can build the hedgehog greedily using $Y$ as the body. ∎

###  4.1. Burr-Erdős Conjecture in hypergraphs

The degeneracy of a hypergraph is the minimum $d$ such that every induced
subgraph contains a vertex incident to at most $d$ edges; such a hypergraph is
called $d$-degenerate. Burr and Erdős conjectured that for every $d$, there
exists a constant $c_{d}\geq 1$ such that every $d$-degenerate graph $G$ on
$n$ vertices satisfies $r_{2}(G)<c_{d}n$ [2]. This was finally proven by Lee
in [12], building on the previous work of several authors ([8],[11]). In the
case of hypergraphs, however, the conjecture fails: Kostochka and Rödl [10]
showed $r_{4}(H_{t}^{(4)})\geq 2^{ct}$, and Conlon, Fox, and Rödl [3] proved
$r_{3}(H_{t}^{(3)};3)\geq\Omega(t^{3}/\log^{6}t)$, while it is easy to see the
degeneracy of hedgehogs is $1$.

This shows that the Burr-Erdős Conjecture fails for $k$-uniform hypergraphs
where $k\geq 4$ and for $3$-uniform hypergraphs provided the number of colours
is at least $3$. For the sake of completeness, we show the following, in this
way disproving fully the Burr-Erdős Conjecture for hypergraphs.

######  Proposition 4.5.

There exists a $3$-uniform hypergraph on $Cn^{2}$ vertices which is
$8$-degenerate and for which the $2$-colour Ramsey number is at least
$Cn^{3}.$

###### Proof.

Let $V$ be a set of $n$ vertices, and with $m={n\choose 2}$, let $B$ be a set
of $m+1$ vertices disjoint from $V$ with a total ordering $x_{1},x_{2},\ldots
x_{m},x_{m+1}$. Consider an ordering on the edges $E$ of the complete graph on
$V$, say $e_{1},e_{2},...,e_{m}$. Let $H$ be a 3-uniform hypergraph consisting
of the following: for each edge $e_{i}=(x,y)\in E$, add the two triples
$\\{x,y,x_{i}\\}$ and $\\{x,y,x_{i+1}\\}$, and for every $i\in[m-3]$, add all
triples within $\\{x_{i},x_{i+1},x_{i+2},x_{i+3},x_{i+4}\\}$. By considering
the smallest element of $B$ in each subset of vertices, we see that $H$ is
$8$-degenerate.

We claim $r_{3}(H)\geq n^{3}/8$. Indeed, given $K_{n^{3}/8}^{(3)}$, let
$W_{1},\ldots W_{n/4}$ be an arbitrary partition of the vertices where
$|W_{i}|=n^{2}/2$ for all $i\in[n/4]$. We colour blue all edges inside any
$W_{i}$ and all edges with vertices in distinct sets
$W_{i_{1}},W_{i_{2}},W_{i_{3}}$. We colour red all edges with exactly two
vertices in a set $W_{i}$, for some $i\in[n/4]$.

Suppose there is a red copy of $H$. In particular, the edges induced by
$S=\\{x_{1},x_{2},x_{3},x_{4},x_{5}\\}$ are all red. If $S$ intersects
distinct parts $W_{i},W_{j}$, and $W_{k}$ for some $i,j,k\in[n/4]$, then the
vertices in the intersections form a blue edge. However, if $S\subseteq
W_{i}\cup W_{j}$, then $|S\cap W_{i}|\geq 3$ or $|S\cap W_{j}|\geq 3$, which
again forms a blue edge. So we have a contradiction.

Suppose instead there is a blue copy of $H$. By pigeonhole, there are two
vertices $v,w\in V$ which both lie in the same $W_{i}$. Let $e_{j}=\\{v,w\\}$.
The edges $\\{v,w,x_{j}\\}$ and $\\{v,w,x_{j+1}\\}$ are both blue, so
$x_{j},x_{j+1}\in W_{i}$. But $\\{x_{j},x_{j+1},x_{j+2}\\}$ and
$\\{x_{j-1},x_{j},x_{j+1}\\}$ are also blue, so this implies
$x_{j-1},x_{j+2}\in W_{i}$. Proceeding inductively, we conclude that all of
$B$ must lie in $W_{i}$.

However, $|W_{i}|=n^{2}/2$ and $|B|={n\choose 2}$, so there are $n/2$ vertices
of $V$ outside of $W_{i}$. Two of these vertices $z$ and $u$ must lie in the
same $W_{j}$ with $j\neq i$. Letting $e_{k}=\\{z,u\\}$, we get that the edge
$\\{z,u,x_{k}\\}$ is coloured red, a contradiction which finishes the proof. ∎

##  5\. Concluding remarks

We have proved that for every positive integer $h$, there exist $q$, $k$, and
an infinite family of $k$-uniform hypergraphs whose $2$-colour Ramsey numbers
differ by a tower of height $h$ from the $q$-colour Ramsey numbers. This
reinforces the fact that the number of colours plays an important role in the
behaviour of Ramsey numbers of hypergraphs and casts a shadow on Erdős’s
conjecture on the $2$-colour Ramsey number of a $3$-uniform clique.

Observe that both of our new stepping-up constructions rely on a dichotomy:
either we can find many suitable substructures within the $\delta$-sequences
(which give rise to many colours) or we must have a long homogeneous sequence
(which allows us to use induction). Since for every $k$-edge there are at most
$k!$ distinct permutations, our methods fail to give good lower bounds for
$r_{k}(t;q,p)$ whenever $k\ll p$. Even in the simplest case $r_{3}(t;q,3)$, we
were not able to prove a double exponential lower bound, leaving open the
following question of Conlon, Fox, and Rödl on $r_{3}(t;q,3)$.

######  Problem 5.1.

[3, Problem 1] Is there an integer $q$, a positive constant $c$, and a
$q$-colouring of the 3-uniform hypergraph on $2^{2^{ct}}$ vertices such that
every subset of order $t$ receives at least 3 colours?

We propose an even weaker problem which we were not able to resolve. A
negative answer would uncover a radical new phenomenon in the Ramsey numbers
of hypergraphs.

######  Problem 5.2.

Does there exist $k\in\mathbb{N}$ such that the following holds? For all
$p\in\mathbb{N}$ there exist $q\in\mathbb{N}$ and $c>0$ such that
$r_{k}(t;q,p)\geq 2^{2^{t^{c}}}$ for all $t$ sufficiently large.

Recall Proposition 4.5 shows there is an infinite family of $3$-uniform
hypergraphs which are $8$-degenerate and for which the the $2$-colour Ramsey
numbers grows faster than linear in the order of the hypergraphs. It would be
interesting to improve the quantitative aspects of this result.

######  Problem 5.3.

Give an infinite family of $1$-degenerate $3$-uniform hypergraphs whose
$2$-colour Ramsey number is not polynomial in the order of the hypergraph.

Finally, we make the following conjecture regarding the Ramsey numbers of
$k$-uniform hedgehogs. This would in particular demonstrate that the
$2$-colour and $q$-colour Ramsey numbers of these hedgehogs, unlike those of
balanced hedgehogs, do not differ by arbitrarily large tower heights.

######  Conjecture 5.4.

There is $\ell\in\mathbb{N}$ such that for every positive integer $k$, for
every sufficiently large $t$,

$r_{k}(H_{t}^{(k)})\geq T_{k-\ell}(t).$

## Acknowledgments

We thank Bhargav Narayanan for helpful conversations on this topic. The first
author was supported in part by Simons Foundation grant 332622. The first and
fourth authors were supported in part by NSF Grant CCF-1814409 and NSF Grant
DMS-1800521. The second author was supported by Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s
Excellence Strategy EXC-2181/1 - 390900948 (the Heidelberg STRUCTURES Cluster
of Excellence) and by EPSRC grant EP/V007327/1. The third author was supported
in part by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation) – 428212407.

## References

  * [1] N. Alon and J.H. Spencer.  The Probabilistic Method.  John Wiley & Sons, 2016.
  * [2] S.A. Burr and P. Erdős.  On the magnitude of generalized Ramsey numbers for graphs, Infinite and Finite Sets I, Colloq. Math. Soc. János Bolyai, 10, North-Holland, Amsterdam-London, 1975.
  * [3] D. Conlon, J. Fox, and V. Rödl.  Hedgehogs are not color blind.  J. Comb., 8(3):475–485, 2017.
  * [4] D. Conlon, J. Fox, and B. Sudakov.  Hypergraph Ramsey numbers.  J. Amer. Math. Soc., 23(1):247–266, 2010.
  * [5] P. Erdős and A. Hajnal.  On Ramsey like theorems, problems and results.  In Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pages 123–140, 1972.
  * [6] P. Erdős and R. Rado.  Combinatorial theorems on classifications of subsets of a given set.  Proc. London Math. Soc., 3(1):417–439, 1952.
  * [7] P. Erdős, A. Hajnal, and R. Rado.  Partition relations for cardinal numbers.  Acta Math. Acad. Sci. Hung., 16:93–196, 1965.
  * [8] J. Fox and B. Sudakov.  Two remarks on the Burr–Erdős conjecture.  European J. Combin., 30:1630–1645, 2009.
  * [9] R.L. Graham, B.L. Rothschild, and J.H. Spencer.  Ramsey Theory, volume 20.  John Wiley & Sons, 1990.
  * [10] A. Kostochka and V. Rödl.  On Ramsey numbers of uniform hypergraphs with given maximum degree.  J. Combin. Theory, Series A, 113(7):1555–1564, 2006.
  * [11] A. V. Kostochka and B. Sudakov.  On Ramsey numbers of sparse graphs.  Combin. Probab. Comput., 12:627–641, 2003.
  * [12] C. Lee.  Ramsey numbers of degenerate graphs.  Ann. of Math., 185(3):791–829, 2017.
  * [13] D. Mubayi and A. Suk.  Cliques with many colors in triple systems.  arXiv:2005.03078, 2020.
  * [14] S. Shelah.  Erdős and Rényi conjecture.  J. Combin. Theory, Series A, 82(2):179–185, 1998.