%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC320  Introdução à Teoria dos Grafos               %
% 2o. semestre de 2010                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Friday 26 Nov 2010 11:11:00am BRST yoshi@delta-2.local>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,a4paper,reqno]{amsart}

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

%\usepackage{refcheck}
%\usepackage{srcltx}
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{hyperref}

\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\comp{^{\rm c}}

\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[MAC320 Teoria dos Grafos]{%
  {\sl Exercícios}\\\medskip
  Introdução à Teoria dos Grafos\\\medskip
  2{\tiny o.} semestre de 2010}  
\date{Versão de \today}
\maketitle
\pagestyle{plain}
\footskip=25pt

\onehalfspace 

\noindent
\textbf{Instruções:}
\bgroup\small
\begin{enumerate}
\item Os problemas e exercícios com data de entrega devem ser
  resolvidos e entregues.  Estes exercícios farão parte de sua
  avaliação.
\item A entrega dos exercícios deve ser feita no começo da aula (as
  datas de entrega serão datas de aula).  

\item O monitor levará em conta não apenas a correção de sua solução,
  mas também a apresentação (soluções mal escritas valerão menos).

\item Você deve fazer os demais problemas e exercícios, mas não é
  necessário entregar suas soluções.

\item Não deixe de atacar os desafios, mas eles podem resistir às suas
  investidas mais seriamente que os problemas.  

\item A entrega de soluções de problemas e desafios sem data de
  entrega pode contribuir em sua avaliação.

\end{enumerate}
\egroup

\bigskip
\noindent\textbf{Exercícios, problemas e desafios:}
\begin{enumerate}
  
\item\label{Q:1} Seja~$X$ um conjunto.  Mostre que não existe uma
  função sobrejetora~$f\:X\to\cP(X)$.  \sugestao{Considere~$S=\{x\in
    X\:x\notin f(x)\}$.}  \datedue{2/9/2010}
  
\item (Problema) Suponha que~$X$ e~$Y$ sejam conjuntos e que existam
  funções injetoras~$f\:X\to Y$ e~$g\:Y\to X$.  Prove que existe uma
  bijeção~$h\:X\to Y$.

\item\label{eq:F_twin} Sejam~$G$ e~$H$ dois grafos.  Suponha que~$G$
  seja isomorfo a um subgrafo de~$H$ e~$H$ seja isomorfo a um subgrafo
  de~$G$.  Mostre que, se os grafos~$G$ e~$H$ são finitos, então~$G$ é
  isomorfo a~$H$.  \datedue{2/9/2010}

\item Mostre que, se omitimos a hipótese de que~$G$ e~$H$ são grafos
  finitos no Exercício~\ref{eq:F_twin}, então a conclusão daquele
  exercício é falsa.

\item (Problema) Seja~$X$ um conjunto e denotemos
  por~$\cP^{<\infty}(X)$ o conjunto dos subconjuntos finitos de~$X$.
  Seja~$f\:\omega=\{0,1,2,\dots\}\to\cP^{<\infty}(X)$ uma função e
  suponha que, para todo~$n\in\omega$, existe uma
  função~$g_n\:n=\{0,\dots,n-1\}\to X$ tal que
  \begin{enumerate}
  \item[(\textit{a})]$g_n(i)\in f(i)$ para todo~$i\in n$ 
  \end{enumerate}
  e
  \begin{enumerate}
  \item[(\textit{b})]os $g_n(i)$ ($i\in n$) são todos distintos.
  \end{enumerate}
  Prove que existe uma função~$g\:\omega\to X$ tal que
  (\textit{a})~$g(i)\in f(i)$ para todo~$i\in\omega$ e (\textit{b})~os
  $g(i)$ ($i\in\omega$) são todos distintos.  Se removemos a hipótese
  de que~$f(i)$ é finito para todo~$i$, o resultado ainda vale?
  \datedue{16/9/2010}

\item Suponha que uma função
  $A\:\omega\times\omega\to\omega^+=\{0,1,\dots,\omega\}$ é tal que
  \begin{equation}
    \label{eq:Ack_def}
    A(m,n)=
    \begin{cases}
      n+1        &\text{se~$m=0$}\\
      A(m-1,1)   &\text{se~$m>0$ e~$n=0$}\\
      A(m-1,A(m,n-1))  &\text{se~$m>0$ e~$n>0$}.
    \end{cases}
  \end{equation}
  Calcule~$A(4,3)$.  Prove que~$A(m,n)<\omega$ para todo~$m$ e~$n$
  usando um argumento de indução (descreva sua indução
  cuidadosamente).  \datedue{2/9/2010}

% \def\gimp{g_{\text{imp}}}
% \item A \textit{cintura} ímpar~$\gimp(G)$ de um grafo~$G$ é
%   \begin{equation}
%     \label{eq:gimp_def}
%     \gimp(G)=\min\{|C|\:\text{$C$ é um circuito de comprimento ímpar
%       de~$G$}\}.
%   \end{equation}
%   No caso em que~$G$ não contém circuitos ímpares, convencionamos
%   que~$\gimp(G)=\infty$.  

\item (Desafio) Sejam~$\ell$ e~$\delta$ inteiros.  Prove que existe
  um grafo~$G$ com~$g(G)\geq\ell$ e~$\delta(G)\geq\delta$.  

\item Encontre um grafo~$G$ com~$g(G)\geq5$ e~$\delta(G)\geq3$ com
  o menor número de vértices possível.  Não deixe de provar que seu
  grafo de fato tem o menor número de vértices possível.
  \datedue{16/9/2010} 

\def\bard{\bar d}
\item Seja~$G$ com grafo com grau médio~$\bard(G)\geq4+10^{-10}$.
  Prove uma cota inferior para a ordem de~$G$ que é exponencial na
  cintura de~$G$, isto é, prove que~$|G|\geq\alpha c^{g(G)}$
  se~$g(G)\geq g_0$, onde~$\alpha$, $c$ e~$g_0$ são constantes
  absolutas com~$\alpha>0$ e~$c>1$.  Não use o teorema de Alon, Hoory
  e Linial.  Prove que, usando o teorema daqueles autores, podemos
  enfraquecer a hipótese para~$\bard(G)\geq2+10^{-10}$.  Prove que
  tais cotas exponenciais não valem se supomos apenas~$\bard(G)\geq2$.

\item Seja~$G$ um grafo $2$-conexo.  Prove que quaisquer dois vértices
  de~$G$ estão contidos em um circuito de~$G$.  \datedue{16/9/2010}
  \sugestao{Fixe~$x$ e~$y\in V(G)$.  Prove que~$x$ pertence a um
    circuito de~$G$.  Dentre todos os circuitos~$C$ de~$G$ que
    contêm~$x$, considere um que minimiza~$d(y,C)=\min\{d(y,z)\:z\in
    V(C)\}$.}

\item (Decomposição em orelhas) Seja~$G$ um grafo $2$-conexo.  Prove
  que existe uma seqüência de subgrafos $H_0\subset
  H_1\subset\dots\subset H_k$ de~$G$ tal que (\textit{i})~$H_0=K^2$,
  (\textit{ii})~$H_k=G$, e (\textit{iii})~$H_i=H_{i-1}+P_i$ para
  todo~$1\leq i\leq k$, onde~$P_i$ é um $H_{i-1}$-caminho.  (Dizemos
  que~$H_i$ é obtido de~$H_{i-1}$ pela adição da
  \textit{orelha}~$P_i$.)  \datedue{16/9/2010}

\item Sejam~$G_i=(V_i,E_i)$ ($i\in\{1,2\}$) dois grafos.  Definimos o
  \textit{produto categórico}~$G_1\times G_2$ de~$G_1$ e~$G_2$ como
  sendo o grafo sobre~$V_1\times V_2$ em que~$(x_1,x_2)$ é adjacente
  a~$(y_1,y_2)$ se e só se~$\{x_1,y_1\}\in E_1$ e~$\{x_2,y_2\}\in
  E_2$.  Prove que~$G_1\times G_2$ é conexo se e só se cada~$G_i$ é
  conexo e pelo menos um dos~$G_i$ contém um circuito de comprimento
  ímpar.  \datedue{21/9/2010}

\item Seja~$G$ um grafo.  Defina a relação~$\sim$ sobre~$E(G)$
  colocando~$e\sim f$ se e só se~$e=f$ ou existe um circuito de~$G$
  que contém ambos~$e$ e~$f$.  Mostre que a relação~$\sim$ é uma
  relação de equivalência.  \datedue{21/9/2010}

\def\bard{\bar d}
\item
  \begin{itemize}
  \item[(\textit{i})] Seja~$G$ um grafo com grau
    médio~$\bard(G)\geq2$.  Mostre que~$G$ contém um subgrafo
    $2$-conexo.
 \item[(\textit{ii})] Exiba um grafo~$G$ com grau médio~$\bard(G)\geq3$
    que não contém um subgrafo $3$-conexo.
  \end{itemize}
  \datedue{23/9/2010}
  
\item Seja~$G$ um grafo com grau médio~$\bard(G)\geq4$ e
  cintura~$g(G)\geq5$.  Mostre que~$G$ contém um subgrafo $3$-conexo.
  \sugestao{Considere subgrafos~$H$ de~$G$ satisfazendo~$|H|\geq4$
    e~$e(H)\geq2(|H|-2)$.  Siga a prova do Teorema de Mader, visto em
    sala.}  \datedue{23/9/2010}

\item Seja~$T$ uma árvore com pelo menos uma aresta e sem vértices de
  grau~$2$.  Prove que mais da metade dos vértices de~$T$ são folhas
  (vértices de grau~$1$).  \datedue{19/10/2010}

\def\cT{\mathcal{T}}
\item\label{Q:Helly}
  Seja~$G$ um grafo e seja~$\cT$ uma coleção não-vazia de
  subárvores não-vazias de~$G$.  Seja~$\nu(\cT)=\max|\cT'|$, onde o
  máximo é tomado sobre todas as subcoleções~$\cT'\subset\cT$ de~$\cT$
  constituídas de árvores duas-a-duas disjuntas nos vértices.  Seja
  também~$\tau(\cT)=\min|C|$, onde o mínimo é tomado sobre todos os
  conjuntos~$C\subset V(G)$ que \textit{cobrem}~$\cT$, isto é,
  conjuntos~$C$ com~$C\cap V(T)\neq\emptyset$ para todo~$T\in\cT$.
  \begin{enumerate}
  \item[(\textit{i})]Prove que, para qualquer grafo~$G$,
    temos~$\nu(\cT)\leq\tau(\cT)$.
  \item[(\textit{ii})]Suponha agora que~$G$ é uma árvore.  Prove
    que~$\nu(\cT)=\tau(\cT)$.  \sugestao{Remova uma folha de~$G$.
      Considere o caso~$\nu(\cT)=1$ primeiro.}
  \end{enumerate}
  \datedue{19/10/2010}

\item (Continuação do Ex.~\ref{Q:Helly}) Sejam~$G$ e~$\cT$ como no
  Exercício~\ref{Q:Helly}.  
  \begin{enumerate}
  \item[(\textit{i})]Dê um exemplo em que temos~$\nu(\cT)=1$
    e~$\tau(\cT)>2010$.
  \item[(\textit{ii})]Suponha agora que~$\cT$ é constituído de árvores
    com no máximo~$t$ vértices cada.  Prove
    que~$\nu(\cT)\leq\tau(\cT)\leq t\nu(\cT)$.
  \end{enumerate}
  \datedue{19/10/2010}

\item Seja~$G$ um grafo.
  \begin{enumerate}
  \item[(\textit{i})]Mostre que~$G$ contém um subgrafo gerador
    bipartido~$B$ com~$\delta(B)\geq\delta(G)/2$.
  \item[(\textit{ii})]Mostre que~$G$ contém um subgrafo 
    bipartido~$B$ com~$\delta(B)\geq\bard(G)/4$, onde~$\bard(G)$  é o
    grau médio~$2|E(G)|/|V(G)|$ de~$G$.
  \end{enumerate}
  \datedue{19/10/2010}

\item Seja~$\cT(3,k)$ a classe das árvores~$T$ com grau
  máximo~$\Delta(T)\leq3$ que contêm no máximo~$k$ vértices de
  grau~$3$.  Fixe um inteiro~$k$ e suponha que~$T_1,T_2,\dots$ seja
  uma seqüência infinita de membros de~$\cT(3,k)$.  Mostre que existem
  índices~$j>i$ com~$T_j$ uma subdivisão de~$T_i$.
  \datedue{21/10/2010}

\item Prove que as seguintes duas asserções são equivalentes para um
  grafo~$G$.  Como de usual, $K^5$ é o grafo completo de ordem~$5$
  e~$K^{3,3}=K(3,3)$ é o grafo bipartido completo com ambas as partes
  de cardinalidade~$3$.
  \begin{enumerate}
  \item[(M)] O grafo~$G$ contém~$K^5$ como menor ou contém~$K(3,3)$
    como menor.
  \item[(T)] O grafo~$G$ contém uma subdivisão de~$K^5$ 
    ou contém uma subdivisão de~$K(3,3)$.
  \end{enumerate}
%  \datedue{21/10/2010}

\item Seja~$G$ um grafo bipartido com bipartição~$(A,B)$.  Mostre que as três
  asserções abaixo são equivalentes:
  \begin{enumerate}
  \item[(\textit{i})]$G$ é conexo e cada aresta de~$G$ pertence a um
    emparelhamento perfeito.
  \item[(\textit{ii})]$G$ não é o complemento do~$K^2$ e, para cada~$x\in A$
    e~$y\in B$, o grafo~$G-x-y$ tem um emparelhamento perfeito.
  \item[(\textit{iii})]$G$ não é o complemento do~$K^2$, $|A|=|B|$, e, para
    cada~$\emptyset\neq X\subset A$, com~$X\neq A$, temos~$|\Gamma(X)|>|X|$.
  \end{enumerate}
  Os grafos bipartidos~$G$ satisfazendo (\textit{i})--(\textit{iii}) são
  conhecidos como \textit{grafos bipartidos elementares}.
  \datedue{11/11/2010}

\item Seja~$G$ um grafo bipartido com bipartição~$(A,B)$.  Suponha que~$G$ tem
  um emparelhamento perfeito e que todo vértice em~$A$ tem grau pelo
  menos~$k$.  Mostre que~$G$ tem pelo menos~$k!$ emparelhamentos perfeitos.
  \datedue{23/11/2010} 

\item Seja~$\cF\subset2^X$, onde~$X$ é um conjunto finito.  Um
  \textit{sistema de representantes distintos} (SRD) de~$\cF$ é uma
  família~$\{r_F\:F\in\cF\}$ de elementos \textit{distintos} de~$X$,
  indexada por~$\cF$, com~$r_F\in F$ para todo~$F\in\cF$.  
  \begin{enumerate}
  \item[(\textit{i})] Prove que~$\cF$ admite um~SRD se e só se,
    \begin{equation}
      \label{eq:SRD_cond}
      \text{ para todo }\cF'\subset\cF\text{, temos
      }\Big|\bigcup\cF'\Big|\geq|\cF'|.  
    \end{equation}
  \item[(\textit{ii})] Como formulado em~(\textit{i}), restringimo-nos
    a coleções~$\cF$ `sem membros repetidos'.  Decida se esta
    restrição é necessária para o resultado valer.
  \end{enumerate}
  \datedue{23/11/2010} 

\item\label{ex:mod-submod}
  Seja~$V$ um espaço vetorial de dimensão finita~$\dim V=n$.
  \begin{itemize}
  \item[(\textit{i})] Sejam~$U$ e~$W$ dois subespaços de~$V$.
    Seja~$U\wedge W$ o maior subespaço de~$V$ contido em ambos~$U$
    e~$W$ e seja~$U\vee W$ o menor subespaço de~$V$ que contém
    ambos~$U$ e~$W$.  Claramente, $U\wedge W=U\cap W$.
    Descreva~$U\vee W$.  Mostre que vale a seguinte relação de
    \textit{modularidade}:
    \begin{equation}
      \label{eq:dim_mod}
      \dim U\wedge W+\dim U\vee W = \dim U+\dim W.
    \end{equation}

  \item[(\textit{ii})] Dado um conjunto~$S$ de vetores de~$V$
    arbitrário, definimos~$\dim S$ como sendo a dimensão do
    subespaço~$\<S\>$ gerado por~$S$.  Sejam agora~$X$ e~$Y$ dois
    conjuntos de vetores de~$V$.  Mostre que vale a seguinte relação
    de \textit{submodularidade}:
    \begin{equation}
      \label{eq:dim_submod}
      \dim X\cap Y+\dim X\cup Y \leq \dim X+\dim Y.
    \end{equation}

  \end{itemize}

\item (Rado) Seja~$V$ um espaço vetorial de dimensão finita e
  seja~$\cF\subset2^V$ uma família de conjuntos de vetores de~$V$.  Um
  \textit{sistema de representantes linearmente independentes} (SRLI)
  de~$\cF$ é uma família~$\{r_F\:F\in\cF\}$ de vetores
  \textit{linearmente independentes} de~$V$, indexada por~$\cF$,
  com~$r_F\in F$ para todo~$F\in\cF$.  Prove que~$\cF$ admite um~SRLI
  se e só se,
  \begin{equation}
    \label{eq:SRD_cond}
    \text{ para todo }\cF'\subset\cF\text{, temos
    }\dim\bigcup\cF'\geq|\cF'|.  
  \end{equation}
  Aqui, a notação é como no Ex.~\ref{ex:mod-submod}(\textit{ii}).
  \datedue{23/11/2010} 
  \sugestao{Faça uma adaptação da prova do teorema de Hall devido a
    Rado; use a submodularidade dada em~\eqref{eq:dim_submod}.}

\item Seja~$G$ um grafo.  Uma matriz de \textit{incidência}~$M=M_G$
  para~$G$ tem suas linhas indexadas pelos vértices de~$G$ e suas
  colunas indexadas pelas arestas de~$G$.  Cada entrada de~$M$ é~$1$,
  $-1$ ou~$0$.  Fixe uma aresta~$e$ de~$G$ e suponha que~$e=\{x,y\}$.
  A coluna correspondente a~$e$ em~$M$ é toda nula, exceto nas linhas
  correspondetes a~$x$ e~$y$; nessas duas linhas, as entradas são~$-1$
  e~$1$ (tanto faz qual delas é~$1$ e qual é~$-1$).  Fixe uma matriz
  de incidência para~$G$.  Prove as asserções abaixo.
  \begin{itemize}
  \item[(\textit{i})] Seja~$T=E(C)$ o conjunto de arestas de um
    circuito~$C$ de~$G$.  Mostre que as colunas de~$M$ correspondentes
    aos elementos de~$T$ são linearmente dependentes.

  \item[(\textit{ii})] Seja~$S$ um conjunto de colunas linearmente
    dependentes de~$M$ e seja~$T\subset E(G)$ o conjunto de arestas
    de~$G$ que correspondem às colunas em~$S$.  Mostre que existe um
    circuito~$C$ em~$G$ que tem seu conjunto de arestas contido
    em~$T$, isto é, com~$E(C)\subset T$.  

  \item[(\textit{iii})] Dado um conjunto de arestas~$T\subset E(G)$,
    seja~$v(T)$ o número de vértices no grafo~$G[T]$ gerado por~$T$
    em~$G$ e seja~$c(T)$ o número de componentes em~$G[T]$.
    Pomos~$\dim T=\dim S$, onde~$S$ é o conjunto de colunas de~$M$
    associadas às arestas em~$T$ (e~$\dim S$ é como definido no
    Ex.~\ref{ex:mod-submod}(\textit{ii})).  Prove que
    \begin{equation}
      \label{eq:rank_cycle_matroid}
      \dim T = v(T) -c(T).
    \end{equation}
  \end{itemize}

\item Seja~$G$ um grafo e sejam~$H_1,\dots,H_m$ subgrafos de~$G$.  Dê
  uma condição necessária e suficiente para que exista uma
  família~$\{e_i\:1\leq i\leq m\}$ de arestas distintas de~$G$,
  com~$e_i\in E(H_i)$ para todo~$i$, tal que o grafo gerado pelo
  conjunto das arestas~$e_i$ ($1\leq i\leq m$) seja uma floresta.
  \datedue{23/11/2010} 

\item Prove que todo grafo $3$-regular $2$-conexo tem um
  emparelhamento perfeito.
  \datedue{25/11/2010} 

%\item (Menger/versão de arestas (versão de conjuntos como dica)) 

%\medskip

%\item[(*)] \textit{É possível que alguns outros exercícios para
%    21/10/2010 ainda sejam adicionados.}

\end{enumerate}

\end{document}

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