Vértice-particionamentos e problemas de densidade em grafos aresta-coloridos infinitos.

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.