• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
10.11606/D.45.2018.tde-10092018-175741
Documento
Autor
Nombre completo
Giulia Satiko Maesaka
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2018
Director
Tribunal
Kohayakawa, Yoshiharu (Presidente)
Collares Neto, Maurício de Lemos Rodrigues
Mota, Guilherme Oliveira
Título en portugués
Grafos e hipergrafos com cintura e número cromático grandes
Palabras clave en portugués
Amálgama
Árvore aumentada
Cintura
Número cromático
Resumen en portugués
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.
Título en inglés
Graphs and hypergraphs with high girth and high chromatic number
Palabras clave en inglés
Amalgamation
Augmented tree
Chromatic number
Girth
Resumen en inglés
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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
diss.pdf (4.08 Mbytes)
Fecha de Publicación
2018-10-01
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2022. Todos los derechos reservados.