Introduction

Given k-uniform hypergraphs, or k-graphs, G 1 , . . . , G q , let r(G 1 , . . . , G q ) denote their Ramsey number, which is the minimum positive integer N such that in every coloring of the edges of the complete k-graph K (k) N on N vertices with color set [q] = {1, . . . , q} there is a color i for which there is a monochromatic copy of G i in color i. When G 1 = • • • = G q = G, we write r(G; q) and when G = K (k) n , we sometimes write r k (n; q). The existence of these numbers was famously proved by Ramsey [19] in 1930. Since then, obtaining good bounds on r k (G; q) for various (hyper)graphs G has been among the most significant areas of study in discrete mathematics. One of the central problems in this area is to obtain good bounds on the so-called diagonal graph Ramsey number, r 2 (n; 2), for which the current best bounds are → 2 n < r(n; 2) ↑ (4 ↓ ω) n , where the lower bound is due to Erd!s [9] and the upper bound is a recent breakthrough of Campos, Gri"ths, Morris and Sahasrabudhe [5]. For a survey on graph Ramsey numbers we refer the reader to [7].

Another classical direction in Ramsey theory is given a fixed graph G, to determine the behavior of r(G; q) as the number of colors, q, tends to infinity. In the case when G is a triangle, the study of this problem goes back to the work of Schur in 1916, who proved a Ramsey-type result for sum-free sets (see [18]). For general G, this problem exhibits the following dichotomy. If G is bipartite, then r(G; q) = O(q C ) for some constant C = C(G). Indeed, this follows from the famous theorem of Kövári, Sós and Turán [15] stating that for bipartite G, there is a constant ω = ω(G) > 0 such that for large enough n, any graph on n vertices with at least n 2→ω edges contains a copy of G. On the other hand, if G is not bipartite, then we have r(G; q) > 2 q . This follows by considering the q-edge-coloring of the complete graph on the vertex set {0, 1} q where a pair of vertices is colored by the index of the first coordinate in which their binary representations di#er. In this coloring, every color class is a bipartite graph, so there is no monochromatic copy of G. Day and Johnson [8] have improved this lower bound by showing that for any non-bipartite graph G, there is a positive ω > 0 such that r(G; q) > (2 + ω) q . Regarding upper bounds, a simple extension of the neighbour chasing argument of Erd!s and Szekeres [12] yields r(K n ; q) < q nq . Hence, for fixed non-bipartite G, we have (2 + ω) q ↑ r(G; q) ↑ 2 O(q log q) . Determining whether these numbers should be exponential or not is a very old and major open problem even for the simplest case when G = K 3 for which Erd!s o#ered a prize of $250 [6]. This problem has an interesting connection to the celebrated Shannon capacity in information theory. Namely, the maximum possible Shannon capacity of a graph with independence number t is equal to lim q↑↓ r(K t+1 ; q) 1/q (see e.g. [2]).

Although already for graph Ramsey numbers there are significant gaps between the lower and upper bounds, our knowledge of hypergraph Ramsey numbers is even weaker. In the clique case, Erd!s and Rado [11] showed that for some constant c = c(q, k), the Ramsey numbers satisfy r k (n; q) ↑ tw k (cn), where tw k (x) denotes the tower function defined as tw 1 (x) = x and tw k (x) = 2 tw k→1 (x) for k ↔ 2. On the other hand, an ingenious construction of Erd!s and Hajnal (see e.g. [14]), known as the stepping-up lemma, allows one to obtain a lower bound for hypergraphs of uniformity k + 1 from lower bounds for uniformity k, essentially gaining an extra exponential at every step. However, this construction only works if the number of colors, q, is at least 4 or the uniformity, k, is at least 3. Therefore, we have r k (n; 4) = tw k (!(n)) and the order of magnitude of r k (n; 2) depends on the behaviour of 3-uniform case. The question whether r 3 (n; 2) grows doubly-exponentially remains one of the most intriguing open problems. We refer the reader to the surveys [7,17] for more details about hypergraph Ramsey problems.

The focus of this work is to determine the growth rate of r(G; q) for fixed G and q tending to infinity. This is a natural variant of Erd!s' question (mentioned above) for hypergraphs. We say that a function f (q) grows as a tower of height h if tw h ("(q c )) ↑ f (q) ↑ tw h (O(q C )) for some constants c, C > 0. We study the following problem.

Problem 1.1. Given a fixed k-uniform hypergraph G, determine the integer h (if it exists) such that r(G; q) grows as a tower of height h as q tends to infinity.

Clearly, not every function grows as a tower of some height, but it might be natural to guess that this is the case for r(G; q) for any fixed k-uniform hypergraph G. As discussed above, in the graph case we have that r(G; q) grows as a tower of height 1 if G is bipartite (and has at least two edges) whereas otherwise it grows as a tower of height 2. The 3-uniform case was first studied almost 50 years ago by Abbott and Williams [1] who, using a modification of the stepping-up construction showed that r(K

4 ; q) grows as a tower of height 3. The 3-uniform case has been revisited in more depth recently by Axenovich, Gyárfás, Liu and Mubayi [4]. They observed that r(G; q) is at most polynomial, i.e. grows as a a tower of height 1 in q if and only if G is tripartite and they determined several classes of 3-graphs for which r(G; q) grows as a tower of height 2. Furthermore, they ask the following question.

Problem 1.2 ([4]

). For which 3-uniform hypergraphs G, is r(G; q) double exponential? Are there other jumps that the Ramsey function exhibits?

We resolve Problem 1.1 in the case k = 3 and answer the question of Axenovich, Gyárfás, Liu and Mubayi in following strong sense. We show that for every non-tripartite 3-uniform hypergraph G, either 2 !(q) < r(G; q) < 2 q C for some C = C(G) or 2 2 q/2 < R(G; q) and characterize which 3-graphs have which behaviour.

To state our main result formally, we first require a definition.

We say that H is obtained from G by collapsing U and that G is reducible to the pair (H, G[U ]) by collapsing U .

We define a nested sequence of sets of 3-graphs U 0 ↗ U 1 ↗ . . . as follows. First, U 0 consists of all tripartite 3-graphs. The set U 1 contains the 3-graphs for which there is a subset of vertices intersecting every edge in exactly one vertex (note that U 1 ⇓ U 0 ). For i > 1, U i is the maximal set containing U i→1 and any hypergraph which is reducible to some (H, F ) with H ≃ U i→1 , F ≃ U i . Note that if G is reducible to (H, F ), then by definition, v(H), v(F ) < v(G), implying that the sets U i are indeed well-defined. Let U := i↗0 U i . We are ready to state our main result determining the behaviour of r(G; q) for any fixed 3-graph G.

Theorem 1.4. Let G be a fixed 3-uniform hypergraph with at least two edges.

Our characterization might seem a bit unwieldy at first, but it turns out to be convenient to work with. For example, using it we can show that most Steiner triple systems have double-exponential multicolor Ramsey numbers, but there are Steiner triple systems for which it is exponential.

The rest of the paper is structured as follows. In the remainder of the introduction, we give some examples which might help understand the definition of the sets U i . We prove Theorem 1.4 in Section 2 which is split into three subsections. In the first subsection we prove the upper bounds, starting with a sketch of the main ideas, in the second we prove the lower bounds and in the third we tie all the bounds together. In Section 3, we provide examples of 3-graphs exhibiting di#erent behaviours of the multicolor Ramsey number. We finish with some concluding remarks in Section 4.

We use standard notation throughout the paper. As it appears frequently in our proofs, we denote by Star (3) (h) the 3-graph on h vertices with the edges being all triples containing a fixed vertex.

About the sets U i

In this subsection, we briefly discuss the sets U i just defined. Observe first that for all i ↔ 0, the set U i is closed under taking subgraphs. The rest of the content of this subsection is not needed for any of our proofs, but it should help clarify the definitions and facilitate understanding the rest of the paper.

First let us show that

Inside each of A and B place a copy of G i and additionally let G i+1 contain all 3-edges of the form {x, a, b}, a ≃ A, b ≃ B. See Figure 1 for an illustration. First, let us show that G i+1 ≃ U i+1 . Indeed, by collapsing A, G i+1 is reducible to (H, G i ), where we shall describe H shortly. Since G i ≃ U i , to show that G i+1 ≃ U i+1 , it su"ces to show that H ≃ U i as well. Indeed, V (H) = {x, a} ↘ B where a represents the collapsed set A. Note that H[B] ↖ = G i and the remaining e a b Figure 2: A 3-graph not in U edges of H are of the form {x, a, b} with b ≃ B. Hence, the set B is collapsible in H and thus H is reducible to (e, G i ), where e denotes the 3-graph consisting of a single edge. Since e ≃ U 0 and

On the other hand, for example the clique K

(3) 4

is not in U . Indeed, it has no collapsible set and no set of vertices such that each edge contains precisely one vertex from this set. A slightly more complicated example is the 3-graph G depicted in Figure 2. Formally, we have V (G) = {a, b, c, d, e} and E(G) = {acd, bcd, ace, bde, cde}. It can be checked that G ⇔ ≃ U 1 and that {a, b} is the only collapsible set in G. However, the 3-graph obtained by collapsing {a, b} is isomorphic to

2 Proof of Theorem 1.4

Upper bounds

Proof sketch This aim of this subsection is to prove the single-exponential upper bound in Theorem 1.4 b). Before presenting the proof formally, we illustrate our ideas on a simple example where G is the Fano plane, that is, the unique 3-graph on 7 vertices with 7 edges which all pairwise intersect in exactly one vertex.

Let U ↗ V (G) denote the vertex set of an arbitrary edge in G. Note that by the abovementioned properties of the Fano plane, every edge intersects U in either one or three vertices. Therefore, U is collapsible and G is reducible to the pair (H, F ) where H = Star (3) (5), i.e. a 4-clique in the link of a vertex, and F is a single edge. Trivially, F, H ≃ U 1 which shows that G ≃ U 2 . Though not required for the upper bound, it is easy to see that G ⇔ ≃ U 1 .

Suppose we are given a q-colored complete 3-graph # on N vertices, where N is of the form 2 O(q 2 log q) and we wish to show that there exists a monochromatic copy of G. By considering all triples through a fixed vertex it is easy to see that r(H; q) ↑ 1 + r(K of H, hence in # there are at least N R / N →5 R→5 ↔ N 5 R 5 monochromatic copies of H. By the pigeonhole principle, there is a set S ↗ V (#), |S| = 4, and a colour, say red, such that there are at least N/(qR 5 ) red copies of H = Star (3) (5) with the set S playing the role of the 4-clique. Let V ↘ denote the set of vertices playing the role of the center of the star in these copies, so |V ↘ | ↔ N/(qR 5 ).

Crucially, observe that if there is a red edge inside the set V ↘ , then these three vertices along with the set S contain a monochromatic copy of G that we aim to find. Therefore, V ↘ is colored by q ↓ 1 colors. Iterating this argument inside V ↘ , we see that it su"ces to take N ↔ 3(qR 5 ) q = 2 O(q 2 log q) , as claimed.

For general G, the argument is a little more complicated. Suppose that G ≃ U ε and it is reducible to (H, F ) for some H ≃ U ε→1 , F ≃ U ε and let U ↗ V (G) be the collapsible set witnessing this. By a supersaturation argument analogous to the one above, we find a large set V ↘ ↗ V (#) of vertices that can play the role of v ↔ ≃ V (H) with the same set S in the same color, say red. Then, however, inside the set V ↘ , we obtain that there is no red copy of F. In the case where G is the Fano plane, F is a single edge, which makes the argument simpler since we only need to ensure that |V ↘ | ↔ r(G; q ↓ 1). In general, we shall require that |V ↘ | is at least the o#-diagonal Ramsey number r(F, G, G, . . . , G), where G appears q ↓ 1 times.

We proceed with the formal proof. We start with the supersaturation argument outlined above, which allows us to reduce the target hypergraph in one of the colors. Lemma 2.1. Let G 1 , . . . , G q be given 3-graphs. For i ≃ [q], let (H i , F i ) be an arbitrary pair to which G i is reducible and if no such pair exists, let

Proof. For convenience, to each graph H i we add isolated vertices so that it has h vertices which clearly does not change the value of r(H 1 , . . . , H q ). Denote R := r(H 1 , . . . , H q ) and N = r(H 1 , . . . , H q ) h • q • max {{1} ↘ {r(G 1 , . . . , G i→1 , F i , G i+1 , . . . , G q ) | G i is reducible}} and consider an arbitrary q-coloring of K

(3) N . Let # denote this q-colored 3-graph. By definition, any set of R vertices of # contains a copy of H i in color i for some i ≃ [q]. Any such copy is contained in N →h R→h sets of R vertices, so in total there are at least

. For such a copy, let v ↔ , v 1 , . . . , v h→1 denote its vertices with v ↔ playing the role of the special vertex as in Definition 1.3 or an arbitrary vertex of

By the pigeonhole principle, there is a color c ≃ [q] and an (h ↓ 1)-tuple of vertices S = (w 1 , . . . , w h→1 ) for which there are at least

N qR h copies of H c in color c with w 1 , . . . , w h→1 , in this order, playing the role of all vertices in of H i except v ↔ . If H c = G c , we are done. Otherwise, let V ↘ ↗ V (#) denote the set of vertices playing the role of v ↔ in these copies, so |V ↘ | ↔ N qR h . Crucially, we claim that if there is a copy of F c in color c inside #[V ↘ ], this yields the desired copy of G c in color c in #. Indeed, suppose there is such a copy in V ↘ and let T ↗ V ↘ denote its vertex set.

Without loss of generality, we have for any v ≃ V ↘ , the vertices {v, w 1 , . . . , w m } form a copy of H c where v is mapped to v ↔ and w i is mapped to x i for every i ≃ [m].

Then, T ↘ {w 1 , . . . , w m } forms a red copy of G c with T being mapped to U and w i being mapped to x i for i ≃ [m]. To see this, note first that by assumption, T contains a red copy of

and since the vertices v, w 1 , . . . , w m , for an arbitrary v ≃ V ↘ , form a red copy of H c , it follows that the edge w i w j w k is red in # as needed. Finally, by definition of a collapsible set, any other edge e ≃ E(G c ) intersects U c in exactly one vertex. Consider such an edge e = ux i x j with u ≃ U c . Then, we have v ↔ x i x j ≃ E(H c ). Recall that u ≃ V (F c ) so in the assumed red copy of F c , it is mapped to some vertex v ≃ T ↗ V ↘ . Since v ≃ V ↘ , the vertices v, w 1 , . . . , w m form a red copy of H c with v mapped to v ↔ and w i mapped to x i for i ≃ [m]. In particular, this implies that the edge vw i w j is red in #, as required.

By our choice of N, we have

. . G q ) so on V ↘ we either find a copy of G i in color i for i ≃ [q] \ {c} or a copy of F c in color c, thus finishing the proof.

To prove the upper bound in Part b) of Theorem 1.4, we use the preceding lemma and apply induction.

Lemma 2.2. Let ε ↔ 1 and let G 1 , . . . , G q ≃ U ε be 3-graphs each on at most h vertices and denote

Proof. We prove the lemma by induction on ε, h, t. We assume h ↔ 3, otherwise there is nothing to prove. Consider first ε = 1 and recall that by definition, each of the graphs G i has a subset of vertices U i intersecting every edge in precisely one vertex. For every i for which

denote the resulting pair of graphs obtained by collapsing U i . Note that F i is the empty graph on |U i | vertices and

. Consider a q-colored 3-uniform clique. In order to find a copy of Star (3) (s i ) in color i for some i, we can fix an arbitrary vertex v and then in its link find a graph clique of size s i in color i. Thus, we can use a classical result in graph Ramsey theory, r 2 (n 1 , . . . , n q ) < q q i=1 n i , to obtain that r(H 1 , . . . , H q ) ↑ q

where in the last inequality we used h ↔ 3.

Now, let ε > 1 and assume we have proved the statement for all sequences of graphs in U ε→1 as well as all sequences of graphs in U ε each on at most h vertices with in total at most t ↓ 1 vertices. Clearly, we may assume that

For each i such that G i is not reducible, let H i = G i . Applying Lemma 2.1 and the induction hypothesis, we have

where in the last inequality we used that t ↑ qh. Corollary 2.3. If G ≃ U ε , then r(G; q) ↑ 2 O(q ω log q) .

Applying Lemma 2.2 with

Lower bounds

Definition 2.4. Let G be a 3-uniform hypergraph. Suppose there is a partition of its vertex set

|V 1 |, t ↔ 2 such that for any edge e ≃ E(G), and any i ≃ [t], we have |e

and let H be the 3-uniform hypergraph obtained by collapsing each of the sets V i into a single vertex. Formally,

We say that G can be decomposed into (H; F 1 , . . . , F t ).

In our proofs of the lower bounds, Definition 2.4 will play a similar role that Definition 1.3 played in the proofs of the upper bounds. By taking

informally speaking, we recover the definition of reducibility. On the other hand, a reduction with t parts can, in some sense, be viewed as a sequence of at most t simple reductions. Formally, we have the following lemma.

Lemma 2.5. If G can be decomposed into (H; F 1 , . . . , F t ), where H, F 1 , . . . , F t ≃ U, then G ≃ U.

↘V t be the partition exhibiting that G can be decomposed into (H; F 1 , . . . , F t ). Without loss of generality, assume that |V i | ↔ 2 for i ≃ [s] and |V i | = 1 for s + 1 ↑ i ↑ t. Denote G 0 = G and for i = 1, . . . , s, let G i be obtained from G i→1 by collapsing V i . Note that these collapses are valid since a set V i remains collapsible after collapsing a disjoint set V j , j < i. The final graph G s is isomorphic to H, hence G s ≃ U. By definition, for each

Hence, by reverse induction, it follows that G s→1 , . . . , G 0 = G are also in U , as claimed.

Our lower bound constructions are based on the stepping-up approach of Erd!s and Hajnal. First, we recall an important function used in this construction. For a nonnegative integer x, let x = ↓ i=0 a i 2 i be its unique binary representation (where a i = 0 for all but finitely many i). We denote bit(x, i) := a i . Then for distinct x, y ≃ Z ↗0 , we define ϑ(x, y) := max{i ≃ Z ↗0 | bit(x, i) ⇔ = bit(y, i)}. See Figure 3 for an illustration. is given by the highest line between x and y on the picture. So, for example, ϑ(0, 1) = ϑ(6, 7) = 0, ϑ(0, 3) = ϑ(5,

The following properties of this function are well known and easy to verify. P1) x < y ↙∝ bit(x, ϑ(x, y)) < bit(y, ϑ(x, y)).

of i and using Property P3) so ϖ(x j x k x i+1 ) = (t, 0). In ϖ, there clearly exists a monochromatic copy of the induced subgraph G[{v i+1 , . . . , v h }] so both H and G[{v i+1 , . . . , v h }] are in U by the induction hypothesis. It follows that G ≃ U, as needed.

Finally, suppose that m ⇔ = t. If m < t, then by ( 1), no edge is colored (t, 0), so we assume m > t. Let 1 ↑ i 1 < • • • < i p < h denote all indices i for which bit(ϑ i , m) = 1 and note that 2 ↑ p + 1 ↑ h. Let I 1 , . . . , I p+1 denote the intervals between consecutive i ↘ j s. Formally, let I 1 = {1, . . . , i 1 }, for 2 ↑ j ↑ p, let I j = {i j→1 + 1, . . . , i j } and let I p+1 = {i p + 1, . . . , h}.

Suppose that there is an edge e = uvw ≃ E(G) with 1 ↑ u < v < w ↑ h and j ≃ [p + 1] such that |e ⇐ I j | = 2. Since I j is an interval, we have either e ⇐ I j = {u, v} or e ⇐ I j = {v, w}. In the former case, by the definition of I j , using (2), we have bit(ϑ(x u , x v ), m) = 0 and bit(ϑ(x v , x w ), m) = 1, which implies ϖ(e) = (m, 0). Completely analogously, in the latter case we obtain ϖ(e) = (m, 1). Both cases contradict our assumptions, so we conclude that for any e ≃ E(G) and j ≃ [p + 1], it holds that |e ⇐ I j | ⇔ = 2.

Furthermore, let H be the hypergraph on the vertex set {1, . . . , p + 1} with edges {uvw | ⇑e ≃ G, |e ⇐ I u | = |e ⇐ I v | = |e ⇐ I w | = 1}. By definition, the hypergraphs H, F 1 , . . . , F p+1 have fewer vertices than H. Hence, G is decomposable into (H; F 1 , . . . , F p+1 ). By the induction hypothesis, F 1 , . . . , F p+1 ≃ U since the vertices {x u | u ≃ I j } form a copy of F j in color (t, 0) by assumption. For j ≃ [p+1], let y j = x min I j . Next we show that {y 1 , . . . , y p+1 } contains a monochromatic copy of H in color (t, 0). Indeed, consider the embedding which maps i ≃ V (H) = [p + 1] into y i . Consider an arbitrary edge uvw ≃ E(H) with 1 ↑ u < v < w ↑ p + 1. Recall that by definition there is a corresponding edge abc ≃ E(G) with a ≃ I u , b ≃ I v , c ≃ I w . By (1) and the definition of i 1 , . . . , i p , we have ϑ(y u , y v ) = ϑ(x min Iu , x min Iv ) = max min Iu⇐j<min Iv

and analogously ϑ(y v y w ) = ϑ(x b , x c ). Hence, ϖ(y u y v y w ) = ϖ(x a x b x c ) = (t, 0). Thus the claimed embedding is indeed monochromatic so, by the induction hypothesis, we have H ≃ U, which, using Lemma 2.5 implies that G ≃ U as well.

An exponential lower bound for non-tripartite 3-uniform hypergraphs was proved in [4], but we include a proof for the sake of completeness.

Lemma 2.7. If G is a non-tripartite 3-uniform hypergraph, then r(G; q) = 2 !(q) .

Proof. Let N = 2 2q/27 and consider q random copies of the complete balanced tripartite 3-uniform hypergraph, which has at least 2 9 N 3 edges, and define ϖ to be the coloring where each triple of K

N is colored by the index of the first copy in which it appears. Since each color induces a tripartite graph, there is no copy of G. It remains to show that with positive probability all edges are colored. Indeed, by a union bound, the probability that not all edges are colored is at most N 3 (1 ↓ 2/9) q < N 3 e →2q/9 < 1, as needed.

Putting it together

Proof of Theorem 1.4. The lower bound in Part a) is obtained by coloring edges of a complete 3-uniform hypergraph on "(q 1/3 ) vertices into distinct colors. For the upper bound, if G is tripartite, by a well

Assume the color of this copy is (j, 0) or (j, 1), for some j ≃

Thus in either case, we have G ≃ L 1 . Now suppose the color of this monochromatic copy is c ≃ [q]. Let j be the first coordinate in which x 1 , . . . , x h are not all equal. Then, there is a partition of the vertex set

empty sets such that the vertices V i correspond to vectors with the same j-th coordinate. Let H be the hypergraph with vertex set [m] and edge set

It is easy to see that there is a monochromatic copy of H in ϖ, and hence H is tripartite. Additionally, for all j ≃ [m], there trivially exists a monochromatic copy of G[V j ] in ϖ ↘ and hence G[V j ] ≃ L 1 by the induction hypothesis. It follows that G ≃ L 1 , as required.

Proposition 3.3. There is a 3-uniform hypergraph G for which r(G; q) = 2 q 2+o (1) .

Proof. Let G be the 3-uniform hypergraph obtained by blowing up a non-central vertex of Star (3) (4) by a set A of 4 vertices and placing a copy of Star (3) (4) inside A. Let v, a 1 , a 2 , a 3 denote the vertices of A with v being the center and let u, b 1 , b 2 denote the remaining vertices with u being the center.

By collapsing the set A we see that G is reducible to (Star (3) (4), Star (3) (4)) implying that G ≃ U 2 and thus the upper bound follows by Corollary 2.3.

Next we show that G ⇔ ≃ L 1 and then the lower bound follows from Lemma 3.2. First, suppose that G is forward-colorable and let

with center u, we have that b 1 , b 2 ≃ V i and u ≃ V ε for some ε < i. But, then the edge ub 1 a 1 has its vertices in three distinct sets, a contradiction. Now, suppose that G is decomposable into (H; F 1 , . . . , F t ) with a partition

Note that if S is a nonempty subset of V (Star (3) (4)) such that any edge of Star (3) (4) contains either 1 or 3 vertices of S, then either |S| = 1 or |S| = 4. Suppose that some V i contains at least two vertices from v, u, b 1 , b 2 . Since these vertices form a star, by the previous observation, it follows that V i contains all of them. Furthermore, since any w ≃ A forms a copy of Star (3) (4) with {u, b 1 , b 2 }, by the same observation, we get

Let G (3) (n, p) denote the random 3-uniform hypergraph on n vertices where each hyperedge is included independently with probability p. Proposition 3.4. There is a positive constant C such that if p ↔ C n 2 , then for G ↖ G (3) (n, p), with high probability, we have r(G; q) ↔ 2 2 q/2 . Proof. Using a standard Cherno# bound (see e.g. [3]), it is easy to show that with high probability,

Conditioning on (4), we show that G ⇔ ≃ U, which would complete the proof by Lemma 2. By assumption, we have G 2 ≃ U so we can apply the same reasoning as above. In general, at each step we have a hypergraph G i whose each vertex corresponds to a collapsed set or a single vertex in G. Now, suppose that at some point we have in total put aside a set T of at least n/100 vertices. Since we never put aside more than half of the current number of vertices, we have |T | < 0.99n so by (4), in G there is an edge with two vertices in V (G) \ T and one vertex in T. However this contradicts the fact that we only put aside vertices outside some collapsible set.

Similarly, we can show that no vertex in V (G i ) represents a set of more than n/100 vertices of G. Indeed, if in some step we collapse a set U ↗ V (G i ) representing in total at least n/100 vertices of G but no more than 0.99n, by (4), in G there is an edge with two vertices represented by U and one vertex not represented by U, a contradiction.

On the other hand, if no vertex of G i represents more than n/100 vertices, we can group the vertices of G i into four sets, where each set represents a set of at least n/100 vertices of G, which, by (4), implies that G i ⇔ ≃ U 1 . Therefore, for any i, G i we can define a new hypergraph G i+1 as above. However, clearly this process cannot go on indefinitely, which will yield a contradiction.

We proceed to the formal proof. For the sake of contradiction, suppose G ≃ U. Now, we run the following algorithm in steps i = 1, . . . At each step, we have a set T i ↗ V (G), and a hypergraph G i , where each vertex v ≃ V (G i ) is labelled with a set S i (v) ↗ V (G) such that the sets

The hypergraph G i will correspond to a hypergraph obtained from G after several reductions and a set S i (v) indicates that v is a vertex representing the collapsed set (possibly in more than one step) S i (v). Formally, we always have

For U ↗ V (G i ), we denote S i (U ) = v≃U S i (v) and we denote its weight by w i (U ) = |S i (U )|. We shall maintain the following:

(ii) For any v ≃ V (G i ), w i ({v}) < n/100. (iv) For any e ≃ E(G) and any

Initially, we set G 1 = G, S 1 (v) = {v}, ′v ≃ V (G) and T 1 = ⇒. Then, we proceed in steps i = 1, . . . as follows.

By assumption, G i ≃ U. Suppose first that G i ≃ U 1 , that is, there is a subset W ↗ V (G i ) such that any edge in G i intersects W in exactly one vertex. Hence, either W or V (G i ) \ W is an independent set in G i with weight at least n/4. Let I denote this independent set. Since w({v}) < n/100 for any v ≃ V (G i ), I can be partitioned into three sets

and the hypergraph H obtained by collapsing U i is also in U . We consider two cases. First, suppose that w i (U i ) ↑ n/2. Let us show that then |w i (U i )| < n/100. Otherwise by (4), G has an edge in S

. Such an edge cannot have two vertices in the same set S i (v) by Property (iv). On the other hand, if all three of its vertices lie in di#erent sets S i (v), this contradicts that U i is collapsible in G i , so indeed we have |w i (U i )| < n/100. Now, we let G i+1 be the hypergraph obtained from G i by collapsing U i and let

Let us verify that Propeties (i)-(iv) for i + 1. Property (i) holds by assmption, (ii) still holds because w i (U i ) < n/100, (iii) is immediate since T i+1 = T i and finally, Property (iv) holds since U i is a collapsible set in G i .

Secondly, suppose that w

Let us verify the invariants. Property (i) is given by the assumption, while properties (ii) and (iv) are immediate since

). Let us check Property (iii). Suppose first there is an edge e ≃ E(G) such that |e ⇐ T i | = 1. Then, it has two vertices inside S i (U i ) and by Property (iv), these two vertices are in distinct sets S i (v), S i (v ↘ ). However, this contradicts the fact that U i is collapsible in G i , proving the second part of (iii). Finally, we show that |T i+1 | < n/100. Suppose otherwise. Recall that G has no edges touching T i in exactly one vertex. Since U i is collapsible in G i , it follows that G has no edges touching T i+1 in exactly one vertex either. However, we have that n/100 ↑ |T i+1 | ↑ n/2, which yields a contradiction to (4) by taking the sets V

To conclude, in each step i = 1, . . . we obtain a new hypergraph G i+1 still satisfying all the invariants. However, we always have |V (G i+1 )| < |V (G i )| so the process cannot run indefinitely, a contradiction.

We remark that considering the process of collapsing sets is in some sense necessary in the proof above. Indeed, one might hope to prove Proposition 3.4 by finding a fixed hypergraph H ⇔ ≃ U such that H appears in G ↖ G (3) (n, C/n 2 ) with high probability. This is however not possible. Indeed, for any fixed k, the expected number of sets of 2k vertices spanning at least k edges is O(n 2k p k ) = O(C k ). By the Poisson paradigm, it follows that with probability "(1), G does not have 2k vertices spanning at least k edges for any fixed k. Thus, every subgraph H of G on at most 2k vertices has an edge whose all but at most one vertex has degree one in H. Collapsing this edge we get a new hypergraph, again having ratio less than 1/2 between number of edges and vertices and therefore we can continue collapsing. This implies that with positive probability G does not contain a fixed hypergraph not in U .

Note that the only property of the random 3-uniform hypergraph we used in the proof of Proposition 3.4 is (4), i.e. that for any three sets of size at least n/100, there is an edge with a vertex in each of the sets. The same property holds for most Steiner triple systems. This was proven in a stronger form implicitly by Kwan [16] and later stated by Ferber and Kwan [13,Theorem 8.1]. Therefore we obtain the following corollary.

Corollary 3.5. A random Steiner triple systems with high probability has double-exponential multicolor Ramsey numbers.

However, this is not the case for all Steiner triple systems. Indeed, let m ↔ 2, and consider the Steiner triple system G on the vertex set V (G) = F m 2 \ {0} where a triple xyz forms an edge if and only if x + y + z = 0. For i ≃ [m], let V i be the set of vectors in V (G) whose last 1-coordinate is in the i-th place. The partition

shows that G is forward-colorable, and hence r(G; q) ↑ 2 O(q 2 log q) by the upper bound in Theorem 1.4 part b).

Concluding remarks

In this paper we determined, for any fixed 3-uniform hypergraph G, the tower height of its multicolor Ramsey number r(G; q) as the number of colors tends to infinity. Several natural questions remain. The most obvious one is to resolve Problem 1.1 for higher uniformities. We tentatively conjecture that the multicolor Ramsey number of any fixed uniform hypergraph grows as a tower of some height. A counterexample would be very interesting.

Our methods do not seem to provide tight bounds for larger uniformities. For example, we do not know the correct answer even for the following 4-uniform hypergraph: let G be the 4-uniform hypergraph with vertex set A ↘ B where A, B are disjoint sets of some fixed size t ↔ 3 and where a 4-tuple forms an edge if and only if it intersects A and B in two vertices each. Since G is not 4-partite, r(G; q) is at least exponential in q as shown in [4] and we can show that r(G; q) is at most double-exponential.

For 3-uniform hypergraphs G ≃ U, our upper and lower bounds usually have di#erent powers of q in the exponent. It would be interesting to refine these bounds further. A natural simple example is the Fano plane for which we have 2 !(q) ↑ r(Fano; q) ↑ 2 O(q 2 log q) . It is easy to see that r(Star (3) (4); q) = 2 q 1+o(1) and Proposition 3.3 provides a 3-uniform hypergraph G with r(G; q) = 2 q 2+o(1) . However, for each ε ↔ 3, there are 3-uniform hypergraphs G ε for which our best upper bound is of the form r(G ε ; q) ↑ 2 q ω+o (1) . It would be interesting to determine whether this can be tight.

Problem 4.1. Does there exist, for every ε ↔ 1, a 3-uniform hypergraph G ε with r(G ε ; q) = 2 q ω+o(1) ?