Teorema de Ramsey e Números de Ramsey

O teorema de Ramsey garante que qualquer grafo completo suficientemente grande e bicolorido contém uma clique monocromática, e os números de Ramsey quantificam o quão grande é "suficiente".

Definition

O número de Ramsey R(s,t) é o menor inteiro n tal que toda coloração vermelho-azul das arestas do grafo completo em n vértices contém uma clique vermelha em s vértices ou uma clique azul em t vértices.

Scope

Este tópico aborda a forma gráfica do teorema de Ramsey, a definição dos números de Ramsey R(s,t), os casos clássicos pequenos como R(3,3)=6, o limite superior de Erdos-Szekeres e o limite inferior probabilístico de Erdos, e a extensão para números de Ramsey multicoloridos e de hipergrafos. É o cerne quantitativo da teoria de Ramsey.

Core questions

• Qual o tamanho mínimo que um grafo completo deve ter para forçar uma clique monocromática de um dado tamanho?
• Quais são os valores exatos e os limites conhecidos para os números de Ramsey?
• Como os argumentos probabilísticos fornecem limites inferiores para os números de Ramsey?
• Como o teorema se generaliza para várias cores e para hipergrafos?

Key concepts

• Teorema de Ramsey para grafos
• Número de Ramsey R(s,t)
• Cliques monocromáticas
• Limite de Erdos-Szekeres
• Limites inferiores probabilísticos
• Números de Ramsey multicoloridos e de hipergrafos

Key theories

Limite superior de Erdos-Szekeres

Os números de Ramsey são finitos e limitados por R(s,t) sendo no máximo o coeficiente binomial de s+t-2 sobre s-1, um limite baseado em recorrência que prova o teorema de Ramsey com estimativas explícitas.

Limite inferior probabilístico de Erdos

Ao contar as cliques monocromáticas esperadas em uma coloração aleatória, Erdos mostrou em 1947 que o número de Ramsey diagonal R(s,s) cresce pelo menos exponencialmente, uma aplicação fundadora do método probabilístico.

Clinical relevance

O método probabilístico introduzido através dos limites inferiores dos números de Ramsey tornou-se uma ferramenta central na combinatória e na ciência da computação teórica, e as garantias do tipo Ramsey sustentam os limites inferiores na comunicação e nas estruturas de dados.

History

Erdos e Szekeres redescobriram e quantificaram o teorema de Ramsey em 1935 enquanto estudavam polígonos convexos; o limite inferior de coloração aleatória de Erdos em 1947 lançou o método probabilístico.

Key figures

• Frank Ramsey
• Paul Erdos
• George Szekeres

Seminal works

• graham1990

Frequently asked questions

Por que R(3,3) é igual a seis?

Entre quaisquer seis pessoas, três são conhecidos mútuos ou três são estranhos mútuos, enquanto cinco pessoas podem ser arranjadas para evitar ambos, então seis é o limiar exato.

Os números de Ramsey exatos são conhecidos?

Apenas um punhado é conhecido exatamente; mesmo R(5,5) está em aberto, com o conhecimento atual apenas o restringindo a um intervalo, porque o espaço de busca cresce muito rapidamente para ser resolvido por computação.