
\documentclass[11pt]{amsart}
%\documentclass{amsart}

%% Escrevendo em portugu\^{e}s:
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc} % isso \'{e} quase redundante
\usepackage{textcomp}
\usepackage[T1]{fontenc}
%----------------------------

\usepackage{fullpage}
\usepackage{./doublespace}
\usepackage{amssymb}
\usepackage{url}
\usepackage{graphicx}
\usepackage{epsfig}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\def\@setdate{\datename\ \@date}
\def\@setthanks{\def\thanks##1{\par##1}\thankses}
\makeatother

\let\:=\colon
\def\bbn{{\mathbb N}}
\def\bbr{{\mathbb R}}
\def\bbz{{\mathbb Z}}
\def\calr{{\mathcal R}}
\def\calz{{\mathcal Z}}
\def\caln{{\mathcal N}}
\def\calf{{\mathcal F}}

\def\sup{\mathop{\text{\rm sup}}\nolimits}
\def\dist{\mathop{\text{\rm dist}}\nolimits}
\def\diag{\mathop{\text{\rm diag}}\nolimits}
\def\diam{\mathop{\text{\rm diam}}\nolimits}

\footskip=20pt

\newtheoremstyle{note}% name
  {4pt}%      Space above
  {4pt}%      Space below 
  {\sl}%      Body font
  {}%         Indent amount (empty = no indent, \parindent = para indent)
  {\bfseries}% Thm head font
  {.}%        Punctuation after thm head
  {.5em}%     Space after thm head: " " = normal interword space;
                                %       \newline = linebreak
  {}%         Thm head spec (can be left empty, meaning `normal')

%Tamanho da identação do parágrafo
\setlength{\parindent}{20pt}

\newtheorem{teorema}             {Teorema}       
\newtheorem{afirmativa}[teorema] {Afirmativa}         
\newtheorem{lema}      [teorema] {Lema}         
\newtheorem{corolario} [teorema] {Corolário}     
\newtheorem{fato}      [teorema] {Fato}          
\newtheorem{conjectura}[teorema] {Conjectura}    
\newtheorem{problema}  [teorema] {Problema}     



\theoremstyle{note}
\newtheorem{propriedade}  [teorema] {Propriedade}       
\newtheorem{definicao}  [teorema] {Definição}       
\newtheorem{exercicio}  [teorema] {Exercício}       

\title[Combinatória]{\textsl{PICME/IME/USP Combinatória}\\\vspace{1\jot}
  Notas - 2009} 

\author[Kohayakawa e Mota]{Yoshiharu Kohayakawa e Guilherme Mota (IME/USP)} 

\thanks{Notas por Guilherme Mota} 

% \def\datename{\textit{Data}:} 
% \date{9/6/2009}

\begin{document}
\maketitle
\thispagestyle{empty}
\onehalfspace



\section{Grafos e número cromático}
\label{sec:grafos-e-numero}
\begin{center}
 2/6/2009
\end{center}

\subsection{}
Um \textit{grafo} $G=(V,E)$ é a estrutura composta por um conjunto de
\textit{vértices} $V$ e um conjunto de \textit{arestas} $E$, onde uma aresta é
um par não ordenado de vértices $\{x,y\}$.

\subsection{}
O \textit{número cromático} $\chi(G)$ de um grafo $G$ é o menor número de
\textit{cores} tal que é possível colorir \textit{propriamente} os vértices de
$G$, isto é, de forma que vértices adjacentes devem receber cores diferentes.

\subsection{}
O \textit{grau} de um vértice $v$, denotado $\deg(v)$, é o número vizinhos de
$v$, isto é, o número de vértices adjacentes a $v$.

\subsection{}
Denotamos por $\delta(G)=\min\{\deg(v)\: v \in V\}$ o grau mínimo de $G$ e~${\Delta(G)=\max\{\deg(v)\: v \in V\}}$ o grau máximo de $G$.

\subsection{}
Uma questão importante sobre números cromáticos, conhecida como o
\textbf{Problema das 4 cores}, foi proposta por Guthrie~(1852) e respondida
por Appel e Haken~(1977) \cite{ApHa77}.

\begin{teorema}[Teorema das 4 cores (Appel e Haken '77)]
  Todo grafo planar pode ser colorido propriamente com~$4$ cores.
\end{teorema}

A demonstração dada por Appel e Haken faz uso do computador e não pode ser
verificada sem ele, de modo que não é uma prova completamente satisfatória.  Para saber mais sobre a história do problema, detalhes de
provas
e generalizações, veja a página do pesquisador Robin Thomas:
\begin{verbatim}
  http://people.math.gatech.edu/~thomas/
\end{verbatim}

\subsection{Problemas e exercícios}
\label{ex:1}
Todos estão convidados a trabalhar nos seguintes problemas, e\-xer\-cí\-cios e
observações. 

\begin{enumerate}
\item[0.]Quais grafos $G$ são tais que $\chi(G)\geq 3$?  A resposta é simples: 
  \begin{enumerate}
  \item[(\textit{i})]$\chi(C^{2k+1})=3$, onde $C^\ell$ é um \textit{circuito}
    com $\ell$ vértices.
  \item[(\textit{ii})]Se $\chi(G)\geq 3$, então $G$ contém um circuito ímpar.
  \end{enumerate}
  
\item[1.]É fácil ver que $\chi(G)\leq \Delta(G) + 1$.  Quais grafos conexos
  são tais que $\chi(G) = \Delta(G) + 1$?
  
  Grafos completos e circuitos ímpares são exemplos de grafos para os quais vale a
  igualdade acima.  Existem outros grafos que satisfazem tal igualdade?
  
\item[2.]Sejam dados grafos $G_1=(V_1,E_1)$ e $G_2=(V_2,E_2)$.  Definimos um
  novo grafo, pondo $G_1\cup G_2 = (V_1\cup V_2,\ E_1\cup E_2)$ (possivelmente, 
  $V_1\cap V_2\neq\varnothing$ e $E_1\cap E_2\neq\varnothing$).  Mostre que
  $\chi(G_1\cup G_2)\leq \chi(G_1)\chi(G_2)$.
  
\item[3.]Sejam dados grafos $G_1=(V_1,E_1)$ e $G_2=(V_2,E_2)$.  Definimos um
  novo grafo $G_1\times G_2 = (V_1\times V_2,E)$, onde
  $E=\big\{\{(x_1,x_2),(y_1,y_2)\}\:\{x_1,y_1\}\in E_1\text{ e }\{x_2,y_2\}\in
  E_2\big\}$.  Mostre que $\chi(G_1\times
  G_2)\leq\min\{\chi(G_1),\chi(G_2)\}$.

\item[**4.]Mostre que $\chi(G_1\times G_2) = \min\{\chi(G_1),\chi(G_2)\}$.
  \begin{enumerate}
  \item[(\textit{i})]Este fato foi conjecturado por Hedetniemi e ainda não se
    sabe se o resultado é válido.
  \item[(\textit{ii})]Sabe-se que o resultado é verdadeiro se
    $\chi(G_1)=\chi(G_2)=4$.
  \item[(\textit{iii})]Em geral, o resultado não vale para grafos com número
    cromático infinito.  Existem $G_1$ e $G_2$ tais que $\chi(G_1)$ e
    $\chi(G_2)$ são não-enumeráveis e $G_1\times G_2$ tem número cromático
    enumerável.
  \end{enumerate}

\item[5.] Seja $G=(\bbn,E)$ um grafo sobre os números naturais.  Suponha que
  $\chi(G')\leq 2009$ para todo~$G'$ com $|V(G')|<\infty$ obtido de $G$
  removendo-se todos os vértices em $\mathbb{N}\setminus V(G')$.  Mostre que
  $\chi(G)\leq 2009$.
 
\item[6.]Encontre um grafo $G$ com $\chi(G)\geq 2009$ que não contém um
  triângulo.   
  
\item[7.]Seja $G=(\bbr^2,E)$, onde $E=\big\{\{x,y\}\: x,\,y\in\bbr^2\text{ e }
  \dist(x,y)=1\big\}$.  Encontre boas cotas inferiores e superiores para
  $\chi(G)$.
\end{enumerate}














\newpage
\section{Grafos dirigidos e grafos perfeitos}
\label{sec:dirigidos-e-perfeitos}
\begin{center}
 9/6/2009
\end{center}

\subsection{}
Um \textit{grafo dirigido} $(\vec{G})$ é um par $(V,A)$ onde $A$ é um conjunto de \textit{pares ordenados} de vértices. Chamamos uma aresta dirigida de \textit{arco}.

\subsection{}
O \textit{grafo linha} $L(\vec{G})$ de $\vec{G}=(V,A)$ é o grafo (não-dirigido) com conjunto de vértices $A$ e em $L(\vec{G})$ temos a aresta $\{a,a'\}$ se $a=(x,y)$ e $a'=(x',y')$ com $x'=y$.

\subsection{}
O \textit{número de clique} $\omega(G)$ de um grafo $G$ é a quantidade de vértices do maior grafo completo (clique) contido em $G$. Observe que a desigualdade $\chi(G)\geq\omega(G)$ é verdadeira.

\subsection{}
Um \textit{subgrafo induzido} $G'=(V',E')$ de um grafo $G=(V,E)$ é o grafo formado por um subconjunto de vértices $V'$ de $V$ e pelas arestas cujas duas extremidades encontram-se em $V'$.

\subsection{}
Um grafo $G$ é dito \textit{perfeito} quando $\chi(G') = \omega(G')$, para todo subgrafo induzido $G'$ de $G$. Observe que, por exemplo, os grafos que contém $C^5$, $C^7$ ou $\bar{C^7}$ não são perfeitos. É um bom exercício calcular $\chi(\bar{C^7})$ e $\omega(\bar{C^7})$.

\subsection{}
Uma \textit{árvore} $T$ é vazia ou da forma $(r;T_1,T_2,\ldots)$, onde $r$ é um vértice chamado \textit{raiz} de $T$ e os $T_i$ são árvores não-vazias (possivelmente, a lista de árvores é vazia, isto é, $T=(r)$). As raízes dos $T_i$ são os \textit{filhos} de $r$.

\subsection{}
Um \textit{caminho (descendente)} em uma árvore $T$ é uma sequência da forma $r_0$, $r_1$,$\ldots$, onde $r_i$ é filho de $r_{i-1}$ para todo $i>0$.


\begin{lema}[Lema de König (D. König '36)]\label{konig36}
Toda árvore infinita (com infinitos vértices) em que a quantidade de filhos de cada vértice é finita possui um caminho infinito.
\end{lema}
\begin{proof}
Pode ser provado por indução, utilizando o fato de que uma partição finita de um conjunto infinito necessariamente contém uma parte infinita.
\end{proof}

\begin{corolario}
 Seja uma sequência infinita de sequências, onde os $a_{i,j}$ pertencem todos a um conjunto finito
\begin{eqnarray*}
s_1 &=& a_{1,1}\\
s_2 &=& a_{2,1},a_{2,2}\\
s_3 &=& a_{3,1},a_{3,2},a_{3,3}\\
&&\vdots \\
s_i &=& a_{i,1},a_{i,2},a_{i,3},\ldots,a_{i,i}\\
&&\vdots
\end{eqnarray*}
Então existe uma sequência infinita $$s=a_1,a_2,\ldots$$ tal que, para todo $n$, existe um $N$ tal que $s$ e $s_N$ coincidem em seus primeiros $n$ símbolos.
\end{corolario}
\begin{proof}
Monte uma árvore com os $s_i$ e aplique o Lema de König.
\end{proof}
\subsubsection*{Observação} O corolário acima implica o Teorema de \textit{de Bruijn--Erd\H os}, que é uma generalização do exercício
\ref{ex:1}-5. Para saber mais sobre este teorema, veja \cite{BrEr51} e \cite{Ra49}.



\subsection{Problemas e exercícios}
\label{ex:2}
Todos estão convidados a trabalhar nos seguintes problemas, e\-xer\-cí\-cios e
observações. 

\begin{enumerate}
\item[1.]Mostre que $\chi(L(\vec{G})) \geq \log_2{\chi(\vec{G})}$.
  
A desigualdade acima pode ser útil na resolução do exercício \ref{ex:1}-6.

  
\item[2.]Sejam $I_1,I_2,\ldots,I_n \subset \mathbb{R}$ intervalos na reta.

\begin{enumerate}
  \item[(\textit{i})]Defina o grafo $G$ sobre $V(G)=\{1,2,\ldots,n\}$ pondo $\{i,j\}\in E(G)$ se e somente se $I_i\cap I_j\neq\varnothing$. Prove que $\chi(G)=\omega(G)$. Ademais, conclua que $G$ é perfeito.
  \item[(\textit{ii})]Defina o grafo $H$ sobre $V(H)=\{1,2,\ldots,n\}$ pondo $\{i,j\}\in E(H)$ se e somente se $I_i\cap I_j = \varnothing$. Prove que $\chi(H)=\omega(H)$. Ademais, conclua que $H$ é perfeito.
\end{enumerate}

\item[3.]Fixe um grafo $G$. Seja $P_G(\lambda)$ o número de colorações próprias de $G$ com no máximo $\lambda$ cores ($\lambda\in \mathbb{N}$). É importante notar que $P_G(\lambda)>0 \leftrightarrow \chi(G)\leq\lambda$. Prove que $P_G(\lambda)$ é um polinômio em $\lambda$.

$P_G(\lambda)$ é conhecido como \textit{polinômio cromático} e foi introduzido por George David Birkhoff em 1912 na tentativa de provar o Teorema das quatro cores. Sua idéia era tentar mostrar que se $G$ é um grafo planar, então $P_G(4)>0$. W. T. Tutte conseguiu mostrar que $P_G(\tau + 2)>0$, onde $\tau$ é a razão áurea ($\approx$ 1.618).
  
\end{enumerate}

















\newpage
\section{Grafos e número cromático - Continuação}
\label{sec:grafos-e-numero-cont}
\begin{center}
 16/6/2009
\end{center}


\subsection{}
Sejam $x=(x_1,x_2,\ldots,x_n)\in \bbr^n$ e $y=(y_1,y_2,\ldots,y_n)\in \bbr^n$. A \textit{distância euclidiana} entre esses dois vetores é
dada por $\dist(x,y) = \left({\displaystyle\sum_{i=1}^{n}{(x_i - y_i)^2}}\right)^{{1/2}}$.

\subsection{}
Um grafo $G^c$ é o \textit{grafo complementar} de um grafo $G$ se possui o mesmo conjunto de vértices de $G$ e $\{x,y\}$ é uma aresta em $G^c$ se e somente se $\{x,y\}$ não é uma aresta em $G$. Um grafo $G$ é dito \textit{autocomplementar} se é isomorfo ao seu complemento $G^c$ ($C^5$ é um exemplo de grafo autocomplementar).

\subsection{}
Sejam $G=(V,E)$ e $e=\{x,y\}\in E$. Definimos dois novos grafos:
\begin{enumerate}
  \item[(\textit{i})]$G-e=(V,E\setminus\{e\})$ é o grafo formado pelo mesmo conjunto de vértices de $G$ e pela remoção da aresta $e$.
  \item[(\textit{ii})]$G/e=(V',(E\setminus\{e\}) \cup E')$, onde $V' = (V\setminus\{x,y\}) \cup z$ e $E'$ é o conjunto de arestas $\{z,i\}$, para todo $i\in N_G(x)\cup N_G(y)$, onde $N_G(i)$ representa o conjunto de vizinhos do vértice $i$ no grafo $G$ (a Figura \ref{fig3-1} ajuda no entendimento da definição).

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=16cm]{fig3-1.eps}
  \caption{Exemplos dos grafos $G-e$ e $G/e$ obtidos a partir de um dado grafo $G$.}
  \label{fig3-1}
  \end{center}
\end{figure}

\end{enumerate}


\subsection{}
(Ajuda para solução da questão \ref{ex:1}-6) O grafo de Mycielski--Grötzsch (veja Figura \ref{fig3-2}) é um grafo $G$ livre de triângulos tal que $\chi(G)=4$. Ademais, é o menor grafo livre de triângulos tal que seu número cromático é maior que três. Generalize o grafo de Mycielski--Grötzsch para obter um grafo com número cromático $k$ livre de triângulos. 


\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=16cm]{fig3-2.eps}
  \caption{Grafo de Mycielski--Grötzsch.}
  \label{fig3-2}
  \end{center}
\end{figure}

\subsection{}
(Ajuda para solução da questão \ref{ex:2}-3) Mostre que $P_G(\lambda) = P_{G-e}(\lambda) - P_{G/e}(\lambda)$. Feito isso, basta aplicar a igualdade recursivamente.


\subsection{Problemas e exercícios}
\label{sec:probs+exx+3}
Todos estão convidados a trabalhar nos seguintes problemas, e\-xer\-cí\-cios e
observações. 

\begin{enumerate}
\item[1.](Exercício \ref{ex:1}-6 revisitado)
\begin{enumerate}
  \item[(\textit{i})]Encontre um grafo $G$ com $\chi(G)\geq 2009$ que não contém triângulos nem circuitos de comprimento quatro e cinco ($C^3$, $C^4$ e $C^5$).
  \item[(\textit{ii})]Mostre que para todos $K$,$L$ inteiros, existe um grafo $G$ com $\chi(G)\geq K$ tal que $G$ não contém circuitos de comprimento $l$ para $l=3,\ldots,L$.
\end{enumerate}
 
\item[2.]O exercício \ref{ex:1}-7 fala sobre cotas para $\chi(G)$, onde $G=(\bbr^2,E)$ com $E=\big\{\{x,y\}\: x,\,y\in\bbr^2\text{ e }
  \dist(x,y)=1\big\}$. Mostre que $4\leq\chi(G)\leq 7$.

\item[3.]Seja $G=(\bbr^n,E)$ onde $E=\big\{\{x,y\}\: x,\,y\in\bbr^n\text{ e }  \dist(x,y)=1\big\}$. Quão rapidamente cresce $\chi(G)$ quando
$n$ tende a infinito?

\item[4.]Seja $G=(\bbr^n,E)$ como definido no exercício anterior.

\begin{enumerate}
  \item[(\textit{i})] Mostre que $\chi(G)\leq f(n)$, para alguma função $f(n)$.
  \item[(\textit{ii})] Sabemos que $\chi(G)\geq n+2$. É verdade que $\chi(G)/n\geq2009$ para todo $n$ suficientemente grande?
\end{enumerate}



\item[5.]Seja $G$ um grafo com $n$ vértices. Calcule o valor do polinômio cromático $P_G(\lambda)$ quando $G$ é um dos seguintes grafos: 

\begin{enumerate}
  \item[(\textit{i})] Árvore.
  \item[(\textit{ii})] Circuito.
  \item[(\textit{iii})] Grafo completo.
  \item[(\textit{iv})] Grafo vazio (isto é, sem arestas).
\end{enumerate}

\item[6.]Seja $G$ um grafo com $n$ vértices. Determine o grau e o coeficiente líder (coeficiente do monômio de grau mais alto) do polinômio cromático $P_G(\lambda)$ de $G$.

\item[7.]Professor Néscio descobriu um grafo autocomplementar com 2009 vértices e número cromático 44. Ele achou isto um tanto contraditório.  Explique por que Professor Néscio está certo em desconfiar de sua descoberta.




\end{enumerate}

















\newpage
\section{Grafos e número cromático - Continuação}
\label{sec:grafos-e-numero-cont}
\begin{center}
 23/6/2009
\end{center}



\subsection{Problemas e exercícios}
\label{sec:probs+exx+4}
Todos estão convidados a trabalhar nos seguintes problemas, e\-xer\-cí\-cios e
observações. 

\begin{enumerate}
\item[1.]Mostre que todo grafo conexo com $n$ vértices, $m$ arestas e circuito mínimo de comprimento (número de arestas) $g$ 
satisfaz $$m \leq \frac{g}{g-2}(n-2).$$

\item[2.]Mostre que um grafo é bipartido se e somente se todos os seus circuitos têm comprimento par. Conclua que um grafo bipartido planar com $n$ vértices tem no máximo $2n-4$ arestas, logo $K_{3,3}$ não é planar.

\item[3.]Mostre que um grafo planar que não possui triângulos (isto é, circuitos de comprimento três) é 4-colorível. (Na verdade, é possível mostrar com argumentos mais complicados que tal grafo é 3-colorível.)

\item[4.]Decida se os seguintes grafos, dados por seus conjuntos de vértices $V$ e arestas $E$ são planares ou não. Justifique a sua resposta.
\begin{enumerate}
  \item[(\textit{i})]$V=\{1,2,3,4,5,6,7,8\}$,\\ $E=\{12,13,14,15,18,23,26,27,34,35,45,46,47,48,57,68,78\}$.
  \item[(\textit{ii})]Grafo de Petersen\\ $V=\{A,B,C,D,E,a,b,c,d,e\}$,\\ $E=\{Aa,Bb,Cc,Dd,Ee,AB,BC,CD,DE,EA,ac,ad,bd,be,ce\}$.
  \item[(\textit{iii})]$V=\{1,2,3,4,5,6,7,8\}$,\\ $E=\{12,13,14,15,23,26,27,34,36,37,48,58,56,67,66,78\}$.
\end{enumerate}

\item[5.]O \emph{$n$-cubo} $C^n$, ou cubo de dimensão $n$, é o grafo de dimensão cujo conjunto de vértices é $V=\{0,1\}^n$ (o conjunto de vetores binários de dimensão $n$) tais que dois vértices são adjacentes se e somente se eles diferem em uma única coordenada. Por exemplo, os vértices adjacentes a $(0,\ldots,0)$ são todos os vetores com uma única coordenada igual a 1. Decida pela não-planaridade ou planaridade de $C^n$ para cada inteiro positivo $n$. 

\item[6.]Mostre que os grafos não-planares $K_5$, $K_6$, $K_7$ e $K_{3,3}$ são imersíveis no toro.

\item[7.]Dados um grafo $G=(V,E)$ e conjunto $\ell(v)$ associados a cada vértice $v \in V$, uma \emph{coloração de listas} de $G$ utilizando as listas $(\ell(v))_{v \in V}$ é uma função $f: V \rightarrow \bigcup_v \ell(v)$ que leva cada vértice $v$ a um elemento de $\ell(v)$ de tal forma que vértices adjacentes têm imagens distintas. O \emph{número de escolha} $ch(G)$ de $G$ é o menor inteiro positivo $k$ tal que, para quaisquer listas de tamanho $k$ associadas aos vértices, o grafo é colorível por estas listas. Prove que a diferença entre $ch(G)$ e $\chi(G)$ pode ser arbitrariamente grande.  


\end{enumerate}
 












\newpage
\section{Teoria de Ramsey}
\label{sec:ramsey}
\begin{center}
 18/8/2009
\end{center}

%Colocar introdução básica sobre teoria de Ramsey.
A seguir apresentamos a teoria de Ramsey de diversas maneiras diferentes, através de alguns exemplos. De forma simples, podemos dizer que a teoria de Ramsey estuda as estruturas combinatórias em que é impossível não existir uma certa \textit{ordem}.\\

\subsection*{Exemplo 1}

\subsection{}
 \textit{Conjunto convexo} é um conjunto de pontos onde para quaisquer dois  pontos $A$ e $B$ no conjunto, o segmento de reta que liga $A$ a $B$ está contido no conjunto.

\subsection{}
O \textit{fecho convexo} de um conjunto de pontos no plano é o menor conjunto convexo que contém todos os pontos do conjunto.

\begin{teorema}
Dados quaisquer cinco pontos no plano, três a três não colineares, existem quatro pontos que são vértices de um quadrilátero convexo (neste caso, dizemos que $5\to 4$).
\end{teorema}
Observe que $4\nrightarrow 4$ e $3\to 3$.



\begin{proof}
Seja $X$ o conjunto dos cinco pontos no plano e $F(X)$ o fecho convexo de $X$. Se quatro ou cinco elementos de $X$ são vértices de $F(X)$, não há o que fazer. Portanto, suponha que apenas três pontos são vértices de $F(X)$. Dessa forma, se traçarmos um segmento de reta $r$ entre os dois pontos internos de $F(X)$, temos um quadrilátero convexo tendo como vértices tais pontos internos e dois dos vértices de $F(X)$.
\end{proof}\ \\

\subsection*{Exemplo 2}
\begin{teorema}[Erd\H os--Szekeres '35 \cite{ErSz35}]
Uma sequência de $n^2 + 1$ números contém uma subsequência crescente\footnote{$x_{k_1}\leq x_{k_2}\leq\ldots\leq x_{k_{n+1}}$} de $n+1$ elementos ou uma subsequência decrescente\footnote{$x_{j_1}> x_{j_2}>\ldots> x_{j_{n+1}}$} de $n+1$ elementos (neste caso, dizemos que $n^2 + 1\to n+1$).
\end{teorema}
Observe que $n^2\nrightarrow n+1$.

\begin{proof}
Seja $x_1,\ x_2,\ldots, x_{n^2 + 1}$ a sequência com os $n^2 + 1$ números. Defina $c_i$ ($d_i$) a quantidade máxima de elementos em uma subsequência crescente (decrescente) terminada em $x_i$. Suponha, por contradição, que $c_i,d_i\leq n$ para todo $1\leq i\leq n^2+1$. Então, há um total de $n \times n=n^2$ pares $(c_i,d_i)$ possíveis. Pelo princípio da casa dos pombos, há $i<j$ com $(c_i,d_i)=(c_j,d_j)$, uma vez que a sequência contém $n^2 + 1$ pontos.
Se $x_i\leq x_j$ então existe uma subsequência crescente com $c_j$ termos terminada em $x_i$, mas essa subsequência juntamente com $x_j$ forma uma subsequência crescente com $c_j + 1$ termos, uma contradição.
Se $x_i> x_j$ então existe uma subsequência decrescente com $d_j$ termos terminada em $x_i$, mas essa subsequência juntamente com $x_j$ forma uma subsequência decrescente com $d_j + 1$ termos, uma contradição.
\end{proof}\ \\

\subsection*{Exemplo 3}

\subsection{}
Dizemos agora que $n\to (r,s)$ se para qualquer coloração de arestas de um grafo completo com $n$ vértices e duas cores (digamos, azul e vermelho), existe um subgrafo completo com $r$ vértices onde todas as arestas são vermelhas ou um subgrafo completo com $s$ vértices onde todas as arestas são azuis.

\subsection{}
Denotamos $\min\{n \colon\ n\to(r,s)\}$ por $R(r,s)$. Observe que ao invés de $\min$, deveríamos utilizar $\inf$, uma vez que , a princípio,
o conjunto em questão poderia ser vazio (no Teorema \ref{Ra30} vemos que tal conjunto não é vazio).


\begin{teorema}[Ramsey '30 \cite{Ra30}]\label{Ra30}
Para todo $r,s\geq 2$, existe $n$ tal que $n\to(r,s)$. Ademais, $R(s,t)\leq R(s-1,t)+R(s,t-1)$.
\end{teorema}
Um exemplo clássico é o caso $6\to (3,3)$, isto é, para qualquer coloração com duas cores de um grafo completo com seis vértices, temos um
triângulo monocromático. Outra forma de pensar é que em um grupo de seis pessoas sempre existem três pessoas que se conhecem mutuamente ou
três que não se conhecem mutuamente.


\begin{proof}
Claramente, $R(r,s)=1$ se $r=1$ ou $s=1$. Provamos o resultado por indução em $r+s$. Supomos $r,s>1$. Seja $n=R(r-1,s) + R(r,s-1)$ e
considere uma coloração $\chi \colon E(K^n)\to \{vermelho,azul\}$ das arestas de $K^n$. Fixe $v\in V(K^n)$. \\
$X = \{ x \in V(K^n)\setminus\{ v \}\colon \{v, x\} $ é vermelho$\}$\\
$Y = \{ y \in V(K^n)\setminus\{ v \}\colon \{v, y\} $ é azul$\}$.

Se $|X|\geq R(r-1,s)$, então, por hipótese de indução, encontramos um $K^{r-1}$ vermelho ou um $K^s$ azul. No caso de encontrar um $K^s$
azul, não há o que fazer. Mas então o $K^{r-1}$ vermelho em $X$ juntamente com o vértice $v$ formam um $K^r$ vermelho, como queríamos.
Analogamente, se $|Y|\geq R(r,s-1)$ estamos feitos. Pela escolha de $n$, temos $|X|\geq R(s-1,t)$ ou $|Y|\geq R(s,t-1)$.
\end{proof}

Segue do teorema acima que $R(r,s)\leq{{r+s-2}\choose{r-1}}$ (exercício: verifique!). Particularmente, $R(r,r)\leq{{2r-2}\choose{r-1}}\leq
4^r$. Outro fato conhecido é que $R(r)=R(r,r)>2^{\lfloor\frac{r}{2}\rfloor}\approx{\sqrt{2}}^r$, para $r\geq3$.
Desses dois fatos, vemos que seria interessante conhecer o valor de $\displaystyle\lim_{r\to\infty}{\sqrt[r]{R(r)}}$, porém não sabe-se nem
mesmo se tal limite existe.


Uma tabela atualizada com os valores conhecidos e limites inferiores e superiores para vários números de Ramsey pode ser vista no
\textit{survey} "Small Ramsey Numbers"\ de Radziszowski em \begin{verbatim}
http://www.combinatorics.org/Surveys/ds1/sur.pdf .\end{verbatim}

\subsection*{Exemplo 4}
\begin{teorema}[Schur '16 \cite{Sc16}]
Se colorirmos $\mathbb{N}^*$ com $k$ cores, há uma solução monocromática de $x+y=z$, isto é, solução onde $x$, $y$ e $z$ possuem as mesmas
cores.
\end{teorema}

\begin{proof}
Seja $n$ tal que $n\to \underbrace{(3,3,\ldots,3)}_{k\ vezes}$ (veja exercício \ref{sec:probs+exx+5}.4) e
$c\colon\mathbb{N}^*\to\{1,\ldots,k\}$ uma coloração de $\mathbb{N}^*$.
Seja $K_n$ o grafo completo com $n$ vértices colorido com $k$ cores, de modo que os vértices são rotulados de $1$ a $n$ e uma aresta
$\{i,j\}$, $i<j$ recebe a cor $c(j-i)$. Pela escolha de $n$, existe um triângulo monocromático formado por $i$, $j$ e $k$, com $i<j<k$.
Desta forma, basta fazer $x=j-i$, $y=k-j$ e $z=k-i$.
\end{proof}

\subsection{Problemas e exercícios}
\label{sec:probs+exx+5}
Todos estão convidados a trabalhar nos seguintes problemas, e\-xer\-cí\-cios e
observações. 

\begin{enumerate}
\item[1.]Dado $n\in \mathbb{N}$, existe $N\in \mathbb{N}$ tal que dados quaisquer $N$ pontos no plano, três a três não colineares, existem
$n$ pontos que são vértices de um polígono convexo com $n$ vértices (Se sim, dizemos que $N\to n$)?
  \begin{enumerate}
      \item[(\textit{i})]Como visto anteriormente, quando $n=4$, basta fazer $N=5$.
      \item[(\textit{ii})]Mostre que $8\nrightarrow 5$ e $9\to 5$.
  \end{enumerate}

\item[2.]Mostre que as seguintes afirmações são válidas para todo $a,b\geq 1$, onde $x\to (y,z)$ diz que qualquer sequência com $x$ números
contém uma subsequência crescente com $y$ números ou uma subsequência decrescente com $z$ números.
  \begin{enumerate}
      \item[(\textit{i})]$ab+1\to(a+1, b+1)$.
      \item[(\textit{ii})]$ab\nrightarrow(a+1, b+1)$.
  \end{enumerate}

\item[3.]Mostre que $R(r,s)\leq{{r+s-2}\choose{r-1}}$ (Dica: prove utilizando indução).

\item[4.](Generalização de Ramsey) Mostre que para todo $k\geq 2$ existe $n$ tal que $n\to \underbrace{(3,3,\ldots,3)}_{k\ vezes}$ ($K_n$
possui um triângulo monocromático).

\item[5.]Investigue se $x+y=3z$ tem a \textit{"propriedade de Schur"}\footnote{A motivação para utilizar o termo "propriedade de Schur"\ é
clara, porém, na literatura esta propriedade é conhecida como "propriedade da particao regular".}, isto é, para qualquer $k$, dada uma
coloração $c\colon\mathbb{N}^*\to\{1,\ldots,k\}$, existe solução monocromática para $x+y=3z$.

\item[6.]Investigue se $x+y=2z$, com $x\neq y$, tem a propriedade de Schur (Observe que, nesse caso, $x$, $z$, $y$ é uma progressão
aritmética).

\end{enumerate}









\newpage
\section{Teoria de Ramsey - Continuação}
\label{sec:ramsey-cont}
\begin{center}
 25/8/2009
\end{center}


\subsection*{Jogo da velha}

\subsection{}
O \textit{jogo $3^2$}, também conhecido como jogo da velha, é um jogo para duas pessoas que consiste em um quadrado particionado em $3\times
3$ quadrados menores, onde cada jogador marca um quadrado por vez e o vencedor é o jogador que conseguir marcar uma linha primeiro que o
outro.
Neste jogo não existe \textit{estratégia vencedora} (sequência de jogadas onde a vitória sempre é alcançada) para o primeiro jogador e
sempre existe uma estratégia em que o segundo jogador pode garantir o empate.

\subsection{}
Generalizações do jogo da velha para dimensões maiores são bem interessantes. Temos, por exemplo, o jogo $3^3$, onde o \textit{tabuleiro} é
o hipercubo tridimensional de lado três, onde qualquer linha do hipercubo garante a vitória. Neste caso, o primeiro jogador possui uma
estratégia vencedora.
Outra generalização bastante conhecida é o jogo $4^3$, em que o tabuleiro é o hipercubo tridimensional de lado quatro. Dadas essas
generalizações, fica claro o que vem a ser o jogo $k^d$.

\subsection{}
Defina $f(k)=\inf\{d\colon$primeiro jogador ganha $k^d\}$. Por exemplo, $f(3)=3$.

\subsection*{Números em Teoria de Ramsey}

\subsection{}
Lembre-se que $\sqrt{2}^s=2^{s/2}<R(s)\leq{{2s-2}\choose{s-1}}\leq 2^{2s-2}\leq4^s$ (onde para a primeira desigualdade,
  supomos que $s\geq3$). Portanto existe um "gap"\ bem grande entre os limites inferior e o superior para $R(s)$.
Tal limite inferior foi dado por Erd\H os \cite{Er47}, através de uma prova não-construtiva, utilizando o que hoje é conhecido como método
probabilístico. Vale ressaltar que até hoje não se conhece nenhum limite substancialmente melhor que o obtido por Erd\H{o}s.

\begin{teorema}[Erd\H os '47 \cite{Er47}]
Para $s\geq 3$, temos que $R(s)>2^{s/2}$.
\end{teorema}

\begin{proof}
Fixe $n=\lfloor2^{s/2}\rfloor$ e considere $K^n$. Pinte cada aresta do $K^n$ com azul ou vermelho, jogando uma moeda honesta para decidir
(isto é equivalente a dizer
que damos uma coloração aleatória das arestas do $K^n$ utilizando duas cores, com todas as colorações equiprováveis).

Fixe um $K^s$ em $K^n$. A probabilidade deste $K^s$ ser monocromático é ${\left({1/2}\right)}^{{s\choose 2}-1}$ . Portanto, o número
esperado de $K^s$'s monocromáticos em $K^n$ é 
$$
\begin{aligned}
{n\choose s}{\left({1/2}\right)}^{{s\choose 2}-1}&\leq\frac{n^s}{s!}2^{\left(1-\frac{s^2-s}{2}\right)}\\
&\leq \frac{1}{s!}2^{\left({s/2}+1\right)}.\\
\end{aligned}
$$

Se $s=3$, é fácil ver que $\frac{2^{\left({s/2}+1\right)}}{s!} < 1$. Se $s\geq 4$, então $\frac{2^{\left({s/2}+1\right)}}{s!} <
\frac{2^{\left({s/2}+1\right)}}{2^{s-1}} = \frac{1}{2^{\left(\frac{s-4}{2}\right)}}\leq 1 $. Portanto, o número esperado de $K^s$'s
monocromáticos em $K^n$ é menor que um. Segue que existe uma coloração de $K^n$ sem $K^s$ monocromático. Isto mostra que
$n=\lfloor2^{s/2}\rfloor\nrightarrow(s,s)$, ou seja, $R(s)>2^{s/2}$.
\end{proof}


\subsection{Problemas e exercícios}
\label{sec:probs+exx+6}
Todos estão convidados a trabalhar nos seguintes problemas, e\-xer\-cí\-cios e
observações. 

\begin{enumerate}
\item[1.]Prove que no jogo $k^d$, ou existe estratégia vencedora para o primeiro jogador, ou existe uma estratégia para o segundo jogador
que consegue garantir o empate.
\item[2.]Prove que, para $k=2,3,\ldots$, existe $d$ tal que o primeiro jogador possui uma estratégia vencedora em $k^d$. Em outras palavras,
prove que $f(k)<\infty$ para qualquer $k\geq 2$.
\item[3.]Mostre que $\left.\displaystyle f(5)<2^{2^{.{^{.{^{.^2}}}}}}\right\}2009$.
\item[4.]Prove que $R(s)>10^6 s$ se $s\geq 10^6$. Procure fazer isso com uma construção explícita.
\item[5.]Prove que $\displaystyle\lim_{s\to\infty}{\frac{R(s)}{2^{\lfloor{s/2}\rfloor}}} = \infty$ e
$\displaystyle\lim_{s\to\infty}{\frac{R(s)}{{{2s-2}\choose{s-1}}}} = 0$.
 
\end{enumerate}





















\newpage
\section{Teoria de Ramsey - Continuação}
\label{sec:ramsey-cont-2}
\begin{center}
 1/9/2009
\end{center}



\subsection{}
Um \textit{hipergrafo $l$-uniforme} (ou \textit{$l$-grafo}) é um par $(V,E)$ tal que $E\subset {{V}\choose{l}} = \{U\subset V\colon \lvert
U\rvert = l\}$.
\subsubsection*{Observação} Um grafo é um $2$-grafo.


\subsection{}
O \textit{$l$-grafo completo de ordem~$n$}, denotado~$K_{n}^{(l)}$, é o
$l$-grafo contendo $n$ vértices e ${n\choose l}$ hiperarestas (ou,
simplesmente, arestas).

\subsection{}
$K_{n}^{(l)} \to \left(K_{s_1}^{(l)},\ldots,K_{s_r}^{(l)}\right)$ significa que se colorimos as hiperarestas de $K_{n}^{(l)}$ com cores
$1,\ldots,r$, então, necessariamente, existe um $K_{s_i}^{(l)}$ colorido monocromaticamente com a cor $i$, para algum $i$.



\begin{teorema}[Teorema de Ramsey (versão generalizada)]\label{Ram-Gen}
Para todo $s_1, \ldots, s_r$, existe $n$ tal que 
\begin{equation}\label{eq:ram-gen}
K_{n}^{(l)} \to \left(K_{s_1}^{(l)},\ldots,K_{s_r}^{(l)}\right).
\end{equation}
\end{teorema}

\subsection{}
Denotamos por $R^{l}(s_1,\ldots,s_r)$ o menor $n$ para o qual vale (\ref{eq:ram-gen}).
 
\noindent\textit{Demonstração}. (Dica)
Para provar o teorema basta usar indução (dupla) e observar que $R^{(l)}(s_1,\ldots,s_r)\leq 1 + R^{(l-1)}(R_1,\ldots,R_r)$, onde
$$
\begin{aligned}
R_1 &= R^{(l)}(s_1-1,s_2,\ldots,s_r)\\
R_2 &= R^{(l)}(s_1,s_2-1,\ldots,s_r)\\
&\vdots\\
R_r &= R^{(l)}(s_1,s_2,\ldots,s_r-1).
\end{aligned}
$$


\subsection{}
Já vimos os seguintes casos do Teorema \ref{Ram-Gen}:
\begin{itemize}
\item $r=2$, $l=2$ (veja o Teorema \ref{Ra30} da Seção \ref{sec:ramsey}).
\item $r$ arbitrário, $l=2$, $s_i = 3$ para todo $i$ (veja o exercício \ref{sec:probs+exx+5}.4 da Seção \ref{sec:ramsey}).
\end{itemize}


\subsection{Teoria de Ramsey euclidiana}

\subsection{}
$\chi(\mathbb{R}^2)$ é o menor $q$ tal que existe uma $q$-coloração dos pontos de $\mathbb{R}^2$ onde não existem pontos $x$,$y\in\mathbb{R}^2$ com mesma cor e $\dist(x,y)=1$.


\subsection{}
Note que $\mathbb{R}^2\to (\{0,1\})_{\chi_2 - 1}$. Isto é, se colorimos $\mathbb{R}^2$ com $\chi_{2} - 1$ cores, então existe a con\-fi\-gu\-ra\-ção $\{0,1\}$ monocromática; mais precisamente, existe uma configuração monocromática congruente a $\{0,1\}$.


Mais geralmente, estamos interessados na relação $\mathbb{R}^n \to (K)_r$, com a qual queremos dizer que, para qualquer coloração de
$\mathbb{R}^n$ com $r$ cores, existe $K'\subset\mathbb{R}^n$ congruente a $K$ com $K'$ monocromático.

\subsection{}
Dizemos que $K\subset\mathbb{R}^k$ é um \textit{conjunto de Ramsey} se, para todo $r$, existe $n$ tal que $\mathbb{R}^n \to (K)_r$. 
Ex.: $K=\{0,1\}$ é um conjunto de Ramsey. De fato, fixado $r$, vemos que há $r+1$ pontos dois-a-dois à distância~$1$ em $\mathbb{R}^r$.  Logo, $\mathbb{R}^r\to \{0,1\}$. 







\subsection{Problemas e exercícios}

\label{sec:probs+exx+7}
Todos estão convidados a trabalhar nos seguintes problemas, e\-xer\-cí\-cios e
observações. 

\begin{enumerate}

\item[1.]Para resolver o "Problema de Klein"\ (exercício \ref{sec:probs+exx+5}.1), podemos usar a versão generalizada do Teorema de Ramsey e um pouco de geometria. Abaixo temos duas possibilidades.
\begin{itemize}
\item[(\textit{i})]Use que $5\to 4$ (aplique o Teorema de Ramsey com $l=4$).
\item[(\textit{ii})]Dada uma tripla~$(A,B,C)$ de pontos não colineares no plano, podemos distinguir dois casos. Ou a tripla é anti-horária, ou é horária (veja a Figura \ref{fig7-2}). Use esta observação e o Teorema de Ramsey para $l=3$.
\end{itemize}
\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=16cm]{fig7-2.eps}
  \caption{Triplas anti-horária e horária.}
  \label{fig7-2}
  \end{center}
\end{figure}

\item[2.] Prove que o conjunto $K=\{-1,0,1\}$ não é um conjunto de Ramsey.
\item[3.] Prove que o conjunto dos vértices de um triângulo equilátero é um conjunto de Ramsey.
\item[4.] Prove que o conjunto dos vértices do triângulo pitagórico de lados 3, 4, e 5 é um conjunto de Ramsey.
\item[5.] Prove que o conjunto dos vértices do triângulo de lados 2, 2, e 1 é um conjunto de Ramsey.
\end{enumerate}









\newpage
\section{Teoria de Ramsey euclidiana - Continuação}
\label{sec:ramseyEucl-cont}
\begin{center}
 8/9/2009
\end{center}


\begin{teorema}[Teorema da Compacidade]\label{teo:comp}
Seja $K\subset \mathbb{R}^k$ uma configuração finita de pontos tal que $\mathbb{R}^n\to(K)_r$. Então existe $L\subset \mathbb{R}^n$ finito
tal que $L\to(K)_ r$.
\end{teorema}

\subsubsection*{Observação} Podemos usar o Teorema de Tikhonov (o produto de espaços topológicos compactos é compacto) para provar o teorema acima.
Provaremos a seguinte versão mais elementar do Teorema~\ref{teo:comp}.

\begin{teorema}\label{teo:comp-ele}
Seja $K\subset \mathbb{R}^k$ uma configuração finita de pontos tal que $\mathbb{Q}^n\to(K)_r$. Então {exis\-te}~$L~\subset~\mathbb{Q}^n$
finito tal que $L\to(K)_ r$.
\end{teorema}

\begin{proof}
Usamos o Lema de König (Lema \ref{konig36}) para mostrar o resultado. Suponha que para todo $L\subset\mathbb{Q}^n$ finito, $L\nrightarrow(K)_r$. Precisamos mostrar que $\mathbb{Q}^n\nrightarrow(K)_r$.
Considere $q_1,q_2,\ldots$ uma enumeração de $\mathbb{Q}^n$ e, para todo $m\geq1$, seja $L_m = \{q_1,\ldots,q_m\}$. Fixe uma $r$-coloração $\chi_m\colon L_m\to[r]$ de $L_m$ que prova que $L_m\nrightarrow(K)_r$. Queremos ``colar''\ essas (ou parte dessas) infinitas colorações para obter uma $r$-coloração de $\mathbb{Q}^n$ que prova que $\mathbb{Q}^n\nrightarrow(K)_r$. Consideremos as sequências 
\begin{eqnarray*}
L_1 &\colon& \chi_1(q_1)\\
L_2 &\colon& \chi_2(q_1), \chi_2(q_2)\\
&\vdots \\
L_m &\colon& \chi_m(q_1), \ldots , \chi_m(q_m)\\
&\vdots
\end{eqnarray*}

Consideremos a árvore infinita associada às infinitas sequências acima. Mais precisamente, seja~$T_r$ a árvore enraizada infinita, em que
todos os nós têm $r$ filhos. Rotule as $r$ arestas que ligam os nós aos seus $r$ filhos de $1,\ldots,r$. Cada sequência da lista acima
define naturalmente um caminho da raiz de $T_r$ a um nó interno de $T_r$. Consideremos a árvore infinita $T$ dada pela união desses
infinitos caminhos. Observe que qualquer caminho infinito nessa árvore corresponde a uma coloração de $\mathbb{Q}^n$. Esta coloração prova
que~$\mathbb{Q}^n\nrightarrow~(K)_r$ [prove esta asserção como exercício!].
\end{proof}

Lembre que um conjunto finito $K\subset\mathbb{R}^k$ é dito ser de Ramsey se, para todo $r$, existe $n$ tal que~$\mathbb{R}^n\to(K)_r$.

\subsection{}
Se $x=(x_1,\ldots,x_k)^T\in\mathbb{R}^{k}$ e $y=(y_1,\ldots,y_l)^T\in\mathbb{R}^{l}$, então temos que $x*y\in\mathbb{R}^{k+l}$ é tal
que~$x~*~y~=~
(x_1,\ldots,x_k,y_1,\ldots,y_l)^T$. Ademais,
se $K\subset\bbr^k$ e $K'\subset\bbr^l$, então o produto $KK'$ é dado por $KK'~=~\{x*y\colon x\in K,\ y\in
K'\}$.

\subsubsection*{Exemplo}\label{ex:prod}Sejam $K=\{0,3\}\subset\mathbb{R}$ e $K'=\{0,4\}\subset\mathbb{R}$. Então, $K*K' =
\left\{{{0}\choose{0}},{{0}\choose{4}},{{3}\choose{0}},{{3}\choose{4}}\right\} \subset \mathbb{R}^2$.


\begin{teorema}[Teorema do Produto]\label{teo:prod}
Se $K_1\subset\mathbb{R}^{k_1}$ e $K_2\subset\mathbb{R}^{k_2}$ são conjunto de Ramsey finitos, então $K_1*K_2 = \{p_1*p_2\colon p_1\in K_1,\
p_2\in K_2\}$ é Ramsey.
\end{teorema}


\begin{proof}
 Fixe $r_1$. Como $K_1$ é Ramsey, existe $n_1$ tal que $\mathbb{R}^{n_1}\to(K_1)_{r_1}$ e, pelo Teorema \ref{teo:comp} (Teorema da
Compacidade), existe $L_1\subset\mathbb{R}^{n_1}$ finito tal que $L_1\to(K_1)_{r_1}$.
Seja $r_2 = {r_1}^{|L_1|}$. Como~$K_2$ é Ramsey, existe $n_2$ tal que $\mathbb{R}^{n_2}\to(K_2)_{r_2}$ e, pelo Teorema \ref{teo:comp},
existe $L_2\subset\mathbb{R}^{n_2}$ finito tal que $L_2\to(K_2)_{r_2}$.
Afirmamos que $L^* = L_1*L_2\subset \mathbb{R}^{n_1+n_2}$ é tal que $L^*\to (K_1*K_2)_{r_1}$ (Exercício: escreva a prova desta afirmação em
detalhes).
\end{proof}

\subsubsection*{Observação} Observe por \ref{ex:prod} e pelo Teorema~\ref{teo:prod} que resolvemos o exercício \ref{sec:probs+exx+7}.4.

\subsection{}
Nos Teoremas  \ref{teo:comp}, \ref{teo:comp-ele} e \ref{teo:prod}, impusemos a hipótese de que as configurações de Ramsey que estão sendo
consideradas são finitas. Ocorre que, na verdade, \textit{toda configuração de Ramsey} é finita. Este é um ótimo exercício para os
interessados.

\subsection{Problemas e exercícios}

\label{sec:probs+exx+8}
Todos estão convidados a trabalhar nos seguintes problemas, e\-xer\-cí\-cios e
observações. 

\begin{enumerate}
 \item[1.]Existem $x$, $y$, $z$ tal que o triângulo de vértices $(x,0,0)$, $(0,y,0)$, $(0,0,z)\in\bbr^3$ tem lados de comprimento $2$, $2$,
$1$?
 \item[2.]Existem $x$, $y$, $z$ tal que o triângulo de vértices $(x,0,0)$, $(0,y,0)$, $(0,0,z)\in\bbr^3$ tem lados de comprimento $a$, $b$,
$c$ arbitrários?
 \item[3.]Prove que o conjunto de vértices do triângulo de lados $\sqrt{2}$, $\sqrt{2}$, $\sqrt{6}$ é Ramsey.
 \item[4.]Neste exercício, voltamos a considerar o problema de Klein (exercício \ref{sec:probs+exx+5}.1). Para cada~$n$, seja~$N(n)$ o
menor~$N$ tal que $N\to n$. Prove que $N(n)\leq\min\{R^{(4)}(n,5),R^{(3)}(n,n)\}$. Estime estas cotas para $n=5$. Você consegue decidir
se~$N(5)\leq10^{10}$?
\subsubsection*{Observação} Um argumento um pouco mais geométrico pode ser usado para provar uma cota muito melhor do que as cotas no
exercício \ref{sec:probs+exx+8}.4. Conjectura-se que $N(n)=2^{n-2}+1$. Uma resenha muito interessante sobre esses problemas e resultados
pode ser visto em \cite{MoSo00}.
\end{enumerate}








\newpage
\section{Teoria de Ramsey euclidiana - Continuação\\
	 Teoria extremal dos conjuntos}
\label{sec:extremal}
\begin{center}
 15/9/2009
\end{center}

\subsection{}
Um conjunto $K\subset\bbr^k$ é \textit{esférico} se existem $d$, $r$, e $K'$ tais que $K$ é congruente a $K'$ e $K'$ está contido na esfera
$d$-dimensional de raio $r$ em $\bbr^{d+1}$:

$$K'\subset S^d(r) = \{X\in \mathbb{R}^{d+1}: \|X\|=r\}.$$


\begin{teorema}\label{naoram}
A configuração $K=\{-1,0,1\}$ não é Ramsey.
\end{teorema}

\begin{teorema}[Erd\H{o}s, Graham, Montgomery, Rothschild, Spencer e Straus '73 \cite{ErGrMoRoSpSt73}]\label{teo:esf}
Toda configuração Ramsey é esférica.
\end{teorema}

\subsubsection*{Observação} A teoria de Ramsey euclidiana foi iniciada pelos autores do Teorema \ref{teo:esf}. Aquele resultado aparece no
primeiro artigo de uma série de três (\cite{ErGrMoRoSpSt73}, \cite{ErGrMoRoSpSt75} e \cite{ErGrMoRoSpSt75-2}), que fundou
a área.

Dentre as conjecturas existentes na teoria de Ramsey euclidiana, a Conjectura \ref{conjgra}, a seguir, é, possivelmente, a mais
importante.

\begin{conjectura}[Graham '94 \cite{Gr94}]\label{conjgra}
Toda configuração esférica finita $K\subset\mathbb{R}^k$ é Ramsey.
\end{conjectura}

Seguindo a tradição de Erd\H{o}s, Ron Graham oferece US\$ 1000 pela solução de sua conjectura.

Uma conjectura mais fraca que a Conjectura \ref{conjgra} é a Conjectura \ref{conjgra-fraca}.

\begin{conjectura}\label{conjgra-fraca}
Quaisquer $4$ pontos de um círculo formam uma configuração Ramsey.
\end{conjectura}

\begin{teorema}[Frankl--R\"odl \cite{FrRo90}]
Toda configuração de $4$ pontos não-coplanares em $\mathbb{R}^3$ é Ramsey.
\end{teorema}

Na verdade, Frankl e Rödl \cite{FrRo90} provaram que quaisquer $d+1$ pontos em posição geral em $\mathbb{R}^d$ formam uma configuração
Ramsey.



Para saber mais sobre teoria de Ramsey euclidiana, inclusive provas para os Teoremas \ref{naoram}~e~\ref{teo:esf}, veja o livro
\textit{Tópicos em Combinatória Contemporânea} \cite{MoKo01}, que pode ser encontrado na página do pesquisador Carlos Gustavo Moreira:

\begin{verbatim}
  http://w3.impa.br/~gugu/coloyoshi.ps
\end{verbatim}

Outro bom material de estudo pode ser encontrado no endereço eletrônico do \textit{MSRI, Mathematical Sciences Research Institute}, 
\verb|http://www.msri.org|. Nesse endereço existe o vídeo de uma palestra de Ron Graham sobre teoria de Ramsey
euclidiana, juntamente com o arquivo dos transparências utilizadas na palestra.

Para uma discussao recente sobre problemas e resultados da área de teoria de Ramsey (incluindo teoria de Ramsey Euclidiana), veja Graham
\cite{Gr08}.

\subsection*{Teoria extremal dos conjuntos}

\subsection{}
Uma \textit{família intersectante} $\mathcal{F}$ é um sistema de conjuntos tal que $|F\cap F'|\neq\varnothing$ para quaisquer~$F$~e~$F'\in
\mathcal{F}$.

\subsection{}
Lembre que $\displaystyle{{[n]}\choose{r}}=\{X\subset [n]\colon |X|=r\}$.

\begin{fato}
Se $\mathcal{F}\subset2^{[n]}$ é uma família intersectante, então $|\mathcal{F}|\leq 2^{n-1}$.
\end{fato}

\subsection{}
Para todo $x\in [n]$, defina $\mathcal{F}_x=\{F\in{[n]\choose r}\colon x\in F\}$.

\begin{teorema}[Erd\H{o}s--Ko--Rado '61 \cite{ErdKoRado61}]\label{ErdosKoRado}
Se $n\geq 2r$ e $\mathcal{F}\subset{{[n]}\choose{r}}$ é uma família intersectante, então~$|\mathcal{F}|\leq
{n-1\choose r-1}$. Ademais, se $n>2r$ e $|\mathcal{F}|={n-1\choose r-1}$, então existe $x\in[n]$ tal que $\mathcal{F} = \mathcal{F}_x$.
\end{teorema}

\begin{proof}(Katona '72 \cite{Ka72})
 Consideramos ordenações cíclicas de $[n]$; formalmente, con\-si\-de\-ra\-mos bijeções $\phi\colon\mathbb{Z}_n\to[n]$. Dizemos que
$F\subset[n]$ e $\phi$ são compatíveis se os elementos de $F$ formam~um~``segmento'' em $\phi$. Por exemplo, se
$\phi\colon\mathbb{Z}_7\to[7]$ é tal que $\phi\colon 6,1,3,7,4,2,5$ (isto é, temos $\phi(0)=6$, $\phi(1)=1$, etc), então $F=\{1,3,6\}$ e
$F'=\{1,5,6\}$ são compatíveis com $\phi$.

Seja $\phi$ uma ordenação cíclica fixa de $[n]$. Afirmamos que o número de $F\in\mathcal{F}$ compatíveis com $\phi$ é no máximo~$r$: este é
um excelente exercício e deixamos para o leitor encontrar uma prova elegante para esse fato.

Vamos calcular o número de pares $(F,\phi)$ onde $F$ é um elemento de $\mathcal{F}$ e $\phi$ é uma ordenação
cíclica de $[n]$. Se $P$ é a quantidade de tais pares, então podemos calcular $P$ de duas maneiras distintas. Temos que
\begin{equation}\label{cont1}
\begin{aligned}
P&=\displaystyle\sum_\phi{(\text{quantidade de elementos de $\mathcal{F}$ compatíveis com $\phi$})}\\
&\leq n! r,
\end{aligned}
\end{equation}
onde o somatório é sobre todas as ordenações cíclicas de $[n]$.
Sabemos também que
\begin{equation}\label{cont2}
\begin{aligned}
P&=\displaystyle\sum_{F\in\mathcal{F}}{(\text{quantidade de ordenações cíclicas $\phi$ compatíveis com $F$})}\\
&=\displaystyle\sum_{F\in\mathcal{F}}{n r!(n-r)!}\\
&=|\mathcal{F}|n r!(n-r)!.
\end{aligned}
\end{equation}

Das equações (\ref{cont1}) e (\ref{cont2}), temos que 
$$
|\mathcal{F}|\leq\frac{n!r}{r!(n-r)!n} = \frac{(n-1)!}{(r-1)!(n-r)!} = {n-1\choose r-1}.
$$

Deixamos a prova do ``ademais'' como exercício.
\end{proof}

\begin{teorema}\label{teo:conj}
Seja $\mathcal{F}\subset2^{[n]}$ tal que todo $F\in\mathcal{F}$ tem cardinalidade ímpar e, para todo  $F$ e $F'\in\mathcal{F}$, temos
que $|F\cap F'|$ é
par. Então $|\mathcal{F}|\leq n$.
\end{teorema}

\begin{proof}
 Usamos álgebra linear sobre o corpo $\mathbb{F}_2=\{0,1\}$ dos inteiros módulo 2. Cada $F\in\mathcal{F}$ pode ser representado por 
$v^{(F)}=(v_i^{(F)})_{1\leq i\leq n}\in\mathbb{F}_2^n$ com 
$$
v_i^{(F)}=\left\{
\begin{array}{ll}
 0, & \textrm{se $i\notin F$,}\\
 1, & \textrm{se $i\in F$.}
\end{array} \right.
$$

Afirmamos que os vetores $v^{(F)}\ (F\in\mathcal{F})$ são linearmente independentes. Daí segue que
\begin{equation*}
\begin{aligned}
|\mathcal{F}| &=\text{quantidade de vetores $v^{(F)}$}\\
&\leq \text{dimensão de $\mathbb{F}_2^n$}\\
&=n.
\end{aligned}
\end{equation*}

Provaremos agora a afirmação que foi feita. Usaremos o produto interno $\langle \cdot, \cdot \rangle \colon \mathbb{F}_2^n \times
\mathbb{F}_2^n \to \mathbb{F}_2$ dado por $\langle x,y\rangle=\sum_{1\leq i\leq n}{x_iy_i}$ para todo $x=(x_i)$ e
$y=(y_i)\in\mathbb{F}_2^n$.
Suponha que~$\displaystyle\sum_{F\in\mathcal{F}}{\lambda_F v^{(F)}}~=~0$. Fixe $F_0\in\mathcal{F}$. Temos que
\begin{equation*}
  0=\langle v^{(F_0)},\displaystyle\sum_{F\in\mathcal{F}}{\lambda_F v^{(F)}}\rangle
\end{equation*}
\begin{equation*}
 \begin{aligned}
   &=\displaystyle\sum_{F\in\mathcal{F}}{\langle v^{(F_0)},\lambda_F v^{(F)}\rangle}\\
   &=\displaystyle\sum_{F\in\mathcal{F}}{\lambda_F\langle v^{(F_0)},v^{(F)}\rangle}\\
   &=\lambda_{F_0}|F_0\cap F|_{\bmod\ 2} =\lambda_{F_0}.
 \end{aligned}
\end{equation*}

Como $F_0$ foi escolhido arbitrariamente, concluímos a prova do teorema.
\end{proof}

\subsection{Problemas e exercícios}
\label{sec:probs+exx+9}
Todos estão convidados a trabalhar nos seguintes problemas, e\-xer\-cí\-cios e
observações. 

\begin{enumerate}

\item[1.]Seja $n\geq 2r$ e $\mathcal{F}\subset{{[n]}\choose{r}}$ uma família intersectante. Se $\phi$ é uma ordenação cíclica de $[n]$,
então prove que a quantidade de $F\in\mathcal{F}$ compatíveis com $\phi$ é no máximo~$r$.

\item[2.]Seja $\mathcal{F}\subset2^{[n]}$ tal que todo $F\in\mathcal{F}$ tem cardinalidade \textit{par} e $|F\cap F'|$ é
  \textit{par} para todo~$F$ e $F'\in\mathcal{F}$.
\begin{itemize}
\item[(\textit{i})]Encontre $\mathcal{F}$ como acima tal que  $|\mathcal{F}|$ é grande.
\item[(\textit{ii})]Obtenha em~(\textit{i}) um~$\mathcal{F}$ máximo: prove que
  não existe $\mathcal{F'}\subset2^{[n]}$ nas mesmas condições tal que
  $|\mathcal{F'}|>|\mathcal{F}|$.
\end{itemize}

\item[3.]Seja $\mathcal{F}\subset2^{[n]}$ tal que existe
  um~$\lambda>0$ tal que $|F\cap F'|=\lambda$ para todo $F$ e
  $F'\in\mathcal{F}$ com~$F\neq F'$.
\begin{itemize}
\item[(\textit{i})]Encontre $\mathcal{F}$ como acima tal que
  $|\mathcal{F}|$ é grande.
\item[(\textit{ii})]Obtenha em~(\textit{i}) um~$\mathcal{F}$ máximo: prove que
  não existe $\mathcal{F'}\subset2^{[n]}$ nas mesmas condições tal que
  $|\mathcal{F'}|>|\mathcal{F}|$.
\end{itemize}

\item[4.]Prove a asserção do ``ademais'' no Teorema \ref{ErdosKoRado} (Erd\H{o}s--Ko--Rado).

\item[5.]Seja $V$ o espaço dos vetores $(a_1,\ldots,a_n)^T$ onde os $a_i$ pertencem a um corpo $F$. Para os vetores
~$a~=(a_1,\ldots,a_n)^T$,
$b=(b_1,\ldots,b_n)^T$, defina seu produto interno por $a^Tb=a_1b_1+\ldots+a_nb_n$. Ademais, seja $M$ um subespaço de $V$ e $A$ uma
transformação linear de $V$ em $V$. Decida se as seguintes asserções são verdadeiras.
\item[(\textit{i})]Se $A$ é não-singular, então sua transposta $A^T$ também é não-singular.
\item[(\textit{ii})]Mais geralmente, se $A$ é não-singular, então $A^TA$ também é não-singular.
\item[(\textit{iii})]Ainda mais geralmente, $A^TA$ e $A$ têm o mesmo núcleo.
\item[(\textit{iv})]$M\cap M^\bot=\{0\}$ (onde $M^\bot$ é o subespaço ortogonal a $M$, isto é, $M^\bot=\{a\colon a^Tb=0$ para cada $b\in
M\}$).
\item[(\textit{v})]$\langle M\cup M^\bot\rangle = V$ ($\langle X\rangle$ denota o espaço gerado por $X$).
\item[(\textit{vi})]$\dim M+ \dim M^\bot = n$.
\item[(\textit{vii})]$(M^\bot)^\bot = M$.

\end{enumerate}









\newpage
\section{Teoria extremal dos conjuntos}
\label{sec:extremal}
\begin{center}
 22/9/2009
\end{center}

\subsection{}
Uma matriz real $B=(b_{ij})\in \mathbb{R}^{m\times m}$ é \textit{positiva semidefinida} se, para todo $x\in\mathbb{R}^m$, é verdade que
$x^TBx\geq
0$. Ademais, se $B$ é positiva semidefinida e $x^TBx=0$ implica que $x=0$, então $B$ é uma matriz \textit{positiva definida}.

\begin{fato}\label{fatoDef}
Se $A$ é uma matriz positiva definida e $B$ é uma matriz positiva semidefinida, então $A+B$ é uma matriz positiva definida.
\end{fato}


\begin{teorema}[Fisher não-uniforme \cite{Is59,Ma53}]\label{FisherNU}
Se $C_1,\ldots,C_m\subset [n]$ é um sistema de conjuntos tal que $1\leq\lambda\leq n$ e $|C_i\cap C_j|=\lambda$ para todo $i\neq j$, então
$m\leq n$.
\end{teorema}

\begin{proof}
Consideramos primeiramente o caso em que existe um $i$ tal que $|C_i|=\lambda$. Com isso, todo $C_j$ com $j\neq i$ deve conter $C_i$ e não
pode ter interseção fora de $C_i$. Assim, temos que o máximo de conjuntos possíveis é $n-\lambda+1\leq n$.

Suponha que não existe $i$ tal que $|C_i|=\lambda$. Seja $\gamma_i=|C_i|-\lambda>0$, para todo $i\in[n]$. Considere os vetores
característicos $x_i\in\mathbb{R}^{n}$ dos conjuntos $C_i$, isto é, $x_{ij}=1$ se $j\in C_i$ e $x_{ij}=0$ se $j\notin C_i$.

Seja $M=(M_{ij})\in\mathbb{R}^{m\times n}$, onde as linhas da matriz são os vetores característicos $x_i$ (assim, temos
que $M_{i,j}=x_{i,j}$).
Podemos escrever $A=MM^T=\lambda
J + C$, onde $J\in\mathbb{R}^{m\times m}$ é a matrix $m\times m$ com todas as entradas iguais a 1 e
$C~=~\diag(\gamma_1,\ldots,\gamma_m)$,
pois $\langle x_i,x_j\rangle = |C_i\cap C_j|$ e, quando $i\neq j$, temos $|C_i\cap C_j|=\lambda$  e, quando $i= j$, temos $|C_i\cap
C_j|=\lambda + \gamma_i$.

Afirmamos que posto($A$)$\geq m$. De fato, temos que
\begin{itemize}
\item[(\textit{i})] $\lambda J$ é positiva semidefinida, pois $y^T\lambda Jy =
\sum_{1\leq i\leq n}\sum_{1\leq j\leq n}{\lambda y_i y_j = \lambda(y_1+\ldots + y_n)^2}\geq 0$;
\item[(\textit{ii})] $C$ é positiva definida, pois $y^TCy=\sum_{1\leq i\leq n}\sum_{1\leq j\leq n}{\gamma_i y_i^2}>0$ e
$y^TCy=0$ somente se $y=0$.
\end{itemize}

Por $(i)$, $(ii)$ e pelo Fato \ref{fatoDef}, $A=MM^T$ é positiva definida. Portanto, posto($A$)$\geq m$; caso contrário, existiria um
$x\neq0$ tal que $Ax=0$ (uma combinação linear das colunas de $A$ teria valor~0). Mas então, $x^TAx=0$, o que contradiz o fato de $A$ ser
positiva definida.

Sabemos que posto($A$)$\leq n$; portanto, temos que $m\leq n$.
\end{proof}


\subsection{}
Dadas funções $f$ e $g$, dizemos que $f = \Omega(g)$ se existe $c>0$ e $x_0$ tal que $f(x)\geq c g(x)$ para todo $x\geq x_0$.

Existe uma construção \textit{explícita} para provar que $R_2(t)=R(t,t)\Omega(t^3)$ (veja o Teorema \ref{Nagy} a seguir).\newpage

\begin{teorema}[Nagy '72 \cite{Na72}]\label{Nagy}
${t\choose 3}\nrightarrow(t+1,t+1)$, isto é, $K^{t\choose 3}\nrightarrow(K^{t+1},K^{t+1})$.
\end{teorema}

\begin{proof}
Consideramos o grafo $K^{t \choose 3}$, cujos vértices são as triplas em $[t]$. Sejam $A,B\in{[t]\choose 3}$ dois vértices distintos de
$K^{t \choose 3}$. Colorimos a aresta $\{A,B\}$ com a cor vermelh1 se $|A\cap B|=1$ e com a cor azul de $|A\cap B|\neq 1$.

Notamos agora que $K^{t \choose 3}$ não contém um $K^{t+1}$ vermelho. De fato, basta aplicar o Teorema \ref{FisherNU} com $n=t$ e
$\lambda=1$. Ademais, $K^{t \choose
3}$ também não contém um $K^{t+1}$ azul pois, caso contrário, teríamos mais que $t$ conjuntos ímpares com interseções dois a dois pares, um
absurdo,
pois contradiz o que o Teorema \ref{teo:conj} estabelece.
\end{proof}

\section*{Teoremas de Frankl \& Wilson}

\begin{teorema}[Ray-Chaudhuri--Wilson não-uniforme; Deza--Frankl--Singhi '85]\label{teo:RCW}
Seja $p$ um primo, com~$L\subset~ \mathbb{Z}$, $|L|=s$ e $\mathcal{F}=\{A_1,\ldots,A_m\}\subset 2^{[n]}$ tal que
\begin{itemize}
\item[(\textit{i})]$|A_i|\notin L\ ({\bmod\  p})$ para todo $i$;
\item[(\textit{ii})]$|A_i\cap A_j|\in L\ ({\bmod\  p})$ para todo $i\neq j$.
\end{itemize}
Então $m\leq\displaystyle\sum_{j=0}^{s}{n \choose j}$.
\end{teorema}

\begin{proof}
A prova desse teorema pode ser vista em \cite{MoKo01}.
\end{proof}



\subsection{Problemas e exercícios}
\label{sec:probs+exx+10}
Todos estão convidados a trabalhar nos seguintes problemas, e\-xer\-cí\-cios e
observações. 

\begin{enumerate}

\item[1.]Prove que $K^{(t-1)^2}\nrightarrow (K^t,K^t)$ com uma coloração explícita.

\end{enumerate}






\newpage
\section{Teoria extremal dos conjuntos - continuação}
\label{sec:extremal}
\begin{center}
 29/9/2009
\end{center}

\subsection{}
Dados $\mathcal{F}=\{A_1,\ldots,A_m\}\subset 2^{[n]}$ e $L\subset \mathbb{Z}$ com $|L|=s$, dizemos que $\mathcal{F}$ é um sistema
de conjuntos $L$-\textit{intersectante} se $|A_i\cap A_j|\in L$ para todo $i\neq j$.
Uma versão modular para essa condição é a seguinte: $|A_i\cap A_j|\in~L~(\bmod\ {p})$ para todo $i\neq j$.

\subsection{}
Seja $m(n,k) = \max\{|\mathcal{F}|\colon \mathcal{F}\subset 2^{[n]}\ e \ $para todos $F$ e $F'\in\mathcal{F}$ distintos, $|F\cap F'|\neq
k\}$.

\begin{teorema}[Frankl \& Rödl '87 \cite{FrRo87}]\label{teo:FR87}
Existem $\varepsilon>0$ e $n_0$ tal que $m(n,\lfloor{n/4}\rfloor)\leq(2-\varepsilon)^n$ para todo~$n~\geq~n_0$.
\end{teorema}

O Teorema \ref{teo:FR87} resolveu um problema de U\$ 500 de Erd\H{o}s. Mais geralmente, temos o seguinte resultado.

\begin{teorema}[Frankl \& Rödl '87 \cite{FrRo87}]
Para todo $\delta>0$, existem $\varepsilon>0$ e $n_0$ tal que, para todo~${n\geq n_0}$, temos ${m(n,\lfloor{\delta
n}\rfloor)\leq(2-\varepsilon)^n}$.
\end{teorema}

\begin{corolario}[do Teorema \ref{teo:RCW}]\label{cor:rw}
Se $L\subset \mathbb{Z}$ com $|L|=s$ e $\mathcal{F}\subset{[n] \choose k}$ é $L$-intersectante,
então $$|\mathcal{F}|\leq\displaystyle\sum_{j=0}^{s}{n \choose j}.$$
\end{corolario}

\begin{proof}
Sem perda de generalidade, podemos supor $L\subset\{0,1,\ldots,k-1\}$. Claramente, basta tomar um primo $p>k$: fazendo isso, $\mathcal{F}$
satisfaz as hipóteses do Teorema \ref{teo:RCW} para este $p$ e o resultado segue.
\end{proof}

\begin{lema}\label{lema:cont}
Se $n\geq 2s$, então
$$\displaystyle\sum_{i=0}^{s}{n \choose i}< {n\choose s}\left(1+\frac{1}{n-2s+1}\right)\leq 2{n\choose s}.$$ 
\end{lema}

\begin{proof}
Temos que 
$${n\choose k-1}\left/{n\choose k}\right. = \frac{k!(n)_{k-1}}{(k-1)!(n)_k} = \frac{k}{n-k+1}\leq\frac{s}{n-s+1}\leq \frac{n/2}{n/2+1}<1.$$
Portanto,
$$
\begin{aligned}
\displaystyle\sum_{i=0}^{s}{n\choose i}&\leq {n\choose
s}\left(1+\frac{s}{n-s+1}+\left(\frac{s}{n-s+1}\right)^2+\ldots\right)\\
&={n \choose s}\frac{1}{1-s/(n-s+1)}\\
&={n\choose s}\left(1+\frac{1}{n-2s+1}\right).
\end{aligned}
$$
\end{proof}



\begin{corolario}[do Teorema \ref{teo:RCW}]\label{cor:RCW}
Seja $p$ um primo. Se $\mathcal{F}\subset {[4p-1]\choose 2p-1}$ é tal que $|F\cap F'|\neq p-1$ para todo $F$, $F'\in~\mathcal{F}$ com $F\neq
F'$, então
$$
\begin{aligned}
|\mathcal{F}|&\leq 2{4p-1\choose 2p-1}\\
&<1{,}7548^{4p-1}.
\end{aligned}
$$
\end{corolario}

\begin{proof}
Tome $L=\{0,\ldots,p-2\}$. Como $|F|=2p-1\equiv p-1\ (\bmod\ ~p)$ para todo~$F~\in~\mathcal{F}$, temos que $|F|\notin L\ ({\bmod\  p})$.
Sabemos também que para todo $F$, $F'\in\mathcal{F}$ com $F\neq F'$, temos que~$|F~\cap~F'|~\in~\{0,\ldots,2p-2\}\setminus\{p-1\}$.
Portanto, $|F\cap F'|\in L \ ({\bmod\  p})$ para todo $F$, $F'\in\mathcal{F}$ distintos. Pelo Teorema \ref{teo:RCW},
$$|\mathcal{F}|\leq\displaystyle\sum_{i=0}^{p-1}{n\choose i}.$$
Pelo Lema \ref{lema:cont},
$$|\mathcal{F}|<2{4p-1\choose 2p-1}.$$
Aplicando Stirling, temos, para todo $p$ suficientemente grande,
$$|\mathcal{F}|<1{,}7548^{4p-1}.$$
\end{proof}

\subsection{}
Seja $\chi_\ell(\mathbb{R}^n)$ o menor inteiro para o qual existe uma coloração de $\mathbb{R}^n$ tal que quaisquer
2 pontos $x,y\in\mathbb{R}^n$ com
$\dist(x,y)=~\ell$ têm cores diferentes.

\subsection{}
Quando $n=2$, temos $4\leq\chi(\mathbb{R}^n)\leq 7$.


\subsection{}
Seja $\alpha(\mathcal{G}_p) = \max\{|W|\colon W\subset V(\mathcal{G}_p)$ tal que existe aresta com suas duas extremidades em~$W\}$.\\



O Corolário \ref{cor:RCW} nos diz que $\alpha(\mathcal{G}_p)$ satisfaz a cota $\alpha(\mathcal{G}_p)\leq 2{4p-1\choose p-1}<1{,}76^n$.



Suponha $F$, $F'\subset[n]$, $|F|=|F'|=k$. Sejam $v^{(F)}$ e $v^{(F')}$ os vetores característicos de $F$ e $F'$, respectivamente.
Então, $|F\triangle F'| = 2(k-|F\cap F'|)$ e $\dist(v^{(F)},v^{(F')})^2=|F\triangle F'| = 2(k - |F\cap F'|)$. Suponha agora que
$\mathcal{F}$ é como no enunciado do Corolário \ref{cor:RCW}. Então para qualquer $F$, $F'\in\mathcal{F}$ com~$F\neq F'$, temos que
$v^{(F)}\in\mathbb{R}^n$, $n=4p-1$ e $\dist(v^{(F)},v^{(F')})\neq\sqrt{2p}$. Consideremos o
grafo $\mathcal{G}_p$ com conjunto de vértices $\{v^{(S)}\colon S\in{[n]\choose 2p-1}\}$ tendo $\{v^{(S)},v^{(S')}\}$ como aresta
se $\dist(v^{(S)},v^{(S')})=\sqrt{2p}$. Claramente, $|V(\mathcal{G}_p)|={n\choose2p-1} = {4p-1\choose 2p-1}$.


Temos a seguinte cota simples para $\chi(\mathcal{G}_p)$:
$$\chi(\mathcal{G}_p)\geq\frac{|V(\mathcal{G}_p)|}{\alpha(\mathcal{G}_p)}.$$
Segue que 
$$
\begin{aligned}
\chi(\mathcal{G}_p)&\geq\frac{{4p-1\choose 2p-1}}{2{4p-1\choose p-1}}\\
&\geq \frac{(1/4p)2^{4p-1}}{(1{,}76)^{4p-1}}\\
&\geq (1{,}1397)^n.
\end{aligned}
$$
Claramente, $\chi(\mathbb{R}^n) = \chi_{\sqrt{2p}}(\mathbb{R}^n)\geq \chi(\mathcal{G}_p)\geq 1{,}1397^{4p-1}$.



Discutimos agora uma construção de Frankl e Wilson '81 \cite{FrWi81}. Seja $V={[n]\choose p^2-1}$ com $p$ primo e~$n>2p^2$. Definimos
$G(n,p)$ como o
grafo com conjunto de vértices~$V$ e se $A,B\in V$ $(A\neq
B)$, então $\{A,B\}$ é aresta de $G$ se e somente se $|A\cap B|\not\equiv -1\ (\bmod\ {p})$. 

\begin{teorema}
O grafo $G(n,p)$ não contém mais que $2{n\choose p-1}$ vértices mutuamente adjacentes e não contém mais que $2{n\choose p-1}$ vértices
mutuamente
não-adjacentes. Isto é, $G(n,p)$ mostra que
$${n \choose p^2-1}\nrightarrow \left(2{n\choose p-1}+1,\ 2{n\choose p-1}+1\right).$$
\end{teorema}





\subsection{Problemas e exercícios}
\label{sec:probs+exx+10}
Todos estão convidados a trabalhar nos seguintes problemas, e\-xer\-cí\-cios e
observações. 

\begin{enumerate}

\item[1.]Mostre que, quando $n\to\infty$, $\chi(\mathbb{R}^n)\leq n^{n/2}$.
\item[2.]Mostre que, quando $n\to\infty$, $\chi(\mathbb{R}^n)\leq c^{n}$, para alguma constante $c$.

\end{enumerate}



\newpage
\section{Teoria extremal dos conjuntos - continuação}
\label{sec:extremal}
\begin{center}
 6/10/2009 e 13/10/2009
\end{center}

\begin{definicao}
O número de independência $\alpha(G)$ de um grafo $G$ é dado pela quantidade de vértices de seu maior conjunto independente, isto é,
conjunto de vértices dois a dois não adjacentes.
\end{definicao}

\begin{definicao}
A cintura $g(G)$ de um grafo $G$ é o comprimento do menor circuito em $G$.
\end{definicao}


\begin{definicao}
Denotamos por $\hom(G)=\max\{\alpha(G),\omega(G)\}$ o tamanho do maior conjunto homogêneo de $G$.
\end{definicao}

\begin{definicao}
Sabemos que $R_2(t)=R(t,t)=\min\{n\colon K^n\to(K^t,K^t)\}$. Observe que, alternativamente, $R(t,t)=\min\{n\colon$ para todo $G^n$,
$\hom(G)\geq t\}$.
\end{definicao}

Seja $V={[n]\choose p^2-1}$ com $p$ primo e~$n>2p^2$. Definimos
$G(n,p)$ como o
grafo com conjunto de vértices~$V$ e, se $A,B\in V$ com $A\neq
B$, então $\{A,B\}$ é aresta de $G$ se e somente se temos que~${|A\cap B|\equiv -1\ (\bmod\ {p})}$. 

\begin{teorema}[Frankl--Wilson '81 \cite{FrWi81}]\label{teo:FrWi81}
Para $G(n,p)$ construído como acima,
$$\hom(G(n,p))\leq 2{n \choose p-1}.$$
\end{teorema}

\begin{proof}
Tomando $L=\{p-1,2p-1,\ldots,(p-1)p -1\}$, pelo Corolário \ref{cor:rw} e pelo Lema \ref{lema:cont}, temos que $\omega(G(n,p))<2{n \choose
p-1}$. Aplicando o Teorema \ref{teo:RCW} com $L=\{0,1,\ldots,p-2\}$ e o primo $p$, temos que $\alpha(G(n,p))<2{n \choose
p-1}$.
\end{proof}

Pelo Teorema \ref{teo:FrWi81}, $G(n,p)$ prova explicitamente que $${n \choose p^2-1}\nrightarrow \left(2{n\choose p-1},\ 2{n\choose
p-1}\right).$$

\begin{corolario}\label{cor:FrWi81}
Seja $w(t)=\log{t}/4\log\log{t}$. Para qualquer $\varepsilon>0$ e $t$ suficientemente grande, podemos construir explicitamente um grafo $G$
com mais que $t^{(1-\varepsilon)w(t)}$ vértices com $\hom(G)<t$.
\end{corolario}

\subsubsection*{Observação} Este grafo $G$ fornece \textit{explicitamente} a cota $R_2(t)>t^{(1-\varepsilon)w(t)}$.

\begin{proof}
Basta tomar $n$ e $p$ apropriadamente na construção de Frankl e Wilson. Seja $n=p^3$ e $p$ o maior primo tal que ${p^3 \choose
p-1}<t$. Para qualquer $\delta>0$, se $t$ é grande o suficiente, $p$ está no intervalo $(1-\delta)\log{t}/2\log\log{t}$ e
$(1+\delta)\log{t}/2\log\log{t}$.
\end{proof}

\subsubsection*{Observação} Há espetaculares resultados recentes melhorando o Corolário \ref{cor:FrWi81}.

\section*{Conjectura de Borsuk}

\begin{definicao}
Seja $X\subset\bbr^n$. O \textit{diâmetro} de $X$ é dado por $\diam(X)=\sup\{\dist(x,x')\colon x,x'\in X\}$.
\end{definicao}

\begin{definicao}
Uma função $f\colon X\to Y$ é uma \textit{antípoda} se $f(-x)=-f(x)$ para todo $x\in X$.
\end{definicao}


\begin{definicao}
A bola aberta de raio $r$, centrada no ponto $x$, denotada por $B_r(x)$, é o conjunto dos pontos $y$ em $\bbr^n$ tais que $\dist(x,y)<r$.
\end{definicao}


\begin{definicao}
Um conjunto $X\subset\bbr^n$ é \textit{aberto} se, para todo $x\in X$, existe $r$ tal que $B_r(x)\subset X$.
\end{definicao}

\begin{definicao}
Um conjunto $X\subset\bbr^n$ é \textit{fechado} se seu complementar é aberto.
\end{definicao}

\begin{definicao}
Uma partição $S_1\cup\ldots\cup S_n$ de um conjunto $S$ em $n$ partes é dita \textit{partição de Borsuk} se $\diam(S_i)<\diam(S)$ para todo
$1\leq i\leq n$.
\end{definicao}


\begin{definicao}
Dado $S$, dizemos que $f(S)$ é o menor $N$ tal que $S$ possui uma partição de Borsuk com $N$ partes. Ademais, pomos $f(n)=\max_{S} f(S)$,
onde o máximo é sobre todos os conjuntos~${S\subset\bbr^n}$ com diâmetro finito.
\end{definicao}



\begin{conjectura}[Borsuk]\label{Borsuk}
Seja $X\subset\mathbb{R}^n$ com diâmetro $1$. Então $X$ possui uma partição de Borsuk com $n+1$ partes.
\end{conjectura}

A Conjectura \ref{Borsuk} diz que $f(n)\leq n+1$. É fácil
provar que $f(n)\leq (3+o(1))^n$ e também sabe-se que~${f(n)\leq (1{,}23+o(1))^n}$.  Em 1993, Jeff Kahn e Gil Kalai mostraram um
contra-exemplo para esta conjectura.

\begin{teorema}[Kahn--Kalai '93 \cite{KaKa93}]\label{teo:KaKa93}
Para $n$ suficientemente grande, temos que $f(n)\leq 1{,}2^{\sqrt{n}}$.
\end{teorema}

\begin{definicao}
Considere $S^n=\{x\in\bbr^{n+1}\colon\lVert X\rVert=1\}\subset\bbr^{n+1}$.
\end{definicao}

\begin{teorema}[Borsuk--Ulam '33]\label{teo:BU}
As seguintes afirmações são válidas.
\begin{itemize}
 \item[(\textit{i})] Se $S^n=U_0,\ldots,U_n$ com $U_i\subset S^n$ aberto para todo ${0\leq i\leq
n}$, então existe $x\in S^n$ e~${0\leq i\leq
n}$ tal que $x\in U_i$ e $-x\in U_i$.
 \item[(\textit{ii})] Se $S^n=F_0,\ldots,F_n$ com $F_i\subset S^n$ fechado para todo ${0\leq i\leq
n}$, então existe $x\in S^n$ e~${0\leq i\leq
n}$
tal que $x\in F_i$ e $-x\in F_i$.
 \item[(\textit{iii})] Para toda função contínua $f\colon S^n\to \bbr^n$, existe $x\in S^n$ tal que $f(x)=f(-x)$.
 \item[(\textit{iv})] Não existe função antípoda $f\colon S^n\to S^{n-1}$.
\end{itemize}
\end{teorema}

\subsubsection*{Observação 1} Os ítens ($i$) e ($ii$) do Teorema \ref{teo:BU} também são conhecidos por Teorema de Lyusternik--Shnirelmann.
\subsubsection*{Observação 2} Segue do Teorema \ref{teo:BU} que $f(n)>n$.

\begin{proof}[Demonstração do Teorema \ref{teo:KaKa93}]
Provamos aqui uma versão levemente mais fraca do Teorema \ref{teo:KaKa93} (provamos que $f(n)\geq1{,}1^{\sqrt{n}}$). Fixe um primo $p$.
Considere
$$\Omega=\{x=(x_i)_{i=1}^{4p}\in\{-1,1\}^{4p}\colon\displaystyle\sum_{i=1}^{4p}x_i=0\}\subset\bbr^{4p}.$$

Para cada $x\in\Omega$, definimos $F_x=\{i\colon x_i=-1\}\subset[4p]$. Temos que $\langle
x,y\rangle=\sum_{1\leq i\leq 4p}{x_i y_i}=0$, para quaisquer $x$, $y\in\Omega$, se e somente se $2(2p-|F_x\cap F_y|)=2p$, isto é, $|F_x\cap
F_y|=p$.

Seja $X\subset\Omega$ tal que, para todos $x$, $y\in X$ com $x\neq y$, temos $\langle x,y\rangle\neq 0$. Desejamos saber quão grande pode
ser o conjunto $X$. Equivalentemente, gostaríamos de saber quão grande pode ser a família de conjuntos $\calf\subset{[4p]\choose 2p}$ tal
que, para todos $F$, $F'\in\calf$ com $F\neq F'$, temos $|F\cap F'|\neq p$.

Seja $\calf'\subset\calf$ tal que $|\calf'\cap\{F$, $F'=[4p]\setminus F\}|\leq 1$ para todo $F\in{[4p]\choose 2p}$. Claramente
temos que~${|\calf|\leq 2|\calf'|}$. Ademais, $\calf'$ satisfaz as hipóteses do Teorema \ref{teo:RCW} quando $L=\{1,\ldots,p-1\}$.
Assim~${|\calf'|\leq\sum_{0\leq j\leq
p-1}{4p\choose j}}$ e, portanto, $|\calf|\leq 2|\calf'|\leq2\sum_{0\leq j\leq p-1}{4p\choose j}\approx 1{,}75^{4p}$. Com isso, o conjunto
$X\subset\Omega$ definido anteriormente é tal que $|X|\leq2\sum_{0\leq j\leq p-1}{4p\choose j}$.

Consideremos agora a função $h\colon \bbr^{4p}\to\bbr^{4p\times 4p}$ tal que $h(x)=xx^T=(x_i x_j)_{i,j=1}^{4p}$. Considere o conjunto 
$V=h(\Omega)\subset\bbr^n$, com $n=(4p)^2$. Temos, para $x$, $y\in\Omega$, que
$$
\begin{aligned}
\lVert h(x)-h(y)\rVert^2&=\lVert (x_i x_j)_{i,j=1}^{4p} - (y_i y_j)_{i,j=1}^{4p}\rVert^2\\
&=\displaystyle\sum_{i,j=1}^{4p}(x_ix_j - y_iy_j)^2\\
&=\displaystyle\sum_{i,j=1}^{4p}(x_i^2x_j^2 - 2x_iy_ix_jy_j + y_i^2y_j^2)^2\\
&=\displaystyle\sum_{i,j=1}^{4p}x_i^2x_j^2 - 2\displaystyle\sum_{i,j=1}^{4p}x_iy_ix_jy_j + \displaystyle\sum_{i,j=1}^{4p}y_i^2y_j^2\\
&=\left(\displaystyle\sum_{i=1}^{4p}x_i^2\right)\left(\displaystyle\sum_{j=1}^{4p}x_j^2\right) -
2\left(\displaystyle\sum_{i=1}^{4p}x_iy_i\right)\left(\displaystyle\sum_{j=1}^{4p}x_jy_j\right) +
\left(\displaystyle\sum_{i=1}^{4p}y_i^2\right)\left(\displaystyle\sum_{j=1}^{4p}y_j^2\right)\\
&=\lVert x\rVert^4 - 2\langle x,y\rangle^2 + \lVert y\rVert^4\\
&=2(4p)^2 - 2\langle x,y\rangle^2\\
&\leq 2(4p)^2,
\end{aligned}
$$
com igualdade se e somente se $\langle x,y\rangle=0$. Assim $\diam(V)=4p\sqrt{2}$. Ademais, $W\subset V$ tem $\diam(W)=\diam(V)$ se e
somente se existem $x$, $y\in\Omega$ tais que $h(x)$, $h(y)\in W$ e $\langle x,y\rangle=0$. Mas vimos que se $X\subset\Omega$ não contém
$x$, $y$ ortogonais, então $|X|\leq2\sum_{0\leq j\leq p-1}{4p\choose j}$. Assim qualquer partição de Borsuk de $V\subset\bbr^n$ tem pelo
menos ${4p\choose 2p}/2\sum_{0\leq j\leq p-1}{4p\choose j}$ partes. Portanto, provamos que $f(n)\geq f(V)\geq (1{,}1)^{\sqrt{n}}$, para $n$
suficientemente grande.
\end{proof}








Paul Erd\H{o}s mostrou que, para quaisquer $q,\ell$, existe um grafo $G$ com $\chi(G)\geq q$ e $g(G)\geq\ell$ (veja exercício
\ref{sec:probs+exx+3}.$1$).

\begin{definicao}
O \textit{grafo de Borsuk} $B^n(\varepsilon)$ é o grafo formado pelo conjunto de vértices $S^n$ e
$\{x,y\}$ é uma aresta de $B^n(\varepsilon)$ se e somente se $\lVert x-y\rVert\geq 2-\varepsilon$.
\end{definicao}

Podemos observar que
\begin{itemize}
 \item[(\textit{a})] $B^n(\varepsilon)$ tem circuitos curtos: $C^4\subset B^n(\varepsilon)$;
 \item[(\textit{a})] $B^n(\varepsilon)$ não tem circuitos ímpares curtos: para todo $k\geq 1$, existe $\varepsilon>0$ tal que
$C^{2k'+1}$ não está contido em $B^n(\varepsilon)$, para todo $k'\leq k$.
\end{itemize}

\begin{definicao}
O grafo de Kneser $K(n,r)$ é o grafo com conjunto de vértices $V={[n+2r-1] \choose r}$ e, se~$A,B\in V$ com $A\neq
B$, então $\{A,B\}$ é aresta de $K(n,r)$ se e somente se $|A\cap B|=\varnothing$. 
\end{definicao}

Kneser conjecturou em 1955 que $\chi(K(n.r))=n+1$. Este resultado foi provado independentemente por Lovász \cite{Lo78} e Bárány
\cite{Ba78}.

\subsection{Problemas e exercícios}
\label{sec:probs+exx+11}
Todos estão convidados a trabalhar nos seguintes problemas, e\-xer\-cí\-cios e
observações. 

\begin{enumerate}

\item[1.]Prove que o Teorema \ref{teo:BU} implica que $\chi(B^n(\varepsilon))>n+1$ (Dica: utilize o ítem ($ii$) do teorema).

\end{enumerate}




\newpage
\section{Teoria extremal dos conjuntos - continuação}
\label{sec:extremal}
\begin{center}
 20/10/2009
\end{center}

\begin{lema}[]\label{lema:isoRamsey}
Todo triângulo de lados $x$, $x$ e $\sqrt{6}$, com $x\geq 2$, é Ramsey.
\end{lema}

\begin{proof}
% Pelo Exercício \ref{sec:probs+exx+8}.3, todo triângulo de lados $\sqrt{2}$, $\sqrt{2}$ e $\sqrt{6}$ é Ramsey. 
Consideremos o triângulo $T=\{(-1,1,0),(-1,0,1),(0,-1,1)\}$. Seja $r\in\bbn^*$ fixo. Tome $n$ tal que $n\to(3)_r^2$, isto é, se
colorimos os pares em $[n]$ com $r$ cores, há $i<j<k$ tal que~${\{i,j\}}$,~$\{j,k\}$ e $\{i,k\}$ têm a mesma cor. Para cada $P=\{a,b\}$, com
$1\leq a<b\leq n$, seja
$$
\begin{aligned}
&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a\ \ \ \ \ \ \ \ \ \ b\ \ \ \ \ \ \ \ \ \\
y(P)&=(0\ldots 0\ -1\ 0\ldots 0\ 1\ 0\ldots0)\in\bbr^n.
\end{aligned}
$$

Temos assim um conjunto $L=\{y(P)\in\bbr^n\colon P\in{n\choose 2}\}$ de ${n\choose 2}$ pontos do $\bbr^n$. Afirmamos que~${L\to(T)_r}$:
qualquer $r$-coloração de $L$ é tal que existem três pontos $y_1$, $y_2$ e $y_3$  em $L$, todos da mesma cor, com $y_1$, $y_2$ e $y_3$
formando uma cópia de $T$. Fixe uma tal $r$-coloração $\chi\colon L\to[r]$. Defina a seguinte $r$-coloração dos pares em $[n]$:
$$\chi'(\{a,b\})=\chi(y(\{a,b\})),$$
para todo $1\leq a<b\leq n$. Pela escolha de $n$, existem $1\leq i<j<k\leq n$ tal que
$\chi'$ associa a mesma cor aos pares $\{i,j\}$, $\{i,k\}$ e $\{j,k\}$:
$$
\begin{aligned}
&\ \ \ \ \ \ \ \ \ \ \ \ \ i\ \ \ \ \ j\ \ \ \ \ k\ \ \ \ \\
y(\{i,j\})&=(\ \ \ \ \ -1\ \ \ \ \  1\ \ \ \ \ \ \ \ \ \ \ )\stackrel{def}{=}y_1\\
y(\{i,k\})&=(\ \ \ \ \ -1\ \ \ \ \  \ \ \ \ \ \ 1\ \ \ \ \ )\stackrel{def}{=}y_2\\
y(\{j,k\})&=(\ \ \ \ \ \ \ \ \ \ \  -1\ \ \ \ \ 1\ \ \ \ \ )\stackrel{def}{=}y_3.
\end{aligned}
$$
Portanto, $T$ é Ramsey (Observe que isso prova o Exercício \ref{sec:probs+exx+8}.3).

Considere $A, B, C\in\bbr$ e a configuração $\{0,w\}\subset\bbr$ e seja $K_w=\{A,B,C\}*\{0,w\}\subset\bbr^4$. Pelo Teorema do Produto
(Teorema \ref{teo:prod}), temos que $K_w$ é Ramsey. Dado o triângulo $T_x$ de lados~$x$,~$x$~e~$\sqrt{6}$, temos que $T_x\subset K_w$ para
$w=w(x)$ adequado desde que $x\geq\sqrt{2}$, concluindo a prova do lema.
\end{proof}
\newpage
\begin{lema}\label{lema:iso}
Seja $t\geq 2$ um inteiro. O triângulo de lados $\sqrt{2t}$, $\sqrt{2t}$ e $\sqrt{8t-6}$ é Ramsey.
\end{lema}

\begin{proof}
Seja $r\in\bbn^*$ fixo. Considere o triângulo $T=\{y_1,y_2,y_3\}$ onde
$$
\begin{aligned}
y_1&=(\overbrace{1,2,\ldots,t-1,t,t-1,\ldots,2,1}^{2t-1},0,0)\in\bbr^{2t+1}\\
y_2&=(0,1,2,\ldots,t-1,t,t-1,\ldots,2,1,0)\in\bbr^{2t+1}\\
y_3&=(0,0,1,2,\ldots,t-1,t,t-1,\ldots,2,1)\in\bbr^{2t+1}.
\end{aligned}
$$
Temos que $\lVert y_1-y_2\rVert = \lVert y_2-y_3\rVert = \sqrt{2}$ e $\lVert y_1-y_3\rVert=\sqrt{8t-6}$. Escolha $n\to(2t+1)^{2t-1}_r$.
Considere o conjunto $L\subset\bbr^n$ cujos membros são os pontos $x=(x_i)_{1\leq i\leq n}$ tal que suas coordenadas não nulas são, nessa
ordem, $1,2,\ldots,t-1,t,t-1,\ldots,2,1$. Temos $\lvert L\rvert={n\choose 2t-1}$. Portanto, $L\to(T)_r$ (É um bom exercício provar este
fato).
\end{proof}

\begin{teorema}[]\label{teo:isoRamsey}
Todo triângulo isósceles é Ramsey.
\end{teorema}

\begin{proof}
Sabemos que  $2\sqrt{2t}/\sqrt{8t-6}\to1$. Portanto, pelo Lema \ref{lema:iso}, temos triângulos isósceles arbitrariamente obtusos que são
Ramsey. Pelo Lema \ref{lema:isoRamsey} e pelo Teorema do Produto, temos que todo triângulo isósceles é Ramsey.
\end{proof}


\newpage
\section{Teoria de Ramsey Euclidiana}\footnotetext[1]{Os resultados desta seção foram apresentados pelo aluno Eric Ossami.}
\label{sec:rams:Eric}
\begin{center}
10/11/2009
\end{center}

Nesta seção provamos o seguinte resultado.

\begin{teorema}\label{ram:esf}
Toda configuração de Ramsey é esférica.
\end{teorema}

Para demonstrar o Teorema \ref{ram:esf}, precisamos de dois lemas auxiliares.

\begin{lema}\label{lema1}
Uma configuração $K=\{x_0,x_1,\ldots,x_k\}$ não é esférica se e somente se existem números reais~${c_1,c_2,\ldots,c_k}$ não todos nulos tais que
\end{lema}
\begin{itemize}
 \item[(\textit{i})]$\sum_{1\leq i \leq k}{c_i(x_i-x_0)}=0$;
 \item[(\textit{ii})]$\sum_{1 \leq i \leq k}{c_i(\left\|x_i\right\|^2-\left\|x_0\right\|^2)}=b \ne 0$.
\end{itemize}

\begin{proof}
($\Leftarrow$) Suponha, por absurdo, que $K$ seja esférica. Assim, existe uma esfera de centro~$w$ e raio $r$ que contém $K$. Suponha que existam $c_1, c_2,\ldots,c_k$ tais que (\textit{i}) seja válida.
Temos que
$$\left\|x_i\right\|^2-\left\|x_0\right\|^2=\left\|x_i-w\right\|^2-\left\|x_0-w\right\|^2+2 \langle x_i-x_0,w\rangle.$$
Assim,
$$\displaystyle\sum_{1\le i\le k}{c_i(\left\|x_i\right\|^2-\left\|x_0\right\|^2)}=2\displaystyle\sum_{1\le i\le k}{\langle x_i-x_0,w\rangle}=2\left\langle\displaystyle\sum_{1\leq i\le k}{c_i(x_i-x_0),w}\right\rangle=0.$$
Portanto, temos que (\textit{ii}) não é válida, uma contradição.


($\Rightarrow$) Seja $K$ uma configuração não esférica. Ademais, suponha $K$ minimalmente não-esférica, isto é, todo subconjunto próprio de $K$ é esférico. Observe que $K$ é afim-independente, ou seja, se os vetores $x_i-x_0$, para $1\leq i\leq k$, são linearmente independentes, então $K$ é esférica. De fato, para cada~$i$, seja $H_i$ o hiperplano afim que contém os pontos equidistantes a $x_0$ e $x_i$. Mostremos que esses hiperplanos se intersectam em pelo menos um ponto.

Seja $y\in \bbr^n$ tal que $\langle x_i-x_0,y-(x_i+x_0)/2\rangle=0$ para $1\le i\le k$. Assim temos, para todo~${1\le i\le k}$, que $\langle y,x_i-x_0\rangle=c_i$, com $c_i$ constante.

Sejam $y=(y_1,y_2,\ldots,y_n)$ e $x_i=(x_{i1},\ldots,x_{in})$. Assim,

$$
\begin{aligned}
y_1(x_{11}-x_{01})+&\ldots+y_n(x_{1n}-x_{0n})&=0 \\
y_1(x_{21}-x_{01})+&\ldots+y_n(x_{2n}-x_{0n})&=0 \\
&\ \ \vdots&\\
y_1(x_{n1}-x_{01})+&\ldots+y_n(x_{nn}-x_{0n})&=0
\end{aligned}
$$

Como os vetores $x_i-x_0$ $(1 \le i\le k)$ são linearmente independentes e existem $k\le n$ equações, então esse sistema possui solução.

Como $K$ não é esférico, existem reais $c_1,\ldots,c_k$ não todos nulos tais que (\textit{i}) vale. Suponha, sem perda de generalidade, $c_k\ne0$ e que a esfera que contém ${x_0,\ldots,x_{k-1}}$ tem centro $w$ e raio $r$. Com isso,
$$
\begin{aligned}
\displaystyle\sum_{1\le i\le k}{c_i(\left\|x_i\right\|^2-\left\|x_0\right\|^2)}&=\displaystyle\sum_{1\le i\le k}{c_i(\left\|x_i-w\right\|^2-\left\|x_0-w\right\|^2)}+2 \left\langle\displaystyle\sum_{1\le i\le k}{c_i(x_i-x_0),w} \right\rangle\ne 0.
\end{aligned}
$$
Portanto, (\textit{ii}) vale.

\end{proof}

\begin{lema}\label{lema2}Sejam $c_1,\ldots,c_k$ e $b$ números reais, com $b\ne 0$. Existem um inteiro $r$ e alguma ${r\text{-coloração}}$ de $\bbr$ tal que toda solução da equação $\sum_{1\le i\le k}{c_i(y_i-y_0)=b}$, com $y_i\in \bbr$ $(1\le i\le k)$, não é monocromática.
\end{lema}

Provaremos um resultado mais geral.

\begin{teorema}\label{teorema1}Seja $K$ um corpo de característica $0$ e $c_1,\ldots,c_k$, $b$ elementos de $K$ com $b\ne 0$. Existe uma $(2k)^k$-coloração $\psi$ de $K$ tal que a equação $\sum_{1\le i\le k}{c_i(y_i-y'_i)}=b$ não tem nenhuma solução em $K$, com $\psi(y_i)=\psi(y'_i)$ para todo $1\le i\le k$.
\end{teorema}

É claro que o Teorema \ref{teorema1} implica o Lema \ref{lema2}. Basta tomar $y'_i=y_0$ $(1\le i\le k)$, assim temos que~$\psi(y_i)=\psi(y_0)$, ou seja, não existe solução monocromática. Provaremos, a seguir, um lema auxiliar que será utilizado na prova do Teorema \ref{teorema1}.

\begin{lema}\label{maisumlema}Existe uma $2k$-coloração $\phi$ de $\bbr$ tal que a equação $\sum_{1\le i\le k}{(x_i-x'_i)}=1$ não possui solução com $\phi(x_i)=\phi(x'_i)$, para todo $1\le i\le k$.
\end{lema}

\begin{proof} Consideramos $\bbr_2=\{\bar{a}\colon a\in \bbr\}$, onde $\bar{a}=\{x\in \bbr\colon x\equiv a (\bmod\ 2)\}$, para definir uma coloração $\phi$ como no enunciado. Podemos identificar $\bbr_2$ com o intervalo $[0,2)$.

Seja $r\in \bbr\mapsto \bar{r}\in \bbr_2$ a projeção canônica. Observamos que é equivalente a $\bar{r}=2\left\{r/2\right\}$. Particionamos o intervalo $[0,2)$ em $2k$ intervalos de comprimento $1/k$ cada. Sejam $I_i=\left[(i-1)/k,i/k\right)$, para todo $1\le i\le 2k$, tais intervalos. Tome $\phi(r)=i$, onde $i$ é tal que $\bar{r}\in I_i$. Observe que se~ ${\phi(x)=\phi(x')}$, então $x$ e~${x'\in I_i\Rightarrow \left|x-x'\right|\le 1/k}$. Mas observe que $x=2\left\lfloor x/2\right\rfloor+2\left\{x/2\right\}$ e~${x'=2\left\lfloor x'/2 \right\rfloor+2\left\{x'/2\right\}}$, logo temos que $x-x'=2\left(\left\lfloor x/2\right\rfloor-\left\lfloor x'/2\right\rfloor \right) + (\bar{x}-\bar{x'})$ $\Rightarrow x-x'=2m+\theta$, onde $x\in \bbz$ e $0\le \theta < 1/k$.

Suponha, por absurdo, que a equação $\sum_{1\le i\le k}{c_i(y_i-y_0)=b}$ possui solução com $\phi(x_i)=\phi(x'_i)$, para todo $1\le i\le k$. Então, para todo $i$, temos que $|x_i-x'_i|=2m_i+\theta_i$ para algum inteiro $m_i$ e $|\theta_i|<1/k$. Assim, $\sum_{1\le i\le k}{(x_i-x'_i)}=2m+\theta$, onde $m$ é inteiro e $0\le |\theta|<1$. Mas sabemos que~$\sum_{1\le i\le k}{c_i(y_i-y_0)=b}$ é válida, portanto $2m+\theta=1$, uma contradição.
\end{proof}

\begin{proof}[Demonstração do Teorema \ref{teorema1}] Considere $K$ um espaço vetorial sobre o conjunto $\mathbb{Q}$. Fixe uma aplicação li\-ne\-ar~$T:K\mapsto \mathbb{Q}$ tal que $T(b)=1$. Tal aplicação linear existe pois vale a seguinte proposição da álgebra linear:

\noindent\textit{Proposição.} Sejam $U$ e $V$ dois espaços vetoriais sobre $K$, se $\{u_1,...,u_n\}$ é uma base de $U$ e, mais ainda, $\{v_1,...,v_n\}\subseteq V$, então existe uma única transformação linear $T:U\mapsto V$ tal que $T(u_i)=v_i$, para cada $i=1,...,n$.

Fixe uma $2k$-coloração $\phi$ de $\bbr$ como no Lema \ref{maisumlema}. Para cada $r\in K$, observe que podemos tomar~$\psi(r)=(\phi(T(c_ir)))_{1\le i\le k}=(\phi(T(c_1r)),\ldots,\phi(T(c_kr)))\in [2k]^k$. Portanto temos que~$\psi$ é uma~$(2k)^k$-coloração de $K$. Suponha que temos uma solução de  $\sum_{1\le i\le k}{c_i(y_i-y'_i)}=b$ em que~${\psi(y_i)=\psi(y'_i)}$, para todo $1\le i\le k$.

Aplicando $T$ em  $\sum_{1\le i\le k}{c_i(y_i-y'_i)}=b$, temos que $\sum_{1\le i\le k}{(T(c_iy_i)-T(c_iy'_i))}=1$. Com isso, tome $x_i=T(c_iy_i)$ e $x'_i=T(c_iy'_i)$. Portanto, para todo $1\le i\le k$, a $i$-ésima coordenada de $\psi(y_i)$, que é $\phi(T(c_iy_i))=\phi(x_i)$, coincide com a $i$-ésima coordenada de $\psi(y'_i)$, que é $\psi(T(c_iy'_i))=\phi(x'_i)$. Uma contradição com a escolha de $\phi$.
\end{proof}
\subsubsection*{Observação} Para $K=\bbr$, podemos tomar $T(y)=y/b$ $(y\in \bbr)$ e usar o fato de $\phi$ estar definida sobre a reta $\bbr$.



\begin{proof}[Demonstração do Teorema \ref{ram:esf}] Seja $K=\{x_0,...,x_k\} \subset \bbr$ uma configuração Ramsey. Suponha por contradição que $K$ não é esférica, então, pelo Lema \ref{lema1}, existem reais $c_1,\ldots,c_k$ não todos nulos e~$b\ne 0$ satisfazendo as condições (\textit{i}) e (\textit{ii}) do Lema \ref{lema1}.

Fixe uma $r$-coloração $\psi$ de $\bbr$ tal que a equação $\sum_{1\le i\le k}{c_i(y_i-y_0)}=b$ não tenha solução monocromática $y_1,\ldots,y_k \in \bbr$. Pelo Lema \ref{lema2}, tal coloração existe. Defina uma $r$-coloração de $\bbr^n$, pondo $\phi(x)=\psi(\left\|x\right\|^2)$. Mostraremos que essa coloração não cria uma cópia monocromática de $K$. A única restrição que temos sobre $n$ é que $K\subset \bbr$.

Suponha que $K'=\{x'_0,\ldots,x'_k\}\subset\bbr$ é uma cópia monocromática de $K$ na coloração $\phi$. Sem perda de generalidade, estendemos a aplicação $\iota:x_i\mapsto x'_i$ $(0\le i\le k)$ a uma isometria de $\bbr^n$. Provemos que as identidades as condições (\textit{i}) e (\textit{ii}) valem para os pontos $x'_i$ $(1\le i\le k)$ de $K'$. É claro que $\sum_{1\le i\le k}{c_i(x'_i-x'_0)}=0$. Assim, a condição (\textit{i}) vale para os $x'_i$, com $1\le i\le k$.

Mostraremos que a condição (\textit{ii}) é válida para $x'_i$. Observamos que $K'$ pode ser obtida a partir de $K$ por uma aplicação de uma isometria que preserva a origem, seguida de uma translação. Suponha então que $\iota$ preserve a origem. É claro que $\left\|x'_i\right\|^2=\left\|\iota(x_i)\right\|^2=\left\|x_i\right\|^2$ para todo $ 1\le i\le k$ e a condição (\textit{ii}) vale neste caso. Seja uma translação por $z\in \bbr^n$, temos
$$
\begin{aligned}
\sum\limits_{1\le i\le k}{\left\|x_i+z\right\|^2-\left\|x_0+z\right\|^2}&=\sum\limits_{1\le i\le k}{\left\|x_i\right\|^2-\left\|x_0\right\|^2}-2\left\langle z, \sum\limits_{1\le i\le k}{c_i(x_i-x_0)}\right\rangle\\
&=\sum\limits_{1\le i\le k}{\left\|x_i\right\|^2-\left\|x_0\right\|^2}\\
&=b\ne 0.
\end{aligned}
$$

Assim a condição (\textit{ii}) vale para $x'_i$. Mas como $K'$ é monocromático, de acordo com $\phi$ isto implica que, tomando $y_i=\left\|x_i\right\|^2$, para todo $1\le i\le k$, temos uma solução monocromática de (\textit{ii}) de acordo com $\psi$, uma contradição.
\end{proof}

\newpage
\bibliographystyle{amsplain_yk}
\bibliography{PICME}


\end{document}


