Sistema de independencia

En matemáticas combinatorias , un sistema de independencia${\displaystyle S}$es un par${\displaystyle (V,{\mathcal {I}})}$, donde${\displaystyle V}$es un conjunto finitoy${\displaystyle {\mathcal {I}}}$es una colección de subconjuntos de${\displaystyle V}$( llamados conjuntos independientes o conjuntos factibles ) con las siguientes propiedades:

1. El conjunto vacío es independiente, es decir,${\displaystyle \emptyset \in {\mathcal {I}}}$. (Alternativamente, al menos un subconjunto de ⁠${\displaystyle V}$es independiente, es decir,${\displaystyle {\mathcal {I}}\neq \emptyset }$.)
2. Cada subconjunto de un conjunto independiente es independiente, es decir, para cada${\displaystyle Y\subsetequ X}$, tenemos${\displaystyle X\in {\mathcal {I}}\Rightarrow Y\in {\mathcal {I}}}$Esto a veces se denomina propiedad hereditaria o cierre hacia abajo .

Otro término para un sistema de independencia es complejo simplicial abstracto .

• Un par${\displaystyle (V,{\mathcal {I}})}$, donde${\displaystyle V}$es un conjunto finitoy${\displaystyle {\mathcal {I}}}$es una colección de subconjuntos de${\displaystyle V}$⁠ ,también se denomina hipergrafo . Al utilizar esta terminología, los elementos del conjunto ⁠${\displaystyle V}$Se denominan vértices y elementos de la familia .${\displaystyle {\mathcal {I}}}$Se denominan hiperaristas . Por lo tanto , un sistema de independencia puede definirse brevemente como un hipergrafo cerrado hacia abajo.
• Un sistema de independencia con una propiedad adicional llamada propiedad de aumento o propiedad de intercambio de conjuntos independientes produce un matroide . La siguiente expresión resume las relaciones entre los términos:

  HIPERGRAFOS ⊃ SISTEMAS DE INDEPENDENCIA = COMPLEJOS SIMPLICIALES ABSTRACTOS ⊃ MATROIDES.

• Bondy, Adrian ; Murty, USR (2008), Teoría de grafos , Textos de posgrado en matemáticas, vol.  244, Springer, pág.  195, ISBN 9781846289699.