ASPECTOS ESTRUTURAIS E ALGORÍTMICOS DE OBJETOS COMBINATÓRIOS

Y. KOHAYAKAWA

Resumo. Apresentamos neste relatório as atividades científicas de nossa equipe no período de outubro de 1996 a dezembro de 1998.

Sumário

1. Introdução 2 2. Equipe 3 3. Publicações 4 4. Orientações 7 5. Viagens 9 6. Visitantes 12 7. Eventos 13 8. Auxílios Vigentes 15 9. Prêmios e Honrarias 17 10. Outras Atividades 17 11. Conclusão e Análise Crítica 17

Data: 30 de dezembro de 1998. Processo fapesp 96/04505–2.

1. Introdução

Este relatório científico refere-se ao período de outubro de 1996 a dezembro de 1998. Enumeramos sucintamente aqui algumas informações para dar uma idéia inicial de nossas atividades neste período.

1.1. Equipe. A equipe do projeto temático Aspectos Estruturais e Algorítmicos de Objetos Combinatórios (Proc. fapesp no. 96/04505–2) é formada atualmente por 8 professores doutores do Departamento de Ciência da Computação da Universidade de São Paulo.

O grupo recebeu a visita de cerca de 15 pesquisadores estrangeiros durante o período, cujas permanências variaram desde alguns dias a algumas semanas. A equipe também contou com um visitante de longa duração, o prof. Bruce Reed (financiado pela fapesp), que deu grande impulso às atividades do grupo.

Esta equipe é atualmente responsável por 7 alunos de doutorado e 8 alunos de mestrado, e orienta ou orientou 9 alunos de iniciação científica no período referente a este relatório. Durante este período, a equipe formou 6 mestres e 1 doutor, hoje docente do Instituto de Computação da UNICAMP.

1.2. Publicações. A lista de publicações no período consiste de 22 artigos (publicados e aceitos para publicação) e 12 submissões em periódicos internacionais com arbitragem, 1 artigo em periódico nacional, 14 trabalhos completos/resumos estendidos em anais de congressos nacionais e internacionais e coletâneas e 2 livros.

Vários membros da equipe participaram de eventos internacionais e nacionais, tendo apresentado mais de 20 trabalhos.

Embora o volume de trabalhos publicados por nossa equipe não seja particularmente grande, destacamos que estes trabalhos apareceram em periódicos de primeira linha, como Journal of Algorithms, Journal of Combinatorial Theory, Series B, Combinatorica, SIAM Journal on Optimization, SIAM Journal on Computing, Algorithmica, Acta Arithmetica, Journal of the London Mathematical Society, Journal of Algebra, e Annals of Applied Probability, e também em congressos de alta competitividade, como o ACM–SIAM Symposium on Discrete Algorithms (SODA).

1.3. Eventos e seminários. A nossa equipe realizou os seguintes eventos no período: Workshop on Probabilistic Methods in Combinatorics and Theoretical Computer Science, o Dia da Combinatória, uma série de Lectures on Treedecompositions, Permanents, Pfaffian Orientations and Even Directed Circuit, um Minicurso sobre Bases de Gröbner, e o Dia de Otimização e Combinatória.

Na oficina de métodos probabilísticos mencionada acima, participaram pesquisadores como N. Alon, Z. Füredi, P. Pudlák, e J.H. Kim. Tivemos portanto 3 palestrantes de Congressos Internacionais de Matemáticos [Tóquio (NA), Zurique (ZF e PP)] e um ganhador da Medalha Fulkerson [Lausanne (JHK)]! A série de palestras sobre decomposição arbórea e temas correlatos ficou sob a responsabilidade do prof. R. Thomas, um dos expoentes máximos na teoria de Robertson-Seymour.

Naturalmente, a equipe mantém e participa ativamente de um seminário semanal com a participação de visitantes estrangeiros do grupo e pesquisadores nacionais de outras instituições ou departamentos.

1.4. Aquisição de equipamento. Foram adquiridos através da verba deste projeto temático 10 X-terminais HP Envizex, com o objetivo de equipar os membros do grupo que ainda não dispunham de terminais, e reequipar aqueles que dispunham de equipamentos já obsoletos.

Igualmente importante foram os pedidos complementares que foram feitos ao longo do projeto até agora.

2. Equipe

2.1. Pesquisadores. A equipe consiste dos seguintes membros do Departamento de Ciência da Computação da USP:

1. Arnaldo Mandel, PhD, Waterloo, 1982; especialidades: matróides, teoria de anéis.

2. Carlos Eduardo Ferreira, Dr. rer. nat., Tech. Uni., Berlim, 1994; métodos poliédricos e otimização combinatória em geral.

3. Cristina Gomes Fernandes, PhD, Georgia Tech, 1997; algoritmos on-line e algoritmos de aproximação. [Esteve afastada para cumprir programa de doutoramento; retornou em julho de 1997]

4. José Augusto Ramos Soares, PhD, Chicago, 1992; algoritmos combinatórios, problemas extremais, compressão de dados.

5. José Coelho de Pina Júnior, Doctor, Amsterdã, 1995; algoritmos combinatórios.

6. Maria Angela de Campos Gurgel, Doutora, USP, 1992; métodos poliédricos em otimização combinatória. [Recém-aposentada]

7. Paulo Feofiloff, PhD, Waterloo, 1983; otimização combinatória, identidades min-max.

8. Yoshiharu Kohayakawa, PhD, Cambridge, 1990; métodos probabilísticos, problemas extremais. [Coordenador do projeto]

9. Yoshiko Wakabayashi, Dr. rer. nat., Augusburg, 1986; grafos, métodos poliédricos e otimização combinatória em geral.

2.2. Alunos envolvidos. A equipe é atualmente responsável pelos seguintes alunos do nosso departamento.

– Doutorado: 1. Estela Maris Rodrigues, Mestre, USP

2. Francisco Elói Soares de Araujo, Mestre, USP

3. Glauber Ferreira Cintra, Mestre, USP

4. Jair Donadelli Júnior, Mestre, USP

5. Liliane Rose Benning Salgado, Mestre, UFPE

6. Marco Aurélio Stefanes, Mestre, USP

7. Orlando Lee, Mestre, USP

– Mestrado: 1. Alexandre Scalzitti

2. Aritanan Borges Garcia Gruber

3. Carlos Ramon Pantaleon Dionisio

4. Edésio Raimundo Sibrão

5. Márcio Grossi de Almeida

6. Mario Leston Rey

7. Luiz Carlos Rozante

8. Said Sadique Adi – Iniciação científica (no período):

Alexandre Cardoso Garcia Leite, Cassio Polpo de Campos, Dan Faccio, Eduardo Garcia de Freitas, Luciano Micheletti Hespanhol, Rodrigo Nonamor Pereira Mariano de Souza, Rogério Brito, Sérgio Gabriel Tavares, Thiago Teixeira Santos.

2.3. Alunos formados. Durante o período, a equipe formou os seguintes alunos.

– Doutorado:

1. Flávio Keidi Miyazawa (Mestre-USP), doutorou-se em dezembro/97.

– Mestrado:

1. Armando Ramos Gouveia, obteve o grau de mestre em novembro/98.

2. César Alberto Bravo Pariente, obteve o grau de mestre em novembro/96.

3. Estela Maris Rodrigues, obteve o grau de mestre em fevereiro/97.

4. Francisco Elói Soares de Araujo, obteve o grau de mestre em agosto/98.

5. Glauber Ferreira Cintra, obteve o grau de mestre em julho/98.

6. Marco Aurélio Stefanes, obteve o grau de mestre em fevereiro/98.

2.4. Página na Teia. Mantemos uma página com informações sobre o projeto e atividades afins.

  http://www.ime.usp.br/~cris/gcomb/tem-fapesp/

Usamos a página acima para manter amplamente disponíveis versões eletrônicas da grande maioria dos nossos trabalhos científicos, como proposto em nosso projeto inicial.

3. Publicações

Observação. Enumeramos abaixo as publicações de nosso grupo no período coberto por este relatório. Observamos que algumas publicações são fruto de trabalhos anteriores. Incluímos também vários trabalhos do prof. Bruce Reed elaborados durante a sua estadia conosco (veja Seção 6). Esperamos que a inclusão destes trabalhos forneça uma fotografia mais completa, como um todo, da produção científica de nosso grupo no período contemplado neste relatório.

3.1. Periódicos internacionais arbitrados.

1. B. Bollobás, Y. Kohayakawa, and R.H. Schelp, On essentially infinite colourings, Journal of the London Mathematical Society, to appear.

2. R. Borndörfer, C.E. Ferreira, and A. Martin, Decomposing matrices into blocks, SIAM Journal on Optimization, to appear.

3. G. Călinescu, C.G. Fernandes, U. Finkler, and H. Karloff, A better approximation algorithm for finding planar subgraphs, Journal of Algorithms 27 (1998), 269–302.

4. P. Erdős, A. Gyárfás, and Y. Kohayakawa, The size of the largest bipartite subgraphs, Discrete Mathematics 177 (1997), no. 1–3, 267–271.

5. C.G. Fernandes, A better approximation ratio for the minimum k-edge-connected spanning subgraph problem, Journal of Algorithms 28 (1998), 105– 124.

6. L.R.G. Fontes, M. Isopi, Y. Kohayakawa, and P. Picco, The spectral gap of the REM under the Metropolis dynamics, Annals of Applied Probability 8 (1998), no. 3, 917–943.

7. J.Z. Gonçalves, A. Mandel, and M. Shirvani, Free products of units in algebras. Part I: quaternion algebras, Journal of Algebra, to appear.

8. M.A.M.C. Gurgel and Y. Wakabayashi, Adjacency of vertices of the complete pre-order polytope, Discrete Mathematics 175 (1997), no. 1–3, 163–172.

9. P.E. Haxell and Y. Kohayakawa, Partitioning by monochromatic trees, Journal of Combinatorial Theory, Series B 68 (1996), no. 2, 218–222.

10. , Packing and covering triangles in tripartite graphs, Graphs and Combinatorics 14 (1998), no. 1, 1–10.

11. P.E. Haxell, Y. Kohayakawa, and T. Łuczak, Turán’s extremal problem in random graphs: forbidding odd cycles, Combinatorica 16 (1996), no. 1, 107–122.

12. Y. Kohayakawa and B. Kreuter, Threshold functions for asymmetric Ramsey properties involving cycles, Random Structures and Algorithms 11 (1997), no. 3, 245–276.

13. Y. Kohayakawa, B. Kreuter, and A. Steger, An extremal problem for random graphs and the number of graphs with large even-girth, Combinatorica 18 (1998), no. 1, 101–120.

14. Y. Kohayakawa, T. Łuczak, and V. Rödl, Arithmetic progressions of length three in subsets of a random set, Acta Arithmetica LXXV (1996), no. 2, 133–163.

15. , Ramsey-type results for oriented trees, Journal of Graph Theory 22 (1996), no. 1, 1–8.

16. Y. Kohayakawa, T. Łuczak, and V. Rödl, On K^{4}-free subgraphs of random graphs, Combinatorica 17 (1997), no. 2, 173–213.

17. Y. Kohayakawa, H.-J. Prömel, and V. Rödl, Induced Ramsey numbers, Combinatorica, to appear.

18. F.K. Miyazawa and Y. Wakabayashi, Approximation algorithms for the orthogonal z-oriented 3-D packing problem, SIAM Journal on Computing, to appear.

19. , An algorithm for the three-dimensional packing problem with asymptotic performance analysis, Algorithmica 18 (1997), 122–144.

20. B. Reed, The list colouring constants, Journal of Graph Theory, to appear.

21. , Mongoes and blueberries, Combinatorica, to appear.

22. , A strengthening of Brooks’ theorem, Journal of Combinatorial Series (B), to appear.

3.2. Periódico nacional. [Indexado no Mathematical Reviews]

1. Y. Wakabayashi, The complexity of computing medians of relations, Resenhas 3 (1998), no. 3, 323–349.

3.3. Livros.

1. P. Feofiloff, Algoritmos de programação linear, Editora da Universidade de São Paulo, 1999.

2. C.E. Ferreira and Y. Wakabayashi, Planos-de-corte faciais e a resolução de problemas de otimização combinatória, I Encontro de Matemática Aplicada e Computacional, ERMAC, São Paulo, Brasil, Junho 1998.

3.4. Anais de Congressos Internacionais e Coletâneas.

1. J. Barrera, C.E. Ferreira, and R.F. Hashimoto, Finding optimal sequential decompositions of erosions and dilations, Mathematical morphology and its applications to image and signal processing (Kluwer Academic, ed.), 1998.

2. B. Bollobás and Y. Kohayakawa, On Richardson’s model on the hypercube, Combinatorics, Geometry and Probability (B. Bollobás and A. Thomason, eds.), Cambridge University Press, Cambridge, 1997, ISBN 0 521 584728, pp. 129– 137.

3. G. Călinescu, C.G. Fernandes, and B. Reed, Multicuts in unweighted graphs with bounded degree and bounded tree-width, Integer Programming and Combinatorial Optimization (Berlin) (R. E. Bixby, E. A. Boyd, and R. Z. Ríos-Mercado, eds.), Lecture Notes in Computer Science, vol. 1412, Springer, 1998, pp. 137–152.

4. C.G. Fernandes, A better approximation ratio for the minimum k-edge-connected spanning subgraph problem, Proc. 8th Annual ACM–SIAM Symposium on Discrete Algorithms (EUA), 1997, pp. 629–638.

5. C.E. Ferreira, C.C. de Souza, and Y. Wakabayashi, Rearrangement of DNA fragments: a branch-and-cut algorithm, Proceedings of the 2nd Workshop on Practical Combinatorial Optimization Problems (Valparaiso, Chile), novembro 1996.

6. , A polyhedral approach for DNA fragments rearrangement, Proc. of the XVI International Symposium on Math. Programming (Lausanne), agosto 1997, abstract.

7. Y. Kohayakawa, Szemerédi’s regularity lemma for sparse graphs, Foundations of Computational Mathematics (Berlin, Heidelberg) (F. Cucker and M. Shub, eds.), Springer-Verlag, January 1997, pp. 216–230.

8. O. Lee and Y. Wakabayashi, Circuit covers in series-parallel mixed graphs, Proceedings of the XVI International Symposium on Math. Programming, 1997, abstract.

9. , Circuit covers in series-parallel mixed graphs, LATIN’98: Theoretical Informatics (Campinas, Brazil) (C.L. Lucchesi and A.V. Moura, eds.), Lecture Notes in Computer Science, vol. 1380, Springer-Verlag, abril 1998, pp. 226–238.

10. F.K. Miyazawa and Y. Wakabayashi, Approximation algorithms for packing problems with orthogonal rotations, Proceedings of the XVI International Symposium on Math. Programming, 1997, abstract.

11. M. Molloy and B. Reed, A pseudo-random method for list colourings, Proceedings of WAIT (Buenos Aires, Argentina), 1997.

12. , Colouring graphs whose chromatic number is almost their maximum degree, Proceedings of LATIN’98: Theoretical Informatics (Campinas, Brazil) (C.L. Lucchesi and A.V. Moura, eds.), Lecture Notes in Computer Science, vol. 1380, Springer-Verlag, 1998, pp. 216–225.

3.5. Anais de Congressos Nacionais.

1. G.F. Cintra and Y. Wakabayashi, Um algoritmo híbrido para o problema de corte unidimensional, XXX SOBRAPO, Anais da III Oficina de Problemas de Corte e Empacotamento (Curitiba), 1998, pp. 79–96.

2. C.E. Ferreira and M. Loparić, Uma aplicação do método branch-and-cut a um problema de roteamento de veículos, Anais do Concurso de Dissertações e Teses da SBC, 1997, pp. 509–516.

3. F.K. Miyazawa and Y. Wakabayashi, Three-dimensional packing problem: Approximation algorithms and performance analysis, Anais da I Oficina Nacional em Problemas de Corte e Empacotamento, 1996, Tech. Report RT-MAC-9610, IME-USP, pp. 11–16.

4. , Approximation algorithms for packing small items, XX CNMAC - Anais da II Oficina Nacional de Problemas de Cortes e Empacotamento, 1997, pp. 7–14.

5. , Parametric on-line packing, XXX SOBRAPO, Anais da III Oficina de Problemas de Corte e Empacotamento (Curitiba), 1998, pp. 109–121.

3.6. Trabalhos submetidos.

1. G. Călinescu, C.G. Fernandes, H. Karloff, and A. Zelikovski, A new approximation algorithm for finding heavy planar subgraphs, submetido, 1998.

2. C.E. Ferreira, C.C. de Souza, and Y. Wakabayashi, Rearrangement of DNA fragments: a branch-and-cut algorithm, Relatório Técnico RT-MAC-9701, 1997.

3. C.E. Ferreira, F.K. Miyazawa, and Y. Wakabayashi, Packing of squares into squares, submetido, 1998.

4. M.A.M.C. Gurgel and Y. Wakabayashi, The complete pre-order polytope: Facets and the separation problem, submetido, 1996.

5. Y. Kohayakawa and B. Kreuter, The width of random subsets of Boolean lattices, submetido, 1998.

6. Y. Kohayakawa, B. Kreuter, and D. Osthus, The length of random subsets of Boolean lattices, submetido, 1998.

7. M. Loparic and C.E. Ferreira, A branch-and-cut algorithm for a vehicle routing problem with capacity and time constraints, submetido, 1997.

8. M. Molloy and B. Reed, Colouring graphs whose chromatic number is almost their maximum degree, submetido, 1998.

9. , Further algorithmic aspects of the local lemma, submetido, 1998.

10. , A pseudo-random method for list colourings, submetido, 1998.

11. M. Molloy, B. Reed, and W. Steiger, On the mixing rate of the triangulation walk, submetido, 1998.

12. B. Reed and R. Thomas, Clique minors in graphs and their complements, submetido, 1998.

3.7. Em preparação.

1. G.F. Cintra and Y. Wakabayashi, A hybrid quasi-exact algorithm for the onedimensional cutting stock problem, 1998.

2. J.C. de Pina and J. Soares, On the integer cone of the bases of a matroid, Relatório Técnico RT-MAC-9803, 1998.

3. Y. Kohayakawa and V. Rödl, Checking pseudorandomness of graphs fast, em preparação, 1998.

4. , Turán type problems for sparse random graphs, em preparação, 1998.

5. Y. Kohayakawa, V. Rödl, and E. Szemerédi, On a Ramsey-Túran type problem for hypergraphs, em preparação, 1998.

6. O. Lee and Y. Wakabayashi, Circuit covers in mixed graphs, em preparação, 1998.

7. H. van der Holst and J.C. de Pina, Length-bounded disjoint paths in planar graphs, 1998.

4. Orientações

Enumeramos os alunos sob nossa responsabilidade no período, especificando o orientador em cada caso.

4.1. Doutorado.

1. Estela Maris Rodrigues [Y. Wakabayashi]. Título do projeto: Problemas sobre Medianas de Grafos, Partições e outras Estruturas Discretas (título provisório). Bolsa do cnpq. Ingresso no programa: março/97. Em andamento.

2. Flávio Keidi Miyazawa [Y. Wakabayashi]. Doutor. Formou-se em novembro/97. Bolsa do cnpq. Título da tese: Algoritmos de Aproximação para Problemas de Empacotamento. Atualmente membro do Instituto de Computação da UNICAMP.

3. Francisco Elói Soares de Araújo [J. Soares]. Título do projeto: Biologia Computacional. Ingresso no programa: agosto/98. Em andamento.

4. Jair Donadelli Júnior [Y. Kohayakawa]. Título do projeto: Métodos Probabilísticos e Métodos Topológicos em Combinatória Extremal. Bolsa da capes até dezembro/97 e bolsa do cnpq desde janeiro/98. Ingresso no programa: março/96. Em andamento.

5. Liliane Rose Benning Salgado [Y. Wakabayashi]. Título do projeto: Aproximabilidade de Problemas de Otimização em Grafos. Bolsa da fapesp desde agosto/98. Ingresso no programa: março/98. Em andamento.

6. Marco Aurélio Stefanes [J. Soares]. Título do projeto: Algoritmos Paralelos para Grafos e Geometria Computacional. Bolsa da fapesp desde agosto/98. Ingresso no programa: março/98. Em andamento.

7. Orlando Lee [Y. Wakabayashi]. Título do projeto: Problemas de Otimização Combinatória: Aspectos Estruturais e Algorítmicos. Bolsa da capes. Ingresso no programa: março/95. Em andamento.

4.2. Mestrado.

1. Alexandre Scalzitti [Y. Kohayakawa]. Título do projeto: Convergência em Grafos Aleatórios. Ingresso no programa: março/96. Em andamento.

2. Aritanan Borges Garcia Gruber [C.E. Ferreira]. Título do projeto: Algoritmos Dinâmicos para Problemas de Otimização Combinatória. Bolsa do cnpq. Ingresso no programa: março/97. Em andamento.

3. Armando Ramos Gouveia [Y. Kohayakawa], Mestre. Formou-se em novembro/98. Bolsa da capes. Título da dissertação: Provas Holográficas de Tamanho Quase-linear.

4. Carlos R. Pantaleon Dionisio [J.C. de Pina]. Título do projeto: Geometria Computacional de Pontos em Movimento. Bolsa do cnpq até fevereiro de 1997. Ingresso no programa: março/96. Em andamento.

5. César Alberto Bravo Pariente [Y. Kohayakawa], Mestre. Formou-se em novembro/96. Bolsa da capes. Título da dissertação: Um Método Probabilístico em Combinatória.

6. Edésio R. Sibrão [C.E. Ferreira]. Título do projeto: Escalonamento em Sistemas de Produção: um Estudo de Caso. Bolsa da capes de agosto/96 até julho/98. Ingresso no programa: agosto/96. Em andamento.

7. Estela Maris Rodrigues [M.A.M.C Gurgel], Mestre. Formou-se em fevereiro/97. Bolsa do cnpq. Título da dissertação: Fatores e Empacotamentos em Grafos.

8. Francisco Elói Soares de Araújo [J. Soares], Mestre. Formou-se em agosto/98. Bolsa da capes. Título da dissertação: Rearranjo de Genomas por Reversões.

9. Glauber Ferreira Cintra [Y. Wakabayashi], Mestre. Formou-se em julho/98. Bolsa do cnpq. Título da dissertação: Algoritmos Híbridos para Problemas de Corte Unidimensional.

10. Marco Aurélio Stefanes [J. Soares], Mestre. Formou-se em fevereiro/98. Bolsa do cnpq de março/95 a fevereiro/97. Título da dissertação: Algoritmos e Implementações Paralelas para Florestas Geradoras Mínimas.

11. Mário Leston Rey [P. Feofiloff]. Título do projeto: T -junções Mínimas. Bolsa do cnpq. Ingresso no programa: março/97. Em andamento.

12. Said Sadique Adi [C.E. Ferreira]. Título do projeto: Algoritmos Combinatórios para Seqüenciamento de DNA. Bolsa do cnpq. Ingresso no programa: março/98. Em andamento.

4.3. Iniciação científica.

1. Alexandre Cardoso Garcia Leite [J. Soares]. Título do projeto: Problemas Combinatórios de Busca. Período: de março de 1995 a fevereiro de 1997. Bolsa do cnpq de agosto de 1995 a fevereiro de 1997.

2. Cassio Polpo de Campos [C.E. Ferreira]. Título do projeto: Geometria Computacional: Algoritmos e Aplicações. Bolsa da fapesp (Processo: 97/09521-9) de fevereiro a dezembro de 1998.

3. Dan Faccio [C.E. Ferreira]. Título do projeto: Algoritmos Combinatórios para Rearranjo de Seqüências de DNA. Bolsa do PIBIC–cnpq de fevereiro de 1997 a janeiro de 1998.

4. Eduardo Garcia de Freitas [C.E. Ferreira]. Título do projeto: Geometria Computacional: Algoritmos e Aplicações. Bolsa da fapesp (Processo: 97/09522-5) de fevereiro a dezembro de 1998.

5. Luciano Micheletti Hespanhol [J. Soares]. Título do projeto: Compressão de Dados. Bolsa do PIBIC–cnpq de outubro de 1996 a fevereiro de 1997.

6. Rodrigo Nonamor Pereira Mariano de Souza [C.E. Ferreira]. Título do projeto: Algoritmos Combinatórios para Árvores Filogenéticas. Bolsa do PIBIC– cnpq desde maio de 1998.

7. Rogério Theodoro de Brito [J. Soares]. Título do projeto: Compressão de Dados. Período: desde março de 1995. Bolsa do cnpq de agosto de 1995 a julho de 1997.

8. Sérgio Gabriel Tavares [C.E. Ferreira]. Título do projeto: Heurísticas para o Problema de Decomposição de Matrizes. Bolsa do PIBIC–cnpq de fevereiro de 1997 a maio de 1998.

9. Thiago Teixeira Santos [C.E. Ferreira]. Título do projeto: Algoritmos Combinatórios para Rearranjo de Seqüências de DNA. Bolsa do PIBIC–cnpq desde fevereiro de 1998.

5. Viagens

5.1. Eventos internacionais.

1. DIMACS Workshop on Probabilistic Methods in Discrete Mathematics, DI-MACS (EUA), 14–18 de outubro de 1996. Y. Kohayakawa participou, com despesas pagas pelo encontro.

2. InFORMS’96 – Institute for Operations Research and the Management Sciences Meeting, Atlanta-GA (EUA), 3–6 de novembro/96.

– C.G. Fernandes apresentou o trabalho A Better Approximation Algori-

thm for Finding Planar Subgraphs.

3. II ALIO/EURO Workshop on Practical Combinatorial Optimization, Valpa-

raiso (Chile), 11–15 de novembro/96.

– C.E. Ferreira apresentou o trabalho Rearrangement of DNA fragments:

a branch-and-cut algorithm.

4. SODA’97 – 8^{th} Annual ACM-SIAM Symposium on Discrete Algorithms, New

Orleans-LA (EUA), 5–7 de janeiro/97.

– C.G. Fernandes apresentou o trabalho A Better Approximation Ratio for

the Minimum k-Edge-Connected Spanning Subgraph Problem.

5. FoCM’97 – Foundations of Computational Mathematics, IMPA, Rio de Ja-

neiro, 5–12 de janeiro/97.

– Y. Kohayakawa (Proc. 97/01873–3 - fapesp) participou da oficina Relations to Computer Science. Apresentou o trabalho Szemerédi’s Regularity Lemma for Sparse Graphs (semi-plenária, 50 minutos).

– Y. Wakabayashi (Proc. 96/12820–5 - fapesp) participou do Workshop on Optimization. Apresentou o trabalho Approximation Algorithms for Three-dimensional Packing Problems.

6. STOC’97 – 29^{th} Annual ACM Symposium on Theory of Computing (STOC),

El Paso-TX (EUA), 4–6 de maio/97.

– Participante: C.G. Fernandes.

7. WAIT ’97, First Argentine Workshop on Theoretical Informatics, Buenos

Aires, 11 de agosto de 1997.

– Y. Kohayakawa proferiu uma palestra convidada, intitulada Pseudoran-

domness in Graph Theory. Participação financiada pelos organizadores.

8. ISMP’97 – XVI International Symposium on Mathematical Programming,

Lausanne, Suíça, 24–29 de agosto/97.

– C.E. Ferreira apresentou o trabalho A Polyhedral Approach for DNA Fragments Arrangement. Financiado pelo ProBRAL 001/94.

– F.K. Miyazawa apresentou o trabalho Approximation Algorithms for Packing Problems with Orthogonal Rotations. Financiado pelo Pro-BRAL 001/94.

– Y. Wakabayashi (Proc. 97/6472-7 - fapesp) apresentou o trabalho Circuit

Covers in Mixed Graphs.

9. Random Graphs and Combinatorial Structures, Oberwolfach, Alemanha,

28 de setembro a 4 de outubro de 1997.

– Y. Kohayakawa apresentou o trabalho Checking Pseudorandomness of

Graphs Fast. Despesas locais cobertas pelos organizadores.

10. LATIN ’98 – Third Latin American Symposium on Theoretical INformatics, UNICAMP, 20–24 de abril/98. Simpósio internacional dedicado à teoria da computação. Participaram vários membros do grupo. Y. Kohayakawa fez parte do Comitê de Programa.

– O. Lee apresentou o trabalho Circuit Covers in Series-parallel Mixed Gra-

phs.

11. From Erdős to Algorithms, DIMACS, 8–10 de junho de 1998. Evento organi-

zado conjuntamente pelo DIMACS e DIMATIA (Praga).

– Y. Kohayakawa apresentou o trabalho Random Sperner-type Results. Participação financiada pelos organizadores.

12. IPCO’98 – 6^{th} Conference on Integer Programming and Combinatorial Opti-

mization, Houston-TX (EUA), 22–24 de junho/98.

– C.G. Fernandes apresentou o trabalho Multicuts in Unweighted Graphs

with Bounded Degree and Bounded Tree-Width. Financiada pelo cnpq.

13. Probabilistic Combinatorics, Mathematical Institute, Budapest, 25 de junho a 8 de julho de 1998. Y. Kohayakawa participou, com despesas locais pagas pelo encontro e passagem paga pelo projeto Complexidade de Estruturas Discretas (pronex).

14. 5th Czech-Slovak International Symposium on Combinatorics, Graph Theory,

Algorithms and Applications, Praga, 6 a 11 de julho de 1998.

– Y. Kohayakawa proferiu a palestra On Essentially Infinite Colourings of

Graphs, palestra convidada (50 minutos).

15. 2a. Escola Brasileira de Probabilidade, Barra de Sahi, SP, 2 a 7 de agosto de

1998.

– Y. Kohayakawa proferiu a palestra Random and Pseudorandom Structures in Combinatorics and Theoretical Computer Science, palestra convidada (40 minutos). Participação financiada pelos organizadores.

16. ICM’98 – International Congress of Mathematicians, Berlin, RFA, 18–27 de

agosto/98.

– Participantes: C.G. Fernandes, Y. Kohayakawa e Y. Wakabayashi. Todos

receberam auxílio dos organizadores.

17. IX CLAIO – Congresso Latino-iberoamericano de Investigación Operativa,

Buenos Aires, Argentina, 2–4 de setembro/98.

– C.G. Fernandes apresentou o trabalho Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width. Financiado pelo pronex.

– Y. Wakabayashi apresentou o trabalho The Complexity of Computing Medians of Relations. Fez parte do Comitê de Programa. Financiado pelo pronex.

18. The DIMACS–IAS Workshop on Randomized and Derandomized Algorithms for Discrete Structures, Institute for Advanced Study, Princeton, NJ, EUA, 2 a 4 de novembro de 1998.

– Y. Kohayakawa proferiu a palestra Embeddings of Small Graphs in Sparse Regular Graphs. Custos locais cobertos pelo evento.

5.2. Eventos no país.

1. III Oficina do Projeto ProComb, 29–30 de abril/97, IME-USP, SP. – O. Lee apresentou o trabalho Cobertura de Circuitos em Grafos Mistos.

2. Oficina do PCE, 16–17 de dezembro/97, IME-USP, SP.

3. XXI Colóquio Brasileiro de Matemática, 21–25 de julho/97. Rio de Janeiro,

RJ. Y. Kohayakawa organizou a Sessão de Combinatória.

– C.E. Ferreira apresentou o trabalho Decomposing Matrices into Blocks – C.G. Fernandes apresentou o trabalho Multicortes em Árvores de Grau

Limitado

4. XX Congresso de Matemática Aplicada e Computacional – II Oficina Nacional

de Problemas de Cortes e Empacotamentos, setembro/97, Gramado, RS.

– F.K. Miyazawa apresentou o trabalho Approximation Algorithms for Packing Small Items.

5. Workshop on Probabilistic Methods in Combinatorics and Theoretical Computer Science, 27 de abril a 1 de maio de 1998, Ubatuba, SP. Participaram C.G. Fernandes, Y. Kohayakawa, e J. Donadelli Jr. Apresentações informais de problemas foram feitas por C.G. Fernandes e Y. Kohayakawa. Veja mais detalhes na Seção 7.2.

6. I Encontro Regional de Matemática Aplicada e Computacional, 10–12 de

junho/98, São José do Rio Preto, SP.

– C.E. Ferreira apresentou o minicurso Planos de Corte Faciais e a Reso-

lução de problemas de Otimização Combinatória.

7. XII Escola de Computação, 20–24 de julho/98, Rio de Janeiro, RJ.

– Participantes: C.E. Ferreira, C.G. Fernandes, J.C. de Pina, M.A.M.C.

Gurgel, Y. Kohayakawa e Y. Wakabayashi.

8. Congresso da Sociedade Brasileira de Computação, 3–5 de agosto/98, Belo

Horizonte, MG.

– Participante: C.E. Ferreira.

9. WPOC — Workshop em Paralelismo e Otimização Combinatória, 28 de se-

tembro/98, Búzios.

– M.A. Stefanes apresentou o trabalho Algoritmo Assíncrono para Floresta Geradora Mínima.

5.3. Estágios no exterior e visitas curtas.

1. Carlos E. Ferreira, ZIB-Berlin, 30 de agosto/97 a 5 de setembro/97. Financiado pelo projeto ProBRAL 001/94 (capes-daad).

2. Cristina G. Fernandes.

• Georgia Tech, 24–27 de junho/98. Financiado pelo cnpq.

• Georgia Tech, janeiro e fevereiro de 1999 [planejado], financiamento da

fapesp.

3. Yoshiharu Kohayakawa.

• AT&T Labs Research, outubro de 1996 (3 semanas). Financiado pela AT&T. Convite de R.L. Graham.

• University of Memphis, 4 meses, a partir de 15 de janeiro de 1997. Financiado pela U. of Memphis. Convite de B. Bollobás.

• Humboldt-Universität zu Berlin, 7 semanas, a partir de 4 de janeiro de 1997. Financiado pelo projeto ProBRAL 026/95 (capes-daad).

• DIMACS e Microsoft Research, janeiro e fevereiro 1999 [planejado], fi-

nanciado por DIMACS, Rutgers e Microsoft.

4. Yoshiko Wakabayashi, ZIB-Berlin, outubro a dezembro/96. Financiado pelo projeto ProBRAL 001/94 (capes-daad).

6. Visitantes

Durante o período, a nossa equipe recebeu a visita de vários pesquisadores estrangeiros. Mesmo devido à longa duração, a visita do prof. Bruce Reed merece especial destaque.

1. Dr. Ralf Borndörfer, ZIB, Berlim (dezembro 1996). [capes-daad - C.E. Ferreira]

2. Professor Bruce Reed, CNRS, Paris (maio/novembro 1997). [Proc. 96/12111– 4 - fapesp - Y. Kohayakawa]

3. Professor Vojtěch Rödl, Emory University, Atlanta (junho 1997). [usp - Y. Kohayakawa] 4. Professor Endre Szemerédi, Rutgers University, NJ (junho 1997). [usp -

Y. Kohayakawa]

5. Dr. Bernd Kreuter, Humboldt-Universität, Berlin (agosto/setembro 1997). [capes-daad - Y. Kohayakawa]

6. Professor Laurence Wolsey, CORE Louvain (3–5 de agosto de 1997). [C.E. Ferreira]

7. Professor Gerhard Wäscher, Martin-Luther-Universität, Halle-Wittenberg (17–19 de setembro 1997) [cnpq - Projeto PCE - Y. Wakabayashi]

8. Professor Hanno Lefmann, Universität Dortmund (outubro 1997). [usp - Y. Kohayakawa]

9. Professor András Sebö, Laboratoire Leibniz-IMAG, Grenoble (1–2 de dezembro 1997). [ime-usp]

10. Professor Robin Thomas, Georgia Tech, Atlanta (abril 1998). [Proc. 97/14469-6 - fapesp - C.G. Fernandes]

11. Professor Pavel Pudlák, Praga (abril/maio 1998). [usp e pronex - Y. Kohayakawa]

12. Professor Zoltán Füredi, Urbana-Champaign e Budapest (abril/maio 1998). [usp - Y. Kohayakawa]

13. Os professores N. Alon, L. Devroye, P.E. Haxell, J.H. Kim, e P. Tetali participaram do Workshop on Probabilistic Methods in Combinatorics and Theoretical Computer Science, Ubatuba, SP, 27 de abril a 1 de maio de 1998. O evento cobriu as despesas locais dos participantes (veja Seção 7.2).

14. Professor Daniel H. Younger, University of Waterloo (6 de julho de 1998). [P. Feofiloff]

15. Professor Kristina Vuskovic, University of Kentucky (13–14 de agosto de 1998). [ime-usp- C.G. Fernandes]

16. Professor John Beasley, Imperial College (9-10 de setembro 1998). [cnpq - projeto PCE - C.E. Ferreira]

7. Eventos

7.1. Seminários. Estes seminários vem ocorrendo regularmente desde 1995, com a participação de membros do nosso grupo de pesquisa e pesquisadores visitantes.

7.1.1. Segundo semestre de 1997.

1. The Complexity of Some Problems on Very Sparse Graphs – Bernd Kreuter, HU Berlin, 22 de agosto.

2. Recent Issues on Cutting and Packing – Gerhard Wäscher, Martin-Luther-Universität, Halle-Wittenberg, 19 de setembro.

3. Multicortes em Árvores de Grau Limitado – Cristina G. Fernandes, IME-USP, 10 de outubro.

4. Finding k-Edge-Connected Spanning Subgraphs: a Better Analysis – Cristina G. Fernandes, IME-USP, 17 de outubro.

5. Independent Sets in Graphs and Hypergraphs and Their Applications – Hanno Lefmann, Universität Dortmund, RFA, 28 de outubro.

6. Um Algoritmo Melhor para Encontrar Subgrafos Planares – Cristina G. Fernandes, IME-USP, 31 de outubro.

7. Computação Quântica – Cristina G. Fernandes, IME-USP, 7 de novembro.

8. Um Algoritmo de Aproximação para Subgrafos Planares Pesados – Cristina G. Fernandes, IME-USP, 21 de novembro.

7.1.2. Primeiro semestre de 1998.

1. A Conjectura de Woodall – Orlando Lee, IME-USP, 6 de março.

2. Multicortes em Grafos de Grau Limitado – Cristina G. Fernandes, IME-USP, 13 de março.

3. Problemas em aberto – apresentação de alguns problemas em aberto feita pelos participantes do seminário, 20 de março.

4. O Teorema de Erdős e Rado e Colorações Essencialmente Infinitas – Yoshiharu Kohayakawa, IME-USP, 27 de março.

5. Hypergraphs in Codes, Designs and in Combinatorial Geometry – Zoltán Füredi, Urbana-Champaign (Illinois) e Budapest, 6 de maio.

6. Conjectura de Woodall: o Caso dos Grafos com Conexão Fonte-Sorvedouro – Paulo Feofiloff, IME-USP: 15 de maio e 22 de maio.

7. Potentials in Undirected Graphs and Planar Multiflows – Mario Leston, IME-USP, 5 de junho.

8. The 3-Flow Conjecture for Graphs – D.H. Younger, University of Waterloo, 6 de julho.

7.1.3. Segundo semestre de 1998.

1. Progressos Recentes sobre Decomposição do Hipercubo em Ciclos Hamiltonianos – Kunio Okuda, IME-USP, 7 de agosto.

2. Progressos Recentes sobre Decomposição do Hipercubo em Ciclos Hamiltonianos - Parte 2 – Carlos Eduardo Rodrigues Alves, IME-USP, 7 de agosto.

3. Decomposition Theorem and Recognition Algorithm for Even-Hole-Free Graphs – Kristina Vuskovic, University of Kentucky (EUA), 14 de agosto.

4. Scheduling Aircraft Landings – John Beasley, Imperial College (Londres), 9 de setembro.

5. Examples from Infinitary Combinatorics – Piotr Koszmider, IME-USP, 18 e 25 de setembro.

7.2. Oficina.

• Workshop on Probabilistic Methods in Combinatorics and Theoretical Com-

puter Science, Ubatuba/SP, 27 de abril a 1 de maio de 1998.

Durante esta oficina extremamente informal, vários dos participantes apresentaram diversos problemas em aberto ou trabalho de pesquisa que vinham realizando relacionados com estruturas aleatórias ou combinatórias em geral. A oficina foi uma ótima ocasião para colaboração.

– Participantes: N. Alon, L. Devroye, J. Donadelli Jr., C.G. Fernandes, Z. Füredi, P.E. Haxell, J.H. Kim, Y. Kohayakawa, L.R. Moura, D. Panario, P. Pudlák, B. Reed, P. Tetali, A. Viola.

Destacamos novamente que 3 destes participantes são renomados pesquisadores que proferiram palestras em Congressos Internacionais de Matemáticos (Alon, Füredi e Pudlák) e um deles (Kim) foi o ganhador da Medalha Fulkerson em 1997.

O idealizador deste encontro foi o professor visitante Bruce Reed, a quem devemos a realização de um encontro de tal qualidade. A organização local ficou a cargo de C.G. Fernandes e Y. Kohayakawa.

7.3. Minicursos e eventos especiais.

1. Dia da Combinatória, IME-USP, 1 de dezembro de 1997.

Neste dia, realizamos uma série de palestras proferidas por professores visitantes.

– On the Jump Number of Ordered Sets – Klaus Reuter, Universidade de Hamburgo, Alemanha.

– Alguns Resultados e Conjecturas em Contagem de Recobrimentos por Dominós – Nicolau Corção Saldanha, Pontifícia Universidade Católica do Rio de Janeiro.

– Flows, View-obstructions and the Lonely Runner – András Sebö, Labo-

ratoire Leibniz-IMAG, Grenoble.

2. Lectures on Tree-decompositions, Permanents, Pfaffian Orientations and

Even Directed Circuits.

O minicurso, dado pelo Prof. Robin Thomas do Georgia Institute of Technology, consistiu de uma série de 6 palestras sobre largura arbórea e problemas correlatos. As palestras ocorreram nos dias 1, 3, 6, 7, 8 e 13 de abril de 1998.

3. Uso de Bases de Gröbner em Combinatória.

O Prof. Arnaldo Mandel, do nosso grupo de pesquisa, preparou e apresentou um minicurso sobre bases de Gröbner. As aulas ocorreram nos dias 9, 16, 23, 30 de outubro e 6 de novembro de 1998, como parte das atividades semanais dos seminários do grupo.

4. Dia de Otimização e Combinatória, IME-USP, 19 de novembro de 1998.

Neste dia, foram realizadas uma série de palestras proferidas por professores visitantes.

– Localização de ERB e Alocação de Canais em Sistemas Móveis Celulares – Geraldo Robson Mateus, UFMG.

– Cem Horas de Solidão – Manoel Lemos, UFPE.

– Packing Identical Boxes into a Container – Sóstenes Lins, UFPE.

8. Auxílios Vigentes

8.1. Bolsas. Mencionamos as bolsas de pesquisa, doutorado, mestrado e iniciação científica obtidas pelos participantes desta equipe.

8.1.1. Bolsas de pesquisa.

– Arnaldo Mandel - Bolsa de Auxílio a Pesquisa do cnpq, nível 1C.

– Carlos Eduardo Ferreira - Bolsa de Auxílio a Pesquisa do cnpq, nível 2C.

– Cristina Gomes Fernandes - Bolsa de Auxílio a Pesquisa do cnpq, nível 2C.

– José Augusto Ramos Soares - Bolsa de Auxílio a Pesquisa do cnpq, nível 2C.

– Yoshiharu Kohayakawa - Bolsa de Auxílio a Pesquisa do cnpq, nível 1C.

– Yoshiko Wakabayashi - Bolsa de Auxílio a Pesquisa do cnpq, nível 1C.

8.1.2. Bolsas de doutorado.

– Estela Maris Rodrigues [Y. Wakabayashi], bolsa do cnpq (Proc. 574226/97-4) desde março/97.

– Jair Donadelli Júnior [Y. Kohayakawa], bolsa do cnpq desde janeiro/98.

– Liliane R.B. Salgado [Y. Wakabayashi], bolsa da fapesp (Proc. 98/02407-9) desde agosto/98.

– Marco Aurélio Stefanes [J. Soares], bolsa da fapesp (Proc. 98/06327-0) desde agosto/98.

– Orlando Lee [Y. Wakabayashi], bolsa da capes desde março/95.

8.1.3. Bolsas de mestrado.

– Aritanan Borges Garcia Gruber [C.E. Ferreira], bolsa cnpq desde março/97.

– Said Sadique Adi [C.E. Ferreira], bolsa cnpq desde março/98.

8.1.4. Bolsas de iniciação científica.

– Cassio Polpo de Campos [C.E. Ferreira], bolsa fapesp (Proc. 97/09522-5) de fevereiro a dezembro/98.

– Eduardo Garcia de Freitas [C.E. Ferreira], bolsa fapesp (Proc. 97/09522-5) de fevereiro a dezembro/98.

– Rodrigo Nonamor Pereira Mariano de Souza [C.E. Ferreira], bolsa PIBIC-cnpq desde maio/98.

– Thiago Teixeira Santos [C.E. Ferreira], bolsa PIBIC-cnpq desde fevereiro/98.

8.2. Projetos integrados. Os membros da equipe deste projeto da fapesp participa(ra)m dos seguintes projetos:

• Projeto de intercâmbio internacional capes-daad: Problemas de Empacotamento e Partição de Grafos e Hipergrafos – ProBRAL 001/94. Este é um projeto de intercâmbio entre o Brasil e a Alemanha. Instituições envolvidas: ZIB–Berlin (coordenador: M. Grötschel), e IME–USP (coordenadora: Y. Wakabayashi). Participantes brasileiros: C.E. Ferreira e Y. Wakabayashi. Vigência: outubro de 1994 a fevereiro de 1998. Página na Teia:

  http://www.ime.usp.br/~cef/probral/

• Projeto de intercâmbio internacional capes-daad: Combinatória Extremal e Métodos Probabilísticos – ProBRAL 026/95. Este é um projeto de intercâmbio entre o Brasil e a Alemanha. Instituições envolvidas: Humboldt-Universität zu Berlin (coordenador: H.J. Prömel), e IME–USP (coordenador: Y. Kohayakawa). Participantes brasileiros: Y. Kohayakawa e J.A.R. Soares. Vigência: setembro de 1995 a agosto de 1998. Página na Teia:

  http://www.ime.usp.br/~yoshi/index_DAAD.html

Observação. Um novo projeto dentro do programa ProBRAL, envolvendo basicamente os mesmos pesquisadores, terá início em janeiro de 1999.

• Projeto Temático Multi-institucional do cnpq: Problemas de Cortes & Empacotamentos e Correlatos – ProTeM-CC-III. Período: outubro/96 a outubro/98. Coordenador: H. Yanasse. Participantes da equipe: C.E. Ferreira, Y. Wakabayashi. Página na Teia:

 http://www.ime.usp.br/~cef/pce/

• Projeto dentro do programa de cooperação capes-cofecub: Algoritmos para Análise de Genomas. Coordenadora: Y. Wakabayashi. Início em janeiro de 1999.

8.3. Núcleo de Excelência. A equipe deste projeto temático faz parte de um núcleo de excelência do programa pronex do mct–finep:

Complexidade de Estruturas Discretas (projeto no. 107/97).

Este núcleo tem apoio no período de janeiro de 1998 a dezembro de 2001. Coordenador: Y. Kohayakawa. Página na Teia:

http://www.ime.usp.br/~yoshi/pronex/

9. Prêmios e Honrarias

9.1. Teses e dissertações premiadas.

– Marko Loparic [C.E. Ferreira] – Dissertação de mestrado premiada em 2^{o.} lugar no CTD’97 (Concurso de Teses e Dissertações) promovido pela SBC (Sociedade Brasileira de Computação). Título da dissertação: Uma aplicação do Método de Branch and Cut a um Problema de Roteamento de Veículos – ime-usp, janeiro/96.

– Flávio Keidi Miyazawa [Y. Wakabayashi] – Tese de doutorado premiada em 1^{o.} lugar no CTD’98 (Concurso de Teses e Dissertações) promovido pela SBC (Sociedade Brasileira de Computação). Título da tese: Algoritmos de Aproximação para Problemas de Empacotamentos – ime-usp, novembro/97.

9.2. Academia Brasileira de Ciências. Y. Kohayakawa foi eleito Membro Associado da Academia Brasileira de Ciências em 16 de novembro de 1998.

10. Outras Atividades

10.1. Miscelâneas.

– Y. Kohayakawa organizou a Sessão de Combinatória no XXI Colóquio Brasileiro de Matemática, 21–25 de julho/97, Rio de Janeiro.

– Y. Kohayakawa participou do Comitê de Programa da XI Escola de Computação, 21–24 de julho/98, Rio de Janeiro.

– Y. Kohayakawa participou do Comitê de Programa do LATIN’98 – Third Latin American Symposium on Theoretical Informatics, 20–24 de abril/98, Campinas.

– Y. Kohayakawa é membro da Coordenação de Área de Matemática e Ciência da Computação da fapesp a partir de dezembro de 1998.

– Y. Kohayakawa será membro do Comitê Assessor de Ciência da Computação do cnpq no biênio 1999/2000.

– Y. Wakabayashi fez parte do Comitê de Programa do IX CLAIO – Congresso Latino-iberoamericano de Investigación Operativa, 2–4 de setembro/98, Buenos Aires, Argentina.

– Y. Wakabayashi foi membro do Comitê Assessor de Ciência da Computação do cnpq no biênio 1997/1998.

11. Conclusão e Análise Crítica

Tecemos aqui uma breve apreciação do desempenho de nossa equipe nestes dois últimos anos.

Inicialmente, observamos que houve um certo descompasso entre as expectativas do coordenador e a produção científica da equipe no primeiro ano deste projeto. Entretanto, visto em uma janela de dois anos, a equipe demonstrou, a nosso ver, como objetivamente relatado neste documento, um desempenho de altíssima qualidade. Acreditamos que, sobretudo, a qualidade dos periódicos em que nossos trabalhos foram publicados (veja Seções 1.2 e 3) atesta que podemos nos considerar uma equipe de nível internacional na área de combinatória. A nossa inserção no comunidade internacional também pode ser vista pela nossa forte colaboração com pesquisadores e centros internacionais de excelência.

Desempenhamos também um papel importante na formação de alunos (veja Seção 4), em todos os níveis. Um de nossos ex-alunos é membro hoje de um dos melhores centros para a ciência da computação no país.

Acreditamos que, com o apoio fundamental da fapesp e de nossos outros projetos de pesquisa, poderemos continuar contribuindo de forma decisiva para o desenvolvimento desta área de pesquisa no país e também poderemos consolidar a nossa posição na comunidade internacional.