Ramsey theory constructions from hypergraph matchings

Joos, Felix; Mubayi, Dhruv

doi:10.1090/proc/16413

Ramsey theory constructions from hypergraph matchings
HTML articles powered by AMS MathViewer

by Felix Joos and Dhruv Mubayi;

Proc. Amer. Math. Soc. 152 (2024), 4537-4550

DOI: https://doi.org/10.1090/proc/16413

Published electronically: September 20, 2024

HTML | PDF

Abstract:

We give asymptotically optimal constructions in generalized Ramsey theory using results about conflict-free hypergraph matchings. For example, we present an edge-coloring of $K_{n,n}$ with $2n/3 + o(n)$ colors such that each $4$-cycle receives at least three colors on its edges. This answers a question of Axenovich, Füredi and the second author [J. Combin. Theory Ser B 79 (2000), pp. 66–86]. We also exhibit an edge-coloring of $K_n$ with $5n/6+o(n)$ colors that assigns each copy of $K_4$ at least five colors. This gives an alternative very short solution to an old question of Erdős and Gyárfás [Combinatorica 17 (1997), pp. 459–467] that was recently answered by Bennett, Cushman, Dudek, and Prałat [J. Combin. Theory Ser. B 169 (2024), pp. 253–297] by analyzing a colored modification of the triangle removal process.

References

Noga Alon and Joel H. Spencer, The probabilistic method, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR 3524748
Maria Axenovich, A generalized Ramsey problem, Discrete Math. 222 (2000), no. 1-3, 247–249. MR 1771403, DOI 10.1016/S0012-365X(00)00052-2
Maria Axenovich, Zoltán Füredi, and Dhruv Mubayi, On generalized Ramsey theory: the bipartite case, J. Combin. Theory Ser. B 79 (2000), no. 1, 66–86. MR 1757023, DOI 10.1006/jctb.1999.1948
Patrick Bennett, Ryan Cushman, Andrzej Dudek, and PawełPrałat, The Erdős-Gyárfás function $f(n,4,5)=\frac {5}{6}n+o(n)$—so Gyárfás was right, J. Combin. Theory Ser. B 169 (2024), 253–297. MR 4776368, DOI 10.1016/j.jctb.2024.07.001
David Conlon, Jacob Fox, Choongbum Lee, and Benny Sudakov, The Erdős-Gyárfás problem on generalized Ramsey numbers, Proc. Lond. Math. Soc. (3) 110 (2015), no. 1, 1–18. MR 3299597, DOI 10.1112/plms/pdu049
Paul Erdős, Problems and results on finite and infinite graphs, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) Academia, Prague, 1975, pp. 183–192. (loose errata). MR 389669
P. Erdős, Solved and unsolved problems in combinatorics and combinatorial number theory, Congr. Numer. 32 (1981), 49–62. MR 681869
Paul Erdős and András Gyárfás, A variant of the classical Ramsey problem, Combinatorica 17 (1997), no. 4, 459–467. MR 1645678, DOI 10.1007/BF01195000
Stefan Glock, Felix Joos, Jaehoon Kim, Marcus Kühn, and Lyuben Lichev, Conflict-free hypergraph matchings, J. Lond. Math. Soc. (2) 109 (2024), no. 5, Paper No. e12899, 78. MR 4745877, DOI 10.1112/jlms.12899
Colin McDiarmid, On the method of bounded differences, Surveys in combinatorics, 1989 (Norwich, 1989) London Math. Soc. Lecture Note Ser., vol. 141, Cambridge Univ. Press, Cambridge, 1989, pp. 148–188. MR 1036755
Dhruv Mubayi, Edge-coloring cliques with three colors on all $4$-cliques, Combinatorica 18 (1998), no. 2, 293–296. MR 1656546, DOI 10.1007/PL00009822
Dhruv Mubayi, An explicit construction for a Ramsey problem, Combinatorica 24 (2004), no. 2, 313–324. MR 2071338, DOI 10.1007/s00493-004-0019-6