One of the oldest open problem in Ramsey theory has been solved. We now know the asymptotics of Ramsey numbers , for any fixed , up-to log factors. Last month, Domagoj Bradač showed that for any fixed and (where the term is hiding log factors), using a beautiful finite-geometric construction. This is very close to the classical upper bound is (roughly) and drastically improves the previous best lower bound of for all . Now an internal model at openai has been used to close the gap, as described in the new version of Domagoj’s paper. The construction is slightly different from the original one by Domagoj. Perhaps expectedly, it uses an old explicit construction of Codenotti, Pudlák and Resta for Ramsey numbers as the base geometric graph and then does a random sampling via a similar, but more involved, argument. In this post I’ll leave out those technical details and only present the general idea behind the construction, along with some personal reflections. I will use a reformulation…
No comments yet. Log in to reply on the Fediverse. Comments will appear here.