%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 19 Jun 2018 04:05:50pm -03 by yoshi on korujinha.local>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno,a4paper]{amsart}

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

%right pdf-output for special characters
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage{aecompl}

%\usepackage{lmodern}
\usepackage{amssymb}

\usepackage{xcolor}
\usepackage[backref]{hyperref}
\hypersetup{
    colorlinks,
    linkcolor={red!60!black},
    citecolor={green!60!black},
    urlcolor={blue!60!black}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%  Page Layout
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{bbm}
\footskip28pt
\usepackage{fancyhdr}
\pagestyle{fancy}

\lhead{}
\chead{}
\rhead{}
\cfoot{}
\fancyfoot[RO,LE]{\thepage}
\fancyfoot[LO,RE]{{\footnotesize\today, \currenttime}}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%------------------ disjoint union with dot -------------------------------%
\makeatletter
\def\moverlay{\mathpalette\mov@rlay}
\def\mov@rlay#1#2{\leavevmode\vtop{%
   \baselineskip\z@skip \lineskiplimit-\maxdimen
   \ialign{\hfil$\m@th#1##$\hfil\cr#2\crcr}}}
\newcommand{\charfusion}[3][\mathord]{
    #1{\ifx#1\mathop\vphantom{#2}\fi
        \mathpalette\mov@rlay{#2\cr#3}
      }
    \ifx#1\mathop\expandafter\displaylimits\fi}
\makeatother

\newcommand{\dcup}{\charfusion[\mathbin]{\cup}{\cdot}}
\newcommand{\bigdcup}{\charfusion[\mathop]{\bigcup}{\cdot}}
%------------------ disjoint union with dot -------------------------------%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{datetime}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{lineno}
\newcommand*\patchAmsMathEnvironmentForLineno[1]{%
\expandafter\let\csname old#1\expandafter\endcsname\csname #1\endcsname
\expandafter\let\csname oldend#1\expandafter\endcsname\csname end#1\endcsname
\renewenvironment{#1}%
{\linenomath\csname old#1\endcsname}%
{\csname oldend#1\endcsname\endlinenomath}}% 
\newcommand*\patchBothAmsMathEnvironmentsForLineno[1]{%
\patchAmsMathEnvironmentForLineno{#1}%
\patchAmsMathEnvironmentForLineno{#1*}}%
\AtBeginDocument{%
\patchBothAmsMathEnvironmentsForLineno{equation}%
\patchBothAmsMathEnvironmentsForLineno{align}%
\patchBothAmsMathEnvironmentsForLineno{flalign}%
\patchBothAmsMathEnvironmentsForLineno{alignat}%
\patchBothAmsMathEnvironmentsForLineno{gather}%
\patchBothAmsMathEnvironmentsForLineno{multline}%
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

\let\:=\colon
\let\epsilon=\varepsilon
\let\phi=\varphi
\let\rho=\varrho
\def\e{{\rm e}}
\def\top{{\rm T}}
\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\One{{\ensuremath{\mathbbm{1}}}}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
\def\comp{^{\text{c}}}
%\let\sim=\thicksim
\def\indarrow{{\displaystyle
  \mathrel{\mathop{\longrightarrow}\limits^{\hbox{\tiny ind}}}}}

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

\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\bfd{\textbf{d}}
\def\bff{\textbf{f}}
\def\bfp{\textbf{p}}
\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}
\def\bfX{\textbf{X}}
\def\bfdelta{\boldsymbol\delta}

\def\ldens{\underline\bfd}
\def\udens{\overline\bfd}
\def\lldens{\underline\bfdelta}
\def\uldens{\overline\bfdelta}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother
\usepackage{enumitem}
\newcommand\rmlabel{\upshape({\itshape\roman*\,\/})}
\newcommand\RMlabel{\upshape(\Roman*)}
\newcommand\alabel{\upshape({\itshape\alph*\,\/})}
\newcommand\Alabel{\upshape({\itshape\Alph*\,\/})}
\newcommand\nlabel{\upshape({\itshape\arabic*\,\/})}
\newcommand\nlabelp{\upshape(P\arabic*)}

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

\begin{document}
\title[MAC5775 Métodos Probabilísticos I]%
{Métodos Probabilísticos em Combinatória e em Teoria da Computação~I\\
  \bigskip\bigskip{\bf\textit{1{\tiny o.} Semestre de 2018}}\\
  \bigskip\bigskip Exercícios
}  

\shortdate
\yyyymmdddate
\def\today{\number\year/\number\month/\number\day}
\settimeformat{ampmtime}
\date{Versão de \today, \currenttime}
\maketitle
\linenumbers 
\onehalfspace
\pagestyle{fancy}

\noindent\textbf{Entrega.}
Entregue suas soluções no Paca.  Soluções entregues fora de prazo
valerão menos.

\medskip

\noindent\textbf{Política de colaboração e uso de fontes.}
Todo trabalho entregue por você deve ser seu.  Você não deve fornecer
suas soluções a seus colegas e você não deve procurar soluções de
terceiros (como colegas ou na Web).  Por outro lado, você é encorajado
a discutir com seus colegas o material visto em sala e os enunciados
dos exercícios.  Caso você acidentalmente encontre a solução de algum
exercício em algum lugar, você deve citar esta fonte em sua solução.
Caso você acidentalmente acabe colaborando com colegas na descoberta
de uma solução, você deve citar esta colaboração em sua solução.  Seu
desempenho nesta disciplina ficará prejudicado caso você viole essas
regras.

\medskip

\begin{enumerate}
  
\item Prove as seguintes estimativas.  
  \begin{enumerate}[label=\rmlabel]
  \item $1+x\leq\e^x$ para todo~$x\in\RR$.
  \item $1+x>\exp\big\{x-x^2/2\big\}$ para todo~$0<x\leq1$. 
  \item $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 Prove que $1+x\geq\exp\{x/(1+x)\}$ para todo~$x>-1$.
  \end{enumerate}

  \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
  \begin{equation}
    \label{eq:1}
    -\log(1-x)=x+{1\over2}x^2+{1\over3}x^3+\dots\ ]  
  \end{equation}
    
\item Prove que, para todo inteiro~$n\geq1$, temos 
  \begin{equation}
    \label{eq:2}
    \e\(n\over\e\)^n\leq n!\leq n\e\(n\over\e\)^n.
  \end{equation}\datedue{14/3/2018}

\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}[label=\rmlabel]
  \item Se~$a\geq b$, então
    \begin{equation}
       \label{eq:binom_lwbd}
       {a\choose b}\geq\(a\over b\)^b.
    \end{equation}
     
  \item Ademais, 
    \begin{equation}
       \label{eq:binom_upbd1}
       {a\choose b}\leq{a^b\over b!}.
    \end{equation}

  \item\label{item:babai}
    Para todo~$b>0$, 
    \begin{equation}
       \label{eq:binom_upbd2}
       {a\choose b}\leq\(\e a\over b\)^b.
    \end{equation}
    \hint{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 Prove a seguinte versão mais forte de~\ref{item:babai}:
  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}
  
\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}[label=\rmlabel]
  \item  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}
    onde~$o(1)\to0$ conforme~$n\to\infty$.
    
  \item 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 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}

\item Seja~$(\Omega,\PP)$ um espaço de probabilidade finito.  Suponha
  que haja~$n$ eventos independentes~$A_1,\dots,A_n\subset\Omega$
  com~$0<\PP(A_i)<1$ para todo~$i$.  Prove que~$|\Omega|\geq2^n$.
  \datedue{14/3/2018}

\item Seja~$G$ um grafo.  Defina $d_i(x)$ ($x\in V(G)$) como sendo o
  número de vértices à distância~$i$ de~$x$.  Por exemplo,
  $d_1(x) = d(x)$ é o grau de~$x$.  
  \begin{itemize}
  \item[(\textit{i})] Seja~$G$ um grafo livre de triângulos.  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$ ou~$5$).  Deduza
    de~(\textit{i}) que
    \begin{equation}
      \alpha(G) \geq \sqrt{n\bar d/2} = \sqrt{|E(G)|},
    \end{equation}
    onde $\bar d=2|E(G)|/|V(G)|$ é o grau médio de~$G$.
  \end{itemize}
  \datedue{28/3/2018}

\item Considere o algoritmo básico~$\cA$ de construção de árvores
  binárias de busca (ABBs).  Se uma ABB~$T$ está vazia, ao
  inserirmos~$x$ em~$T$, a ABB~$T$ passa a ter~$x$ como raiz.  Se~$T$
  não é vazia, ao inserirmos~$x$, comparamos~$x$ com a raiz de~$T$, e
  decidimos se devemos inserir~$x$ na subárvore esquerda de~$T$ ou na
  subárvore direita de~$T$, e o fazemos recursivamente.  Suponha
  $x_1<\dots<x_n$ e seja~$\pi\in_U S_n$.  Suponha que construímos a
  ABB~$T$ com~$n$ nós alimentando a sequência
  $x_{\pi(1)},\dots,x_{\pi(n)}$ a~$\cA$.
  \begin{enumerate}[label=\rmlabel]
  \item Seja~$N(\pi)$ o número total de comparações que são feitas
    por~$\cA$ na construção de~$T$.  Prove que~$\EE(N)\leq2n\log n$.
  \item Suponha que geramos~$T$ como acima, e ainda escolhemos algum
    elemento~$x_i$ ($i\in[n]$) uniformemente ao acaso.  Suponha que
    buscamos~$x_i$ em~$T$ até encontrá-lo.  Seja~$C$ o número esperado
    de comparações que fazemos nessa busca com sucesso de~$x_i$ (ao
    compararmos~$x_i$ com algum elemento~$y$ da árvore, a resposta
    será~$x_i=y$, $x_i<y$ ou~$x_i>y$).  Prove que~$C\leq2\log n$.
  \end{enumerate}
  \datedue{28/3/2018}

\item Seja~$P$ um conjunto pontos no plano.  Três pontos
  não-colineares de~$P$ determinam um triângulo de área positiva.
  \begin{enumerate}[label=\rmlabel]
  \item Encontre uma configuração~$P\subset\RR^2$ com~$|P|=n$ que
    determina~$\Omega(n^2)$ triângulos de área unitária.
  \item Prove que se~$|P|=n$, então o número de triplas de pontos
    de~$P$ que determinam triângulos de área unitária é~$O(n^{7/3})$.
    \hint{Seja~$\cL_0=\{\ell\:|\ell\cap P|\geq2\}$ o conjunto de retas
      determinadas por~$P$.  Seja
      também~$\cL_1=\{\ell\:\ell\parallel\ell_0\in\cL_0\text{ e
      }\ell\cap P\neq\emptyset\}$
      o conjunto das retas que interceptam~$P$ e são paralelas a
      alguma reta de~$\cL_0$.  Dizemos que uma reta~$\ell\in\cL_1$ é
      \textit{rica} se~$|\ell\cap P|\geq n^{1/3}$ e \textit{pobre}
      caso contrário.  Seja~$\cL_1^1\subset\cL_1$ o conjunto das retas
      ricas.  Seja~$\triangle abc$ um triângulo determinado por~$P$.
      Considere o lado~$ab$ desse triângulo e seja~$\ell_{ab}$ a reta
      determinada por~$ab$.  Seja~$\ell_c^{ab}$ a reta em~$\cL_1$
      com~$\ell_c^{ab}\parallel\ell_{ab}$ e~$c\in\ell_c^{ab}$.
      Dizemos que~$ab$ é \textit{pobre} se~$\ell_c^{ab}$ é pobre.
      Prove que o número de triângulos de área~$1$ determinados
      por~$P$ que têm um lado pobre é~$O(n^{7/3})$.}
  \end{enumerate}
  \datedue{11/4/2018}

\item Seja~$P$ um conjunto de~$n$ pontos no plano, não todos contidos
  em uma mesma reta.  Mostre que há um ponto~$x\in P$ tal que~$x$
  pertence a pelo menos~$cn$ retas distintas determinadas por~$P$,
  onde~$c>0$ é uma constante absoluta.  (Uma reta~$L$ é determinada
  por~$P$ se~$|L\cap P|\geq2$).  \datedue{4/4/2018}

\item Sejam~$v_i=(x_i,y_i)$ ($1\leq i\leq n$) vetores com coordenadas
  inteiras.  Suponha que~$|x_i|$, $|y_i|\leq10^{-2}n^{-1/2}2^{n/2}$
  para todo~$i$.  Prove que existem conjuntos disjuntos~$I$
  e~$J\subset[n]$ tais que
  \begin{equation}
    \label{eq:3}
    \sum_{i\in I}v_i=\sum_{j\in J}v_j.
  \end{equation}
  \datedue{11/4/2018}

\item Derive o teorema de Rödl do teorema de Frankl, Rödl e Pippenger
  (isto é, prove que a conjectura de Erd\H os e Hanani é um corolário
  do teorema de Frankl, Rödl e Pippenger).  \datedue{23/4/2018}

\item\label{E:packing} Um \textit{$n$-empacotamento} de um grafo~$H$ é
  uma coleção $\cP=\{H_1,\dots,H_t\}$ de subgrafos~$H_i$ de um grafo
  completo~$K^n$ fixo, com~$H_i$ isomorfo a~$H$ para todo~$i$
  e~$E(H_i)\cap E(H_j)=\emptyset$ para todo~$i\neq j$.  O
  \textit{tamanho} de um tal empacotamento~$\cP$ é~$|\cP|$.
  \begin{enumerate}[label=\rmlabel]
  \item Encontre um $5$-empacotamento de~$C^5$ (o circuito de
    comprimento~$5$) de tamanho~$2$.
  \item\label{item:C5} Seja~$p_{C^5}(n)$ o tamanho máximo de um
    $n$-empacotamento de~$C^5$.  Determine~$p_{C^5}(n)$
    assintoticamente, isto é, encontre uma função~$f(n)$ tal que
    \begin{equation}
      \label{eq:4}
      \lim_{n\to\infty}p_{C^5}(n)/f(n)=1
    \end{equation}
    (Naturalmente, prove que~\eqref{eq:4} vale para sua
    função~$f(n)$.)  
  \item Seja~$H$ um grafo arbitrário e defina~$p_H(n)$ de forma
    análoga.  Generalize seu resultado de~\ref{item:C5}.  Neste item,
    basta esboçar as demonstrações.
  \end{enumerate}
  \datedue{23/4/2018}

\item Neste exercício, generalizamos a noção $n$-empacotamento do
  Exercício~\ref{E:packing}: em vez de considerarmos subgrafos
  aresta-disjuntos de~$K^n$, consideramos subgrafos aresta-disjuntos
  de um grafo arbitrário~$G$.  Chamamos tais de empacotamentos de
  \textit{$G$-empacotamentos} de~$H$ e definimos~$p_H(G)$ de forma
  análoga a~$p_H(n)$.  Consideramos o caso em que~$G$ é o grafo
  aleatório~$G(n,p)$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$p_{K^3}(G(n,p))=o(pn^2)$ quase certamente
    se~$p\ll n^{-1/2}$. 
  \item Determine~$p_{K^3}(G(n,p))$ assintoticamente
    para~$p\gg\((\log n)/n\)^{1/2}$.  \NB{Enuncie precisamente o
      resultado que você provará como resposta a esse item.}
  \end{enumerate}
  \datedue{18/5/2018}

\item Suponha agora que~$p=(C/n)^{1/2}$, onde~$C$ é uma constante.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que existem constantes absolutas~$C_0$ e~$\epsilon>0$
    tais que se~$C\geq C_0$, então
    \begin{equation}
      \label{eq:6a}
      \lim_{n\to\infty}
      \PP\Big(p_{K^3}(G(n,p))\geq\epsilon\,{p\over3}{n\choose2}\Big)
      =1.
    \end{equation}\hint{Seja~$K_+^{2,k}$ ($k\geq1$)
      o grafo que obtemos ao adicionarmos ao grafo bipartido
      completo~$K^{2,k}$ uma aresta à parte de cardinalidade~$2$.
      Conte o número de ocorrências de~$K_+^{2,k}$ em~$G(n,p)$ e prove
      que é possível remover-se uma pequena fração das arestas
      de~$G(n,p)$ de forma que todas as arestas passam a pertencer a
      um número limitado de triângulos.} 
    \datedue{18/5/2018}
  \item Decida se, para todo~$\epsilon>0$, existem~$C_0$ e~$n_0$ tais
    que se~$C\geq C_0$, então
    \begin{equation}
      \label{eq:6}
      \PP\Big(p_{K^3}(G(n,p))\geq(1-\epsilon){p\over3}{n\choose2}\Big)
      \geq.99
    \end{equation}
    para todo~$n\geq n_0$.
  \item Decida se, para todo~$\epsilon>0$, existe~$C_0$ tal que 
    se~$C\geq C_0$, então
    \begin{equation}
      \label{eq:6b}
      \lim_{n\to\infty}
      \PP\Big(p_{K^3}(G(n,p))\geq(1-\epsilon){p\over3}{n\choose2}\Big)
      =1.
    \end{equation}
  \end{enumerate}

\item Um conjunto~$X\subset\RR^n$ é um \textit{$\theta$-conjunto} se,
  para quaisquer~$x$, $y$ e~$z\in X$ distintos, o ângulo~$\angle xyz$
  com vértice~$y$ e lados~$yx$ e~$yz$ é menor que~$\theta$, isto é,
  \begin{equation}
    \label{eq:7}
    \cos^{-1}{\<x-y,z-y\>\over\|x\|\|y\|}<\theta
  \end{equation}
  (aqui supomos~$0\leq\cos^{-1} x\leq\pi$).  Prove que, para
  quaisquer~$n\geq1$ e~$\epsilon>0$, existe~$\delta>0$ tal que
  existe um $(\pi/3+\epsilon)$-conjunto $X\subset\RR^n$
  com~$|X|\geq(1+\delta)^n$.

\item Seja~$\alpha(G)$ o \textit{número de independência} de~$G$, isto
  é,
  \begin{equation}
    \label{eq:9}
    \alpha(G)=\max\{k\:K^k\subset G\comp\},
  \end{equation}
  onde~$G\comp$ é o complemento de~$G$.  Prove que
  \begin{equation}
    \label{eq:8}
    \lim_{n\to\infty}\PP\big(\alpha(G(n,1/2))<2\log_2n\big)=1. 
  \end{equation}
  \hint{Use a estimativa~\eqref{eq:binom_upbd2}.}  Deduza que
  \begin{equation}
    \label{eq:8}
    \lim_{n\to\infty}\PP\big(\chi(G(n,1/2))>n/2\log_2n\big)=1,
  \end{equation}
  onde~$\chi(G)$ denota o \textit{número cromático} de~$G$, o número
  necessário e suficiente de conjuntos independentes de~$G$ para
  cobrir~$V(G)$.   \datedue{11/5/2018}

\item Uma \textit{subdivisão} de um grafo~$H$ é um grafo~$\top H$
  obtido substituindo-se arestas de~$H$ por caminhos de
  comprimento~$1$ ou mais, com todos esses caminhos internamente
  disjuntos nos vértices.  (Subdivisões de~$H$ são também chamadas de
  cópias topológicas de~$H$.)  Seja
  \begin{equation}
    \label{eq:10}
    \sigma(G)=\max\{k\:\exists\,\top K^k\subset G\}.
  \end{equation}
  Assim, $\sigma(G)$ é o maior~$k$ para o qual~$G$ contém uma
  subdivisão de um grafo completo de ordem~$k$.  Uma conjectura de
  Hajós~(1961) afirmava que~$\chi(G)\leq\sigma(G)$ (esta conjectura é
  mais forte que uma bem-conhecida conjectura da Hadwiger).
  Use~\eqref{eq:8} para provar que a conjectura de Hajós é em geral
  falsa.  \datedue{11/5/2018}

\item Prove que existe uma constante~$c>0$ tal que quase-certamente
  $\sigma(G(n,1/2))\geq c\sqrt n$.  \hint{Separe um conjunto de
    vértices~$S$ para serem os vértices de um~$K^k$
    ($k\sim c\sqrt n$).  Para obter~$\top K^k\subset G(n,1/2)$,
    conecte todos os pares~$\{x,y\}\in{S\choose2}$ por caminhos de
    comprimento~$2$.  Para tanto, mostre que, para qualquer~$\{x,y\}$,
    há um grande número de tais caminhos.}  \datedue{11/5/2018}

\item\label{Q:cube} Seja~$V=\{0,1\}^n$ ($n\geq1$).  Defina o
  grafo~$Q^n$ sobre~$V$, colocando em~$Q^n$ todas as arestas da
  forma~$\{x,x'\}$, onde~$x$ e~$x'$ diferem em exatamente uma
  coordenada.  O grafo~$Q^n$ assim obtido é o \textit{$n$-hipercubo}
  ou \textit{$n$-cubo}.  O $n$-cubo tem~$N=2^n$ vértices
  e~$nN/2=n2^{n-1}$ arestas.  Seja~$d$ a função distância em~$Q^n$,
  isto é, para~$x$ e~$y\in Q^n$, seja~$d(x,y)$ a distância de~$x$
  a~$y$ em~$Q^n$.  Seja~$\diam Q^n=\max\{d(x,y)\:x,\,y\in V(Q^n)\}$ e
  seja~$\Ave_{x,\,y\in V(Q^n)}d(x,y)=2^{-2n}\sum_{x,y\in
    V(Q^n)}d(x,y)$.
  Seja~$S\subset V(Q^n)$.  Pomos $d(x,S)=\min\{d(x,s)\:s\in S\}$ para
  todo~$x\in V(Q^n)$.  Para~$S\subset V(Q^n)$ e~$r\geq0$,
  seja~$B(S,r)=\{x\in V(Q^n)\:d(x,S)\leq r\}$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que $\diam(Q^n)=n$.
  \item Prove que, se~$S\neq\emptyset$, então~$B(S,n)=V(Q^n)$.
  \item Prove que $\Ave_{x,\,y\in V(Q^n)}d(x,y)=n/2$.
  \end{enumerate}

\item Continuamos a considerar o $n$-cubo~$Q^n$ (veja o
  Exercício~\ref{Q:cube}).  Seja~$S\subset V(Q^n)$ não-vazio. 
  \begin{enumerate}[label=\rmlabel]
  \item Seja~$\alpha=|S|2^{-n}$ e~$r=\sqrt{2n\log1/\alpha}$.  Prove
    que 
    \begin{equation}
      \label{eq:11}
      |B(S,r)|\geq(1-\alpha)2^n.
    \end{equation}\hint{Seja~$f(x)=d(x,S)$ ($x\in V(Q^n)$).  Observe
      que~$S=\{f=0\}$.} 
  \item Seja~$\omega=\omega(n)$ qualquer função
    com~$\lim_{n\to\infty}\omega(n)=\infty$ e suponha
    que~$|S|\geq10^{-10}2^n$.  Prove que quase todo~$x\in V(Q^n)$ está
    a uma distância menor ou igual a~$\omega\sqrt n$ de~$S$, isto é,
    prove que
    \begin{equation}
      \label{eq:12}
      \lim_{n\to\infty}|B(S,\omega\sqrt n)|2^{-n}=1.
    \end{equation}
  \end{enumerate}
  \datedue{18/5/2018}  

\item Sejam~$H$ e~$G$ grafos.  Um \textit{vértice-empacotamento}
  de~$H$ em~$G$ é uma família~$\cF=\{H_1,\dots,H_t\}$ de subgrafos
  de~$G$ com cada~$H_i$ isomorfo a~$H$ e tal que os~$H_i$ são
  dois-a-dois vértice-disjuntos ($V(H_i)\cap V(H_j)=\emptyset$ para
  todo~$i\neq j$).  Seja~$q_H(G)$ a cardinalidade máxima de um
  vértice-empacotamentos de~$H$ em~$G$.  Naturalmente,
  $q_H(G)\leq|V(G)|/|V(H)|$.  
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$q_{K^3}(G(n,p))=o(n)$ quase certamente se~$p\ll
    n^{-2/3}$. 
  \item Prove que, para todo~$\epsilon>0$, existe~$C$ tal que
    se~$p\geq Cn^{-2/3}$, então~$q_{K^3}(G(n,p))\geq(1/3-\epsilon)n$
    quase certamente.
  \item Seja agora~$H$ um grafo arbitrário.  Encontre uma
    constante~$\alpha=\alpha(H)$ para a qual valem as seguintes
    afirmações. 
    \begin{enumerate}[label=\alabel]
    \item Se~$p\ll n^{-1/\alpha}$, então~$q_H(G(n,p))=o(n)$ quase
      certamente.
    \item Para todo~$\epsilon>0$, existe~$C$ tal que
      se~$p\geq Cn^{-1/\alpha}$, então, quase certamente, vale
      que~$q_H(G(n,p))\geq(1-\epsilon)n/h$, onde~$h=|V(H)|$.
    \end{enumerate}
  \end{enumerate}
  \datedue{25/5/2018}  

\item Seja~$G=(V,E)$ um grafo e~$\ell$ um inteiro positivo.  Suponha
  que temos~$L\:V\to\cP(\NN)$, uma função com~$|L(v)|\geq\ell$ para
  todo~$v$.  Ademais, suponha o seguinte: \textsl{para todo~$v$ e
    todo~$c\in L(v)$, vale que no máximo~$\ell/2\e$ vértices~$w$
    adjacentes a~$v$ são tais que~$c\in L(w)$.}  Prove que
  existe~$\chi\:V\to\NN$ com~$\chi(v)\in L(v)$ para todo~$v$ tal que,
  para toda aresta~$\{v,w\}\in E$, temos~$\chi(v)\neq\chi(w)$ (isto é,
  $\chi$~é uma coloração própria de~$G$ que `respeita' as
  listas~$L(v)$ ($v\in V$); as cores em~$L(v)$ são ditas
  \textit{admissíveis} para~$v$).  \observacao{Resolva este exercício
    inicialmente para grafos finitos~$G$.  Resolva depois para
    grafos~$G$ com~$V$ infinito enumerável, por exemplo, supondo
    que~$V=\NN$.  Se você conhece argumentos de compacidade, resolva
    este exercício para grafos~$G$ com~$V$ de cardinalidade
    arbitrária.}  \datedue{29/6/2018}  

% \item Seja~$\Omega_n=\{0,1\}^n$ ($n\geq1$).  Seja~$\PP_n$ a
%   distribuição de probabilidade uniforme sobre~$\Omega_n$.  Uma
%   função~$f\:\Omega_n\to\RR$ é \textit{Lipschitz}
%   se~$|f(x)-f(y)|\leq1$ para quaisquer~$x$ e~$y\in\Omega_n$
%   com~$|x-y|\leq1$ (aqui,
%   $|(z_i)_{1\leq i\leq n}|=\sum_{1\leq i\leq n} |z_i|$).  Uma família
%   de funções~$(f_n)_{n\geq1}$ ($f_n\:\Omega_n\to\RR$) é
%   \textit{quase-constante} se existe~$\mu\in\RR$ (independente de~$n$)
%   tal que, para qualquer~$\epsilon>0$, temos
%   \begin{equation}
%     \label{eq:5}
%     \lim_{n\to\infty}\PP_n\Big(\Big|{1\over n}f_n-\mu\Big|\leq\epsilon\Big)=1.
%   \end{equation}
%   Prove que~$(f_n)_{n\geq1}$ é quase-constante se os~$f_n$ são
%   Lipschitz, o limite~$\lim_{n\to\infty}n^{-1}\EE(f_n)$ existe e esse
%   limite é finito.

\end{enumerate}  

\endgroup
\end{document}

%%% Local Variables:
%%% mode: latex
%%% eval: (auto-fill-mode t)
%%% eval: (LaTeX-math-mode t)
%%% eval: (flyspell-mode t)
%%% TeX-master: t
%%% End:
