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 |
Keywords:
closure systems; Galois connections; knowledge spaces; lattices; Moore families; Moore co-familiesCitations:
Zbl 1274.05013References:
| [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 · doi:10.1215/S0012-7094-37-00334-X |
| [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(2), 155-185 (1992) · Zbl 0767.68029 · doi:10.1016/0166-218X(92)90028-9 |
| [8] | Duquenne, V.: Latticial structure in data analysis. Theor. Comp. Sci. 217, 407-436 (1999) · Zbl 1034.68510 · doi:10.1016/S0304-3975(98)00279-5 |
| [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 · doi:10.1007/978-3-642-59830-2 |
| [11] | Doignon, J.P., Falmagne, J.C.: Knowledge Spaces. Springer, Berlin (1999) · Zbl 0908.92040 · doi:10.1007/978-3-642-58625-5 |
| [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 · doi:10.1016/S0166-218X(02)00209-3 |
| [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 · doi:10.1016/0304-3975(91)90359-A |
| [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 · doi:10.1016/j.disc.2004.11.010 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
