%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC5827 Topicos de Matemática Discreta               %
% 2o. semestre de 2008                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 19 Nov 2008 02:39:52pm BRST yoshi@turan.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

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

%\usepackage{refcheck}
\usepackage{srcltx}

\let\:=\colon
\let\epsilon=\varepsilon
\let\phi=\varphi
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\dim{\mathop{\rm dim}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\im{\mathop{\rm im}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim

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

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cE{\mathcal E}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}
\def\cZ{\mathcal Z}

\def\barp{{\bar p}}

\def\Ave{\mathop{{\rm Ave}}\nolimits}
\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}
\def\diam{\mathop{{\rm diam}}\nolimits}
\def\PG{\mathop{{\rm PG}}\nolimits}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfa{\textbf{a}}
\def\bfb{\textbf{b}}
\def\bff{\textbf{f}}
\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}
\def\bfX{\textbf{X}}
\def\bfdelta{\boldsymbol\delta}

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

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

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

\begin{enumerate}
  
\def\Poly{{\rm P}}
\def\NP{{\rm NP}}
\item{} [Desafio] Decida se $\Poly=\NP$.  \datedue{até o final do semestre} 
  
\item{} [Desafio] Sejam~$G_1,\dots,G_M$ grafos distintos sobre
  $[n]=\{1,\dots,n\}$.  Suponha que a interseção~$G_i\cap G_j$ contém um
  triângulo para todo~$i$ e~$j$.
  \begin{itemize}
  \item[(\textit{i})]Exiba uma tal coleção de grafos
    com~$M=2^{{n\choose2}-3}$. 
  \item[(\textit{ii})]Dê uma cota superior para~$M$.  
  \end{itemize}

\item Prove as seguintes estimativas.  Nesta questão, escrevemos~$O(f(x))$
  para qualquer termo~$y$ tal que~$|y|\leq C|f(x)|$ para todo~$x$
  satisfazendo~$|x|\leq x_0$, onde~$C$ e~$x_0>0$ são constantes absolutas.
  (Observe que, nestas estimativas, estamos intessados em uma vizinhança
  de~$0$.)
  \begin{enumerate}
  \item[(\textit{i})]$1+x\leq\e^x$ para todo~$x\in\RR$.
  \item[(\textit{ii})]$1+x>\exp\big\{x-x^2/2\big\}$ para todo~$0<x\leq1$. 
  \item[(\textit{iii})]$1-x>\exp\big\{-x-x^2\big\}$ para todo~$0<x<x_0$,
    para algum~$x_0>0$.  De fato, podemos tomar, por exemplo,~$x_0=0{.}68$.  
  \item[(\textit{iv})]Prove que $1+x\geq\exp\{x/(1+x)\}$ para todo~$x>-1$.
  \end{enumerate}
  [\textit{Sugestão.} Lembre que~$1/(1-x)=1+x+x^2+\dots$ uniformemente
  se~$|x|\leq x_0$ e~$x_0<1$.  Integre ambos os lados para obter
  $$
  -\log(1-x)=x+{1\over2}x^2+{1\over3}x^3+\dots]
  $$
  
\item\label{Q:binom_bds} Prove as seguintes estimativas para~$a\choose b$,
  onde~$a$ e~$b$ são inteiros não-negativos.
  \begin{enumerate}
  \item[(\textit{i})]Se~$a\geq b$, então
    \begin{equation}
       \label{eq:binom_lwbd}
       {a\choose b}\geq\(a\over b\)^b.
    \end{equation}
     
  \item[(\textit{ii})]
    \begin{equation}
       \label{eq:binom_upbd1}
       {a\choose b}\leq{a^b\over b!}.
    \end{equation}

  \item[(\textit{iii})]Para todo~$b>0$, 
    \begin{equation}
       \label{eq:binom_upbd2}
       {a\choose b}\leq\(\e a\over b\)^b.
    \end{equation}
    [\textit{Sugestão para~$(\text{\textit{iii}}\,)$.} Avalie~$(1+x)^a$ por
    cima e por baixo para~$x=b/a$.  Use, para tanto, $1+x\leq\e^x$ e o binômio
    de Newton: $(1+x)^a\geq{a\choose b}x^b$.]

  \item[(\textit{iv})]Prove a seguinte versão mais forte de~(\textit{iii}): 
    \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 Para inteiros~$t\leq n$, ponha
  \begin{equation}
    \label{eq:max_t_inter}
    g(n,t)=\max|\cF|
  \end{equation}
  onde o máximo é tomado sobre todos os~$\cF\subset\cP([n])=2^{[n]}$ que são
  \textit{$t$-intersectantes}, isto é, para todo~$F$ e~$F'\in\cF$,
  temos~$|F\cap F'|\geq t$.  (Note que, aqui, não estamos considerando
  $r$-grafos para algum~$r$ fixo, mas sistemas de conjuntos sem restrição de
  cardinalidade para seus membros).
  \begin{enumerate}
  \item[(\textit{i})]Mostre que~$g(n,1)=2^{n-1}$.
  \item[(\textit{ii})]Mostre que, para todo inteiro~$t\geq2$,
    temos~$g(n,t)=(1+o(1))2^{n-1}$.  Isto é, prove que
    $\lim_{n\to\infty}g(n,t)2^{-n+1}=1$. \sugestao{Use a fórmula de Stirling 
      \begin{equation}
        \label{eq:Stirling}
        n!=(1+o(1))\(n\over\e\)^n\sqrt{2\pi n}
      \end{equation}
      para provar que 
      \begin{equation}
        \label{eq:middle_bin}
        {n\choose\lfloor n/2\rfloor+k}=(1+o(1))2^n\sqrt{2\over\pi n}=o(2^n),
      \end{equation}
      para todo~$k\in\ZZ$ fixo.  Deduza que
      $$
      \sum_{k\geq(n+t)/2}{n\choose k}=(1+o(1))2^{n-1},
      $$
      e use esse fato.}  
  \end{enumerate}
  \datedue{5/11/2008}
  
\item{}[Caso de igualdade no Erd\H os--Ko--Rado] Sejam~$n$ e~$k$ inteiros
  positivos, com~$n>2k$.  Seja~$\cF\subset{[n]\choose k}$ um sistema
  $k$-uniforme intersectante com
  \begin{equation}
    \label{eq:q0.2}
    |\cF|={n-1\choose k-1}.
  \end{equation}
  Prove que existe~$x\in[n]$ para o qual temos
  \begin{equation}
    \label{eq:q0.1b}
    \cF=\{F\subset[n]\:|F|=k\text{ and }x\in F\}.
  \end{equation}
  \datedue{5/11/2008}

\item Seja~$\cF\subset{[4r]\choose2r}$ um sistema $2$-intersecting com~$|\cF|$
  o maior possível.  Prove que
  \begin{equation}
    \label{eq:(4r,2r,2)-trivial}
    |\cF|=\({1\over2}-\epsilon(r)\){4r\choose2r}, 
  \end{equation}
  onde~$\lim_{r\to\infty}\epsilon(r)=0$.  \datedue{17/11/2008}
  
\item\label{ex:Turan-graph} Seja~$H=H^n$ um grafo $r$-partido de ordem~$n$.
  Prove que~$H$ tem no máximo
  \begin{equation}
    \label{eq:r-partt-max}
    {n\choose2}-\sum_{0\leq i<r}{\lfloor(n+i)/r\rfloor\choose2}
  \end{equation}
  arestas.  Mostre que, a menos de isomorfismo, existe um único tal~$H$ com o
  número de arestas dado por~\eqref{eq:r-partt-max} (tais grafos são às vezes
  chamados de \textit{grafos de Turán} e são denotados por~$T_r(n)$).

\item Deduza o Teorema de Turán do Teorema de Erd\H os: o número máximo de
  arestas em um grafo~$G$ de ordem~$n$ que não contém~$K^{r+1}$ como subgrafo
  é dado por~\eqref{eq:r-partt-max}.  Ademais, se um tal grafo~$G$ tem o
  número de arestas dado em~\eqref{eq:r-partt-max}, então~$G$ é isomorfo
  a~$T_r(n)$ (veja o Exercício~\ref{ex:Turan-graph}).  \datedue{17/11/2008}
  
\item Considere o plano projetivo~$\PG(2,q)$.  Seja~$G$ o grafo cujos vértices
  são os pontos de~$\PG(2,q)$, e o vértice~$(x,y,z)$ é adjacente~$(x',y',z')$
  se e só se~$xx'+yy'+zz'=0$.  Use~$G$ para mostrar que
  \begin{equation}
    \label{eq:ERS}
    \lim_{n\to\infty}\ex(n,C^4)n^{-3/2}=1/2.
  \end{equation}\datedue{8/12/2008}
\end{enumerate}  
 
\end{document}

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