Objetivos (Numere e enuncie os objetivos do projeto, tal como proposto)

Objetivo 1:

Fomentar a integra��o dos diversos centros de pesquisa interessados na �rea de Combinat�ria, ampliando o grau de intera��o iniciado pelo projeto ProComb (que integrou diversos pesquisadores deste projeto e foi financiado pelo ProTem-CC-II do CNPq).

Objetivo 2:

Aumentar a produ��o cient�fica do grupo atrav�s de uma maior quantidade de publica��es em revistas internacionais de primeira linha, assim como uma maior participa��o da equipe em congressos realizados no exterior e no pa�s.

Objetivo 3:

Aumentar a participa��o da equipe na comunidade nacional de Ci�ncia da Computa��o e Matem�tica.

Objetivo 4:

Ampliar ainda mais a forma��o de profissionais na �rea, atraindo, atrav�s de maior divulga��o das atividades da equipe, mais estudantes de doutorado, mestrado e inicia��o cient�fica.

Os pesquisadores deste projeto t�m especial interesse pelos seguintes subtemas:

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.

Problemas num�ricos em teoria de Ramsey; estudo de variedades e matr�ides; enumera��o de grafos com subgrafos proibidos; grafos de comparabilidade; investiga��o poli�drica de problemas combinat�rios; geometria computacional; cortes e empacotamentos; algoritmos e teoria dos jogos.

Comente resumidamente o andamento do projeto, com relacao a cada objetivo acima (utilize apenas esta p�gina)

Objetivo 1:

A integra��o dos centros de pesquisa participantes deste projeto aumentou significativamente nesse primeiro ano, prenunciando um aumento ainda maior nos pr�ximos anos. Para destacar essa integra��o mencionamos alguns dos trabalhos conjuntos inter-institucionais que resultaram da pesquisa desenvolvida dentro deste projeto.

- UFRJ e UNICAMP. Pesquisadores dessas instituti��es t�m v�rios trabalhos em co-autoria na �rea de grafos. Por exemplo, em colora��o de grafos: Celina M. H. de Figueiredo (UFRJ), C�lia P. Mello (UNICAMP) e J. Meidanis (UNICAMP).

- UNICAMP e USP. Pesquisas na �rea de combinat�ria poli�drica t�m sido desenvolvidas pelos pesquisadores Cid C. de Souza (UNICAMP), Carlos E. Ferreira (USP) e Y. Wakabayashi (USP). Estudos sobre problemas de cortes e empacotamentos t�m sido desenvolvidos por Fl�vio K. Miyazawa (UNICAMP), Carlos E. Ferreira (USP) e Y. Wakabayashi (USP).

- UFMS e UNICAMP. Pesquisa sobre ``matching covered graphs'' t�m sido desenvolvidas por M.H. Carvalho (UFMS) e C.L. Lucchesi (UNICAMP); alguns em co-autoria com U.S.R. Murty (Waterloo).

- UFRJ, UNICAMP e USP. Na pesquisa relativa ao estudo de n�o-planaridade em grafos, trabalhos est�o sendo desenvolvidos pelos pesquisadores Celina M. H. de Figueiredo (UFRJ), Candido Xavier de M. Neto (UNICAMP) e Cristina G. Fernandes (USP).

Al�m dessa integra��o dentro do pa�s, houve um interc�mbio com centros de pesquisa no exterior, que foi extremamente prof�cua. Foram mantidos contatos estreitos com v�rios pesquisadores do exterior, dentre os quais destacamos: B. Bollob�s (Cambridge, e Memphis), P.E. Haxell (Waterloo). Reed (CNRS, Paris), V. R�dl (Emory University, Atlanta), E. Szemer�di (Rutgers University, NJ), R. Thomas (Georgia Tech), Z. F�redi (Urbana e Budapest), U.S.R. Murty (Waterloo), D. Younger (Waterloo), H-J. Pr�mel (Humboldt-Universit�t, Berlin), L.A. Wolsey (CORE- Louvain), J. Oxley (Lousiana State University), A. Martin (ZIB-Berlin), F. Maffray (...), H. Everett(..).

Esses pesquisadores e outros n�o mencionados aqui foram co-autores de 50% dos artigos em revistas indexadas que foram publicados ou aceitos no per�odo.

Est� prevista a realiza��o de um Workshop Internacional em 1999. Esperamos que este evento venha alavancar novos trabalhos em parceria, al�m de estreitar o interc�mbio com pesquisadores do exterior. Este evento ser� em homenagem a W.T.Tutte (Waterloo), pesquisador que trouxe grandes contribui��es � �rea de Combinat�ria. O Workshop estava previsto para o ano de 1998, mas foi adiado devido � dificuldade para agendar uma data que possibilitasse a vinda de Tutte ao Brasil. Al�m de W.T. Tutte, os pesquisadores D. Younger e U.S. Murty j� confirmaram a sua presen�a.

Foi criada uma homepage deste projeto, onde consta a lista de publica��es do grupo (e os arquivos em postscript dos trabalhos), bem como outras informa��es pertinentes: http://www.ime.usp.br/ yoshi/pronex/. Dessa forma, o grupo tem se mantido atualizado com rela��o ao andamento do projeto.

Objetivo 2:

A produ��o cient�fica do grupo nesse primeiro ano foi boa. O grupo publicou (ou teve aceita��o de) 29 artigos em revistas indexadas, e submeteu 23 artigos; totalizando 52 artigos. Publicou 3 livros did�ticos completos e um de seus membros foi o editor de um volume especial da Lecture Notes in Computer Science, dedicado ao LATIN'98. Apresentou 20 trabalhos em congressos no exterior, dos quais 12 deles resultaram em trabalhos completos publicados como cap�tulos de livros ou revistas dedicadas ao evento. Apresentou 9 trabalhos em congressos nacionais.

Vale aqui destacar que o grupo teve trabalhos publicados/aceitos em peri�dicos de reconhecida qualidade, como ADVANCES IN MATHEMATICS, ALGORITHMICA, ANNALS OF APPLIED PROBABILITY, COMBINATORICA, DISCRETE APPLIED MATHEMATICS, JOURNAL OF ALGEBRA, JOURNAL OF ALGORITHMS, JOURNAL OF COMBINATORIAL THEORY (B), JOURNAL OF GRAPH THEORY, JOURNAL OF THE LONDON MATHEMATICAL SOCIETY, MATHEMATICAL PROGRAMMING, RANDOM STRUCTURES AND ALGORITHMS, SIAM JOURNAL ON COMPUTING e SIAM JOURNAL ON OPTIMIZATION. Tratam-se de peri�dicos de primeira linha na �rea em que o grupo atua.

A participa��o da equipe em congressos de primeira linha no exterior mostra que os participantes t�m feito pesquisa de ponta e de grande interesse para a comunidade internacional. Membros desta equipe participaram (quase sempre apresentando trabalhos ou como palestrantes convidados) do IPCO'98 (Integer Programming and Combinatorial Optimization), SODA'99 (Symposium on Discrete Algorithms), LATIN'98 (Latin-American Theoretical informatics), CPM'98 (Combinatorial Pattern Matching), ICM'98 (International Congress of Mathematicians), Probabilistic Combinatorics (Budapest), 5th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications (Praga), e de duas oficinas promovidas em 1998 pelo DIMACS (Center for Discrete Mathematics and Theoretical Computer Science, um centro de excel�ncia na �rea).

Um dos membros da equipe (Lucchesi) foi o presidente do comit� de programa do LATIN'98 e outro participante deste projeto foi membro deste comit�.

Considerando que ..... artigos foram submetidos e .... est�o sendo preparados, e algumas colabora��es novas entre os integrantes est�o surgindo, consideramos o saldo bastante positivo neste primeiro ano.

Objetivo 3:

A participa��o da equipe na comunidade nacional de Ci�ncia da Computa��o e Matem�tica foi significativa. Nesse per�odo a equipe participou de eventos nacionais como Congresso da SBC, JAI, CNMAC, SOBRAPO e Escola de Computa��o, apresentando trabalhos ou mini-cursos. Integrantes desta equipe atuaram e continuar�o a atuar em comit�s cient�ficos de destaque no pa�s. No ``Comit� Assessor de Ci�ncia da Computa��o do CNPq'': Y. Wakabayashi (97-98) e Y. Kohayakawa (a partir de 99); e na ``Coordena��o da �rea de Matem�tica e Ci�ncia da Computa��o da FAPESP'': C. Lucchesi (97-98) e Y. Kohayakawa (desde dez/98).

V�rios projetos de coopera��o tanto nacionais como internacionais tamb�m t�m sido liderados por membros desta equipe: Projeto Genoma/FAPESP para sequenciamento da bact�ria Xylella fastidiosa (J. Carlos Setubal e J. Meidanis). Projeto PROBRAL/CAPES-DAAD (Y. Kohayakawa), Projeto CAPES-COFECUB (Y. Wakabayashi) e outros.

As atividades mencionadas mostram uma efetiva participa��o de integrantes desta equipe no cen�rio acad�mico nacional.

Objetivo 4:

Nesse per�odo a equipe formou 11 alunos de inicia��o cient�fica, 13 mestres e 2 doutores. Tem atualmente 22 alunos de inicia��o cient�fica, 26 mestrandos e 17 doutorandos. Um doutorado desse grupo recebeu o primeiro pr�mio no Concurso de Teses e Disserta��es (CTD'98), promovido pela SBC.

• Sobre este documento...