---
# System prepended metadata

title: Nota inicial - Orientação

---

# Nota inicial - Orientação

## Semana 1

Número de Ramsey(k, x) é o menor inteiro __n__, tal que qualquer bi-coloração das arestas do grafo completo __Kn__ gera ao menos um clique azul de tamanho __k__ ou um clique vermelho de tamanho __x__.

(Ramsey 1929) Mostrou que R(x, y) é finito para qualquer inteiros x, y.

__Teorema__
Vamos obter um lower_bound para os números de Ramsey diagonais da forma R(k, k)

__Proposição 1.1.1__

$$
If {n \choose k} * 2^{1 - {k \choose 2}} < 1 => (R(k, k) >  \left \lfloor{2^{k/2}}\right \rfloor  , \forall k >= 3)
$$

Para mostrar que o lado esquerdo é de fato < 1, o autor usou a aproximação de Stirling para o binomial e massageou um pouco a equação para mostrar que essa cota superior da probabilidade de ao menos um clique monocromático nesse grafo aleatório é < 1. ( Para mais detalhes, basta olhar o capítulo 1 do livro )

Essa prova motiva algumas outras perguntas:
* Qual a chance de ter exatamente um clique?
* Qual a chance de ter ao menos dois clique? O que isso muda nos bounds e no N?
* Qual é a quantidade esperada de cliques no grafo





