A Ramsey-type conjecture for \(2\)-colorings of complete \(3\)-graphs

A hypergraph \( H\) consists of a vertex set \( V\) together with a family \( E\) of subsets of \( V\), which are called the edges of \( H\). A \( r\)-uniform hypergraph, or \( r\)-graph, for short, is a hypergraph whose edge set consists of \( r\)-subsets of \( V\). A graph is just a special case of an \( r\)-graph with \( r=2\).

Erdös[2] asked the following question:

Problem (proposed by Erdös [2])

Suppose \(|S|=n\) and the triples from \(S\) are split into two classes. Is it true that there are always two sets \(A \subset S\), \(B \subset S\) with \(|A|=|B|\geq c (\log n)^{1/2}\) so that all triples which hit both \(A\) and \(B\) belong to a single class ?

An old result [1] of Erdös shows that this is true if we only require that all triples \( (x,y,z)\) satisfying \( x \in A, y \in A, z \in B\) are in a single class. Note that this is a Ramsey-type result (as opposed to a density or Turán-type result) since one can find \( (1-o(1))\binom{n}{3} \) triples from \( S\) which do not contain such a system.

The difference between graphs and hypergraphs is strikingly illustrated by the following contrasting Ramsey behavior. It is not hard to show that for any function \( f(n) \rightarrow \infty\), one can \( 2\)-color the edges of \( K_m\), \( m=2^{n/f(n)} \), so that every subgraph \( K_n\) contains \( (\frac 1 2 +o(1))\binom n 2\) edges of each color. That is, uniformity for edge color can be maintained until very close to the Ramsey number (at which time we must find \( K_n\)'s with all edges have a single color). On the other hand, Erdös and Hajnal [3] showed that there is a \( c>0\) so that no matter how one \( 2\)-colors the edges of \( K_s^{(3)}\), \( s=2^{n^2}\), there is always a set \( T\) of \( n\) elements which has more than \( (\frac 1 2 +c) \binom n 3 \) triples from \( T\) in one color. This, in spite of the fact that it is generally believed that the corresponding Ramsey number is essentially \( 2^{2^{cn}}\). Clearly, there is a lot of room to improve our understanding of the truth here.


Bibliography
1 P. Erdös. On some extremal problems on \( r\)-graphs, Discrete Math. 1 (1971/72) no. 1, 1-6.

2 P. Erdös, Problems and results on graphs and hypergraphs: similarities and differences, Mathematics of Ramsey theory, Algorithms Combin., 5, (J. Nešetril and V. Rödl, eds.), 12-28, Springer, Berlin, 1990.

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