- 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
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.
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.
Categoría:- Teoría de hipergrafos
Wikimedia foundation. 2010.