5 votos

¿El fuerte eliminación axioma mantenga también para el conjunto de dependiente de conjuntos de un matroid?

Deje $M$ ser un matroid con $\mathcal C$ como conjunto de circuitos de $M$, e $\mathcal D$ como conjunto de dependiente de conjuntos de $M$, respectivamente.

Recordemos que $\mathcal C \subseteq \mathcal D$. Sabemos que el fuerte de la eliminación axioma tiene por $\mathcal C$, es decir,

$$\forall C_1, C_2 \in \mathcal C\ \forall x \in C_1 \cap C_2\ \forall y \in C_1\setminus C_2\ \exists C_3 \in \mathcal C: y \in C_3 \subseteq (C_1 \cup C_2)\setminus \{x\}.$$

Pregunta: ¿$\mathcal D$ también tienen esta propiedad, que es

$$\forall X, Y \in \mathcal D\ \forall x \in X \cap Y\ \forall y \in X\setminus Y\ \exists Z \in \mathcal D: y \in Z \subseteq (X \cup Y)\setminus \{x\}?$$

Si se mantiene, lo que es una prueba de este hecho? Si no, ¿qué es un contra-ejemplo?

5voto

Milo Brandt Puntos 23147

El dependiente de conjuntos no necesariamente satisfacen los débiles eliminación axioma. Por ejemplo, si tenemos un matroid en $\{a,b,c\}$ con un circuito de $\{a\}$, $X=\{a,b\}$ $Y=\{a\}$ son dependientes de conjuntos, pero no es $Z$ que es un subconjunto de a $X\cup Y \setminus \{a\}$. Incluso si le pedimos que $X$ no es un subconjunto de a $Y$ y viceversa, un contraejemplo conjuntos de $X=\{a,b\}$$Y=\{a,c\}$, a continuación, elimina $a$, pero esto falla porque $\{b,c\}$ es independiente.

El problema general es que no todos los dependientes de conjuntos puede ser escrito como una unión de los circuitos. Si tenemos algo de $x\in X$ para un conjunto dependiente $X$ tal que para todos los circuitos de $Y\subseteq X$ tenemos $x\not \in Y$, entonces, asumiendo débil eliminación obras, nos podemos preguntar:

¿Cuál es el mínimo conjunto dependiente $X'$ tal que $x\in X'$$X'\subseteq X$?

Si $X'$ contiene algunas circuito de $Y$$y\in Y$, entonces podemos usar débil eliminación en $y$ para obtener un dependiente de la $Z\subseteq X'\setminus \{y\}$. A continuación, $X''=Z\cup \{x\}$ es un conjunto dependiente con $x\in X''$$X''\subset X'$, lo $X'$ no fue mínima. Por lo tanto, la minimización de la $X'$ no contiene circuitos. Sin embargo, esto es una contradicción, ya que $X'$ se definió a ser dependiente.


Notas: Si débil mantenidos para la eliminación dependiente de conjuntos, esto implicaría una fuerte eliminación, ya que sólo podría unión el elemento que estaban tratando de preservar de nuevo en el conjunto si se había eliminado. También, si usted quiere encontrar un conjunto dependiente que no es una unión de los circuitos, una construcción que trabajan a menudo es tomar un plano de $F$ que es dependiente y no de todo el espacio. Entonces, para cualquier $x\not\in F$ el conjunto $F\cup\{x\}$ no contiene circuitos que contengan $x$. Así, por ejemplo, si este es el matroid de un arreglo de vectores, vectores deben estar en posición general (es decir, no subespacio de menos que la plena dimensión contiene más puntos que el subespacio de dimensión). Se extiende a partir de esto, se puede, con un poco de esfuerzo, demostrar que la debilidad de la eliminación sólo funciona en dependiente establece cuando cada circuito tiene el mismo número de elementos (es decir, cuando los circuitos son exactamente los subconjuntos de la base de tamaño de $r+1$ donde $r$ es el rango).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X