Algoritmos de conteo de las familias de moore aplicación al caso n = 7

Abstract

Una familia de Moore sobre un conjunto Un = {0, 1, ..., n − 1} es una colección de conjuntos M cerrada para la operaci´on de intersección y que contiene Un. El conjunto de las familias de Moore para un n dado, notado Mn, crece de forma más que exponencial con respecto a n, así |M3| vale 61 y |M4| vale 2480. En [9], los autores han determinado este número para n = 6 en 24h. La evaluación de este número para n = 7 es entonces un reto técnico difícil. En este artículo, presentamos una estrategia de conteo de las familias de Moore para n = 7 y damos su valor: 14 087 648 235 707 352 472. Nuestro cálculo se apoya en particular sobre la enumeración de las familias de Moore equivalentes mediante un isomorfismo para n de 1 a 6.