Grafos e hipergrafos com cintura e número cromático grandes

• Ano de defesa: 2018
• Autor(a) principal: Maesaka, Giulia Satiko
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Amálgama; Amalgamation; Árvore aumentada; Augmented tree; Chromatic number; Cintura; Girth; Número cromático
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-10092018-175741/

A demonstração feita por Erdos da existência de grafos com cintura e número cromático grandes é uma das primeiras aplicações do método probabilístico. Essa demonstração fornece um limite para o número de vértices de um grafo desse tipo, que é exponencial na cintura quando o número cromático é fixado. O foco deste texto, no entanto, são as construções determinísticas de grafos com cintura e número cromático grandes e os números de vértices dos grafos obtidos. As construções elementares conhecidas fornecem apenas grafos com um número Ackermanniano de vértices. O texto começa com uma breve repetição das demonstrações probabilísticas da existência de grafos e hipergrafos com cintura e número cromático grandes. Depois, a busca por construções determinísticas é motivada apresentando-se algumas construções para o caso particular de grafos livres de triângulo e com número cromático grande. São construídos os grafos de Tutte, Zykov, Mycielski e Kneser, os grafos de shift e os de planos projetivos finitos. Os números de vértices dessas construções são computados e comparados. De fato, a construção a partir de planos projetivos finitos tem um número polinomial de vértices. A parte principal do texto são as construções de grafos e hipergrafos com cintura e número cromático grandes. A primeira construção apresentada foi feita por Kriz. Ela foi a primeira construção para grafos com cintura e número cromático grandes que não envolvia hipergrafos. A segunda construção apresentada foi feita por Nesetril e Rödl. Essa construção antecede a de Kriz. Ela utiliza a amalgamação entre grafos e hipergrafos para obter um hipergrafo uniforme com cintura e número cromático grandes. A terceira e última construção apresentada foi encontrada por Alon, Kostochka, Reiniger, West e Zhu. Essa construção consegue obter hipergrafos uniformes com cintura e número cromático grandes diretamente a partir de um grafo, que é uma certa árvore aumentada. Em particular, essa construção obtém grafos com cintura e número cromático grandes sem envolver hipergrafos. Os números de vértices dos hipergrafos obtidos por essas construções são computados e comparados.