%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC5827 Topicos de Matemática Discreta               %
% 2o. semestre de 2002                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 11 Dec 2002 12:37:31am BRST yoshi@ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

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

%\usepackage{refcheck}

\let\:=\colon
\let\epsilon=\varepsilon
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\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\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\barp{{\bar p}}

\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\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\bfx{\textbf{x}}
\def\bfy{\textbf{y}}

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

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

\begin{document}
\title[MAC5827 Matemática Discreta]{Exercícios de Matemática 
  Discreta\\2{\tiny o.} semestre de 2002} 
\date{Versão de \today}
\maketitle
\pagestyle{plain}
\footskip=20pt

\begin{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$).  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$.
  \datedue{22/8/2002}
  
\item($^+$) [Kleitman] Seja~$B$ um espaço normado.  (Se você não está
  familiarizado com espaços normados, suponha que~$B$ é o~$\RR^d$ para
  algum~$d$.)  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 B$ 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~$B$ é~$\RR$.
  
\item{}[Erd\H os--Szekeres] Prove que toda seqüência $a_0,\dots,a_{n^2}$ contém
  uma subseqüência monótona com~$n+1$ elementos, isto é, uma subseqüência
  não-crescente ou uma subseqüência não-decrescente com~$n+1$ elementos.  Mais
  precisamente, prove que existem~$0\leq i_0<\dots<i_n\leq n^2$ com
  $a_{i_0}\leq\dots\leq a_{i_n}$ ou com $a_{i_0}>\dots>a_{i_n}$.
  \datedue{27/8/2002} 
  
\item Seja~$P$ uma ordem parcial infinita que não contenha uma anticadeia com
  mais de~$m$ elementos ($m\in\NN$).  Deduza da versão finita do teorema de
  Dilworth que~$P$ pode ser coberta por uma família de~$m$ cadeias.
  \sugestao{Considere o espaço topológico compacto~$[m]^P$ das funções de~$P$
    em~$[m]=\{1,\dots,m\}$.  Caso você não tenha familiaridade com topologia
    (elementar), dê uma demonstração ``puramente combinatória'' para o caso em
    que~$P$ é enumerável.}
  
\item Fixe um inteiro positivo~$n$ e considere a ordem
  parcial~$P_n=([n],\preceq)$ sobre~$[n]$ com~$x\preceq y$ se e só se~$x$
  divide~$y$.  Encontre uma anticadeia~$A$ em~$P_n$ e uma partição em
  cadeias~$\cC$ de~$P_n$ com~$|A|=|\cC|$.  Deduza que~$A$ é máximo e~$|\cC|$ é
  mínimo e assim determine o valor de~$\alpha(P_n)=\beta(P_n)$.
  \datedue{29/8/2002}

\item\label{Q:Zarankiewicz}[Kövári, Sós, e Turán]
  \begin{enumerate}
  \item[(\textit{i})]Seja~$G=G^n$ um grafo $r$-regular (todos os vértices têm
    grau~$r$), com~$r\geq cn$ para alguma constante~$c>0$.  Conte o número de
    cópias do grafo~$K^{2}(1,s)$ em~$G$ e, usando que
    \begin{equation}
      \label{eq:simple_ineq}
      n{r\choose s}\geq s{n\choose s}\text{ para~$n\geq n_0(s,c)$,}
    \end{equation}
    deduza que se~$n$ é suficientemente grande, então~$G$ contém~$K^2(s,s)$.
    (Não deixe de provar~\eqref{eq:simple_ineq}.)
    
  \item[(\textit{ii})]Use as idéias em~(\textit{i}) e a desigualdade
    \begin{equation}
      \label{eq:Jensen}
      {1\over n}\sum_{x\in V(G)}{d(x)\choose s}
      \geq{n^{-1}\sum_{x\in V(G)}d(x)\choose s}
    \end{equation}
    para provar que~$\ex(n,H)=o(n^2)$ (isto é, $\lim_{n\to\infty}\ex(n,H)/n^2=0$)
    para todo grafo bipartido~$H$.  (Você sabe provar~\eqref{eq:Jensen}?)
  \item[(\textit{iii})]Conclua que~$\ex(n,H)=o(n^2)$ se e só se~$H$ é
    bipartido.
  \end{enumerate}\datedue{10/9/2002}
  
\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 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{Prove que
    $\ex(n,K^{(2)}(2,3))=O(n^{3/2})$ usando o método do
    Ex.~\ref{Q:Zarankiewicz} e use este resultado ($K^{(2)}(2,3)$ é o grafo
  bipartido completo com classes de vértices de cardinalidades~$2$ e~$3$).}
  \datedue{12/9/2002} 
  
\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}
    \datedue{17/9/02}
  \end{enumerate}

\item Para inteiros~$t\leq n$, ponha
  \begin{equation}
    \label{eq:max_t_inter}
    g(n,t)=\max|\cF|
  \end{equation}
  onde o máximo é tomado sobre todos os~$\cF\subset\cP([n])=2^{[n]}$ que são
  \textit{$t$-intersectantes}, isto é, para todo~$F$ e~$F'\in\cF$,
  temos~$|F\cap F'|\geq t$.  (Note que, aqui, não estamos considerando
  $r$-grafos para algum~$r$ fixo, mas sistemas de conjuntos sem restrição de
  cardinalidade para seus membros).
  \begin{enumerate}
  \item[(\textit{i})]Mostre que~$g(n,1)=2^{n-1}$.
  \item[(\textit{ii})]Mostre que, para todo inteiro~$t\geq2$,
    temos~$g(n,t)=(1+o(1))2^{n-1}$.  Isto é, prove que
    $\lim_{n\to\infty}g(n,t)2^{-n+1}=1$. \sugestao{Use a fórmula de Stirling 
      \begin{equation}
        \label{eq:Stirling}
        n!=(1+o(1))\(n\over e\)^n\sqrt{2\pi n}
      \end{equation}
      para provar que 
      \begin{equation}
        \label{eq:middle_bin}
        {n\choose\lfloor n/2\rfloor+k}=(1+o(1))2^n\sqrt{2\over\pi n}=o(2^n),
      \end{equation}
      para todo~$k\in\ZZ$ fixo.  Deduza que
      $$
      \sum_{k\geq(n+t)/2}{n\choose k}=(1+o(1))2^{n-1},
      $$
      e use esse fato.}  
  \end{enumerate}
  \datedue{19/9/2002}

\item\label{Q:num_crom}
    Provamos que, para todo primo~$p$, temos que o número cromático
  do~$\RR^n$ satisfaz
  \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}
  \begin{itemize}
  \item[(\textit{i})]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{ii})]Use a fórmula de Stirling~\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{iii})]Prove que o lado direito de~\eqref{eq:chromatic_lwbd} é
    pelo menos~$(1.139)^{4p-1}$ se~$p$ é suficientemente grande.
  \end{itemize}
  \datedue{24/9/2002}
  
\item\label{Q:TNP} O Exercício~\ref{Q:num_crom} mostra
  que~$c(4p-1)\geq(1.139)^{4p-1}$ para todo primo~$p$ suficientemente grande.
  Seja~$\pi(x)$ o número de números primos~$p\leq x$.  O bem conhecido teorema
  dos números primos diz que
  $$
  \lim_{x\to\infty}\pi(x){\log x\over x}=1.
  $$
  Use esse resultado para provar que~$c(n)\geq(1.13)^n$ para todo~$n$
  suficientemente grande.
  
\item\label{Q:Borsuk} Seja~$p$ um primo.  Construa um conjunto~$X$ de
  ${4p\choose2p}$ pontos em~$\RR^{4p-1}$ com a seguinte propriedade:
  \textsl{todo~$X'\subset X$ que não contém dois elementos ortogonais é tal
    que
    $$
    |X'|\leq2\sum_{0\leq j<p}{4p\choose j}.
    $$}\sugestao{Considere vetores com coordenadas~$\pm1$ em~$\RR^{4p}$ com o
    mesmo número de~$+1$s e~$-1$s.}  Use esse conjunto~$X$ para construir
  conjuntos~$Y\subset\RR^d$ que desprovam a conjectura de Borsuk,
  onde~$d={4p-1\choose2}$.  \sugestao{Considere a aplicação
    $$
    g\:(a_{ij})_{1\leq i,j\leq4p-1}\mapsto(a_{ij})_{1\leq i<j\leq4p-1},
    $$
    que leva matrizes $(4p-1)\times(4p-1)$ em matrizes triangulares
    superiores.}  \datedue{26/9/2002}
  
\item{}[Problema de Witsenhausen; Frankl e Wilson] Seja~$S^d\subset\RR^{d+1}$
  a esfera unitária em~$\RR^{d+1}$:
  $$
  S^d=\{\bfx\in\RR^{d+1}\:\|\bfx\|=1\}.
  $$
  Pomos
  \begin{equation}
    \label{eq:Witsenhausen_def}
    \mu(d)=\sup_E{\mu_d(E)\over\mu_d(S^d)},
  \end{equation}
  onde o supremo é tomado sobre todos os conjuntos (mensuráveis)~$E\subset
  S^d$ que não contêm dois vetores ortogonais, e~$\mu$ denota a medida de
  Lebesgue $d$-dimensional.  Mostre que~$\mu(d)\leq(1-\epsilon)^d$ para alguma
  constante absoluta~$\epsilon>0$.  \observacao{A única dificuldade desse
    exercício está na teoria da medida envolvida, pois tudo se resume em uma
    aplicação do teorema de Fubini.  Aqueles que não têm familiaridade
    suficiente com a teoria da medida podem dar um ``argumento informal'' para
    provar esse resultado.}

\item\label{Q:constructive_Ramsey}[Frankl e Wilson]
  \begin{itemize}
  \item[(\textit{i})]Seja~$\cA\subset{[n]\choose k}$ um sistema de
    $k$-conjuntos e~$L$ um conjunto de $s$~inteiros.  Suponha que, para
    todo~$A$ e~$A'\in\cA$ distintos, temos~$|A\cap A'|\in L$.  Prove que 
    \begin{equation}
      \label{eq:non_uniform_RW_weak}
      |\cA|\leq\sum_{0\leq j\leq s}{n\choose j}.
    \end{equation}
  \item[(\textit{ii})]Sejam~$p$ um primo e~$n$ um inteiro positivo, e
    considere o grafo completo~$K$ com conjunto de vértices
    \begin{equation}
      \label{eq:FW_V_def}
      V={[n]\choose p^2-1}.
    \end{equation}
    Pinte a aresta~$\{A,B\}$ de~$K$ de azul se
    \begin{equation}
      \label{eq:FW_edges_def}
      |A\cap B|\equiv-1\pmod p
    \end{equation}
    e de vermelho caso contrário.  Seja~$\alpha(n,p)$ o número máximo de
    vértices em um subgrafo completo vermelho em~$K$, e seja~$\omega(n,p)$ o
    número máximo de vértices em um subgrafo completo azul em~$K$.  Prove que
    se~$p-1\leq(n+1)/3$, então
    \begin{equation}
      \label{eq:FW_bounds}
      \alpha(n,p),\;\omega(n,p)<2{n\choose p-1}.
    \end{equation}
  \end{itemize}
  \datedue{3/10/2002}
  
\item (Continuação do Ex.~\ref{Q:constructive_Ramsey}) Use o teorema dos
  números primos (veja Ex.~\ref{Q:TNP}) e umas estimativas simples para
  coeficientes binomiais para mostrar que, escolhendo~$n=p^3$, a coloração
  definida acima prova (construtivamente!) o seguinte: \textsl{para todo~$\epsilon>0$,
    se~$t\geq t_0(\epsilon)$, o número de Ramsey~$R(t)$ satisfaz
    \begin{equation}
      \label{eq:FW_constructive}
      R(t)\geq\exp\left\{\({1\over4}-\epsilon\){(\log t)^2\over\log\log
          t}\right\}. 
    \end{equation}}%
  A cota inferior para~$R(t)$ em~\eqref{eq:FW_constructive} é a melhor que se
  sabe provar de forma construtiva.
  
\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\label{Q:deB-E}[de Bruijn e Erd\H os] Seja~$G=(V,E)$ um grafo e~$k$ um
  inteiro.  Suponha que~$\chi(G)\geq k$.  Prove que~$G$ contém um subgrafo
  \textit{finito}~$H$ com~$\chi(H)\geq k$.  Equivalentemente, mostre que
  existe~$W\subset V$ \textit{finito} com o grafo $G[W]$ induzido por~$W$
  em~$G$ tal que~$\chi(G[W])\geq k$.  O grafo~$G[W]$ tem, por definição,
  conjunto de vértices~$W$ e conjunto de arestas
  $$
  {W\choose2}\cap E.
  $$
  
\item\label{Q:Erdos-Hajnal}[Erd\H os e Hajnal] Fixe um inteiro~$d$ e um
  real~$\epsilon>0$.  O grafo de Borsuk~$B(d,\epsilon)$ tem como conjunto de
  vértices
  $$
  S^d=\{\bfx\in\RR^{d+1}\:\|\bfx\|=1\}
  $$
  e~$\{\bfx,\bfy\}\subset S^d$ é uma aresta de~$B(d,\epsilon)$ se
  $$
  \|\bfx-\bfy\|\geq2-\epsilon.
  $$
  Prove que para todo~$k$ e~$\ell$ inteiros, existem~$d$ e~$\epsilon>0$
  tais que~$B(d,\epsilon)$ tem número cromático~$\geq k$ e cintura
  ímpar~$\geq2\ell+1$.  A \textit{cintura ímpar~$\og(G)$} de um grafo~$G$ é o
  comprimento mínimo de um circuito de comprimento ímpar em~$G$:
  \begin{multline*}\quad
    \og(G)=\min\{2r+1\:\exists x_0,\dots,x_{2r}\in V(G)\text{ distintos}\\
    \text{com $\{x_{i-1},x_i\}\in E(G)$ para todo~$i$ (índices mod $2r+1$)}
    \}    
  \end{multline*}
  \sugestao{Use o teorema de Borsuk: \textsl{se cobrimos a esfera~$S^d$
      com~$d+1$ fechados (respectivamente, abertos), sempre há um par de
      pontos antípodas em um dos fechados (respectivamente, abertos).}}

  Deduza do Ex.~\ref{Q:deB-E} que~$B(d,\epsilon)$ (com~$d$ e~$\epsilon$
  apropriados) contém subgrafos finitos~$G$ com~$\chi(G)\geq k$
  e~$\og(G)\geq2\ell+1$.
  
\item (Continuação do Ex.~\ref{Q:Erdos-Hajnal}) Nesta questão, dizemos que um
  grafo~$G$ tem a propriedade~$P(c)$ se todo subgrafo~$H$ de~$G$ é tal
  que~$\alpha(H)\geq c|V(H)|$.
  \begin{enumerate}
  \item[(\textit{i})]Mostre que se~$G$ é tal que~$\chi(G)=k$, então~$G$ tem a
    propriedade~$P(1/k)$.
  \item[(\textit{ii})]Mostre que se~$G$ tem a propriedade~$P(1/2)$,
    então~$\chi(G)\leq2$.
  \item[(\textit{iii})]Mostre que para todo inteiro~$k$ e~$0<c<1/2$, existe um
    grafo~$G$ que tem a propriedade~$P(c)$ mas~$\chi(G)\geq k$.
    \sugestao{Mostre que~$B(d,\epsilon)$ com~$d$ e~$\epsilon$ apropriados é um
      tal grafo.}
  \end{enumerate}

\item Suponha que
  \begin{equation}
    \label{eq:p_def}
    p=p(n)={\log n+f\over n}, 
  \end{equation}
  onde~$f=f(n)$, e considere o grafo aleatório~$G(n,p)$.  Prove que as
  seguintes asserções valem para quase todo~$G=G(n,p)$.
  \begin{enumerate}
  \item[(\textit{i})] Se~$f=f(n)\to\infty$, então~$G$ não tem vértices isolados.
  \item[(\textit{ii})] Se~$f=f(n)\to-\infty$ e~$|f|\leq\log n$, então~$G$ tem
    vértices isolados.  De fato, o número de vértices isolados~$X=X(G)$ em~$G$
    satisfaz
    $$
    X\sim\exp\{-f\}.
    $$
  \item[(\textit{iii})] O que você consegue dizer sobre o caso em
    que~$f=f(n)\to f_0$ para alguma contante~$f_0$?
  \end{enumerate}
  \datedue{17/10/2002}
  
\def\PA{\text{PA}}

\item Considere~$[n]=\{1,\dots,n\}$ e suponha que sorteamos um subconjunto
  aleatório~$R$ de~$[n]$ colocando~$x\in[n]$ em~$R$ com probabilidade~$p$,
  independentemente para cada~$x$.  Considere a propriedade~$\PA_k$ de~$R$
  conter uma progressão aritmética de~$k$ elementos, onde~$k\geq3$ é um
  inteiro fixo, independente de~$n$.  Mostre que~$p^*=p^*(n)=n^{-2/k}$ é uma
  função limiar para a propriedade~$\PA_k$.  \datedue{22/10/2002}.

\item Considere a identidade
  \begin{equation}
    \label{eq:linha_Pascal}
    \sum_{0\leq k\leq n}{n\choose k}=2^n,
  \end{equation}
  e seja~$\omega=\omega(n)$ uma função com~$\omega\to\infty$
  conforme~$n\to\infty$.  Podemos dizer que a soma em~\eqref{eq:linha_Pascal}
  está `concentrada' nos termos com~$k$ satisfazendo
  \begin{equation}
    \label{eq:cond_k}
    \left|k-{n\over2}\right|\leq\omega\sqrt n,
  \end{equation}
  pois
  \begin{equation}
    \label{eq:concentracao}
    \sum_k\nolimits^*{n\choose k}\sim2^n,
  \end{equation}
  onde~$\sum_k^*$ indica soma sobre todos os~$k$
  satisfazendo~\eqref{eq:cond_k} e escrevemos~$f(n)\sim g(n)$
  se~$\lim_nf(n)/g(n)=1$.  
  
  Suponha agora que~$\epsilon>0$ é um número real fixo.  Podemos dizer que a
  soma em~\eqref{eq:linha_Pascal} está `exponencialmente concentrada' nos
  termos com~$k$ satisfazendo
  \begin{equation}
    \label{eq:cond_k2}
    \left|k-{n\over2}\right|\leq\epsilon n,
  \end{equation}
  pois
  \begin{equation}
    \label{eq:concentracao2}
    \sum_k\nolimits'{n\choose k}\leq2^n\exp\{-c_\epsilon n\},
  \end{equation}
  onde~$\sum_k'$ indica soma sobre todos os~$k$
  para os quais~\eqref{eq:cond_k2} \textit{não vale}, $c_\epsilon>0$ é uma
  constante que depende apenas de~$\epsilon$, e supomos~$n\geq
  n_0(\epsilon)$. 
  \begin{enumerate}
  \item[(\textit{i})]Prove~\eqref{eq:concentracao}.  
  \item[(\textit{ii})]Prove que a condição de que~$\omega\to\infty$ é
    necessária para que~\eqref{eq:concentracao} valha.  Para tanto, use a
    fórmula de Stirling~\eqref{eq:Stirling}.  
%     Uma versão desta fórmula é como
%     segue: para todo~$n\geq1$, existe~$\alpha_n$
%     com~$1/(12n+1)<\alpha_n<1/12n$ tal que
%     \begin{multline}
%       \label{eq:Stirling}
%       \hspace{2.5cm}n!=\sqrt{2\pi n}\(n\over\e\)^n\e^{\alpha_n}\\
%       =\sqrt{2\pi n}\(n\over\e\)^n\(1+{1\over12n}+O\(1\over n^2\)\).
%       \qquad
%     \end{multline}
    De fato, use~\eqref{eq:Stirling} para provar que se~$k=k(n)=n/2+c_n\sqrt
    n$, onde~$c_n\to c$ ($n\to\infty$) e~$c$ é uma constante, então
    \begin{equation}
      \label{eq:middle_binom}
      {n\choose k}={n!\over k!(n-k)!}\sim{d\over\sqrt n}2^n,
    \end{equation}
    onde~$d=d(c)>0$ é uma constante que depende apenas de~$c$.
  \item[(\textit{iii})]Prove~\eqref{eq:concentracao2}.  Qual é o maior valor
    de~$c_\epsilon$ com o qual você consegue provar~\eqref{eq:concentracao2}? 
  \end{enumerate}
  \sugestao{Considere um variável aleatória binomial~$X$ de parâmetros $n$
    e~$1/2$, de forma que~$\PP(X=k)={n\choose k}2^{-n}$.  Para~(\textit{i}),
    aplique a desigualdade de Chebyshev.  Para~(\textit{iii}), use uma
    desigualdade para grandes desvios.}
  \datedue{24/10/2002}
  
\item Prove as seguintes estimativas.  Nesta questão, escrevemos~$O(f(x))$
  para qualquer termo~$y$ tal que~$|y|\leq C|f(x)|$ para todo~$x$
  satisfazendo~$|x|\leq x_0$, onde~$C$ e~$x_0>0$ são constantes absolutas.
  (Observe que, nestas estimativas, estamos intessados em uma vizinhança
  de~$0$.)
  \begin{enumerate}
  \item[(\textit{i})]$1+x\leq\e^x$ para todo~$x\in\RR$.
  \item[(\textit{ii})]$1+x>\exp\big\{x-x^2/2\big\}$ para todo~$0<x\leq1$. 
  \item[(\textit{iii})]$1-x>\exp\big\{-x-x^2\big\}$ para todo~$0<x<x_0$,
    para algum~$x_0>0$.  De fato, podemos tomar, por exemplo,~$x_0=0{.}68$.  
  \item[(\textit{iv})]Prove que $1+x\geq\exp\{x/(1+x)\}$ para todo~$x>-1$.
  (Este item substituiu dois itens que constavam nesta lista anteriormente.) 
%   \item[(\textit{iv})]$1+x\geq\exp\big\{x+O(x^2)\big\}$ para todo~$x>-1$. 
%   \item[(\textit{v})]$1+x\geq\exp\big\{x-x^2/2+O(x^3)\big\}$ para
%     todo~$x>-1$.  
  \end{enumerate}
  [\textsl{Sugestão.} Lembre que~$1/(1-x)=1+x+x^2+\dots$ uniformemente
  se~$|x|\leq x_0$ e~$x_0<1$.  Integre ambos os lados para obter
  $$
  -\log(1-x)=x+{1\over2}x^2+{1\over3}x^3+\dots]
  $$
  
\item\label{Q:binom_bds} Prove as seguintes estimativas para~$a\choose b$,
  onde~$a$ e~$b$ são inteiros não-negativos.
  \begin{enumerate}
  \item[(\textit{i})]Se~$a\geq b$, então
    \begin{equation}
       \label{eq:binom_lwbd}
       {a\choose b}\geq\(a\over b\)^b.
    \end{equation}
     
  \item[(\textit{ii})]
    \begin{equation}
       \label{eq:binom_upbd1}
       {a\choose b}\leq{a^b\over b!}.
    \end{equation}

  \item[(\textit{iii})]Para todo~$b>0$, 
    \begin{equation}
       \label{eq:binom_upbd2}
       {a\choose b}\leq\(\e a\over b\)^b.
    \end{equation}
    [\textsl{Sugestão para~$(\text{\textit{iii}}\,)$.} Avalie~$(1+x)^a$ por
    cima e por baixo para~$x=b/a$.  Use, para tanto, $1+x\leq\e^x$ e o binômio
    de Newton: $(1+x)^a\geq{a\choose b}x^b$.]
  \end{enumerate}
  
\item\label{Q:Shamir-spencer} [Shamir--Spencer] Considere o grafo
  aleatório~$G=G(n,1/2)$, ou, equivalentemente, seja~$G$ um grafo
  escolhido uniformemente ao acaso dentre todos os grafos com~$n$ vértices
  fixos, digamos~$[n]$.  Defina
  \begin{equation}
    \label{eq:edge_blocks}
    A_i=\big\{\{i,j\}\:i<j\leq n\big\}
  \end{equation}
  e
  \begin{equation}
    \label{eq:2edge_blocks}
    \Gamma_i=2^{A_i}=\cP(A_i)
  \end{equation}
  para todo~$1\leq i<n$.  Note que os~$A_i$ ($1\leq i<n$)
  particionam~${[n]\choose2}$.  Assim, podemos identificar~$G$ com um
  vetor~$(X_1,\dots,X_{n-1})$, onde $X_i\in\Gamma_i$ para todo~$i$.  Note que
  os~$X_i$ ($1\leq i<n$) são independentes.  Como de usual, seja~$\chi(G)$ o
  número cromático de~$G$.
  \begin{enumerate}
  \item[(\textit{i})]Prove que~$\chi\:\prod_{1\leq i<n}\Gamma_i\to\RR$ é
    $1$-Lipschitz; note que isso equivale a dizer que para quaisquer dois
    grafos~$G$ e~$G'$ com conjunto de vértices~$[n]$, se~$E(G)\triangle
    E(G')=(E(G)\cup E(G'))\setminus(E(G)\cap E(G'))\subset A_i$ para
    algum~$i$, então~$|\chi(G)-\chi(G')|\leq1$.
    
  \item[(\textit{ii})]Seja~$\lambda=\lambda(n)$ uma função arbitrária
    com~$\lambda\to\infty$.  Mostre que~$\chi(G)$ está concentrada em uma
    faixa de largura~$2\lambda\sqrt n$ em torno de~$\EE(\chi)$, isto é, mostre
    que a probabilidade de termos
    \begin{equation*}
      |\chi(G)-\EE(\chi)|\leq\lambda\sqrt n
    \end{equation*}
    é~$1-o(1)$.
    
  \item[(\textit{iii})]Como de usual, seja~$\omega(G)$ o número de clique
    de~$G$, isto é, $\omega(G)$~é a cardinalidade máxima de um conjunto de
    vértices mutuamente adjacentes em~$G$.  Mostre que~$\omega(G)<2\log_2n$
    com probabilidade~$1-o(1)$, e conclua que~$\chi(G)>n/2\log_2n$ com
    probabilidade~$1-o(1)$.  \sugestao{Estime o valor esperado do número
      de~$U\subset[n]$, $|U|=\lceil2\log_2n\rceil$, com~${U\choose2}\subset
      E(G)$ (isto é, $U$~induz um clique).  Para tanto, use
      Ex.~\ref{Q:binom_bds}(\textit{iii}).}

  \item[(\textit{iv})]Observe que segue de~(\textit{ii}) e~(\textit{iii}) que
  $\chi(G)\sim\EE(\chi)$ com probabilidade~$1-o(1)$.
  \end{enumerate}
  \datedue{31/10/2002}
  
\item\label{Q:K3iso} Chamemos uma cópia de~$K^3$ (um triângulo) em um
  grafo~$G$ de \textit{isolado} se ele não tem aresta comum com nenhum outro
  triângulo.  Seja~$Y$ o número conjuntos~$U\in{[n]\choose3}$ que induzem um
  triângulo isolado no grafo aleatório~$G(n,p)$.  Mostre
  que~$\EE(Y)\geq(1/6-o(1))n^3p^3$ se~$p=\lambda n^{-2/3}$
  com~$\lambda=\lambda(n)\to\infty$, mas, digamos, $\lambda\ll n^{1/6}$.
  \sugestao{Seja~$X$ o número de~$U\in{[n]\choose3}$ que induzem um triângulo
    em~$G(n,p)$ e seja~$Z$ o número de $W\in{[n]\choose4}$ que induzem pelo
    menos~$5$ arestas.  Note que~$Y\geq X-4Z$.}\footnote{Os enunciados dos
    Ex.~\ref{Q:K3iso}--\ref{Q:large_chi3} ainda podem sofrer certa revisão.}
  
\item\label{Q:better_exp} Considere o grafo aleatório~$G(n,p)$ com~$p=\lambda
  n^{-2/3}$, com~$\lambda=\lambda(n)\to\infty$ e $\lambda\ll n^{1/6}$, e
  sejam~$X$ e~$Y$ como no Ex.~\ref{Q:K3iso}.  Prove que
  \begin{equation}
    \label{eq:prob_non-contain}
    \PP(X=0)\leq\PP(Y=0)\leq\exp\left\{-c\lambda^6\right\}
  \end{equation}
  para uma constante~$c>0$.  \sugestao{Observe que~$Y$ é $1$-Lipschitz.}
  \textbf{Observação.}  Infelizmente, a sugestão não está correta (você vê o
  motivo?).  Chamemos uma família de triângulos de \textit{independente} se
  quaisquer dois triângulos nesta família não têm aresta comum.  Seja~$Y'$ a
  cardinalidade máxima de uma família independente de triângulos.
  \textit{Mostre que~$Y'$ é $1$-Lipschitz}.  Use esse fato para provar que
  \begin{equation}
    \label{eq:prob_non-containB}
    \PP(X=0)\leq\exp\left\{-c\lambda^6\right\}
  \end{equation}
  para alguma constante~$c>0$.
  \datedue{5/11/2002}
  
\item\label{Q:Luczak}[\L uczak] (Continuação do Ex.~\ref{Q:better_exp}) A cota
  superior para~$\PP(X=0)$ do Ex.~\ref{Q:better_exp} pode ser melhorada para
  \begin{equation}
    \label{eq:prob_non-containLuczak}
    \PP(X=0)\leq\exp\left\{-cn^3p^3\right\}
  \end{equation}
  para alguma constante~$c>0$, desde que, digamos, $p\ll1/\sqrt n$. Eis um
  roteiro da prova\footnote{Eu ficaria contente se alguém pudesse verificar
    este roteiro.}: inicialmente, fixe uma coloração
  $\gamma\:{[n]\choose2}\to[f]$ de~${[n]\choose2}$ com~$f$ cores, onde~$f\sim
  Cn^3p^3$ e~$C$ é uma constante convenientemente grande, e
  $|\gamma^{-1}(i)|\leq n^2/f$ para todo~$i$ (isto é, cada cor é usada no
  máximo~$n^2/f$ vezes).
  
  Defina uma cópia~$H$ de~$K^3$ em~$G(n,p)$ como \textit{$\gamma$-isolada} se
  as cores que ocorrem nas três arestas de~$H$ não ocorrem em nenhuma outra
  cópia~$H'$ de~$K^3$ em~$G(n,p)$ com~$E(H')\cap E(H)=\emptyset$.
  Seja~$Y_\gamma$ o número de cópias isoladas de~$K^3$ em~$G(n,p)$.
  \begin{enumerate}
  \item[(\textit{i})] Prove que
    \begin{equation}
      \label{eq:EEiso_lwbd}
      \EE(Y_\gamma)\geq c_1n^3p^3
    \end{equation}
    para alguma constante~$c_1>0$ desde que~$C$ seja suficientemente grande.
    \sugestao{Sejam~$X$ e~$Z$ como no Ex.~\ref{Q:K3iso}.
      Como~$\EE(Z)\ll\EE(X)$, podemos ignorar cópias de~$K^3$ que não são
      isoladas (no sentido do Ex.~\ref{Q:K3iso}).  Seja agora~$Z_\gamma$ o
      número de pares~$(H,H')$ de cópias de~$K^3$ em~$G(n,p)$, com $E(H)\cap
      E(H')=\emptyset$ e com alguma aresta em~$H$ e alguma aresta em~$H'$ da
      mesma cor (isto é, ambos~$H$ e~$H'$ encontram um mesmo~$\gamma^{-1}(i)$
      para algum~$i$).  Você pode estimar~$\EE(Z_\gamma)$ por
      \begin{equation*}
        O\(f{n^2/f\choose2}n^2p^4\)=O\(n^3p^3/C\).
      \end{equation*}
      Conclua~\eqref{eq:EEiso_lwbd}.}
  \item[(\textit{ii})] Ponha
    agora~$\Gamma_i=2^{\gamma^{-1}(i)}=\cP(\gamma^{-1}(i))$ ($1\leq i\leq f$).
    Observe que~$G(n,p)$ pode ser identificado com um vetor $(X_1,\dots,X_f)$
    com os~$X_i\in\Gamma_i$ para todo~$i$ e com os~$X_i$ independentes.  Prove
    que~$Y_\gamma$ é $1$-Lipschitz, no sentido que se temos dois grafos~$G$
    e~$G'$ com~$E(G)\triangle E(G')=(E(G)\cup E(G'))\setminus(E(G)\cap
    E(G'))\subset\gamma^{-1}(i)$ para algum~$i$, então
    $|Y_\gamma(G)-Y_\gamma(G')|\leq1$.
  \item[(\textit{iii})] Conclua~\eqref{eq:prob_non-containLuczak}.
  \end{enumerate}
  
\item\label{Q:large_chi3} Dado um grafo~$G$, seja~$\chi_3(G)$ o número mínimo
  de partes em que podemos particionar o conjunto de vértices de~$G$ de forma
  que cada uma das partes não induza triângulos.  Equivalentemente,
  $\chi_3(G)=k$ se podemos colorir os vértices de~$G$ com~$k$ cores de forma
  que nenhum triângulo fique monocromático (tenha seus~$3$ vértices da mesma
  cor), mas~$k-1$ cores não bastam.\footnote{Definindo~$\chi_2(G)$ de forma
    análoga, $\chi_2(G)=\chi(G)$, o número cromático usual de~$G$.}  Prove
  que, para todo inteiro~$k$, existe um grafo~$G$ que não contém~$K^4$, mas
  temos $\chi_3(G)\geq k$.  \sugestao{Considere~$G(n,p)$ com~$p=\lambda
    n^{-2/3}$ com~$\lambda=\lambda(n)$ apropriado.
    Use~\eqref{eq:prob_non-containLuczak} para mostrar que, com
    probabilidade~$1-o(1)$, conjuntos que não induzem~$K^3$ em~$G(n,p)$ são de
    cardinalidade~$o(n)$.  Altere~$G(n,p)$ de forma apropriada para obter~$G$
    como no enunciado.}  \datedue{5/11/2002}
  
\item\label{Q:Talagrand} Seja~$G=G^n$ um grafo com~$n$ vértices e grau máximo 
  $$
  \Delta=\Delta(G)=\max\{\deg(x)\:x\in V(G)\}.
  $$
  Seja~$m=|E(G)|$ o número de arestas em~$G$.  Seja~$0<p=p(n)<1$ e suponha
  que escolhemos um conjunto aleatório~$W\subset V(G)$ pondo $\PP(x\in W)=p$,
  independetemente para todo~$x\in V(G)$.  Seja~$Y$ o número de arestas
  induzidas por~$W$, isto é,
  $$
  Y=\left|E(G)\cap{W\choose2}\right|.
  $$
  Ponha~$\mu=\EE(Y)$.  
  \begin{enumerate}
  \item[(\textit{i})]Observe que~$\mu=p^2m$.  Observe também que~$Y$ é
    $\Delta$-Lipschitz, isto é, se~$W\triangle W'=(W\setminus
    W')\cup(W'\setminus W)$ é unitário, então~$|Y(W)-Y(W')|\leq\Delta$.

  \item[(\textit{ii})]Deduza que, para todo~$t\geq0$, temos
    \begin{equation}
      \label{eq:bounded_diffs}
      \PP(|Y-\mu|\geq t)\leq2\exp\{-t^2/2\Delta^2n\}.
    \end{equation}

  \item[(\textit{iii})]Prove que, para alguma constante universal~$c>0$,
    \begin{equation}
      \label{eq:Talagrand}
      \PP(|Y-\mu|\geq t)\leq4\exp\{-ct^2/\Delta^2(\mu+t)\}
    \end{equation}
    para todo~$t\geq0$.  \sugestao{Note que, para todo inteiro~$r\geq1$, a
      desigualdade~$Y\geq r$ pode ser justificada por um certificado de
      ``tamanho'' no máximo~$2r\Delta^2$; isto é, tome $\psi(r)=2r\Delta^2$.}
    
  \item[(\textit{iv})]Suponha agora que~$G$ é $d$-regular, isto é, todos os
    seus vértices têm grau~$d$.  Deduza de~\eqref{eq:bounded_diffs}
    e~\eqref{eq:Talagrand} que se
    $$
    p\gg\min\{n^{-1/4},\sqrt{d/n}\}, 
    $$
    então~$Y\sim\mu$ com probabilidade~$1-o(1)$; isto é, para alguma
    função~$g(n)\to0$, temos
    $$
    \lim_{n\to\infty}\PP(|Y/\mu-1|\leq g(n))=1.
    $$
  \end{enumerate}
  \datedue{19/11/2002}
  
\item\label{Q:Janson}[Janson] Este exercício ilustra uma forma alternativa de
  se provar o resultado no Ex.~\ref{Q:Luczak}.
  \begin{enumerate}
  \item[(\textit{i})]Prove~\eqref{eq:prob_non-containLuczak} usando a
    desigualdade de Janson.  Mais explicitamente, mostre que existe uma
    constante absoluta~$c>0$ tal que se~$p\ll 1/\sqrt n$,
    então~\eqref{eq:prob_non-containLuczak} vale.
    
  \item[(\textit{ii})]Suponha agora que~$p\gg1/\sqrt n$.  Mostre que a
    desigualdade~\eqref{eq:prob_non-containLuczak} não vale.  Mostre,
    entretanto, que
    $$
    \PP(X=0)\leq\exp\{-cpn^2\}
    $$
    para alguma constante~$c>0$.  Prove ainda que
    $$
    \PP(X=0)\geq\exp\{-c'pn^2\}
    $$
    para alguma constante~$c'>0$.
  \end{enumerate}
  \datedue{19/11/2002}
  
\item\label{Q:Kleitman}[Kleitman] Suponha que~$\cF$, $\cG$, $\cH$, e~$\cI$ são
  sistemas de conjuntos sobre o conjunto~$X=[n]$, isto é, $\cF$, $\cG$, $\cH$,
  e~$\cI\subset2^X=\cP(X)$.  Suponha ainda que~$\cF$ e~$\cG$ são ``fechados
  por se tomar subconjuntos'' e~$\cH$ e~$\cI$ são ``fechado por se tomar
  superconjuntos''.  Isto é, se $F\subset F'\in\cF$, então~$F\in\cF$ e
  analogamente para~$\cG$; enquanto que se $H\subset H'$ e~$H\in\cH$,
  então~$H'\in\cH$ e analogamente para~$\cI$.  Prove que
  \begin{align}
    |\cF\cap\cG|&\geq2^{-n}|\cF||\cG|,\label{eq:Kleitman}\\    
    |\cH\cap\cI|&\geq2^{-n}|\cH||\cI|,\label{eq:Kleitman2}
   \end{align}
  e
  \begin{align}
    \label{eq:Kleitman3}    
    |\cF\cap\cH|&\leq2^{-n}|\cF||\cH|.
   \end{align}
   \sugestao{É suficiente provar, por exemplo, \eqref{eq:Kleitman3}.  Para
     tanto, fixe um~$x\in X$ e considere os membros de~$\cF$ e~$\cH$ que
     contêm~$x$ e os membros de~$\cF$ e~$\cH$ que não contêm~$x$
     separadamente, e use indução em~$n=|X|$.}
   
 \item\label{Q:Janson0}[Janson, \L uczak, e Ruci\'nski]
   Sejam~$\cS\subset\cP([n])=2^{[n]}$,
   $$
   X_S=[S\subset\Gamma_{p_1,\dots,p_n}],
   $$
   e~$X=\sum_{S\in\cS}X_S$, como em sala.  Seja
   ainda~$\Delta=\sum_{A,B}\EE(X_AX_B)$, onde a soma é sobre os pares
   ordenados~$(A,B)\in\cS\times\cS$ com~$A\neq B$ e~$A\cap B\neq\emptyset$.
  \begin{enumerate}
  \item[(\textit{i})]Ponha~$\Psi(s)=\EE(e^{-sX})$, para todo~$s\geq0$.  Prove
    que
    \begin{equation}
      \label{eq:Janson0a}
      \log\PP(X=0)=\int_0^\infty(\log\Psi(s))'\,ds.
    \end{equation}
  \item[(\textit{ii})]Seja~$Y_A=\sum_BX_B$, onde a soma é sobre todos
    os~$B\in\cS$ com $A\cap B\neq\emptyset$.
    Prove que
    \begin{equation}
      \label{eq:Janson0b}
      \int_0^\infty\EE(e^{-sY_A}\mid X_A=1)\,ds=\EE(1/Y_A\mid X_A=1). 
    \end{equation}
  \item[(\textit{iii})]Seja~$Y_A'=Y_A-X_A$.  Use que~$1/(1+y')\geq1-y'/2$
    para~$y'\geq1$ para deduzir que
    \begin{equation}
      \label{eq:Janson0c}
      \sum_{A\in\cS}\PP(X_A=1)\EE(1/Y_A\mid X_A=1)
      \geq\mu-\Delta,
    \end{equation}
    onde~$\mu=\EE(X)$.
  \item[(\textit{iv})]Finalmente, lembre que provamos que
    \begin{equation}
      \label{eq:Afirmacao}
      -(\log\Psi(s))'\geq\sum_{A\in\cS}\PP(X_A=1)\EE(e^{-sY_A}\mid X_A=1). 
    \end{equation}
    Deduza de~\eqref{eq:Janson0a}--\eqref{eq:Afirmacao} que
    \begin{equation}
      \label{eq:Janson0_ineq}
      \PP(X=0)\leq e^{-\mu+\Delta}.
    \end{equation}
  \end{enumerate}\datedue{21/11/2002}
  
\item Vimos dois teoremas de Roth.  A grosso modo, estes resultados podem ser
  enunciados da seguinte forma: (\textit{i})~Para qualquer~$A\subset[N]$,
  existe uma progressão aritmética~$P\subset[N]$ para o qual a discrepância
  $$
  \big||A\cap P|-\eta|P|\big|,
  $$
  onde~$\eta=|A|/N$, é `grande'.  (\textit{ii})~Para qualquer
  conjunto~$A\subset[N]$ com~$|A|/N\geq\eta$, onde~$\eta>0$ é uma constante
  positiva, se~$N\geq N_0(\eta)$, então~$A$ contém uma progressão aritmética
  com três elementos.  Escreva a prova destes dois resultados em um único
  texto, de forma organizada, destacando os princípios comuns e as
  tecnicalidades específicas de cada uma das
  demonstrações.  \datedue{10/12/2002} 

\end{enumerate}  
 
\end{document}

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

