Prova do teorema de Ramsey: o número de cliques ou anticliques em um gráfico

O teorema de Ramsey afirma que todo gráfico com nós contém um clique ou um conjunto independente com pelo menos nós.$n$$\frac{1}{2}\log_2 n$

Tentei procurar em alguns lugares (incluindo o Sipser), mas não consegui entender muito bem as provas. Eu apreciaria se alguém pudesse me dar uma prova (ou uma intuição clara) sobre isso.

Seja o menor número inteiro modo que todo gráfico em ou mais vértices contenha um$R(s,t)$$k$$k$$s$-clique ou conjunto independente de tamanho $t.$

Acontece que esse número está bem definido (chamado número de Ramsey ) e a afirmação em sua pergunta apenas significa dizer que

$$R(t,t) \leq 2^{2t}.$$

Um limite superior bem conhecido para o número de Ramsey indica se , o valor acima se reduz ao coeficiente binomial central que é sempre menor que

$$R(s,t) \leq R(s,t-1)+R(s-1,t) \leq {s+t-2 \choose t-1} \; \; \; (1)$$ $s = t$ ${2t-2 \choose t-1}$$2^{2t}$

Para provar pode-se usar indução em . Partindo da base de indução como um exercício para você, vamos supor que a desigualdade vale para todos e seja um gráfico com vértices.$(1)$$s+t$$R(1,t), R(s,1)$$s+t < k$$G$$R(s,t-1)+R(s-1,t)$

Seja um vértice arbitrário de e divida os vértices restantes do gráfico em dois grupos - aqueles adjacentes a aqueles que não são adjacentes a Agora desde que , temosAgora, se a primeira desigualdade for satisfeita, o gráfico induzido por contém uma classe ou o gráfico induzido por contém um conjunto independente de tamanhoEm particular, isso implica que, neste caso, contém um$v$$G$$A,N$$v$$v.$

$$|A|+|N|+1 = R(s,t-1)+R(s-1,t)$$ $$|N| \geq R(s,t-1) \quad \mbox{ or} \quad |A| \geq R(s-1,t).$$ $N$$s$$N \cup \{v\}$$t.$$G$$s$-clique ou conjunto independente de tamanhoO segundo caso é verificado analogamente e estabelece a primeira parte do limite declarado. Para a última parte, observe que$t.$ $${s+t-3 \choose s-1} + {s+t-3 \choose s-2} = {s+t-2 \choose s-1}.$$