Dois resultados em combinatória contemporânea

Autor(es)

Guilherme Oliveira Mota

• Tipo de documento: Tese de Doutorado
• Imprenta: São Paulo.
• Instituição: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
• Data de defesa: 2013-08-30

Membros da banca

Yoshiharu Kohayakawa; Fabricio Siqueira Benevides; Carlos Hoppen; Daniel Morgato Martin; Rudini Menezes Sampaio

• Orientador: Yoshiharu Kohayakawa

Resumo

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. (AU)

• Processo FAPESP: 09/06294-0 - Combinatória assintótica de estruturas esparsas e regularidade
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Bolsas no Brasil - Doutorado