Growth Rate of 3-Uniform Hypergraph Ramsey Numbers

Growth Rate of 3-Uniform Hypergraph Ramsey Numbers

Definitions and mathematical statement

For $t\ge3$, let $r_3(t)$ be the least integer $N$ such that every map $c:\binom{[N]}3\to\{0,1\}$ has a $t$-element set $A$ on which $c$ is constant on all triples. Here $[N]=\{1,\ldots,N\}$ and a monochromatic complete $3$-uniform hypergraph means precisely this condition. The task is to determine the asymptotic growth of $r_3(t)$; its highlighted lower-bound question is \[ \exists c>0\ \exists t_0\ \forall t\ge t_0, \qquad r_3(t)\ge 2^{\,2^{ct}}. \] The two colours are fixed, and $t$ tends to infinity. A result for more colours, or a lower bound with only one exponential, does not establish this particular target. The requested asymptotic determination is broader than merely improving a finite bound.

Formulation and concept references: [S1].

Short English statement

How fast must a set grow before every two-colouring of its triples forces a large monochromatic subset, and is a double-exponential lower bound necessary?

Research attempt

Status: UNRESOLVED. Elementary probabilistic and selection arguments establish the familiar single-exponential lower scale and double-exponential upper scale. A full four-colour stepping-up construction is proved to expose the precise colour obstruction in using it for this two-colour question. The requested double-exponential two-colour lower bound is not obtained.

Source audit and the number of colours.

The primary article [S1], consulted on 27 September 2026, studies the large differences possible between colour counts and describes the two-colour three-uniform gap in its introduction. Its multicolour results cannot be read as a two-colour lower bound. Here $r_3(t)$ always has two colours; when four colours are used, the notation is explicitly $r_3(t;4)$.

A colouring on $N$ vertices with no monochromatic $t$-set proves $r_3(t)>N$, not an upper bound. Conversely a proof that every colouring on $N$ vertices has such a set proves $r_3(t)\le N$. These directions remain important when combining constructions at different uniformities.

1. A complete random-colouring lower bound.

Colour each triple independently and uniformly with one of two colours. A fixed $t$-element set is monochromatic with probability \[ 2\left(\frac12\right)^{\binom t3}=2^{1-\binom t3}. \] If $X$ counts monochromatic $t$-sets, then \[ \mathbb EX=\binom Nt\,2^{1-\binom t3} \le N^t2^{1-\binom t3}. \] For $t\ge4$, take \[ N=2^{\left\lfloor (t-1)(t-2)/6\right\rfloor-1}. \] This is a positive integer, and the last bound is at most $2^{1-t}<1$. Since $X$ is a nonnegative integer, some colouring has $X=0$. Thus $r_3(t)>N$, in particular $r_3(t)\ge2^{ct^2}$ for a fixed positive $c$ and all sufficiently large $t$.

This argument uses only the first moment, not independence between different monochromatic-set events. Those events share triples and are not mutually independent. The first moment is enough for the stated scale, but it is far from a double exponential in $t$.

2. Why the same first-moment proof cannot be pushed to the target.

For $N=2^{2^{ct}}$, the logarithm of $N^t2^{1-\binom t3}$ is $t2^{ct}+1-\binom t3$, which is positive and enormous for large $t$. More precisely, when $N\ge t$, the lower bound $\binom Nt\ge(N/t)^t$ shows that the exact expectation is also large at this scale. Therefore the sufficient condition $\mathbb EX<1$ cannot hold there for this independent fair colouring.

A large expectation does not prove that every colouring has a monochromatic $t$-set. Exceptional highly structured colourings might still avoid one. The calculation diagnoses the limitation of this existence proof; it is not an upper bound for the Ramsey number.

3. A graph Ramsey estimate used in the upper bound.

Let $R(a,b)$ be the two-colour graph Ramsey number for a red $a$-clique or a blue $b$-clique. Choosing one vertex and partitioning its neighbors by incident colour gives \[ R(a,b)\le R(a-1,b)+R(a,b-1), \] with $R(1,b)=R(a,1)=1$. Induction using Pascal's identity yields \[ R(a,b)\le\binom{a+b-2}{a-1}. \] In particular $R(t-1,t-1)\le4^{t-2}$. This proof applies to pair colourings; the next selection step is what transfers it to triples.

4. Selecting a sequence whose triple colours stabilize.

Set $m=R(t-1,t-1)+1$ and begin with \[ N=(m+1)2^{\binom m2} \] vertices of an arbitrary two-coloured triple system. Choose vertices $v_1,\ldots,v_m$ sequentially, maintaining an unused reservoir. After choosing $v_j$, for each $i<j$ retain a largest colour class of the triples $\{v_i,v_j,w\}$ as $w$ ranges over the current reservoir. There are $j-1$ such refinements. They preserve all conditions imposed at earlier stages.

If the reservoir after stage $j$ is $S_j$, then \[ |S_j|\ge\frac{|S_{j-1}|-1}{2^{j-1}} \ge\frac{N}{2^{j(j-1)/2}}-j. \] The second inequality follows by induction. With the chosen $N$ it remains positive through stage $m$, so every required choice is possible. For $i<j<k\le m$, the colour of $\{v_i,v_j,v_k\}$ is now a fixed colour $c_{ij}$ depending only on its first two indices.

Colour the pairs among $v_1,\ldots,v_{m-1}$ by $c_{ij}$. They contain a monochromatic $(t-1)$-set $A$ by the definition of $m$. Every triple within $A$, and every triple consisting of two vertices of $A$ and $v_m$, has the same colour. Therefore $A\cup\{v_m\}$ is a monochromatic $t$-set.

This proves $r_3(t)\le(m+1)2^{\binom m2}$. Since $m\le4^{t-2}+1$, it implies a bound of the form $2^{2^{Ct}}$ with an absolute constant $C$. It is an upper bound at the scale requested for the conjectural lower bound, not a matching determination of the growth rate.

5. A complete four-colour stepping-up construction.

Start with a red-blue colouring $c$ of the pairs of $[N]$ with no monochromatic $s$-set. Order the $2^N$ binary strings as integers, with coordinate $N$ most significant. For distinct strings $x<y$, let $\delta(x,y)$ be the largest coordinate where they differ.

For $x<y<z$ one has \[ \delta(x,y)\ne\delta(y,z),\qquad \delta(x,z)=\max\{\delta(x,y),\delta(y,z)\}. \] Indeed, at the highest differing coordinate an increasing pair has bits zero then one. If both adjacent pairs had that same coordinate, the middle bit would have to be both one and zero. The larger of two different highest coordinates persists between the endpoints. Iteration also gives that $\delta(x_i,x_j)$ is the largest consecutive delta between those indices.

Colour a triple $x<y<z$ by the pair \[ \left(c(\{\delta(x,y),\delta(y,z)\}), \ \text{whether }\delta(x,y)<\delta(y,z)\right). \] There are four possible colours. Suppose $x_1<\cdots<x_{s+1}$ were monochromatic. Put $d_i=\delta(x_i,x_{i+1})$. The second colour coordinate forces $d_1,\ldots,d_s$ to be strictly increasing throughout or strictly decreasing throughout.

In the increasing case, for $i<j$ the triple $(x_i,x_{i+1},x_{j+1})$ has deltas $(d_i,d_j)$, so $c(\{d_i,d_j\})$ is the common first colour coordinate. In the decreasing case use $(x_i,x_j,x_{j+1})$, whose deltas are again $(d_i,d_j)$. In either case the $s$ distinct deltas form a monochromatic $s$-set in the original pair colouring, a contradiction.

Thus $r_3(s+1;4)>2^N$. A graph first-moment construction, proved in the same way as paragraph 1 using pairs instead of triples, permits $N$ exponential in $s$. This gives a double-exponential lower bound with four colours.

6. The missing two-colour step is structural.

Discarding the comparison coordinate leaves only two colours, but removes the inference that all consecutive deltas are monotone. The two interval-maximum identities used above no longer produce every pair $(d_i,d_j)$ in the required way. Merging the four colours by another rule also needs a new argument: a set monochromatic after merging may use both pre-merge colours and need not be monochromatic before merging.

For example, a prohibition of monochromatic sets in a four-coloured system is not preserved under arbitrary colour merging. Even at four vertices, assigning different colours to its four triples avoids a monochromatic four-set before merging, whereas mapping all those colours to one creates such a set. The issue is not a bookkeeping choice in notation; it changes the combinatorial property.

One could seek a large monotone delta subsequence or impose more structure on the base pair colouring. But the size losses must be controlled strongly enough to leave a monochromatic set of the required size in the base. No such loss estimate is proved here. The successful four-colour proof therefore isolates, rather than resolves, the bottleneck in this route to two colours.

7. Finite checks and the scale left open.

The offline script enumerates all two-colour triple systems through five vertices, counts their monochromatic subsets, and checks the expectation formula by exact rational averaging. It independently verifies the delta identities on small ordered binary strings. For every two-colouring of the three-vertex complete graph without a monochromatic triangle, it builds the four-colour construction on eight strings and verifies the absence of monochromatic four-sets. It also tests the integer inequalities in the selected reservoir bound and lower-bound parameter choices.

These calculations verify finite instances and the algebra of the constructions. They do not extrapolate a growth rate from small Ramsey numbers. The proven bounds here remain between $2^{ct^2}$ and $2^{2^{Ct}}$. The highlighted question asks whether the lower scale can be raised to $2^{2^{ct}}$ for two colours, and the broader task asks for the asymptotic growth. Both remain unresolved by this attempt.

Sources

• S1 Dubroff, Girao, Hurley, and Yap, Tower Gaps in Multicolour Ramsey Numbers, Forum of Mathematics, Sigma $2023$, introduction. https://www.cambridge.org/core/journals/forum-of-mathematics-sigma/article/tower-gaps-in-multicolour-ramsey-numbers/B688491701E6FCC40E202C9B7B3AB672. Formulation source.