Grafos e hipergrafos com cintura e número cromático grandes (2018)
- Authors:
- Autor USP: MAESAKA, GIULIA SATIKO - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: CIENCIA DA COMPUTACAO
- Keywords: Amálgama; Amalgamation; Árvore aumentada; Augmented tree; Chromatic number; Cintura; Girth; Número cromático
- Agências de fomento:
- Language: Português
- Abstract: 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
- Imprenta:
- Data da defesa: 08.06.2018
-
ABNT
MAESAKA, Giulia Satiko. Grafos e hipergrafos com cintura e número cromático grandes. 2018. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2018. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-10092018-175741/. Acesso em: 23 jan. 2026. -
APA
Maesaka, G. S. (2018). Grafos e hipergrafos com cintura e número cromático grandes (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-10092018-175741/ -
NLM
Maesaka GS. Grafos e hipergrafos com cintura e número cromático grandes [Internet]. 2018 ;[citado 2026 jan. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-10092018-175741/ -
Vancouver
Maesaka GS. Grafos e hipergrafos com cintura e número cromático grandes [Internet]. 2018 ;[citado 2026 jan. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-10092018-175741/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
