Colorações canônicas em Teoria de Ramsey (2026)
- Authors:
- Autor USP: VICENTE, HUGO MARTINS - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2026.tde-16032026-144300
- Subjects: COMBINATÓRIA; GRAFOS ALEATÓRIOS; MÉTODOS PROBABILÍSTICOS; TEORIA DE RAMSEY; TEORIA DOS GRAFOS
- Keywords: Combinatorics; Funções limiares; Graph theory; Probabilistic method; Ramsey theory; Random graphs; Threshold functions
- Agências de fomento:
- Language: Português
- Abstract: A propriedade Ramsey-canônica expande a teoria clássica de Ramsey ao considerar colorações em grafos sem restrição no número de cores, buscando padrões inevitáveis. Nesse contexto, uma cópia de um grafo H em um grafo G é chamada de canônica se for monocromática, rainbow ou lexicográfica. O Teorema de Ramsey Canônico, de Erdos e Rado, garante que, para qualquer grafo H, todo grafo suficientemente grande contém uma cópia canônica de H, sob qualquer coloração de suas arestas. Neste trabalho, estudamos o surgimento da propriedade Ramsey-canônica no modelo de grafos aleatórios G(n,p), isto é, investigamos para quais funções p = p(n) essa propriedade ocorre com alta probabilidade. Apresentamos e discutimos três resultados recentes nessa direção: o primeiro determina o limiar da propriedade para o caso em que H é um grafo completo Kl, o segundo estabelece o limiar no caso em que H é um grafo arbitrário, mas limitado a colorações com restrições de listas, e o terceiro mostra uma cota superior quase justa para o caso em que H é um ciclo par. As definições de propriedade Ramsey-canônica adotadas nesses três resultados variam ligeiramente, especialmente nas condições impostas sobre as cópias lexicográficas e, em geral, nenhum dos resultados implica o outro. As demonstrações desses resultados fazem uso de diversas técnicas de combinatória extremal e probabilística, como exposição em múltiplas rodadas, o uso cuidadoso de propriedades estruturais de G(n,p), método de Contêineresde hipergrafos, dentre outros. Ao longo desta dissertação, discutimos as diferenças fundamentais entre cada definição adotada, bem como as ideias centrais das demonstrações e ferramentas intermediárias necessárias
- Imprenta:
- Data da defesa: 27.01.2026
- Status:
- Nenhuma versão em acesso aberto identificada
-
ABNT
VICENTE, Hugo Sánchez. Colorações canônicas em Teoria de Ramsey. 2026. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2026. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-16032026-144300/. Acesso em: 11 abr. 2026. -
APA
Vicente, H. S. (2026). Colorações canônicas em Teoria de Ramsey (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-16032026-144300/ -
NLM
Vicente HS. Colorações canônicas em Teoria de Ramsey [Internet]. 2026 ;[citado 2026 abr. 11 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-16032026-144300/ -
Vancouver
Vicente HS. Colorações canônicas em Teoria de Ramsey [Internet]. 2026 ;[citado 2026 abr. 11 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-16032026-144300/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
