Double exponential lower bound for \(3\)uniform hypergraph Ramsey numbers
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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).
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="/latex2htmlicons/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), 165186.

2  P. Erdös and A. Hajnal. Ramseytype theorems, Combinatorics and complexity (Chicago, IL, 1987), Discrete Appl. Math. 25 (1989) no. 12, 3752

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

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, NorthHolland Publishing Co., AmsterdamNew York, 1984.

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