Dois resultados em combinatória contemporânea

• Ano de defesa: 2013
• Autor(a) principal: Mota, Guilherme Oliveira
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: embedding; hipergrafos; hypergraphs; imersão; Pseudoaleatoriedade; Pseudorandomness; Ramsey; regularidade.; regularity
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-31102013-110457/

Dois problemas combinatórios são estudados: (i) determinar a quantidade de cópias de um hipergrafo fixo em um hipergrafo uniforme pseudoaleatório, e (ii) estimar números de Ramsey de ordem dois e três para grafos com largura de banda pequena e grau máximo limitado. Apresentamos um lema de contagem para estimar a quantidade de cópias de um hipergrafo k-uniforme linear livre de conectores (conector é uma generalização de triângulo, para hipergrafos) que estão presentes em um hipergrafo esparso pseudoaleatório G. Considere um hipergrafo k-uniforme linear H que é livre de conectores e um hipergrafo k-uniforme G com n vértices. Seja d_H=\\max\\{\\delta(J): J\\subset H\\} e D_H=\\min\\{k d_H,\\Delta(H)\\}. Estabelecemos que, se os vértices de G não possuem grau grande, famílias pequenas de conjuntos de k-1 elementos de V(G) não possuem vizinhança comum grande, e a maioria dos pares de conjuntos em {V(G)\\choose k-1} possuem a quantidade ``correta\'\' de vizinhos, então a quantidade de imersões de H em G é (1+o(1))n^{|V(H)|}p^{|E(H)|}, desde que p\\gg n^{1/D_H} e |E(G)|={n\\choose k}p. Isso generaliza um resultado de Kohayakawa, Rödl e Sissokho [Embedding graphs with bounded degree in sparse pseudo\\-random graphs, Israel J. Math. 139 (2004), 93--137], que provaram que, para p dado como acima, esse lema de imersão vale para grafos, onde H é um grafo livre de triângulos. Determinamos assintoticamente os números de Ramsey de ordem dois e três para grafos bipartidos com largura de banda pequena e grau máximo limitado. Mais especificamente, determinamos assintoticamente o número de Ramsey de ordem dois para grafos bipartidos com largura de banda pequena e grau máximo limitado, e o número de Ramsey de ordem três para tais grafos, com a suposição adicional de que ambas as classes do grafo bipartido têm aproximadamente o mesmo tamanho.