Aplicacoes de quase-aleatoriedade em combinatoria.

Resumo

Um objeto quase-aleatório é um objeto que compartilha suas propriedades com muitos outros objetos do mesmo gênero. Neste projeto, planejamos investigar certos tipos de objetos quase-aleatórios, suas propriedades, e como utilizá-los para atacar problemas da área de matemática discreta. O projeto é apresentado em partes, como segue: (a) Quase-aleatoriedade. Aqui descrevemos algumas classes conhecidas de objetos quase-aleatórios e suas propriedades. Nosso objetivo nesta linha de pesquisa é identificar e investigar outras classes de objetos quase-aleatórios. (b) Método da regularidade e aplicações. 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 se encontrar certas subestruturas no objeto original. A pergunta principal aqui é como estender este método para outros objetos (em nosso caso, para hipergrafos). (c) Números de Ramsey. Em muito casos, certos parâmetros numéricos de grafos e hipergrafos, como por exemplo números de Ramsey, são conhecidos assintoticamente. Planejamos investigar algumas situações em que um certo fenômeno de 'estabilidade" pode tornar a determinação exata dos parâmetros correspondentes em um problema acessível. (AU)