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:
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:
Números de Dedekind
Plantilla:AP 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 Plantilla: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.