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. / The proof by Erdos of the existence of graphs with high girth and high chromatic number is one of the first applications of the probabilistic method. This proof gives a bound on the number of vertices of such graphs, which is exponential on the girth if the chromatic number is fixed. The focus of this text is however on the deterministic construction of graphs with high girth and high chromatic number and on the number of vertices of the obtained graphs. The elementary known constructions can only give us graphs with an Ackermannian number of vertices. We begin by briefly repeating the probabilistic proofs of the existence of graphs and hypergraphs with high girth and high chromatic number. Then we motivate the search for deterministic constructions of such graphs by showing some constructions for the special case of triangle-free graphs with high chromatic number. We construct Tutte, Zykov, Mycielski and Kneser graphs, the shift graphs and graphs built from finite projective planes. We count and compare the number of vertices of the graphs obtained by each of these constructions. In fact, the construction based on finite projective planes gives us graphs with a polynomial number of vertices. The main part of the text consists of constructions of graphs and hypergraphs with high girth and high chromatic number. The first construction we present is due to Kriz. This was the first construction to give graphs with high girth and high chromatic number without using hypergraphs. The second construction we present is due to Nesetril and Rödl. This construction precedes the one by Kriz. It uses amalgamations between graphs and hypergraphs to obtain uniform hypergraphs with high girth and high chromatic number. The third and last construction we show was found by Alon, Kostochka, Reiniger, West and Zhu. This construction manages to build uniform hypergraphs with high girth and high chromatic number directly from a single graph, which is an augmented-tree. In particular, it constructs graphs with high girth and high chromatic number without using hypergraphs. We count and compare the number of vertices of the hypergraphs obtained by these constructions.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-10092018-175741 |
| Date | 08 June 2018 |
| Creators | Maesaka, Giulia Satiko |
| Contributors | Kohayakawa, Yoshiharu |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | English |
| Type | Dissertação de Mestrado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0022 seconds