\magnification=\magstep1
\input amstex
\hsize=16truecm
\parskip=4pt
\centerline{\bf MATROIDELM\'ELETI FELADATOK}
\vskip 1 cm
 
\item{1.} Keress\"unk olyan matroidot, amelyik semmilyen vektort\'er
felett sem rep\-re\-zen\-t\'al\-hat\'o.
 
\item{2.}  Legyenek $B_1$ \'es $B_2$ egy $M$ matroid b\'azisai.
 
 \itemitem{(a)} Bizony\'\i tsuk be, hogy l\'etezik egy olysn $f$
bijekci\'o $B_1$ \'es $B_2$
k\"oz\"ott, amelyikre $B_1-x+f(x)$ minden $x \in B_1$ eset\'en b\'azis
$M$-ben.
 
 \itemitem{(b)} Bizony\'\i tsuk be az er\H os b\'azisaxi\'om\'at:
 \itemitem{}
Legyen $x \in B_1-B_2$. Ekkor l\'etezik olyan $y \in B_2-B_1$, hogy
$B_1-x+y$ \'es $B_2-y+x$ is b\'azisok $M$-ben.
 
\item{3.} Legyenek $C_1,\dots,C_m$ egy $M$ matroid k\"orei, melyekre
$$
C_i \not \subseteq \bigcup_{j \neq i}C_j.
$$
\'es $D \subseteq S$, $|D| < m$. Bizony\'\i tsuk be, hogy l\'etezik olyan $C$
k\"or $M$-ben, melyre
$$
C \subseteq \bigcup_{i=1}^m C_i-D.
$$
 
\item{4.} Legyen $M$ egy matroid $S$-n az $r$ rangf\"uggv\'ennyel
\'es $f$ egy
sz\"urjekci\'o $S$-r\H ol $T$-re. Bizony\'\i tsuk be, hogy a $T$-n kapott
matroid (az $S$-beli f\"uggetlenbe p\'aros\'\i that\'o
halmazok f\"uggetlenek)
rangf\"uggv\'enye teljes\'{\i}ti az
$$
r_f(A) = \min_{Y \subseteq A} (r(f^{-1}(Y)) +|A-Y|)
\qquad (A \subseteq T)
$$
azonoss\'agot.
 
\item{5.} Legyenek $M_1$ \'es $M_2$ matroidok $S$-n az $r_1$ ill.
$r_2$ rangf\"uggv\'ennyel. Ekkor az uni\'omatroid rangf\"uggv\'enye
teljes\'{\i}ti az
$$
r(X) = \max_{Y \subseteq X} (r_1(Y) + r_2(X-Y)) \qquad (X
\subseteq S)
$$
azonoss\'agot.
 
\item{6.}  Egy $G$ gr\'af k\"ormatroidja akkor \'es csak akkor
irreducibilis (nem \'all el\H o nem trivi\'alis m\'odon k\'et matroid
uni\'ojak\'ent), ha minden $e$ \'elre $G-e$ 2-\"osszef\"ugg\H o.
 
 
\end