%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Prova 2 de MAC5827 Topicos de Matemática Discreta                  %
% 2o. semestre de 2008                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 19 Nov 2008 02:39:52pm BRST yoshi@turan.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

%\usepackage{refcheck}
\usepackage{srcltx}
\usepackage{amssymb}

\let\:=\colon
\let\epsilon=\varepsilon
\let\phi=\varphi
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\dim{\mathop{\rm dim}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\im{\mathop{\rm im}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\QQ{\mathbb Q}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim

\def\inR{\mathrel{\in_{\text R}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cE{\mathcal E}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}
\def\cZ{\mathcal Z}

\def\barp{{\bar p}}

\def\Ave{\mathop{{\rm Ave}}\nolimits}
\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}
\def\diam{\mathop{{\rm diam}}\nolimits}
\def\PG{\mathop{{\rm PG}}\nolimits}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfa{\textbf{a}}
\def\bfb{\textbf{b}}
\def\bff{\textbf{f}}
\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}
\def\bfX{\textbf{X}}
\def\bfdelta{\boldsymbol\delta}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}
%\def\datedue#1{}
\def\sugestao#1{[\textit{Sugestão.} #1]}
\let\hint\sugestao
\def\observacao#1{[\textit{Observação.} #1]}

\begin{document}
\title[MAC5827 Matemática Discreta]{Prova 2 de Matemática 
  Discreta\\2{\tiny o.} semestre de 2008} 
\date{Versão de \today}
\maketitle
\pagestyle{plain}
\footskip=25pt

\noindent \textbf{Instruções:}
\begin{enumerate}
\item As soluções a serem entregues devem ser elaboradas
  individualmente.  Entretanto, você pode discutir os problemas com
  colegas e professores. \textbf{Cite toda e qualquer fonte que você
    usar para elaborar suas soluções.}  O uso de fontes, devidamente
  citadas, não diminuirá sua nota.
\item Você deve tentar entregar ao menos um exercício de cada uma das
  seguintes~$4$ listas:
  \begin{enumerate}
  \item 1, 2, 3, 4
  \item 5, 6, 7, 8
  \item 9, 10, 11, 12, 13
  \item 14, 15, 16, 17, 18.
  \end{enumerate}
  Você pode entregar quantos exercícios quanto quiser.  

\end{enumerate}

\noindent \textbf{Questões:}

\begin{enumerate}

\item\label{item:symmchains} Dizemos que uma
  cadeia~$\cC=\{A_1,\dots,A_k\}$, com $A_1\subset\dots\subset A_k$, de
  elementos de~$\cP([n])$ é uma \textit{cadeia simétrica} se valem as
  seguintes condições:
  \begin{enumerate}
  \item[(\textit{a})]$\cC$ é \textit{saturada}, isto é, $|A_i|=|A_{i-1}|+1$ 
    para todo~$1<i\leq k$.
  \item[(\textit{b})]$|A_1|+|A_k|=n$.
  \end{enumerate}
  Prove as seguintes asserções:
  \begin{enumerate}
  \item[(\textit{i})]$\cP([n])$ pode ser particionado em cadeias
    simétricas.  \hint{Use indução em~$n$.  Suponha que~$n>0$ e que o
      resultado vale para valores menores de~$n$.
      Seja~$\cP([n-1])=\bigcup_{\lambda\in\Lambda}\cC_\lambda$ uma
      decomposição de~$\cP([n-1])$ em cadeias simétricas.  Construa
      duas cadeias a partir de cada~$\cC_\lambda$ da sequinte forma.
      Suponha que~$\cC_\lambda$ é a cadeia $A_1\subset\dots\subset
      A_k$.  Considere então $A_1\subset\dots\subset A_k\subset
      A_k\cup\{n\}$ e $A_1\cup\{n\}\subset\dots\subset
      A_{k-1}\cup\{n\}$.} 
    
  \item[(\textit{ii})][Sperner] A cardinalidade máxima de uma família
    de Sperner sobre~$[n]$ (isto é, o número máximo de elementos em
    uma anticadeia em $\cP([n])$) é~${n\choose\lfloor n/2\rfloor}$.
    
  \end{enumerate}
  
\item\label{Q:Erdos}[Erd\H os] Sejam~$x_1,\dots,x_n$ números reais.  Considere
  as~$2^n$ somas da forma
  $$
  x_{i_1}+\dots+x_{i_k},
  $$
  onde~$i_1<\dots<i_k$ e~$k\geq0$.  Digamos que um conjunto~$S$ dessas
  somas seja \textit{pequeno} se quaisquer dois membros de~$S$
  distem~$<1$ (a diferença é menor que~$1$ em módulo).  Determine o
  tamanho máximo de um conjunto pequeno supondo que os~$x_i$ sejam
  todos tais que~$|x_i|\geq1$.  Isto é, determine~$f(n)$ para
  todo~$n\geq0$, onde definimos~$f(n)$ como sendo
  $$
  \max_{x_1,\dots,x_n}\max\{|S|\:\text{$S$ é pequeno}\}
  $$
  e o (primeiro) máximo é tomado sobre todas as
  seqüências~$x_1,\dots,x_n\in\RR$ com~$|x_i|\geq1$ para todo~$i$.
  
\item{}[Kleitman] Generalizemos o Ex.~\ref{Q:Erdos} para dimensões
  arbitrárias.  Supomos agora que os~$x_i$ estão em~$\RR^d$,
  onde~$d\geq1$.  Determine~$f_d(n)$ para todo~$n\geq0$, onde
  definimos~$f_d(n)$ como sendo
  $$
  \max_{x_1,\dots,x_n}\max\{|S|\:\text{$S$ é pequeno}\}
  $$
  e o (primeiro) máximo é tomado sobre todas as
  seqüências~$x_1,\dots,x_n\in\RR^d$ com~$\|x_i\|\geq1$ para todo~$i$
  (isto é, todos os~$x_i$ têm norma pelo menos~$1$).
  Naturalmente, este problema se reduz ao Ex.~\ref{Q:Erdos} se~$d=1$.

  \sugestao{Você pode achar interessante considerar a ``filosofia''
    subjacente à solução sugerida do Ex.~\ref{item:symmchains}.}

\item Sejam~$x_1,\dots,x_n\in\RR^d$ e~$\Delta\geq0$.  Considere as~$2^n$ somas
  da forma
  $$
  x_{i_1}+\dots+x_{i_k},
  $$
  onde~$i_1<\dots<i_k$ e~$k\geq0$.  Dizemos que um conjunto~$S$ dessas
  somas é $\Delta$-\textit{pequeno} se quaisquer dois membros de~$S$
  distam~$\leq\Delta$.
  
  Seja
  $$
  m_d(n,\Delta)=\max_{x_1,\dots,x_n}\max\{|S|\:\text{$S$ é
    $\Delta$-pequeno}\}
  $$
  e o (primeiro) máximo é tomado sobre todas as
  seqüências~$x_1,\dots,x_n\in B$ com~$||x_i||\geq1$ para todo~$i$ (isto é,
  todos os~$x_i$ têm norma pelo menos~$1$).  Prove que existe uma
  constante~$c_d$ que depende apenas de~$d$ para o qual vale
  \begin{equation}
    \label{eq:weak_FF_for_LO}
    m_d(n,\Delta)\leq c_d(\lfloor\Delta\rfloor+1){n\choose\lfloor
      n/2\rfloor}. 
  \end{equation}

\item Sejam $p$ um número primo e $L$ um conjunto de $s$ números
  inteiros. Suponha que $\cF=\{A_1,A_2,\dots,A_m\}$ é uma família de
  subconjuntos de um conjunto de $n$ elementos tal que
  \begin{itemize}
  \item[(\textit{i})] $|A_i|\notin L \pmod p \quad (1\le i\le m)$;
  \item[(\textit{ii})] $|A_i\cap A_j| \in L\pmod p\quad (1\le i< j\le m)$.
  \end{itemize}
  Prove que 
  $$
  m\le \sum_{j=0}^s \binom{n}{j}.
  $$
  \observacao{Acima, $x\in L\pmod p$ significa que~$x\equiv\ell$ para
    algum~$\ell\in L$.}

  \sugestao{Considere o seguinte polinômio em $2n$ variáveis $(x,y)$,
    $x=(x_1,\dots,x_n)$, $y=(y_1,\dots,y_n)$: $$ F(x,y)=\prod_{\ell\in
      L} (\langle x,y\rangle-\ell), \quad \text{ onde } \quad \langle
    x,y\rangle=\sum_{i=1}^n x_i y_i.  $$ Considere agora os polinômios
    em $n$ variáveis $f_i(x)=F(x,v_i)$, onde $v_i\in\{0,1\}^n$ é o
    {\it vetor de incidência\/} do conjunto $A_i$, isto é,
    $v_i=(v_{i1},v_{i2},\dots,v_{in})$, onde
    $$ v_{ij}=\chi_{{}_{A_i}}(j)= \begin{cases} 1 \text{ se } j\in A_i \\ 0 \text{
        se } j\notin A_i.
    \end{cases}
    $$
    Pela definição de $F$ e pelas hipóteses do teorema, $p\mid
    f_i(v_j)$ se $i\ne j$ e $p\nmid f_i(v_i)$, para todo~$i$.
    Como~$x^2=x$ para~$x=0$ e~$x=1$, podemos trocar os polinômios
    $f_i$ por polinômios multilineares $\widetilde f_i$ de grau $\le
    s$ que coincidem com $f_i$ em $\{0,1\}^n$, e portanto nos vetores
    $v_i$.  Prove que $\widetilde f_1,\widetilde f_2,\dots,\widetilde
    f_m$ são linearmente independentes sobre $\QQ$.  Observe que a
    dimensão do espaço dos polinômios multilineares em $n$ variáveis
    de grau $\le s$ é $\sum_{j=0}^s \binom{n}{j}$.  Deduza o
    resultado.}

\item\label{Q:num_crom} Seja~$c(n)=\chi(\RR^n)$ o \textit{número
    cromático} do~$\RR^n$: o número mínimo de cores com que podemos
  colorir os elementos de~$\RR^n$ de forma que quaisquer dois pontos
  da mesma cor não estão à distância~$1$.
  \begin{itemize}
  \item[(\textit{i})] Prove que~$4\leq c(2)\leq7$.
  \item[(\textit{ii})]Seja~$p$ um primo.  Prove que
    \begin{equation}
      \label{eq:chromatic_lwbd}
      c(4p-1)
      \geq{4p-1\choose2p-1}\bigg(\sum_{0\leq j<p}{4p-1\choose j}\bigg)^{-1}. 
    \end{equation}
  \item[(\textit{iii})]Prove que
    $$
    \sum_{0\leq j<p}{4p-1\choose j}
    \leq\(1+{1\over3}+{1\over3^2}+\dots\){4p-1\choose p-1}
    \leq{3\over2}{4p-1\choose p-1}.
    $$
    
  \item[(\textit{iv})]Lembra a fórmula de Stirling:
    \begin{equation}
      \label{eq:Stirling}
      n!=(1+o(1))\(n\over\e\)^n\sqrt{2\pi n}.
    \end{equation}
    Use~\eqref{eq:Stirling} para deduzir que
    $$
    {n\choose\alpha n}=\(1\over\alpha^\alpha(1-\alpha)^{1-\alpha}\)
    ^{(1+o(1))n},
    $$
    ou, equivalentemente,
    $$
    \lim_{n\to\infty}{1\over n}\log{n\choose\alpha n}=H(\alpha),
    $$
    onde~$H(\alpha)=\alpha\log(1/\alpha)+(1-\alpha)\log(1/(1-\alpha))$ é a
    assim chamada função entropia.
    
  \item[(\textit{v})]Prove que o lado direito de~\eqref{eq:chromatic_lwbd} é
    pelo menos~$(1.139)^{4p-1}$ se~$p$ é suficientemente grande.
  \end{itemize}\sugestao{Para fazer~(\textit{ii}), considere o
    seguinte roteiro.  Seja~$n=4p-1$.  Seja $V$ o conjunto dos vetores
    com coordenadas~$0$ e~$1$ com exatamente~$2p-1$ coordenadas iguais
    a~$1$: $V=\{\bfx=(x_i)_{1\leq i\leq n}\in\{0,1\}^n\:\text{$x_i=1$
      para~$2p-1$ índices~$i$}\}$.  Considere o grafo~$G=(V,E)$
    sobre~$V$, onde dois vértices são adjacentes se e só se a
    distância euclideana entre eles é~$\sqrt{2p}$.  Mostre que
    se~$U\subset V$ tem mais de $\sum_{0\leq j<p}{n\choose j}$
    elementos, então há dois vértices adjacentes em~$U$.}

\item\label{Q:PNT} Para~$x\in\RR$, seja~$\pi(x)$ o número de
  números primos~$p\leq x$.  O teorema dos números primos nos diz que
  \begin{equation}
    \label{eq:PNT}
    \pi(x)=(1+o(1)){x\over \log x},
  \end{equation}
  onde~$o(1)\to0$ conforme~$x\to\infty$.  Seja~$p_k$ o $k$-ésimo primo (assim,
  $p_1=2$, $p_2=3$, e~$p_{10}=29$).
  \begin{enumerate}
  \item[(\textit{i})]Prove que~$p_k/p_{k-1}=1+o(1)$ conforme~$k\to\infty$.

  \item[(\textit{ii})]Prove que~$p_k=(1+o(1))k\log k$ conforme~$k\to\infty$.
  \end{enumerate}

\item\label{Q:_general_n} O Exercício~\ref{Q:num_crom} mostra
  que~$c(4p-1)\geq(1.139)^{4p-1}$ para todo primo~$p$ suficientemente grande.
  Use o resultado do Ex.~\ref{Q:PNT} para deduzir que~$c(n)\geq(1.13)^n$ para
  todo~$n$ suficientemente grande.

\item Seja~$G$ um grafo infinito.  A \textit{densidade superior}~$\bsigma(G)$
  de~$G$ é definida como sendo
  \begin{equation}
    \label{eq:upper_dens_def}
    \limsup_{n\to\infty}\sigma_n(G),
  \end{equation}
  onde
  \begin{equation}
    \label{eq:sigma_n_def}
    \sigma_n(G)=\sup\{\sigma(G[W])\:W\subset V(G),\;|W|=n\},
  \end{equation}
  e~$\sigma(G[W])$ denota a densidade~$e(G[W]){|W|\choose2}^{-1}$ do
  grafo~$G[W]=(W,E(G)\cap{W\choose2})$ induzido por~$W$ em~$G$.
  Deduza do teorema de Erd\H os e Stone ou Erd\H os--Stone--Simonovits
  que as únicas densidades superiores possíveis são
  $$
  0,{1\over2},{2\over3},\dots,1.
  $$
  Isto é
  $$
  \{\bsigma(G)\:\text{$G$ grafo infinito}\}
  =\left\{1-{1\over t}\:t\in\NN\right\}\cup\{1\}.
  $$
  
\item\label{Q:repeated_distances}[Erd\H os] Seja~$f^{(d)}(n)$ o número
  máximo de vezes que a distância~$1$ ocorre em uma configuração
  de~$n$ pontos em~$\RR^d$.  Mostre que ~$f^{(2)}(n)=O(n^{3/2})$.
  \sugestao{Lembre que $\ex(n,K^{(2)}(2,3))=O(n^{3/2})$ e use este
    resultado ($K^{(2)}(2,3)$ é o grafo bipartido completo com classes
    de vértices de cardinalidades~$2$ e~$3$).}
  
\item (Continuação do Ex.~\ref{Q:repeated_distances}) Mostre
  que~$f^{(2)}(n)$ é superlinear, isto é,
  $$
  \lim_{n\to\infty}f^{(2)}(n)/n=\infty.
  $$

\item\label{Q:lagrange}
  Seja~$\cH\subset{[n]\choose k}$ um hipergrafo $k$-uniforme.
  Para~$\bfx=(x_i)_{1\leq i\leq n}\in\RR^n$, seja
  \begin{equation}
    \label{eq:lagrange_def}
    \lambda_\cH(\bfx)=\sum_{H\in\cH}\prod_{i\in H}x_i.
  \end{equation}
  Em palavras, para cada hiperaresta~$H$ de~$\cH$, consideramos o monômio
  $\prod_{i\in H}x_i$, e consideramos a soma de todos estes monômios.  Pomos
  \begin{multline}
    \label{eq:simplex}\qquad\quad
    \Delta=\Big\{\bfx=(x_i)_{1\leq i\leq n}\in\RR^n\:\\
      \sum\nolimits_{1\leq i\leq n}x_i=1\text{ e }
      x_i\geq0\text{ para todo~$i$}\Big\}\qquad\quad
  \end{multline}
  e
  \begin{equation}
    \label{eq:langrange_max}
    \lambda^*(\cH)=\sup\{\lambda_\cH(\bfx)\:\bfx\in\Delta\}.
  \end{equation}
  Para~$\bfx=(x_i)_{1\leq
    i\leq n}\in\RR^n$, seja
  \begin{equation}
    \label{eq:supp_def}
    \supp(\bfx)=\{i\in[n]\:x_i\neq0\}.
  \end{equation}
  Segue da compacidade de~$\Delta$ que~$\lambda^*(\cH)=\lambda_\cH(\bfx^*)$
  para algum~$\bfx^*=(x_i^*)_{1\leq i\leq n}\in\Delta$.  Podemos, ademais,
  escolher~$\bfx^*$ de forma que a cardinalidade de $\supp(\bfx^*)$ seja a
  menor possível.
  \begin{itemize}
  \item{}[Frankl e Rödl] Prove que para todo~$i$
    e~$j\in\supp(\bfx^*)$, existe~$H\in\cH$ tal que~$\{i,j\}\subset
    H\subset\supp(\bfx^*)$. 
  \end{itemize}

\item\label{Q:Motzkin}[Motzkin e Straus] (Continuação do Ex.~\ref{Q:lagrange})
  \begin{enumerate}
  \item[(\textit{i})]Mostre que~$\lambda^*(\cH)\geq|\cH|/n^k$.  
  \item[(\textit{ii})]Suponha agora que~$k=2$, isto é, estamos falando de
    grafos.  Seja~$\omega(H)$ o número máximo de vértices mutuamente adjacentes
    em~$H$, isto é, $\omega(H)=\max\{k\:\text{ $H$ contém $K^k$}\}$.  Mostre que 
    \begin{equation}
      \label{eq:lagrange_max_grafos}
      \lambda^*(H)\leq{1\over2}\(1-{1\over\omega}\).
    \end{equation}
  \item[(\textit{iii})] Deduza o seguinte corolário do teorema de Turán: para
    todo $t\geq1$, temos
    \begin{equation}
      \label{eq:weak_turan}
      \lim_{n\to\infty}\ex(n,K^{t+1}){n\choose2}^{-1}
      =1-{1\over t}.
    \end{equation}
  \end{enumerate}

\item{}[Lema de König] Nesta questão, consideramos árvores
  (infinitas).  Uma \textit{árvore}~$T$ é definida da seguinte forma
  recursiva: $T=(r;T_1,\dots,T_d)$, onde~$r$ é um \textit{vértice}
  distinguido, chamado de \textit{raiz}, e os~$T_i$ ($1\leq i\leq d$)
  são árvores não-vazias, chamadas de \textit{subárvores} de~$r$.  As
  raízes das subárvores~$T_i$ são chamados de \textit{filhos} de~$r$.
  O número~$d$ é chamado de \textit{grau} de~$r$ ($d$~pode ser~$0$).
  Assim, $r$ tem~$d$ filhos.  Um caminho (que parte da raiz de~$T$) é
  uma seqüência da forma~$r_0,r_1,\dots$, onde~$r_0$ é a raiz de~$T$
  e, em geral, $r_i$~é um filho de~$r_{i-1}$.  Dizemos que uma árvore
  é localmente finita se todo vértice tem um número finito de filhos
  (isto é, $d$~na definição acima é sempre um inteiro não-negativo).   

  Prove que uma árvore localmente finita que tem infinitos vértices
  tem um caminho infinito.   
  
\item Considere as seguintes asserções:
  \begin{enumerate}
  \item[(\textit{i})] Qualquer partição do conjunto dos números
    naturais em um número finito de partes é tal que alguma das partes
    contém progressões aritméticas (PAs) arbitrariamente longas.
  \item[(\textit{ii})] Para todo natural~$k\geq1$, vale que qualquer
    partição do conjunto dos números naturais em um número finito de
    partes é tal que alguma das partes contém uma PA com~$k$
    elementos.
  \item[(\textit{iii})] Para todos os naturais~$k\geq1$ e~$r\geq1$,
    existe um inteiro~$W$ tal que se~$[W]=W_1\cup\dots\cup W_r$ é uma
    partição arbitrária de~$[W]$, então para algum~$i$ a parte~$W_i$
    contém uma PA de~$k$ elementos.
  \end{enumerate}
  Prove que as asserções acima são equivalentes.  \sugestao{Use o Lema
    de König para mostrar que~(\textit{ii}) implica~(\textit{iii})}

\item\label{Q:deB-E}[de Bruijn e Erd\H os] Nesta questão, consideramos
  o número cromático de grafos infinitos.  Lembre que o número
  cromático~$\chi(G)$ de um grafo~$G$ é o número mínimo de cores com que
  podemos colorir os vértices de~$G$ de forma que quaisquer dois
  vértices da mesma cor não são adjacentes.
  \begin{enumerate}
  \item[(\textit{i})]Seja~$G$ um grafo com conjunto de
    vértices~$V(G)=\NN^*=\{1,2,\dots\}$ e com~$\chi(G)=q<\infty$.
    Prove que existe um subgrafo~$G'$ de~$G$ com um número finito de
    vértices e~$\chi(G')=q$.  Isto é, se todos os subgrafos finitos de
    um grafo infinito~$G$ são $(q-1)$-coloríveis, então~$G$ é
    $(q-1)$-colorível.  \sugestao{Use o Lema de König.
      Alternativamente, siga o roteiro a seguir.  Seja~$G_i$ o
      subgrafo de~$G$ induzido por~$[i]$ ($i\geq1$).  Suponha
      que~$\chi(G_i)<q$ para todo~$i$.  Fixe uma $(q-1)$-coloração
      própria de~$G_i$ para todo~$i$.  Para infinitos~$i$ (digamos,
      $i_1<i_2<\dots$), o vértice~$1$ de~$G$ recebe uma mesma cor nas
      $(q-1)$-colorações dos~$G_{i_1},G_{i_2},\dots$, digamos~$c_1$.
      Pinte o vértice~$1$ de~$G$ da cor~$c_1$.  Passamos a considerar
      os grafos $G_{i_1},G_{i_2},\dots$ no resto da prova.
      Ponha~$G_1^{(1)}=G_{i_1}$, $G_2^{(1)}=G_{i_2}$, etc.  Para
      infinitos~$i$ (digamos, $i_1^{(1)}<i_2^{(1)}<\dots$), o
      vértice~$2$ de~$G$ recebe uma mesma cor nas $(q-1)$-colorações
      dos~$G_{i_1}^{(1)},G_{i_2}^{(1)},\dots$, digamos~$c_2$.  Pinte o
      vértice~$2$ de~$G$ da cor~$c_2$.  Complete esta prova.}
    
  \item[(\textit{ii})]Considere agora o caso em que~$G$ acima tem
    conjunto de vértices~$\RR$ (e não mais~$\NN^*$).  Como seria o
    resultado análogo?  Como seria a prova?

  \end{enumerate}

\item Fixe um inteiro positivo~$n$.  Nesta questão, escrevemos~$\{x<y\}$ para
  um par de inteiros~$\{x,y\}$ com~$x<y$.  Considere o grafo~$\Gamma=\Gamma_n$
  cujos vértices são os pares~$\{x,y\}\subset[n]$ e cujas arestas são todos os
  pares de vértices da forma
  $$
  \big\{\{x<y\},\{y<z\}\big\}.
  $$
  ($\Gamma=\Gamma_n$ tem~${n\choose2}$ vértices e~${n\choose3}$ arestas.)
  Observe que~$\Gamma$ não tem triângulos.  Mostre que, dado qualquer
  inteiro~$k$, existe~$n_0$ tal que se~$n\geq n_0$, então o número cromático
  de~$\Gamma=\Gamma_n$ é pelo menos~$k$.  \datedue{15/10/2002}

\item Prove que existe uma coloração dos números naturais com azul e
  vermelho tal que nenhuma progressão aritmética infinita fica
  colorida com uma única cor.

\end{enumerate}  
 
\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: