×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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
[2] 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
[3] Bohman, T.: The triangle-free process. Adv. Math.221, 1653-1677 (2009)Zbl 1195.05074 MR 2522430 · Zbl 1195.05074
[4] 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
[5] Chung, F. R. K.: Open problems of Paul Erd˝os in graph theory. J. Graph Theory25, 3-36 (1997)Zbl 0872.05052 MR 1441976
[6] 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
[7] 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
[8] Conlon, D., Fox, J., Sudakov, B.: Personal communication
[9] 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
[10] Eli´aˇs, M., Matouˇsek, J.: Higher-order Erd˝os-Szekeres theorems. Adv. Math.244, 1-15 (2013) Zbl 1283.05175 MR 3077863
[11] 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
[12] Erd˝os, P.: Some remarks on the theory of graphs. Bull. Amer. Math. Soc.53, 292-294 (1947) Zbl 0526.01014 MR 0720650
[13] 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
[14] 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
[15] 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
[16] Erd˝os, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math.2, 463-470 (1935)Zbl 0012.27010 MR 1556929
[17] Graham, R., Rothschild, B., Spencer, J.: Ramsey Theory. 2nd ed., Wiley, New York (1990) Zbl 0705.05061 MR 1044995 · Zbl 0705.05061
[18] 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
[19] Lenz, J., Mubayi, D.: The poset of hypergraph quasirandomness. Random Structures Algorithms46, 762-800 (2015)Zbl 1328.05172 MR 3346466 · Zbl 1328.05172
[20] 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
[21] Linial, N., Morgenstern, A.: On high-dimensional acyclic tournaments. Discrete Comput. Geom.50, 1085-1100 (2013)Zbl 1280.05052 MR 3138147 · Zbl 1280.05052
[22] 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
[23] 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
[24] Mubayi, D., Razborov, A.: Polynomial to exponential transition in Ramsey theory. arXiv:1901.06029(2019)
[25] Mubayi, D., Suk, A.: Constructions in Ramsey theory. J. London Math. Soc.97, 247-257 (2018)Zbl 1386.05115 MR 3789846 · Zbl 1386.05115
[26] 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
[27] 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.