Problemas de coloração em teoria extremal de conjuntos

Abstract

Neste trabalho de mestrado tratamos de problemas de coloração em Teoria Extremal de Conjuntos. Para números inteiros positivos n, k, q e t, uma (q, t)-coloração de um hipergrafo k-uniforme H com n vértices é uma função que associa cada hiperaresta de H a uma cor em [q], onde dois elementos de mesma cor possuem intersecção de tamanho pelo menos t. Um resultado recente [1] informa qual é o hipergrafo que admite o maior número de (q, t)-colorações quando q {2, 3, 4} ou q ≥ 5 e k ≥ 2t - 1. No caso em que q ≥ 5 e k < 2t 1, este resultado determina propriedades que um hipergrafo que atinge o número máximo de colorações deve possuir, porém não identi ca os hipergrafos ótimos entre todos que satisfazem essas propriedades. A principal contribuição do nosso trabalho foi estudar uma conjectura proposta pelos autores daquele trabalho. Adaptando uma técnica clássica, demonstramos que essa conjectura é verdadeira em alguns casos. Uma outra contribuição deste trabalho foi a apresentação detalhada de demonstrações de resultados clássicos associados a este problema.

In this master's thesis we considered problems in Extremal Set Theory. For positive numbers n, k, q and t, we say that a (q, t)-coloring of an n-vertex k-uniform hypergraph H is a function such that each hyperedge from H is associated with a color in [q], where two hyperedges with the same color have at least t elements in common. A recent result [1] determined the set of hypergraphs allowing the maximum number of (q, t)-colorings when q {2, 3, 4}or when q ≥ 5 and k ≥ 2t . In the case q ≥ 5 and k < 2t - 1, that work found properties that a hypergraph with the maximum number of (q, t)-colorings satis es, but did not determine which hypergraphs are extremal. The main contribution of our work is to study a conjecture proposed by the authors of [1], which further restricts the class of possible extremal hipergraphs. Using a classical technique, we prove their conjecture for q 2 f5; 6g and restrict the class of possible extremal hipergraphs in the other cases. Another contribution of this work is the presentation of detailed proofs of the classical results related to this problem.