%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Arquivo LaTeX2e para % % % % Exercícios de MAC5827 Topicos de Matemática Discreta % % 2o. semestre de 2003 % % Y. Kohayakawa % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Time-stamp: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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\<{\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\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)>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: