×

Counting of Moore families for \(n=7\). (English) Zbl 1274.05013

Kwuida, Léonard (ed.) et al., Formal concept analysis. 8th international conference, ICFCA 2010, Agadir, Morocco, March 15–18, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-11927-9/pbk). Lecture Notes in Computer Science 5986. Lecture Notes in Artificial Intelligence, 72-87 (2010).
Summary: Given a set \(U_n = \{ 0, 1, \dots, n-1 \}\), a collection \(\mathcal{M}\) of subsets of \(U_n\) that is closed under intersection and contains \(U_n\) is known as a Moore family. The set of Moore families for a given \(n\), denoted by \(M_n\), increases very quickly with \(n\), thus \(|M_3|\) is 61 and \(|M_4|\) is 2480. In [M. Habib and L. Nourine, Discrete Math. 294, No. 3, 291–296 (2005; Zbl 1083.06003)], the authors determined the number for \(n = 6\) and stated a 24h-computation-time. Thus, the number for \(n=7\) can be considered as an extremely difficult technical challenge. In this paper, we introduce a counting strategy for determining the number of Moore families for \(n=7\) and we give the exact value : 14 087 648 235 707 352 472. Our calculation is particularly based on the enumeration of Moore families up to an isomorphism for \(n\) ranging from 1 to 6.
For the entire collection see [Zbl 1184.68008].

MSC:

05A15 Exact enumeration problems, generating functions
06A15 Galois correspondences, closure operators (in relation to ordered sets)

Citations:

Zbl 1083.06003
PDF BibTeX XML Cite
Full Text: DOI