Clutter (matemàtica)

En teoria de hipergrafos i combinatòria, el clutter (també cridat Família de Sperner) d'un hipergrafo H definit sobre un conjunt base A, és el hipergrafo ν(H) conformat per tots els subconjunts de A que "responen" a H, o be que "contenen" a totes les hiperaristas de H. Formalment, donat un hipergrafo H definit sobre un conjunt base A, el clutter de H és l'operador definit com:

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

Note que H és subconjunt de ν(H), i est és a la seua volta subconjunt del conjunt potencia del conjunt base, P(A).

El clutter d'una estructura de hipergrafos G:=(H, K) es definix com:

$\nu (𝒢):=(\nu (\mathscr{H}),\nu (𝒦))$

Números de Dedekind

Artícul principal → Número de Dedekind.

El número de famílies de Sperner en un conjunt de n elements és contat pels números de Dedekind, dels quals els primers són els següents:

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 Plantilla:OEIS.

Encara que es coneixen estimacions asintòtiques precises per a valors de n majors, es desconeix actualment una fòrmula que puga ser computada eficientemente per a números superiors a 8.

Complexitat computacional

El clutter és un operador ineficiente, que creix exponencialment en funció del tamany de l'entrada (siga esta H o G). En efecte, l'única forma de determinar tots els seus elements és recorrent tots els elements de P(A), i verificant la condició d'inclusió de la definició.