• 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
 
 
Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.45.2000.tde-20220712-115125
Document
Auteur
Nom complet
Marcio Grossi de Almeida
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2000
Directeur
Titre en portugais
Números de Ramsey induzidos e semi-induzidos
Mots-clés en portugais
Combinatória
Teoria Dos Grafos
Resumé en portugais
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
Titre en anglais
not available
Resumé en anglais
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
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2022-07-13
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2024. Tous droits réservés.