%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 15 Dec 2020 04:02:57pm -03 by yoshi on pokopon.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\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}
%\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\top{{\rm T}}

\def\tomega{\widetilde\omega}

\def\barp{{\bar p}}
\def\bard{{\bar d}}

\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\ee{{\rm e}}

\def\bfa{\textbf{a}}
\def\bfb{\textbf{b}}
\def\bfd{\textbf{d}}
\def\bff{\textbf{f}}
\def\bfp{\textbf{p}}
\def\bfu{\textbf{u}}
\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{2{\tiny o} Semestre de 2020}}\\
  \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 e-Disciplinas.  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}

\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 Prove que toda função booleana $f\:\{0,1\}^n\to\{0,1\}$ pode ser
  expressa for uma fórmula~$\phi=\phi(x_1,\dots,x_n)$ de
  comprimento~$O(2^n)$.  \datedue{9/9/2020}

\item Seja~$\phi=\phi(x_1,\dots,x_n)$ uma fórmula booleana da forma
  \begin{equation}
    \label{eq:3}
    \phi=\bigwedge_{1\leq i\leq t}C_i,
  \end{equation}
  com~$C_i=\ell_{i1}\vee\ell_{i2}\vee\ell_{i3}$ para todo~$i$, onde
  os~$\ell_{ij}$ são literais, isto é, cada~$\ell_{ij}$ é uma
  variável~$x_k$ ou sua negação~$\neg x_k$.  Adicionalmente, suponha
  que, para cada~$i$, as três variáveis que ocorrem em~$C_i$ são
  distintas.  Prove que existe uma atribuição de valores para as
  variáveis~$x_1,\dots,x_n$ que satisfaz pelo menos~$7t/8$ dos~$C_i$.
  \datedue{9/9/2020}

\item Para $f\:\{0,1\}^n\to\{0,1\}$, seja $L(f)=\min_\phi|\phi|$, onde
  o mínimo é tomado sobre todas as fórmulas booleanas~$\phi$ que
  expressam~$f$.  Prove que, para todo~$\epsilon>0$, quase todas as
  funções~$f$ como acima\footnote{isto é, para $(1-o(1))2^{2^n}$
    dessas funções, onde~$o(1)\to0$ quando~$n\to\infty$} são tais que
  $L(f)\geq(1-\epsilon)2^n/\log_2(n+8)$.

\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{16/9/2020}
  
\item Sejam~$X$ e~$Y$ variáveis aleatórias sobre um espaço de
  probabilidade~$(\Omega,\PP)$.  Prove
  que $\EE(XY)^2\leq\EE(X^2)\EE(Y^2)$.
  
\item Um circuito hamiltoniano em um grafo~$G$ de ordem~$n$ é uma
  ordenação $(x_1,\dots,x_n)$ de seus vértices de forma
  que~$x_{i-1}x_i\in E(G)$ para todo~$1< i\leq n$ e~$x_nx_1\in E(G)$.
  Seja~$X$ o número de circuitos hamiltonianos no grafo
  aleatório~$G(n,p)$ e seja~$\eta$ uma constante positiva.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$\EE(X)\to\infty$ se~$p\geq(\ee+\eta)/n$ e que
    que~$\EE(X)\to0$ se~$p\leq(\ee-\eta)/n$.
  \item Decida se~$p=\ee/n$ é a função limiar para a propriedade
    de~$G(n,p)$ ter um circuito hamiltoniano.
  \end{enumerate}
  \datedue{16/9/2020}

\item Determine a função limiar para a propriedade de~$G(n,p)$
  conter~$H$ como subgrafo nos seguintes casos.
  \begin{enumerate}[label=\rmlabel]
  \item $H$ é uma árvore.
  \item $H$ é um grafo completo.
  \item $H$ é o grafo de Petersen.
  \end{enumerate}
  \datedue{23/9/2020}
  
\item Seja~$\Gamma=[n]\times[n]=[n]^2$.  Um \textit{quadrado}
  em~$\Gamma$ é uma quádrupla~$Q=\{x_1,x_2,x_3,x_4\}\subset\Gamma$
  com~$x_2=x_1+(a,0)$, $x_3=x_1+(a,b)$ e $x_4=x_1+(0,b)$, onde~$a$
  e~$b$ são inteiros positivos quaisquer (assim, $Q$~é formado pelos
  quatro vértices de um quadrado alinhado com os eixos).
  Seja~$\cP\subset2^\Gamma$ a família dos conjuntos~$S\subset\Gamma$
  que contêm quadrados.  Seja~$0\leq p=p(n)\leq1$ e
  considere~$\Gamma_p$.  Determine a função limiar para a propriedade
  de~$\Gamma_p$ conter um quadrado.
  \datedue{23/9/2020}

\item Seja~$\tomega(n)$ o número de divisores primos de~$n$, contando
  multiplicidades: $\tomega(n)=\sum_{p^a\mid n}1=\sum_{p^a\|n}a$.
  Seja~$\tau(n)$ o número de divisores de~$n$:
  $\tau(n)=\sum_{d\mid n}1$.  Suponha que~$n\inU[N]$ (isto é, suponha
  que $n$~seja escolhido aleatoriamente em~$[N]$, uniformemente ao
  acaso).
  \begin{enumerate}[label=\rmlabel]
  \item Prove que $\EE(\tomega(n))=\log\log N+O(1)$.
  \item Prove que $\EE(\tau(n))=\log N+O(1)$.
  \end{enumerate}
  \datedue{30/9/2020}

\item Deduza do teorema de Hardy e Ramanujan que o valor típico
  de~$\omega(n)$ é~$\log\log n$.  [Para provar essa afirmação, você
  precisa provar o seguinte: para todo~$\epsilon>0$, o conjunto
  $S_\epsilon=\{n\in\NN\:|\omega(n)-\log\log n|\leq\epsilon\log\log
  n\}$ tem densidade~$1$.] 
  \datedue{30/9/2020}

\item Sejam dados~$\ell\geq3$ e~$\epsilon>0$.  Prove que, para
  todo~$k\geq k_0(\ell,\epsilon)$, existe um grafo~$G$
  com~$n\leq k^{(1+\epsilon)\ell}$ vértices tal que~$\chi(G)>k$
  e~$g(G)>\ell$.

\item Seja~$G$ um grafo com~$g(G)>\ell$
  e~$|V(G)|<k^{\lfloor\ell/2\rfloor}$.  Prove que~$\chi(G)\leq k$. 

\item Seja~$G$ um hipergrafo $k$-uniforme com~$\chi(G)>2$.  Prove que
  existem duas hiperarestas~$e$ e~$f\in E(G)$ com~$|e\cap f|=1$.
  
\item\label{ex:T} Seja~$G$ um grafo.  Prove
  que~$\alpha(G)\geq\sum_{x\in V(G)}1/(d(x)+1)$, onde~$d(x)$ é o grau
  de~$x$ em~$G$.  \hint{Considere uma ordenação
    aleatória~$(x_1,\dots,x_n)$ de~$V(G)$, com todas as~$n!$ possíveis
    permutações igualmente prováveis.  Considere o
    conjunto~$S=\{x_i\:\text{se }x_ix_j\in E(G)\text{, então }i<j\}$.}

\item Deduza do Ex.~\ref{ex:T} que~$\alpha(G)\geq|V(G)|/(\bard(G)+1)$.
  \hint{Note que~$f(x)=1/(x+1)$ é convexa e aplique a desigualdade de
    Jensen.} 
  
\item\label{ex:20} Seja~$\ell\geq3$ um inteiro.  Seja~$G$ um grafo
  com~$\bard(G)\geq2\Delta(G)^{1-1/\ell}$, onde~$\Delta(G)$ é o grau
  máximo em~$G$.  Suponha adicionalmente que~$\Delta(G)\geq4^\ell$.
  Prove que~$G$ contém um subgrafo~$H$ com~$g(H)>\ell$
  e~$\bard(H)\geq\bard(G)\Delta(G)^{1/\ell-1}/4$.
  \hint{Tome~$p=\Delta(G)^{1/\ell-1}/2$ e considere o subgrafo
    aleatório~$J=G_p=(V(G),E(G)_p)$.}  \datedue{7/10/2020}

\item Dizemos que um grafo~$G$ é \textit{$[a,b]$-regular} se
  $a\leq d(x)\leq b$ para todo vértice~$x$ de~$G$, onde~$d(x)$ é o
  grau de~$x$ em~$G$.  Sejam dados~$k$ e~$\ell$.  Prove que
  existe~$r_0=r_0(k,\ell)$ tal que, para todo~$r\geq r_0$, todo grafo
  $[r,r(\log r)^{2020}]$-regular tem um subgrafo~$H$ com
  $\bard(H)\geq k$ e~$g(H)>\ell$.  \hint{Use o Ex.~\ref{ex:20}.  A
    função $(\log r)^{2020}$ pode ser substituída por qualquer
    função~$\omega=\omega(r)$ com~$\log\omega=o(\log r)$.}
  \datedue{7/10/2020}
  
\item Lembre que~$M(n,k,l)$ é a cardinalidade mínima de uma família de
  $k$-subconjuntos de~$[n]$ que cobre todos os $l$-subconjuntos
  de~$[n]$.  Deduza do teorema de Frankl e Rödl/Pippenger e Füredi
  (Teorema~9.9) que, para quaisquer~$l<k$ e~$\eta>0$ fixos,
  existe~$n_0=n_0(l,k,\eta)$ tal que, para todo~$n\geq n_0$, temos
  $M(n,k,l)\leq(1+\eta){n\choose l}{k\choose l}^{-1}$.

\item Lembre que~$m(n,k,l)$ é a cardinalidade máxima de uma
  família~$\cP$ de $k$-subconjuntos de~$[n]$ tal que, para
  quaisquer~$A$ e~$B\in\cP$ distintos, temos~$|A\cap B|<l$.
  A conjectura de Erd\H os e Hajnal~(1963) diz que
  \begin{equation}
    \label{eq:4}
    \lim_{n\to\infty}M(n,k,l){k\choose l}{n\choose l}^{-1}
    =\lim_{n\to\infty}m(n,k,l){k\choose l}{n\choose l}^{-1}=1.
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Prove que ambos os limites em~\eqref{eq:4} existem. 
  \item Prove que um dos limites em~\eqref{eq:4} é~$1$ se e só se o
    outro limite em~\eqref{eq:4} também é~$1$.
  \end{enumerate}

\item Suponha que exista uma configuração tática com parâmetros
  $(n,k,l)$ (veja a Definição~9.2).  Prove que
  \begin{equation}
    \label{eq:5}
    {n-t\choose l-t}{k-t\choose l-t}^{-1}
  \end{equation}
  é inteiro para qualquer $0\leq t\leq l$.

\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:C4} Seja~$p_{C^4}(n)$ o tamanho máximo de um
    $n$-empacotamento de~$C^4$.  Determine~$p_{C^4}(n)$
    assintoticamente, isto é, encontre uma função~$f(n)$ tal que
    \begin{equation}
      \label{eq:2018.4}
      \lim_{n\to\infty}p_{C^4}(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:C4}.  Neste item,
    basta esboçar as demonstrações.
  \end{enumerate}
  \datedue{14/10/2020}  

\item\label{E:pGnp} 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 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}$.  \datedue{21/10/2020}
  \item\label{ex:pK3} 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}
  
\item Suponha agora que~$p=(c/n)^{1/2}$, onde~$c$ é uma
  constante. 
  \begin{enumerate}[label=\rmlabel]
  \item Prove que existe uma constante~$c_0$ tal que, se~$0<c<c_0$,
    então existe~$\epsilon=\epsilon(c)>0$ tal que 
    \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^4_-$ o grafo com~$4$ vértices e~$5$
      arestas.  O que você pode fazer se o número de~$K^4_-$ é menor
      que o número de~$K^3$?}
    \datedue{21/10/2020}
  \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 Dizemos que um hipergrafo é $D$-regular se todos os seus
  vértices têm grau~$D$.  Seja~$H=H^N$ um hipergrafo $k$-uniforme
  $D$-regular.  Prove que~$\cov(H)\leq(1+\log k)N/k$.

\item Considere o seguinte $3$-grafo~$H_r$ $(r\geq1)$.  Para~$V(H_r)$,
  tomamos~$U_0\cup U_1\cup\dots\cup U_{2r}$, onde os~$U_i$ são conjuntos
  dois a dois disjuntos, $|U_0|=3r$ e $|U_i|=3$ para
  todo~$1\leq i\leq2r$.  As hiperarestas de~$H_r$ são as triplas~$e$
  com~$|e\cap U_0|=1$ e~$|e\cap U_i|=2$ para algum~$1\leq i\leq2r$.  
  \begin{enumerate}[label=\rmlabel]
  \item Verifique que~$H_r$ tem~$N=9r$ vértices e que~$H_r$ é
    $6r$-regular. 
  \item Prove que $\cov(H_r)=4r$.
  \item Note que~$N/3=3r$ e assim~$H_r$ é tal que a
    cota~$\cov(H)\geq N/k$ para hipergrafos $k$-uniformes~$H=H^N$ está
    longe de ser justa para o hipergrafo $3$-uniforme~$H_r$.  Explique
    por que este exemplo não contradiz o teorema de Frankl e
    Rödl/Pippenger e Füredi, que diz que essa cota é basicamente justa
    para certos hipergrafos~$H$.
  \end{enumerate}
  \datedue{21/10/2020}
  
\item\label{eq:PIE} Sejam~$B_1,\dots,B_T$ eventos em um espaço de
  probabilidade.  Seja~$p_k$ a probabilidade de exatamente~$k$ desses
  eventos ocorrer ($k\in\NN$).  Seja~$\sigma_j=\sum_{|J|=j}\PP(B_J)$,
  onde~$B_J=\bigcap_{i\in J}B_i$ ($j\in\NN$).  Prove a seguinte
  generalização do princípio da inclusão e exclusão: para
  todo~$k\geq0$, temos
  \begin{equation}
    \label{eq:6k}
    p_k=\sum_{j\geq k}(-1)^{j+k}{j\choose k}\sigma_j.
  \end{equation}

\item Sejam~$A$, $B$ e~$C$ conjuntos finitos.  Prove que
  \begin{multline}
    \label{eq:8}
    |A\setminus(B\cup C)|
    +|B\setminus(A\cup C)|
    +|C\setminus(A\cup B)|
    \\=|A|+|B|+|C|
    -2\big(|A\cap B|+|A\cap C|+|B\cap C|\big)
    +3|A\cap B\cap C|.
  \end{multline}
  \datedue{28/10/2020}
  
\item (Continuação do Exercício~\ref{eq:PIE}; Bonferroni
  generalizado)\, Prove que
  \begin{equation}
    \label{eq:7}
    p_k=\sum_{j\geq k}(-1)^{j+k}{j\choose k}\sigma_j
  \end{equation}
  tem a propriedade das somas alternantes, no sentido que 
  \begin{equation}
    \label{eq:7a}
    p_k\leq\sum_{k\leq j\leq t}(-1)^{j+k}{j\choose k}\sigma_j
  \end{equation}
  se~$t-k+1$ é ímpar (isto é, o número de parcelas na soma do lado
  direito em~\eqref{eq:7a} é ímpar) e 
  \begin{equation}
    \label{eq:7b}
    p_k\geq\sum_{k\leq j\leq t}(-1)^{j+k}{j\choose k}\sigma_j
  \end{equation}
  se~$t-k+1$ é par.
  \datedue{28/10/2020}
  
\item Complete a prova do Teorema~2 da Aula~13: prove que
  $\lim_{n\to\infty}\PP(X^{(n)}=k)=\ee^{-\mu}\mu^k/k!$ para
  todo~$k\geq1$ (provamos na aula que esta afirmação vale
  para~$k=0$). 

\item Complete a prova do Teorema~15.7, que afirma que todo grafo
  dirigido~$D$ $d$-regular com cintura dirigida pelo menos~$8\ee d$
  tem arboricidade linear dirigida~$d+1$.  \hint{Lembre que já
    obtivemos uma decomposição das arestas de~$D$ em~$d$
    $1$-fatores~$F_i$ ($1\leq i\leq d$) (subgrafos geradores
    $1$-regulares).  Temos assim uma decomposição de~$E(D)$ em um
    certo número de circuitos dirigidos, que, pela hipótese sobre a
    cintura dirigida de~$D$, têm comprimento pelo menos~$8\ee d$.
    Lembre-se agora do Teorema~14.7, sobre transversais
    independentes.}  \datedue{4/11/2020}
  
\item Seja~$\delta>0$ uma constante.  Seja~$p=p(n)=\sqrt{9(\log
  n)/\delta^2n}$ e considere~$G=G(n,p)$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que, assintoticamente quase-certamente (isto é,
    com probabilidade que tende a~$1$ quando~$n\to\infty$), vale que
    todo par de vértices de~$G$ é ligado por $(1\pm\delta)p^2n$
    caminhos de comprimento~$2$.
  \item Faça o Exercício~\ref{E:pGnp}\ref{ex:pK3}.
  \end{enumerate}
  \datedue{11/11/2020}
  
\item (Desigualdade de Jensen) Seja~$f\:\RR\to\RR$ uma função convexa.
  \begin{enumerate}[label=\rmlabel]
  \item Sejam~$x_1,\dots,x_n\in\RR$ e~$\lambda_1,\dots,\lambda_n\geq0$
    tais que~$\sum_{1\leq i\leq n}\lambda_i=1$.  Prove que
    \begin{equation}
      \label{eq:10a}
      f\bigg(\sum_{1\leq i\leq n}\lambda_ix_i\bigg)\leq\sum_{1\leq i\leq
        n}\lambda_if(x_i). 
    \end{equation}
  \item Seja~$X$ uma variável aleatória e suponha que a função
    convexa~$f$ seja continuamente duas vezes diferenciável (isto é,
    suponha que~$f$ seja de classe~$C^2$).  Suponha
    que~$\EE(X)<\infty$.  Prove que
    \begin{equation}
      \label{eq:10b}
      f(\EE(X))\leq\EE(f(X)).
    \end{equation}
    \NB{A desigualdade~\eqref{eq:10b} de fato vale para qualquer
      função convexa~$f$.}
  \end{enumerate}
  
\item Sejam~$X_1,\dots,X_n$ variáveis aleatórias independentes,
  com~$0\leq X_i\leq1$ para todo~$i$.
  Sejam~$X=\sum_{1\leq i\leq n}X_i$ e~$\mu=\EE(X)$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que, para todo~$0\leq t\leq n-\mu$, temos
    \begin{equation}
      \label{eq:9a}
      \PP(X\geq\mu+t)\leq\(\mu\over{\mu+t}\)^{\mu+t}\(n-\mu\over
      n-\mu-t\)^{n-\mu-t}. 
    \end{equation}
  \item Deduza que, para todo~$t\geq0$, temos
    \begin{equation}
      \label{eq:9b}
      \PP(X\geq\mu+t)
      \leq\exp\(-{t^2\over2(\mu+t/3)}\)
    \end{equation}
    e
    \begin{equation}
      \label{eq:9b}
      \PP(X\leq\mu-t)\leq\exp\(-{t^2\over2\mu}\).
    \end{equation}
  \end{enumerate}
  \hint{Note inicialmente que aqui as variáveis~$X_i$ não
    necessariamente assumem valores em~$\{0,1\}$.  Ademais, não
    estamos supondo que os~$X_i$ têm a mesma distribuição.  Assim, as
    esperanças individuais~$p_i=\EE(X_i)$ não precisam coincidir (mas
    temos~$p=n^{-1}\sum p_i$).  Apesar disso, podemos obter as cotas
    acima usando a mesma técnica que usamos para tratar o caso em
    que~$X\sim\Bi(n,p)$.  Para tanto, use a desigualdade de Jensen
    para provar que $e^{ux}\leq1-x+x\ee^u$ para
    estimar~$\EE(e^{uX_i})$.  Seja~$f(x)=f_a(x)=1+ax$.  Use a
    desigualdade de Jensen ou a desigualdade da média aritmética e
    média geométrica para ver que $\prod_if(p_i)\leq f(p)^n$.}
  \datedue{18/11/2020}

\item Complete a prova do Teorema~18.6 (Desigualdade de McDiarmid).
  Para tanto, basta provar que o martingal~$(X_i)_{0\leq i\leq n}$ que
  definimos em aula satisfaz $|X_i-X_{i-1}|\leq c_i$ para
  todo~$1\leq i\leq n$.  Você pode supor que os~$\Lambda_i$ são
  finitos.  Diga explicitamente onde você está usando a independência
  das variáveis aleatórias~$Y_i$.  \hint{Sem perda de generalidade,
    suponha que~$\Omega=\Lambda_1\times\dots\times\Lambda_n$.}
  \datedue{18/11/2020}

\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\|\|z-y\|}<\theta
  \end{equation}
  (aqui supomos~$0\leq\cos^{-1} x\leq\pi$).  Prove que, para
  qualquer~$\epsilon>0$, existe~$\delta>0$ tal que para
  qualquer~$n\geq1$ existe um $(\pi/3+\epsilon)$-conjunto
  $X\subset\RR^n$ com~$|X|\geq(1+\delta)^n$.  Note que, portanto,
  existe uma quantidade exponencial em~$n$ de pontos no~$\RR^n$ tal
  que quaisquer três deles determinam um triângulo
  ``quase-equilátero''.
  
\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)$ para todo grafo~$G$
  (esta conjectura é mais forte que uma bem-conhecida conjectura da
  Hadwiger).  Prove que a conjectura de Hajós é falsa para quase todo
  grafo (isto é, prove que se sortearmos um grafo~$G$ com~$n$ vértices
  uniformemente ao acaso, então, com alta probabilidade,
  $\chi(G)>\sigma(G)$).  \datedue{25/11/2020}

\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{9/12/2020}

\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$.
  \item Prove que, tipicamente, $d(x,y)=(1/2+o(1))n$ (inicialmente,
    traduza essa afirmação para uma afirmação precisa, e então prove
    essa afirmação precisa).
  \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=2\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\}$.  Considere~$V(Q^n)$ como um espaço de
      probabilidade com a distribuição uniforme, e considere a
      variável aleatória~$X=f$.  Seja~$\mu=\EE(X)$.  Prove
      inicialmente que~$\mu\leq\sqrt{2n\log1/\alpha}$.  Prove então
      que~$\PP(X>r)\leq\alpha$.} 
  \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}
    Informalmente: se temos uma fração positiva fixa de vértices
    de~$Q^n$, então quase todo vértice de~$Q^n$ está a uma
    distância~$\leq\omega\sqrt n$ desse conjunto de vértices.  Dado
    que o diâmetro de~$Q^n$ e também as distâncias média e típica
    entre dois vértices de~$Q^n$ são lineares em~$n$, isso pode
    parecer paradoxal.  Você consegue ``resolver'' esse paradoxo?
  \end{enumerate}
  \datedue{25/11/2020}  

\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{2/12/2020}    

\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.}
  
\item\label{ex:PM} Seja $G=(U,W;E)$ um grafo bipartido aleatório
  com~$|U|=|W|=n$ e cada aresta ligando um vértice de~$U$ a um vértice
  de~$W$ presente com probabilidade~$p$, independentemente.  Prove que
  se~$C$ é uma constante grande o suficiente
  e~$p=p(n)\geq C(\log n)/n$, então a.q.c.~$G$ tem um emparelhamento
  perfeito.  \hint{Verifique a condição de Hall.}
    
\item\label{ex:12f} Seja $G=(U,W;E)$ um grafo bipartido com~$|U|=n$
  e~$|W|=2n$.  Um $(2,1)$-fator de~$G$ é um subgrafo~$F=(U,W;E')$
  de~$G$ em que todo vértice em~$U$ tem grau~$2$ e todo vértice em~$W$
  tem grau~$1$.
  \begin{enumerate}[label=\alabel]
  \item Suponha que todo~$S\subset U$ é tal
    que~$|\Gamma(S)|\geq2|S|$.  Prove que~$G$ tem um $(2,1)$-fator.
    \hint{Use o teorema de Hall.}
  \item Suponha agora que~$G$ é aleatório, com cada aresta ligando um
    vértice de~$U$ a um vértice de~$W$ presente com probabilidade~$p$,
    independentemente.  Prove que se~$C$ é uma constante grande o
    suficiente e~$p=p(n)\geq C(\log n)/n$, então a.q.c.~$G$ tem um
    $(2,1)$-fator.
  \end{enumerate}

\item Seja~$T_3$ a árvore infinita $3$-regular.  Seja~$r$ um vértice
  de~$T_3$.  Para todo natural~$h$, seja~$T_3^{(h)}$ o
  \textit{truncamento de altura~$h$} de~$T_3$ (em~$r$): isto é,
  seja~$T_3^{(h)}$ a subárvore de~$T_3$ induzida pelos vértices em
  $B_h(r)=\{x\in V(T_3)\:\dist(r,x)\leq h\}$.  Assim, $T_3^{(h)}$~é
  uma árvore com $n_h=1+3(2^h-1)$ vértices, dos quais~$3\times2^{h-1}$
  são folhas e~$n_h-3\times2^{h-1}$ têm grau~$3$ no caso em que~$h>0$.
  Prove que existe uma constante~$C$ tal que
  se~$p=p(n)\geq C(\log n)/n$, então a.q.c.~$G(n_h,p)$
  contém~$T_3^{(h)}$ como subgrafo gerador.  Mais formalmente, prove
  que
  \begin{equation}
    \label{eq:9}
    \lim_{h\to\infty}\PP(G(n_h,p(n_h))\supset T_3^{(h)})=1.
  \end{equation}
  \hint{Use E\ref{ex:PM}, E\ref{ex:12f} e exposição múltipla.}
  \datedue{16/12/2020}
  
\item Seja~$G$ um grafo $d$-regular e~$X_0,X_1,\dots$ o passeio
  aleatório em~$G$, com~$X_0\sim\pi^{(0)}$.  Seja~$\pi^{(t)}$ a
  distribuição de~$X_t$.  Sabemos que~$\pi^{(t)}=(\hat A)^t\pi^{(0)}$,
  onde~$\hat A=d^{-1}A$ e~$A$ é a matriz de adjacência de~$G$.  A
  \textit{taxa de mistura} do passeio aleatório em~$G$ é
  \begin{equation}
    \label{eq:13}
    \mu=\sup_{\pi^{(0)}}\limsup_{t\to\infty}\|\pi^{(t)}-\bfu\|_2^{1/t}
    =\sup_{\pi^{(0)}}\limsup_{t\to\infty}\|(\hat
    A)^t\pi^{(0)}-\bfu\|_2^{1/t}, 
  \end{equation}
  onde~$\bfu$ é a distribuição uniforme sobre~$V=V(G)$ e o supremo é
  tomado sobre o conjunto das distribuições~$\pi^{(0)}$ sobre~$V$.
  Provamos que, se~$G$ é um $(n,d,\lambda)$-grafo,
  então~$\mu\leq\lambda/d$.  Prove que~$\mu\geq\lambda/d$.
  \datedue{23/12/2020}
  
\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:
