Problemas de coloração em teoria extremal de conjuntos
![Thumbnail](/bitstream/handle/10183/106441/000943856.pdf.jpg?sequence=3&isAllowed=y)
View/ Open
Date
2014Author
Advisor
Academic level
Master
Type
Abstract in Portuguese
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 e ...
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. ...
Abstract
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 ...
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. ...
Institution
Universidade Federal do Rio Grande do Sul. Instituto de Matemática. Programa de Pós-Graduação em Matemática Aplicada.
Collections
-
Exact and Earth Sciences (5092)Mathematics (362)
This item is licensed under a Creative Commons License
![](/themes/Mirage2Novo//images/lume/cc.png)