• 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
 
 
Tesis Doctoral
DOI
https://doi.org/10.11606/T.45.2013.tde-31102013-110457
Documento
Autor
Nombre completo
Guilherme Oliveira Mota
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2013
Director
Tribunal
Kohayakawa, Yoshiharu (Presidente)
Benevides, Fabricio Siqueira
Hoppen, Carlos
Martin, Daniel Morgato
Sampaio, Rudini Menezes
Título en portugués
Dois resultados em combinatória contemporânea
Palabras clave en portugués
hipergrafos
imersão
Pseudoaleatoriedade
Ramsey
regularidade.
Resumen en 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 en inglés
Two problems in modern combinatorics
Palabras clave en inglés
embedding
hypergraphs
Pseudorandomness
Ramsey
regularity
Resumen en 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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
tese.pdf (676.65 Kbytes)
Fecha de Publicación
2013-11-08
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2024. Todos los derechos reservados.