%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Prova de MAC5827 Topicos de Matemática Discreta                    %
% 2o. semestre de 2003                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 03 Mar 2004 11:41:48am BRT yoshi@erdos.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
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\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\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\barp{{\bar p}}

\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\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\bfx{\textbf{x}}
\def\bfy{\textbf{y}}

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

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

\begin{document}
\title[MAC5827 Matemática Discreta]{Prova de Matemática 
  Discreta\\2{\tiny o.} semestre de 2003} 
\date{Versão de \today}
\maketitle
\pagestyle{plain}
\footskip=20pt

\noindent\textbf{Instruções.}  Esta prova é \textit{individual}, mas
naturalmente você pode consultar suas anotações, livros, etc.  Entregue suas
soluções até as 14:00 do dia 12/12/2003, na secretaria do MAC. 

\bigskip

\begin{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$.  (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}

\item\label{Q:Kleitman}[Kleitman] Suponha que~$\cF$, $\cG$, $\cH$, e~$\cI$ são
  sistemas de conjuntos sobre o conjunto~$X=[n]$, isto é, $\cF$, $\cG$, $\cH$,
  e~$\cI\subset2^X=\cP(X)$.  Suponha ainda que~$\cF$ e~$\cG$ são ``fechados
  por se tomar subconjuntos'' e~$\cH$ e~$\cI$ são ``fechado por se tomar
  superconjuntos''.  Isto é, se $F\subset F'\in\cF$, então~$F\in\cF$ e
  analogamente para~$\cG$; enquanto que se $H\subset H'$ e~$H\in\cH$,
  então~$H'\in\cH$ e analogamente para~$\cI$.  Prove que
  \begin{align}
    |\cF\cap\cG|&\geq2^{-n}|\cF||\cG|,\label{eq:Kleitman}\\    
    |\cH\cap\cI|&\geq2^{-n}|\cH||\cI|,\label{eq:Kleitman2}
  \end{align}
  e
  \begin{align}
    \label{eq:Kleitman3}    
    |\cF\cap\cH|&\leq2^{-n}|\cF||\cH|.
  \end{align}
  \sugestao{É suficiente provar, por exemplo, \eqref{eq:Kleitman3}.  Para
    tanto, fixe um~$x\in X$ e considere os membros de~$\cF$ e~$\cH$ que
    contêm~$x$ e os membros de~$\cF$ e~$\cH$ que não contêm~$x$
    separadamente, e use indução em~$n=|X|$.}
  
\item Use o Lema de Kleitman, dado na Questão~\ref{Q:Kleitman}, para provar os 
  resultados abaixo.
  \begin{enumerate}
  \item[(\textit{i})]Seja~$\cF\subset\cD\subset\cP([n])$.  Mostre que se~$\cF$
    é intersectante e~$\cD$ é fechado por se tomar subconjuntos,
    então~$|\cF|\leq(1/2)|\cD|$.
  \item[(\textit{ii})]Seja~$\cF\subset\cP([n])$ tal que, para todo~$F$
    e~$F'\in\cF$, temos~$F\cap F'\neq\emptyset$ e~$F\cup F'\neq[n]$.  Prove
    que~$|\cF|\leq2^{n-2}$.  Mostre um exemplo em que ocorre a igualdade.
  
\item[(\textit{iii})]Sejam~$\cF_1,\dots,\cF_k\subset\cP([n])$ famílias
  intersectantes.  Prove que
  \begin{equation}
    \label{eq:Kleitman4}
    |\cF_1\cup\dots\cup\cF_k|\leq2^n-2^{n-k}.
  \end{equation}
  Para todo~$n$ e~$k$ com~$1\leq k\leq n$,
  exiba~$\cF_1,\dots,\cF_k\subset\cP([n])$ para os quais vale a igualdade
  em~\eqref{eq:Kleitman4}.
  \end{enumerate}
  
\let\hint\sugestao
\item Prove que os subconjuntos infinitos de~$\NN$ podem ser coloridos de
  vermelho e azul de forma que nenhum subconjunto infinito~$S$ de~$\NN$ tem
  todos os seus subconjuntos infinitos da mesma cor.  \hint{Ponha~$A\sim B$ se
    a diferença simétrica~$A\bigtriangleup B$ é finita; pinte os conjuntos de
    forma que, se~$A=B\setminus\{b\}$, então~$A$ e~$B$ têm cores distintas.}
  
\item Seja~$\cA=\{A_\lambda\:\lambda\in\Lambda\}$ uma família de subconjuntos
  de um conjunto finito~$V$.  Considere os
  subconjuntos~$\Lambda'\subset\Lambda$ tais que o sistema de
  conjuntos~$A_\lambda$ ($\lambda\in\Lambda'$) admite uma transversal (isto é,
  um sistema de representantes distintos: uma coleção de elementos dois a dois
  distintos~$a_\lambda\in A_\lambda$ ($\lambda\in\Lambda'$).  Mostre que
  quaisquer dois tais conjuntos~$\Lambda'\subset\Lambda$ têm a mesma
  cardinalidade.  Defina um matróide sobre~$\Lambda$ a partir desta
  observação.
  
\item\label{Q:Edmonds}[Edmonds] Sejam~$M=M(S)$ e~$N=N(S)$ dois matróides
  sobre~$S$.  Prove que
  \begin{multline}
    \label{eq:Edmonds_inter}
    \qquad\qquad\max\{|I|\:I\in\cI(M)\cap\cI(N)\}\\
    =\min\{r_M(A)+r_N(S\setminus A)\:A\subset S\}.\qquad
  \end{multline}
  \hint{Considere o matróide~$M\vee N^*$, onde~$N^*$ é o dual de~$N$.}  
  
\item Seja~$G$ um grafo conexo, e suponha que as arestas de~$G$ estão
  coloridas de forma arbitrária.  Prove que~$G$ contém uma árvore geradora com
  todas as suas arestas de cores distintas se e só se, para todo subgrafo~$H$
  de~$G$, o número de cores que ocorrem em~$E(G)\setminus E(H)$ é pelo
  menos~$c(H)-1$, onde~$c(H)$ é o número de componentes conexas em~$H$.
  \hint{Lembre-se do matróide uniforme~$U_{n,m}$.  Para cada cor, considere os
    conjuntos de arestas daquela cor e~$m=1$ (isto dá um matróide para cada
    cor).  Aplique o teorema de Edmonds dado na Questão~\ref{Q:Edmonds}.
    Alternativamente, dê uma prova elementar.}

\end{enumerate}  
 
\end{document}

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

