Sobre a Conjectura do Número de Queima de um Grafo

Aluno: Lucas Sepeda Lima

Orientador: Prof. Dr. Fábio H. Botler

Curso: Bacharelado em Ciência da Computação

Instituição: Instituto de Matemática e Estatística – Universidade de São Paulo

Ano: 2025

Resumo

O objetivo central deste trabalho é estudar, de maneira sistemática e detalhada, a prova apresentada por Norin e Turcotte (2024) de que a Conjectura do Número de Queima vale assintoticamente, isto é, que para todo grafo conexo com n vértices tem-se b(G) ≤ (1 + o(1))√n. Em vez de apenas registrar o resultado final, o foco do texto está em reconstruir cuidadosamente cada etapa do argumento, tornando explícita a lógica que conduz da formulação original do processo de queima ao limitante assintótico.

A abordagem segue de perto a estratégia do artigo original. Inicialmente, reinterpretamos a dinâmica de queima como um problema de cobertura por bolas, o que permite a transição para o modelo contínuo de árvores métricas. Em seguida, introduzimos e analisamos com detalhe as técnicas probabilísticas centrais da prova, em particular o uso de coberturas aleatórias, da medida de expectativa e do controle do momento, que garantem uma distribuição quase uniforme dos raios ao longo da árvore.

Por fim, investigamos como os resultados obtidos no cenário contínuo são transferidos de volta para o contexto discreto de grafos finitos, completando o argumento assintótico. Ao longo de todo o trabalho, a ênfase recai na explicação conceitual e técnica das ferramentas probabilísticas empregadas, com o objetivo de tornar o método transparente e acessível para aplicações futuras em problemas análogos de cobertura em grafos.

📄 Acessar a monografia completa (PDF)