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

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

Full description

Autores:: Colomb, Pierre
Raynaud, Oliver
Irlande, Alexis

Tipo de recurso:: Article of journal

Fecha de publicación:: 2009

Institución:: Universidad Nacional de Colombia

Repositorio:: Universidad Nacional de Colombia

Idioma:: spa

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

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

Publicaciones similares