Aspectos estruturais e algorítmicos de objetos combinatórios

Resumo

O objeto central da pesquisa proposta neste projeto temático é investigar aspectos estruturais de objetos combinatórios. Os aspectos específicos a serem abordados serão aqueles motivados por (i) seu interesse intrínseco, vistos como tópicos da matemática pura, e pela (ii) sua importância para o desenvolvimento de algoritmos eficientes para problemas computacionais combinatórios específicos ou para a identificação da complexidade computacional de tais problemas. Principais subtemas a serem abordados neste projeto: 1. propriedades assintóticas de estruturas combinatórias, investigadas através de métodos combinatórios e extra-combinatórios, como métodos probabilísticos, algébricos, e topológicos; 2. propriedades estruturais de grafos, hipergrafos, e estruturas correlatas; 3. métodos e problemas geométricos em combinatória, com especial ênfase em métodos poliédricos em otimização combinatória. Uma lista de tópicos específicos de pesquisa, que não esgotam mas ilustram os nossos interesses, é a seguinte: problemas numéricos em teoria de Ramsey, problemas extremais tipo Turán, enumeração assintótica de grafos, objetos pseudo-aleatórios e suas aplicações, métodos algébricos e topológicos, bases de Hilbert, compressão de dados, problemas de empacotamento tridimensional, investigação poliédrica de problemas combinatórios, algoritmos de aproximação.(AU)