A PROVA DE ZYKOV PARA O TEOREMA DE TURAN E PORQUE ELA FALHA EM HIPERGRAFOS

Resumo

Traçamos um paralelo entre Grafos e Hipergrafos no contexto do Teorema de Turán. Grafos são estruturas combinatórias formadas por um conjunto de pontos (chamados vértices) e um conjunto de alguns pares desses pontos (chamados arestas). Enquanto os Hipergrafos se diferem por ao invés de termos pares de vértices, termos conjuntos com uma quantidade qualquer de vértices (chamados de hiperarestas). A priori, um hipergrafo é apenas uma coleção de conjuntos finitos. Contudo, ele recebe tal nome quando há interesse em se apossar do arcabouço de ferramentas que existem para grafos e tentar determinar quais delas se estendem para hipergrafos. Grafos (e hipergrafos) possuem grande importância devido à sua enorme versatilidade, podendo ser aplicados em diversas áreas, como a Ciência da Computação, Biologia, Física e Química. Um hipergrafo é chamado de k-uniforme quando todas as suas hiperarestas possuem exatamente k vertices. Um hipergrafo k-uniforme é completo quando cada um dos subconjuntos de vértices com k elementos é uma hiperaresta. Vale ressaltar que um grafo é um hipergrafo 2-uniforme. Dados n e k, o Teorema de Turán fornece o número máximo de aresta que um grafo com n vértices pode ter sem possuir um grafo completo, com k vértices. Dados n, k e r>2, a pergunta análoga para hipergrafos r-uniformes é um problema em aberto para quase todas as triplas (n,k,r), tendo por exceção apenas valores muito pequenos destes parâmetros. Neste trabalho começamos por analisar uma prova do Teorema de Turán (para Grafos) que usa a técnica de simetrização de Zykov. Estudamos também uma variação do problema clássico de Erdos-Rothschild sobre contagem de um certo tipo de colorações de um grafo, com base no artigo "Edge-colorings of graphs avoiding complete graphs with a prescribed coloring" de Fabrício S. Benevides, Carlos Hoppen, e Rudini M. Sampaio. Nele uma generalização das ideias da prova de Zykov é utilizada. Agradece-se ao CNPq.