Repositório Digital

A- A A+

Problemas de coloração em teoria extremal de conjuntos

.

Problemas de coloração em teoria extremal de conjuntos

Mostrar registro completo

Estatísticas

Título Problemas de coloração em teoria extremal de conjuntos
Autor Contiero, Lucas de Oliveira
Orientador Hoppen, Carlos
Data 2014
Nível Mestrado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Matemática. Programa de Pós-Graduação em Matemática Aplicada.
Assunto Hipergrafos
Matematica aplicada
Resumo 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 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.
Tipo Dissertação
URI http://hdl.handle.net/10183/106441
Arquivos Descrição Formato
000943856.pdf (768.4Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.