To cheer you up in difficult times 12: Asaf Ferber and David Conlon found new lower bounds for diagonal Ramsey numbers

Update (Sept. 28): Yuval Wigderson has made a further improvement on the multicolor Ramsey number bound for more than three colors.

Lower bounds for multicolor Ramsey numbers

The Ramsey number r(t; ℓ) is the smallest natural number n such that every ℓ-coloring of the edges of the complete graph K_n contains a monochromatic K_t. (r(t;2) is often denoted by R(t,t) and r(t;3) by R(t,t,t) etc.) Famously, R(3,3)=6; R(4,4)=18;  and R(3,3,3)=17. Understanding R(t,t) is among the most famous problems in combinatorics. (Understanding if r(3; ) is exponential or superexponential in is also a very famous problem.)

It is known since the 1940s that t/2 +o(1) \le log_2 R(t,t) \le 2t.

Lower bounds for R(t,t) where used by Lefmann in 1987 to give lower bounds on r(t; ℓ) for >2. Asaf Ferber and David Conlon gave now exponential improvement. This is truly remarkable and the paper is just 4-page long! congratulations Asaf and David!

Expect more cheering news of discrete geometry nature from Oberwolfach. (I take part remotely in the traditional meeting on Discrete and computational geometry, see pictures below).

Update (Sept 24.): An excellent blog post on Anurag math blog. Anurag describes in details the construction, describes the connections with finite geometries, and improves the construction to get a better result. (See also there many cool posts, e.g., an earlier post with some connections of finite geometries and different Ramsey problems Heisenberg groups, irreducible cubics and minimal Ramsey.)

This entry was posted in Combinatorics and tagged , . Bookmark the permalink.

3 Responses to To cheer you up in difficult times 12: Asaf Ferber and David Conlon found new lower bounds for diagonal Ramsey numbers

  1. Pingback: Improved lower bounds for multicolour diagonal Ramsey numbers | Anurag's Math Blog

  2. Gil Kalai says:

    Yuval Wigderson has made a further improvement on the multicolor Ramsey number bound for more than three colors. https://arxiv.org/abs/2009.12020.

  3. Thank you Gil for linking to my blog posts. I truly believe that group theoretic and finite geometric approaches are going to be quite useful in Ramsey problems.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s