%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC5827 Topicos de Matemática Discreta               %
% 2o. semestre de 2003                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Friday 10 Oct 2003 09:36:39am 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\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 2003} 
\date{Versão de \today}
\maketitle
\pagestyle{plain}
\footskip=25pt

\noindent[Os exercícios desta lista são reciclados de edições anteriores desta
e disciplinas semelhantes.  Alguns exercícios estão em sua versão original, em
inglês.  (Melhor assim do que demorar mais ainda para eu disponibilizá-los).]

\begin{enumerate}
  
\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 Considere a identidade
  \begin{equation}
    \label{eq:linha_Pascal}
    \sum_{0\leq k\leq n}{n\choose k}=2^n,
  \end{equation}
  e seja~$\omega=\omega(n)$ uma função com~$\omega\to\infty$
  conforme~$n\to\infty$.  Podemos dizer que a soma em~\eqref{eq:linha_Pascal}
  está `concentrada' nos termos com~$k$ satisfazendo
  \begin{equation}
    \label{eq:cond_k}
    \left|k-{n\over2}\right|\leq\omega\sqrt n,
  \end{equation}
  pois
  \begin{equation}
    \label{eq:concentracao}
    \sum_k\nolimits^*{n\choose k}\sim2^n,
  \end{equation}
  onde~$\sum_k^*$ indica soma sobre todos os~$k$
  satisfazendo~\eqref{eq:cond_k} e escrevemos~$f(n)\sim g(n)$
  se~$\lim_nf(n)/g(n)=1$.  
  
  Suponha agora que~$\epsilon>0$ é um número real fixo.  Podemos dizer que a
  soma em~\eqref{eq:linha_Pascal} está `exponencialmente concentrada' nos
  termos com~$k$ satisfazendo
  \begin{equation}
    \label{eq:cond_k2}
    \left|k-{n\over2}\right|\leq\epsilon n,
  \end{equation}
  pois
  \begin{equation}
    \label{eq:concentracao2}
    \sum_k\nolimits'{n\choose k}\leq2^n\exp\{-c_\epsilon n\},
  \end{equation}
  onde~$\sum_k'$ indica soma sobre todos os~$k$
  para os quais~\eqref{eq:cond_k2} \textit{não vale}, $c_\epsilon>0$ é uma
  constante que depende apenas de~$\epsilon$, e supomos~$n\geq
  n_0(\epsilon)$. 
  \begin{enumerate}
  \item[(\textit{i})]Prove que a condição de que~$\omega\to\infty$ é
    necessária para que~\eqref{eq:concentracao} valha.  Para tanto, use a
    fórmula de Stirling~\eqref{eq:Stirling}.  
%     Uma versão desta fórmula é como
%     segue: para todo~$n\geq1$, existe~$\alpha_n$
%     com~$1/(12n+1)<\alpha_n<1/12n$ tal que
%     \begin{multline}
%       \label{eq:Stirling}
%       \hspace{2.5cm}n!=\sqrt{2\pi n}\(n\over\e\)^n\e^{\alpha_n}\\
%       =\sqrt{2\pi n}\(n\over\e\)^n\(1+{1\over12n}+O\(1\over n^2\)\).
%       \qquad
%     \end{multline}
    De fato, use~\eqref{eq:Stirling} para provar que se~$k=k(n)=n/2+c_n\sqrt
    n$, onde~$c_n\to c$ ($n\to\infty$) e~$c$ é uma constante, então
    \begin{equation}
      \label{eq:middle_binom}
      {n\choose k}={n!\over k!(n-k)!}\sim{d\over\sqrt n}2^n,
    \end{equation}
    onde~$d=d(c)>0$ é uma constante que depende apenas de~$c$.
    
  \item[(\textit{ii})]Seja~$0<\alpha<1$ um real fixo.  Ponha
    \begin{equation}
      \label{eq:entropy_def}
      H(\alpha)=\alpha\log_2{1\over\alpha}+(1-\alpha)\log_2{1\over1-\alpha}.
    \end{equation}
    Prove que 
    \begin{equation}
      \label{eq:entropy}
      \binom{n}{\lfloor\alpha
        n\rfloor}=2^{(H(\alpha)+o(1))n},
    \end{equation}
    onde~$o(1)\to0$ conforme~$n\to\infty$.  \sugestao{Stirling!}

  \item[(\textit{iii})]Prove~\eqref{eq:concentracao}.  

  \item[(\textit{iv})]Prove~\eqref{eq:concentracao2}.
  \end{enumerate}
  \sugestao{Considere um variável aleatória binomial~$X$ de parâmetros $n$
    e~$1/2$, de forma que~$\PP(X=k)={n\choose k}2^{-n}$.  Para~(\textit{iii}),
    aplique a desigualdade de Chebyshev (consulte suas notas de
    probabilidade!).  Para~(\textit{iv}), use~(\textit{ii}).}
  \datedue{24/10/2002}
  
\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{19/9/2002}

\item Para naturais~$n$, $a$, e~$b$, seja
  \begin{equation}
    \label{eq:f_def}
    f(n,a,b)=\max|\cF|,
  \end{equation}
  onde o máximo é tomado sobre todos os sistemas de
  conjuntos~$\cF\subset2^{[n]}$ satisfazendo
  \begin{equation}
    \label{eq:diag_inter}
    |F|\equiv a\!\!\pmod 2 \qquad\text{para todo~$F\in\cF$}
  \end{equation}
  e
  \begin{equation}
    \label{eq:cross_inter}
    |F\cap F'|\equiv b\!\!\pmod 2 \quad\text{para todo~$F$, $F'\in\cF$
     com~$F\neq F'$.} 
  \end{equation}
  Determine ou estime~$f(n,a,b)$ para todos
  pares~$(a,b)\in\{0,1\}\times\{0,1\}$. 

\item{}[Equality case in Erd\H os--Ko--Rado] Let positive integers~$n$ and~$k$
  be given, with~$n>2k$.  Suppose~$\cF\subset{[n]\choose k}$ is an
  intersecting $k$-uniform hypergraph with
  \begin{equation}
    \label{eq:q0.2}
    |\cF|={n-1\choose k-1}.
  \end{equation}
  Prove that there is~$x\in[n]$ for which we have
  \begin{equation}
    \label{eq:q0.1b}
    \cF=\{F\subset[n]\:|F|=k\text{ and }x\in F\}.
  \end{equation}

\item Let~$\cF\subset{[4r]\choose2r}$ be a $2$-intersecting family
  with~$|\cF|$ as large as possible.  Prove that
  \begin{equation}
    \label{eq:(4r,2r,2)-trivial}
    |\cF|=\({1\over2}-\epsilon(r)\){4r\choose2r}, 
  \end{equation}
  where~$\lim_{r\to\infty}\epsilon(r)=0$.  
  
  [Extra credit] Try to prove~\eqref{eq:(4r,2r,2)-trivial} for a
  `large'~$\epsilon(r)$.  Can you prove it for some~$\epsilon(r)$ such
  that~$\epsilon(r){4r\choose2r}\to\infty$?
  
\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 Suppose~$\cF\subset\cD\subset\cP([n])$.  Show that if~$\cF$ is
  intersecting and~$\cD$ is a down-set, then~$|\cF|\leq(1/2)|\cD|$.
  
\item{}[Kleitman] Let~$\cF_1,\dots,\cF_k\subset\cP([n])$ be intersecting
  families.  Show that
  \begin{equation}
    \label{eq:Kleitman4}
    |\cF_1\cup\dots\cup\cF_k|\leq2^n-2^{n-k}.
  \end{equation}
  For each~$n$ and~$k$ with~$1\leq k\leq n$,
  exhibit~$\cF_1,\dots,\cF_k\subset\cP([n])$ for which equality holds
  in~\eqref{eq:Kleitman4}. 

\item{}[Kleitman] Let~$\cF\subset\cP([n])$ be such that, for all~$F$,
  $F'\in\cF$, we have~$F\cap F'\neq\emptyset$ and~$F\cup F'\neq[n]$.  Prove
  that~$|\cF|\leq2^{n-2}$.
  
\item Fix an integer~$k\geq2$ and let~$\epsilon>0$ be a real number.  Show
  that if~$n\geq n_0(k,\epsilon)$, then there is a
  system~$\cB\subset{[n]\choose k}$ with
  \begin{equation}
    \label{eq:approx_Steiner}
    |\cB|\leq(1+\epsilon){n\choose k-1}{k\choose k-1}^{-1}
  \end{equation}
  covering all $(k-1)$-element subsets of~$n$, that is, such that for
  any~$C\in{[n]\choose k-1}$, there is some~$B\in\cB$ such that~$C\subset B$.
  \hint{Consider $k$-tuples $x_1,\dots,x_k$ with $\sum_ix_i\equiv0\pmod n$.}
  
\item Let integers~$2\leq\ell\leq k\leq n$ be fixed.  Let~$\cC\subset{[n]\choose\ell}$
  be a system \textit{hitting all $k$-element subsets of~$[n]$}, that is, such
  that for any~$B\in{[n]\choose k}$, there is~$C\in\cC$ with~$C\subset B$.
  \begin{enumerate}
  \item[(\textit{i})]Show that
    \begin{equation}
      \label{eq:Turan}
      |\cC|\geq{n\choose\ell}{k\choose\ell}^{-1}.
    \end{equation}
  \item[(\textit{ii})]Suppose now that~$\ell=2$.  How sharp do you think the
  lower bound in~\eqref{eq:Turan} is?  \hint{This is actually a graph theory
  question.  Check your favourite graph theory book, if you don't see what
  this question is about.}
  \end{enumerate}

\item Let us say that a chain~$\cC=\{A_1,\dots,A_k\}$, with
  $A_1\subset\dots\subset A_k$, of elements of~$\cP([n])$ is a
  \textit{symmetric chain} if the following conditions hold:
  \begin{enumerate}
  \item[(\textit{a})]$\cC$ is \textit{saturated}, that is, $|A_i|=|A_{i-1}|+1$ 
    for all~$1<i\leq k$.
  \item[(\textit{b})]$|A_1|+|A_k|=n$.
  \end{enumerate}
  Prove the following assertions:
  \begin{enumerate}
  \item[(\textit{i})]$\cP([n])$ may be partitioned into symmetric chains.
    \hint{Use induction on~$n$.  Suppose~$n>0$ and that the result holds for
      smaller values of~$n$.
      Let~$\cP([n-1])=\bigcup_{\lambda\in\Lambda}\cC_\lambda$ be a
      decomposition of~$\cP([n-1])$ into symmetric chains.  Construct two
      chains from each~$\cC_\lambda$ as follows.  Suppose~$\cC_\lambda$ is the
      chain $A_1\subset\dots\subset A_k$.  Then consider
      $A_1\subset\dots\subset A_k\subset A_k\cup\{n\}$ and
      $A_1\cup\{n\}\subset\dots\subset A_{k-1}\cup\{n\}$.}
    
  \item[(\textit{ii})][Sperner] The maximal number of elements in an antichain
    in $\cP([n])$ is~${n\choose\lfloor n/2\rfloor}$.
    
  \item[(\textit{iii})] The chains in the decomposition of~$\cP([n])$ may be
    required to satisfy the following extra condition.  Suppose~$\cC_\lambda$
    is a chain $A_1\subset\dots\subset A_k$ in the decomposition
    of~$\cP([n])$.  Then, for any~$1<i<k$, there is~$B\subset[n]$ such that
    \begin{equation}
      \label{eq:sandwich}
      A_{i-1}\subset B\subset A_{i+1}
    \end{equation}
    and, furthermore, the chain of the decomposition that contains~$B$ has
    cardinality less than~$k$.  \hint{Check the hint for~(\textit{i}).}
  \end{enumerate}
  
\item{}[Hansel] Prove that the number of antichains in~$\cP([n])$ is at most
  \begin{equation}
    \label{eq:Hansel_bd}
    3^{n\choose\lfloor n/2\rfloor},
  \end{equation}
  following the steps below or otherwise.
  \begin{enumerate}
  \item[(\textit{i})]Observe that we need to give an upper bound for the
    number of functions~$f\:\cP([n])\to\{0,1\}$ that are decreasing (that is,
    such that~$f^{-1}(1)$ is a down-set).
  \item[(\textit{ii})]Consider a decomposition~$\Pi$ of~$\cP([n])$ into
    symmetric chains satisfying~(\textit{iii}) of the previews exercise.
  \item[(\textit{iii})]Check how many decreasing functions~$f$ one may produce
    by defining~$f$ on each chain in~$\Pi$ in turn, considering smaller chains
    first.  Suppose a function~$f$ is being constructed, and consider a
    chain~$\cC$ in~$\Pi$ with~$k$ elements ($k\geq2$) on which~$f$ is still
    undefined ($f$ is already defined on all smaller chains in~$\Pi$).  Argue
    that~$f$ can only be extended in at most~$3$ ways on~$\cC$.  \hint{This is
      clear for~$k=2$.  For~$k>2$, use property~(\textit{iii}) of the previous
      exercise.}
  \end{enumerate}

\item Prove that there is a colouring of the natural numbers with red and blue
  such that no infinite arithmetic progression is monochromatic.

\item Prove that the infinite subsets of~$\NN$ may be coloured with red and
  blue in such a way that no infinite subset~$S\subset\NN$ has all its
  infinite subsets coloured with the same colour.  \hint{Write~$A\sim B$ if
    the symmetric difference~$A\bigtriangleup B$ is finite; colour the sets so
    that, if~$A=B\setminus\{b\}$, then~$A$ and~$B$ have different colours.}
  
\item Prove that there is a colouring of the pairs ($2$-element subsets)
  of~$\RR$ with red and blue such that no uncountable subset~$S\subset\RR$ has
  all its pairs of the same colour.
  %\hint{Consider a well ordering~$\preceq$
  %of the reals.  Colour a pair~$\{x,y\}$ blue if~$x\preceq y$ and~$x\leq y$
  %($\leq$ is the usual order on the reals).}
  
\item
  \begin{itemize}
  \item[(\textit{i})]Suppose a family of sets~$\cF\subset\cP(\NN)=2^\NN$ is
    such that the symmetric difference~$F\bigtriangleup F'$ is finite for all
    distinct~$F$, $F'\in\cF$.  Prove that~$\cF$ is countable.
  \item[(\textit{ii})]A family of sets~$\cF$ is called \textit{quasi-disjoint}
    if the intersection~$F\cap F'$ is finite for all distinct~$F$, $F'\in\cF$.
    Prove that there is an uncountable quasi-disjoint family of
    sets~$\cF\subset\cP(\NN)=2^\NN$.
  \end{itemize}

\end{enumerate}  
 
\end{document}

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