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. � o 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, divulgaremos 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 investigados neste neste projeto. Notemos em primeiro lugar que as estruturas combinat�rios mais bem estudadas at� hoje s�o, provavelmente, os grafos. Aqui estar�o eles tamb�m presentes em praticamente todos os t�picos a serem estudados. 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.