%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <2010-11-26 14:52:38 yoshi>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno,a4paper]{amsart}

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

%\usepackage{refcheck}
\usepackage{srcltx}

\usepackage{fullpage}
\usepackage{setspace}

\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\aut{\mathop{{\rm aut}}\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[MAC320 Teoria dos grafos]{Segunda Prova de Introdução 
  à Teoria dos Grafos\\2{\tiny o.} semestre de 2010}
\date{Versão de \today\ (versão final)} 
\maketitle
\footskip=20pt

\vspace{-\medskipamount}
\noindent{\bf Instruções:}
\begin{enumerate}\small
\item Esta prova é individual.
\item Você deve fazer todas as questões.
\item Procure fazer as questões sem nenhuma consulta.  Caso você não
  consiga resolver uma questão e você consulte algum material, você
  deve citar em detalhe qual material foi consultado.
\item A qualidade da redação será levada em conta para a atribuição de
  nota. 
\item Asserções imprecisas valem pouco.  Também valem pouco asserções
  corretas não-triviais sem justificativa: Justifique suas asserções (dentro
  do razoável)!
\end{enumerate}

\smallskip
\onehalfspacing

%\textbf{Faça duas questões!}\medskip

\begin{enumerate}
\thispagestyle{empty}  

\item{} Dizemos que um grafo~$G$ é \textit{$(a,b)$-regular} se
  $a\leq\delta(G)\leq\Delta(G)\leq b$.  Suponha que $1\leq k\leq s\leq
  r$.  Prove que todo grafo $(r-k,r)$-regular tem um \textit{fator}
  $(s-k,s)$-regular, isto é, um subgrafo gerador que é
  $(s-k,s)$-regular.  \sugestao{Suponha~$s=r-1$.  Considere um fator
    $(r-k,r)$-regular minimal.  Note que, neste fator, não há dois
    vértices de grau~$r$ adjacentes.  Remova um conjunto de arestas
    independentes cobrindo os vértices de grau~$r$.}

\item{} Sejam~$G$ um grafo e~$x$ e~$y$ dois vértices de~$G$.  Suponha
  que a distância~$d_G(x,y)$ entre~$x$ e~$y$ em~$G$ é~$t\geq2$.  Seja
  \begin{equation}
    \label{eq:tau_t(x,y)_def}
    \tau_t(x,y)=\min|X|,
  \end{equation}
  onde o mínimo é tomado sobre os conjuntos~$X\subset
  V(G)\setminus\{x,y\}$ tais que, se~$G'=G-X$, então~$d_{G'}(x,y)>t$
  (isto é, a remoção de~$X$ aumenta a distância entre~$x$ e~$y$).
  Seja 
  \begin{equation}
    \label{eq:nu_t(x,y)_def}
    \nu_t(x,y)=\max|\cF|,
  \end{equation}
  onde o máximo é tomado sobre todas as coleções~$\cF$ de $x$--$y$
  caminhos \textit{mínimos}, dois a dois internamente disjuntos (isto
  é, conjuntos~$\cF$ constituídos de $x$--$y$ caminhos de
  comprimento~$t$, tais que se~$P$ e~$P'\in\cF$, então~$V(P)\cap
  V(P')=\{x,y\}$).  Prove que
  \begin{equation}
    \label{eq:minmax}
    \tau_t(x,y)=\nu_t(x,y).
  \end{equation}
  \sugestao{Estude a versão do teorema de Menger para grafos
    dirigidos.}

\item{} Sejam~$I_0,I_1,\dots,I_{rs}$ intervalos da reta real~$\RR$,
  onde~$r$ e~$s\geq1$ são inteiros.  Prove que~$r+1$ desses intervalos
  têm interseção (total) não-vazia, ou~$s+1$ desses intervalos são
  dois a dois disjuntos.

\item Seja~$P=(X,\leq)$ uma ordem parcial, com~$X$ infinito
  enumerável.  Suponha que~$P$ não contém anticadeias com mais de~$t$
  elementos.  Mostre que~$X$ pode ser escrito como a união de~$t$
  cadeias em~$P$.  \sugestao{Deduza este resultado do teorema de
    Dilworth, provado para ordens parciais finitas.}

\item Seja~$G$ um grafo bipartido com bipartição~$V(G)=A\cup B$ e
  suponha~$a=|A|\leq b=|B|$.  Suponha que~$G$ não contém circuitos de
  comprimento~$4$.
  \begin{enumerate}
  \item[(\textit{i})] Contando triplas da forma~$(x,v,w)\in A\times
    B\times B$ com~$\{x,v\}$, $\{x,w\}\in E(G)$, prove que
    \begin{equation}
      \label{eq:cherries}
      \sum_{x\in A}{d(x)\choose2}\leq{b\choose2}.
    \end{equation}
  \item[(\textit{ii})] Deduza que~$e(G)\leq\max\{2b,a\sqrt{2b}\}$. 
  \end{enumerate}

\item{} Seja~$f(n)$ o maior~$r$ para o qual existem
  inteiros~$1<s_1<s_2<\dots<s_r\leq n$ tais que, para todo~$i$, $j$,
  $k$ e~$l$, se~$s_is_j=s_ks_l$, então~$\{i,j\}=\{k,l\}$.
  Seja~$\pi(n)$ o número de primos menores ou iguais a~$n$.
  \begin{itemize}
  \item[(\textit{i})]Prove que~$f(n)\geq\pi(n)$.
  \item[(\textit{ii})]Prove que~$f(n)\leq\pi(n)+O(n^{7/8})$.
    \sugestao{Seja~$t=\lfloor n^{2/3}\rfloor$.  Sejam~$A=[t]$
      e~$B'=[t]\cup P$, onde~$P$ é o conjunto dos primos~$\leq n$.
      Seja~$B$ uma ``cópia'' de~$B'$, disjunta de~$A$ (formalmente,
      poderíamos definir~$B$ como sendo~$B'\times\{1\}$, mas não
      seguiremos este formalismo).  Prove que todo inteiro~$m\leq n$
      pode ser escrito como~$ab$, com~$a\in A$ e~$b\in B$ e~$a\leq b$.
      Para cada~$s_i$ na seqüência dada, fixe uma representação da
      forma~$a_ib_i$ como acima.  Considere o grafo bipartido~$G$ com
      bipartição~$V(G)=A\cup B$ e conjunto de
      arestas~$E(G)=\big\{\{a_i,b_i\}\:1\leq i\leq r\big\}$.  Prove
      que~$G$ não contém circuitos de comprimento~$4$.
      Sejam~$B_1=\{b\:1\leq b\leq n^{1/2}\}$, $B_2=\{b\:n^{1/2}<b\leq
      n^{3/4}\}$ e $B_3=\{b\:n^{3/4}<b\leq n\}$.  Seja~$E_i$
      ($i\in\{1,2,3\}$) o conjunto de arestas de~$G$ que tem uma ponta
      em~$B_i$.  Prove cotas superiores para a cardinalidade dos~$E_i$
      separadamente, usando o fato de~$G$ ser livre de~$C^4$.
      Observamos que um argumento mais cuidadoso fornece uma cota
      melhor, a saber, $f(n)\leq\pi(n)+O(n^{3/4})$.}
 \end{itemize}
  
\item{} Prove que existe um grafo~$G$ (finito) com cintura pelo
  menos~$2010$ e grau mínimo~$2010$.

% \item{} Seja~$G$ um grafo de ordem~$n$ com~$m$ arestas. 
%   \begin{enumerate}
%   \item[(\textit{i})]Suponha~$t\geq3$ e que~$m\geq2^{t-3}n$.  Prove
%     que~$G$ tem~$K^t$ como menor.  \sugestao{...}
%   \item[(\textit{ii})]Seja~$H$ um grafo com~$k$ arestas e suponha
%     que~$m\geq2^kn$.  Prove que~$G$ contém uma subdivisão de~$F$.
%     \sugestao{...} 
%   \end{enumerate}
  
% \item{} (large angle problem?)

\end{enumerate}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% eval: (iso-accents-mode t)
%%% eval: (auto-fill-mode t)
%%% eval: (LaTeX-math-mode t)
%%% TeX-master: t
%%% End: