Clutter (matemática)

En teoría de hipergrafos y combinatoria, el clutter (también llamado Familia de Sperner) de un hipergrafo H definido sobre un conjunto base A, es el hipergrafo ν(H) conformado por todos los subconjuntos de A que "responden" a H, o bien que "contienen" a todas las hiperaristas de H. Formalmente, dado un hipergrafo H definido sobre un conjunto base A, el clutter de H es el operador definido como:

$\nu ({\mathcal {H}}):=\{W\subseteq A;\exists X\in {\mathcal {H}},X\subseteq W\}$

Note que H es subconjunto de ν(H), y este es a su vez subconjunto del conjunto potencia del conjunto base, P(A).

El clutter de una estructura de hipergrafos G:=(H, K) se define como:

$\nu ({\mathcal {G}}):=(\nu ({\mathcal {H}}),\nu ({\mathcal {K}}))$

Números de Dedekind

El número de familias de Sperner en un conjunto de n elementos es contado por los números de Dedekind, de los cuales los primeros son los siguientes:

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sucesión A000372 en OEIS).

Aunque se conocen estimaciones asintóticas precisas para valores de n mayores, se desconoce actualmente una fórmula que pueda ser computada eficientemente para números superiores a 8.

Complejidad computacional

El clutter es un operador ineficiente, que crece exponencialmente en función del tamaño de la entrada (sea esta H o G). En efecto, la única forma de determinar todos sus elementos es recorriendo todos los elementos de P(A), y verificando la condición de inclusión de la definición.

Referencias

• Polyméris, Andreas (2008). «Stability of two player game structures». Discrete Applied Mathematics 156 (14). ISSN 0166-218X, p. 2636-2646. 

• Datos: Q819142