Algunas preguntas sobre matroid

Question

Tengo una pregunta desconocida

Gracias de antemano.

Sea $M=(E,I)$ sea un matroid y que $B$ y $B$ sean dos bases disjuntas de $M$ . Sea $B$ sea dividirse en conjuntos $Y_1$ y $Y_2$ . Demuestre que existe una partición de $B$ en conjuntos $Z_1$ y $Z_2$ para que ambos $Y_1 \cup Z_2$ y $Z_1 \cup Y_2$ son bases de $M$ .

Answer 1

He aquí una prueba por inducción algo larga. Sea $B = \{b_{1}, b_{2}, \dots b_{n}\}$ y $B' = \{c_{1}, c_{2}, \dots c_{n}\}$ . En primer lugar, mostramos el caso base de $Y_{1} = \{b_{i}\}$ .

Considere $B - \{b_{i}\}$ . Por el axioma de intercambio de bases, sabemos que existe un $c_{j} \in B'$ con $(B - \{b_{i}\}) \cup \{c_{j}\}$ independiente. Afirmo que $(B' - \{c_{j}\}) \cup \{b_{i}\}$ también es independiente, lo que da la partición requerida ( $Y_{1} = \{b_{i}\}$ , $Y_{2} = (B - Y_{1})$ y lo mismo para $Z_{1}, Z_{2}$ ).

Puedes comprobarlo mirando la función de rango. Si hay un $c_{k} \in B'$ con $r(\{b_{i}, c_{k}\}) = 1$ también podemos ver que $r(\{c_{j}, b_{i}\}) = 1$ así que $r(\{b_{i}, c_{k}, c_{j}\}) = 1$ . Esto implica que $r((B' - \{c_{j}\}) \cup \{b_{i}\} \cup \{c_{j}\}) = r(B' \cup \{b_{i}\}) \leq |B'| - 1$ lo cual es una contradicción ya que $r(B') = |B'|$ y el rango es monótono creciente. Equivalentemente, no puede haber tres elementos paralelos ya que al menos dos están en la misma base.

Para el paso de inducción, consideremos el matroid $M'$ con bases $B - Y_{1}$ y $B' - Z_{1}$ donde $Y_{1}, Z_{1}$ son partes en particiones de $B, B'$ . Por el caso base, podemos particionar las bases de $M'$ con piezas $Y_{1}', Z_{1}'$ tal que $|(Y_{1} \cup Y_{1}')| = |Y_{1}| + 1$ y $|(Z_{1} \cup Z_{1}')| = |Z_{1}| + 1$ . Los conjuntos $(Y_{1} \cup Y_{1}'), (Z_{1} \cup Z_{1}')$ ahora son piezas para una partición de $B, B'$ que cumpla la condición (podemos dejar que $Y_{2} = B - Y_{1}$ ).