%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Prova de MAC5827 Topicos de Matemática Discreta                    %
% 2o. semestre de 2002                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Thursday 12 Dec 2002 01:33:18pm BRST yoshi@erdos.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

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

%\usepackage{refcheck}

\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\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 2002} 
\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 12:00 do dia 16/12/2002, na secretaria do MAC.  Faça quantas
questões quanto você conseguir; minha expectativa é que você consiga
basicamente fazer todas as~6 questões.  Após a entrega, farei uma pequena
entrevista com cada aluno que fizer a prova.

\bigskip

\begin{enumerate}
  
\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 Para todo natural~$n>1$, seja
  \begin{equation}
    \label{eq:Omega_def}
    \Omega(n)=\sum_ie_i,
  \end{equation}
  onde~$n=p_1^{e_1}\dots p_k^{e_k}$ é a fatoração de~$n$ em primos distintos.
  Isto é, $\Omega(n)$ é o número de primos que dividem~$n$, contados com
  multiplicidade.  Prove que
  \begin{equation}
    \label{eq:HR}
    \Omega(n)=(1+o(1))\log\log N
  \end{equation}
  para quase todo~$n$ escolhido uniformemente ao acaso em~$[N]$.
  
\item Sejam dados um natural~$n$ e um real~$\epsilon>0$.  Seja
  \begin{equation}
    \label{eq:g_def}
    g_\epsilon(n)=\sup|S|,
  \end{equation}
  onde o supremo é tomado sobre todos os~$S\subset\RR^n$ tais que para
  todo~$x\in S$, temos~$\|x\|=1$, e para todo~$x$ e~$y\in S$ com~$x\neq y$
  temos~$|\<x,y\>|\leq\epsilon$.
  \begin{enumerate}
  \item[(\textit{i})]Prove que~$g_\epsilon(n)<\infty$ para todo~$n\geq1$
    e~$\epsilon<1$.
  \item[(\textit{ii})]Mais ainda, prove
    que~$\limsup_{n\to\infty}g_\epsilon(n)^{1/n}<\infty$ se~$\epsilon<1$. 
  \item[(\textit{iii})]Prove que para qualquer~$\epsilon>0$ existem~$n_0$
    e~$\delta>0$ tais que
  \begin{equation}
    \label{eq:g_exponential}
    g_\epsilon(n)\geq(1+\delta)^n
  \end{equation}
  para todo~$n\geq n_0$.

  \end{enumerate}
  
\item Prove que quase todo grafo~$G^n$ é conexo.
  
\item Dizemos que um grafo é \textit{$k$-universal} se ele contém todos os
  grafos com~$k$ vértices como subgrafos induzidos.  Ademais, dizemos que um
  grafo~$G$ satisfaz a propriedade~$P(a,b)$ se, para toda $a$-upla
  $x_1,\dots,x_a\in V(G)$ e toda $b$-upla~$y_1,\dots,y_b\in V(G)$ de vértices
  distintos de~$G$, existe um vértice~$z$ em~$G$, diferente de todos os~$x_i$
  e~$y_j$, tal que~$z$ é adjacente a todos os~$x_i$ ($1\leq i\leq a$) e não é
  adjacente a nenhum~$y_j$ ($1\leq j\leq b$).
  \begin{enumerate}
  \item[(\textit{i})]Prove que se~$G$ satisfaz~$P(k-1,k-1)$, então~$G$
    é~$k$-universal. 
  \item[(\textit{ii})]Prove que quase todo grafo~$G^n$ é $k$-universal para
  todo~$k$ fixo.
  \end{enumerate}

\item Vimos dois teoremas de Roth.  A grosso modo, estes resultados podem ser
  enunciados da seguinte forma: (\textit{i})~Para qualquer~$A\subset[N]$,
  existe uma progressão aritmética~$P\subset[N]$ para o qual a discrepância
  $$
  \big||A\cap P|-\eta|P|\big|,
  $$
  é `grande', onde~$\eta=|A|/N$.  (\textit{ii})~Para qualquer
  conjunto~$A\subset[N]$ com~$|A|/N\geq\eta$, onde~$\eta>0$ é uma constante
  positiva, se~$N\geq N_0(\eta)$, então~$A$ contém uma progressão aritmética
  com três elementos.  Escreva a prova destes dois resultados em um único
  texto, de forma organizada, destacando os princípios comuns e as
  tecnicalidades específicas de cada uma das
  demonstrações.

\end{enumerate}  
 
\end{document}

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

