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: 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: 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.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.