DADOS SOLICITADOS - RELATÓRIO PRONEX - ANO I

Periodo: 01/fevereiro/98 a 01/fevereiro/99

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.

A seguir, mencionamos alguns tópicos que vêm sendo estudados por participantes do Núcleo. A lista abaixo não pretende ser completa, mas apenas um apanhado ilustrativo de nossos interesses.

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.