Double exponential lower bound for $3$-uniform hypergraph Ramsey numbers

Home
Search
Subjects

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

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.

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

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