• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tese de Doutorado
DOI
10.11606/T.45.2013.tde-31102013-110457
Documento
Autor
Nome completo
Guilherme Oliveira Mota
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2013
Orientador
Banca examinadora
Kohayakawa, Yoshiharu (Presidente)
Benevides, Fabricio Siqueira
Hoppen, Carlos
Martin, Daniel Morgato
Sampaio, Rudini Menezes
Título em português
Dois resultados em combinatória contemporânea
Palavras-chave em português
hipergrafos
imersão
Pseudoaleatoriedade
Ramsey
regularidade.
Resumo em português
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.
Título em inglês
Two problems in modern combinatorics
Palavras-chave em inglês
embedding
hypergraphs
Pseudorandomness
Ramsey
regularity
Resumo em inglês
Two combinatorial problems are studied: (i) determining the number of copies of a fixed hipergraph in uniform pseudorandom hypergraphs, and (ii) estimating the two and three color Ramsey numbers for graphs with small bandwidth and bounded maximum degree. We give a counting lemma for the number of copies of linear k-uniform \emph hypergraphs (connector is a generalization of triangle for hypergraphs) that are contained in some sparse hypergraphs G. Let H be a linear k-uniform connector-free hypergraph and let G be a k-uniform hypergraph with n vertices. Set d_H=\max\{\delta(J)\colon J\subset H\} and D_H=\min\{kd_H,\Delta(H)\}. We proved that if the vertices of G do not have large degree, small families of (k-1)-element sets of V(G) do not have large common neighbourhood and most of the pairs of sets in {V(G)\choose k-1} have the `right' number of common neighbours, then the number of embeddings of H in G is (1+o(1))n^{|V(H)|}p^{|E(H)|}, given that p\gg n^{1/D_H} and |E(G)|={n\choose k}p. This generalizes a result by Kohayakawa, R\"odl and Sissokho [Embedding graphs with bounded degree in sparse pseudo\-random graphs, Israel J. Math. 139 (2004), 93--137], who proved that, for p as above, this result holds for graphs, where H is a triangle-free graph. We determine asymptotically the two and three Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. More generally, we determine asymptotically the two color Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that both classes of the bipartite graph have almost the same size.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
tese.pdf (676.65 Kbytes)
Data de Publicação
2013-11-08
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2020. Todos os direitos reservados.