\documentclass[11pt]{amsart}
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
\usepackage{textcomp}
\usepackage[T1]{fontenc}

\usepackage{fullpage}
\usepackage{./doublespace}
\usepackage{amssymb}
\usepackage{url}
\usepackage{graphicx}
\usepackage{epsfig}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\def\@setdate{\datename\ \@date}
\def\@setthanks{\def\thanks##1{\par##1}\thankses}
\makeatother

\usepackage{./atalhos}

\footskip=20pt

\newtheoremstyle{note}% name
  {4pt}%      Space above
  {4pt}%      Space below 
  {\sl}%      Body font
  {}%         Indent amount (empty = no indent, \parindent = para indent)
  {\bfseries}% Thm head font
  {.}%        Punctuation after thm head
  {.5em}%     Space after thm head: " " = normal interword space;
                                %       \newline = linebreak
  {}%         Thm head spec (can be left empty, meaning `normal')

%Tamanho da identação do parágrafo
\setlength{\parindent}{20pt}

\newtheorem{teorema}             {Teorema}       
\newtheorem{afirmativa}[teorema] {Afirmativa}         
\newtheorem{lema}      [teorema] {Lema}         
\newtheorem{corolario} [teorema] {Corolário}     
\newtheorem{fato}      [teorema] {Fato}          
\newtheorem{conjectura}[teorema] {Conjectura}    
\newtheorem{problema}  [teorema] {Problema}     



\theoremstyle{note}
\newtheorem{propriedade} [teorema] {Propriedade}       
\newtheorem{definicao}   [teorema] {Definição}       
\newtheorem{exercicio}   [teorema] {Exercício}       

\title[Combinatória]{\textsl{PICME/IME/USP Combinatória}\\\vspace{1\jot}
  Notas - 2010} 

\author[Kohayakawa e Mota]{Yoshiharu Kohayakawa e Guilherme Mota (IME/USP)} 
\thanks{Notas por Guilherme Mota} 

\begin{document}
\maketitle
\thispagestyle{empty}
\onehalfspace

\section{($n,d,\lambda$)-grafos}
\label{sec:expanders}
\begin{center}
 01/03/2010
\end{center}

O objeto de estudo desta seção é um tópico bastante estudado por Noga Alon. Sobre este assunto, o leitor pode encontrar uma boa palestra deste pesquisador em \begin{verbatim}http://www.pims.math.ca/resources/multimedia.\end{verbatim}

Seja $G$ um grafo com conjunto de vértices $V(G)=[n]=\{1,\ldots, n\}$ e conjunto de arestas $E$. A matriz de adjacência $A=(a_{i,j})_{1\leq i,j\leq n}$ de $G$ é a matriz em que $a_{i,j} = 1$, caso $(i,j)\in E$ e $a_{i,j} = 0$, caso contrário.

\begin{definicao}
Dizemos que $\lambda$ é autovalor de uma matriz $A$ se existe um vetor não nulo $x$ tal que~${Ax=\lambda x}$. Dizemos que $x$ é um autovetor associado ao autovalor $\lambda$.
\end{definicao}

Como a matriz de adjacência $A$ é real e simétrica, possui $n$ autovalores reais, denotados por~${\lambda_0\text{, }\lambda_1}$, $\ldots$, $\lambda_{n-1}$, onde estamos considerando $\lambda_0\geq \lambda_1 \geq \ldots \geq \lambda_{n-1}$ (as vezes supõe-se que~${|\lambda_0|\geq |\lambda_1| \geq \ldots \geq |\lambda_{n-1}|}$) e $\underline{x}_0$, $\underline{x}_1$, $\ldots$, $\underline{x}_{n-1}$ são os autovetores associados, respectivamente, a $\lambda_0$, $\lambda_1$, $\ldots$, $\lambda_{n-1}$. Ademais, podemos supor que os vetores $\underline{x}_0$, $\underline{x}_1$, $\ldots$, $\underline{x}_{n-1}$ formam uma base ortonormal de $\mathbb{R}^n$, isto é, $\langle \underline{x}_i, \underline{x}_j\rangle = 1$, se $i=j$ e $\langle \underline{x}_i, \underline{x}_j\rangle = 0$, caso contrário.

Se $O = [\underline{x}_0$ $|$ $\ldots$ $|$ $\underline{x}_{n-1}]$, então $O^tO=OO^t=I_n$ (matriz identidade). Se $D$ é a matriz $O^tAO$, temos que~${D = \diag(\lambda_0,\lambda_1,\ldots,\lambda_{n-1})}$. Portanto, $A=ODO^t$, isto é,
$$A=(\displaystyle\sum_{i=0}^{n-1}\lambda_i \underline{x}_i \underline{x}_i^t),$$
pois $(\sum_{i=0}^{n-1}\lambda_i\underline{x}_i\underline{x}_i^t)\underline{x}j = \sum_{i=0}^{n-1}\lambda_i\underline{x}_i(\underline{x}_i^t\underline{x}j) = \lambda_j\underline{x}_j = A\underline{x}_j$.

Deste ponto em diante, vamos considerar $G$ como sendo um grafo $d$-regular.
\newpage
\begin{fato}
Todo autovalor $\lambda$ de $G$ satisfaz $|\lambda|\leq d$.
\end{fato}

\begin{proof}
Seja $\underline{x}=(x_i)^n$ um autovetor associado a $\lambda$. Assim, $A\underline{x} = \lambda\underline{x}$. Suponha que~$x_p$ seja tal que~${|x_p|\geq|x_i|}$, para todo $i$. Então, 
$$|\lambda||x_p|=|(\lambda\underline{x})_p|=|(A\underline{x})_p|=|\sum_{j=1}^{n}a_{pj}x_j|\leq|\sum_{j=1}^{n}a_{pj}||x_p|=d|x_p|.$$ Como~${\underline{x}\neq\underline{0}}$, então $|x_p|>0$. Portanto, $|\lambda|\leq d$.
\end{proof}

Observe que, com a notação que estamos utilizando, $\lambda_0=d$. Ademais, $\underline{x}_0 = (1,\ldots,1)/\sqrt{n}$.

\begin{definicao}
Um grafo $G$ é um $(n,d,\lambda)$-grafo se é $d$-regular, tem $n$ vértices e seus autovalores satisfazem $|\lambda_i|\leq \lambda$, para $i=1,\ldots,n-1$.
\end{definicao}

\begin{fato}
Seja $G$ um $(n,d,\lambda)$-grafo. Se $d\leq (1-\varepsilon)n$, então $\lambda\geq \sqrt{\varepsilon d}$.
\end{fato}

\begin{proof}
Seja $A$ a matriz de adjacência de $G$. Assim, $A^2$ tem autovalores $\lambda_0^2$, $\lambda_1^2$, $\ldots$, $\lambda_{n-1}^2$, onde $\lambda_0$, $\lambda_1$, $\ldots$, $\lambda_{n-1}$ são os autovalores de $A$. Ademais, $nd=tr(A^2)=\sum_{i=0}^{n-1}\lambda_i^2$, onde $tr(A)$ é a soma dos elementos da diagonal principal de $A$. Portanto, $nd = \lambda_0^2 + \sum_{i=1}^{n-1}\lambda_i^2 \leq d^2 + (n-1)\lambda^2$. Concluímos que $\lambda^2(n-1)\geq nd - d^2 = d(n-d)\geq\varepsilon nd$, logo $\lambda^2\geq \varepsilon d$.
\end{proof}

Existem construções determinísticas de $(n,d,\lambda)$-grafos. Duas importantes construções foram feitas por Lubotzky, Phillips e Sarnak \cite{LuPhSa88} e Margulis \cite{Mar88}. Os grafos obtidos nestas construções são tais que $\lambda=2\sqrt{d-1}$. Estes grafos são chamados \textit{grafos de Ramanujan}.

\begin{definicao}
Seja $G=(V,E)$ um grafo. Denotamos por $e(U,W)$ a quantidade de arestas com uma extremidade em $U$ e a outra em $W$, onde as arestas que possuem as duas extremidades em $U\cap W$ são contadas duas vezes. Isto é, $e(U,W)=|\{(u,w)\colon u\in U$, $w\in W$ e $\{u,w\}\in E(G)\}|$.
\end{definicao}

\begin{teorema}[\textit{Expander Mixing Lemma}]\label{teorema:EML}
Seja $G$ um $(n,d,\lambda)$-grafo. Então, para todo $U,W\subset V(G)$, temos que
$$\left|e(U,W) - \frac{d|U||W|}{n}\right|\leq\lambda\sqrt{|U||W|}.$$
\end{teorema}

\subsubsection*{Observação 1} Se $U=W$, temos que $|e(U,U)-d|U|^2/n|\leq\lambda|U|$. Ademais, $e(U,U)$ é igual a duas vezes o número de arestas induzidas por $U$, que denotamos por $e(U)$. Portanto, temos que~${|2e(U)-d|U|^2/n|\leq\lambda|U|}$, isto é, $|e(U)-d|U|^2/2n|\leq(\lambda/2)|U|$.
\subsubsection*{Observação 2} $\alpha(G) = \max_I{|I|}$, onde o máximo é tomado sobre os conjuntos $I\subset V(G)$ que são independentes (estáveis), isto é, que não induzem nenhuma aresta. 
Se $I\subset V(G)$ é independente, então $e(I)=0$. O Teorema \ref{teorema:EML} diz que $d|I|^2/2n\leq(\lambda/2)|I|$, isto é, $|I|\leq (n/d)\lambda$. Portanto, concluímos que $\alpha(G)\leq\lambda(n/d)$ para todo $(n,d,\lambda)$-grafo.
\subsubsection*{Observação 3} Se $G$ é um $(n,d,\lambda)$-grafo, então
$$\chi(G)\geq \frac{n}{\alpha(G)} \geq \frac {n}{\frac{\lambda n}{d}}=\frac{d}{\lambda}.$$

\begin{proof}[Demonstração do Teorema \ref{teorema:EML}]
Fixe $U,W\subset V(G)$. Sejam $\chi_U=(\chi_{U,i})^n$ e $\chi_W$ os vetores característicos de $U$ e $W$, isto é, $\chi_{U,i}=1$, se $i\in U$ e $\chi_{U,i}=0$, caso contrário (analogamente para $\chi_W$). Temos que $e(U,W)=\chi_U^t A \chi_W$. Lembre que $A = \sum_{i=0}^{n-1}\lambda_i \underline{x}_i \underline{x}_i^t = \lambda_0 \underline{x}_0 \underline{x}_0^t + \sum_{i=1}^{n-1}\lambda_i \underline{x}_i \underline{x}_i^t$, onde dizemos que $A_0=\lambda_0 \underline{x}_0 \underline{x}_0^t$ (termo principal) e $E=\sum_{i=1}^{n-1}\lambda_i \underline{x}_i \underline{x}_i^t$ (termo de erro). Temos $\chi_U=\sum_{i=0}^{n-1}\alpha_i\underline{x}_i$ e~$\chi_W=\sum_{i=0}^{n-1}\beta_i\underline{x}_i$, onde $\alpha_i=\langle \chi_U,\underline{x}_i\rangle = \chi_U^t\underline{x}_i$ e $\beta_i=\langle \chi_W,\underline{x}_i\rangle = \chi_W^t\underline{x}_i$.

Observe que $A_0$ é a matriz com todas as posições tendo valor $d/n$, pois ${\underline{x}_0=(1,\ldots,1)/\sqrt{n}}$ e~$\lambda_0=d$. Assim, fica fácil ver que $\chi_U^t A_0 \chi_W = d|U||W|/n$. Ademais

$$
\begin{aligned}
\chi_U^t E \chi_W &= \left(\displaystyle\sum_{i=0}^{n-1}\alpha_i\underline{x}_i^t\right)\left(\displaystyle\sum_{j=1}^{n-1}\lambda_j\underline{x}_j\underline{x}_j^t\right)\left(\displaystyle\sum_{k=0}^{n-1}\beta_k\underline{x}_k\right)\\
&=\left(\displaystyle\sum_{i=0}^{n-1}\alpha_i\underline{x}_i^t\right)\left(\displaystyle\sum_{k=1}^{n-1}\lambda_k\beta_k\underline{x}_k\right)\\
&=\left(\displaystyle\sum_{k=1}^{n-1}\lambda_k\alpha_k\beta_k\right).
\end{aligned}
$$
Com isso, temos que $|\chi_U^t E \chi_W|\leq \sum_{k=1}^{n-1}|\lambda_k||\alpha_k||\beta_k|$. Utilizando a desigualdade de Cauchy--Schwarz,
$$
\begin{aligned}
|\chi_U^t E \chi_W|&\leq\lambda\displaystyle\sum_{k=0}^{n-1}|\alpha_k||\beta_k|\\
&\leq\lambda\left(\displaystyle\sum_{k=0}^{n-1}\alpha_k^2\right)^{1/2}\left(\displaystyle\sum_{k=0}^{n-1}\beta_k^2\right)^{1/2}\\
&=\lambda\sqrt{|U|}\sqrt{|W|}.
\end{aligned}
$$
Assim, $e(U,W)=\chi_U^t A \chi_W = (d/n)|U||W| + O_1(\lambda\sqrt{|U||W|})$, onde $O_1(x)$ denota um valor $y$ tal que~$|y|\leq x$. 
\end{proof}

\newpage
\subsection{Problemas e exercícios}
\label{sec:exercicios:ndlambda-grafos}
Todos estão convidados a trabalhar nos seguintes e\-xer\-cí\-cios. 

\begin{enumerate}

\item[1.]Suponha que $G=(X,Y;E)$ seja um grafo bipartido. Mostre que, se $\lambda$ é um autovalor de $G$, então $-\lambda$ também o é.
\item[2.]Considere um grupo com $n$ pessoas. Suponha que, para quaisquer duas pessoas $x$ e $y$ do grupo, exista uma terceira pessoa $z$ tal que $x$ e $y$ conhecem $z$. Prove que existe uma pessoa do grupo que conhece todas as outras.

\end{enumerate}
\newpage

\section{Grafos expansores - parte I}
\label{sec:expanders:2}
\begin{center}
 08/03/2010
\end{center}

Intuitivamente, dizemos que um grafo $G$ é \textit{expansor} se todo conjunto $U\subset V(G)$ possui muitos vizinhos.

\begin{definicao}
Considere um grafo $G=(V,E)$ e $U\subset V$. Dizemos que $\Gamma_G(U)$ é a vizinhança de~$U$ em $G$, isto é, $\Gamma_G(U)=\{w\in V(G)\colon\{v,w\}\in E(G), v\in U\}$. Quando é claro qual o grafo em questão, podemos simplesmente utilizar $\Gamma(U)$.
\end{definicao}

\begin{definicao}
Um grafo $G$ é um $(b,f)$\textit{-expansor} se $|\Gamma(U)|\geq f|U|$, para todo $U\subset V(G)$ tal que~${|U|\leq b}$.
\end{definicao}

Claramente, se $\Delta(G)$ denota o grau máximo de um vértice em $G$, então $|\Gamma(U)|\leq\Delta|U|$.

Vamos provar que qualquer subgrafo $H$ de um $(n,d,\lambda)$-grafo é expansor, desde que $\delta(H)$ (grau mínimo de um vértice em $H$) seja limitado inferiormente.

\begin{teorema}\label{teorema:auxiliar}
Seja $G$ um grafo. Se $H$ é um subgrafo de $G$ tal que $\delta(H)\geq \delta d$, com $0<\delta\leq 1$, então~$H$ é um $((1-\eta)\delta n/f,f)$-expansor, onde $f=(n\delta d/\lambda)^2$, para todo $0<\eta<1$.
\end{teorema}

\begin{proof}
Suponha, por contradição, que $H$ não seja um $((1-\eta)\delta n/f,f)$-expansor, isto é, existe um subconjunto $U$ de vértices de $H$ tal que $|U|\leq (1-\eta)\delta n/f$ e $|\Gamma_H(U)|<f$. Observe que~${\delta d|U|\leq e_H(U,\Gamma_H(U)) \leq e_G(U,\Gamma_H(U))}$. Pelo Teorema \ref{teorema:EML}, temos que
$$
\begin{aligned}
\delta d|U|&\leq \frac{d}{n}|U||\Gamma_H(U)| + \lambda \sqrt{|U||\Gamma_H(U)|}\\
&\leq\frac{d}{n}|U|(f|U|) + \lambda \sqrt{|U||\Gamma_H(U)|}\\
&\leq\frac{d}{n}|U|(1-\eta)\delta n + \lambda \sqrt{|U||\Gamma_H(U)|}.
\end{aligned}
$$
Assim, $\eta\delta d|U| < \lambda\sqrt{|U||\Gamma_H(U)|}$. Portanto, $|\Gamma_H(U)|>(\eta\delta d/\lambda)^2|U|=f|U|$. Mas isto contradiz a escolha de $U$.
\end{proof}

Enunciamos a seguir um importante lema obtido por Lajos Pósa.

\begin{lema}[Lema de Pósa]\label{lema:posa}
Sejam $G$ um grafo não vazio e $b$ um inteiro positivo tal que, para todo~${X\subset V(G)}$, com $|X|\leq b$, temos $|\Gamma(X)\setminus X|\geq 2|X|-1$. Então $G$ contém um $p^{3b-1}$ (caminho com $3b-1$ vértices).
\end{lema}

É um bom exercício provar o lema acima.

\newpage
\section{Grafos expansores - parte II}
\label{sec:expanders:3}
\begin{center}
 15/03/2010
\end{center}

Inicialmente, vamos relembrar algumas definições.
\begin{definicao}
O \emph{número de Ramsey} é dado por $R(n)=\min\{N\colon K^N\to(K^n,K^n)\}$, onde a notação~${G\to(H_1,H_2)}$ significa que ao colorir as arestas do grafo $G$ com as cores azul e vermelho, existe, em $G$, uma cópia de $H_1$ somente com arestas azuis ou uma cópia de $H_2$ somente com arestas vermelhas.
\end{definicao}

Observe que podemos generalizar o conceito de números de Ramsey.
\begin{definicao}
O \emph{número de Ramsey generalizado} é dado por~${r(H)=\min\{N\colon K^N\to(H,H)\}}$.
\end{definicao}

O seguinte teorema nos dá uma cota superior para o número de Ramsey generalizado.
\begin{teorema}[Chvátal--Rödl--Szemerédi--Trotter \cite{ChRoSzTr83}]\label{teorema:CRZT}
Para todo $\Delta>0$, existe um $c>0$ tal que se~$H$ é um grafo com $n$ vértices e grau máximo $\Delta(H)\leq\Delta$, então $r(H)\leq cn$.
\end{teorema}

Podemos definir também o número de Ramsey relativo às arestas de um grafo. Definimos tal número por~${r_a(H)=\min\{e(G)\colon G\to(H,H)\}}$.

\subsubsection*{Observação}Se $\Delta(H)\leq\Delta$, então, utilizando o Teorema \ref{teorema:CRZT}, temos que
$$r_a(H)\leq {r(H)\choose 2}\leq{cn\choose 2}\leq\frac{1}{2}(cn)^2=c'n^2.$$

Paul Erd\H{o}s fez a seguinte pergunta (oferecendo \$ 100,00 para quem resolvesse): É verdade que~$r_a(P^n)<<{n\choose 2}$? József Beck forneceu a resposta a esta questão mostrando que $r_a(P^n)\leq cn$, para algum $c>0$, porém, através de uma prova não construtiva \cite{Be83}. Em 1988, Noga Alon e Fan~Chung deram uma prova construtiva utilizando $(n,d,\lambda)$-grafos \cite{AlCh88}. Abaixo mostramos um esboço da prova de Alon e Chung.

Seja $G^N$ um $(N,d,\lambda)$-grafo com $\lambda<<d=O(1)$ (lembre-se que tais grafos existem \cite{LuPhSa88,Mar88}). Fixe~${H\subset G}$ com $e(H)\geq e(G)/2$. Afirmamos que se $N$, $d$ e $\lambda$ forem escolhidos apropriadamente, então $H\supset P^n$. De fato, basta que consigamos $d=O(1)$ e $N=O(n)$. Isto prova o resultado.

Observe que $H$ contém um subgrafo $H'$ com $\delta(H')\geq d/4$. De fato, seja inicialmente $H'=H$. Eliminamos vértices de $H'$, sucessivamente, enquanto houver vértices com grau menor que $d/4$. Se exaurirmos o conjunto de vértices, temos menos que $Nd/4=e(G)/2$ arestas em $H$, uma contradição com a escolha de $H$. Logo, ao término deste processo temos o grafo $H'$ desejado.

Com isso, sabemos que $H'$ é um $(b,f)$-expansor, para todo $0<f\leq (d/(8\lambda))^2$ e $b=N/8f$ (para obter tais valores, faça $\delta=1/4$ e $\eta=1/2$ no Teorema \ref{teorema:auxiliar}). Suponha que $(d/(8\lambda))^2\geq 3$. Então, temos que $H'$ é um $(N/24,3)$-expansor.

Tomando $b=\lfloor N/24\rfloor$, temos que se $X\subset V(H')$ com $|X|\leq\lfloor N/24\rfloor$, então $|\Gamma(X)|\geq 3|X|$. Portanto, $|\Gamma(X)\setminus X|\geq 2|X|\geq 2|X|-1$. Pelo Lema \ref{lema:posa} (Lema de Pósa), sabemos que $H'\supset P^{3b-1}$, mas $3b-1=3\lfloor N/24\rfloor - 1\geq3(N/24 - 1)-1=N/8-4$. Portanto, escolhendo $N\geq 8n + 32$, temos que $3b-1\geq n$. Assim, $H'\supset P^{n}$, concluindo a esboço da prova.

Vamos agora provar o Lema de Pósa (Lema \ref{lema:posa}).

\begin{definicao}
Dado um grafo $G=(V,E)$, seja $P$ um caminho entre vértices $x$ e $y$ em $G$. Se $z$ é um vizinho de $y$ que está em $P$ mas não é o vizinho de $y$ em $P$, existe um vizinho $z'$ de $z$, de modo que podemos gerar um novo caminho $P'$ de mesmo tamanho que $P$ adicionando a aresta $\{y,z\}$ e removendo a aresta $\{z,z'\}$ (veja Figura \ref{figura:trocaCaminho}). Chamamos esta transformação de \emph{troca de caminho}.
\end{definicao}

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=16cm]{pathExchange.eps}
  \caption{Troca de caminho de $P$ para $P'$.}
  \label{figura:trocaCaminho}
  \end{center}
\end{figure}

\begin{proof}[Demonstração do Lema de Pósa]
Seja $P$ um caminho máximo no grafo $G$ e $\mathcal{P}$ o conjunto de todos os caminhos obtidos a partir de $P$ através de troca de caminhos. Se $X$ é o conjunto dos extremos de caminhos em $\mathcal{P}$, defina $X^-$ e $X^+$ como os conjuntos de vértices que, respectivamente, antecedem e sucedem imediatamente os elementos de $X$ em $P$. 

Mostraremos inicialmente que $\Gamma(X)\subset X^-\cup X\cup X^+$. Considere um caminho $P'\in\mathcal{P}$ que começa em um vértice $x\in X$ (tal caminho existe, pela definição de $X$) e seja~${y\in V(G)\setminus X^-\cup X\cup X^+}$. Se $y\in V(G)\setminus V(P)$, então, como $P'$ é máximo, $x$ e $y$ não são adjacentes. Suponha agora que~ ${y\in V(P)\setminus X^-\cup X\cup X^+}$. Assim, $y$ possui os mesmos vizinhos em qualquer caminho de~${\mathcal{P}}$, pois uma troca de caminhos que torna $y$ não adjacente a algum desses vizinhos faria com que $y$ ou tal vizinho pertencesse a $X$, uma contradição, pois $y\notin X^-\cup X\cup X^+$. Portanto, uma troca de caminhos aplicada em $P'$ faria com que $y$ fosse vizinho de um elemento em $X$, uma contradição. Logo, $x$ e $y$ não podem ser adjacentes, de onde concluímos que todos os vizinhos de vértices em $X$ estão em $X^-\cup X\cup X^+$.

Sabendo que $\Gamma(X)\subset X^-\cup X\cup X^+$, considere um caminho máximo $P$ em $G$. Assim, temos que~${\Gamma(X)\setminus X\subset X^-\cup X^+}$, de onde concluimos que $|\Gamma(X)\setminus X|\leq 2|X|-2$. Pela hipótese no enunciado do Lema de Pósa, $|X|>b$. Logo, existe $X'\subset X$ tal que $|X'|=b$ e, portanto, temos~${|\Gamma(X')\setminus X'|\geq 2|X'|-1}$. Mas, como $X'\cup\Gamma(X')\subset V(P)$, temos que $$|V(P)|\geq|X'\cup\Gamma(X')|=|X'|+|\Gamma(X')\setminus X'|\geq 3|X'|-1=3b-1.$$ Portanto, existe um $P^{3b-1}$ em $G$.
\end{proof}


\newpage
\section{Grafos expansores - parte III}
\label{sec:expanders:4}
\begin{center}
 22/03/2010
\end{center}

\begin{definicao}
Dado um grafo $G$, um \emph{emparelhamento} é um subconjunto de arestas não adjacentes de $G$. Ademais, dizemos que $M$ cobre $U\subset V(G)$ se todo vértice de $U$ é extremo de alguma aresta em $M$.
\end{definicao}

\begin{teorema}[Teorema de Hall \cite{Ha35}]
Seja $B=(U,W;E)$ um grafo bipartido. Se, para todo $U'\subset U$, temos que $|\Gamma_B(U')|\geq |U'|$, então $B$ possui um emparelhamento que cobre $U$.
\end{teorema}

\begin{proof}[Demonstração (Rado \cite{Ra67})]
Remova as arestas de $B$ até que a hipótese seja satisfeita de forma mi\-ni\-mal, isto é, se removermos qualquer outra aresta de $B$, a hipótese falha. Se $B$ não contém vértices~${u_1,u_2\in U}$ e $w\in W$ tais que $\{u_1,w\},\{u_2,w\}\in E$, então, claramente, existe um em\-pa\-re\-lha\-men\-to que cobre $U$. Portanto, supomos que existem tais vértices $u_1$, $u_2$ e $w$. Como removemos arestas de forma que a hipótese seja válida minimalmente, existem $U_1,U_2\subset U$ (com $u_1\in U_1$ e~$u_2\in U_2$) tais que a hipótese falha para $B_i=B-\{u_i,w\}$, com $i=\{1,2\}$. Assim, $|\Gamma_{B}(U_i)|=|U_i|$, para $i=\{1,2\}$. Ademais, $w\notin \Gamma_B(U_1\setminus\{u_1\})$ e $w\notin \Gamma_B(U_2\setminus\{u_2\})$. Concluímos então que 
$$w\cup(\Gamma_B(U_1\setminus\{u_1\}) \cap \Gamma_B(U_2\setminus\{u_2\}))\subset (\Gamma_B(U_1)\cap \Gamma_B(U_2)),$$ onde $w\notin \Gamma_B(U_1\setminus\{u_1\}) \cap \Gamma_B(U_2\setminus\{u_2\})$. Portanto,
$$
\begin{aligned}
|\Gamma_B(U_1)\cap\Gamma_B(U_2)| &\geq |\Gamma_B(U_1\setminus\{u_1\}) \cap \Gamma_B(U_2\setminus\{u_2\})| + 1\\
&\geq |\Gamma_B(U_1\setminus\{u_1\} \cap U_2\setminus\{u_2\})| + 1\\
&=|\Gamma_B(U_1\cap U_2)| + 1.
\end{aligned}
$$
Podemos então concluir que
$$
\begin{aligned}
|\Gamma_B(U_1\cup U_2)| &= |\Gamma_B(U_1)\cup\Gamma_B(U_2)|=|\Gamma_B(U_1)| + |\Gamma_B(U_2)| - |\Gamma_B(U_1)\cap\Gamma_B(U_2)|\\
&\leq |\Gamma_B(U_1)| + |\Gamma_B(U_2)| - (|\Gamma_B(U_1\cap U_2)|+1)\\
&=|U_1| + |U_2| - |\Gamma_B(U_1\cap U_2)|-1\\
&\leq|U_1| + |U_2| - |U_1\cap U_2|-1\\
&=|U_1\cup U_2|-1,
\end{aligned}
$$
uma contradição.
\end{proof}

Provaremos agora um resultado de Friedman e Pippenger \cite{FrPi87} sobre contenção de árvores em certos grafos com propriedades de expansão. Para isso, precisamos de algumas definições.

\begin{definicao}
Seja $G$ um grafo, $T$ uma árvore e $n$, $d$ inteiros positivos. Dizemos que uma árvore $T$ é ($n,d$)-\emph{pequena}, ou simplesmente \emph{pequena} se $|V(T)|\leq n$ e $\Delta(T)\leq d$.
\end{definicao}

Lembre-se que um grafo $G$ é dito $(b,f)$-expansor se $|\Gamma(X)|\geq f|X|$, para todo $X\subset V(G)$ tal que~${|X|\leq b}$. No Teorema \ref{teorema:frpi87}, denotamos um $(2n-2,d+1)$-expansor simplesmente por \emph{expansor}.

\begin{definicao}
Uma \emph{imersão} de um grafo $H$ em um grafo $G$ é uma função injetiva $f:V(H)\to V(G)$ com $\{f(x),f(y)\}\in E(G)$ para todo $\{x,y\}\in E(H)$, isto é, $f$ preserva adjacências.
\end{definicao}



\begin{teorema}[Friedman--Pippenger \cite{FrPi87}]\label{teorema:frpi87}
Fixe $n,d>0$. Todo grafo expansor não vazio $G$ contém toda árvore ($n,d)$-pequena $T$.
\end{teorema}

\begin{proof}
Fixe $f:V(T)\to V(G)$ uma imersão de $T$ em $G$. Definimos:
\begin{itemize}
\item[1.] Para todo $x\in V(G)$, defina $J_f(x) = \deg_T(f^{-1}(x))$, se $x\in f(V(T))$, e 0, caso contrário.
\item[2.] $A_f(X) = |\Gamma_G(X)\setminus f(V(T))|$, onde $X\subset V(G)$.
\item[3.] $B_f(X) = \sum_{x\in X}B_f(x)$, onde $B_f(x)=d-J_f(x)$ e $X\subset V(G)$.
\item[4.] $C_f(X) = A_f(X) - B_f(X)$, onde $X\subset V(G)$.
\end{itemize}

Dizemos que um conjunto $X\subset V(G)$ é \emph{solvente} se $C_f(X)\geq 0$, é \emph{crítico} se $C_f(X)= 0$ e é~\emph{falido} se $C_f(X)< 0$. Uma imersão é dita \emph{boa} se todo $X\subset V(G)$, com $|X|\leq 2n-2$, é solvente. Vamos provar as seguintes proposições.
\begin{itemize}
\item[$P_1$.]Se $|V(T)|=1$, então qualquer imersão $f:V(T)\to V(G)$ é boa.
\item[$P_2$.]Seja $v$ uma folha de $T$ e $S=T-v$. Se $f:V(S)\to V(G)$ é uma imersão boa, então existe uma extensão $g:V(T)\to V(G)$ que é boa.
\end{itemize}
Observe que isso prova o resultado.
\end{proof}


\subsection{Problemas e exercícios}
\label{sec:exercicios:espanders4}
Todos estão convidados a trabalhar nos seguintes e\-xer\-cí\-cios. 

Nos exercícios abaixo, dado um grafo $G$, denote por $r(G)$ o número máximo de arestas em uma floresta (grafo acíclico) contida em $G$.
\begin{enumerate}
\item[1.]Suponha que $F_1,F_2\ldots,F_n$ sejam $n$ florestas com conjunto de vértices $[n]$. Imaginemos que~$F_i$ seja \emph{colorido} com a cor $i$, para $i=1,\ldots,n$. Suponha que, para todo~${I\subset[n-1]}$, temos~${r(\bigcup_{i\in I}F_i)\geq |I|}$. Mostre que $\bigcup_{i=1}^{n-1}F_i$ contém uma árvore geradora (floresta com $n-1$ arestas) multicolorida, isto é, onde todas suas arestas têm cores diferentes.
\item[2.]Seja $V$ um espaço vetorial de dimensão finita. Considere $F_i\subset (V)$, para $i=1,\ldots,N$. Suponha que, para todo $I\subset[N]$, temos ${r(\bigcup_{i\in I}F_i)\geq |I|}$, onde $r(X)=\dim\langle X\rangle$. Mostre que existe $T=(t_i)^N$, com $t_i\in F_i$ para todo $i=1,\ldots,N$ e $t_1,\ldots,t_N$ linearmente independentes.
\item[3.]Seja $B=(U,W;E)$ um grafo bipartido e $k\in\mathbb{N}$ fixo. Suponha que, para todo $U'\subset U$, temos~$|\Gamma(U')|\geq k|U'|$. Prove que existe $H\subset B$ tal que, para todo $u\in U$, vale $d_H(u)=3$ e, para todo $w\in W$, vale $d_H(w)\leq 1$.
\item[4.]Demonstre a proposição $P_1$ na prova do Teorema \ref{teorema:frpi87}.

\end{enumerate}


\newpage
\section{Grafos expansores - parte IV}
\label{sec:expanders:5}
\begin{center}
05/04/2010
\end{center}

Dando continuidade à prova do Teorema \ref{teorema:frpi87} sobre contenção de árvores \emph{pequenas} em expansores, precisamos provar a proposição $P_2$ enunciada na seção anterior. Dados $n,d>0$, seja~$G$ um~${(2n-2,d+1)}$-expansor (por simplicidade, chamemos somente de \emph{expansor}) e $T$ uma árvore pequena~${(|V(T)|\leq n}$ e $\Delta(T)\leq d$). Relembrando:
\begin{itemize}
\item[$P_2$.] Seja $v$ uma folha de $T$ e $S=T-v$. Se $f:V(S)\to V(G)$ é uma imersão boa, então existe uma extensão $g:V(T)\to V(G)$ que é boa.
\end{itemize}

Nos três lemas abaixo, que nos permitiram provar a proposição $P_2$, considere um expansor $G$, uma árvore pequena $T$ e $S=T-v$, onde $v$ é uma folha de $T$.

\begin{lema}\label{lema:lema1}
Seja $X\subset V(G)$. Se $C_f(X)=0$ e $|X|\leq 2n-2$, então $|X|\leq n-1$.
\end{lema}
\begin{proof}
Observe que $|\Gamma_G(X)|\geq(d+1)|X|$. Assim, $$A_f(X)\geq(d+1)|X| - |f(V(S))| = d|X| + |X| - (n-1).$$
Ademais, $B_f(X)\leq d|X|$. Portanto, $0=C_f(X)\geq d|X|+|X|-n+1-d|X|$, isto é, $|X|\leq n-1$.
\end{proof}

\begin{definicao}
Seja $Z$ um conjunto. Dizemos que uma função $\varphi\colon\mathcal{P}(Z)\to \mathbb{R}$ é \emph{submodular} se, para todos $A,B\subset Z$, temos que $\varphi(A\cup B)+\varphi(A\cap B)\leq\varphi(A) + \varphi(B)$.
\end{definicao}


\begin{lema}\label{lema:lema2}
Prove que $C_f(X)$ é submodular.
\end{lema}
\noindent\emph{Demonstração.}
Exercício 2.


\begin{lema}\label{lema:lema3}
Seja $f$ uma imersão boa e $X,Y\subset V(G)$ tais que $C_f(X),C_f(Y)=0$ e ${|X|,|Y|\leq n-1}$. Assim, temos que $C_f(X\cup Y)=0$ e $|X\cup Y|\leq n-1$.
\end{lema}
\begin{proof}
Temos que $|X\cup Y|,|X\cap Y|\leq 2n-2$. Como $f$ é boa e $C_f(X)$ é submodular (pelo Lema \ref{lema:lema2}), temos que $$0\leq C_f(X\cup Y) + C_f(X\cap Y) \leq C_f(X) + C_f(Y) = 0.$$
Portanto, $C_f(X\cup Y),C_f(X\cap Y)=0$. Pelo Lema \ref{lema:lema1}, $|X\cup Y|\leq n-1$.
\end{proof}

\begin{proof}[Demonstração da proposição $P_2$] Seja $T$ uma árvore pequena e $S$ a árvore obtida através da remoção de uma folha $v$ de $T$ e a aresta $\{v,w\}$ incidente a $v$. Considere $\xi$ o conjunto das imersões que são extensões de $F$ para $T$. Tome~${Y=\Gamma_G(f(w))\setminus f(V(S))}$. O mapeamento $g\mapsto g(v)$ é, claramente, uma bijeção entre $\xi$ e $Y$.

Suponha, por contradição, que nenhuma extensão $g\in\xi$ é boa. Assim, para cada $g\in\xi$, existe um conjunto $X_g\subset V(G)$ com $|X_g|\leq 2n -2$ tal que \begin{equation}\label{equacao:gRuim}
C_g(X_g)<0.
\end{equation}
Como $f$ é uma imersão boa, temos que
\begin{equation}\label{equacao:fBom}
C_f(X_g)\geq 0.
\end{equation}
Temos que $g(V(T)) = (\im f) \cup \{g(v)\} = f(V(S))\cup\{g(v)\}$. Ademais,~${A_g(X) = |\Gamma_G(X)\setminus g(V(T))|}$, isto é,  $A_g(X)=A_f(X) - [g(v)\in\Gamma_G(X)]$, onde $[p]=1$ se $p$ é válido e $[p]=0$ se $p$ é falso.
Observe que, como $E(T)=E(S)\cup\{v,w\}$, temos $B_g(X) = B_f(X) - [f(w)\in X] - [g(v)\in X]$. Assim, temos que~${C_g(X) = C_f(X) - [g(v)\in\Gamma_G(X)] + [f(w)\in X] + [g(v)\in X]}$.

Por (\ref{equacao:gRuim}) e (\ref{equacao:fBom}), deduzimos que, para toda extensão $g\in\xi$, valem as seguintes quatro afirmações:
\begin{itemize}
\item[1)]  $C_f(X_g)=0$.
\item[2)]  $g(v)\in\Gamma_G(X_g)$.
\item[3)]  $f(w)\in\ X_g$.
\item[4)]  $g(v)\notin X_g$.
\end{itemize}

Ponha $X^*=\bigcup_{g\in\xi}X_g$. Pelo Lema \ref{lema:lema1}, $|X_g|\leq n-1$, para todo $g\in\xi$. Assim, por indução e pelo Lema \ref{lema:lema3}, temos que $C_f(X^*)=0$ e $|X^*|\leq n-1$. Ponha agora $X'=X^*\cup\{f(w)\}$. Temos que~${|X'|\leq n}$. Como $f$ é boa, $C_f(X')\geq 0$.

Sabemos que $g(v)\in\Gamma_G(X_g)$ para toda extensão $g\in\xi$. Assim, $Y\subset\Gamma_G(X^*)$. Portanto,
$$
\begin{aligned}
A_f(X') &= A_f(X^*\cup f(w))\\
&=\Gamma_G(X^*\cup f(w))\setminus f(V(S))\\
&=\Gamma_G(X^*)\setminus f(V(S))\\
&=A_f(X^*).
\end{aligned}
$$

Temos $f(w)\notin X_g$ para toda extensão $g\in\xi$. Portanto, $f(w)\notin X^*$. Portanto, temos que~${B_f(X')= B_f(X^*) + B_f(f(w)) = B_f(X^*) + d - J_f(f(w)) > B_f(X^*).}$
Logo, podemos concluir que $0\leq C_f(X')=A_f(X') - B_f(X') < A_f(X^*) - B_f(X^*) = C_f(X^*) = 0$, uma contradição.


\end{proof}


\subsection{Problemas e exercícios}
\label{sec:exercicios:espanders5}
Todos estão convidados a trabalhar nos seguintes e\-xer\-cí\-cios. 

\begin{enumerate}
\item[1.]Seja $G$ um grafo e $X\subset V(G)$. Mostre que $\varphi(X)=|\Gamma_G(X)|$ é submodular.
\item[2.]Prove o Lema \ref{lema:lema2}.
\end{enumerate}

\newpage
\section{Hipergrafos com número cromático alto sem circuitos pequenos}\footnotetext[1]{Os resultados desta seção foram apresentados pelo aluno Marcelo Matheus Gauy.}
\label{sec:hiper-NeRo}
\begin{center}
 12/04/2010
\end{center}

\begin{definicao}
Um \emph{hipergrafo $l$-uniforme} (ou \emph{$l$-grafo}) é um par $(X,\mathcal{M})$ com~${\mathcal{M}\subset {{X}\choose{l}}}$, onde temos que~${{{X}\choose{l}} = \{U\subset X\colon \lvert
U\rvert = l\}}$.
\end{definicao}

\begin{definicao}
Um hipergrafo $G=(X,\calm)$ é dito \emph{$a$-partido} se existe uma partição $\{X_1,X_2,\ldots,X_a\}$ de $X$ em que cada aresta de $\calm$ contém no máximo um vértice de cada classe de vértices da partição.
\end{definicao}
\subsubsection*{Observação} Um grafo é um $2$-grafo.

\begin{definicao}
Um circuito de tamanho $p$ em um hipergrafo $(X,\calm)$ é uma sequência $M_1,\ldots,M_p$ de arestas diferentes de $\calm$ onde existem diferentes vértices $x_i\in M_i\cap M_{i+1}$, com $i\in\{1,2,\ldots,p-2\}$ e $x_p\in M_1\cap M_p$.
\end{definicao}

\begin{definicao}
A \emph{cintura} $g(G)$ de um hipergrafo $G$ é o comprimento do menor circuito em $G$.
\end{definicao}


Apresentamos, nesta seção, uma prova construtiva da existência de hipergrafos com número cromático e cintura arbitrariamente grandes. Formalmente, provamos o seguinte resultado.

\begin{teorema}[Ne\v{s}et\v{r}il--Rödl \cite{NeRo79}]\label{teo:NeRo79}
Para quaisquer inteiros positivos $l$, $n$, $p$, existe um $l$-grafo $(X,\calm)$ tal que
\begin{itemize}
\item[1)]Todos os circuitos de $(X,\calm)$ tem tamanho maior que $p$.
\item[2)]$\chi(X,\calm)> n$.
\end{itemize}
\end{teorema}

Antes de provar o Teorema \ref{teo:NeRo79}, precisamos definir uma operação entre certos hipergrafos. Dados
\begin{itemize}
  \item[-] $((X_i),\calm)$ um $l$-grafo $a$-partido, onde $(X_i)$ é a partição $\{X_1,X_2,\ldots,X_a\}$ de um conjunto $X$ e $|X_r|=k$ para um $r\in[1,a]$ fixo,
  \item[-] $(Y,\caln)$ um $k$-grafo,
\end{itemize}
dizemos que $(Y,\caln) \ast_{r} ((X_i),\calm)$ é o $l$-grafo $a$-partido $((X_i'),\calm')$, onde os vértices desse hipergrafo são definidos por
\begin{itemize}
  \item[-] $X_i'=X_i\times \caln$, para $i\neq r$,
  \item[-] $X_r' = Y$,
\end{itemize}
e uma hiperaresta $M'$ pertence a $\calm'$ se e somente se existem $N\in\caln$ e $M\in\calm$ tais que
\begin{itemize}
  \item[-] $M'\cap X_i' = (M\cap X_i,N)$, para $i\neq r$,
  \item[-] $M'\cap X_r' = \iota_N(M\cap X_r)$,
\end{itemize}
onde $\iota_N\colon X_r\to N$ é uma bijeção, para $N\in\caln$. Denotados uma hiperaresta $M'\in\calm'$ por um par~${(M,N)}$. Na Figura \ref{figura:amalgama}, temos um exemplo mostrando o que acontece com uma aresta que contém interseção com $X_r$ quando realizamos esta operação.

\begin{figure}[h!]
  \begin{center}
    \includegraphics[width=16cm]{amalgama.eps}
  \caption{Resultado da operação $Y\ast_4 G$ em um $4$-grafo $Y$ e um $3$-grafo $G$ com partição $\{X_1,X_2,X_3,X_4\}$, onde $|X_4|= 4$. Do lado esquerdo temos os hipergrafos $G$ e $Y$ e as bijeções $\iota_f$ e $\iota_{f'}$. Do lado direito temos o resultado da operação.}
  \label{figura:amalgama}
  \end{center}
\end{figure}

\begin{proof}[Demonstração do Teorema \ref{teo:NeRo79}]
Fixe $n$, $l$. Provamos o resultado utilizando indução em $p$. Se~${p=1}$, o resultado é válido, pois não temos restrição alguma quanto ao tamanho dos circuitos. Tome $p>1$ e suponha que o resultado é válido para $1\leq p'<p$. Seja $a=(l-1)n + 1$ e considere o $l$-grafo $a$-partido $((X_i^1),\calm^1)$ onde, para cada conjunto de $l$ partes $\omega\subset[1,a]$ com $|\omega|=l$, existe uma aresta~${M\in\calm^1}$ onde $M\cap X_i^1\neq\varnothing$ para todo $i\in\omega$. Claramente, $((X_i^1),\calm^1)$ pode ser escolhido de modo a não conter circuitos de tamanho menor ou igual a $p$, pois podemos utilizar quantos vértices forem necessários em cada $X_i$.

Indutivamente, definimos $l$-grafos $a$-partidos $((X_i^t),\calm^t)$, onde $t\in[2,a+1]$. Se $((X_i^{t-1}),\calm^{t-1})$ é um $l$-grafo $a$-partido tal que $|X_{t-1}^{t-1}|=k_{t-1}$, então, pela hipótese indutiva, sabemos que exis\-te um~$k_{t-1}\text{-grafo}$~${(Y^{t-1},\caln^{t-1})}$ sem circuitos de tamanho menor que $p$ e com número cromático maior que $n$. Assim, fazemos $((X_i^t),\calm^t) = (Y^{t-1},\caln^{t-1}) \ast_{t-1}  ((X_i^{t-1}),\calm^{t-1})$. Mostraremos que o~${\text{$l$-grafo}\  ((X_i^{a+1}),\calm^{a+1})}$ não possui circuitos com tamanho menor ou igual a $p$ e tem número cromático maior que $n$.

Utilizando indução em $j$, mostramos agora que $((X_i^j),\calm^j)$ não contém circuitos de tamanho menor ou igual a $p$ para $j\in[1,a+1]$. Suponha, por contradição, que $((X_i^j),\calm^j)$ não contém circuitos de tamanho menor ou igual a $p$, mas $((X_i^{j+1}),\calm^{j+1})$ contém tal circuito $C=\{M_1',\ldots,M'_q\}$, com $q\leq p$. Assim, as arestas $M_1',\ldots,M_q'$ podem ser denotadas por $(M_1,N_1),\ldots,(M_q,N_q)$. Mas veja que $N_1,\ldots,N_q$ não podem ser todos iguais, pos teríamos um circuito de tamanho $q$ em~${((X_i^j),\calm^j)}$. Ademais, pela definição de $((X_i^{j+1}),\calm^{j+1})$, temos que $N_1,\ldots,N_q$ também não podem ser todos diferentes. Mas como $C$ é um circuito, $N_1,\ldots,N_q$ contém um circuito de tamanho no máximo $q-1$ em $(Y^j,\caln^j)$, uma contradição com a escolha de $(Y^j,\caln^j)$.

Resta mostrar que $\chi((X_i^{a+1}),\calm^{a+1})>n$. Suponha, por contradição, que ${\chi(X_i^{a+1}),\calm^{a+1})\leq n}$. Seja $c$ uma coloração com $n$ cores dos vértices de ${((X_i^{a+1}),\calm^{a+1}) = (Y^a,\caln^a)\ast_a((X_i^{a}),\calm^{a})}$. Lembrando que $\chi(Y^a,\caln^a)>n$, existe $N^a\in\caln^a$ tal que $|c(N^a)|=1$. Considere tal coloração aplicada a~${(X_{a-1}^a;N^a) = \{(x,N^a)\colon x\in X^a_{a-1}\}}$. Mas ${((X_i^{a}),\calm^{a}) = (Y^{a-1},\caln^{a-1})\ast_{a-1}((X_i^{a-1}),\calm^{a-1})}$ e~${\chi(Y^{a-1},\caln^{a-1})>n}$, assim, existe $N^{a-1}\subset X_{a-1}^{a}$, tal que $X_{a-1}^{a}\in\caln^{a-1}$ e ${|c(N^{a-1};N^a)|=1}$. Repetindo o processo, temos uma aresta $N^i\in\caln^i$ tal que ${|c(N^i;N^{i+1},\ldots,N^a|=1}$ para~${i\in[1,a]}$. Definindo $Z_i=|c(N^i;N^{i+1},\ldots,N^a|=1$, temos que $Z_i\subset X_i^{a+1}$. Pela definição de~${((X_i^{a+1}),\calm^{a+1})}$, o subhipergrafo de ${((X_i^{a+1}),\calm^{a+1})}$ formado por $\bigcup_{i=1}^{a}Z_i$ contém uma cópia de~${((X_i^1,\calm^1)}$. Assim, como $a=(l-1)n + 1$, existe $\omega\subset[1,a]$ com $|\omega|=l$ tal que $|c(\bigcup_{i\in\omega}Z_i)|=1$. Mas, lembrando da definição de~${((X_i^1,\calm^1)}$, existe uma aresta monocromática $M\in\calm^1$ tal que $M\subset\bigcup_{i\in\omega}Z_i$. Portanto, temos uma contradição.


\end{proof}



\newpage
\section{Teorema da amizade / funções limiares}\footnotetext[1]{Os resultados desta seção foram apresentados pelo aluno Thiago da Silva Pinheiro.}
\label{sec:amizade-limiares}
\begin{center}
 19/04/2010
\end{center}


\section*{Teorema da amizade}

\begin{teorema}[Teorema da Amizade (Erd\H{o}s--Rényi--Sós \cite{ErReSo66}]\label{teo:ErReSo66}
Se $G$ é um grafo em que quaisquer dois vértices distintos possuem um único vizinho, então $G$ tem um vértice que é vizinho de todos os outros vértices.
\end{teorema}

\begin{proof}
Seja $G=(V,E)$ um grafo. Suponha, por contradição, que não existe um vértice que é vizinho de todos os outros vértices. Seja $k$ o maior grau de um vértice em $G$ e $v$ um vértice de grau $k$. Sejam $w_1,\ldots,w_k$ os vizinhos de $v$ e seja $x$ um vértice qualquer que não é vizinho de~$v$ (ele existe, pela suposição que fizemos no início da prova). Claramente, $x$ só pode ser vizinho de um único elemento em $\{w_1,\ldots,w_k\}$, pois caso contrário $x$ e $v$ teriam dois vizinhos em comum. Seja $z_i$ um vizinho em comum de $x$ e $w_i$, onde $\{x,w_i\}\notin E$ (ele existe, pois a distância entre $x$ e $w_i$ é dois). Sabemos que tal $z_i$ está à distância dois de $v$, pois não pode ser um dos elementos de $\{w_1,\ldots,w_k\}$ e qualquer par de vértices está à distância dois em $G$. Observe agora que cada $z_i$ é único, pois caso contrário $x$ e $w_i$ teriam dois vizinhos em comum. Assim, concluímos que $\deg(x)=k$, o grau máximo de $G$. Repetindo o mesmo procedimento (com $x$ fazendo o papel de $v$), obtemos que todo vértice possui grau $k$. Portanto, $G$ é $k$-regular, de modo que possui $1+k+k(k-2)$ vértices.

Seja $A$ a matriz de adjacência de $G$. A matriz $A^2=(a_{i,j})$ é tal que $a_{i,j}$ contém a quantidade de caminhos de tamanho dois entre os vértices $i$ e $j$. Temos que $\det(A^2 - \lambda I) = (k^2-\lambda)(k-1-\lambda)^{k^2-k}$, logo $k^2$ é autovalor de $A^2$ e $k-1$ é autovalor de $A^2$ com multiplicidade $k^2-k$. Assim, temos que os autovalores de $A$ são $k$, $\sqrt{k-1}$ e $-\sqrt{k-1}$. Se $r$ a multiplicidade de $\sqrt{k-1}$ e $s$ a multiplicidade de $-\sqrt{k-1}$, então $k+r\sqrt{k-1}-s\sqrt{k-1}=0$. Desta forma, $k^2=(s-r)^2(k-1)$. Portanto, temos que $k-1|k^2$, que implica $k-1|k$ e assim, $k-1|1$. Assim, temos que $k=2$, um absurdo, pois $G$ seria um triângulo (todos os vértices são vizinhos de todos os outros).
\end{proof}
% \newpage
\section*{Funções limiares}


\begin{definicao}
Dada uma variável aleatória $X$. A variância de $X$ é dada por $$\var(X) = \bbe((X-\mathbb{E}(X))^2)=\mathbb{E}(X^2)-\mathbb{E}(X)^2.$$
\end{definicao}

\begin{definicao}
Dadas duas variáveis aleatórias $X$ e $Y$. A covariância de ($X,Y$) é dada por $$\cov(X,Y) = \bbe(XY)-\bbe(X)\bbe(Y).$$
\end{definicao}

Se $X\geq 0$ e $\lambda>0$, a seguinte desigualdade é válida.
\begin{equation}\label{eq:markov}
\Pr(X\geq\lambda)\leq\frac{\mathbb{E}(X)}{\lambda}.
\end{equation}
Fazendo $X=(Y-\mathbb{E}(Y))^2$ e $\lambda=\omega^2$ em (\ref{eq:markov}), temos $\Pr((Y-\mathbb{E}(Y))^2\geq\omega^2)\leq\var(Y)/\omega^2$. Logo,
\begin{equation}\label{eq:chebyshev}
\Pr(|Y-\mathbb{E}(Y)|\geq\omega)\leq\frac{\var(Y)}{\omega^2}.
\end{equation}
Fazendo $\lambda=1$ em (\ref{eq:markov}) temos que 
\begin{equation}\label{eq:markovum}
\Pr(X\geq 1)\leq\bbe(X).
\end{equation}
Fazendo $\omega=\bbe(Y)$ em (\ref{eq:chebyshev}) temos que 
\begin{equation}\label{eq:chebzero}
\Pr(Y=0)\leq\frac{\var(Y)}{\bbe(Y)^2}.
\end{equation}

\begin{definicao}
Dizemos que uma função $f(n)<<g(n)$ quando $\lim_{n\to\infty} f(n)/g(n) = 0$.
\end{definicao}

\begin{definicao}
Dizemos que $G_{n,p}$ é um grafo com $n$ vértices onde cada par de vértices define uma aresta do grafo independentemente com probabilidade
$p$.
\end{definicao}


\begin{definicao}
Considere o grafo $G_{n,p}$. Dizemos que $f(n)$ é \emph{função limiar} para um evento $A$ se temos as seguintes afirmações.
\begin{itemize}
 \item[a)] Se $p>>f(n)$, então $\lim_{n\to\infty}\Pr(A)=1$ ($1$-afirmação);
 \item[b)] Se $p<<f(n)$, então $\lim_{n\to\infty}\Pr(A)=0$ ($0$-afirmação).
\end{itemize}
\end{definicao}
\newpage
\begin{teorema}
A função $n^{-2/3}$ é limiar para o evento $K^4\subset G_{n,p}$.
\end{teorema}
\begin{proof}
Seja $S$ um conjunto de quatro vértices. Definimos a variável aleatória indicadora~$X_S$ como sendo $1$ caso $S$ induza um $K^4$ em $G_{n,p}$ e $0$ caso contrário. Assim, se $X$ representa a quantidade de cópias de $K^4$ em $G_{n,p}$, temos que $X=\sum_{S}X_S$. Desta forma, sabemos que $\bbe(X)=\sum_{S}\bbe(X_S)$, portanto,~$\bbe(X)=O(n^{4}p^6)$.

Mostramos agora a $0$-afirmação. Suponha que $p<<n^{-2/3}$. Pela desigualdade (\ref{eq:markovum}) podemos concluir que~${\Pr(X\geq 1)\leq\bbe(X)=O(n^{4}p^6)<<1}$. Assim, quando $n\to\infty$, temos que $\Pr(X\geq 1)$ tende a zero, isto é, $G_{n,p}$ não contém cópias de $K^4$.

A $1$-afirmação requer um pouco mais de esforço. Suponha que $p>>n^{-2/3}$. Vamos mostrar que~$\Pr(X=0)$ tende a zero quando $n\to\infty$. Observe que 
$$
\begin{aligned}
\bbe(X^2)&=\displaystyle\sum_{S}\bbe({X_S}^2) + \displaystyle\sum_{(S,T),\ S\neq T}\bbe(X_S X_T).\\
\bbe(X)^2&=\left(\bbe\left(\displaystyle\sum_S X_S\right)\right)^2 = \left(\displaystyle\sum_S \bbe\left(X_S\right)\right)^2\\
&=\displaystyle\sum_{S}\bbe(X_S)^2 + \displaystyle\sum_{(S,T),\ S\neq T}\bbe(X_S)\bbe(X_T).
\end{aligned}
$$
Assim, temos que
$$
\begin{aligned}
\var(X) &= \bbe(X^2)-\bbe(X)^2\\
&=\displaystyle\sum_S\left(\bbe({X_S}^2) - \bbe(X_S)^2\right) + \displaystyle\sum_{(S,T),\ S\neq T}\bbe(X_S X_T) - \displaystyle\sum_{(S,T),\ S\neq T}\bbe(X_S)\bbe(X_T)\\
&=\displaystyle\sum_S\var(X_S) + \displaystyle\sum_{(S,T),\ S\neq T}\cov(X_S,X_T).
\end{aligned}
$$

Para utilizarmos a desigualdade (\ref{eq:chebzero}) e obter o resultado que estamos procurando, precisamos li\-mi\-tar superiormente o valor de $\var(X)$. Observe que $\var(X_S) = \bbe({X_S}^2)-\bbe(X_S)^2\leq \bbe({X_S}^2)$. Mas como~$X_S$ é uma variável indicadora, temos $\var(X_S)\leq\bbe(X_S)=p^6$. Logo,~${\sum_{S}\var(X_S)=O(n^4p^6)}$.

Resta limitarmos superiormente a covariância de $X_S$ e $X_T$ quando $S\neq T$. Se~${|S\cap T|\leq 1}$, então~${\cov(X_S,X_T)=0}$. Se~${|S\cap T|=2}$, como~${\cov(X_S,X_T)\leq \bbe(X_S X_T)}$, temos que~${\cov(X_S,X_T)\leq p^{11}}$, de onde concluímos que~${\sum \cov(X_S,X_T)=O(n^6p^{11})}$, onde a soma é sobre os pares $(S,T)$ tais que~${|S\cap T|=2}$. Por fim, se~${|S\cap T|=3}$, como~${\cov(X_S,X_T)\leq \bbe(X_S X_T)}$, temos~${\cov(X_S,X_T)\leq p^{9}}$, de onde concluímos que~${\sum \cov(X_S,X_T)=O(n^5p^{9})}$, onde a soma é sobre os pares $(S,T)$ tais que~${|S\cap T|=3}$. Desta forma, podemos calcular um limitante superior para $\var(X)$.

$$
\begin{aligned}
\var(X)&=\displaystyle\sum_S\var(X_S) + \displaystyle\sum_{(S,T),\ S\neq T}\cov(X_S,X_T)\\
&=O(n^4p^6 + n^6p^{11} + n^5p^9).
\end{aligned}
$$
Sabemos que $\bbe(X)=O(n^{4}p^6)$. Portanto, temos todos os ingredientes para aplicar a desigualdade~(\ref{eq:chebzero}).
$$
\begin{aligned}
\Pr(X=0)&=O\left(\frac{n^4p^6}{n^8p^{12}} + \frac{n^6p^{11}}{n^8p^{12}} + \frac{n^5p^9}{n^8p^{12}}\right)\\
&=O(n^{-4}p^{-6} + n^{-2}p^{-1} + n^{-3}p^{-3})\\
&<<1,
\end{aligned}
$$
onde a última relação segue pela escolha de $p$. Assim, quando $n\to\infty$, temos que~$\Pr(X=0)$ tende a zero, isto é, $G_{n,p}$ contém pelo menos uma cópia de $K^4$.
\end{proof}

Vimos que se $p<<n^{-2/3}$, então $\Pr(K_4\subset G_{n,p})$ tende a zero quando $n$ tende a infinito. Vimos também que se $p>>n^{-2/3}$, então $\Pr(K_4\subset G_{n,p})$ tende a infinito quando $n$ tende a infinito. Portanto, é natural perguntar o que acontece quando $p=cn^{-2/3}$, onde $c$ é uma constante. É um bom exercício tentar estimar $\lim_{n\to\infty}\Pr(K_4\nsubseteq G_{n,p})$, onde $p=cn^{-2/3}$.


\subsection{Problemas e exercícios}
Todos estão convidados a trabalhar nos seguintes e\-xer\-cí\-cios. 


Dizemos que $G\xrightarrow{ind}H$ se, colorindo as arestas de $G$ com duas cores, necessariamente existe um subgrafo $H'$ \emph{induzido} de $G$ tal que $H'\sim H$ e
$H'$ é monocromático.



\begin{enumerate}
\item[1.]Encontre um grafo $G$ tal que
\item[(\textit{i})]$G\xrightarrow{ind} C^4$.
\item[(\textit{ii})]$G\xrightarrow{ind} C^5$.
\item[2.]Encontre um grafo $G$ tal que
\item[(\textit{i})]$G\to K^3$ e $G\nsupseteq K_4$.
\item[(\textit{ii})]$G\to K^3$ e $G\nsupseteq K_5$.
\item[(\textit{iii})]$G\to K^3$ e $G\nsupseteq K_6$.
\end{enumerate}


\newpage
\section{Um problema geométrico de Erd\H{o}s e Füredi}
\label{sec:26-04-2010}
\begin{center}
 26/04/2010
\end{center}

\begin{definicao}
Seja $\bbe^d$ o espaço euclidiano $d$-dimensional. Dizemos que $\calp\subset\bbe^d$ \emph{determina} o ângulo~${\alpha}$ se existem $a, b, c\in\calp$ tal que $\sphericalangle abc = \alpha$.
\end{definicao}

\begin{definicao}
Seja $\calp$ finito. Pomos~${\alpha_d(\calp) = \max\{0\leq\alpha\leq\pi\:\calp\text{ determina }\alpha\}}$. Ademais,
pomos também~${\alpha_d(n) = \inf_{\calp\subset\bbe^d}\{\alpha_d(\calp)\: |\calp|=n\}}$.
\end{definicao}

Observe que, por exemplo, $\alpha_2(3)=\pi/3$. De fato, se~${\calp}$ é um conjunto de três pontos formando um triângulo equilátero, então obtemos~${\alpha_2(3)\leq\pi/3}$. Sabemos também que, como quaisquer três pontos não colineares no plano formam um triângulo, todo conjunto~${\calp}$ determina um ângulo maior ou igual a~${\pi/3}$, de onde concluímos que~${\alpha_2(3)\geq\pi/3}$.

\begin{definicao}
Pomos~${f(d) = \max_{\calp\subset\bbe^d}\{|\calp|\:\text{$\calp$ determina somente ângulos agudos}\}}$.
\end{definicao}

Veja que, por exemplo, $f(2)=3$. De fato, se~${\calp}$ é um conjunto de três pontos formando um triângulo equilátero, então obtemos~${f(2)\geq3}$. Observe que, se $|\calp|\geq 4$, então o fecho convexo de $\calp$ é um quadrilátero ou um triângulo que contém pontos em seu interior. Em ambos os casos, existe um ângulo que não é agudo. Portanto,~${f(2)\leq3}$.

Considere a seguinte invariante~${f'(d) = \max_{\calp\subset\bbe^d}\{|\calp|\:\text{$\calp$ determina somente ângulos $\leq\pi/2$}\}}$. Temos que $f'(d)\geq 2^d$ (contrua um hipercubo de dimensão $d$). Danzer e Grünbaum \cite{DaGr62} provaram o seguinte resultado sugerido por Erd\H{o}s \cite{Er57}: $f'(d)\leq 2^d$ (Exercício \ref{exercicios:26-04}.3).

Erd\H{o}s e Füredi sugeriram que existe uma constante absoluta~${\varepsilon>0}$ tal que~${\alpha_d(2^d+1)\geq\pi/2 + \varepsilon}$. Conjecturava-se que~${f(d)\leq 2d-1}$. Porém, Erd\H{o}s e Füredi \cite{ErFu83} provaram que~${f(d)\geq(1.18\ldots)^d}$, sempre que~${d\geq d_0}$, para algum $d_0>0$. Um resultado que encontra-se em aberto até os dias de hoje é mostrar que~${f(d)\leq(2-\varepsilon)^d}$ para algum~${\varepsilon>0}$. Ademais, será que~${f(d)\leq 2^d-1}$?

Usaremos o método probabilístico para obter cotas inferiores exponenciais para~${f(d)}$. Escolha aleatoriamente~$m$ pontos do hipercubo em~${\bbe^d}$, isto é,~${\underline{x}_1,\ldots, \underline{x}_m \in\{0,1\}^d}$, com cada $\underline{x}_i$ sendo es\-co\-lhi\-do uniformemente de forma independente dentre os~$2^d$ possíveis. Afirmamos que a probabilidade de~${\sphericalangle\underline{x}_A\underline{x}_B\underline{x}_C = \pi/2}$ é~${(3/4)^d}$. Isto segue do seguinte lema.

\begin{lema}\label{lema:uniaointersecao}
Sejam~$A,B,C\subset [d]$ e~${\underline{x}_A\underline{x}_B\underline{x}_C\in\{0,1\}^d}$ os respectivos vetores característicos. Temos que~${\sphericalangle\underline{x}_A\underline{x}_B\underline{x}_C = \pi/2}$ se e somente se~${(A\cap C)\subset B\subset (A\cup C)}$.
\end{lema}
\begin{proof}
Exercício \ref{exercicios:26-04}.4.
\end{proof}

Observe que, dada qualquer tripla formada pelos pontos escolhidos, o ângulo que ela determina é menor ou igual a~${\pi/2}$ (pois escolhemos pontos do hipercubo). Seja $X$ o número de triplas~${(i,j,k)}$ tal que~${\sphericalangle\underline{x}_A\underline{x}_B\underline{x}_C = \pi/2}$. Desta forma, podemos observar que~${\bbe(X)=m(m-1)(m-2)(3/4)^d}$. Se~${\bbe(X)<1}$, então existe um experimento tal que todos os ângulos são menores que~${\pi/2}$, de onde concluímos que, neste caso,~${f(d)\geq m}$. Pondo~${m<(1,1)^d}$, temos que~${\bbe(X)<1}$. Portanto, provamos que~${f(d)\geq(1,1)^d}$.

É possível melhorar o resultado anterior através do \emph{Método da Alteração}. Escolha~${m}$ de modo que~${(2m)_3(3/4)^d<m}$. Assim, temos que~${m=\lfloor(2/\sqrt3)^d/(2\sqrt2)\rfloor}=(1,15\ldots)^d/(2\sqrt2)$. Ge\-ra\-mos~${\underline{x}_1,\ldots, \underline{x}_{2m}}$ como antes. Como~${\bbe(X)=(2m)_3(3/4)^d}<m$, existe uma configuração com~${2m}$ pontos tal que~${X<m}$. Então, existe uma configuração~${\calp}$ com mais que~${2m-m=m}$ pontos tal que todos os ângulos são menores que~${\pi/2}$. Portanto, obtemos o seguinte resultado.

\begin{teorema}[Erd\H{o}s--Füredi\cite{ErFu83}]
$$f(d)>\frac{1}{2\sqrt2}\left(\frac{2}{\sqrt3}\right)^d.$$
\end{teorema}


\subsection{Problemas e exercícios}\label{exercicios:26-04}
Todos estão convidados a trabalhar nos seguintes e\-xer\-cí\-cios. 

\begin{enumerate}
\item[1.]Prove que $f(3)=5$.
\item[2.]É fácil ver que $f(d)\geq d+1$. Prove a seguinte cota: $f(d)\geq 2d-1$.
\item[3.]Prove que $f'(d)\leq 2^d$. Observe que isto é o mesmo que provar~${\alpha_d(2^d+1)>\pi/2}$.
\item[4.]Prove o Lema \ref{lema:uniaointersecao}.
\item[5.]Prove que, para todo $\varepsilon>0$, existe $\delta>0$ tal que existem pelo menos~${(1+\delta)^d}$ pontos em~$\bbe^d$ que determinam apenas ângulos agudos menores que~${\pi/3+\varepsilon}$.
\end{enumerate}


\newpage
\section{Funções geradoras e lançamento de moedas}\footnotetext[1]{Os resultados desta seção foram apresentados pelos alunos Eric Ossami Endo e Renato dos Santos Nunes.}\footnotetext[2]{O conteúdo desta seção foi baseado em \cite{GrKnPa94}.}
\label{sec:03-05-2010}
\begin{center}
03/05/2010
\end{center}

\section*{Funções geradoras}

\begin{definicao}
Dado um polinômio $f(z)$, denotamos por $[z^n]f(z)$ o coeficiente de $z^n$ em $f(z)$.
\end{definicao}

\begin{definicao}
Seja $\langle g_n\rangle_{n\in\bbn}$ uma sequência em $\bbc$. Dizemos que $G(z)$ é \emph{função geradora} de~${\langle g_n \rangle}$ se~${[z^n]G(z) = g_n}$. Isto é,~${G(z)=\sum_{n=0}^{\infty}g_nz^n}$.
\end{definicao}

Considere as funções geradoras~${F(z)}$ e~${G(z)}$ para as sequências~${\langle f_n \rangle_{n\in\bbn}}$ e~${\langle g_n \rangle_{n\in\bbn}}$, res\-pec\-ti\-va\-men\-te. Temos que~${\alpha F(z) + \beta G(z) = \alpha\sum_{n=0}^{\infty}f_nz^n + \beta\sum_{n=0}^{\infty}g_nz^n} = \sum_{n=0}^{\infty}(\alpha f_n + \beta g_n)z^n$. Portanto,~${\alpha F(z) + \beta G(z)}$ é a função geradora da sequência~${\langle\alpha f_n +\beta g_n\rangle_{n\in\bbn}}$.

De agora em diante, $F(z)$ e $G(z)$ sempre representarão funções geradoras de sequências~${\langle f_n \rangle}_{n\in\bbn}$ e~${\langle g_n \rangle}_{n\in\bbn}$, respectivamente. A derivada de~${G(z)}$ com relação a~$z$ é dada por
$$G'(z)=\displaystyle\sum_{n=0}^\infty (n+1)g_{n+1}z^n.$$
Desta forma, temos
$$zG'(z)=\displaystyle\sum_{n=1}^\infty ng_{n}z^n.$$

Multiplicando $F(z)$ e $G(z)$, obtemos
$$F(z)G(z) = \displaystyle\sum_{n=0}^{\infty}\left(\displaystyle\sum_{k=0}^{n}f_k g_{n-k}\right)z^n.$$

\begin{definicao}
Dada uma variável aleatória $X$ que assume valores inteiros não negativos, dizemos que~$G_X(z)$ é a \emph{função geradora de probabilidade} de~$X$ se $G_X(z) = \sum_{k=0}^{\infty}\Pr(X=k)z^k$.
\end{definicao}
\subsubsection*{Observação} Temos que $G_X(1)=1$.

Funções geradoras de probabilidade tornam simples os cálculos de valor esperado e variância. Considere uma variável aleatória $X$ que assume valores inteiros não negativos. Para o cálculo do valor esperado, temos
\begin{equation}\label{media_X}
\begin{aligned}
\bbe(X)&=\sum_{k=0}^{\infty}k\Pr(X=k)\\
&=\sum_{k=0}^{\infty}k\Pr(X=k)z^{k-1}\left.\right|_{z=1}\\
&=G'_X(1).
\end{aligned}
\end{equation}
Para o cálculo da variância, sabemos que $\var(X)=\bbe(X^2)-\bbe(X)^2$. Mas observe que
$$
\begin{aligned}
\bbe(X^2)&=\sum_{k=0}^{\infty}k^2\Pr(X=k)\\
&=\sum_{k=0}^{\infty}\left.\left(k(k-1)z^{k-2} + kz^{k-1}\right)\right|_{z=1}\Pr(X=k)\\
&=G''_X(1) + G'_X(1).
\end{aligned}
$$
Assim, temos que
\begin{equation}\label{var_X}
\var(X)=G''_X(1) + G'_X(1) - G'_X(1)^2.
\end{equation}

Considere agora que as variáveis aleatórias $X$ e $Y$ sejam independentes. Desta forma,
$$
\begin{aligned}
G_{X+Y}(z)&=\sum_{n=0}^{\infty}\Pr(X+Y=n)z^n\\
&=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\Pr(X=k\text{ e }Y=n-k)z^n\\
&=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\Pr(X=k)\Pr(Y=n-k)z^n\\
&=G_X(z)G_Y(z).
\end{aligned}
$$

Observe que $\bbe(X+Y)=(G_X(z)G_Y(z))'\left.\right|_{z=1}=G'_X(1)G_Y(1) + G_X(1)G'_Y(1)$. Mas sabemos que~${G_X(1)=G_Y(1)=1}$, portanto,~${\bbe(X+Y)=\bbe(X) + \bbe(Y)}$. Calculemos agora a variância de~${X+Y}$. Para isto, precisamos calcular~${G''_{X+Y}(1)}$ e~${G'_{X+Y}(1)}$.
$$
G'_{X+Y}(1)=G'_{X}(1)G_{Y}(1) + G_{X}(1)G'_{Y}(1) = G'_{X}(1) + G'_Y(1).
$$
Ademais,
$$
\begin{aligned}
G''_{X+Y}(1)&=G''_{X}(1)G_{Y}(1) + 2G'_{X}(1)G'_{Y}(1) + G_{X}(1)G''_{Y}(1)\\
&=G''_{X}(1) + 2G'_{X}(1)G'_{Y}(1) + G''_{Y}(1).
\end{aligned}
$$
Assim, como~${\var(X+Y)=G''_{X+Y}(1) + G'_{X+Y}(1) - G'_{X+Y}(1)^2}$, temos que
$$
\begin{aligned}
\var(X+Y) &= (G''_X(1) + G'_X(1) - G'_X(1)^2) + (G''_Y(1) + G'_Y(1) - G'_Y(1)^2)\\
&= \var(X) + \var(Y).
\end{aligned}
$$

\section*{Lançando moedas}

Consideremos agora o lançamento de uma moeda onde a probabilidade de dar cara é $p$ e a probabilidade de dar coroa é $q=1-p$; Se $X$ é a variável aleatória representando a quantidade de caras após um lançamento, temos que a função de probabilidade de $X$ é dada por~${H_X(z)=q+pz}$. Se $Y$ representa a quantidade de caras em $n$ lançamentos independentes, $Y$ é gerada por~$${H_Y(z)=H_X(z)^n = \sum_{k=0}^{n}{n\choose k}p^kq^{n-k}z^k}.$$ A sequência de probabilidades $\langle{n\choose k}p^kq^{n-k}\rangle_{k=1}^{n}$ é chamada de \emph{distribuição binomial}. Observe que, por~(\ref{media_X}), temos~${\bbe(Y)=(H'_Y(1))=(H_X(z)^n)'\left.\right|_{z=1}=(nH_X(z)^{n-1}H'_X(z))}\left.\right|_{z=1} = nH'_X(1) = np$, como era esperado. Por~(\ref{var_X}), temos que
$$
\begin{aligned}
\var(Y)&=(H_X(z)^n)''\left.\right|_{z=1} + (H_X(z)^n)'\left.\right|_{z=1} = \bbe(Y)^2\\
&=(n(n-1)p^2) + (np) - n^2p^2\\
&=np(1-p).
\end{aligned}
$$

Vamos agora considerar o processo de lançar moedas independentemente até que apareça a primeira cara. Seja $X$ a variável aleatória representando a quantidade de lançamentos realizados até o aparecimento da primeira cara. Claramente, $X$ é gerada por $${G_X(z)=\sum_{k=0}^{\infty}q^kpz^{k+1}} = \frac{pz}{1-qz}.$$
Repetindo esse processo até o aparecimento de $n$ caras, temos~
\begin{equation}\label{eq:binomiotorto}
G_X(z)^n= \frac{p^nz^n}{(1-qz)^n} = p^nz^n(1-qz)^{-n}.
\end{equation}
Seja $(n)_k=n(n-1)\ldots(n-k+1)$. Assim, se $n$ é um inteiro positivo, temos que
$$
\begin{aligned}
{-n\choose k}&=\frac{(-n)_k}{k!}\\
&=\frac{(-1)^k(n+k-1)_k}{k!}\\
&=(-1)^k{n+k-1\choose k}.
\end{aligned}
$$
Desta forma, por (\ref{eq:binomiotorto}), temos
$$
\begin{aligned}
G_X(z)^n &=  p^nz^n\displaystyle\sum_{k=0}^{n}{-n\choose k}(-1)^kq^kz^k\\
&=p^nz^n\displaystyle\sum_{k=0}^{n}{n+k-1\choose k}q^kz^k.
\end{aligned}
$$
Dividindo por $z^n$ dos dois lados, obtemos
$$\frac{p^n}{(1-qz)^n} = \displaystyle\sum_{k=0}^{n}{n+k-1\choose k}p^nq^kz^k,$$
que é a função geradora para a chamada \emph{distribuição binomial negativa}.

Seja $Y$ uma variável aleatória com distribuição binomial negativa como acima. Uma maneira fácil de calcular o valor esperado e a variância de $Y$ é através da chamada \emph{função geradora recí\-proca}~${I(z)=(1-qz)/p=1/p - (q/p)z}$. Observe que, apesar de $I(z)$ não ser uma função geradora de probabilidade,~${I(1)=1}$ (podemos ver~${I(z)^{-n}}$ gerando uma distribuição binomial com parâme\-tros~${-n}$ e $-q/p$). Assim,~${\bbe(Y)=(-n)(-q/p)=nq/p}$ e~${\var(Y)=(-n)(-q/p)(1/p)=nq/p^2}$.

Vamos considerar agora o experimento de lançar moedas independentemente até que duas caras apareçam seguidamente. Veja que o espaço de probabilidades deste experimento é dado por~${\Omega=\{HH,THH,TTHH,HTHH,\ldots\}}$, onde $H$ representa que o resultado do lançamento foi cara e $T$ que o resultado do lançamento foi coroa. Trocando $H$ por $p$ e $T$ por $q$, obtemos a probabilidade de uma dada sequência ser obtida. Se $X$ é a variável aleatória representando a quantidade de lançamentos até a ocorrência de duas caras seguidas, então $X$ é gerada pela seguinte função geradora de probabilidade.
$$
G_X(z) = p^2z^2 + qp^2z^3 + +q^2p^2z^4 + qp^3z^4 + \ldots
$$
A soma acima é obtida trocando $H$ por $pz$ e $T$ por $qz$ para todo elemento de $\Omega$ e somando-os.

Podemos dividir os elementos de $\Omega$ pela quantidade de $T's$ que possuem. Vamos ver com qual valor, os elementos de $\Omega$ que possuem $n$ termos $T$, contribuem com a soma $G_X(z)$. Como não pode haver duas caras seguidas (a menos das últimas), existem $(n)_k/k!$ elementos com $k+2$ caras e $n$ coroas. Cada um desses elementos contribui com $p^{k+2}q^{n}z^{n+k+2}$. Assim, 
$$
\begin{aligned}
G_X(z) &= \displaystyle\sum_{n=0}^{\infty}\left(\displaystyle\sum_{k=0}^{n}{n\choose k}p^{k+2}q^{n}z^{n+k+2}\right)\\
&= p^2z^2\displaystyle\sum_{n=0}^{\infty}\left(\displaystyle\sum_{k=0}^{n}{n\choose k}(pqz^2)^{k}(qz)^{n-k}\right)\\
&= p^2z^2\displaystyle\sum_{n=0}^{\infty}(pqz^2 + qz)^n\\
&= \frac{p^2z^2}{1 - pqz^2 - qz}
\end{aligned}
$$
Desta forma, utilizaremos a função $F(z)=z^2/G_X(z) =(1-pqz^2-qz)/p^2$ para calcular o valor esperado e a variância de $X$. Simples cálculos são suficientes para mostrar que $F'(1)=-p^{-2} - p^{-1} + 2$ e $F''(1)=-p^{-4}-2p^{-3}+2p^{-2}+p^{-1}$. Mas, como $G_X(z)F(z)=z^2$, temos que
$$
\begin{aligned}
\bbe(X)&=2 - (-p^{-2} - p^{-1} + 2)\\
&= p^{-1} + p^{-2}.
\end{aligned}
$$
Ademais,
$$
\begin{aligned}
\var(X)&=0 - (-p^{-4}-2p^{-3}+2p^{-2}+p^{-1})\\
&= p^{-4}+2p^{-3}-2p^{-2}-p^{-1}.
\end{aligned}
$$


\newpage
\section{Lançamento de moedas}\footnotetext[1]{Os resultados desta seção foram apresentados pelos alunos Eric Ossami Endo e Renato dos Santos Nunes.}\footnotetext[2]{O conteúdo desta seção foi baseado em \cite{GrKnPa94}.}
\label{sec:10-05-2010}
\begin{center}
10/05/2010
\end{center}

Vamos considerar o experimento onde realizamos lançamentos independentes de uma moeda, parando quando uma determinada sequência de caras e coroas apareça pela primeira vez. Seja $p$ a probabilidade de dar cara e $q=1-p$ a probabilidade de dar coroa em qualquer dos lançamentos. Por exemplo, se considerarmos a sequência $THTTH$, o espaço de probabilidades desse evento é dado por $\Omega = \{THTTH, HTHTTH, TTHTTH, HHTHTTH, HTTHTTH,\ldots\}$. Se $X$ é a variável aleatória representando a quantidade de lançamentos até a ocorrência da sequência em questão, então $X$ é gerada pela seguinte função geradora de probabilidade.
$$
G_X(z) = p^2q^3z^5 + qp^3q^3z^6 + p^2q^4z^6 + p^4q^3z^7 + \ldots
$$
Trocando $pz$ por $H$ e $qz$ por $T$, podemos, para clarear as idéias, representar a expressão acima como a soma~${S = THTTH + HTHTTH + TTHTTH + HHTHTTH + \ldots}$. Dizemos que $S$ é a soma das sequências vencedoras para $THTTH$. Da mesma maneira, considere $N$ como a soma das sequências em que $THTTH$ não ocorre, onde $1$ representa a sequência vazia. Assim, temos que
\begin{equation}\label{eq:somas1}
1+N(H+T) = N+S.
\end{equation}
\begin{equation}\label{eq:somas2}
NTHTTH = S + STTH.
\end{equation}
Por (\ref{eq:somas1}), temos que $(1-S)(1-(H+T))^{-1}=N$. Assim, por (\ref{eq:somas2}), temos $$(1-S)(1-(H+T))^{-1}THTTH = S(1+TTH).$$Portanto,
$$
(1-G_X(z))(1-z)^{-1}p^2q^3z^5 = G_X(z)(1+pq^2z^3).
$$
Logo,
$$
G_X(z)=\frac{p^2q^3z^5}{p^2q^3z^5 + (1+pq^2z^3)(1-z)}.
$$
Faça $G_X(z)=z^5/F_X(z)$. Assim, com alguns cálculos, obtemos $F'_X(1)=5-(1+pq^2)/(p^2q^3)$ e~${F''_X(1)=20-(6pq^2)/(p^2q^3)}$. Com isso, podemos calcular o valor esperado e a variância de $X$.

\noindent Valor esperado:
$$
\begin{aligned}
\bbe(X) &= G'_X(1)\\
&= 5 - F'_X(1)\\
&= p^{-2}q^{-3} + p^{-1}q^{-1}.
\end{aligned}
$$
Variância:
$$
\begin{aligned}
\var(X) &= G''_X(1) + G'_X(1) - G'_X(1)^2\\
&= -(F''_X(1) + F'_X(1) - F'_X(1)^2)\\
&= \bbe(X)^2 - 9p^{-2}q^{-3} - 3p^{-1}q^{-1}.
\end{aligned}
$$

Pensaremos agora sobre o que ocorre no caso de considerarmos uma sequência qualquer. Seja~$A$ tal sequência de caras e coroas de tamanho $m$. Seja $S$ a sequência das sequências vencedoras para~$A$, e $N$ a soma das sequências onde $A$ não aparece. Note que a igualdade (\ref{eq:somas1}) continua válida. Defina~$A^{(k)}$ e~$A_{(k)}$, respectivamente, como os $k$ últimos caracteres e os  $k$ primeiros caracteres de $A$. Assim, temos que
\begin{equation}\label{eq:somas3}
NA=S\left(1+\displaystyle\sum_{k=1}^{m-1}A^{(k)}\left[A_{(m-k)}=A^{(m-k)}\right]\right),
\end{equation}
lembrando que $[p]=1$ se $p$ é válido e $[p]=0$ se $p$ é falso.

Vamos calcular o valor esperado e a variância de $X$, onde $X$ representa a quantidade de lançamentos da moeda até que a sequência $A$ ocorra pela primeira vez. Substituindo (\ref{eq:somas1}) em (\ref{eq:somas3}), obtemos
$$
S=\frac{A}{A + \left(1+\displaystyle\sum_{k=1}^{m-1}A^{(k)}\left[A_{(m-k)}=A^{(m-k)}\right]\right)(1-H-T)}.
$$
Fazendo~${\tilde A_{(k)}}$ o valor resultante da substituição de $H$ por $p^{-1}$ e $T$ por $q^{-1}$ em $A_{(k)}$. Considere também $\hat A_{(k)} = {\tilde A_{(k)}}^{-1}$. Assim, 
$$
G_X(z)=\frac{\hat A_{(m)}z^m}{\hat A_{(m)}z^m + \left(1+\displaystyle\sum_{k=1}^{m-1}\hat A^{(k)}\left[A_{(m-k)}=A^{(m-k)}\right]\right)(1-z)}.
$$
Portanto, fazendo $F_X(z)=z^m/G_X(z)$ e observando que $\hat A^{(k)}/{\hat A^{(m)}} = \tilde A_{(m-k)}$, temos que
$$
F_X(z) = z^m + \left(\displaystyle\sum_{k=1}^{m}\tilde A_{(k)}z^{(m-k)}\left[A_{(k)}=A^{(k)}\right]\right)(1-z).
$$
Assim,
$$
F'_X(1) = m - \displaystyle\sum_{k=1}^{m}\tilde A_{(k)}\left[A_{(k)}=A^{(k)}\right].
$$
Ademais,
$$
F''_X(1) = (m-1)m - 2\displaystyle\sum_{k=1}^{m}(m-k)\tilde A_{(k)}\left[A_{(k)}=A^{(k)}\right].
$$
Desta forma, podemos facilmente calcular o valor esperado e a variância de $X$.

\noindent Valor esperado:
$$
\bbe(X) = G'_X(1) = m-F'(1) = \displaystyle\sum_{k=1}^{m}\tilde A_{(k)}\left[A_{(k)}=A^{(k)}\right].
$$
Variância:
$$
\begin{aligned}
\var(X) &= G''_X(1) + G'_X(1) - G'_X(1)^2\\
&= -(F''_X(1) + F'_X(1) - F'_X(1)^2)\\
&= \bbe(X)^2 - \displaystyle\sum_{k=1}^{m}(2k-1)\tilde A_{(k)}\left[A_{(k)}=A^{(k)}\right].
\end{aligned}
$$

Vamos considerar agora o jogo conhecido por ``Penney ante''. Neste jogo existem os jogadores $1$ e $2$ e cada um deles escolhe uma configuração de caras e coroas, respectivamente, $A$ e $B$, da maneira que quiserem. Uma moeda honesta é lançada repetidas vezes até que $A$ apareça ou $B$ apareça. A configuração que aparecer primeiro dá a vitória ao jogador correspondente. Considere $S_A$ e $S_B$ como sendo as somas das sequências vencedoras para $A$ e $B$, respectivamente, onde $|A|=l$ e $|B|=m$, e seja $N$ a soma das sequências que não são vencedoras nem para $A$ nem para $B$.

Observe que temos
\begin{equation}\label{eq:somasCompletas1}
1+N(H+T) = N+S_A + S_B.
\end{equation}
\begin{equation}\label{eq:somasCompletas2}
\begin{aligned}
NA &= S_A\displaystyle\sum_{k=1}^{l}A^{(l-k)}\left[A^{(k)}=A_{(k)}\right] + S_B\displaystyle\sum_{k=1}^{\min\{l,m\}}A^{(l-k)}\left[B^{(k)}=A_{(k)}\right].\\
NB &= S_B\displaystyle\sum_{k=1}^{m}B^{(m-k)}\left[B^{(k)}=B_{(k)}\right] + S_A\displaystyle\sum_{k=1}^{\min\{l,m\}}B^{(m-k)}\left[A^{(k)}=B_{(k)}\right].
\end{aligned}
\end{equation}
Como a moeda que estamos considerando no jogo é honesta, (\ref{eq:somasCompletas2}) nos diz que
\begin{equation}\label{eq:penneyEquations}
\begin{aligned}
N &= S_A\displaystyle\sum_{k=1}^{l}2^{k}\left[A^{(k)}=A_{(k)}\right] + S_B\displaystyle\sum_{k=1}^{\min\{l,m\}}2^k\left[B^{(k)}=A_{(k)}\right].\\
N &= S_B\displaystyle\sum_{k=1}^{m}2^k\left[B^{(k)}=B_{(k)}\right] + S_A\displaystyle\sum_{k=1}^{\min\{l,m\}}2^k\left[A^{(k)}=B_{(k)}\right].
\end{aligned}
\end{equation}

Defina agora a operação $A:B$ como segue, onde $A$ pode ser igual a $B$.
$$
A:B = \displaystyle\sum_{k=1}^{\min\{l,m\}}2^{k-1}\left[A^{(k)}=B_{(k)}\right].
$$
Assim, igualando as expressões em (\ref{eq:penneyEquations}), obtemos uma igualdade bem simples.
$$
\frac{S_A}{S_B} = \frac{B:B - B:A}{A:A - A:B}.
$$

Vale ressaltar que a relação de vitória entre os padrões escolhidos neste jogo não são transitivas. Por exemplo, suponha que jogadores $1$, $2$ e $3$ escolheram as sequências~$HHTH$, $HTHH$ e $THHH$, respectivamente. Temos que o jogador~1 vence o jogador~2 com probabilidade $3/2$ e o jogador~2 vence o jogador~3 com probabilidade $7/5$, porém, o jogador 3 vence o jogador 1 com probabilidade~$7/5$. De fato, se o jogador 1 escolheu a sequência $\tau_1,\ldots,\tau_l$, o jogador 2 sempre ganhará se escolher a sequência~${\bar\tau_2\tau_1,\tau_2,\ldots,\tau_{l-1}}$ (veja o exercício \ref{exercicios:10-05}.1).


\subsection{Problemas e exercícios}\label{exercicios:10-05}
Todos estão convidados a trabalhar nos seguintes e\-xer\-cí\-cios. 

\begin{enumerate}
\item[1.]Seja  $\tau_1,\ldots,\tau_l$ a sequência escolhida pelo jogador 1 no jogo ``Penney ante''.
\item[(\textit{i})]Mostre que o jogador 2 sempre vencerá caso escolha a sequência $\bar\tau_2\tau_1,\tau_2,\ldots,\tau_{l-1}$.
\item[(\textit{i})]A sequência $\bar\tau_2\tau_1,\tau_2,\ldots,\tau_{l-1}$ é a melhor escolha para o jogador 2 (isto é, a que lhe dá a maior probabilidade de vitória)?
\end{enumerate}



\newpage
\section{Teoria probabilística dos números}\footnotetext[1]{Os resultados desta seção foram apresentados pelo aluno Thiago da Silva Pinheiro.}
\label{sec:17-05-2010}
\begin{center}
17/05/2010
\end{center}

Nesta seção utilizaremos a seguinte forma da desigualdade de Chebyshev.
\begin{equation}\label{eq:modifiedChebyshev}
\Pr\left(|X-\mathbb{E}(X)|\geq \omega\sqrt{\var(X)}\right)\leq\frac{1}{\omega^2},
\end{equation}
onde $\omega$ é um número positivo qualquer. O seguinte lema também será necessário.
\begin{lema}\label{lema:lemaSemProvas}
$$\displaystyle\sum_{p\leq x}\frac{1}{p} = \ln\ln x + O(1).$$
\end{lema}
\begin{proof}[Demonstração do limite inferior]
Lembre que, para qualquer $n$ inteiro, podemos escrevê-lo de maneira única na forma $n=mq^2$, onde $m$ é livre de quadrados, isto é, $m$ não é divisível por nenhum quadrado perfeito. Assim, temos que
$$
\begin{aligned}
\sum_{n\leq x}\frac{1}{n} &= \sum_{m\leq x}\left(\frac{1}{m}\sum_{q\leq\sqrt{x/m}}\frac{1}{q^2}\right)\\
&\leq2\sum_{m\leq x}\frac{1}{m}\\
&=2\prod_{p\leq x}\left(1+\frac{1}{p}\right).
\end{aligned}
$$
Mas
$$
\begin{aligned}
\sum_{n\leq x}\frac{1}{n} &\geq \sum_{n\leq x}\int_{n}^{n+1}\frac{1}{t}\,dt\\
&\geq\log x.
\end{aligned}
$$
Portanto, $\log x\leq 2\prod_{p\leq x}(1+1/p)\leq2\prod_{p\leq x}e^{1/p}=2e^{\sum_{p\leq x}1/p}$. Assim, $$\sum_{p\leq x}1/p\geq\ln\ln x + O(1)$$.
\end{proof}

\begin{definicao}
Denotamos por $v(n)$ o número de primos positivos que dividem $n$.
\end{definicao}

O seguinte teorema nos diz, de forma grosseira, que quase todo número $n$ possui uma quantidade de fatores primos muito próxima de $\ln\ln n$.

\begin{teorema}[Hardy--Ramanujan \cite{HaRa17}]
Seja $\omega$ uma função qualquer tal que $\omega=\omega(n)\to\infty$. A quantidade de elementos~${x\in[n]}$ tais que $|v(x)-\ln\ln n| > \omega\sqrt{\ln\ln n}$ é $o(n)$.
\end{teorema}
\begin{proof}[Demonstração (feita por Turán \cite{Tu34})]
Utilizaremos o método do segundo momento. Tome $x\in[n]$ escolhido aleatoriamente com distribuição uniforme. Para $p$ primo, denotamos~${X_p=1}$ se $p|x$ e~${X_p=0}$ caso contrário. Fazendo $m=n^{1/10}$, dizemos que $X=X(x)=\sum_{p\leq m}X_p$, onde este somatório é sobre todos os primos menores que $m$. Observe que $X(x)$ representa a quantidade de primos não maiores que $m$ que dividem $x$. Ademais, podemos notar que não existem mais que $10$ elementos maiores que $m$ que dividem $x$. Assim, temos que $v(x)-10\leq X(x)\leq v(x)$.

Podemos calcular o valor esperado de $X$. Temos $\bbe(X_p)=\lfloor n/p\rfloor/n = 1/p + O(1/n)$, onde a última igualdade segue do fato de $x-1\leq\lfloor x\rfloor\leq x$. Portanto, 
$$
\begin{aligned}
\bbe(X(x)) &= \sum_{p\leq m}\bbe(X_p)\\
&= \sum_{p\leq m}(1/p + O(1/n))\\
&= \left(\sum_{p\leq m}1/p\right) + O(1)\\
&= \ln\ln n + O(1),
\end{aligned}
$$
onde a última igualdade segue do Lema \ref{lema:lemaSemProvas}.

Precisamos agora calcular a variância de $X(x)$. Vimos em seções anteriores que se~${X=\sum_S{X_S}}$, então temos que~${\var(X) = \sum_{S}\var(X_S) + \sum_{(S,T),S\neq T}\cov(X_S,X_T)}$. Assim, precisamos saber os va\-lo\-res de $\var(X_p)$ e $\cov(X_p,X_q)$ para $p\neq q$.
$$
\begin{aligned}
\var(X_p) &= \bbe({X_p}^2) - \bbe(X_p)^2\\
&=\bbe(X_p)-\bbe(X_p)^2\\
&=\bbe(X_p)(1-\bbe(X_p))\\
&=\left(\frac{1}{p}+O\left(\frac{1}{n}\right)\right)\left(1-\frac{1}{p}+O\left(\frac{1}{n}\right)\right)\\
&=\frac{1}{p}\left(1-\frac{1}{p}\right) + O\left(\frac{1}{n}\right).
\end{aligned}
$$
Portanto,
$$
\begin{aligned}
\displaystyle\sum_{p\leq m}\var(X_p)&=\displaystyle\sum_{p\leq m}\left(\frac{1}{p}\left(1-\frac{1}{p}\right) + O\left(\frac{1}{n}\right)\right)\\
&=\left(\displaystyle\sum_{p\leq m}\frac{1}{p}\right) + O(1)\\
&=\ln\ln n + O(1),
\end{aligned}
$$
onde a última igualdade segue do Lema \ref{lema:lemaSemProvas}. Para a covariância, temos
$$
\begin{aligned}
\cov(X_p,X_q) &= \bbe(X_pX_q) - \bbe(X_p)\bbe(X_q)\\
&=\frac{\lfloor n/pq\rfloor}{n} - \frac{\lfloor n/p\rfloor}{n}\frac{\lfloor n/q\rfloor}{n}\\
&\leq\frac{1}{pq} - \left(\frac{1}{p} - \frac{1}{n}\right)\left(\frac{1}{q} - \frac{1}{n}\right)\\
&\leq\frac{1}{n}\left(\frac{1}{p}+\frac{1}{q}\right).
\end{aligned}
$$
Portanto,
$$
\begin{aligned}
\displaystyle\sum_{p\neq q}\cov(X_p X_q) &\leq \frac{1}{n}\displaystyle\sum_{p\neq q}\left(\frac{1}{p} + \frac{1}{q}\right)\\
&\leq\frac{2m}{n}\displaystyle\sum_{p\leq m}\frac{1}{p}\\
&=2n^{-9/10}(\ln\ln n + O(1))\\
&=o(1).
\end{aligned}
$$

Com isso, vemos que a covariância não tem nenhum efeito sobre a variância de $X(x)$. Logo, 
$$
\begin{aligned}
\var(X(x)) &= \displaystyle\sum_{p\leq m}\var(X_p) + \displaystyle\sum_{p\neq q}\cov(X_p X_q)\\
&= \ln\ln n + O(1).
\end{aligned}
$$

Utilizando a desigualdade (\ref{eq:modifiedChebyshev}) e lembrando que $v(x)-10\leq X\leq v(x)$, temos que
$$
\Pr\left(|v(x) - \ln\ln n|>\omega\sqrt{\ln\ln n}\right)<\omega^{-2},
$$
onde $\omega=\omega(n)$ tende a infinito quando $n$ tende a infinito. Isto completa a prova.
\end{proof}

O seguinte teorema mostra um importante resultado, obtido por Erd\H{o}s e Kac em 1940, que relaciona a quantidade de fatores primos de um número $n$ com a distribuição normal.
\begin{teorema}[Erd\H{o}s--Kac \cite{ErKa40}]
Para todo $t\in\bbr$, se $x\in[n]$ é escolhido aleatoriamente com distribuição uniforme, então
$$
\lim_{n\to\infty}\Pr\left(\frac{v(x) - \ln\ln n}{\sqrt{\ln\ln n}} \geq t\right) = \frac{1}{\sqrt{2\pi}}\int_t^\infty e^{-s^2/2}\,ds.
$$
\end{teorema}


\newpage
\section{Teoria probabilística dos números - Continuação}\footnotetext[1]{Os resultados desta seção foram apresentados pelo aluno Thiago da Silva Pinheiro.}
\label{sec:24-05-2010}
\begin{center}
24/05/2010
\end{center}

Provaremos agora o Lema \ref{lema:lemaSemProvas}, isto é, mostraremos que $\sum_{p\leq x}1/p = \ln\ln x + O(1)$. Para isto, precisaremos utilizar alguns resultados.

\begin{lema}[Soma de Abel]\label{lema:somaAbel}
É verdade que
$$
\sum_{s<r\leq t}a(r)f(r) = A(t)f(t) - A(s)f(s) - \int_s^t A(\theta)f'(\theta)\,d\theta,
$$
onde $A(\theta) = \sum_{s<r\leq \theta}a(r)$.
\end{lema}

\begin{proof}
Consideramos, nesta prova, $s$ e $t$ inteiros, porém, o mesmo resultado é válido sem esta restrição (veja o exercício \ref{exercicios:24-05}.1). Sabemos que 
$$
\begin{aligned}
\int_k^{k+1}A(\theta)f'(\theta)\,d\theta &= \int_k^{k+1}A(k)f'(\theta)\,d\theta\\
&=A(k)\int_k^{k+1}\!f'(\theta)\,d\theta\\
&=A(k)\left(f(k+1)-f(k)\right). 
\end{aligned}
$$
Assim,
$$
\begin{aligned}
&\int_s^{s+1}A(\theta)f'(\theta)\,d\theta =A(s)\left(f(s+1)-f(s)\right).\\
&\int_{s+1}^{s+2}A(\theta)f'(\theta)\,d\theta =A(s+1)\left(f(s+2)-f(s+1)\right).\\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\
&\int_{t-1}^{t}A(\theta)f'(\theta)\,d\theta =A(t-1)\left(f(t)-f(t-1)\right).\\
\end{aligned}
$$
Portanto,
$$
\begin{aligned}
\int_s^{t}A(\theta)f'(\theta)\,d\theta &= -A(s)f(s)\\
&\ \ \ -f(s+1)(A(s+1)-A(s))\\
&\ \ \ -f(s+2)(A(s+2)-A(s+1))\\
&\ \ \ \ \ \ \ \ \ \ \ \ \vdots\\
&\ \ \  -f(t-1)(A(t-1)-A(t-2))\\
&\ \ \  +A(t-1)f(t) + (f(t)a(t)-f(t)a(t)).
\end{aligned}
$$
Mas, como $A(k+1) - A(k) = a(k)$, temos que
$$
\int_s^{t}A(\theta)f'(\theta)\,d\theta = -A(s)f(s) - \sum_{s< r\leq t}a(r)f(r) + A(t)f(t).
$$
Assim, o resultado segue.
\end{proof}

O seguinte lema também será necessário.

\begin{lema}\label{lema:auxSomaLog}
A igualdade $\sum_{p\leq x}(\ln p)/p = \ln x + O(1)$ é válida, onde $x\in\bbr$ e a soma é sobre os primos não maiores que $x$.
\end{lema}

\begin{proof}
Estimaremos o valor de $\ln x!$ de duas maneiras distintas. Primeiro, observe que
\begin{equation}\label{eq:somaLog}
\begin{aligned}
\ln x! &= \sum_{p\leq x}\left(\left(\left\lfloor \frac{x}{p}\right\rfloor + \left\lfloor \frac{x}{p^2}\right\rfloor +\ldots\right)\ln p\right)\\
&=\sum_{p\leq x}\left(\left\lfloor \frac{x}{p}\right\rfloor\ln p\right) + \sum_{p\leq x}\left(\left(\left\lfloor \frac{x}{p^2}\right\rfloor + \left\lfloor \frac{x}{p^3}\right\rfloor +\ldots\right)\ln p\right)\\
&<\sum_{p\leq x}\left(\left\lfloor \frac{x}{p}\right\rfloor\ln p\right) + x\sum_{p\leq x}\left(\left(\frac{1}{p^2}+\frac{1}{p^3}\ldots\right)\ln p\right)\\
&=\sum_{p\leq x}\left(\left\lfloor \frac{x}{p}\right\rfloor\ln p\right) + x\sum_{p\leq x}\frac{\ln p}{p(p-1)}\\
&=\sum_{p\leq x}\left(\left\lfloor \frac{x}{p}\right\rfloor\ln p\right) + O(x).
\end{aligned}
\end{equation}
Mas veja que $0\leq \int_{x}^{x+1}\ln t\,dt-\ln x=\int_x^{x+1}\ln(t/x) dt\leq \int_x^{x+1}(t/x - 1)\,dt = 1/2x$. Assim,
$$
\sum_{n\leq x-1}\left(\int_{n}^{n+1}\ln t\,dt - \ln n\right) = O(\ln x),
$$
de onde concluimos que
$$
\int_1^{x}\ln t\,dt - \sum_{n\leq x-1}\ln n = O(\ln x).
$$
Logo, temos que $x\ln x - x + 1 - \sum_{n\leq x-1}\ln n = O(\ln x)$. Portanto,
$$
\sum_{n\leq x}\ln n = x\ln n + O(x).
$$
Desta forma, $\ln x! = x\ln n + O(x)$. Isto, juntamente com (\ref{eq:somaLog}), nos diz que
\begin{equation}\label{eq:limiteFloor}
\sum_{p\leq x}\left(\left\lfloor \frac{x}{p}\right\rfloor\ln p\right) = x\ln x + O(x).
\end{equation}
Observando que $\sum_{p\leq x}(\lfloor x/p\rfloor\ln p) = \sum_{p\leq x}(x/p + O(1))\ln p$, obtemos
\begin{equation}\label{eq:arredFloor}
\sum_{p\leq x}\left(\left\lfloor \frac{x}{p}\right\rfloor\ln p\right) = \sum_{p\leq x}\left(\frac{x}{p} \ln p\right) + O(\pi(x)\ln x),
\end{equation}
onde $\pi(x)$ denota a quantidade de primos não maiores que $x$. Dividindo (\ref{eq:limiteFloor}) e (\ref{eq:arredFloor}) por $x$, temos
$$
\sum_{p\leq x}\left(\frac{\ln p}{p}\right) = \ln x + O(1) + O\left(\frac{\pi(x)}{x/\ln x}\right).
$$
Mas é verdade que $\pi(x)=\theta(x/\ln x)$ (Este fato será provado na próxima seção). Com isto, completamos a prova, pois
$$
\sum_{p\leq x}\left(\frac{\ln p}{p}\right) = \ln x + O(1).
$$
\end{proof}

Vamos à prova do Lema \ref{lema:lemaSemProvas}, isto é, provaremos que $\sum_{p\leq x}1/p = \ln\ln x + O(1)$.
\begin{proof}[Demonstração do Lema \ref{lema:lemaSemProvas}]
Tomando $f(r)=1/\ln r$ e fazendo $a(r) = (\ln p)/p$ se $r=p$ para $p$ primo e $a(r)=0$ caso contrário, obtemos a seguinte relação ao aplicar o Lema \ref{lema:somaAbel} (Soma de Abel).
$$
\sum_{p\leq x}\frac{1}{p} = \frac{A(x)}{\ln x} + \int_2^x \frac{A(t)}{t(\ln t)^2}\, dt.
$$
Mas como $A(x) = \sum_{p\leq x}(\ln p)/p$, obtemos, pelo Lema \ref{lema:auxSomaLog},
$$
\begin{aligned}
\sum_{p\leq x}\frac{1}{p} &=1+O(1)+\int_2^x \frac{\ln t + O(1)}{t(\ln t)^2}\, dt\\
&=1+O(1)+\int_2^x \frac{1}{t\ln t} + \int_2^x \frac{O(1)}{t(\ln t)^2}\, dt\\
&=\ln\ln x + O(1) + \int_2^x \frac{O(1)}{t(\ln t)^2}\, dt\\
&=\ln\ln x + O(1).
\end{aligned}
$$
\end{proof}



\subsection{Problemas e exercícios}\label{exercicios:24-05}
Todos estão convidados a trabalhar nos seguintes e\-xer\-cí\-cios. 

\begin{enumerate}
\item[1.]Prove o Lema \ref{lema:somaAbel} sem a suposição de que $s$ e $t$ sejam inteiros.
\end{enumerate}


\newpage
\section{Teoria aditiva dos números}
\label{sec:31-05-2010}
\begin{center}
31/05/2010
\end{center}

Em uma carta endereçada a Euler, Goldbach propôs, em 1742, a seguinte conjectura.

\begin{conjectura}[Goldbach]\label{conj:goldbach}
Para todo $n\geq 2$ par, existem primos $p$, $q$ tal que $p+q=n$.
\end{conjectura}

Computacionalmente já foi verificado que tal conjectura é válida para $n\leq4 \times10^{11}$. Os seguintes resultados dizem respeito a esta conjectura.

\begin{teorema}[Lagrange]\label{teo:lagrange}
Todo natural pode ser escrito como soma de no máximo quatro quadrados. 
\end{teorema}

\begin{teorema}[Fermat]\label{teo:fermat}
Todo primo $p\equiv 1\ (\bmod\ {4})$ pode ser escrito como soma de dois quadrados.
\end{teorema}

\begin{teorema}[Vinogradov]\label{teo:vinogradov}
Todo inteiro ímpar suficientemente grande pode ser escrito como soma de no máximo três primos.
\end{teorema}

\begin{teorema}[Shnirelman]\label{teo:shnirelman}
Existe uma constante $h$ tal que todo inteiro $n\geq 2$ pode ser escrito como soma de no máximo $h$ primos.
\end{teorema}

Provaremos o Teorema \ref{teo:shnirelman}. Para tal, considere o conjunto $A=\{0<a_1<a_2<\ldots\}\subset \bbn$ e seja~${A(x) = \max\{k\colon a_k\leq x\}}$ a quantidade de elementos de $A$ não maiores que $x$. Definimos a \emph{densidade de Shnirelman} como~${\sigma(A)=\inf_{n\geq 1}A(n)/n}$. Podemos observar os seguintes fatos sobre a densidade de Shnirelman.
\begin{itemize}
\item[(\textit{i})] Se $1\notin A$, então $\sigma(A)=0$.
\item[(\textit{ii})] Se $a_k = 1+(k-1)d$, para $k=1,2,\ldots$, então $\sigma(A)=1/d$.
\item[(\textit{iii})] Se $a_n=\lfloor(1+\alpha)^n\rfloor$, para $\alpha>0$, então $\sigma(A)=0$.
\item[(\textit{iv})] Se $a_n=n^2$, para $n\geq 1$, então $\sigma(\alpha)=0$.
\item[(\textit{v})] Se $1\in A$ mas $\sigma(A)=0$, então, para todo $\varepsilon>0$, existe $m$ arbitrariamente grande tal que~${A(m)\leq \varepsilon m}$.
\item[(\textit{vi})] $\sigma(A)=1$ se e somente se $\{1,2,\ldots\}\subset A$.
\end{itemize}

Dados $A,B\subset \bbn$, definimos $A+B=\{a+b\colon a\in A,\ b\in B\}$. Em geral, para $A_1,\ldots,A_h\subset\bbn$, temos que $A_1+\ldots+A_h=\{a_1+\ldots+a_h\colon a_i\in A_i\text{ para todo $i$}\}$. Considere também os seguintes conjuntos.
\begin{itemize}
\item[1)]$S=\{0,1,4,9,16,\ldots\}$, o conjunto de todos os quadrados perfeitos.
\item[2)]$(4\bbn + 1)=\{x\in\bbn\colon x=1\ (\bmod\ {4})\}$.
\item[3)]$\calp=\{p_1<p_2<\ldots\}$, o conjunto de todos os primos.
\item[4)]$\calp_0=\calp\cup\{0\}$.
\end{itemize}

Podemos reescrever a Conjectura de Goldbach e os teoremas enunciados anteriormente com base nesses conjuntos.\\

\noindent{\bf Conjectura \ref{conj:goldbach}} (Goldbach).
$2\calp\supset\{n>2\colon n\in\bbn\ par\}$.

\noindent{\bf Teorema \ref{teo:lagrange}} (Lagrange)
$4S\supset\bbn$.


\noindent{\bf Teorema \ref{teo:fermat}} (Fermat)
$2S\supset\calp\cap(4\bbn+1)$.


\noindent{\bf Teorema \ref{teo:vinogradov}} (Vinogradov)
Existe $n_0$ tal que $3\calp_0\supset\{n\in\bbn\colon \text{$n\geq n_0$, $n$ ímpar}\}$.


\noindent{\bf Teorema \ref{teo:shnirelman}} (Shnirelman)
Existe $h\in\bbn$ tal que $h\calp_0\supset\bbn\setminus\{1\}$.\\

A seguinte definição será importante.

\begin{definicao}
Dizemos que $A\subset\bbn$ é uma \emph{base de ordem $h$} de $\bbn$ se $hA\supset\bbn$. Ademais, se existe $h$ tal que $A$ é base de ordem $h$, então dizemos que $A$ é uma \emph{base de ordem finita}.
\end{definicao}

Os seguintes resultados compõem a prova do Teorema \ref{teo:shnirelman} (Shnirelman).

\begin{teorema}\label{teo:shnirelman2}
Se $0\in A\subset\bbn$ e $\sigma(A)>0$, então $A$ é base de ordem finita.
\end{teorema}

\begin{lema}\label{lema:paraShnirelman}
Se $A=2\calp + \{0,1\}$, então $\sigma(A)>0$.
\end{lema}

\begin{teorema}\label{teo:concluiShnirelman}
O Teorema \ref{teo:shnirelman2} e o Lema \ref{lema:paraShnirelman} implicam o Teorema \ref{teo:shnirelman}.
\end{teorema}

\begin{proof}[Demonstração do Teorema \ref{teo:concluiShnirelman}]
Seja $A$ como no Lema \ref{lema:paraShnirelman}. Pelo Teorema \ref{teo:concluiShnirelman}, $A$ é base de ordem $h$, para algum $h$. Seja $N\geq 2$. Como $A$ é base de ordem $h$, temos que~${0\leq N-2=a_1+\ldots+a_h}$, com~${a_i\in A}$ para todo~$i$. Sem perda de generalidade, temos~${N-2= k + (p_1+q_1)+\ldots + (p_l+q_l)}$, onde~${k+l\leq h}$ e~$\{p_i,q_i\}\in\calp$ para todo~$i$. Se~$k=0$, então podemos escrever~$N$ da seguinte forma:~${N=2+p_1+q_1+\ldots+p_l+q_l}$, isto é, como soma de~$2l+1\leq 2h$ primos. Suponha que temos~${0<k=2m+r}$, com~${r\in\{0,1\}}$. Se~$r=0$, então $N=2(m+1) + \sum_{i=1}^{l}(p_i+q_i)$. Assim, $N$ é soma de $m+1+2l\leq 3h$ primos. Se $r=1$, então~${N=3+2m+\sum_{i=1}^{l}(p_i+q_i)}$. Logo,~$N$ é soma de~${2m+1+2l\leq 3h}$ primos. Concluimos que $(3h)\calp_0\supset\{2,3,\ldots\}$.
\end{proof}

A fim de provar o Teorema \ref{teo:shnirelman2}, precisamos provar alguns lemas e corolários.

\begin{lema}\label{lema:paraShnirelman2}
Suponha que $0\in A\subset \bbn$ e $0\in B\subset \bbn$. Se $h\geq 0$ e $A(n)+B(n)\geq n$, então $n\in A+B$.
\end{lema}

\begin{proof}
Se $n\in A$ ou $n\in B$, então $n\in A+B$. Portanto, podemos considerar $n\notin A\cup B$. Assim,  temos~${A(n-1)+B(n-1)=A(n)+B(n)\geq n}$. Suponha~${A\cap[n-1]=\{a_1<a_2<\ldots<a_r\}}$ e~${B\cap[n-1]=\{b_1<b_2<\ldots<b_s\}}$. Considere $A$ e $n-(B\cap[n-1])=\{n-b_s<\ldots<n-b_1\}$. Como $r+s=A(n-1)+B(n-1)\geq n$, segue que existem $i,j$ tais que $a_i=n-b_j$. Portanto, temos~${n=a_i+b_j}$.
\end{proof}

\begin{corolario}
Seja $0\in A\subset \bbn$ e $0\in B\subset \bbn$. Se $\sigma(A)+\sigma(B)\geq 1$, então $n\in A+B$ para todo~${n\geq 0}$.
\end{corolario}

\begin{proof}
Fixado $n$, temos que $A(n)+B(n)\geq n\sigma(A) + n\sigma(B)\geq n$. Pelo Lema \ref{lema:paraShnirelman2}, temos que~$n\in A+B$.
\end{proof}

\begin{corolario}\label{cor:corolario6}
Se $0\in A$ e $\sigma(A)\geq 1/2$, então $A$ é uma base de ordem $2$, isto é, $2A\supset\bbn$.
\end{corolario}

\begin{lema}
Se $0\in A\subset \bbn$ e $0\in B\subset \bbn$, então $\sigma(A+B)\geq\sigma(A)+\sigma(B)-\sigma(A)\sigma(B)$, isto é,~${1-\sigma(A+B)\leq (1-\sigma(A))(1-\sigma(B))}$.
\end{lema}

\subsubsection*{Observação} Mann provou um resultado melhor que o apresentado no lema acima, onde concluiu que $\sigma(A+B)\geq\sigma(A)+\sigma(B)$.

Por indução em $h$, podemos provar o seguinte resultado.

\begin{corolario}\label{cor:corolario8}
Se $0\in A_i\subset\bbn$ para $i=1,\ldots,h$, então $1-\sigma(A_1+\ldots+A_h)\leq\prod_{i=1}^{n}(1-\sigma(A_i))$.
\end{corolario}

Finalmente estamos aptos a provar o Teorema \ref{teo:shnirelman2}.

\begin{proof}[Demonstração do Teorema \ref{teo:shnirelman2}]
Seja $A\subset N$ com $0\in A$ e $\sigma(A)>0$. Então $1-\sigma(A)<1$ e portanto existe $k$ tal que $(1-\sigma(A))^k<1/2$. Assim, pelo Corolário \ref{cor:corolario8}, temos que~${1-\sigma(kA)\leq (1-\sigma)^k)\leq 1/2}$. Assim, $kA$ é tal que $\sigma(kA)\geq 1/2$. Pelo Corolário \ref{cor:corolario6}, temos que~$kA$ é base de ordem $2$. Segue que~$A$ é base de ordem $h=2k$.
\end{proof}

Nos resta mostrar a validade do Lema \ref{lema:paraShnirelman}. Seja $r(N)$ a quantidade de maneiras de escrever $N$ como soma de dois primos (por exemplo, $r(5)=2$). Os seguintes dois lemas, quando combinados, implicam o Lema \ref{lema:paraShnirelman}.

\begin{lema}
Existem $x_0$ e $c>0$ tais que $\sum_{N=1}^{x}r(N)\geq cx^2/(\log x)^2$ para todo $x\geq x_0$.
\end{lema}

O lema acima segue do fato de $\pi(x)\geq c''x/\log x$ para uma certa constante positiva $c''$.

\begin{lema}
Existem $x_0'$ e $c'>0$ tais que $\sum_{N=1}^{x}r(N)^2\leq c'x^3/(\log x)^4$ para todo $x\geq x_0'$.
\end{lema}

\begin{proof}[Demonstração do Lema \ref{lema:paraShnirelman}]
Por Cauchy-Schwarz, $(\sum_{N=1}^x r(N))^2\leq(\sum_{N=1}^x 1)(\sum_{n\leq x} r(N)^2)$. Assim,
$$
\begin{aligned}
\left(\sum_{N=1}^x r(N)\right)^2&\leq (2\calp)(x)\sum_{N=1}^x r(N)^2\\
&\leq A(x)\sum_{N\leq x} r(N)^2.
\end{aligned}
$$
Portanto,
$$
\begin{aligned}
A(x)&\geq\frac{\left(\sum_{N=1}^x r(N)\right)^2}{\sum_{N=1}^x r(N)^2}\\
&\geq \left(\frac{c}{c'}\right)x,
\end{aligned}
$$
onde a última desigualdade é válida quando $x>\max\{x_0,x_0'\}$. Desta forma, como $1\in A$, segue que~${\sigma(A)\geq\min\{1/\max\{x_0,x_0'\},c/c'\}>0}$. Portanto, estamos feitos.
\end{proof}

Para maiores detalhes sobre o assunto, veja o livro de Khinchin \cite{Kh52}.


\newpage
\section{Um problema geométrico de Erd\H{o}s e Füredi - Continuação}
\label{sec:7-6-2010}
\begin{center}
7/6/2010
\end{center}

Na seção \ref{sec:26-04-2010} vimos um problema geométrico abordado por Erd\H{o}s e Füredi em 1983 \cite{ErFu83}.
Dizemos que $\calp$ determina $\sphericalangle abc = \alpha$ se $a,b,c\in \calp$. Lembre que~${\alpha_n(\calp) =
\max\{0\leq\alpha\leq\pi\:\calp\text{ determina }\alpha\}}$, onde $\calp\subset\bbr^n$ com $\calp$ finito. Erd\H{o}s e
Füredi mostraram que existe $c>1$ tal que existe $\calp\subset \bbr^n$ onde~${|\calp|\geq c^n}$ e
$\alpha_n(\calp)<\pi/2$ (Observe que não podemos ter limite $\pi/3$, pois quaisquer três pontos determinam um ângulo
não menor que $\pi/3$).

Tome $f_\alpha^{\leq}(n) = \max\{|\calp|\colon \calp\subset\bbr^n,\ \alpha_n(\calp)\leq\alpha\}$. Considerando o
simplexo regular de dimensão~$n$, observamos que $f_{\pi/3}^{\leq}(n)\geq n+1$. Mas é verdade que
$f_{\pi/3}^{\leq}(n)\leq n+1$?

Um bom exercício é pensar no seguinte problema.
\begin{problema}
Fixe $\varepsilon>0$. Prove que $f_{{\pi/3}+\varepsilon}^{\leq}(n)\geq e^{cn}$ para algum $c=c(\varepsilon)>0$.
\end{problema}


\newpage
\section{Estimativas de Chebyshev}
\label{sec:14-6-2010}
\begin{center}
14/6/2010
\end{center}

O postulado de Bertrand diz que todo intervalo $(n,2n]$, com $n\geq 1$, contém pelo menos um
primo. Apresentamos nesta seção uma prova elegante de um resultado que implica uma versão mais
fraca do postulado de Bertrand, a saber, para cada $\varepsilon>0$, existe $n_0=n_0(\varepsilon)$
tal que se $n\geq n_0$, então o intervalo $(n,(2+\varepsilon)n]$ contém pelo menos um primo. O
seguinte teorema é o resultado principal desta seção.

\begin{teorema}\label{teo:estimativaPrincipalChebyshev}
Para $n\geq 4$, temos que
$$
(\ln 2)\frac{n}{\log n} \leq \pi(n) \leq \left(\ln 4+\frac{8\ln\ln n}{\ln n}\right)\frac{n}{\ln n}.
$$
\end{teorema}
 
Para provarmos o limite superior, vamos precisar da seguinte estimativa.

\begin{teorema}\label{teo:produtorioPrimos}
Para $n\geq 1$, temos
$$
\prod_{p\leq n}p\leq4^n.
$$
\end{teorema}

Com a estimativa dada pelo Teorema \ref{teo:produtorioPrimos}, observe que, para todo $1\leq t\leq n$, temos
$$
t^{\pi(n)-\pi(t)}\leq\prod_{t<p\leq n}p\leq4^n.
$$
Assim, aplicando o logaritmo natural dos dois lados, obtemos
$$
\pi(n)\leq \frac{n\ln 4}{\ln t} + t.
$$
Fazendo $t=n/(\ln n)^2$, temos que
$$
\pi(n)\leq\left(\ln 4+\frac{8\ln\ln n}{\ln n}\right)\frac{n}{\ln n},
$$
desde que $n\geq 4$ (exercício).

Antes de provarmos o limite inferior, vamos à prova do Teorema \ref{teo:produtorioPrimos}.

\begin{proof}[Demonstração do Teorema \ref{teo:produtorioPrimos}]
Utilizamos indução em $n$ e supomos $n\geq 3$.  Se $n$ é par, o resultado segue por indução, uma vez que $n$ não é
primo. Portanto, considere $n$ ímpar e faça $n=2m + 1$. Observe que, como ${2m+1\choose m}={2m+1\choose m+1}$, então
este coeficiente aparece duas vezes na expansão binomial de $(1+1)^{2m+1}$. Portanto,
$$
{2m+1\choose m}\leq\frac{2^{2m+1}}{2}=4^m.
$$
Mas é fácil ver que
$$\left(\prod_{m+1<p\leq 2m+1}p\right) \left| {2m+1\choose m}\leq 4^m\right..$$
Pela hipótese indutiva, temos que
$$
\begin{aligned}
\prod_{p\leq n}p &= \prod_{p\leq m+1}p\prod_{m+1<p\leq 2m+1}p\\
&\leq 4^{m+1}4^m\\
&=4^n.
\end{aligned}
$$
\end{proof}

Para completar a prova (provar o limite inferior), considere $d_n$ o mínimo
múltiplo comum dos números $1,2,\ldots,n$. Dizemos que $p^v||x$ se $p^v| x$ e $p^{v+1}$ não divide $x$. Assim, se
$p^v||n$, então existe~$m\leq n$ tal que $p^v||m$, de onde concluímos que $p^v\leq n$. Portanto,
$$
\begin{aligned}
d_n&=\prod_{p\leq n,\ p^v||d^n}p^v\\
&\leq \prod_{p\leq n} n\\
&=n^{\pi(n)}.
\end{aligned}
$$
Aplicando logaritmo dos dois lados da desigualdade acima, obtemos $\pi(n)\geq \ln d_n/\ln n$. O teorema abaixo completa
a prova do Teorema \ref{teo:estimativaPrincipalChebyshev}.



\begin{teorema}[Nair \cite{Na82}]
Para $n\geq 7$, temos que $d_n\geq 2^n$.
\end{teorema}
\begin{proof}
Para começar, definimos, para $1\leq m\leq n$,
$$
I(m,n)=\int_0^1 x^{m-1}(1-x)^{n-m}dx.
$$
Através da expansao binomial de $(1-x)^{n-m}$, obtemos
$$
I(m,n)=\sum_{j=0}^{n-m}(-1)^j{n-m \choose j}\frac{1}{m+j}.
$$
Assim, é fácil ver que $I(m,n)$ é um número racional cujo denominador divide $d_n$, uma vez que $d_n$ é o mínimo
múltiplo comum dos números $1,2,\ldots,n$. Mas note que, para todo $0\leq y\leq 1$, temos a seguinte igualdade.
$$
\begin{aligned}
\sum_{m=1}^{n}{n-1\choose m-1}y^{m-1}I(m,n) &= \int_0^1(1-x+xy)^{n-1}dx\\
&=\frac{1}{n}\sum_{m=1}^n y^{m-1}.
\end{aligned}
$$
Desta forma, para $1\leq m\leq n$, temos que
$$
I(m,n)=\frac{1}{n{n-1 \choose m-1}} = \frac{1}{m{n\choose m}}.
$$
Com isso, temos que $m{n\choose m}|d_n$ para $1\leq m\leq n$. Portanto, podemos concluir que~$n{2n\choose
n}|d_{2n}|d_{2n+1}$ e~$(n+1){2n+1\choose n}=(2n+1){2n\choose n}|d_{2n+1}$. Mas como $n$ e $2n+1$ são números primos
entre si, temos que~${n(2n+1){2n\choose n}|d_{2n+1}}$. Assim, podemos concluir que
$$
\begin{aligned}
d_{2n+1}&\geq n 4^n,\ &n\geq 1.\\
d_{2n+1}&\geq 2.4^n=2^{2n+1},\ &n\geq 2.\\
d_{2n+2}&\geq d_{2n+1}\geq 4^n+1,\ &n\geq 4. 
\end{aligned}
$$
Temos então o resultado desejado, $d_n\geq 2^n$, para $n\geq 9$. Para $n=7$ e $n=8$, o resultado pode ser facilmente
verificado.
\end{proof}



\newpage
\bibliographystyle{amsplain_yk}
\bibliography{minhabib}

\end{document}

