Teoria dos Grafos Extremal

A teoria dos grafos extremal investiga o quão grande ou denso um grafo pode ser enquanto evita uma subestrutura prescrita, e identifica as configurações extremas.

Definition

O estudo do valor máximo ou mínimo de um parâmetro de grafo, como o número de arestas, sujeito a uma restrição estrutural, como a ausência de um subgrafo fixo.

Scope

Este tópico centra-se em problemas do tipo Turan – o número máximo de arestas num grafo sem um dado subgrafo – começando com os teoremas de Mantel e Turan e estendendo-se ao teorema de Erdos-Stone, que determina a densidade extremal assintótica para qualquer subgrafo proibido. Introduz a interação entre densidade, estrutura e o método de regularidade de Szemeredi.

Core questions

• Qual é o número máximo de arestas num grafo com n vértices que não contém uma cópia de um dado subgrafo?
• Quais grafos atingem esses limites extremals?
• Como o número cromático de um subgrafo proibido governa a resposta assintótica?
• Como os métodos de regularidade reduzem grafos densos a uma estrutura limitada?

Key concepts

• Subgrafos proibidos
• Grafo de Turan
• Teorema de Mantel
• Número extremal (número de Turan)
• Teorema de Erdos-Stone
• Lema de regularidade de Szemeredi

Key theories

Teorema de Turan

Entre todos os grafos com n vértices sem um subgrafo completo em r+1 vértices, o grafo r-partido completo balanceado possui o maior número de arestas, generalizando o limite de Mantel para grafos sem triângulos e ancorando a teoria dos grafos extremal.

Teorema de Erdos-Stone

Para qualquer subgrafo proibido H fixo, a densidade máxima de arestas de um grafo livre de H é assintoticamente determinada pelo número cromático de H, unificando os resultados extremals do tipo Turan.

Clinical relevance

Os resultados de densidade extremal limitam a estrutura de grandes redes e sistemas de restrição, e o método de regularidade desenvolvido nesta área tem aplicações em testes de propriedades, ciência da computação teórica e combinatória aditiva.

History

O limite de Mantel de 1907 para grafos sem triângulos e a generalização de Turan de 1941 lançaram o campo; a teoria de Erdos-Stone-Simonovits e o lema de regularidade de Szemeredi tornaram-no um pilar central da combinatória moderna.

Key figures

• Paul Turan
• Paul Erdos
• Endre Szemeredi

Seminal works

• bollobas1998
• diestel2017

Frequently asked questions

O que é um problema do tipo Turan?

Ele pergunta qual o maior número de arestas que um grafo pode ter enquanto evita um subgrafo fixo; o exemplo canônico é o número máximo de arestas em um grafo sem triângulos.

Como a teoria dos grafos extremal se relaciona com a teoria de Ramsey?

Ambas estudam a estrutura inevitável, mas a teoria extremal fixa um subgrafo proibido e maximiza as arestas, enquanto a teoria de Ramsey garante uma estrutura monocromática quando o grafo é grande o suficiente.