×

Generation of union-closed sets and Moore families. (English) Zbl 1384.05015

Summary: We describe an algorithm to constructively enumerate non-isomorphic union-closed sets and Moore sets. We confirm the number of isomorphism classes of union-closed sets and Moore sets on \(n\leq 6\) elements presented by other authors, and give the number of isomorphism classes of union-closed sets and Moore sets on 7 elements. Due to the enormous growth of the number of isomorphism classes, it seems unlikely that constructive enumeration for 8 or more elements will be possible in the foreseeable future.

MSC:

05A15 Exact enumeration problems, generating functions
05-04 Software, source code, etc. for problems pertaining to combinatorics
PDF BibTeX XML Cite
Full Text: arXiv Link

References:

[1] G. Brinkmann, Isomorphism rejection in structure generation programs, in P. Hansen, P.W. Fowler, and M. Zheng, editors, Discrete Mathematical Chemistry, DIMACS Series on Discrete Mathematics and Theoretical Computer Science51 (2000), 25-38. · Zbl 0963.05126
[2] H. Bruhn and O. Schaudt, The journey of the union closed sets conjecture. Graphs and Combinatorics31(6) (2015), 2043-2074. · Zbl 1327.05249
[3] H. Bruhn and O. Schaudt, The union-closed sets conjecture almost holds for almost all random bipartite graphs. European J. Combinatorics 59 (2017), 129-149. · Zbl 1348.05187
[4] P. Colomb, A. Irlande, and O. Raynaud, Counting of Moore families for n = 7, in Formal Concept Analysis, Vol. 5986 of Lecture Notes in Computer Science, Springer, 2010, pp. 72-87. · Zbl 1274.05013
[5] R. Deklerck, Een constructief algoritme voor union closed sets, Master’s thesis, Ghent University, 2016.
[6] I. A. Faradˇzev, Constructive enumeration of combinatorial objects, Colloques Interna- tionaux C.N.R.S. No. 260 — Probl‘emes Combinatoires et Th´eorie des Graphes, Orsay, 1976, pp. 131-135.
[7] M. Habib and L. Nourine, The number of Moore families on n = 6, Discrete Math. 294 (2005), 291-296. · Zbl 1083.06003
[8] A. Higuchi, Lattices of closure operators, Discrete Math. 179 (1998), 267-272. · Zbl 0910.06004
[9] R. C. Read, Every one a winner, Ann. Discrete Math. 2 (1978), 107-120. · Zbl 0392.05001
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.