Caracterization for disjoint transversal and partition partial transversal

57 Views Asked by At

In book of Schrijver (Combinatorial Optimization Polyedra and Efficiency), has a affirmation follows below: Illustration

He suggested that is possible to show using matroid base packing theorem and matroid base covering theorem, respectively below has the illustration these:

Illustration packing and covering base matroid

Moreover, suggested to use Equation (39.19) that expressed the rank function $r$ of a transversal matroid that I annexed below:

Ilustration Equation (39.19)

For the first, let $M$ the transversal matroid induced by ${\cal X}$. We have that ${\cal X}$ has $k$ disjoints transversals if only if exists $k$ disjoints bases in $M$. By matroid base packing theorem (Corollary 42.1d of Figure), this is equivalent at $$k \cdot (r(S) - r(U)) \leq |S-U|$$ for each $U \subseteq S$. How I can to conclude the remains of proof?

For the second, let $M$ the transversal matroid induced by ${\cal X}$. We have that $S$ can be partitioned in $k$ partial transversals if only if $S$ can be covered by $k$ independents sets of $M$. By matroid base covering theorem (Corollary 42.1c), this equivale:

$$k \cdot r(U) \geq |U|$$ for each $U \subseteq S$. How I can to do the remain of proof too?