Aplicacoes de quase-aleatoriedade em combinatoria.

• Processo: 04/15397-4
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de maio de 2005
• Data de Término da vigência: 30 de junho de 2006
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Yoshiharu Kohayakawa
• Beneficiário: Jozef Skokan
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas, AP.PRNX.TEM
• Assunto(s): Estabilidade
• Palavra(s)-Chave do Pesquisador: Estabilidade | Hipergrafos | Metodo De Regularidade | Numeros De Ramsey | Quase-Aleatoriedade

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)

Publicações científicas

(4)

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

HAXELL‚ P.; LUCZAK‚ T.; PENG‚ Y.; RÖDL‚ V.; RUCINSKI‚ A.; SKOKAN‚ J.. The Ramsey number for 3-uniform tight hypergraph cycles. COMBINATORICS PROBABILITY & COMPUTING, v. 18, n. 1-2, p. 165-203, 2009. (04/15397-4, 03/09925-5)

KIM‚ S.J.; NAKPRASIT‚ K.; PELSMAJER‚ M.J.; SKOKAN‚ J.. Transversal numbers of translates of a convex body. DISCRETE MATHEMATICS, v. 306, n. 18, p. 2166-2173, 2006. (03/09925-5, 04/15397-4)

MARCINISZYN‚ M.; SKOKAN‚ J.; SPÖHEL‚ R.; STEGER‚ A.. Asymmetric Ramsey properties of random graphs involving cliques. RANDOM STRUCTURES & ALGORITHMS, v. 34, n. 4, p. 419-453, 2009. (03/09925-5, 04/15397-4)

BENEVIDES, FABRICIO SIQUEIRA; SKOKAN, JOZEF. The 3-colored Ramsey number of even cycles. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 99, n. 4, p. 690-708, JUL 2009. (05/52494-0, 04/15397-4, 03/09925-5)