![\"\"](\"https:\/\/cienciasbahia.org.br\/novo\/wp-content\/uploads\/2023\/04\/IMPA-descoberta-300x207.jpeg\")
<\/p>\n<\/p>\n
Nos \u00faltimos 88 anos, pesquisadores de todo o mundo tentaram avan\u00e7ar no limite superior para o Teorema de Ramsey, um dos primeiros na \u00e1rea de combinat\u00f3ria. Durante o Programa de Ver\u00e3o do IMPA (Instituto de Matem\u00e1tica Pura e Aplicada), um grupo composto por <\/span>Robert David Morris<\/span><\/a> (IMPA), que \u00e9 membro titular da Academia Brasileira de Ci\u00eancias; Marcelo Campos (doutor pelo IMPA); <\/span>Simon Griffiths<\/span><\/a> (PUC-Rio), membro afiliado da ABC; e Julian Sahasrabudhe (Cambridge) chegou a um novo algoritmo capaz de melhorar o limite do teorema. O avan\u00e7o \u00e9 o mais significativo na \u00e1rea desde 1935.<\/span><\/p>\n Proposto pelo brit\u00e2nico Frank Plumpton Ramsey (1903 \u20131930), o teorema procura encontrar regularidades dentro de uma estrutura larga e ca\u00f3tica. O estudo do problema abriu novas portas para a combinat\u00f3ria, ramo da matem\u00e1tica que estuda as maneiras pelas quais cole\u00e7\u00f5es finitas de objetos podem ser organizadas.<\/span><\/p>\n \u201cComo esse \u00e9 um dos problemas mais famosos de combinat\u00f3ria, quase todo mundo da \u00e1rea tentou resolv\u00ea-lo. E n\u00f3s ach\u00e1vamos que seria necess\u00e1ria uma ferramenta muito diferente ou que precis\u00e1vamos entender a \u2018estrutura\u2019 da colora\u00e7\u00e3o para chegar na resposta, mas a verdade \u00e9 que a prova \u00e9 mais simples do que todos esperavam\u201d, disse Robert Morris.<\/span><\/p>\n Marcelo Campos explicou o problema usando as redes sociais como exemplo. A Teoria de Ramsey atesta que para qualquer n\u00famero k, existe um n\u00famero R(k) com a seguinte propriedade: se houver R(k) pessoas no Facebook, e quaisquer duas delas forem amigas ou n\u00e3o se conhecerem, ent\u00e3o \u00e9 poss\u00edvel encontrar k pessoas que s\u00e3o ou todas amigas umas das outras ou todas desconhecidas.<\/span><\/p>\n \u201cA rede social representa o que na matem\u00e1tica chamamos de grafo. Para n\u00f3s o que importa \u00e9 a liga\u00e7\u00e3o entre os pontos de um grafo. Buscamos o tipo de estrutura em que todos os pontos est\u00e3o interligados ou que nenhum est\u00e1 ligado\u201d, explicou Campos. Encontrar essa estrutura n\u00e3o \u00e9 t\u00e3o simples, sobretudo se a colora\u00e7\u00e3o \u2013 ou seja, os pares interligados \u2013 s\u00e3o determinados de forma \u201cquase\u201d aleat\u00f3ria.<\/span><\/p>\n \u201cEsse conjunto, que no exemplo s\u00e3o as pessoas na rede social, pode ser pensado de v\u00e1rias formas. Ent\u00e3o, pensamos que temos um \u2018advers\u00e1rio\u2019 que pode adotar uma estrat\u00e9gia que dificulte isso, para lidar com o pior cen\u00e1rio poss\u00edvel. Uma das estrat\u00e9gias que ele poderia adotar \u00e9 conectar as pessoas aleatoriamente. Ou seja, \u00e9 como se jog\u00e1ssemos uma moeda e ela determinasse quem \u00e9 \u2018amigo\u2019 ou \u2018n\u00e3o amigo\u2019 dentro do Facebook. O que a gente quer provar \u00e9 que o algoritmo encontra a estrutura que estamos buscando mesmo assim.\u201d<\/span><\/p>\n Desafiadora, a teoria se revelou um campo vasto e foi explorada pelo matem\u00e1tico brit\u00e2nico William Timothy Gowers, ganhador da Medalha Fields, em 1998. Em uma sequ\u00eancia de tweets, Gowers reconheceu o progresso do grupo. \u201cBasicamente todos os pesquisadores de combinat\u00f3ria tentaram arduamente responder essa pergunta, incluindo eu mesmo\u201d, escreveu.<\/span><\/p>\n \u00daLTIMO AVAN\u00c7O NO LIMITE SUPERIOR FOI EM 1935<\/span><\/p>\n O problema \u00e9 interpretado a partir da Teoria dos Grafos, onde os objetos \u2013 chamados v\u00e9rtices \u2013 s\u00e3o interligados por arestas com cores azuis ou vermelhas. Os conjuntos s\u00e3o chamados de \u201ccliques\u201d e a quest\u00e3o \u00e9: qual \u00e9 o n\u00famero de v\u00e9rtices necess\u00e1rio para garantir a exist\u00eancia de um clique de um certo tamanho com arestas de uma s\u00f3 cor?<\/span><\/p>\n Em 1935, Erd\u0151s e Szekeres mostraram u\u00a0 resultado pioneiro e chegaram ao limite superior R(k)<4^k atrav\u00e9s de um algoritmo. Campos, Griffiths, Morris e Sahasrabudhe encontraram um novo limite superior: (3,995)^k. \u201c\u00c9 uma busca por um tipo de subestrutura em um grafo. N\u00f3s conseguimos dar a primeira melhoria exponencial para esse trabalho. Esse algoritmo permite que encontremos a subestrutura de forma mais eficiente \u2013 e funciona para qualquer grafo que voc\u00ea queira. Sempre vai ser poss\u00edvel encontrar a subestrutura\u201d, disse Campos.<\/span><\/p>\n O resultado pode contribuir para a pesquisa dos especialistas em combinat\u00f3ria e, inclusive, gerar desdobramentos em outras \u00e1reas. \u201cEm um problema como esse, voc\u00ea quer entender o objeto, ent\u00e3o quanto mais provas melhor. Achar provas diferentes da mesma coisa pode abrir caminhos que voc\u00ea nem imaginava que existiam. Esperamos que o nosso trabalho fa\u00e7a com que outras pessoas tamb\u00e9m encontrem provas diferentes deste teorema. A troca de ideias enriquece a matem\u00e1tica\u201d, disse Morris.<\/span><\/p>\n Desde 2018, o grupo se re\u00fane para explorar o problema e, ap\u00f3s muitas tentativas, foi poss\u00edvel definir a melhor solu\u00e7\u00e3o encontrada. O momento \u201ceureca\u201d aconteceu durante o Programa de Ver\u00e3o do IMPA, oportunidade \u00fanica para os matem\u00e1ticos se encontrarem presencialmente, visto que Julian Sahasrabudhe \u00e9 professor assistente na Universidade de Cambridge. Anteriormente, Sahasrabudhe foi p\u00f3s-doutor de excel\u00eancia do IMPA (2017-2018), assim como <\/span>Simon Griffiths<\/span><\/a>, tamb\u00e9m p\u00f3s-doutor de excel\u00eancia do instituto (2010-2013) e atual professor adjunto da PUC-Rio. J\u00e1 Marcelo Campos foi orientado por Robert Morris no doutorado e apresentou a tese em mar\u00e7o deste ano.<\/span><\/p>\n Fonte: IMPA \/ Academia Brasileira de Ci\u00eancias<\/span><\/p>\n Foto: IMPA (<\/span>Robert Morris<\/span><\/a>, Julian Sahasrabudhe, <\/span>Simon Griffiths<\/span><\/a> e Marcelo Campos)<\/span><\/p>\n","protected":false},"excerpt":{"rendered":" Nos \u00faltimos 88 anos, pesquisadores de todo o mundo tentaram avan\u00e7ar no limite superior para o Teorema de Ramsey, um dos primeiros na \u00e1rea de combinat\u00f3ria. Durante o Programa de Ver\u00e3o do IMPA (Instituto de Matem\u00e1tica Pura e Aplicada), um grupo composto por Robert David Morris (IMPA), que \u00e9 membro titular da Academia Brasileira de […]<\/p>\n","protected":false},"author":3,"featured_media":4370,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","footnotes":""},"categories":[1],"tags":[],"class_list":["post-4369","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-noticias"],"acf":[],"_links":{"self":[{"href":"https:\/\/cienciasbahia.org.br\/novo\/wp-json\/wp\/v2\/posts\/4369","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cienciasbahia.org.br\/novo\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/cienciasbahia.org.br\/novo\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/cienciasbahia.org.br\/novo\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/cienciasbahia.org.br\/novo\/wp-json\/wp\/v2\/comments?post=4369"}],"version-history":[{"count":1,"href":"https:\/\/cienciasbahia.org.br\/novo\/wp-json\/wp\/v2\/posts\/4369\/revisions"}],"predecessor-version":[{"id":4371,"href":"https:\/\/cienciasbahia.org.br\/novo\/wp-json\/wp\/v2\/posts\/4369\/revisions\/4371"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/cienciasbahia.org.br\/novo\/wp-json\/wp\/v2\/media\/4370"}],"wp:attachment":[{"href":"https:\/\/cienciasbahia.org.br\/novo\/wp-json\/wp\/v2\/media?parent=4369"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/cienciasbahia.org.br\/novo\/wp-json\/wp\/v2\/categories?post=4369"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/cienciasbahia.org.br\/novo\/wp-json\/wp\/v2\/tags?post=4369"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}