Extended Workshop on Combinatorics, com a série de palestras Combinatorics, Random Structures, and Algorithms

Carlos Gustavo Moreira  Yoshiharu Kohayakawa

1 O evento

Teve lugar em São Paulo, Ubatuba, e Rio de Janeiro o

Extended Workshop on Combinatorics, 4 a 14 de março de 2002.

Um evento de destaque dentro deste workshop foi uma série de palestras intitulada

Combinatorics, Random Structures, and Algorithms, IMPA, 12 e 13 de março de 2002.

2 Objetivos

Os objetivos principais do encontro foram continuar a colaboração já existente entre vários dos participantes e encorajar novas colaborações e projetos conjuntos.

Devido à extensão, número de participantes, e informalidade do encontro, estes objetivos foram alcançados. Em particular, o objetivo de promover novos projetos conjuntos está sendo alcançado na forma de uma colaboração entre os grupos de Luminy, Atlanta, São Paulo, e IMPA (estamos no momento escrevendo um trabalho conjunto).

3 Tópicos principais

O nosso workshop teve como tópicos de interesse principais os métodos probabilísticos em combinatória e em teoria da computação, estruturas discretas aleatórias e pseudo-aleatórias, problemas assintóticos para grafos e hipergrafos incluindo aspectos da teoria de Ramsey e problemas combinatórios extremais, e o lema de regularidade de Szemerédi para grafos e hipergrafos.

A área de algoritmos esteve presente através de um subgrupo de participantes trabalhando em algoritmos de aproximação.

4 Comissão organizadora e apoio financeiro

A comissão organizadora e o comitê de programa do Extended Workshop foram constituídos de Carlos Gustavo Moreira e Yoshiharu Kohayakawa. Contamos com Vojtěch Rödl para a elaboração da lista de convidados.

Para a sua realização o Extended Workshop on Combinatorics contou com o apoio financeiro do Instituto do Milênio (IM–AGIMB) e do projeto Complexidade de Estruturas Discretas (PRONEX). Alguns pesquisadores finaciaram sua participação por completo pelo NSF, dentro de um projeto de colaboração CNPq/NSF.

Todos os participantes estrangeiros financiaram suas próprias passagens.

5 Importância do evento

Este workshop reuniu pesquisadores internacionais de renome na área de combinatória. Vários deles têm colaboração com alguns pesquisadores do país, e com este workshop esta colaboração está se ampliando para englobar mais membros da comunidade nacional.

Há em Luminy um grupo de pesquisadores que trabalham em seqüências pseudo-aleatórias. Com a participação de um membro desta equipe (Mauduit), está nascendo uma colaboração frutífera entre uma parte da comunidade de combinatória que trabalha em estruturas pseudo-aleatórias com a equipe de Luminy.

Participaram do Extended Workshop on Combinatorics 22 pesquisadores,^{1} dos quais 8 estrangeiros e 14 brasileiros. A lista dos participantes encontra-se a seguir:

1. Andrew Thomason, Univ. of Cambridge, Inglaterra

2. Arnaldo Mandel, USP

3. Brendan Nagle, Georgia Tech., EUA

4. Carlos Gustavo Tamm de Araujo Moreira, IMPA 5. Carlos Tomei, PUC–Rio

1Alguns pesquisadores participaram de apenas parte do Extended Workshop.

6. Christian Mauduit, Luminy, França

7. Cristina Gomes Fernandes, USP

8. Dwight Duffus, Emory University, EUA

9. Eduardo S. Laber, PUC–Rio

10. Flávio Keidi Miyazawa, UNICAMP

11. Hanno Lefmann, T.U. Chemnitz, Alemanha

12. Jair Donadelli, USP

13. Jayme Luiz Szwarcfiter, UFRJ

14. José Coelho de Pina, USP

15. Jozef Skokan, Univ. of Illinois at Urbana-Champaign

16. Nicolau C. Saldanha, PUC–Rio

17. Pavel Pudlák, Academia Tcheca de Ciências

18. Renato Carmo, UFPR

19. Thomas Lewiner, PUC–Rio

20. Vojtěch Rödl, Emory University, EUA

21. Yoshiharu Kohayakawa, USP

22. Yoshiko Wakabayashi, USP

Finalmente, destacamos o nível dos participantes do nosso evento, dentre os quais tivemos dois palestrantes de Congressos Internacionais de Matemáticos (Rödl e Pudlák).

6 Combinatorics, Random Structures, and Algo-

rithms

Como mencionado, um evento de destaque dentro deste workshop foi uma série de palestras intitulada Combinatorics, Random Structures, and Algorithms, que teve lugar no IMPA, nos dias 12 e 13 de março de 2002.

6.1 Programa científico

No total ocorreram 10 palestras de 45 minutos, dadas por especialistas de reconhecida liderança nas áreas mencionadas acima. As seguintes palestras foram proferidas na série Combinatorics, Random Structures, and Algorithms:

1. Ramsey type theorems for integers, V. Rödl (Emory Univ., EUA)

2. A generalization of the Helly property, J. Szwarcfiter (UFRJ)

3. Hypergraph regularity, algorithms and applications, B. Nagle (Georgia Tech., EUA)

4. Maximal antichains and fibres in finite ordered sets, D. Duffus (Emory Univ., EUA)

5. Results on counting of domino tilings, N. Saldanha (PUC/RJ)

6. Sparse parity check matrices, H. Lefmann (T.U. Chemnitz, Alemanha)

7. Extremal theory for graph minors, A. Thomason (Cambridge, UK)

8. Counting small cliques in uniform hypergraphs, J. Skokan (Univ. Illinois at Urbana-Champaign, EUA)

9. An application of Hindman’s theorem to a problem on computational complexity, P. Pudlák (Academia Tcheca de Ciências, República Tcheca)

10. Measures of pseudorandomness for finite sequences, C. Mauduit (Luminy, França)