Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/52845
Title in Portuguese: Vértice-particionamentos e problemas de densidade em grafos aresta-coloridos infinitos.
Title: Vertex-partitioning and density problems in infinite edge-colored graphs.
Author: Cunha, Arthur Carvalho Walraven da
Advisor(s): Benevides, Fabrício Siqueira
Keywords: Coloração de arestas
Partição de vértices
Densidade de subgrafos
Grafos enumeravelmente infinitos
Issue Date: 29-Apr-2020
Citation: CUNHA, Arthur Carvalho Walraven. Vértice-particionamentos e problemas de densidade em grafos aresta-coloridos infinitos. 2020. 84 f. Dissertação (Mestrado Acadêmico em Matemática) – Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2020.
Abstract in Portuguese: Recentemente, duas questões clássicas de combinatória extremal em grafos enumeravelmente infinitos voltaram a receber atenção. Dado r natural, um grafo G, chamado de hospedeiro, e uma família de subgrafos (caminhos, ciclos, grafos completos, etc.), no primeiro problema, estuda-se a quantidade mínima necessária de partes para que seja possível vértice-particionar qualquer r-coloração das arestas de G de forma que cada parte possua um subgrafo gerador na família escolhida. No outro, uma variação do problema de Ramsey, analisa-se a maior densidade, d, tal que qualquer r-coloração das arestas de G contenha um subgrafo monocromático de densidade pelo menos d pertencente à família escolhida. Nesta dissertação, revisamos a literatura referente à versão infinita desses tópicos, rescrevemos algumas demonstrações antigas usando a linguagem de artigos e livros mais recentes e simplificamos outras com auxílio de ultrafiltros não-principais. Também estudamos alguns resultados da variante clássica, correspondente a grafos hospedeiros finitos, e discutimos sua relação com a versão infinita.
Abstract: Recently, two classic questions of extremal combinatorics in enumerably infinite graphs have again received attention. Given the natural r, a graph G, called a host, and a family of subgraphs (paths, cycles, complete graphs, etc.), in the first problem, we study the minimum necessary number of parts so that it is possible to vertex-partition any r-coloring the edges of G so that each part has a generator subgraph in the chosen family. In the other, a variation of the Ramsey problem, the highest density, d, is analyzed, such that any r-coloring of the edges of G contains a monochrome subgraph of density at least d belonging to the chosen family. In this dissertation, we review the literature on the infinite version of these topics, rewrite some old statements using the language of more recent articles and books, and simplify others with the help of non-mainstream filters. We also studied some results of the classic variant, corresponding to finite host graphs, and discussed its relationship with the infinite version.
URI: http://www.repositorio.ufc.br/handle/riufc/52845
metadata.dc.type: Dissertação
Appears in Collections:DMAT - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2020_dis_acwcunha.pdf698,74 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.