<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC5827 Topicos de Matemática Discreta               %
% 2o. semestre de 2003                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: &lt;Thursday 27 Nov 2003 01:41:31pm BRST yoshi@erdos.ime.usp.br&gt;   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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\&lt;{\langle}
\def\&gt;{\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 Let~$\cA=\{A_\lambda\:\lambda\in\Lambda\}$ be a family of subsets of a
  finite set~$W$.  Consider the subsets~$\Lambda'\subset\Lambda$ such that the
  family of sets~$A_\lambda$ ($\lambda\in\Lambda'$) admits a system of
  distinct representatives.  Show that any two such \textit{maximal} sets
  (under inclusion) have the same cardinality.
  
\item Let~$M_i=M_i(S_i)$ ($1\leq i\leq k$) be matroids on pairwise disjoint
  sets~$S_i$.  Let
  \begin{equation}
    \label{eq:indept_def}
    \cI=\Big\{\bigcup_{1\leq i\leq k}I_i\:I_i\in\cI(M_i)\Big\}
  \end{equation}
  be the family of unions of independent sets in the matroids~$M_i$ (one
  independent set~$I_i$ for each~$i$).  Clearly, $\cI\subset2^S$,
  where~$S=\bigcup_{1\leq i\leq k}S_i$.
  \begin{itemize}
  \item[(\textit{i})]Show that~$\cI$ is the set of independent sets of a
    matroid on~$S$.  This matroid is called the \textit{direct sum} of the
    matroids~$M_i$ ($1\leq i\leq k$), and is usually denoted~$\bigoplus_{1\leq
      i\leq k}M_i$.
  \item[(\textit{ii})]Determine the rank function of~$\bigoplus_{1\leq i\leq
      k}M_i$.
  \end{itemize}
  
\item Let~$f\:S\to T$ be a surjection, where~$S$ is a finite set.
  Suppose~$M=M(S)$ is a matroid on~$S$.  Let
  \begin{equation}
    \label{eq:indept_homo_def}
    \cI=\{f(I)\:I\in\cI(M)\}
  \end{equation}
  be the family of images of independent sets in~$M$ under~$f$.  Clearly,
  $\cI\subset2^T$.
  \begin{itemize}
  \item[(\textit{i})]Show that~$\cI$ is the set of independent sets of a
    matroid on~$T$.  This matroid is sometimed called the \textit{homomorphic
      image} of~$M$ under~$f$.
  \item[(\textit{ii})]Let~$N=N_f$ be the homomorphic image of~$M$ under~$f$.
    Show that the rank function~$r_N$ of~$N$ is given by
    \begin{equation}
      \label{eq:homo_rank}
      r_N(A)=\min\{r_M(f^{-1}(B))+|A\setminus B|\:B\subset A\}
    \end{equation}
    for all~$A\subset T$, where~$r_M$ is the rank function of~$M$.
  \end{itemize}

\item{}[Horn] Let~$k$ be a positive integer.  Suppose~$x_1,\dots,x_n$ are
  vectors in some vector space such that, for any~$J\subset[n]$, there
  is~$J'\subset J$ such that~$|J'|\geq|J|/k$ and the vectors~$x_j$ ($j\in J'$)
  are linearly independent.  Prove that~$x_1,\dots,x_n$ may be partitioned
  into at most~$k$ families of linearly independent vectors.

\item{}[Nash-Williams] Let~$G$ be a multigraph with no loops and at least one
  edge.  Prove that the edge set of~$G$ may be written as a union of~$k$
  forests if and only if
  \begin{equation}
    \label{eq:NW_cov}
    k\geq{|E(H)|\over|V(H)|-c(H)}
  \end{equation}
  for all subgraphs~$H\subset G$ of~$G$ with~$|V(H)|-c(H)&gt;0$, where~$c(H)$
  denotes the number of components in the graph~$H$.
  
\item{}[Tutte] Let~$G$ be a connected graph.  Prove that~$G$ contains~$k$
  edge-disjoint spanning trees if and only if for any partition~$\pi$ of the
  vertex set of~$G$, the number of edges joining vertices in distinct blocks
  of~$\pi$ is at least~$k(|\pi|-1)$, where~$|\pi|$ denotes the number of
  blocks in~$\pi$.
  
\item{}[Edmonds] Let~$M=M(S)$ and~$N=N(S)$ be two matroids on~$S$.  Prove that
  \begin{multline}
    \label{eq:Edmonds_inter}
    \qquad\qquad\max\{|I|\:I\in\cI(M)\cap\cI(N)\}\\
    =\min\{r_M(A)+r_N(S\setminus A)\:A\subset S\}.\qquad
  \end{multline}
  \hint{Consider the matroid~$M\vee N^*$, where~$N^*$ is the dual of~$N$.} 
  
\item Let~$G$ be a connected graph, and suppose that the edges of~$G$ are
  coloured in an arbitrary way.  Prove that~$G$ contains a spanning tree with
  all its edges coloured with different colours if and only if, for all
  subgraphs~$H\subset G$ of~$G$, the number of colours that occur
  in~$E(G)\setminus E(H)$ is at least~$c(H)-1$, where, again, $c(H)$~denotes
  the number of components in~$H$.  \hint{Observe that, if~$S$ is a finite
    set, then the family of all sets of cardinality at most~$m$ is the family
    of independent sets of a matroid (this is the \textit{uniform
      matroid}~$U_{n,m}$, where~$n=|S|$).  Use this observation for~$m=1$
    and~$S$ the colour classes of the edge colouring of~$G$.  Apply the above
    theorem of Edmonds.  Alternatively, give a proof from first principles.}
  
\end{enumerate}  
 
\end{document}

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

</pre></body></html>