Lista de todos los matroides

Question

Lista de todos los matroides $(E, S)$ con $E = \{1\}, E = \{1, 2\}, E = \{1, 2, 3\}$ .

Sé que $(E, S)$ se llama sistema de independencia, y que según la definición $S \subseteq 2^E$ y $S$ está cerrado bajo inclusión. La cuestión es que, no entiendo exactamente el problema anterior. ¿Cuáles serán los matroides en cuestión?

EDITAR:

Matroides para $E = \{1, 2\}$

$\{ \emptyset \}, \{ \emptyset, \{1\} \}, \{ \emptyset, \{2\} \}, \{ \emptyset, \{1\}, \{2\}\}, \{ \emptyset, \{1\}, \{2\}, \{1, 2\}\}$

Matroides para $E = \{1, 2, 3\}$

$\{ \emptyset \}, \{ \emptyset, \{1\} \}, \{ \emptyset, \{2\} \}, \{ \emptyset, \{3\} \}, \{ \emptyset, \{1\}, \{2\}\}, \{ \emptyset, \{1\}, \{3\}\}, \{ \emptyset, \{2\}, \{3\}\}, \{ \emptyset, \{1\}, \{2\}, \{1, 2\}\}, \{ \emptyset, \{1\}, \{3\}, \{1, 3\}\}, \{ \emptyset, \{2\}, \{3\}, \{2, 3\}\}, \{ \emptyset, \{1\}, \{2\}, \{3\}\}, \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1, 2, 3\}\}$

Answer 1

En la pregunta se pide que conjuntos de subconjuntos $S$ satisfacer los requisitos de un sistema de independencia.

Por ejemplo, para $E=\{1\}$ tenemos $2^E=\{\emptyset, \{1\}\}$ Así que $|2^E|=2$ . Por lo tanto, potencialmente hay $2^2=4$ candidatos:

$S_1=\{\}=\emptyset$
$S_2=\{\emptyset\}$
$S_3=\{\{1\}\}$
$S_4=\{\emptyset,\{1\}\}$

Sin embargo, eliminamos $S_3$ porque no se cierra bajo la inclusión. También eliminamos $S_1$ porque no contiene el conjunto vacío (requisito para ser un sistema independiente). Por lo tanto, es exactamente $S_2$ y $S_4$ que son sistemas de independencia para ese $E$ .

Answer 2

Podría estar totalmente equivocado, esto es confuso y nuevo para mí también.

Ver https://people.cs.umass.edu/~barring/cs611/lecture/4.pdf páginas 8 y 9.

Teniendo en cuenta eso y el cartel anterior, creo (¿espero?) que esto debería ser correcto

E = $\{1\}$

S = $\{\emptyset, \{1\}\}$

E = $\{1, 2\}$

S = $\{\emptyset, \{1\}, \{2\}, \{1,2\}\}$

E = $\{1, 2, 3\}$

S = $\{\emptyset, \{1\}, \{2\},\{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$

Creo que todos estos satisfacen las 3 propiedades de los matroides...

1) el conjunto vacío es independiente

2) todo subconjunto de un conjunto independiente es independiente; $\{2,3\} \subset \{1,2,3\}\ $ , $\{2,3\} \subset S$ y $\{1,2,3\} \subset S$

3) $A = \{1,2,3\}$

$\,\,\,\,\,$$ B = \{3\}$

$\,\,\,\,\,$$ B\a, \a, \a, \a, \a, \a, = \a, \a, \a, \a, \a, \a, \a, en S$

$\,\,\,\,\,$$ B\a, \a, \a, \a, \a, \a, = \a, \a, \a, \a, \a, \a, \a, \a, en S$

Answer 3

Utilizando el Macaulay2 paquete de software Matroides se pueden obtener rápida y fácilmente todas las clases (de isomorfismo) de matroides en $n$ elementos para $n\le 8$ . Para ello, utilice el allMatroids método:

i1 : loadPackage "Matroids";

i2 : VerticalList apply (allMatroids 1, M -> bases M)
o2 = {{set {}} }
     {{set {0}}}

i3 : VerticalList apply (allMatroids 2, M -> bases M)
o3 = {{set {}}          }
     {{set {0}, set {1}}}
     {{set {1}}         }
     {{set {0, 1}}      }

i4 : VerticalList apply (allMatroids 3, M -> bases M)
o4 = {{set {}}                            }
     {{set {0}, set {1}, set {2}}         }
     {{set {1}, set {2}}                  }
     {{set {2}}                           }
     {{set {0, 1}}                        }
     {{set {0, 2}, set {0, 1}}            }
     {{set {1, 2}, set {0, 2}, set {0, 1}}}
     {{set {0, 1, 2}}                     }

Nótese que sólo hemos especificado las bases de cada (representante de la clase de isomorfismo de un) matroide. Pero esto es suficiente, ya que el complejo de independencia de un matroide es un complejo simplicial y todo complejo simplicial está determinado por sus símbolos máximos.