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

• Autores: Pierre Colomb, Olivier Raynaud, Alexis Irlande
• Localización: Boletín de matemáticas, ISSN 0120-0380, ISSN-e 2357-6529, Vol. 16, Nº. 1, 2009, págs. 57-77
• Idioma: español
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    Una familia de Moore sobre un conjunto Un = {0, 1, ..., n - 1} es una colecci´on de conjuntos M cerrada para la operaci´on de intersecci ´on y que contiene Un. El conjunto de las familias de Moore para un n dado, notado Mn, crece de forma m´as que exponencial con respecto a n, as´ý |M3| vale 61 y |M4| vale 2480. En [9], los autores han determinado este n´umero para n = 6 en 24h. La evaluaci´on de este n´umero para n = 7 es entonces un reto t´ecnico 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´alculo se apoya en particular sobre la enumeraci´on de las familias de Moore equivalentes mediante un isomorfismo para n de 1 a 6.

  • English

    A Moore family on a set Un = {0, 1, ..., n - 1} is as a collection of sets M which is closed by intersection and containing Un. The set of Moore families for a given n, denoted by Mn, increases faster than exponentially with respect to n, thus |M3| is 61 and |M4| is 2480. In [9] the authors found this number for n = 6 in 24h. Thus, its evaluation for n = 7 can be considered as a difficult technical challenge. In this paper, we will introduce a counting strategy for Moore families in the case n=7 and give its value: 14 087 648 235 707 352 472. Our calculation is mostly based on the enumeration of Moore families up to an isomorphism for n ranging from 1 to 6.