Double exponential lower bound for \(3\)-uniform hypergraph Ramsey numbers

A \( t\)-graph has a vertex set \( V\) and an edge set \( E\) consisting of some prescribed set of \( t\)-subsets of \( V\). For \( t\)-graphs \( G_i\), \( i=1,\dots,k\), let \( r_t(G_1,\dots,G_k)\) denote the smallest integer \( m\) satisfying the property that if the edges of the complete \( t\)-graph on \( m\) vertices are colored in \( k\) colors, then for some \( i\), \( 1\leq i\leq k\), there is a subgraph isomorphic to \( G_i\) with all \( t\)-edges in the \( i\)-th color. We denote \( r_t(n_1, \dots, n_k)= r_t(K_{n_1}, \dots, K_{n_k})\).

The only known hypergraph Ramsey number is \( r_3(4,4)=13\), evaluated by direct computation [5]. Erdös, Hajnal and Rado[3] raised the following question:

Conjecture ($500) (proposed by Erdös, Hajnal and Rado [3])

Is there an absolute constant \(c >0\) such that \[ \log \log r_3(n,n) \geq c n? \]

This is true if four colors are allowed [4].

If just three colors are allowed, there is some improvement due to Erdös and Hajnal (unpublished).

\(\displaystyle r_3(n,n,n) > e^{c n^2 \log^2 n}. \)

In [3], it was shown

\begin{equation} 2^{cn^2} < r_3(n,n) < 2^{2^n}. \end{equation}

Erdös[1] said,
"We believe the upper bound is closer to the truth, although Hajnal and I [2] have a result which seems to favor the lower bound. We proved that if we color the triples of a set of \( n\) elements by two colors, there is always a set of size \( s = \lfloor \sqrt{\log n} \rfloor\) on which the distribution is unbalanced, i.e., one of the colors contains at least \( (\frac 1 2 + \epsilon) \binom{s}{3} \) triples. This is in strong contrast to the case of \( k=2\), where it is possible to \( 2\)-color the pairs of an \( n\)-set so that in every set of size \( f(n) \log n\), where \( f(n) \rightarrow \infty\), both colors get asymptotically the same number of pairs. We would begin to doubt seriously that the upper bound in (\([*]" SRC="/latex2html-icons/crossref.gif\)) is correct if we could prove that in any \( 2\)-coloring of the triples of an \( n\)-set, some set of size \( s=(\log n)^{\epsilon} \) for which at least \( (1-\eta) \binom s 3 \) triples have the same color. However, at the moment we can prove nothing like this."

1 P. Erdös, Some of my favourite problems in number theory, combinatorics, and geometry, Combinatorics Week (Portuguese) (São Paulo, 1994), Resenhas 2 (1995), 165-186.

2 P. Erdös and A. Hajnal. Ramsey-type theorems, Combinatorics and complexity (Chicago, IL, 1987), Discrete Appl. Math. 25 (1989) no. 1-2, 37-52

3 P. Erdös, A. Hajnal and R. Rado. Partition relations for cardinal numbers, Acta Math. cad. Sci. Hungar. 16 (1965), 93-196.

4 P. Erdös, A. Hajnal, A. Máté and R. Rado, Combinatorial set theory: partition relations for cardinals, Studies in Logic and the Foundations of Mathematics, 106, North-Holland Publishing Co., Amsterdam-New York, 1984.

5 B. D. McKay and S. P. Radziszowski. The first classical Ramsey number for hypergraphs is computed, Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'91, San Francisco, (1991), 304-308.