An improved lower bound on multicolor Ramsey numbers

Wigderson, Yuval

doi:10.1090/proc/15447

An improved lower bound on multicolor Ramsey numbers
HTML articles powered by AMS MathViewer

by Yuval Wigderson PDF

Proc. Amer. Math. Soc. 149 (2021), 2371-2374 Request permission

Abstract:

A recent breakthrough of Conlon and Ferber yielded an exponential improvement on the lower bounds for multicolor diagonal Ramsey numbers. In this note, we modify their construction and obtain improved bounds for more than three colors.

References

N. Alon, Lovász, vectors, graphs and codes, In I. Bárány, G. Katona, and A. Sali (eds.), Building Bridges II, Bolyai Soc. Math. Stud., vol. 28, Springer, 2019.
Noga Alon and Vojtěch Rödl, Sharp bounds for some multicolor Ramsey numbers, Combinatorica 25 (2005), no. 2, 125–141. MR 2127608, DOI 10.1007/s00493-005-0011-9
E. R. Berlekamp, On subsets with intersections of even cardinality, Canad. Math. Bull. 12 (1969), 471–474. MR 249303, DOI 10.4153/CMB-1969-059-3
David Conlon, A new upper bound for diagonal Ramsey numbers, Ann. of Math. (2) 170 (2009), no. 2, 941–960. MR 2552114, DOI 10.4007/annals.2009.170.941
David Conlon and Asaf Ferber, Lower bounds for multicolor Ramsey numbers, Adv. Math. 378 (2021), Paper No. 107528, 5. MR 4186575, DOI 10.1016/j.aim.2020.107528
P. Erdös, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292–294. MR 19911, DOI 10.1090/S0002-9904-1947-08785-1
P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470. MR 1556929
Xiaoyu He and Yuval Wigderson, Multicolor Ramsey numbers via pseudorandom graphs, Electron. J. Combin. 27 (2020), no. 1, Paper No. 1.32, 8. MR 4064053
H. Lefmann, A note on Ramsey numbers, Studia Sci. Math. Hungar. 22 (1987), no. 1-4, 445–446. MR 932230
D. Mubayi and J. Verstraëte, A note on pseudorandom Ramsey graphs, arXiv:1909.01461, 2019.
Jaroslav Ne et il and Moshe Rosenfeld, I. Schur, C. E. Shannon and Ramsey numbers, a short story, Discrete Math. 229 (2001), no. 1-3, 185–195. Combinatorics, graph theory, algorithms and applications. MR 1815606, DOI 10.1016/S0012-365X(00)00208-9
A. Sah, Diagonal Ramsey via effective quasirandomness, arXiv:2005.09251, 2020.
Joel Spencer, Ramsey’s theorem—a new lower bound, J. Combinatorial Theory Ser. A 18 (1975), 108–115. MR 366726, DOI 10.1016/0097-3165(75)90071-0