Counting of moore families for n=7

Pierre Colomb

Alexis Irlande

Olivier Raynaud

pp. 72-87

in: Lonard Kwuida, Bar Sertkaya (eds), Formal concept analysis, Berlin, Springer, 2010

Abstrakt

Given a set U _n  = {0,1,...,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 ₃| is 61 and |M ₄| is 2480. In [1] 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.