Discovery of Ramsey numbers is a mathematical breakthrough – 06/08/2023 – Fundamental Science

One of the attractions of parties is knowing how many guests we know. Another, perhaps more exciting, is knowing how many guests we don’t know. So, the fundamental question of any self-respecting host is the following: how many guests does it take for at least X of them to know each other or at least Y of them not to know each other? The host’s life (like all of us) is greatly facilitated by mathematics.

Simply because the answer to that question goes through a beautiful theory — Ramsey’s theory —, whose foundations were laid by the British mathematician Frank Plumpton Ramsey, in 1930. It should be noted that Ramsey thought big, and also contributed to philosophy and to science. economy. Perhaps one of his main legacies was his partnership with John Maynard Keynes to (re)attract Ludwig Wittgenstein to Cambridge.

One of the fundamental problems of the theory can be put like this: we want to know how many elements a set has to have so that at least X of them are connected or at least Y of them are not connected. For example, if we have a thousand followers on a social network, is it possible to guarantee that at least 204 of them follow each other? Or that at least 192 do not follow each other?

Ramsey’s theory says yes. In fact, the number of guests that ensures that at least X know each other or at least Y don’t know each other is the Ramsey number R(X,Y). An important curiosity is that Ramsey demonstrated mathematically that such a number exists. But he didn’t teach us how to calculate it. This number is known in some particular, eventually simpler cases; for example, if we want to ensure that at least three guests know each other or at least three do not, we are looking for the Ramsey number R(3,3). Scalded mathematicians know that R(3,3)=6. That is, it is enough to have six guests at the party. We also know that R(3,4)=9 and R(3,5)=14. But, for example, we don’t know R(29,5)… And calculating these numbers is far from being a trivial experience. Even in such particular cases.

Knowing the Ramsey number is not only useful for those who organize parties or manage social networks. The theory finds several applications within mathematics itself (for example, in number theory) and in several other disciplines, such as the design of communication channels.

Imagine that we want to develop a network that transmits messages written with a given alphabet. And we know that the mechanism risks mixing up some letters. For example, let’s assume that the mechanism can confuse the letter I and the letter O. Then the word YES would not be distinguished from the word SOUND. Ramsey’s number tells us how big the alphabet (letters invited to the party) ensures that we can choose 23 of them that won’t be confused by the engine.

But again: except for a few special cases, we don’t know how to calculate the Ramsey number. A useful strategy when we want to know a quantity that we don’t know how to calculate is to look for bounds. That is, even if we don’t know R(X,Y), we would like to know if this number is between two other known ones. That is, it has a lower bound and an upper bound. This allows us to sandwich the number between known quantities and get some idea about it.

The problem is that estimating bounds for the Ramsey number is still a colossal task. And it has already attracted brilliant professionals like Paul Erdös, who in 1935, in a joint effort with George Szekeres, inaugurated the search for these limitations. Since then, progress has seemed stagnant.

Until another day. This year, the theory raised the cruising altitude by a few knots: a new upper bound for the Ramsey number was discovered, which improves previous estimates. And it improves by proposing new techniques, very out-of-the-box approaches. That is: not only does it bring a new answer to a fundamental problem, but it also teaches new ways of thinking about it. And the best part: it is a contribution produced largely in Brazil, by Simon Griffiths and his collaborators Julian Sahasrabudhe, Marcelo Campos and Robert Morris. It is very fine mathematics, discovered among the corridors of the Department of Mathematics at PUC-Rio, the corridors of IMPA and those of the University of Cambridge.

The advance that this result represents for pure mathematics is fundamental. And imagining the different applications it will have on human activities in the coming years (100, 200 years…) is a fun exercise without any upper limit.

*

Edgard Pimentel is a researcher at the Mathematics Center of the University of Coimbra and professor at PUC-Rio.

The blog Ciência Fundamental is edited by Serrapilheira, a private, non-profit institute that supports science in Brazil. Sign up for the Serrapilheira newsletter to keep up with news from the institute and the blog.

PRESENT LINK: Did you like this text? Subscriber can release five free hits of any link per day. Just click the blue F below.