Recursive decomposition and bounds of the lattice of Moore co-families.(English)Zbl 1311.06003

Summary: A collection of sets on a ground set $$U_n$$ ($$U_n=\{1,2,\ldots,n\}$$) closed under intersection and containing $$U_n$$ is known as a Moore family. The set of Moore families for a fixed $$n$$ is in bijection with the set of Moore co-families (union-closed families containing the empty set) denoted $$\mathbb M_n$$. In this paper, we propose a recursive definition of the set of Moore co-families on $$U_n$$. Then we apply this decomposition result to compute a lower bound on $$|\mathbb M_n|$$ as a function of $$|\mathbb M_{n-1}|$$, the Dedekind numbers and the binomial coefficients. These results follow the work carried out by P. Colomb et al. [Lect. Notes Comput. Sci. 5986, 72-87 (2010; Zbl 1274.05013)] to enumerate the number of Moore families on $$U_7$$.

MSC:

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

Zbl 1274.05013
Full Text:

References:

 [1] Colomb, P., Irlande, A., Raynaud, O.: Counting of Moore families on n = 7. In: ICFCA, LNAI 5986, pp. 72-87 (2010) · Zbl 1274.05013 [2] Birkhoff, G.: Lattice Theory. American Mathematical Society (1940) · Zbl 0063.00402 [3] Cohn, P.: Universal Algebra. Harper and Row, New York (1965) · Zbl 0141.01002 [4] van de Vel, L.: Theory of convex structures. North-Holland, Amsterdam (1993) · Zbl 0785.52001 [5] Birkhoff, G, Rings of sets, Duke Math. J., 3, 443-454, (1937) · Zbl 0017.19403 [6] Davey, B.A., Priestley, H.A.: Introduction to lattices and orders. Cambridge University Press, Cambridge (1991) · Zbl 0701.06001 [7] Demetrovics, J; Libkin, L; Muchnik, I, Functional dependencies in relational databases: A lattice point of view, Discrete Appl. Math., 40, 155-185, (1992) · Zbl 0767.68029 [8] Duquenne, V, Latticial structure in data analysis, Theor. Comp. Sci., 217, 407-436, (1999) · Zbl 1034.68510 [9] Barbut, M., Monjardet, B.: Ordre et classification. Hachette (1970) · Zbl 0267.06001 [10] Ganter, B., Wille, R.: Formal concept analysis, mathematical foundation. Berlin-Heidelberg-NewYork et al.: Springer (1999) · Zbl 0909.06001 [11] Doignon, J.P., Falmagne, J.C.: Knowledge Spaces. Springer, Berlin (1999) · Zbl 0908.92040 [12] Caspard, N; Monjardet, B, The lattices of closure systems, closure operators, and implicational systems on a finite set: a survey, Discrete Appl. Math., 127, 241-269, (2003) · Zbl 1026.06008 [13] Demetrovics, J; Molnar, A; Thalheim, B, Reasoning methods for designing and surveying relationships described by sets of functional constraints, Serdica J. Computing, 3, 179-204, (2009) · Zbl 1187.68189 [14] Burosh, G; Demetrovics, J; Katona, G; Kleitman, D; Sapozhenko, A, On the number of databases and closure operations, Theor. Comp. Sci., 78, 377-381, (1991) · Zbl 0717.68019 [15] Demetrovics, J., Libkin, L., Muchnik, I.: Functional dependencies and the semilattice of closed classes. In: MFDBS, LNCS 364. pp. 136-147 (1989) · Zbl 0717.68019 [16] Alekseev, V, The number of families of subsets that are closed with respect to intersections, Diskretn. Mat., 1, 129-136, (1989) · Zbl 0725.05009 [17] Habib, M; Nourine, L, The number of Moore families on n = 6, Discrete Math., 294, 291-296, (2005) · Zbl 1083.06003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.