%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC5827 Topicos de Matemática Discreta               %
% 2o. semestre de 2007                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Friday 14 Dec 2007 07:37:11pm 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\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 2007} 
\date{Versão de \today}
\maketitle
\pagestyle{plain}
\footskip=25pt

\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}
  \datedue{28/8/2007}
 
\item($^+$) [Kleitman] Seja~$B$ um espaço normado.  (Se você não está
  familiarizado com espaços normados, suponha que~$B$ é o~$\RR^d$ para
  algum~$d$.)  Sejam~$x_1,\dots,x_n\in B$.  Considere
  as~$2^n$ somas da forma
  $$
  x_{i_1}+\dots+x_{i_k},
  $$
  onde~$i_1<\dots<i_k$ e~$k\geq0$.  Dizemos que um conjunto~$S$ dessas
  somas é \textit{pequeno} se quaisquer dois membros de~$S$ distam~$<1$.
  
  Determine~$f(n)$ para todo~$n\geq0$, onde definimos~$f(n)$ como sendo
  $$
  \max_{x_1,\dots,x_n}\max\{|S|\:\text{$S$ é pequeno}\}
  $$
  e o (primeiro) máximo é tomado sobre todas as
  seqüências~$x_1,\dots,x_n\in B$ com~$||x_i||\geq1$ para todo~$i$ (isto é,
  todos os~$x_i$ têm norma pelo menos~$1$).
  
\item Sejam~$x_1,\dots,x_n\in\RR^d$ e~$\Delta\geq0$.  Considere as~$2^n$ somas
  da forma
  $$
  x_{i_1}+\dots+x_{i_k},
  $$
  onde~$i_1<\dots<i_k$ e~$k\geq0$.  Dizemos que um conjunto~$S$ dessas
  somas é $\Delta$-\textit{pequeno} se quaisquer dois membros de~$S$
  distam~$\leq\Delta$.
  
  Seja
  $$
  m_d(n,\Delta)=\max_{x_1,\dots,x_n}\max\{|S|\:\text{$S$ é
    $\Delta$-pequeno}\}
  $$
  e o (primeiro) máximo é tomado sobre todas as
  seqüências~$x_1,\dots,x_n\in B$ com~$||x_i||\geq1$ para todo~$i$ (isto é,
  todos os~$x_i$ têm norma pelo menos~$1$).  Prove que existe uma
  constante~$c_d$ que depende apenas de~$d$ para o qual vale
  \begin{equation}
    \label{eq:weak_FF_for_LO}
    m_d(n,\Delta)\leq c_d(\lfloor\Delta\rfloor+1){n\choose\lfloor
      n/2\rfloor}. 
  \end{equation}
  \datedue{28/8/2007}
  
\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{30/8/2007}
  
\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{30/8/2007}
  
\item{}[Erd\H os--Szekeres] 
  \begin{itemize}
  \item[(\textit{i})]Prove que, para todo~$n\geq1$, existe~$N=N(n)$ tal que
    toda seqüência $a_0,\dots,a_N$ de números contém uma subseqüência
    mo\-nó\-to\-na com~$n+1$ elementos, isto é, uma subseqüência não-crescente
    ou uma subseqüência não-decrescente com~$n+1$ elementos.  Mais
    formalmente, prove que existem~$0\leq i_0<\dots<i_n\leq N$ com
    $a_{i_0}\leq\dots\leq a_{i_n}$ ou com $a_{i_0}>\dots>a_{i_n}$.

  \item[(\textit{ii})]Prove que podemos tomar~$N(n)=n^2$ em~(\textit{i})
    acima.  
  \end{itemize}
  \datedue{11/9/2007} 

\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\}$ (os dois casos estudados em sala podem
  ser discutidos sucintamente).  \datedue{11/9/2007}
  
\item Seja~$\cF\subset{[4r]\choose2r}$ um sistema $2$-intersecting com~$|\cF|$
  o maior possível.  
  \begin{enumerate}
  \item[(\textit{i})]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$.  
    
  \item[(\textit{ii})] [Desafio] Tente provar~\eqref{eq:(4r,2r,2)-trivial}
    para~$\epsilon(r)$ `grande'.  Você consegue
    provar~\eqref{eq:(4r,2r,2)-trivial} para algum~$\epsilon(r)$ tal
    que~$\epsilon(r){4r\choose2r}\to\infty$?
  \end{enumerate}
  \datedue{11/9/2007}
  
\item Seja $V$ o espaço dos vetores $(a_1,\dotsc, a_n)^T$, onde os $a_i$
  pertencem a um corpo $F$.  Para $\bfa = (a_1, \dotsc, a_n)^T$ e $\bfb =
  (b_1, \dotsc, b_n)^T$, defina o produto interno entre $\bfa$ e~$\bfb$ como
  $\bfa^T\bfb = a_{1}b_{1} + \dotsm + a_{n}b_{n}$. Além disso, seja~$M$ um
  subespaço de $V$ e $A$ uma transformação linear de $V$ em~$V$.  Decida se as
  seguintes afirmações são verdadeiras:
  \begin{itemize}
  \item[(a)] Se $A$ é não-singular, então $A^T$ também é não-singular.
  \item[(b)] Se $A$ é não-singular, então $A^TA$ é
    não-singular.
  \item[(c)] $A$ e $A^{T}A$ têm o mesmo núcleo (kernel).
  \item[(d)] $M\cap M^\perp = \{ 0\}$, onde $M^{\perp}$ é o subespaço
    ortogonal a $M$, isto é, $M^{\perp} = \{\bfa \: \bfa^{T}\bfb = 0 \,
    \text{ para todo }\bfb \in M\}$.
  \item[(e)] O subespaço gerado por $M\cup M^{\perp}$ é igual a $V$.
  \item[(f)] $\dim(M) + \dim(M^{\perp}) = n$.
  \item[(g)] $(M^{\perp})^{\perp} = M$.
  \end{itemize}
  \datedue{14/9/2007}

\item\def\GF{{\rm GF}}
  \begin{itemize}
  \item[(a)] Seja $V$ um espaço $n$-dimensional sobre $\GF(2)=\ZZ_2$, e~$M$ um
    subespaço de $V$. Mostre que $(1,\dotsc, 1)^T \in \< M\cup M^{\perp}\>$,
    onde $\< X\>$ indica o espaço gerado por $X$.
    
  \item[(b)] Seja $A$ uma matriz simétrica onde todas as entradas assumem
    valores em $\{ 0, 1\}$. Prove que a diagonal de $A$, considerada como um
    vetor linha, pertence ao espaço gerado pelas linhas de $A$ sobre~$\GF(2)$.
  \end{itemize}

  \datedue{18/9/2007}

\item
  Seja $G$ um grafo.
  \begin{itemize}
  \item[(a)] $V(G)$ pode ser particionado em
    dois conjuntos $V_{1}$ e $V_{2}$ de modo que os subgrafos de $G$
    induzidos por esses conjuntos satisfazem que todos os vértices têm
    grau par (nos subgrafos induzidos).
  \item[(b)] $V(G)$ pode ser particionado em dois conjuntos $V_{1}$ e
    $V_{2}$ de modo que o subgrafo induzido por $V_{1}$ satisfaz que
    todos os seus vértices têm grau par e o subgrafo induzido por
    $V_{2}$ satisfaz que todos os seus vértices têm grau ímpar.
  \item[(c)] Assuma que para todo vértice de um grafo há uma lâmpada e
    um botão. No começo todas as lâmpadas estão acesas. Apertar o
    botão de um vértice inverte a configuração de sua lâmpada e das
    lâmpadas dos seus vizinhos (as que estavam apagadas se acendem e as que
    estava acesas se apagam). Mostre que é possível apertar os botões de
    forma que todas as lâmpadas ficarão apagadas.
  \end{itemize}

  \datedue{18/9/2007}
  
\item\label{Q:chi_R_n} Consideramos aqui o número cromático~$\chi(\RR^n)$
  do~$\RR^n$, o menor número de cores com que podemos colorir os pontos
  de~$\RR^n$ evitando dois pontos à distância~$1$ da mesma cor.
  \begin{enumerate}
  \item[(\textit{i})]Desenhe/descreva um grafo que prova
    que~$\chi(\RR^2)\geq4$.  Justifique sua resposta sucintamente. 
    
  \item[(\textit{ii})]Descreva um grafo que prova que~$\chi(\RR^n)\geq1.2^n$
    para todo~$n$ com~$n\geq n_0$ para algum~$n_0$.  Justifique sua resposta
    sucintamente.  \observacao{Uma versão simplificada desse item é o
      Ex.~\ref{Q:num_crom}.  Se você preferir, você pode entregar
      Ex.~\ref{Q:num_crom} no lugar desse item.}

  \end{enumerate}

  \datedue{25/9/2007}
  
\item\label{Q:deB-E} 
  \begin{enumerate}
  \item[(\textit{i})]Seja~$G$ um grafo com conjunto de
    vértices~$V(G)=\NN^*=\{1,2,\dots\}$ e com~$\chi(G)=q<\infty$.  Prove que
    existe um subgrafo~$G'$ de~$G$ com um número finito de vértices
    e~$\chi(G')=q$.  Isto é, se todos os subgrafos finitos de um grafo
    infinito~$G$ são $(q-1)$-coloríveis, então~$G$ é $(q-1)$-colorível.
    \sugestao{Seja~$G_i$ o subgrafo de~$G$ induzido por~$[i]$ ($i\geq1$).
      Suponha que~$\chi(G_i)<q$ para todo~$i$.  Fixe uma $(q-1)$-coloração
      própria de~$G_i$ para todo~$i$.  Para infinitos~$i$ (digamos,
      $i_1<i_2<\dots$), o vértice~$1$ de~$G$ recebe uma mesma cor nas
      $(q-1)$-colorações dos~$G_{i_1},G_{i_2},\dots$, digamos~$c_1$.  Pinte o
      vértice~$1$ de~$G$ da cor~$c_1$.  Passamos a considerar os grafos
      $G_{i_1},G_{i_2},\dots$ no resto da prova.  Ponha~$G_1^{(1)}=G_{i_1}$,
      $G_2^{(1)}=G_{i_2}$, etc.  Para infinitos~$i$ (digamos,
      $i_1^{(1)}<i_2^{(1)}<\dots$), o vértice~$2$ de~$G$ recebe uma mesma cor
      nas $(q-1)$-colorações dos~$G_{i_1}^{(1)},G_{i_2}^{(1)},\dots$,
      digamos~$c_2$.  Pinte o vértice~$2$ de~$G$ da cor~$c_2$.  Basta agora
      completar esta prova.} \datedue{25/9/2007}
    
  \item[(\textit{ii})][Para meditar] Considere agora o caso em que~$G$ acima
    tem conjunto de vértices~$\RR$ (e não mais~$\NN^*$).  Como seria o
    resultado análogo?  Como seria a prova?

  \end{enumerate}
  
\item\label{Q:PNT} Para~$x\in\RR$, seja~$\pi(x)$ o número de
  números primos~$p\leq x$.  O teorema dos números primos nos diz que
  \begin{equation}
    \label{eq:PNT}
    \pi(x)=(1+o(1)){x\over \log x},
  \end{equation}
  onde~$o(1)\to0$ conforme~$x\to\infty$.  Seja~$p_k$ o $k$-ésimo primo (assim,
  $p_1=2$, $p_2=3$, e~$p_{10}=29$).
  \begin{enumerate}
  \item[(\textit{i})]Prove que~$p_k/p_{k-1}=1+o(1)$ conforme~$k\to\infty$.

  \item[(\textit{ii})]Prove que~$p_k=(1+o(1))k\log k$ conforme~$k\to\infty$.
  \end{enumerate}
  \datedue{27/9/2007}
  
\item\label{Q:num_crom} Seja~$c(n)=\chi(\RR^n)$ o número cromático do~$\RR^n$.
  \begin{itemize}
  \item[(\textit{i})]Seja~$p$ um primo.  Prove que
    \begin{equation}
      \label{eq:chromatic_lwbd}
      c(4p-1)
      \geq{4p-1\choose2p-1}\bigg(\sum_{0\leq j<p}{4p-1\choose j}\bigg)^{-1}. 
    \end{equation}
  \item[(\textit{ii})]Prove que
    $$
    \sum_{0\leq j<p}{4p-1\choose j}
    \leq\(1+{1\over3}+{1\over3^2}+\dots\){4p-1\choose p-1}
    \leq{3\over2}{4p-1\choose p-1}.
    $$
    
  \item[(\textit{iii})]Use a fórmula de Stirling~\eqref{eq:Stirling} para
    deduzir que
    $$
    {n\choose\alpha n}=\(1\over\alpha^\alpha(1-\alpha)^{1-\alpha}\)
    ^{(1+o(1))n},
    $$
    ou, equivalentemente,
    $$
    \lim_{n\to\infty}{1\over n}\log{n\choose\alpha n}=H(\alpha),
    $$
    onde~$H(\alpha)=\alpha\log(1/\alpha)+(1-\alpha)\log(1/(1-\alpha))$ é a
    assim chamada função entropia.
    
  \item[(\textit{iv})]Prove que o lado direito de~\eqref{eq:chromatic_lwbd} é
    pelo menos~$(1.139)^{4p-1}$ se~$p$ é suficientemente grande.
  \end{itemize}
  \datedue{27/9/2007} \observacao{Esta é uma versão levemente simplificada do
    Ex.~\ref{Q:chi_R_n}(\textit{ii}).  Você pode entregar esse exercício em
    vez de entregar o Ex.~\ref{Q:chi_R_n}(\textit{ii})}
  
\item\label{Q:_general_n} O Exercício~\ref{Q:num_crom} mostra
  que~$c(4p-1)\geq(1.139)^{4p-1}$ para todo primo~$p$ suficientemente grande.
  Use o resultado do Ex.~\ref{Q:PNT} para deduzir que~$c(n)\geq(1.13)^n$ para
  todo~$n$ suficientemente grande.  \datedue{27/9/2007}
  
\item\label{Q:Borsuk} 
  \begin{enumerate}
  \item[(\textit{i})]Seja~$p$ um primo.  Construa um conjunto~$X$ de
    ${4p\choose2p}$ pontos em~$\RR^{4p-1}$ com a seguinte propriedade:
    \textsl{todo~$X'\subset X$ que não contém dois elementos ortogonais é tal
      que
      $$
      |X'|\leq2\sum_{0\leq j<p}{4p\choose j}.
      $$}\sugestao{Considere vetores com coordenadas~$\pm1$ em~$\RR^{4p}$ com
      o mesmo número de~$+1$s e~$-1$s.}
  \item[(\textit{ii})]Use o conjunto~$X$ de~(\textit{i}) para construir um
    conjunto~$Y\subset\RR^d$ que desprova a conjectura de Borsuk (em dimensão
    suficientemente alta), onde~$d={4p-1\choose2}$.  \sugestao{Considere a
      aplicação
      $$
      g\:(a_{ij})_{1\leq i,j\leq4p-1}\mapsto(a_{ij})_{1\leq i<j\leq4p-1},
      $$
      que leva matrizes $(4p-1)\times(4p-1)$ em matrizes triangulares
      superiores.}  
  \item[(\textit{iii})]Seja~$f(d)$ o menor~$k$ tal que todo~$S\subset\RR^d$
    admite uma particão de Borsuk em~$k$ partes, isto é, uma partição em~$k$
    partes de diâmetro menor que~$\diam(S)$.  Use~(\textit{ii}) para provar
    uma cota inferior exponencial para~$f(d)$ para todo~$d$ suficientemente
    grande.
  \end{enumerate}
  \datedue{2/10/2007}
  
\item\label{Q:Erdos-Hajnal} 
  \begin{enumerate}
  \item[(\textit{i})]Fixe um inteiro~$d$ e um real~$\epsilon>0$.  O
    \textit{grafo de Borsuk}~$B(d,\epsilon)$ tem como conjunto de vértices
    $$
    S^d=\{\bfx\in\RR^{d+1}\:\|\bfx\|=1\}
    $$
    e~$\{\bfx,\bfy\}\subset S^d$ é uma aresta de~$B(d,\epsilon)$ se
    $$
    \|\bfx-\bfy\|\geq2-\epsilon.
    $$
    Prove que para todo~$k$ e~$\ell$ inteiros, existem~$d$ e~$\epsilon>0$
    tais que~$B(d,\epsilon)$ tem número cromático~$\geq k$ e cintura
    ímpar~$\geq2\ell+1$.  A \textit{cintura ímpar~$\og(G)$} de um grafo~$G$ é o
    comprimento mínimo de um circuito de comprimento ímpar em~$G$:
    \begin{multline*}\quad
      \og(G)=\min\{2r+1\:\exists x_0,\dots,x_{2r}\in V(G)\text{ distintos}\\
      \text{com $\{x_{i-1},x_i\}\in E(G)$ para todo~$i$ (índices mod $2r+1$)}
      \}    
    \end{multline*}
    \sugestao{Use o teorema de Borsuk: \textsl{se cobrimos a esfera~$S^d$
        com~$d+1$ fechados (respectivamente, abertos), sempre há um par de
        pontos antípodas em um dos fechados (respectivamente, abertos).}}
    
  \item[(\textit{ii})] Deduza do Ex.~\ref{Q:deB-E}(\textit{ii})
    que~$B(d,\epsilon)$ (com~$d$ e~$\epsilon$ apropriados) contém subgrafos
    finitos~$G$ com~$\chi(G)\geq k$ e~$\og(G)\geq2\ell+1$.
    
  \end{enumerate}
  \datedue{2/10/2007}
  
\item (Continuação do Ex.~\ref{Q:Erdos-Hajnal}) Nesta questão, dizemos que um
  grafo~$G$ tem a propriedade~$P(c)$ se todo subgrafo~$H$ de~$G$ é tal
  que~$\alpha(H)\geq c|V(H)|$.
  \begin{enumerate}
  \item[(\textit{i})]Mostre que se~$G$ é tal que~$\chi(G)=k$, então~$G$ tem a
    propriedade~$P(1/k)$.  \datedue{2/10/2007}
  \item[(\textit{ii})]Mostre que se~$G$ tem a propriedade~$P(1/2)$,
    então~$\chi(G)\leq2$.  \datedue{2/10/2007}
  \item[(\textit{iii})][Para meditar] Mostre que para todo inteiro~$k$
    e~$0<c<1/2$, existe um grafo~$G$ que tem a propriedade~$P(c)$
    mas~$\chi(G)\geq k$.  \sugestao{Mostre que~$B(d,\epsilon)$ com~$d$
      e~$\epsilon$ apropriados é (basicamente) um tal grafo.  Use
    Ex.~\ref{Q:Erdos-Hajnal}(\textit{ii}).} 
  \end{enumerate}
  \datedue{2/10/2007}
  
\item\label{Q:Galois} Fixe um corpo~$F$ e um conjunto~$U$ de polinômios com
  coeficientes em~$F$ nas indeterminadas~$\bfX=(X_1,\dots,X_n)$: $U\subset
  F[\bfX]$.  Para~$A\subset U$, pomos $V(A)=\{\bfx\in F^n\:a(\bfx)=0\text{
    para todo }a\in A\}$.  Claramente, $V(A)=\bigcap_{a\in A}V(a)$, onde
  escrevemos~$V(a)$ para~$V(\{a\})$.  Dado~$X\subset F^n$, seja~$I(X)=\{a\in
  U\:a(\bfx)=0\text{ para todo }\bfx\in X\}$.  Prove que o par~$(V,I)$
  constitui uma \textit{conexão de Galois} entre as partes de~$U$ e as partes
  de~$F^n$, isto é, prove as seguintes afirmações:
  \begin{enumerate}
  \item[(\textit{i})] Tanto~$V$ quanto~$I$ \textit{invertem} a ordem: para
    todo~$A\subset B$, temos~$V(A)\supset V(B)$ e analogamente para~$I$. 

  \item[(\textit{ii})] Para todo~$A\subset U$ temos~$I(V(A))\supset A$ e para
    todo~$X\subset F^n$ temos~$V(I(X))\supset X$.
  \end{enumerate}
  Deduza de~(\textit{i}) e~(\textit{ii}) que vale o seguinte.
  \begin{enumerate}
  \item[(\textit{iii})] Sejam~$\im V=\{V(A)\:A\subset U\}$ e~$\im
    I=\{I(X)\:X\subset F^n\}$.  Prove que~$V$ é uma bijeção de~$\im I$ em~$\im
    V$.  
  \end{enumerate}
  Qual é a inversa de~$V\:\im I\to\im V$?  \datedue{16/10/2007}
  
\item (Continuação do Ex.~\ref{Q:Galois}) Dizemos que~$b\in U$
  \textit{depende} de~$A$ se~$V(b)\supset V(A)$.  O \textit{fecho} de~$A$
  em~$U$ é~$\bar A=\{b\in U\:\text{ $b$ depende de~$A$}\}$.  Um conjunto~$A$ é
  \textit{fechado} em~$U$ se~$\bar A=A$.  Prove as seguintes asserções:
  \begin{enumerate}
  \item[(\textit{i})] A operação~$A\mapsto\bar A$ é uma \textit{operação de
      fecho}, isto é, (a)~$A\subset\bar A$ para todo~$A$, (b)~para
    quaisquer~$A$ e~$B$ com~$A\subset B$, temos~$\bar A\subset\bar B$, e
    (c)~$\bar{\bar A}=\bar A$.

  \item[(\textit{ii})] Seja~$(A_\lambda)_{\lambda\in\Lambda}$ uma família de
    fechados em~$U$.  Então~$\bigcap_{\lambda\in\Lambda}A_\lambda$ é um fechado.

%  \item[(\textit{iii})] Sejam~$A_1,\dots,A_n$ fechados em~$U$.  Prove que
%    $A_1\cup\dots\cup A_n$ é fechado em~$U$.  \textbf{[Wrong?!]}
    
  \end{enumerate}
  Identifique os fechados de~$U$ em termos das aplicações~$V$ e~$I$ (veja
  Ex.~\ref{Q:Galois}).  \datedue{16/10/2007}
  
\item Considere os padrões de zeros~$\bfdelta(\bff(\bfx))\in\{0,*\}^m$
  ($\bfx\in F^n$) de uma seqüência de polinômios~$\bff=(f_1,\dots,f_m)$ sobre
  um corpo~$F$ nas indeterminadas~$\bfX=(X_1,\dots,X_n)$.  Seja~$\cZ_F(\bff)$
  o conjunto de tais padrões e~$Z_F(\bff)=|\cZ_F(\bff)|$.
  \begin{enumerate}
  \item[(\textit{i})] Seja~$U=\{f_1,\dots,f_m\}$.  Exiba uma injeção
    de~$\cZ_F(\bff)$ nos fechados de~$U$.
    
  \item[(\textit{ii})] Dizemos que~$A$ \textit{gera} um fechado~$B$ de~$U$
    se~$\bar A=B$.  Suponha agora que os~$f_i$ em~$U$ são todos lineares, isto
    é, são da forma
    $f_i(\bfX)=\<\bfa_i,\bfX\>+b_i=a_{i1}X_1+\dots+a_{in}X_n+b_i$.  Prove que
    todo fechado~$B\subset U$ com~$B\neq U$ admite um conjunto gerador~$A$
    com~$|A|\leq n$.
    
  \item[(\textit{iii})] Conclua que, no caso em que os~$f_i$ são lineares,
    temos
    \begin{equation}
      \label{eq:linear_Warren.1}
      Z_F(\bff)\leq1+\sum_{j=0}^n{m\choose j}.
    \end{equation}

  \item[(\textit{iv})] Altere levemente o argumento acima para provar
    que~\eqref{eq:linear_Warren.1} pode ser melhorado para 
    \begin{equation}
      \label{eq:linear_Warren.2}
      Z_F(\bff)\leq\sum_{j=0}^n{m\choose j}.
    \end{equation}

  \end{enumerate}\datedue{16/10/2007}
  
\item Prove que a vasta maioria das funções booleanas de $n$~variáveis exige
  circuitos booleanos com~$\Omega(2^n/n)$ portas para sua representação (isto
  é, existe~$c>0$ tal que, para~$n\geq n_0$, o número necessário de portas é
  maior que~$c2^n/n$).  \datedue{23/10/2007}
  
\item Seja~$M(x_1,\dots,x_n)$ a função booleana `da maioria', dada por
  \begin{equation}
    \label{eq:Maj}
    M(x_1,\dots,x_n)=
    \begin{cases}
      0&\text{se~$\sum_{1\leq i\leq n}x_i<n/2$}\\
      1&\text{se~$\sum_{1\leq i\leq n}x_i\geq n/2$}.
    \end{cases}
  \end{equation}
  \begin{enumerate}
  \item[(\textit{i})] Prove que existe um circuito com~$O(n^2)$ portas que
    calcula~$M$. \datedue{23/10/2007}
    
  \item[(\textit{ii})] Prove que existe um circuito com~$O(n\log n)$ portas
    que calcula~$M$. \datedue{23/10/2007}
    
  \item[(\textit{ii})] [Desafio] Prove que existe um circuito com~$O(n)$
    portas que calcula~$M$.
  \end{enumerate}
  
\item Neste problema, o termo \textit{$\Delta$-sistema} significa um
  $\Delta$-sistema com $3$~membros (isto é, um girassol com três pétalas).
  Seja~$\phi(n)$ o menor inteiro tal que toda família~$\cF$ de $n$-conjuntos
  (conjuntos com $n$~elementos) com~$|\cF|>\phi(n)$ contém um
  $\Delta$-sistema.  Ademais, seja~$\gamma(n)$ o menor inteiro tal que toda
  família \textit{intersectante} de $n$-conjuntos com~$|\cF|>\gamma(n)$ contém
  um $\Delta$-sistema.
  \begin{enumerate}
  \item[(\textit{i})]Prove que
    \begin{equation}
      \label{eq:SFi}
      \phi(n)\leq n\phi(n-1)+\gamma(n)
    \end{equation}
    para todo~$n>1$.
    
  \item[(\textit{ii})]Seja~$\cE$ um sistema intersectante de $n$-conjuntos
    com~$\gamma=\gamma(n)$ membros que não contém um $\Delta$-sistema.  Seja
    \begin{multline}
      \label{eq:ave_int}\qquad
      t=\Ave\{|E\cap E'|\:E,\,E'\in\cE,\;E\neq E'\}\\
      ={\gamma\choose2}^{-1}\sum\{|E\cap E'|\:E,\,E'\in\cE,\;E\neq E'\}
    \end{multline}
    a média das cardinalidades das interseções de pares de membros distintos
    de~$\cE$.  Prove que
    \begin{equation}
      \label{eq:SFii}
      \gamma\leq{n\over t}\phi(n-1).
    \end{equation}
    \hint{Prove por um argumento de média que existe~$E_0\in\cE$ para o
      qual~$\Ave_{E\neq E_0}|E_0\cap E|\geq t$.  Também por um argumento de
      média, prove que existe~$x\in E_0$ tal que~$\deg(x)\geq t\gamma/n$.}
    
  \item[(\textit{iii})]  Prove que
    \begin{equation}
      \label{eq:SFiii}
      \gamma(n)\leq t\phi(n-1)+(n-1)^2\phi(n-2).
    \end{equation}
    \hint{Seja~$\cE$ como em~(\textit{ii}) acima.  Mostre por um argumento de
      média que existem~$E_1$ e~$E_2\in\cE$ tais que~$|E_1\cap E_2|\leq t$.
      Considere os~$F$ em~$\cE\setminus\{E_1,E_2\}$.  Para limitar o número
      de~$F$ que são disjuntos de~$I=E_1\cap E_2$, observe
      que~$F\cap(E_i\setminus I)\neq\emptyset$.}

  \item[(\textit{iv})]Deduza que, para uma certa constante~$C$, temos
    \begin{equation}
      \label{eq:SFiv}
      \phi(n)\leq Cn!\(5\over3\)^n.
    \end{equation}
    \observacao{Refinando este argumento, podemos provar que para
      todo~$\epsilon>0$, existe~$C$ para o qual temos~$\phi(n)\leq
      Cn!(1+\epsilon)^n$, isto é, $\phi(n)\leq n!(1+o(1))^n$.}  
  \end{enumerate}
  \datedue{1/11/2007}

\item Fixe um inteiro positivo~$n$.  Nesta questão, escrevemos~$\{x<y\}$ para
  um par de inteiros~$\{x,y\}$ com~$x<y$.  Considere o grafo~$\Gamma=\Gamma_n$
  cujos vértices são os pares~$\{x,y\}\subset[n]$ e cujas arestas são todos os
  pares de vértices da forma
  $$
  \big\{\{x<y\},\{y<z\}\big\}.
  $$
  ($\Gamma=\Gamma_n$ tem~${n\choose2}$ vértices e~${n\choose3}$ arestas.)
  Observe que~$\Gamma$ não tem triângulos.  Mostre que, dado qualquer
  inteiro~$k$, existe~$n_0$ tal que se~$n\geq n_0$, então o número cromático
  de~$\Gamma=\Gamma_n$ é pelo menos~$k$.  \datedue{4/12/2007}
  
\item Suponha que
  \begin{equation}
    \label{eq:p_def}
    p=p(n)={\log n+f\over n}, 
  \end{equation}
  onde~$f=f(n)$, e considere o grafo aleatório~$G(n,p)$.  Prove que as
  seguintes asserções valem para quase todo~$G=G(n,p)$.
  \begin{enumerate}
  \item[(\textit{i})] Se~$f=f(n)\to\infty$, então~$G$ não tem vértices isolados.
  \item[(\textit{ii})] Se~$f=f(n)\to-\infty$ e~$|f|\leq\log n$, então~$G$ tem
    vértices isolados.  De fato, (*)~\textsl{o número de vértices
      isolados~$X=X(G)$ em~$G$ satisfaz~$X\sim\exp\{-f\}$}.  [Inicialmente,
    reescreva~(*) de forma mais explícita.]
  \item[(\textit{iii})] O que você consegue dizer sobre o caso em
    que~$f=f(n)\to f_0$ para alguma contante~$f_0$?  [Aqui você pode apenas
    conjecturar o resultado; não é necessário provar sua conjectura.]
  \end{enumerate}
  \datedue{4/12/2007}
  
\item Prove que~$p_0=p_0(n)=n^{-2/3}$ é a função limiar para a existência
  de~$K^4$ em~$G(n,p)$.  \datedue{4/12/2007}

\def\PTAS{\textsc{PTAS}}
\def\MAXCUT{\textsc{MaxCut}}

\item Desenvolva um \PTAS\ para o \MAXCUT\ restrito a grafos densos (isto é,
  suponha que temos uma constante~$c>0$ fixa e restringimos as entradas de
  \MAXCUT\ a grafos~$G=G^n$ com~$\geq cn^2$ arestas).  \datedue{4/12/2007}

\item{}[Desafio] Para cada~$n\geq1$, defina o grafo~$G_n$ com conjunto de
  vértices $V_n=\cP([n])=2^{[n]}$ e com conjunto de arestas~$E_n$ dado
  por~$\{x,y\}\in E_n$ se e só se~$|x\cap y|$ é ímpar.  Mostre que, para
  todo~$S\subset V_n$, temos
  \begin{equation}
    \label{eq:Q_1}
    |E(G[S])|={1\over2}{|S|\choose2}+o(N^2),
  \end{equation}
  onde~$N=2^n=|V_n|$.  %\datedue{4/12/2007}
  
\item Prove que, para todo~$\epsilon>0$, existe~$\ell(\epsilon)$ para o qual
  vale a seguinte afirmação.  Suponha que~$G=G^n$ seja tal
  que~$\chi(G-F)\geq3$ para todo~$F\subset E(G)$
  com~$|F|\leq\epsilon{n\choose2}$.  Então~$G$ contém um circuito ímpar de
  comprimento~$\leq\ell(\epsilon)$.  \datedue{4/12/2007}

\end{enumerate}  
 
\end{document}

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