O objetivo deste projeto é o de desenvolver pesquisa de primeira linha em combinatória, vista fundamentalmente como uma disciplina dentro da teoria da computação, mas que se situa na fronteira entre a computação e a matemática pura.
As linhas de pesquisa são três, e podem ser caracterizadas pelos seguintes problemas:
Justificamos este projeto pela reconhecida importância da combinatória na teoria da computação. Problemas de caráter combinatório ocorrem freqüentemente em várias áreas da matemática e são fundamentais em essencialmente todas as áreas da teoria da computação. A teoria da computação, por sua vez, dá o fundamento teórico sobre o qual a ciência da computação se apóia, e é de fato a existência de tal fundamento sólido que a caracteriza como uma ciência. Ademais, é a teoria que proporciona à ciência da computação uma robustez capaz de absorver o rápido desenvolvimento da tecnologia de forma mais eficiente possível. É objetivo deste projeto contribuir ao estado-da-arte da teoria da computação através de investigações vigorosas de uma coleção específica de problemas combinatórios.
Concretamente, a motivação que gera esta proposta reside na necessidade de haver uma infraestrutura de suporte à pesquisa integrada em combinatória no país. Por exemplo, a cooperação entre os pesquisadores no país deve ser aumentada, e para tanto o suporte financeiro para encontros periódicos entre os pesquisadores precisa ser garantido. A nível internacional, o intercâmbio de pesquisadores entre o país e os centros de pesquisa no exterior deve ser facilitado.
Contemplamos neste projeto a organização de três oficinas nacionais e um workshop internacional ao longo dos dois anos de duração do projeto. O workshop contará com especialistas do exterior, que ministrarão mini-cursos em assuntos de pesquisa de ponta. As oficinas terão caráter mais local, sendo duas as suas funções primordiais: (i) a de ser um ponto de verificação objetiva do andamento do projeto, através de apresentações de trabalhos de pesquisa realizados até então, e (ii) a de ser um ponto de entrosamento dos integrantes do grupo e de atração de pesquisadores de outras instituições. Nestas ocasiões, pretendemos divulgar amplamente estes encontros, convidando especialmente pesquisadores de centros emergentes com os quais desejamos estreitar contatos. Em particular, o projeto terá como subproduto certo quatro atas (um para cada evento) com publicações deste grupo de pesquisa e com contribuições de autores nacionais e internacionais convidados.
A nossa meta dentro deste projeto é o de desenvolver, através da cooperação entre as instituições participantes e de intercâmbios com centros de pesquisa internacionais de excelência, pesquisas que gerem resultados em teoria da computação que possam ser julgados favoravelmente dentro do critério natural para esta área: por um lado objetiva-se obter resultados aplicáveis a problemas computacionais reais, mas por outro exige-se fundamentação teórica para os resultados obtidos. Efetivamente, caso a cooperação e a integração entre as várias instituições deste projeto se dêem de forma esperada, considerando-se a magnitude deste projeto e o porte do grupo de pesquisa envolvido, podemos ter como meta a elaboração de um número significativo, da ordem de algumas dezenas, de trabalhos para publicação em periódicos e congressos internacionais. O nível de atividade científica na área de teoria da computação, ou mais especificamente em combinatória, poderá então ser considerado altamente satisfatório no país.
Além do fortalecimento deste grupo de pesquisa em teoria da computação, o sucesso deste projeto trará como conseqüência a formação de recursos humanos de alta qualidade em computação.
Finalmente, descrevemos de forma breve os três problemas que serão o objeto das investigações deste projeto. Os objetos combinatórios mais bem estudados até hoje são, provavelmente, os grafos. O Problema 1 versa sobre alguns aspectos centrais da teoria dos grafos: coloração de grafos; estudo de classes de grafos do ponto de vista estrutural e a aplicação dos resultados obtidos no espírito das aplicações de algoritmos gráficos à biologia computacional; otimização em grafos, incluindo problemas sobre circuitos e caminhos ótimos, sobre emparelhamentos máximos, e sobre cortes e transversais em grafos. O Problema 2 versa sobre métodos que têm origem fora da combinatória clássica: os métodos poliedrais usam ferramentas de combinatória poliédrica combinados com técnicas de programação linear para resolver problemas NP-difíceis de grande porte (surge neste contexto a necessidade de se desenvolver métodos heurísticos ou exatos para a determinação eficiente dos chamados `planos-de-corte'); os métodos multi-algorítmicos combinam vários algoritmos de forma não-trivial e conseguem muitas vezes obter resultados inesperados quando aplicados a problemas NP-difíceis. Finalmente, o nosso Problema 3 concerne à introdução de elementos aleatórios em problemas combinatórios ou computacionais usualmente determinísticos; é o estudo das conseqüências surpreendentes desta idéia que forma a parte central deste problema. Temos aqui em mente desde resultados recentes de complexidade computacional (verificação de provas e aproximabilidade) até os resultados recentes da combinatória probabilística como aqueles sobre as propriedades de Ramsey de grafos aleatórios.