As long as k<\/em> is a low number, the theorem is easily solvable. If k<\/em> is 2, the answer to the problem is also 2. In a party with a pair of participants, the two guests are necessarily either acquaintances or strangers. There is no third possibility. If k<\/em> is 3, the theorem can also be solved. The answer is 6. It takes a bit more effort, but even a layperson can understand and demonstrate that with just six guests, there will always be three who know each other or three who do not. For k<\/em> equal to 4, 18 guests are required.<\/p>\n For a k<\/em> value of 5 and beyond, mathematicians do not have a definitive answer to the theorem. They can only state that, in this case, the minimum number of guests falls within a range between 43 and 48 people. Thus, as the value of k<\/em> increases, all combinatorics experts can assert is that the answer to the problem lies between a lower bound (in the previous example, the number 43) and an upper bound (48).<\/p>\n Two different formulas are used to calculate each bound in the partial solution to the theorem. However, both are still far from precise and leave room for optimization. In other words, the equation for the lower bound gives a result much smaller, and the equation for the upper bound gives a result much larger, than the unknown precise answer to the problem. Campos, Morris, Griffiths, and Sahasrabudhe developed an algorithm that significantly improved the formula used to calculate the upper bound. Instead of being 4 raised to the power of k<\/em> (4k<\/sup><\/em>), their new paper shows that the equation could be reduced to 3.995 raised to the power of k<\/em> (3.995k<\/sup><\/em>). The difference may seem subtle, but since 1935, when Hungarian mathematicians Paul Erd\u00f6s (1913\u20131996) and George Szekeres (1911\u20132005) arrived at the formula 4k<\/sup><\/em>, no substantial improvement had been made to the equation.<\/p>\n \u201cWe used a mathematical trick and got lucky,\u201d Griffiths humorously noted about the group\u2019s approach to improving the upper bound formula. \u201cIn this initial paper, which we plan to publish soon in a journal, we haven\u2019t fully exhausted our method. We believe there is still potential to further reduce the value of 3.995 in our equation.\u201d<\/p>\n The group decided to work on Ramsey\u2019s theorem in 2018 when Sahasrabudhe, the Canadian researcher who is now a professor at the University of Cambridge, was nearing the end of his postdoctoral studies at IMPA. \u201cWe are always on the lookout for interesting and challenging problems,\u201d says Morris from IMPA. \u201cOur usual approach is to spend a few days discussing a new problem in front of the blackboard, brainstorming ideas, and sketching out the main obstacles. Then we decide if we have an approach worth pursuing further.\u201d The group held most of their meetings in Rio during the summer, when Sahasrabudhe could join them from the UK. During the pandemic, they switched from face-to-face to online meetings.<\/p>\n<\/div> Although they had been considering potential approaches to solving the theorem for around five years, the breakthrough came in January 2023 when they opted for a change of strategy. Once they found the most promising pathway, they arrived at their solution in a matter of days and promptly wrote the paper reporting on their discovery. \u201cWe opted for a probabilistic approach to solving nonrandom problems, drawing on the works of Erd\u00f6s,\u201d says Campos, who joined the group in 2021.<\/p>\n Ramsey\u2019s theorem may not be directly applicable in everyday life, but it has had and continues to have a significant impact on mathematics and related fields. Determining or estimating Ramsey numbers is one of the central problems in combinatorics, with implications in disciplines such as computer science, logic, and statistical physics. Graph theory, a fundamental branch of combinatorics, is closely connected with the theorem.<\/p>\n A graph serves as an abstract representation of a set of elements and the pairwise relationships between elements within that structure. The elements are referred to as nodes, while the relationships between them are represented by lines, or edges, connecting pairs of elements. In the social analogy used to explain Ramsey\u2019s theorem, the graph representing the party consists of nodes (one for each guest) and edges (representing the relationship between each pair of guests, indicating whether they are mutual acquaintances or strangers). Edges connecting two acquaintances are typically depicted in blue by convention, while edges connecting two strangers are often colored red. The underlying concept of Ramsey\u2019s theorem is that within any structure comprising a set of elements, however large and random, there is always a subset of those elements \u2014 a smaller structure \u2014 that exhibits a certain degree of order.<\/p>\n \u201cEven amidst chaos, there is a trace of organization,\u201d explains Mota. Essentially, the solution to the problem reveals the minimum size that this chaotic structure must have in order for there to consistently exist a substructure with some form of pattern.<\/p>\n Revisiting the party example is helpful to clarify this central point. How many people, acquaintances or strangers, must there be in the set of party guests \u2014 an essentially chaotic structure \u2014 so that there always exists a group of k<\/em> mutual acquaintances or a group of k<\/em> mutual strangers? Both of these groups are a substructure with an inherent order.<\/p>\n \u201cThe significance of studying Ramsey\u2019s theorem is that we don\u2019t know much organization may be \u201chidden\u201d within a structure that, in other respects, seems random,\u201d says Morris. \u201cThis is a fundamental question in the study of large finite objects. Investigating Ramsey\u2019s theorem could lead to the development of a toolset that can be applied in a wide range of contexts.\u201d<\/p>\n J. M. Keynes Papers Archive \/ Wikimedia Commons<\/span>Frank Plumpton RamseyJ. M. Keynes Papers Archive \/ Wikimedia Commons<\/span><\/p><\/div><\/p>\n Ramsey\u2019s theorem is arguably the best-known scientific contribution of British mathematician Frank Plumpton Ramsey (1903\u20131930), who was regarded as a genius by his contemporaries. His work spanned the fields of mathematics, philosophy, and economics. Born in Cambridge, Ramsey was the son of a suffragette and a mathematics professor at Magdalene College, one of 31 colleges forming Cambridge University. He enrolled in higher education at the age of 17. In 1920 he gained admission to Trinity College, another renowned college in Cambridge, and graduated in 1923 as the top student in his mathematics class.<\/p>\n Proficient in German, during his second year of college, Ramsey began translating the book Tractatus logico-philosophicus<\/em> by Austrian philosopher Ludwig Wittgenstein (1889\u20131951) into English. Wittgenstein was one of the members of the influential Vienna Circle, a group of philosophers, mathematicians, and thinkers who regularly met in the Austrian capital during the 1920s to debate language and scientific methodology. Ramsey visited Vienna in 1923 and spent six months there the following year, during which he had the opportunity to meet Wittgenstein and other members of the circle.<\/p>\n He published the ideas behind his theorem (and which form the basis of graph theory) in 1930, the year of his untimely death, just before he turned 27. Ramsey died of mysterious causes after an emergency surgery, possibly due to kidney failure, jaundice, or leptospirosis.<\/div>\n![](\"\/wp-content\/uploads\/2023\/07\/ramsey_site-ok_328_eng3.png\")
\n <\/picture>Rodrigo Cunha \/ Revista Pesquisa FAPESP<\/span><\/div>
\n<\/strong>British mathematician Frank Plumpton Ramsey formulated the theorem that bears his name at the age of 26, shortly before his death<\/em><\/p>\n![\"\"](\"https:\/\/revistapesquisa.fapesp.br\/wp-content\/uploads\/2023\/07\/RPF-teorema-ramsey-2023-05-site-400.jpg\")
To a layperson this might appear modest, but what the researchers accomplished received global acclamation as a significant feat, with their paper receiving extensive coverage in science magazines and in the broader media. \u201cI was floored\u201d on learning about the paper, remarked mathematician Yuval Wigderson from Tel Aviv University, in an interview with Quanta Magazine<\/em>. \u201cI was literally shaking for half an hour to an hour.\u201d Guilherme Mota, a researcher from IME-USP who organized the seminar given by Campos at the S\u00e3o Paulo university, was also surprised by the contributions of his colleagues. \u201cEvery expert in combinatorics has tackled this theorem at some point,\u201d says Mota, who also works in the field and has collaborated with two of the four authors of the new paper. \u201cAfter such a long time without major breakthroughs, it was unexpected.\u201d<\/p>\n Formulated in 1930 by British mathematician Frank Plumpton Ramsey (1903\u20131930), the theorem that bears his name is as easy to understand as it is difficult to solve as the integer value in its formula increases. A popular adaptation of its formal statement poses the question in everyday terms: what is the minimum number of guests a party must have to ensure there are at least a given number of mutual acquaintances or at least the same number of mutual strangers?<\/em> It is not necessary that both conditions are satisfied. This mysterious number of guests is represented generically by the letter k <\/em>in the Ramsey theorem, denoted as R(k)<\/em>. In this example, it is assumed that the relationship of acquaintance or nonacquaintance is reciprocal: if one person is another person\u2019s acquaintance, then the latter is also the former\u2019s acquaintance.<\/p>\n<\/div>![](\"\/wp-content\/uploads\/2023\/07\/ramsey_site-ok_328_eng.png\")
\n <\/picture>