Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.2000.tde-20220712-115125
Documento
Autor
Nome completo
Marcio Grossi de Almeida
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2000
Orientador
Título em português
Números de Ramsey induzidos e semi-induzidos
Palavras-chave em português
Combinatória
Teoria Dos Grafos
Resumo em 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 em inglês
not available
Resumo em 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
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.
Data de Publicação
2022-07-13