Behavior of generalized hypergraph Ramsey numbers

Denote by \( F^{(t)}(n, \alpha)\) the largest integer for which it is possible to split the \( t\)-tuples of a set \( S\) of \( n\) elements into \( 2\) classes so that for every \( X \subset S\) with \( \vert X\vert \geq F^{(t)}(n, \alpha)\), each class contains more than \( \alpha \binom{\vert X\vert}{t} \) \( t\)-tuples of \( X\). Note that \( F^{(t)}(n,0)\) is just the usual Ramsey function \( r_t(n,n)\). It is easy to show that for every \( 0 \leq \alpha \leq 1/2\),

\(\displaystyle c(\alpha) \log n < F^{(2)} (n,\alpha) < c'(\alpha) \log n. \)

It is conjectured [1] that for \( t=2\),

\(\displaystyle F^{(2)}(n,\alpha) \sim c \log n \)

for an appropriate \( c\).

As Erdös says in [1], the situation for \( t \geq 3\) is much more mysterious. It is well-known[1] that if \( \alpha\) is sufficiently close to \( 1/2\), then

\(\displaystyle c_t(\alpha) (\log n)^{1/(t-1)} < F^{(t)} (n, \alpha) < c'_t(\alpha) (\log n)^{1/(t-1)} . \)

On the other hand, since \( F^{(t)}(n,0)\) is just the usual Ramsey function, then the old conjecture of Erdös, Hajnal, Rado[2] would imply

\(\displaystyle c_1 \log _{t-1} n < F^{(t)} (n,0) < c_2 \log_{t-1} n. \)

Thus, assuming this conjecture holds, as \( \alpha\) increases from 0 to \( 1/2\), \( F^{(t)}(n, \alpha)\) increases from \( \log_{t-1} n\) to \( (\log n)^{1/(t-1)} \).

Problem ($ 500)

Does the change in \(F^{(t)} (n,\alpha)\) occur continuously, or are there jumps?

Erdös suspected there might only be one jump, this occurring at 0.

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

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