# zbMATH — the first resource for mathematics

The Erdős-Hajnal hypergraph Ramsey problem. (English) Zbl 1439.05218
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. P. Erdős and 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)] proved in 1972 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.
##### MSC:
 05D10 Ramsey theory 05C65 Hypergraphs 05C55 Generalized Ramsey theory
##### Keywords:
hypergraph Ramsey numbers; stepping-up lemma
Full Text:
##### References:
  Ajtai, M., Koml´os, J., Szemer´edi, E.: A note on Ramsey numbers. J. Combin. Theory Ser. A 29, 354-360 (1980)Zbl 0455.05045 MR 0600598  Bhat, V., R¨odl, V.: Note on upper density of quasi-random hypergraphs. Electron. J. Combin. 20, no. 2, art. 59, 8 pp. (2013)Zbl 1298.05235 MR 3084601  Bohman, T.: The triangle-free process. Adv. Math.221, 1653-1677 (2009)Zbl 1195.05074 MR 2522430 · Zbl 1195.05074  Bohman, T., Keevash, P.: The early evolution of theH-free process. Invent. Math.181, 291- 336 (2010)Zbl 1223.05270 MR 2657427 · Zbl 1223.05270  Chung, F. R. K.: Open problems of Paul Erd˝os in graph theory. J. Graph Theory25, 3-36 (1997)Zbl 0872.05052 MR 1441976  Conlon, D., Fox, J., Sudakov, B.: Hypergraph Ramsey numbers. J. Amer. Math. Soc.23, 247- 266 (2010)Zbl 1287.05087 MR 2552253 · Zbl 1287.05087  Conlon, D., Fox, J., Sudakov, B.: An improved bound for the stepping-up lemma. Discrete Appl. Math.161, 1191-1196 (2013)Zbl 1277.05115 MR 3030610 · Zbl 1277.05115  Conlon, D., Fox, J., Sudakov, B.: Personal communication  Duffus, D., Lefmann, H., R¨odl, V.: Shift graphs and lower bounds on Ramsey numbers rk(l;r). Discrete Math.137, 177-187 (1995)Zbl 0822.05047 MR 1312451 · Zbl 0822.05047  Eli´aˇs, M., Matouˇsek, J.: Higher-order Erd˝os-Szekeres theorems. Adv. Math.244, 1-15 (2013) Zbl 1283.05175 MR 3077863  Fox, J., Pach, J., Sudakov, B., Suk, A.: Erd˝os-Szekeres-type theorems for monotone paths and convex bodies. Proc. London Math. Soc.105, 953-982 (2012)Zbl 1254.05114 MR 2997043 · Zbl 1254.05114  Erd˝os, P.: Some remarks on the theory of graphs. Bull. Amer. Math. Soc.53, 292-294 (1947) Zbl 0526.01014 MR 0720650  Erd˝os, P., Hajnal, A.: On Ramsey like theorems, problems and results. In: Combinatorics (Oxford, 1972), Inst. Math. Appl., Southend-on-Sea, 123-140 (1972)Zbl 0242.05122 MR 0337636  Erd˝os, P., Hajnal, A., Rado, R.: Partition relations for cardinal numbers. Acta Math. Acad. Sci. Hungar.16, 93-196 (1965)Zbl 0158.26603 MR 0202613 · Zbl 0158.26603  Erd˝os, P., Rado, R.: Combinatorial theorems on classifications of subsets of a given set. Proc. London Math. Soc.3, 417-439 (1952)Zbl 0048.28203 MR 0065615 · Zbl 0048.28203  Erd˝os, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math.2, 463-470 (1935)Zbl 0012.27010 MR 1556929  Graham, R., Rothschild, B., Spencer, J.: Ramsey Theory. 2nd ed., Wiley, New York (1990) Zbl 0705.05061 MR 1044995 · Zbl 0705.05061  Kohayakawa, Y., Nagle, B., R¨odl, V., Schacht, M.: Weak hypergraph regularity and linear hypergraphs. J. Combin. Theory Ser. B100, 151-160 (2010)Zbl 1216.05094 MR 2595699 · Zbl 1216.05094  Lenz, J., Mubayi, D.: The poset of hypergraph quasirandomness. Random Structures Algorithms46, 762-800 (2015)Zbl 1328.05172 MR 3346466 · Zbl 1328.05172  Lenz, J., Mubayi, D.: Eigenvalues and linear quasirandom hypergraphs. Forum Math. Sigma 3, art. e2, 26 pp. (2015)Zbl 1306.05144 MR 3324939 · Zbl 1306.05144  Linial, N., Morgenstern, A.: On high-dimensional acyclic tournaments. Discrete Comput. Geom.50, 1085-1100 (2013)Zbl 1280.05052 MR 3138147 · Zbl 1280.05052  Moshkovitz, G., Shapira, A.: Ramsey-theory, integer partitions and a new proof of the Erd˝os- Szekeres theorem. Adv. Math.262, 1107-1129 (2014)Zbl 1295.05255 MR 3228450 · Zbl 1295.05255  Milans, K. G., Stolee, D., West, D.: Ordered Ramsey theory and track representations of graphs. J. Combinatorics6, 445-456 (2015)Zbl 1325.05111 MR 3382604 · Zbl 1325.05111  Mubayi, D., Razborov, A.: Polynomial to exponential transition in Ramsey theory. arXiv:1901.06029(2019)  Mubayi, D., Suk, A.: Constructions in Ramsey theory. J. London Math. Soc.97, 247-257 (2018)Zbl 1386.05115 MR 3789846 · Zbl 1386.05115  Mubayi, D., Suk, A.: New lower bounds for hypergraph Ramsey numbers. Bull. London Math. Soc.50, 189-201 (2018)Zbl 1386.05190 MR 3830113 · Zbl 1386.05190  Mubayi, D.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.