Tower gaps in multicolour Ramsey numbers

EUROCOMB’23

Abstract
Resolving a problem of Conlon, Fox, and Rödl, we construct a family of hypergraphs with arbitrarily large tower height separation between their $2$-colour and $q$-colour Ramsey numbers. The main lemma underlying this construction is a new variant of the Erdős-Hajnal stepping-up lemma for a generalized Ramsey number $r_k(t;q,p)$, which we define as the smallest integer $n$ such that every $q$-colouring of the $k$-sets on $n$ vertices contains a set of $t$ vertices spanning fewer than $p$ colours. Our results provide the first tower-type lower bounds on these numbers.

Pages:
380–385
References

Stanley, R. P. (2011). Enumerative Combinatorics, vol. 1. Cambridge Studies in Advanced Mathematics.
https://doi.org/10.1017/CBO9781139058520

Xu, X., Shao, Z., Su, W., Li, Z. (2009). Set-coloring of edges and multigraph Ramsey numbers. Graphs and Combinatorics, 25(6), 863-870.
https://doi.org/10.1007/s00373-010-0888-y

Aragão, L., Collares, M., Marciano, J. P., Martins, T., Morris, R. (2022). A lower bound for set-coloring Ramsey numbers. arXiv preprint arXiv:2212.06802.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-007

Conlon, D., Fox, J., He, X., Mubayi, D., Suk, A., Verstraëte, J. (2022). Set-coloring Ramsey numbers via codes. arXiv preprint arXiv:2206.11371.

Erdős, P., Szemerédi, A. (1972). On a Ramsey type theorem. Periodica Mathematica Hungarica, 2(1-4), 295-299.
https://doi.org/10.1007/BF02018669

Erdős, P., Hajnal, A., Rado, R. (1965). Partition relations for cardinal numbers. Acta Math. Acad. Sci. Hung., 16, 93-196.
https://doi.org/10.1007/BF01886396

Erdős, P., Hajnal, A. (1972). On Ramsey like theorems, problems and results. In Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972) (pp. 123-140).

Fox, J., Sudakov, B. (2009). Two remarks on the Burr-Erdős conjecture. European J. Combin., 30, 1630-1645.
https://doi.org/10.1016/j.ejc.2009.03.004

Kostochka, A. V., Sudakov, B. (2003). On Ramsey numbers of sparse graphs. Combin. Probab. Comput., 12, 627-641.
https://doi.org/10.1017/S0963548303005728

Conlon, D., Fox, J., Sudakov, B. (2013). Discrete Appl. Math., 161(9), 1191-1196.
https://doi.org/10.1016/j.dam.2010.10.013

Conlon, D., Fox, J., Sudakov, B. (2010). Hypergraph Ramsey numbers. J. Amer. Math. Soc., 23(1), 247-266.
https://doi.org/10.1090/S0894-0347-09-00645-6

Conlon, D., Fox, J., Rödl, V. (2017). Hedgehogs are not color blind. J. Comb., 8(3), 475-485.
https://doi.org/10.4310/JOC.2017.v8.n3.a4

Mubayi, D., Suk, A. (2020). Cliques with many colors in triple systems. arXiv:2005.03078.
https://doi.org/10.4310/JOC.2021.v12.n4.a2

Erdős, P., Szekeres, G. (1935). A combinatorial problem in geometry. Compos. Math., 2, 463-470.

Shelah, S. (1998). Erdős and Rényi Conjecture. J. Combin. Theory, Series A, 82(2), 179-185.
https://doi.org/10.1006/jcta.1997.2845

Graham, R. L., Rothschild, B. L., Spencer, J. H. (1990). Ramsey Theory, vol. 20. John Wiley & Sons.

Alon, N., Spencer, J. H. (2016). The Probabilistic Method. John Wiley & Sons.

Erdős, P., Rado, R. (1952). Combinatorial theorems on classifications of subsets of a given set. Proc. London Math. Soc., 3(1), 417-439.
https://doi.org/10.1112/plms/s3-2.1.417

Kostochka, A., Rödl, V. (2006). On Ramsey numbers of uniform hypergraphs with given maximum degree. J. Combin. Theory, Series A, 113(7), 1555-1564.
https://doi.org/10.1016/j.jcta.2005.12.007

Burr, S. A., Erdős, P. (1975). On the magnitude of generalized Ramsey numbers for graphs, Infinite and Finite Sets I, Colloq. Math. Soc. János Bolyai, 10, North-Holland, Amsterdam-London.

Lee, C. (2017). Ramsey numbers of degenerate graphs. Ann. of Math., 185(3), 791-829. Department of Mathematics of Princeton University.
https://doi.org/10.4007/annals.2017.185.3.2

Metrics

0

Views

0

PDF views