• 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
 
 
Dissertação de Mestrado
DOI
10.11606/D.45.2018.tde-10092018-175741
Documento
Autor
Nome completo
Giulia Satiko Maesaka
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2018
Orientador
Banca examinadora
Kohayakawa, Yoshiharu (Presidente)
Collares Neto, Maurício de Lemos Rodrigues
Mota, Guilherme Oliveira
Título em português
Grafos e hipergrafos com cintura e número cromático grandes
Palavras-chave em português
Amálgama
Árvore aumentada
Cintura
Número cromático
Resumo em 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 em inglês
Graphs and hypergraphs with high girth and high chromatic number
Palavras-chave em inglês
Amalgamation
Augmented tree
Chromatic number
Girth
Resumo em 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.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
diss.pdf (4.08 Mbytes)
Data de Publicação
2018-10-01
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2018. Todos os direitos reservados.