| Processo: | 08/50338-0 |
| Linha de fomento: | Bolsas no Exterior - Pesquisa |
| Vigência (Início): | 01 de junho de 2008 |
| Vigência (Término): | 31 de agosto de 2008 |
| Área do conhecimento: | Ciências Exatas e da Terra - Matemática - Geometria e Topologia |
| Pesquisador responsável: | Maya Jakobine Stein |
| Beneficiário: | Maya Jakobine Stein |
| Anfitrião: | Bernhard Kron |
| Instituição-sede: | Pessoa Física |
| Local de pesquisa: | University of Vienna, Áustria |
Resumo Este é um resumo do projeto de pesquisa Problemas finitos e infinitos da teoria dos grafos e hipergrafos supervisado por Yoshiharu Kohayakawa, e desenvolvido por Maya Stein, como bolsista de pós-doutoramento da FAPESP (Proc. FAPESP 2005/54051-9). A bolsa foi concedida em 2005, e prolongada duas vezes. Descrevemos aqui brevemente os objetivos científicos deste projeto. O projeto de pesquisa contempla três vertentes: (i) Problemas para grafos infinitos. Vários resultados para grafos finitos podem ser estendidos para grafos infinitos se levarmos em conta os assim chamados términos (ends). Um exemplo é o grau, que tanto pode ser definido para um vértice como para um término. Com este conceito, o grau minimal de um grafo pode ser medido de uma maneira mais adequada. Nesta área, dois trabalhos já foram elaborados durante a duração da bolsa de pós-doutoramento, um deles em colaboração com Heninng Bruhn. (ii) O método da regularidade para grafos e hipergrafos. Grafos esparsos e hipergrafos Este método decompõe um dado objeto (por exemplo, um grafo) em um número limitado de objetos quase-aleatórios (por exemplo, grafos bipartidos quase-aleatórios). Esta decomposição é então usada para encontrar certas subestruturas no objeto original. A pergunta principal aqui é como estender este método para outros objetos. O objetivo final dessa linha de pesquisa seria provar um assim chamado lema da remoção esparso ótimo, que teria conseqüências de interesse como, por exemplo, versões esparsas (ou relativas, na linguagem de Terence Tao) do teorema de Szemerédi sobre progressões aritméticas. A conjectura de Loebl, Komlós, e Sós. Esta conhecida conjectura da área da combinatória extremal trata de achar subgrafos específicos num grafo, supondo uma quota inferior no grau mediano do grafo. Uma versão aproximada desta conjectura foi provada pela bolsista junto com a sua colaboradora D. Piguet. Alguns casos especiais, como o das árvores de diâmetro pequeno, foram estudadas pelas mesmas autoras. O caso aberto mais interessante é o caso esparso da própria versão aproximada, o qual as colaboradoras estão investigando no momento. (iii) Problemas Ramsey e anti-Ramsey. Alguns problemas envolvendo grafos munidos com uma coloração nas arestas são apresentados no projeto. Todos estes problemas encaixam-se na teoria de Ramsey (alguns sendo de natureza anti-Ramsey). Provavelmente, o método da regularidade, métodos probabilísticos variados, e métodos combinatórios elementares serão investigados para se atacar estes problemas. Há problemas de natureza numérica como de natureza estrutural. (AU) | |