The Erdős-Hajnal hypergraph Ramsey problem (Q2178253)

Summary: Given integers \(2\leq t \leq k+1 \leq n\), let \(g_k(t,n)\) be the minimum \(N\) such that every red/blue coloring of the \(k\)-subsets of \(\{1, \dots, N\}\) yields either a \((k+1)\)-set containing \(t\) red \(k\)-subsets, or an \(n\)-set with all of its \(k\)-subsets blue. \textit{P. Erdős} and \textit{A. Hajnal} [``On Ramsey like theorems, problems and results'', in: Combinatorics. Proceedings of the Conference on Combinatorial Mathematics held at the Mathematical Institute, Oxford, 3--7 July, 1972. Southend-on-Sea: The Institute of Mathematics and its Applications. 123--140 (1972), \url{https://users.renyi.hu/~p_erdos/1972-10.pdf}] proved that for fixed \(2\leq t \leq k\), there are positive constants \(c_1\) and \(c_2\) such that \[2^{c_1 n} < g_k(t, n) < \operatorname{twr}_{t-1} (n^{c_2}),\] where \(\operatorname{twr}_{t-1}\) is a tower of 2's of height \(t-2\). They conjectured that the tower growth rate in the upper bound is correct. Despite decades of work on closely related and special cases of this problem by many researchers, there have been no improvements of the lower bound for \(2 < t < k\). Here we settle the Erdős-Hajnal conjecture in almost all cases in a strong form, by determining the correct tower growth rate, and in half of the cases we also determine the correct power of \(n\) within the tower. Specifically, we prove that if \(2 < t < k - 1\) and \(k - t\) is even, then \[g_k(t, n) = \operatorname{twr}_{t-1} ( n^{k-t+1 + o(1)} ).\] Similar results are proved for \(k - t\) odd.