Prêmios e Destaques Acadêmicos
Simon Griffths, da PUC-Rio, junto aos professores Robert Morris, do Impa, Yoshiharu Kohayakawa, do IME-SP - Foto: acervo pessoal
O artigo The Chromatic Thresholds of Graphs, de autoria do professor Simon Griffiths, do Departamento de Matemática, e dos pesquisadores Robert Morris, do Impa, Yoshiharu Kohayakawa, do IME-SP, e Peter Allen e Julia Böttcher, da London School of Economics and Political Science, recebeu o Prêmio Fulkerson, considerado o “Nobel” da área de combinatória, otimização combinatória e algoritmos.
Concedido pela Mathematical Opitimization Society e pela American Mathematical Society, a cada três anos, para artigos de excelência em Matemática Discreta, a premiação fez parte do 23º Simpósio Internacional de Programação Matemática, realizado na França, entre os dias 1 e 6 de julho.
- De maneira geral, um grafo é uma rede abstrata, como a rede de amizades do Facebook, uma rede de computadores ou as vizinhanças entre países, explica Griffiths.
Segundo o professor, o resultado mais famoso da teoria dos grafos é que bastam quatro cores para se obter um mapa em que países vizinhos tenham cores diferentes. "Uma coloração dos vértices de um grafo G é válida se os vértices conectados por uma aresta sempre receberem cores diferentes", observa. Os matemáticos Kenneth Appel e Wolfgang Haken receberam o prêmio Fulkerson em seu primeiro ano, 1979, por este resultado.
Para Griffiths, o Teorema das Quatro Cores é interessante por atribuir um limite superior fixo, de 4, que não depende do tamanho do grafo. “O resultado vale tanto para um mapa com dez países quanto para um mapa com milhões de países”. Ele esclarece que uma família de grafos é simples se cada grafo tiver uma coloração válida com, no máximo, C cores, para alguma constante fixa de C. “Dado o Teorema das Quatro Cores, era natural perguntar quais outras infinitas famílias de grafos seriam simples”.
No artigo premiado The Chromatic Thresholds of Graphs, os autores encontraram muitas outras famílias simples. “Além disso, o resultado principal caracteriza quando certas condições geram uma família simples”, resume o matemático.
Simon Griffiths tem quatro pós-doutorados, ministra aulas e realiza pesquisas na área de Combinatória e Probabilidade na PUC-Rio desde 2016.
Os professores Peter Allen e Julia Böttcher, da London School of Economics and Political Science - Foto: acervo pessoal