
==== Front
Res Math Sci
Res Math Sci
Research in the Mathematical Sciences
2522-0144
2197-9847
Springer International Publishing Cham

39027703
463
10.1007/s40687-024-00463-w
Research
The growth rate of multicolor Ramsey numbers of 3-graphs
Bradač Domagoj 1
Fox Jacob 2
http://orcid.org/0000-0003-3307-9475
Sudakov Benny benjamin.sudakov@math.ethz.ch

1
1 https://ror.org/05a28rw58 grid.5801.c 0000 0001 2156 2780 Department of Mathematics, ETH Zürich, Zürich, Switzerland
2 https://ror.org/00f54p054 grid.168010.e 0000 0004 1936 8956 Department of Mathematics, Stanford University, Stanford, CA USA
16 7 2024
16 7 2024
2024
11 3 5215 1 2024
27 6 2024
© The Author(s) 2024
2024
https://creativecommons.org/licenses/by/4.0/ Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
The q-color Ramsey number of a k-uniform hypergraph G,  denoted r(G; q), is the minimum integer N such that any coloring of the edges of the complete k-uniform hypergraph on N vertices contains a monochromatic copy of G. The study of these numbers is one of the most central topics in combinatorics. One natural question, which for triangles goes back to the work of Schur in 1916, is to determine the behavior of r(G; q) for fixed G and q tending to infinity. In this paper, we study this problem for 3-uniform hypergraphs and determine the tower height of r(G; q) as a function of q. More precisely, given a hypergraph G, we determine when r(G; q) behaves polynomially, exponentially or double exponentially in q. This answers a question of Axenovich, Gyárfás, Liu and Mubayi.

http://dx.doi.org/10.13039/501100001711 Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung 200021_196965 Sudakov Benny issue-copyright-statement© Springer Nature Switzerland AG 2024
==== Body
pmcIntroduction

Given k-uniform hypergraphs, or k-graphs, G1,⋯,Gq, let r(G1,⋯,Gq) denote their Ramsey number, which is the minimum positive integer N such that in every coloring of the edges of the complete k-graph KN(k) on N vertices with color set [q]={1,…,q} there is a color i for which there is a monochromatic copy of Gi in color i. When G1=⋯=Gq=G, we write r(G; q),  and when G=Kn(k), we sometimes write rk(n;q). The existence of these numbers was famously proved by Ramsey [19] in 1930. Since then, obtaining good bounds on rk(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, r2(n;2), for which the current best bounds are 2n<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, Griffiths, 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(qC) 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 n2-ε edges contains a copy of G. On the other hand, if G is not bipartite, then we have r(G;q)>2q. 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 differ. 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 neighbor chasing argument of Erdős and Szekeres [12] yields r(Kn;q)<qnq. Hence, for fixed non-bipartite G,  we have (2+ϵ)q≤r(G;q)≤2O(qlogq). Determining whether these numbers should be exponential or not is a very old and major open problem even for the simplest case when G=K3 for which Erdős offered 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 limq→∞r(Kt+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 rk(n;q)≤twk(cn), where twk(x) denotes the tower function defined as tw1(x)=x and twk(x)=2twk-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 rk(n;4)=twk(Θ(n)) and the order of magnitude of rk(n;2) depends on the behavior of 3-uniform case. The question whether r3(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 twh(Ω(qc))≤f(q)≤twh(O(qC)) 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(K4(3);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 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)<2C for some C=C(G) or 2q/2<R(G;q) and characterize which 3-graphs have which behavior.

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

Definition 1.3

Let G be a 3-graph. A set U⊆V(G) with 2≤|U|<|V(G)| is called collapsible if no edge of G intersects U in exactly two vertices. Let v∗ denote a new vertex and let H be the 3-graph with vertex set (V(G)\U)∪{v∗} and edge set E(H)={e∈E(G)|e∩U=∅}∪{xyv∗|∃u∈U,xyu∈E(G)}. 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 U0⊆U1⊆⋯ as follows. First, U0 consists of all tripartite 3-graphs. The set U1 contains the 3-graphs for which there is a subset of vertices intersecting every edge in exactly one vertex (note that U1⊇U0). For i>1, Ui is the maximal set containing Ui-1 and any hypergraph which is reducible to some (H, F) with H∈Ui-1,F∈Ui. Note that if G is reducible to (H, F),  then by definition, v(H),v(F)<v(G), implying that the sets Ui are indeed well defined. Let U:=⋃i≥0Ui.

We are ready to state our main result determining the behavior 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. If G∈U0 (i.e., G is tripartite), then r(G;q)=qΘ(1).

If G∈U\U0, then 2Ω(q)≤r(G;q)≤2O(1). More precisely, if G∈Uℓ, then r(G;q)≤2O(qℓlogq).

If G∉U, then 2q/2≤r(G;q)≤2O(qlogq).

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 Ui. We prove Theorem 1.4 in Sect. 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 Sect. 3, we provide examples of 3-graphs exhibiting different behaviors of the multicolor Ramsey number. We finish with some concluding remarks in Sect. 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 Ui

In this subsection, we briefly discuss the sets Ui just defined. Observe first that for all i≥0, the set Ui 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 Ui\Ui-1≠∅ for all i≥1. It is easy to see that Star(3)(4)∈U1\U0. Now, let i≥1 and suppose there is some Gi∈Ui\Ui-1. We define Gi+1 as follows. The vertex set of Gi+1 is where |A|=|B|=|V(Gi)|. Inside each of A and B place a copy of Gi and additionally let Gi+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 Gi+1∈Ui+1. Indeed, by collapsing A,  Gi+1 is reducible to (H,Gi), where we shall describe H shortly. Since Gi∈Ui, to show that Gi+1∈Ui+1, it suffices to show that H∈Ui as well. Indeed, V(H)={x,a}∪B where a represents the collapsed set A. Note that H[B]≅Gi and the remaining 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,Gi), where e denotes the 3-graph consisting of a single edge. Since e∈U0 and Gi∈Ui, it follows that H∈Ui, as claimed.

Now, we show that Gi+1∉Ui. We claim that any collapsible set in Gi+1 intersects at most one of A, B. Indeed, suppose that U is collapsible in Gi+1 and contains a vertex a∈A and a vertex b∈B. Since {x,a,b}∈E(Gi+1), we must have x∈U. However, since {x,a,b′}∈E(Gi+1) for any b′∈B, it follows that B⊆U and analogously A⊆U, so U=V(Gi+1), a contradiction. Now, suppose that Gi+1 is reducible to (H, G[U]) by collapsing some set U. Without loss of generality, U∩B=∅, so Gi≅Gi+1[B]⊆H, implying that H∈Ui. As U was arbitrary, we have that Gi+1∉Ui.

On the other hand, for example, the clique K4(3) 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∉U1 and that {a,b} is the only collapsible set in G. However, the 3-graph obtained by collapsing {a,b} is isomorphic to K4(3), so G∉U.Fig. 1 Construction of Gi+1

Fig. 2 A 3-graph not in U

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 above-mentioned 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∈U1 which shows that G∈U2. Though not required for the upper bound, it is easy to see that G∉U1.

Suppose we are given a q-colored complete 3-graph Γ on N vertices, where N is of the form 2O(q2logq), 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(K4(2);q)≤q4q using the classical bound of Erdős and Szekeres. Let R=r(H;q). By definition, every set of R vertices contains a monochromatic copy of H;  hence, in Γ there are at least NR/N-5R-5≥N5R5 monochromatic copies of H. By the pigeonhole principle, there is a set S⊆V(Γ), |S|=4, and a color, say red, such that there are at least N/(qR5) 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/(qR5).

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 suffices to take N≥3(qR5)q=2O(q2logq), 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 off-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 G1,⋯,Gq be given 3-graphs. For i∈[q], let (Hi,Fi) be an arbitrary pair to which Gi is reducible and if no such pair exists, let Hi=Gi. Denoting h=maxi∈[q]v(Hi), we haver(G1,⋯,Gq)≤r(H1,⋯,Hq)h·q·max{1}∪{r(G1,⋯,Gi-1,Fi,Gi+1,⋯,Gq)|Giis reducible}.

Proof

For convenience, to each graph Hi we add isolated vertices so that it has h vertices which clearly does not change the value of r(H1,⋯,Hq). Denote R:=r(H1,⋯,Hq) and N=r(H1,⋯,Hq)h·q·max{1}∪{r(G1,⋯,Gi-1,Fi,Gi+1,⋯,Gq)|Giis reducible} and consider an arbitrary q-coloring of KN(3). Let Γ denote this q-colored 3-graph.

By definition, any set of R vertices of Γ contains a copy of Hi in color i for some i∈[q]. Any such copy is contained in N-hR-h sets of R vertices, so in total there are at leastNR/N-hR-h≥NhRh

distinct h-sets of V(Γ) each of which is a monochromatic copy of Hi in color i for some i∈[q]. For such a copy, let v∗,v1,⋯,vh-1 denote its vertices with v∗ playing the role of the special vertex as in Definition 1.3 or an arbitrary vertex of Hi if Hi=Gi. By the pigeonhole principle, there is a color c∈[q] and an (h-1)-tuple of vertices S=(w1,⋯,wh-1) for which there are at leastNhRh/(qNh-1)=NqRh

copies of Hc in color c with w1,⋯,wh-1, in this order, playing the role of all vertices in of Hi except v∗. If Hc=Gc, we are done. Otherwise, let V′⊆V(Γ) denote the set of vertices playing the role of v∗ in these copies, so |V′|≥NqRh.

Crucially, we claim that if there is a copy of Fc in color c inside Γ[V′], this yields the desired copy of Gc in color c in Γ. Indeed, suppose there is such a copy in V′ and let T⊆V′ denote its vertex set. Let Uc⊆V(Gc) be the collapsible set such that Gc is reducible to (Hc,Fc) by collapsing Uc and let V(Gc)\Uc={x1,⋯,xm}. So by definition, V(Hc)={v∗,x1,⋯,xm}. Without loss of generality, we have for any v∈V′, the vertices {v,w1,⋯,wm} form a copy of Hc where v is mapped to v∗ and wi is mapped to xi for every i∈[m].

Then, T∪{w1,⋯,wm} forms a red copy of Gc with T being mapped to U and wi being mapped to xi for i∈[m]. To see this, note first that by assumption, T contains a red copy of Fc=Gc[U]. Furthermore, any edge e=xixjxk∈E(Gc) disjoint from Uc is contained in Hc, and since the vertices v,w1,⋯,wm, for an arbitrary v∈V′, form a red copy of Hc, it follows that the edge wiwjwk is red in Γ as needed. Finally, by definition of a collapsible set, any other edge e∈E(Gc) intersects Uc in exactly one vertex. Consider such an edge e=uxixj with u∈Uc. Then, we have v∗xixj∈E(Hc). Recall that u∈V(Fc) so in the assumed red copy of Fc, it is mapped to some vertex v∈T⊆V′. Since v∈V′, the vertices v,w1,⋯,wm form a red copy of Hc with v mapped to v∗ and wi mapped to xi for i∈[m]. In particular, this implies that the edge vwiwj is red in Γ, as required.

By our choice of N,  we have |V′|≥r(G1,⋯,Gc-1,Fc,Gc+1,⋯Gq) so on V′ we either find a copy of Gi in color i for i∈[q]\{c} or a copy of Fc 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 G1,⋯,Gq∈Uℓ be 3-graphs each on at most h vertices and denote t=∑i=1qv(Gi). Then,r(G1,⋯,Gq)≤(qh)qℓ-1·h2ℓt.

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 Gi has a subset of vertices Ui intersecting every edge in precisely one vertex. For every i for which |Ui|>1, let (Hi,Fi) denote the resulting pair of graphs obtained by collapsing Ui. Note that Fi is the empty graph on |Ui| vertices and Hi is a subgraph of Star(3)(v(Gi)-|Ui|+1). If |Ui|=1, then let Hi=Gi which is again a subset of a star Star(3)(v(Gi)-|Ui|+1). Consider a q-colored 3-uniform clique. In order to find a copy of Star(3)(si) in color i for some i,  we can fix an arbitrary vertex v and then in its link find a graph clique of size si in color i. Thus, we can use a classical result in graph Ramsey theory, r2(n1,⋯,nq)<q∑i=1qni, to obtain that r(H1,⋯,Hq)≤q∑i=1qv(Gi)-|Ui|+1. Note that if |Ui|>1, then r(G1,⋯,Gi-1,Fi,Gi+1,Gr)≤v(Fi)≤h since Fi has no edges. Applying Lemma 2.1, we obtainr(G1,⋯,Gq)≤(q∑i=1qv(Gi)-|Ui|+1)h·q·h≤qht+1h≤(qh)h2t,

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 G1∈Uℓ\Uℓ-1. For each i∈[q] such that Gi is reducible, let (Hi,Fi) be a pair with Hi∈Uℓ-1,Fi∈Uℓ to which Gi is reducible and recall that v(Hi),v(Fi)<v(Gi). For each i such that Gi is not reducible, let Hi=Gi. Applying Lemma 2.1 and the induction hypothesis, we haver(G1,⋯,Gq)≤r(H1,⋯,Hq)h·q·max{1}∪{r(G1,⋯,Gi-1,Fi,Gi+1,⋯,Gq)|Giis reducible}≤(qh)qℓ-2h2ℓ-2(t-1)h·q·(qh)qℓ-1h2ℓ(t-1)≤(qh)qℓ-1h2ℓ·(t-1qh+1qh+t-1)≤(qh)qℓ-1h2ℓ·t,

where in the last inequality we used that t≤qh. □

Applying Lemma 2.2 with G1=⋯=Gq=G, we obtain the upper bound claimed in Theorem 1.4,  Part b).

Corollary 2.3

If G∈Uℓ, then r(G;q)≤2O(qℓlogq).

Lower bounds

Definition 2.4

Let G be a 3-uniform hypergraph. Suppose there is a partition of its vertex set with |V1|,t≥2 such that for any edge e∈E(G), and any i∈[t], we have |e∩Vi|≠2. For i∈[t], let Fi:=G[Vi] and let H be the 3-uniform hypergraph obtained by collapsing each of the sets Vi into a single vertex. Formally, V(H)=[t] and E(H)={xyz|∃e∈E(G),|e∩Vx|=|e∩Vy|=|e∩Vz|=1}. We say that G can be decomposed into (H;F1,⋯,Ft).

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 V1=U and |V2|=⋯=|Vt|=1, 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;F1,⋯,Ft), where H,F1,⋯,Ft∈U, then G∈U.

Proof

Let be the partition exhibiting that G can be decomposed into (H;F1,⋯,Ft). Without loss of generality, assume that |Vi|≥2 for i∈[s] and |Vi|=1 for s+1≤i≤t. Denote G0=G and for i=1,⋯,s, let Gi be obtained from Gi-1 by collapsing Vi. Note that these collapses are valid since a set Vi remains collapsible after collapsing a disjoint set Vj,j<i. The final graph Gs is isomorphic to H, hence Gs∈U. By definition, for each 0≤i≤s-1, Gi is reducible to (Gi+1,G[Vi+1]), where G[Vi+1]=Fi+1∈U. Hence, by reverse induction, it follows that Gs-1,⋯,G0=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∞ai2i be its unique binary representation (where ai=0 for all but finitely many i). We denote bit(x,i):=ai. 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.Fig. 3 It is convenient to think about the function δ in the following way. The value of δ(x,y) is given by the highest line between x and y on the picture. So, for example, δ(0,1)=δ(6,7)=0, δ(0,3)=δ(5,6)=1,δ(3,4)=δ(2,7)=2.

The following properties of this function are well known and easy to verify. x<y⟺bit(x,δ(x,y))<bit(y,δ(x,y)).

For any x<y<z, δ(x,y)≠δ(y,z).

For any x1<x2<⋯<xk, δ(x1,xk)=max1≤i≤k-1δ(xi,xi+1).

For every even q, we define a q-coloring ϕq of a complete 3-uniform hypergraph on the vertex set {0,⋯,Nq-1}, where Nq:=2q/2. For 0≤x<y<z<Nq, letϕq(x,y,z):=δ(δ(x,y),δ(y,z)),1{δ(x,y)>δ(y,z)}.

For example, δ(1,4)=2,δ(4,6)=1 and δ(2,1)=1, so ϕq(1,4,6)=(1,1).

By P2), we have δ(x,y)≠δ(y,z) so ϕq is well defined. Additionally, note that δ(x,y),δ(y,z)<2q/2, implying 0≤δ(δ(x,y),δ(y,z))≤q/2-1, so ϕq indeed uses at most q colors.

We are ready to prove our double-exponential lower bound.

Lemma 2.6

For any even q,  if ϕq contains a monochromatic copy of a 3-graph G,  then G∈U.

Proof

We prove the lemma using induction on |V(G)|. For |V(G)|<3, there is nothing to prove.

Now, consider a 3-uniform hypergraph G such that there is a monochromatic copy of G in ϕ=ϕq. Suppose the statement holds for all 3-uniform hypergraphs with fewer vertices. Denote N=Nq=2q/2. Suppose the color of this monochromatic copy is (t, s),  where t∈{0,⋯,q/2-1} and s∈{0,1}. Let the vertices of G be {1,⋯,h} and without loss of generality, suppose that in the monochromatic copy vertex i is embedded into xi where 0≤x1<x2<⋯<xh<N.

If s=1, for i∈[h], define xi′=N-1-xi, i.e., xi′ is obtained by complementing the binary representation of xi. Then, we have 0≤xh′<xh-1′<⋯<x1<N and δ(xi′,xj′)=δ(xi,xj) for any 1≤i<j≤h. It follows that the set {xh′,⋯,x1′} forms a monochromatic copy of G in color (t, 0). Therefore, we may assume that s=0.

For 1≤i<h, let δi:=δ(xi,xi+1). Observe that by Property P3), we have1 ∀u,v,1≤u<v≤h,δ(xu,xv)=maxu≤i<vδi.

Let m be the largest nonnegative integer such that bit(δi,m) for i∈[h-1] are not all equal. Since δ1≠δ2, m is well defined. By Property , this choice of m implies2 ∀1≤u<v≤h,bit(δ(xu,xv),m)=1⟺∃i,u≤i<v,bit(δi,m)=1.

Suppose first that m=t. Then,3 ∀u,v,w,u<v<w,uvw∈E(G)⇒bit(δ(xu,xv),m)=0and bit(δ(xv,xw),m)=1.

Indeed, this is true because for an edge uvw,  we have ϕ(xuxvxw)=(m,0).

Now, let i be the minimal index such that bit(δi,m)=1. Suppose that i=h-1. Then, by (1), for any 1≤u<v≤h-1, we have bit(δ(xu,xv),m)=bit(maxu≤i<vδi,m)=0. By (3), it follows that every edge of G contains the last vertex h,  implying that G∈U1⊆U.

Hence, we may assume that i<h-1. Then, in G there can be no edge uvw with u≤i and v,w≥i+1, as then bit(δ(xu,xv),m)=1 by (2), contradicting (3). Therefore, we can collapse the set {i+1,⋯,h}, which has at least two vertices by our assumption, to obtain a new 3-uniform hypergraph H on the vertex set {1,2,⋯,i,v∗}. Let us show that the vertex set {x1,⋯,xi+1} forms a monochromatic copy of H in color (t, 0) with j being embedded into xj for j∈[i] and v∗ embedded into xi+1. Indeed, {x1,⋯,xi} is a copy of H[{1,⋯,i}] in color (t, 0) because {x1,⋯,xh} is a copy of G in color (t, 0). Furthermore, for every edge {j,k,v∗}∈E(H), we have bit(δ(xj,xk),t)=0 and bit(δ(xk,xi+1),t)=1 by our choice of i and using Property  so ϕ(xjxkxi+1)=(t,0). In ϕ, there clearly exists a monochromatic copy of the induced subgraph G[{vi+1,⋯,vh}] so both H and G[{vi+1,⋯,vh}] 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≤i1<⋯<ip<h denote all indices i for which bit(δi,m)=1 and note that 2≤p+1≤h. Let I1,⋯,Ip+1 denote the intervals between consecutive ij′s. Formally, let I1={1,⋯,i1}, for 2≤j≤p, let Ij={ij-1+1,⋯,ij} and let Ip+1={ip+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∩Ij|=2. Since Ij is an interval, we have either e∩Ij={u,v} or e∩Ij={v,w}. In the former case, by the definition of Ij, using (2), we have bit(δ(xu,xv),m)=0 and bit(δ(xv,xw),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∩Ij|≠2.

For j∈[p+1], denote Fj=G[Ij]. Furthermore, let H be the hypergraph on the vertex set {1,⋯,p+1} with edges {uvw|∃e∈G,|e∩Iu|=|e∩Iv|=|e∩Iw|=1}. By definition, the hypergraphs H,F1,⋯,Fp+1 have fewer vertices than H. Hence, G is decomposable into (H;F1,⋯,Fp+1). By the induction hypothesis, F1,⋯,Fp+1∈U since the vertices {xu|u∈Ij} form a copy of Fj in color (t, 0) by assumption. For j∈[p+1], let yj=xminIj. Next we show that {y1,⋯,yp+1} contains a monochromatic copy of H in color (t, 0). Indeed, consider the embedding which maps i∈V(H)=[p+1] into yi. 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∈Iu,b∈Iv,c∈Iw. By (1) and the definition of i1,⋯,ip, we haveδ(yu,yv)=δ(xminIu,xminIv)=maxminIu≤j<minIvδj=maxu≤ℓ<vδiℓ=δ(xa,xb),

and analogously δ(yvyw)=δ(xb,xc). Hence, ϕ(yuyvyw)=ϕ(xaxbxc)=(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=22q/27 and consider q random copies of the complete balanced tripartite 3-uniform hypergraph, which has at least 29N3 edges, and define ϕ to be the coloring where each triple of KN(3) 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 mostN3(1-2/9)q<N3e-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 Ω(q1/3) vertices into distinct colors. For the upper bound, if G is tripartite, by a well-known result of Erdős [10], there is an ε>0 such that for large enough N, any 3-uniform hypergraph on N vertices with at least N3-ε edges contains a copy of G. Hence, if we are given a q-colored complete graph on N=(10q)1/ε vertices, one of the colors will have at least N3/q>N3-ε edges and thus contains a copy of G.

The lower bound in Part b) is given by Lemma 2.7 and the upper bound in Corollary 2.3.

Finally, the lower bound in Part c) is given by Lemma 2.6, while the upper bound follows from the upper bound for cliques proved by Erdős and Rado [11]. □

Remark

If G is tripartite and has at least two edges, its multicolor Ramsey number r(G; q) is given by its extremal (or Turán) number ex(N,G) up to a logarithmic factor in the number of colors. Indeed, every color class in the Ramsey coloring has at most ex(N,G) edges, which implies that q≥Θ(N3/ex(N,G)). On the other hand, by taking q=O(logN·N3/ex(N,G)) random copies of an extremal 3-uniform hypergraph on N vertices and using similar computations as in Lemma 2.7, one can obtain a coloring with no monochromatic copy of G.

Examples

Recall that for non-tripartite G∈U, we have the lower bound r(G;q)≥2Ω(q) given by Lemma 2.7 while the upper bound is of the form 2O(qℓlogq) for some ℓ≥1. Unless G∈U1, these bounds are far apart. However, in certain cases we can refine the lower bound. We start with a definition.

Definition 3.1

We say that a 3-uniform hypergraph G is forward colorable if there is a vertex partition such that for any edge e∈E(G), there are i<j for which |e∩Vi|=1 and |e∩Vj|=2.

Observe that U2 contains all forward colorable 3-uniform hypergraphs. Indeed, suppose G is forward colorable with a vertex partition as defined above. If t=2, every edge of G touches V1 in exactly one vertex, so G∈U1. Else, U=V1∪V2 is a collapsible set and G is reducible to the pair (H, G[U]) where H is forward colorable with t-1 parts and G[U]∈U1. The claim follows by induction on t.

Let L1 be the maximal family containing all forward-colorable 3-uniform hypergraphs as well as any 3-uniform hypergraph which is reducible to some (H;F1,⋯,Ft) such that H is tripartite and F1,⋯,Ft∈L1.

Lemma 3.2

For any 3-uniform hypergraph G not in L1, it holds that r(G;q)≥2Ω(q2).

Proof

Let q be a large integer and let ϕ be a coloring of KN(3) with colors {1,⋯,q} containing no monochromatic non-tripartite graph given by Lemma 2.7, where N=2Ω(q). We define a coloring ϕ′ on Nq vertices using 3q colors and containing no monochromatic copy of any 3-uniform hypergraph in L1, the existence of which implies the statement. To describe ϕ′, we identify the vertex set [Nq] with [N]q. For a vector a∈[N]q we write a=(a1,⋯,aq). Consider three vectors x,y,z∈[N]q where x<y<z according to the lexicographic ordering which is defined as a<b if for some i∈[q], ai<bi and aj=bj for all 1≤j<i. Let j be the first coordinate for which xj,yj,zj are not all equal. If xj,yj,zj are all distinct, then set ϕ′(x,y,z)=ϕ(xj,yj,zj). Else if xj<yj=zj, set ϕ′(x,y,z)=(j,0) and if xj=yj<zj, then set ϕ′(x,y,z)=(j,1). Note that this covers all cases by the assumed ordering.

Now, we prove, by induction on |V(G)|,  that ϕ′ is a Ramsey coloring for any 3-uniform hypergraph G∉L1. Let G be a 3-graph, denote V(G)={1,⋯,h} and suppose in ϕ′ there exists a monochromatic copy of a G with vertex v∈[h] embedded into xv∈[N]q. Assume the color of this copy is (j, 0) or (j, 1),  for some j∈[r]. For s∈[N], set Vs={v∈V(G)|xvj=s}. Then if the color of the copy is (j, 0),  it is easy to see that G is forward colorable with vertex partition while if the color is (j, 1), then G is forward colorable with vertex partition Thus, in either case, we have G∈L1. Now suppose the color of this monochromatic copy is c∈[q]. Let j be the first coordinate in which x1,⋯,xh are not all equal. Then, there is a partition of the vertex set into m≥2 non-empty sets such that the vertices Vi correspond to vectors with the same j-th coordinate. Let H be the hypergraph with vertex set [m] and edge set E(H)={abc|E(G)∩(Va×Vb×Vc)≠∅}. 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[Vj] in ϕ′ and hence G[Vj]∈L1 by the induction hypothesis. It follows that G∈L1, as required. □

Proposition 3.3

There is a 3-uniform hypergraph G for which r(G;q)=22+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,a1,a2,a3 denote the vertices of A with v being the center, and let u,b1,b2 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∈U2, and thus, the upper bound follows by Corollary 2.3.

Next we show that G∉L1, and then, the lower bound follows from Lemma 3.2.

First, suppose that G is forward colorable and let be a partition which certifies it. Then, there are indices i<j such that v∈Vi and {a1,a2,a3}⊆Vj. By the same argument, since {u,v,b1,b2} form a Star(3)(4) with center u,  we have that b1,b2∈Vi and u∈Vℓ for some ℓ<i. But, then the edge ub1a1 has its vertices in three distinct sets, a contradiction.

Now, suppose that G is decomposable into (H;F1,⋯,Ft) with a partition Note that if S is a non-empty 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 Vi contains at least two vertices from v,u,b1,b2. Since these vertices form a star, by the previous observation, it follows that Vi contains all of them. Furthermore, since any w∈A forms a copy of Star(3)(4) with {u,b1,b2}, by the same observation, we get Vi=V(G), a contradiction. Therefore, the vertices u,v,b1,b2 are in different sets, implying that Star(3)(4)⊆H. Since Star(3)(4) is not tripartite, it follows that G∉L1, as claimed. □

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≥Cn2, then for G∼G(3)(n,p), with high probability, we have r(G;q)≥2q/2.

Proof

Using a standard Chernoff bound (see e.g. [3]), it is easy to show that with high probability,4 |E(G)∩(A1×A2×A3)|≥Cn/109,∀A1,A2,A3⊆V(G),|Ai|≥n/100,∀i∈[3].

Conditioning on (4), we show that G∉U, which would complete the proof by Lemma 2.6.

Let us first informally explain the ideas of the proof. If G∈U, then G∈U1 or there is a collapsible set U⊆V(G) such that G is reducible to (H, G[U]) by collapsing U, where H,G[U]∈U. If |U|<n/2, next consider the hypergraph G2=H and otherwise we “put aside” the vertices V(G)\U and consider the hypergraph G2=G[U]. Note that this way, |V(G2)|≥|V(G)|/2. By assumption, we have G2∈U so we can apply the same reasoning as above. In general, at each step we have a hypergraph Gi 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(Gi) represents a set of more than n/100 vertices of G. Indeed, if in some step we collapse a set U⊆V(Gi) 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 Gi represents more than n/100 vertices, we can group the vertices of Gi into four sets, where each set represents a set of at least n/100 vertices of G,  which, by (4), implies that Gi∉U1. Therefore, for any i,  Gi we can define a new hypergraph Gi+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 Ti⊆V(G), and a hypergraph Gi, where each vertex v∈V(Gi) is labeled with a set Si(v)⊆V(G) such that the sets (Si(v))v∈V(Gi) partition V(G)\Ti. The hypergraph Gi will correspond to a hypergraph obtained from G after several reductions and a set Si(v) indicates that v is a vertex representing the collapsed set (possibly in more than one step) Si(v). Formally, we always have5 E(Gi)={v1v2v3|∃e∈E(G),|e∩Si(vj)|=1,∀j∈[3]}.

For U⊆V(Gi), we denote Si(U)=⋃v∈USi(v) and we denote its weight by wi(U)=|Si(U)|. We shall maintain the following: (i) Gi∈U.

(ii) For any v∈V(Gi),wi({v})<n/100.

(iii) |Ti|<n/100 and for any e∈E(G),|e∩Ti|≠1.

(iv) For any e∈E(G) and any v∈V(Gi), it holds that |e∩Si(v)|≠2.

Initially, we set G1=G, S1(v)={v},∀v∈V(G) and T1=∅. Then, we proceed in steps i=1,⋯ as follows.

By assumption, Gi∈U. Suppose first that Gi∈U1, that is, there is a subset W⊆V(Gi) such that any edge in Gi intersects W in exactly one vertex. Hence, either W or V(Gi)\W is an independent set in Gi with weight at least n/4. Let I denote this independent set. Since w({v})<n/100 for any v∈V(Gi), I can be partitioned into three sets A1,A2,A3, with w(Ai)≥n/100, for all i∈ [3]. However, by definition of Gi, this implies E(G)∩(A1×A2×A3)=∅, contradicting (4).

Hence, Gi∉U1, implying that there is a collapsible subset Ui⊆Gi such that Gi[Ui]∈U and the hypergraph H obtained by collapsing Ui is also in U. We consider two cases.

First, suppose that wi(Ui)≤n/2. Let us show that then |wi(Ui)|<n/100. Otherwise by (4), G has an edge in Si(Ui)×Si(Ui)×Si(V(G)\(Ti∪Ui)). Such an edge cannot have two vertices in the same set Si(v) by Property (iv). On the other hand, if all three of its vertices lie in different sets Si(v), this contradicts that Ui is collapsible in Gi, so indeed we have |wi(Ui)|<n/100. Now, we let Gi+1 be the hypergraph obtained from Gi by collapsing Ui and let Ti+1=Ti. For any v∈V(Gi)\Ui, we let Si+1(v)=Si(v) and for the new vertex v∗∈V(Gi+1) representing the collapsed set Ui, we let Si+1(v∗)=∪v∈UiSi(v). Let us verify that Properties (i)–(iv) for i+1. Property (i) holds by assumption, (ii) still holds because wi(Ui)<n/100, (iii) is immediate since Ti+1=Ti, and finally, Property (iv) holds since Ui is a collapsible set in Gi.

Secondly, suppose that wi(Ui)>n/2. Denote Ti+1=Ti∪Si(V(Gi)\Ui), let Gi+1=Gi[Ui] and Si+1(v)=Si(v) for all v∈Ui. Let us verify the invariants. Property (i) is given by the assumption, while properties (ii) and (iv) are immediate since Si+1(v)=Si(v) for all v∈Ui=V(Gi+1). Let us check Property (iii). Suppose first there is an edge e∈E(G) such that |e∩Ti|=1. Then, it has two vertices inside Si(Ui) and by Property (iv), these two vertices are in distinct sets Si(v),Si(v′). However, this contradicts the fact that Ui is collapsible in Gi, proving the second part of (iii). Finally, we show that |Ti+1|<n/100. Suppose otherwise. Recall that G has no edges touching Ti in exactly one vertex. Since Ui is collapsible in Gi, it follows that G has no edges touching Ti+1 in exactly one vertex either. However, we have that n/100≤|Ti+1|≤n/2, which yields a contradiction to (4) by taking the sets V(G)\Ti,V(G)\Ti,Ti.

To conclude, in each step i=1,⋯ we obtain a new hypergraph Gi+1 still satisfying all the invariants. However, we always have |V(Gi+1)|<|V(Gi)| 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/n2) 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(n2kpk)=O(Ck). 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 proved 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)=F2m\{0} where a triple xyz forms an edge if and only if x+y+z=0. For i∈[m], let Vi 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)≤2O(q2logq) 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 different 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)≤2O(q2logq).

It is easy to see that r(Star(3)(4);q)=21+o(1) and Proposition 3.3 provides a 3-uniform hypergraph G with r(G;q)=22+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ℓ+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ℓ+o(1)?

Acknowledgements

We would like to thank David Conlon for helpful comments and the anonymous referees for valuable suggestions that improved the presentation of this paper.

Funding

Open access funding provided by Swiss Federal Institute of Technology Zurich

Data availability

The research in this paper is of purely theoretical nature and has no data associated with it.

Research supported in part by SNSF grant 200021-228014. Research supported by NSF Awards DMS-1953990 and DMS-2154129.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
==== Refs
References

1. Abbott HL Williams ER Lower bounds for some Ramsey numbers J. Comb. Theory Ser. A 1974 16 1 12 17 10.1016/0097-3165(74)90067-3
Abbott, H.L., Williams, E.R.: Lower bounds for some Ramsey numbers. J. Comb. Theory Ser. A 16(1), 12–17 (1974)10.1016/0097-3165(74)90067-3
2. Alon, N., Lovász: vectors, graphs and codes. In Building Bridges II: Mathematics of László Lovász, pp. 1–16. Springer (2020)
3. Alon, N., Spencer, J.H.: The Probabilistic Method. John Wiley & Sons (2016)
4. Axenovich M Gyárfás A Hong L Mubayi D Multicolor Ramsey numbers for triple systems Discrete Math. 2014 322 69 77 10.1016/j.disc.2014.01.004
Axenovich, M., Gyárfás, A., Hong, L., Mubayi, D.: Multicolor Ramsey numbers for triple systems. Discrete Math. 322, 69–77 (2014)10.1016/j.disc.2014.01.004
5. Campos, M., Griffiths, S., Morris, R., Sahasrabudhe, J.: An exponential improvement for diagonal Ramsey. arXiv preprint arXiv:2303.09521, (2023)
6. Chung, F., Graham, R.: Erdős on graphs. A K Peters, Ltd., Wellesley, MA (1998). His legacy of unsolved problems
7. Conlon D Fox J Sudakov B Recent developments in graph Ramsey theory Surv. Comb. 2015 424 2015 49 118
Conlon, D., Fox, J., Sudakov, B.: Recent developments in graph Ramsey theory. Surv. Comb. 424(2015), 49–118 (2015)
8. Day AN Johnson JR Multicolour Ramsey numbers of odd cycles J. Comb. Theory Ser. B 2017 124 56 63 10.1016/j.jctb.2016.12.005
Day, A.N., Johnson, J.R.: Multicolour Ramsey numbers of odd cycles. J. Comb. Theory Ser. B 124, 56–63 (2017)10.1016/j.jctb.2016.12.005
9. Erdős P Some remarks on the theory of graphs Bull. Am. Math. Soc. 1947 53 292 294 10.1090/S0002-9904-1947-08785-1
Erdős, P.: Some remarks on the theory of graphs. Bull. Am. Math. Soc. 53, 292–294 (1947)10.1090/S0002-9904-1947-08785-1
10. Erdős P On extremal problems of graphs and generalized graphs Israel J. Math. 1964 2 183 190 10.1007/BF02759942
Erdős, P.: On extremal problems of graphs and generalized graphs. Israel J. Math. 2, 183–190 (1964)10.1007/BF02759942
11. Erdős P Rado R Combinatorial theorems on classifications of subsets of a given set Proc. Lond. Math. Soc. 1952 3 2 417 439 10.1112/plms/s3-2.1.417
Erdős, P., Rado, R.: Combinatorial theorems on classifications of subsets of a given set. Proc. Lond. Math. Soc. 3(2), 417–439 (1952)10.1112/plms/s3-2.1.417
12. Erdős P Szekeres G A combinatorial problem in geometry Compos. Math. 1935 2 463 470
Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935)
13. Ferber, A., Kwan, M.: Almost all Steiner triple systems are almost resolvable. In Forum of Mathematics, Sigma, volume 8, page e39. Cambridge University Press (2020)
14. Graham, R.L., Rothschild, B.L., Spencer, J.H.: Ramsey Theory, volume 20. John Wiley & Sons (1991)
15. Kővári, P., T. Sós, V., Turán, P.: On a problem of Zarankiewicz. In Colloquium Mathematicum, volume 3, pp. 50–57. Polska Akademia Nauk (1954)
16. Kwan M Almost all Steiner triple systems have perfect matchings Proc. Lond. Math. Soc. 2020 121 6 1468 1495 10.1112/plms.12373
Kwan, M.: Almost all Steiner triple systems have perfect matchings. Proc. Lond. Math. Soc. 121(6), 1468–1495 (2020)10.1112/plms.12373
17. Mubayi, D., Suk, A.: A survey of hypergraph Ramsey problems. Discrete Math. Appl., pp. 405–428 (2020)
18. Nešetil, J., Rosenfeld, M., Schur, I., Shannon, C.E., Ramsey: numbers, a short story. Discrete Math., 229, 185–195 (2001)
19. Ramsey, F.P.: On a problem of formal logic. Proceedings of the London Mathematical Society, s2-30(1):264–286 (1930)
