%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC5775 Métodos Probabilísticos I                    %
% 1o. semestre de 2009                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 16 Jun 2009 12:51:53am BRT yoshi@turan.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

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

%\usepackage{refcheck}
\usepackage{srcltx}

\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\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim
\def\indarrow{{\displaystyle
  \mathrel{\mathop{\longrightarrow}\limits^{\hbox{\tiny ind}}}}}

\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\cK{\mathcal K}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}
\def\cZ{\mathcal Z}

\def\tG{\widetilde G}
\def\tcG{\widetilde\cG}

\def\barp{{\bar p}}

\def\Ave{\mathop{{\rm Ave}}}
\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\bfp{\textbf{p}}
\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[MAC5775 Métodos Probabilísticos]{Exercícios de Métodos Probabilísticos
  I\\1{\tiny o.} semestre de 2009}  
\date{Versão de \today}
\maketitle
\pagestyle{plain}
\footskip=25pt

\begin{enumerate}
  
\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$.
  \end{enumerate}\datedue{10/3/2009}

  \noindent [\textit{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}
    [\textit{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$.]

  \item[(\textit{iv})]Prove a seguinte versão mais forte de~(\textit{iii}):
  se~$b\leq a$, então
    \begin{equation}
       \label{eq:binom_upbd3}
       \sum_{0\leq j\leq b}{a\choose j}\leq\(\e a\over b\)^b.
    \end{equation}
  \end{enumerate}\datedue{10/3/2009}
  
\item A fórmula de Stirling diz que 
  \begin{equation}
    \label{eq:Stirling}
    n!=(1+o(1))\(n\over\e\)^n\sqrt{2\pi n},
  \end{equation}
  onde~$o(1)\to0$ conforme~$n\to\infty$.  
  \begin{enumerate}
  \item[(\textit{i})] Prove que, para todo~$\ell$ fixo, independente de~$n$, temos
    \begin{equation}
      \label{eq:middle_bin}
      {n\choose\lfloor n/2\rfloor+\ell}=(1+o(1))2^n\sqrt{2\over\pi n}.
    \end{equation}
    
  \item[(\textit{ii})] Prove 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 que, para todo~$0<\alpha<1$ fixo, temos 
    \begin{equation}
      \label{eq:entropy_binom}
      {n\choose\lfloor\alpha
      n\rfloor}=\(1\over\alpha^\alpha(1-\alpha)^{1-\alpha}\)^{(1+o(1))n}, 
    \end{equation}
    ou, equivalentemente,
    \begin{equation}
      \label{eq:entropy_binom.2}
      \lim_{n\to\infty}{1\over n}\log{n\choose\alpha n}=H(\alpha),
    \end{equation}
    onde~$H(\alpha)=\alpha\log(1/\alpha)+(1-\alpha)\log(1/(1-\alpha))$ é a
    assim chamada função entropia.
  \end{enumerate}\datedue{10/3/2009}
  
\item{}[Shearer] Defina $d_{i}(x)$ como o número de vértices à distância~$i$
  de~$x$.  Por exemplo, $d_{1}(x) = d(x)$.  Seja~$G$ um grafo livre de
  triângulos.  
  \begin{itemize}
  \item[(\textit{i})] Prove que
    \begin{equation}
      \alpha(G) \geq \sum_{v \in V_{G}}
      \frac{d_{1}(v)}{1+d_{1}(v)+d_{2}(v)}.
      \label{eq:shearer1}
    \end{equation} 
  \item[(\textit{ii})] Seja~$G$ um grafo livre de~$C^3$ e~$C^5$ (isto é,
    $G$~não contém circuitos de comprimento~$3$ e~$5$).  Deduza
    de~(\textit{i}) que
    \begin{equation}
      \alpha(G) \geq \sqrt{n\overline{d}/2} = \sqrt{|E(G)|},
    \end{equation}
    onde $\overline{d} = 2|E(G)|/|V(G)|$ é o grau médio de~$G$.
  \end{itemize}
  \datedue{17/3/2009}
  
\item{}[Tuza] Sejam $(A_{1},B_{1}), \ldots, (A_{m},B_{m})$ pares de conjuntos
  finitos com $A_{i} \cap B_{i} = \emptyset$ para todo~$i$ e com $A_{i} \cap
  B_{j} \neq \emptyset$ ou $A_{j} \cap B_{i} \neq \emptyset$ para todo~$i \neq
  j$.  Se $|A_i| \leq a$ e $|B_{i}| \leq b$ para todo~$i$, prove
  que
  \begin{equation}
    m \leq \frac{(a+b)^{a+b}}{a^{a}b^{b}}.
  \end{equation}\hint{Prove que, para qualquer $0 < p < 1$, tem-se
    \begin{equation}
      \sum_{i=1}^{m} p^{|A_i|}{(1-p)}^{|B_i|}\leq 1.
    \end{equation}
    Utilize essa cota para derivar o resultado.}
  \datedue{17/3/2009}

\item{}[Katona, Nemetz, e Simonovits] Seja~$\cF$ um $r$-grafo.
  \begin{itemize}
  \item[(\textit{i})] Suponha
    que~$\ex(n_0,\cF)\leq M_0$.  Prove que, para todo~$n\geq n_0$, temos
    \begin{equation}
      \label{eq:KNSi.1}
      \ex(n,\cF)\leq M_0{n_0\choose r}^{-1}{n\choose r}.
    \end{equation}
  \item[(\textit{ii})] Deduza de~(\textit{i}) que
    \begin{equation}
      \label{eq:KNSi.2}
      \lim_{n\to\infty}\ex(n,\cF){n\choose r}^{-1}
    \end{equation}
    existe.
  \end{itemize}
  \datedue{17/3/2009}

\item Seja
  \begin{equation}
    \label{eq:Turan_const.1}
    \tau(r,k)=\lim_{n\to\infty}\ex(n,\cK_k^{(r)}){n\choose r}^{-1}.
  \end{equation}
  Prove que
  \begin{equation}
    \label{eq:Turan_const.2}
    {5\over9}\leq\tau(3,4)\leq{7\over10}.
  \end{equation}

\item Seja~$\cK^4_-$ o $3$-grafo de ordem~$4$ com~$3$ triplas, e
  seja~$\cK^4_{--}$ o $3$-grafo de ordem~$4$ com~$2$ triplas.  
  \begin{itemize}
  \item[(\textit{i})] Prove que $\ex(n,\cK^4_{--})\leq(1/3){n\choose2}$.
  \item[(\textit{ii})] Prove que
    \begin{equation}
      \label{eq:tournament}
      \lim_{n\to\infty}\ex(n,\cK^4_-){n\choose r}^{-1}\geq{1\over4}.
    \end{equation}\hint{Considere um torneio aleatório~$T$ de ordem~$n$.
      Defina um $3$-grafo a partir de~$T$, definindo como hiperarestas as
      triplas que definem triângulos orientados de forma cíclica.  Um
      \textit{torneio} é uma orientação do grafo completo (portanto,
      existem~$2^{n\choose2}$ torneios de ordem~$n$ e~$T$ é escolhido
      uniformente ao acaso dentre todos esses torneios).}
  \item[(\textit{iii})] Dê uma cota superior não-trivial e interessante(!)
    para o limite em~\eqref{eq:tournament}.
  \item[(\textit{iv})] Seja~$\cF(r,s)$ o $r$-grafo de ordem~$2r-s$
    constituído de duas hiperarestas com interseção de cardinalidade~$s$.
    Prove 
    \begin{equation}
      \label{eq:packing}
      \ex(n,\cF(r,s))\leq{n\choose s}{r\choose s}^{-1}.
    \end{equation}
    Observe que~\eqref{eq:packing} generaliza~(\textit{i}).
  \end{itemize}
  \datedue{17/3/2009}
  
\item Seja~$\cH^k$ o conjunto dos grafos de ordem~$k$ (a menos de
  isomorfismo).  Dizemos que um grafo~$G$ é \textit{$k$-universal} se~$G$
  contém todos os grafos de ordem~$k$ como subgrafos induzidos, isto é, para
  cada~$H\in\cH^k$, existe um subgrafo induzido~$\widetilde H$ de~$G$ que é
  isomorfo a~$H$.  Seja
  \begin{equation}
    \label{eq:univ_def}
    f(n)=\max\{k\:\text{existe um grafo $k$-universal~$G$ de ordem~$n$}\}.
  \end{equation}
  \begin{itemize}
  \item[(\textit{i})] Prove que~$|\cH^k|\geq2^{k\choose2}/k!$.
  \item[(\textit{ii})] Deduza de~(\textit{i}) que $f(n)\leq2\log_2n+O(1)$.  
  \item[(\textit{iii})] Prove que existe um~$n_0$ tal que, para todo~$n\geq
    n_0$, temos
    \begin{equation}
      \label{eq:univ_bd}
      f(n)\geq\log_2n-\log_2\log n-\log_2\log_2n.
    \end{equation}
    \hint{Dizemos que um grafo~$G$ tem a propriedade~$\cP_k$ se, para
      quaisquer $k$-vértices distintos~$x_1,\dots,x_k$ de~$G$ e~$0\leq
      h\leq k$, existe um vértice~$y$ em~$G$ tal que~$y$ é adjacente a~$x_i$
      para todo~$0\leq i\leq h$ e~$y$ não é adjacente~$x_i$ para todo~$h<i\leq
      k$.  Prove que a.q.t.~$G_{1/2}=G(n,1/2)$ tem a propriedade~$\cP_k$
      para~$k=\lfloor\log_2n-\log_2\log n-\log_2\log_2n\rfloor$.}
  \end{itemize}
  \datedue{27/3/2009}

\item Prove que grafos completos, circuitos e árvores são grafos balanceados. 
  
\item Seja~$H$ um grafo de ordem positiva e seja~$d(H)=e(H)/v(H)$ a densidade
  de~$H$.  Seja também
  \begin{equation}
    \label{eq:cP_H_def}
    \cP_H=\{G\:\text{$G$ contém~$H$ como subgrafo}\}. 
  \end{equation}
  \begin{itemize}
  \item[(\textit{i})] Um teorema de Erd\H os e Rényi afirma
    que~$p_0=p_0(n)=n^{-1/d(H)}$ é uma função limiar para a
    propriedade~$\cP_H$ se~$H$ é balanceado.  Dê uma família ``grande'' de
    grafos conexos~$H$ que mostram que a hipótese de~$H$ ser balanceado neste
    teorema é essencial.
    
  \item[(\textit{ii})] Dê um bom candidato a função limiar para a
    propriedade~$\cP_H$ no caso geral, em que~$H$ não é necessariamente
    balanceado.  Mostre ao menos algumas (``boas'') propriedades deste seu
    candidato para justificar sua escolha.  \hint{Lembre que
      $m(H)=\max\{d(J)\:J\subset H\text{, }v(J)>0\}$ e considere este
      parâmetro.}
  \end{itemize}
  \datedue{31/3/2009}
  
\item Seja~$\cP$ uma propriedade de grafos monótona crescente.
  \begin{itemize}
  \item[(\textit{i})] Sejam~$0\leq M_1=M_1(n)\leq M_2=M_2(n)\leq{n\choose2}$.
    Prove que 
    \begin{equation}
      \label{eq:incr_G(n,M)}
      \PP(G(n,M_1)\in\cP)\leq\PP(G(n,M_2)\in\cP).
    \end{equation}
    
  \item[(\textit{ii})] Sejam~$0\leq p_1=p_1(n)<p_2=p_2(n)\leq1$ e suponha
    que~$\cP$ seja não-trivial.  Mostre que, para todo~$n$ suficientemente
    grande, temos
    \begin{equation}
      \label{eq:strict_incr}
      \PP(G(n,p_1)\in\cP)<\PP(G(n,p_2)\in\cP).
    \end{equation}
    Isto é, no espaço~$\cG(n,p)$, a função
    $\phi_n^\cP\:p\mapsto\PP(G(n,p)\in\cP)$ é estritamente crescente para
    todo~$n$ suficientemente grande.

  \item[(\textit{iii})] Vale um resultado análogo a~(\textit{ii}) no
    espaço~$\cG(n,M)$? 

  \end{itemize}
  \datedue{3/4/2009}
  
\item Uma versão bastante precisa da fórmula de Stirling, devido a
  Robbins~(1955), é que, para todo~$n=1,2,\dots$,
  \begin{equation}
    \label{eq:Stirling_Robbins}
    n!=\(n\over\e\)^n(2\pi n)^{1/2}\e^{\alpha(n)},
  \end{equation}
  onde
  \begin{equation}
    \label{eq:Stirling_Robbins.2}
    {1\over12n+1}<\alpha(n)<{1\over12n}.
  \end{equation}
  Prove as seguintes desigualdades para o coeficiente binomial: 
  \begin{multline}
    \label{eq:binom+Stirling}
    \qquad\e^{-1/6k}{n^n\over k^k(n-k)^{n-k}}
    \(n\over2\pi k(n-k)\)^{1/2}
    \leq{n\choose k}\\
    \leq{n^n\over k^k(n-k)^{n-k}}
    \(n\over2\pi k(n-k)\)^{1/2}.
  \end{multline}
  
\item\label{Q:Pittel} Seja~$\cP$ uma propriedade qualquer de grafos e
  sejam~$0<p=M/N=M{n\choose2}^{-1}<1$ e~$q=1-p$.  Prove que
  \begin{multline}
    \label{eq:Pittel}
    \qquad\PP(G(n,M)\in\cP)\leq\PP(G(n,p)\in\cP)\e^{1/6M}(2\pi pqN)^{1/2}\\
    \leq3M^{1/2}\PP(G(n,p)\in\cP).
  \end{multline}
  \hint{Use que
    \begin{multline}
      \label{eq:hint_Pittel}
      \qquad\PP(G(n,p)\in\cP)=\\\sum_t\PP(G(n,p)\in\cP\mid
      e(G(n,p))=t)\PP(e(G(n,p))=t)
    \end{multline}
    e que~\eqref{eq:binom+Stirling} fornece uma cota inferior adequada
    para~$\PP(e(G(n,p))=t)$ para~$t=M$.}  \datedue{14/4/2009}

\item 
  \begin{itemize}
  \item[(\textit{i})] A \textit{fórmula de Cayley} diz que há~$k^{k-2}$
    árvores rotuladas de ordem~$k$.  Prove que a probabilidade de~$G(n,p)$
    ter um componente de ordem~$k$ é no máximo
    \begin{equation}
      \label{eq:order_k_component}
      {n\choose k}k^{k-2}p^{k-1}\e^{-pk(n-k)}.
    \end{equation}
  \item[(\textit{ii})] Seja~$\omega=\omega(n)=\log\log\log n$ e
    seja~$t=\lfloor(n/2)(\log n-\omega)\rfloor$.  Mostre que
    a.q.c.~$G(n,t)\in\cG(n,t)$ é constituído de um componente de
    ordem~$(1-o(1))n$ e de vértices isolados.  \hint{Trabalhe com~$G(n,p)$
      com~$p$ adequado e use o resultado do Exercício~\ref{Q:Pittel}.}
  \item[(\textit{iii})] Consideramos agora
    processos~$\tG=(G_t)_{t=0}^N\in\tcG(n)$.  Prove que a.q.c.~$\tG$ é tal que
    \begin{equation}
      \label{eq:conn_hitting_time}
      \tau(\tG;\text{conn})=\tau(\tG;\delta\geq1).
    \end{equation}
    Isto é, a.q.c., no momento em que os vértices isolados desaparecem, o
    grafo~$G_t$ torna-se conexo.  \hint{De acordo com~(\textit{ii}),
      a.q.c.~$\tG$ é tal que, um pouco antes de~$G_t$ tornar-se conexo, há, a
      menos de um componente, somente vértices isolados.  Argumente que, a
      partir deste momento, a.q.c., os vértice isolados são absorvidos um a um
      pela `componente gigante'.}
  \end{itemize}
  \datedue{14/4/2009}
  
\item Seja~$p=p(n)=c/n$ onde~$c>0$ é uma constante fixa.
  \begin{itemize}
  \item[(\textit{i})] Suponha que~$c<1$.  Prove que todas as componentes
    de~$G(n,p)$ têm ordem limitada superiormente por
    \begin{equation}
      \label{eq:before_GC}
      {1\over\alpha}\log n,
    \end{equation}
    onde~$\alpha=c-1-\log c$.
    
  \item[(\textit{ii})] Suponha agora que~$c>1$, e que já sabemos que
    a.q.c.~$G(n,p)$ contém uma única componente de ordem maior
    que~$(\alpha/2c)n$ (a `componente gigante').  Prove que todas as
    \textit{outras} componentes de~$G(n,p)$ têm ordem limitada superiormente
    por~\eqref{eq:before_GC}; isto é, exceto pela componente gigante, todas as
    componentes têm ordem limitada como em~(\textit{i}).

  \end{itemize}
  \datedue{14/4/2009}

\item\label{Q:ErFu}[Erd\H os e Füredi] Para~$0<\theta\leq\pi$, defina
  \begin{equation}
    \label{eq:Danzer-Gruenbaum}
    f(\theta;n)=\max|S|,
  \end{equation}
  onde o máximo é tomado sobre todo~$S\subset\RR^n$ tal que~$\angle
  ABC<\theta$ para toda tripla de elementos distintos~$A$, $B$, e~$C$ de~$S$.
  \begin{itemize}
  \item[(\textit{i})] Prove que existe algum~$\alpha>0$ tal que
    \begin{equation}
      \label{eq:Erdos-Furedi.1}
      f(\pi/2;n)\geq(1+\alpha)^n
    \end{equation}
    para todo~$n$ suficientemente grande.  Encontre o maior~$\alpha$ que você
    conseguir.  \hint{Para cada~$A\subset[n]$, seja~$x^A=(x^A_i)_{1\leq i\leq
        n}\in\{0,1\}^n\subset\RR^n$ com~$x^A_i=1$ se e só se~$i\in A$.  Mostre
      que~$\angle x^Ax^Bx^C\leq\pi/2$ para quaisquer~$A$, $B$, e~$C\subset[n]$
      e que vale a igualdade  se e só se~$A\cap C\subset B\subset
      A\cup C$.  Sorteie uma família grande de conjuntos~$A_\lambda\subset[n]$
      ($\lambda\in\Lambda$) e mostre que os~$x^{A_\lambda}$ correspondentes
      servem com probabilidade positiva.}
  \item[(\textit{ii})] Prove que, para todo~$\epsilon>0$, existe~$\beta>0$ tal
    que 
    \begin{equation}
      \label{eq:Erdos-Furedi.2}
      f(\pi/3+\epsilon;n)\geq(1+\beta)^n.
    \end{equation}
    \hint{Mostre que os~$x^{A_\lambda}$ em~(\textit{ii}) são, com
      probabilidade positiva, tais que quaisquer dois tais pontos estão a uma
      distância euclidiana muito próxima de~$\sqrt{n/2}$, mesmo
      que~$|\Lambda|$ seja exponencialmente grande.}
  \end{itemize}
  \datedue{24/4/2009}
  
\item A sugestão para~(\textit{ii}) do Exercício~\ref{Q:ErFu} diz que podemos
  encontrar uma quantidade exponencialmente grande de pontos no~$\RR^n$
  formando um conjunto \textit{quase-equilátero} (todos os pares do conjunto
  definem aproximadamente uma mesma distância).  Prove que a cardinalidade
  máxima de um conjunto \textit{equilátero} no~$\RR^n$ é~$n+1$.
  Equivalentemente, prove que se~$S\subset\RR^n$ e, para quaisquer~$x$, $y\in
  S$ ($x\neq y$), temos~$\|x-y\|=1$, então~$|S|\leq n+1$.
  
\item{}[Chebyshev] Sejam~$a_1\leq\dots\leq a_n$ e~$b_1\leq\dots\leq b_n$ reais
  positivos dados.  Sejam~$\bar a=(1/n)\sum_ia_i$, $\bar b=(1/n)\sum_ib_i$
  e~$\bar c=(1/n)\sum_ia_ib_i$ as médias de~$(a_i)$, $(b_i)$ e~$(a_ib_i)$.
  Prove que~$\bar a\bar b\leq\bar c$.
  \datedue{28/4/2009}
  
\item Seja~$\Gamma$ um grafo.  Seja~$\Gamma_{1/2}$ o subgrafo aleatório
  de~$\Gamma$ obtido selecio\-nan\-do-se cada aresta de~$\Gamma$ com
  probabilidade~$1/2$, independentemente (o conjunto de vértices de~$\Gamma_p$
  é o conjunto de vértices de~$\Gamma$).  Suponha que colorimos cada aresta
  de~$\Gamma$ de azul ou vermelho, com igual probabilidade, independentemente
  para cada aresta.  Sejam~$\Gamma_{\rm azul}$ e~$\Gamma_{\rm vermelho}$ os
  grafos sobre~$V(\Gamma)$ cujos conjuntos de arestas são o conjunto de
  arestas azuis e o conjunto de arestas vermelhas, respectivamente.
  
  Seja~$P$ a probabilidade de~$\Gamma_{1/2}$ ser conexo e seja~$Q$ a
  probabilidade de ambos~$\Gamma_{\rm azul}$ e~$\Gamma_{\rm vermelho}$ serem
  conexos.  Decida se vale que~$Q\leq P^2$.
  \datedue{28/4/2009}

  
\item Denotamos o grau máximo~$\max\{d(v)\:v\in V(G)\}$ de um grafo~$G$
  por~$\Delta(G)$.  Analogamente, denotamos o grau mínimo~$\min\{d(v)\:v\in
  V(G)\}$ de~$G$ por~$\delta(G)$.  Considere~$G_{1/2}=G(n,1/2)$, o grafo
  aleatório de ordem~$n$, cujas arestas estão presentes com
  probabilidade~$1/2$ cada uma, todas de forma independente.
  \begin{itemize}
  \item[(\textit{i})] Suponha que~$n$ é par.  Prove
    que~$\PP(\Delta(G_{1/2})<n/2)\geq2^{-n}$.
  \item[(\textit{ii})] Seja~$C>1$ uma constante fixa.  Prove que, a.q.c.,
    temos 
    \begin{equation}
      \label{eq:almost_reg.1}
      {1\over2}n-C\sqrt{n\log n}\leq\delta(G_{1/2})
      \leq\Delta(G_{1/2})\leq{1\over2}n+C\sqrt{n\log n}
    \end{equation}
  \item[(\textit{iii})] Dizemos que um grafo~$G$ é
    \textit{$\epsilon$-quase-grau-regular} ($\epsilon$-q.g.r.) se
    \begin{equation}
      \label{eq:almost_reg.2}
      {\Delta(G)\over\delta(G)}\leq1+\epsilon.
    \end{equation}
    Fixe~$\epsilon>0$.  Deduza que~$G_{1/2}$ é a.q.c.\ $\epsilon$-q.g.r.  
  \item[(\textit{iv})] Prove que, para qualquer~$\epsilon>0$, existe~$C$ tal
    que se~$p\geq C\log n$, então~$G(n,p)$ é, a.q.c., $\epsilon$-q.g.r.  
    
  \item[(\textit{v})] Fixe~$\epsilon>0$ e suponha que~$p=p(n)\ll\log n$.
    Prove que~$G(n,p)$ a.q.c.\ não é $\epsilon$-q.g.r.
  \end{itemize}
  \datedue{28/4/2009}
  
\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$; analogamente, se $H\subset H'$ e~$H\in\cH$,
  então~$H'\in\cH$ e idem 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{Use alguma desigualdade de correlação.}
   \datedue{5/5/2009}

\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 a desigualdade de
    Janson 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/5/2009}
  
\item Considere o grafo aleatório~$G=G(n,1/2)$, com conjunto de
  vértices~$[n]$.  Defina um hipergrafo $3$-uniforme~$\cH=\cH(G)$
  sobre~$[n]$ da seguinte forma: uma tripla~$\{a,b,c\}$, com~$a<b<c$,
  está presente em~$\cH$ se e só se \textit{exatamente} um dos
  pares~$\{a,b\}$ e~$\{a,c\}$ é uma aresta de~$G$.
  \begin{enumerate}
  \item[(\textit{i})]Prove que, para todo~$\eta>0$, a.q.c.\ temos
    \begin{equation}
      \label{eq:unif_triples}
      \left|e_{\cH}(U)-{1\over2}{|U|\choose3}\right|\leq\eta n^3
    \end{equation}
    para todo~$U\subset[n]$; isto é, informalmente falando, as triplas
    de~$\cH$ estão uniformemente distribuídas.
  \item[(\textit{ii})]Prove que~$\cH$ não contém~$K^{(3)}_4$, o
    hipergrafo $3$-uniforme completo com~$4$ vértices.
  \end{enumerate}
  \datedue{5/6/2009}

\item Seja~$G$ um $(n,d,\lambda)$-grafo e~$0<\alpha<1$.  Suponha
  que~$H$ é um subgraph de~$G$ com~$e(H)\geq\alpha e(G)$.
  \begin{enumerate}
  \item[(\textit{i})]Mostre que existe um subgrafo~$H'$ de~$H$ que tem
    grau mínimo pelo menos~$\alpha d/2$.
  \item[(\textit{ii})]Sejam~$f=(\alpha^2/16)d^2/\lambda^2$
    e~$b=(\alpha/4)n/f$.  Mostre que~$H'$ é \textit{$(b,f)$-expansor},
    isto é, todo conjunto~$U$ de vértices de~$H'$ é tal que sua
    vizinhança $\Gamma_{H'}(U)=\{w\in V(H')\:\{u,w\}\in E(H')\}$ é tal
    que~$|\Gamma_{H'}(U)|\geq f|U|$.
  \item[(\textit{iii})]Suponha que~$\lambda\leq C\sqrt n$ e que um
    adversário maliciosamente remove no máximo $(1-\alpha)e(G)$
    arestas de~$G$.  Mostre que o grafo resultante contém qualquer
    árvore~$T$ com~$t$ vértices e grau máximo~$\Delta$, desde
    que~$t\leq c_1n$ e~$\Delta\leq c_2d$, onde~$c_1=c_1(\alpha,C)$
    e~$c_2=c_2(\alpha,C)$ são constantes que dependem apenas
    de~$\alpha$ e~$C$.  \sugestao{Use um teorema de Friedman e
      Pippenger que afirma que todo grafo não-vazio
      $(2t-2,\Delta+1)$-expansor contém toda árvore com~$t$ vértices e
      grau máximo~$\leq\Delta$.}
  \end{enumerate}
  \datedue{9/6/2009}

\item Seja~$G$ o grafo sobre~$V=2^{[n]}=\cP([n])$ com conjunto de
  arestas
  \begin{equation}
    \label{eq:even_inter}
    E=\big\{\{f,g\}\:\text{$f$, $g\subset[n]$ com $|f\cap g|$ par}\big\}.
  \end{equation}
  \begin{enumerate}
  \item[(\textit{i})]Mostre que, para todo~$h$, existe~$n_0$ tal que
    se~$n\geq n_0$, então~$G$ é \textit{$h$-universal}, isto é,
    $G$~contém todo grafo com~$h$ vértices como subgrafo induzido.
  \item[(\textit{ii})]Mostre que, para todo~$\eta>0$, existe~$n_0$ tal
    que se~$n\geq n_0$, então~$G$ é tal que, para todo~$U\subset V$
    com~$|U|\geq\eta2^n$, temos
    \begin{equation}
      \label{eq:even_inter_unif}
      \left|e_G(U)-{1\over2}{|U|\choose2}\right|\leq\eta{|U|\choose2}.
    \end{equation}
  \end{enumerate}
  \datedue{9/6/2009}

\item Consideramos aqui seqüências de grafos~$(G_n)_{n\geq1}$ com
  $|V(G_n)|\to\infty$ (todos os limites são em relação
  a~$n\to\infty$).  Para~$k\geq1$ fixo, seja~$\cH^{\leq k}$ a coleção
  de todos os grafos conexos~$H$ com~$2\leq|V(H)|\leq k$, a menos de
  isomorfismo.  Dados grafos~$G=G^n$ e~$H=H^s$, pomos
  $c_H(G)=(n)_s^{-1}\#\{H\hookrightarrow G\}$; isto é, $c_H(G)$ é a
  probabilidade de uma injeção aleatória~$\iota\:V(H)\hookrightarrow
  V(G)$ ser um isomorfismo entre~$H$ e o grafo induzido
  por~$G[\iota(V(H))]$.  Para cada~$G$, definimos o
  \textit{$k$-perfil} de~$G$ como sendo o vetor
  \begin{equation}
    \label{eq:perfil}
    c_{\cH^{\leq k}}(G)=(c_H(G))_{H\in\cH^{\leq k}}\in[0,1]^{\cH^{(\leq
        k)}}\subset\RR^{\cH^{(\leq k)}}. 
  \end{equation}
  Claramente, $c_{\cH^{\leq k}}(G)$ pode ser pensado como um vetor
  em~$\RR^N$, onde $N=|\cH^{\leq k}|$.  Definimos
  \begin{equation}
    \label{eq:S_ELS_def}
    S=\{\bfx\in\RR^{\cH^{\leq k}}\:\exists(G_n)_{n\geq1}\text{ como acima com
    }c_{\cH^{\leq k}}(G)\to\bfx\}. 
  \end{equation}
  Um teorema de Erd\H os, Lovász, e Spencer~(1979) diz que~$S$ tem
  interior não-vazio em~$\RR^{\cH^{\leq k}}$. 

  Fixe agora uma constante~$0<p<1$ e defina a
  projeção natural~$\pi_{\leq4}\:\RR^{\cH^{\leq
      k}}\to\RR^{\cH^{\leq4}}$ dada por
  \begin{equation}
    \label{eq:pi_4_def}
    \pi_{\cH^{\leq k}}(\bfx)=(x_H)_{H\in\cH^{\leq4}}, 
  \end{equation}
  para todo~$\bfx=(x_H)_{H\in\cH^{\leq k}}\in\RR^{\cH^{\leq k}}$.
  Seja~$\bfp=(p_H)_{H\in\cH^{\leq4}}$ o vetor com entradas
  $p_H=p^{|V(H)|\choose2}$ para todo~$H\in\cH^{\leq4}$.
  \begin{enumerate}
  \item[(\textit{i})]Prove que existe um único~$\bfx=\bfx(p)\in S$ tal
    que~$\pi_{\leq4}(\bfx)=\bfp$.
  \item[(\textit{ii})]Identifique o vetor~$\bfx(p)$ em~(\textit{i}).
  \item[(\textit{iii})]O ponto~$\bfx(p)$ pode pertencer ao interior
    de~$S$?
  \end{enumerate}\sugestao{Enuncie uma generalização relevante de um
    resultado de Chung, Graham e Wilson e aplique esta generalização.}
  \datedue{16/6/2009}

\item Considere o grafo aleatório~$G_n=G(n,1/2)$.  Dizemos que o
  número cromático de~$G_n$ \textit{está concentrado em~$L(n)$
    valores} se existem conjuntos~$S_n\subset\NN$ ($n=1,2,\dots$) tais
  que~$|S_n|\leq L(n)$ para todo~$n$ e
  \begin{equation}
    \label{eq:conc_L_points}
    \lim_{n\to\infty}\PP(\chi(G_n)\in S_n)=1.
  \end{equation}
  Seja~$L(n)$ tal que~$L(n)/\sqrt n\to\infty$ conforme~$n\to\infty$.
  Prove que~$\chi(G_n)$ está concentrado em~$L(n)$ valores.
  \sugestao{Use o teorema de McDiarmid; para cada~$1<i\leq n$,
    seja~$A_i=2^{[i-1]}$, onde supomos que~$V(G_n)=[n]$.  Para
    especificar~$G_n$, especificamos o conjunto~$N_i\subset[i-1]$ dos
    vértices~$j<i$ adjacentes a~$i$ em~$G_n$.}  \datedue{19/6/2009}
  
\item Sejam dados grafos~$G$ e~$H_1,\dots,H_r$.
  Escrevemos~$G\indarrow(H_1,\dots,H_r)$ se vale o seguinte: para qualquer
  coloração das arestas de~$G$ com cores~$1,\dots,r$, para algum~$1\leq i\leq
  r$, um subgrafo induzido~$H$ de~$G$ isomorfo a~$H_i$ tem todas suas arestas
  coloridas com a cor~$i$.\footnote{Isto é, existe~$U\subset V(G)$ tal que o
    subgrafo~$H=G[U]=(U,{U\choose2}\cap E(G))$ induzido por~$U$ em~$G$ é
    isomorfo a~$H_i$ e todas as arestas em~${U\choose2}\cap E(G)$ são
    coloridas com a cor~$i$.}  Prove que, para quaisquer~$r$
  grafos~$H_1,\dots,H_r$, existe um grafo~$G$ tal
  que~$G\indarrow(H_1,\dots,H_r)$.  \sugestao{Tome para~$G$ um grafo
    quase-aleatório suficientemente grande.  Aplique o lema de regularidade de
    Szemerédi, o teorema de Turán, o teorema de Ramsey, e o lema da imersão de
    forma adequada.}  \datedue{30/6/2009}

\end{enumerate}  

\end{document}

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