¿Definición alternativa y concepto opuesto a matroide?

Question

En Wikipedia

En términos de independencia, un matroid finito $M$ es un par $(E,\mathcal{I})$ donde $E$ es un conjunto finito (llamado conjunto básico) y $\mathcal{I}$ es una familia de subconjuntos de $E$ (denominados conjuntos independientes) con las siguientes propiedades:

• El conjunto vacío es independiente, es decir, $\emptyset\in\mathcal{I}$ . Alternativamente, al menos un subconjunto de $E$ es independiente, es decir $\mathcal{I}\neq\emptyset$ .

• Todo subconjunto de un conjunto independiente es independiente, es decir, para cada $A'\subset A\subset E$ si $A\in\mathcal{I}$ entonces $A'\in\mathcal{I}$ . A veces se denomina propiedad hereditaria.

• Si $A$ y $B$ son dos conjuntos independientes de $\mathcal{I}$ y $A$ tiene más elementos que $B$ entonces existe un elemento en $A$ que cuando se añade a $B$ da un conjunto independiente mayor. A veces se denomina propiedad de aumento o propiedad de intercambio de conjuntos independientes.

Un subconjunto del conjunto terreno E que no es independiente se denomina dependiente. Un conjunto independiente máximo, es decir, un conjunto independiente que se vuelve dependiente al añadir cualquier elemento de E, se denomina base del matroide.

1. ¿Puede definirse un matroid de forma equivalente sustituyendo el aumento por la siguiente :

   • $\forall A \in \mathcal{I}$ , $A$ tiene un superconjunto máximo en $\mathcal{I}$ y la cardinalidad del superconjunto máximo de $A$ es igual para todos los miembros de $\mathcal{I}$ .

2. Me preguntaba si ya ha existido un concepto que sea opuesto a un matroid? Por ejemplo, para un par $(E, \mathcal{J})$ ,

   • $E \in \mathcal{J}$ ,

   • para cada $A'\subset A\subset E$ si $A' \in\mathcal{J}$ entonces $A \in\mathcal{J}$ .

   • Si $A$ y $B$ están ambos en $\mathcal{J}$ y $A$ tiene menos elementos que $B$ entonces existe un elemento en $B$ cuando se retira de $B$ da un miembro más pequeño en $\mathcal{J}$ . ( $A$ puede o puede no ser útil para encontrar dicho elemento en $B$ .)

   o puede sustituirse el tercer punto por

   • $\forall A \in \mathcal{J}$ , $A$ tiene un subconjunto mínimo en $\mathcal{J}$ y la cardinalidad del subconjunto mínimo de $A$ es igual para todos los miembros de $\mathcal{J}$ .

   A partir de esta definición, ¿podemos definir mejor un concepto sólo opuesto a una base de un matroid, algo así como "un conjunto mínimo en $\mathcal{J}$ se denomina base de $(E, \mathcal{J})$ ".

   Un ejemplo $(E, \mathcal{J})$ será la colección de todas las bases de una topología .

Gracias y saludos.

Answer 1

Para la primera pregunta, la propiedad de aumento no puede sustituirse por esta nueva afirmación. Esta afirmación dice esencialmente que todos los conjuntos máximos independientes (bases) tienen el mismo tamaño. Pero esto no basta para demostrar la propiedad de aumento. Consideremos este ejemplo, con $E = \{ 1,2,3,4\}$ y $I = \{ \phi, \{1\}, \{2\}, \{1,2\}, \{3\}, \{4\}, \{3,4\}\}$ . Esto satisface su nueva afirmación, pero no la propiedad de aumento. Cuando se intenta describir en términos de bases, un propiedad similar al aumento. En términos de conjuntos independientes, otra definición típicamente utilizada es sustituir el aumento por la siguiente propiedad.

• Dado cualquier $A \subseteq E$ todos los conjuntos máximos independientes contenidos en $A$ tienen el mismo tamaño.

Answer 2

Como señala @polkjh, la propiedad de aumento no es equivalente a la propiedad de que todos los conjuntos máximamente independientes tengan el mismo tamaño. Mientras que (los conjuntos independientes de) cualquier matroide forman un complejo simplicial puro no todo complejo simplicial puro es un matroide. El ejemplo dado en la respuesta de @polkjh del complejo simplicial sobre $\{1,2,3,4\}$ con facetas $\{1,2\},\{3,4\}$ es un ejemplo mínimo.

Veamos ahora la segunda colección de axiomas. Los tres primeros juntos implican que el sistema de conjuntos resultante $\mathcal{J}$ se compone siempre de todos los subconjuntos de $E$ . Para ver esto tenga en cuenta que $E \in \mathcal{J}$ por el primer axioma. Aplicando repetidamente el tercer axioma encontramos que el conjunto vacío también está en $\mathcal{J}$ . Aplique ahora el segundo axioma para ver que todos los subconjuntos de $E$ están en $\mathcal{J}$ .

Obsérvese que un sistema de conjuntos que satisface el tercer axioma se denomina sistema de conjuntos accesible. Se utiliza en la definición de greedoid un tipo de sistema de conjuntos que generaliza tanto los matroides como los antimatroides.

Sustituyendo el tercer axioma por el cuarto se obtienen sistemas de conjuntos que son precisamente los nonfaces de un complejo simplicial cuyo Stanley-Reisner ideal se genera en un solo grado. Un complejo simplicial de este tipo no tiene por qué ser puro: por ejemplo, el ideal de Stanley-Reisner del complejo simplicial sobre $\{1,2,3,4\}$ con facetas $\{1,2,4\},\{1,3,4\},\{2,3\}$ está generado por los monomios $x_1x_2x_3$ y $x_2x_3x_4$ . Aquí hay una imagen para ayudar a visualizar la situación. Las facetas están sombreadas en azul mientras que las caras más pequeñas están rodeadas por un círculo azul. Del mismo modo, las no caras mínimas están sombreadas en gris, mientras que la no cara no mínima está rodeada por un círculo gris.

Answer 3

Mi definición "alternativa" favorita de un matroide es: Un matroide es un complejo simplicial cuyo subcomplejo inducido es puro.