• 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
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.45.2000.tde-20220712-115125
Documento
Autor
Nombre completo
Marcio Grossi de Almeida
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2000
Director
Título en portugués
Números de Ramsey induzidos e semi-induzidos
Palabras clave en portugués
Combinatória
Teoria Dos Grafos
Resumen en portugués
Dados dois grafos G e H quaisquer, chamamos de número de Ramsey semi-induzido `r sind(G,H)¦ e de número de Ramsey semi-induzido para arestas `r sind(G,H)¦, respectivamente, a menor ordem e o menor número de arestas possíveis para um grafo`GAMA¦com a propriedade de que sempre que suas arestas são coloridas com as cores vermelha e azul, ou `GAMA¦ possui uma cópia vermelha de G ou `GAMA¦ possui uma cópia induzida de H. Para o caso em que T é uma árvore e H é um grafo qualquer, nósmostramos que `r sind(T,H)¦< OU = `(t-1)`h POT.2¦ e `r sind(T,H)¦< OU = `[(t-1)h] POT.2[E(H)], se h=[V(H)] > OU = 2 e t=[V(T)] > OU =2. No caso em que T possui grau máximo limitado, nós mostramos que, para todo E > 0, se h=[V(H)] > OU =`0SOB.0¦(E), t=[V(T)] > OU = `0 SOB.t¦(E) e d=¦DELTA¦(T) então `r sind(T,H) < `cd POT.9/2¦(`h POT.2¦ `t POT.3/2¦)`POT.1+E[E(H¦)], onde c é uma constante que depende de E. Nós também investigamos o número de Ramsey induzido `r ind(G,H)¦, que édefinido como sendo a menor ordem possível para um grafo `GAMA¦ com a propriedade de que sempre que suas arestas são coloridas com as cores vermelha e azul, ou `GAMA¦ possui uma cópia vermelha induzida de G ou `GAMA¦ possui uma cópia azulinduzida de H. Nós mostramos que se o grafo G pertence à classe `EH POT.var¦({`K POT.1¦, `K POT.2¦, `I POT.2¦}) - que equivale à classe dos grafos simples definida em Erdos e Hajnal [5] - então `r ind(G,H) < [V(H)] POT.f¦, onde f é uma constanteque depende somente de G
Título en inglés
not available
Resumen en inglés
For any given graphs G and H, we define the semi-induced Ramsey number r sind(G,H) and the edge semi-induced Ramsey number r sind(G,H), as the smallest order and the smallest number of edges of a graph `GAMA¦ having the property that, wheneveritsedges are coloured red and blue, either a red copy of G arises or else a blue induced copy of H arises. When T is a tree and H is a graph, we show that r ind (T,H) < OU = (t-1)¦h POT.2¦ and r sind(T,H) < OU = [(t-1)h] POT.2[E(H)], where h=[V(H)] > ou = 2 and t = [V(T)] > OU = 2. When T has bounded maximum degree, we show that, for any E > 0, if we have h = [V(H)] > OU = `0 SOB. h¦(E), t=[V(T)] > OU = `0 SOB.t¦ (E) and d = `DELTA¦(T) then r sind(T,H) < `cd POT.9/2¦(`hPOT.2¦tPOT.3/2¦)`POT.1=E¦[E(H)], where c is a constant that only depends on E. We also investigate the induced Ramsey number r ind(G,H), which is defined as the smallest order of a graph `GAMA¦ having the property that, whenever its edges arecolouredred and blue, either a red induced copy of G arises or else a blue induced copy of H arises. We show that if G belongs to a class of graphs called `EH POT.var({`K POT.1, K POT.2, 1 POT.2}) - which is the Erdos and Hajnal [5] class ofsimplegraphs - then r ind(G,H) < `[V(H)]POT.f¦, where f is constant that only depends on G
 
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.
Fecha de Publicación
2022-07-13
 
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.