# 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

$$2^{cn^2} < r_3(n,n) < 2^{2^n}.$$

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."

Bibliography
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.