Generation of Union-Closed Sets and Moore Families

Gunnar Brinkmann and Robin Deklerck Applied Mathematics, Computer Science and Statistics Ghent University Krijgslaan 281 S9 B9000 Ghent Belgium

                   gunnar.brinkmann@ugent.be
                    robindeklerck@skynet.be.

Abstract 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 ≤ 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.

1 Introduction

All sets in this article are finite. A union-closed set is a set U of sets with the property that for all A, B ∈ U we have A ∪ B ∈ U. We call Ω_{U} = ⋃_{A∈U} A the universe of U. Two unionclosed sets with universe Ω_{U}, resp., Ω_{U′} are defined to be isomorphic if there is a bijective mapping Ω_{U} → Ω_{U′} inducing a bijection between the union-closed sets.

As we are mainly interested in isomorphism classes, we may assume Ω_{U} = Ω_{n} = {1, …, n} for some n. While the whole universe Ω_{U} is by definition an element of a union-closed set U, this is not the case for the empty set. As the empty set has no impact on the structure of a union-closed set, one often either requires the empty set to be an element of each union-closed set or forbids it to be an element. We choose for the first convention, so our union-closed sets contain Ω_{n} as well as the empty set. We denote a set containing one representative of each isomorphism class of union-closed sets with universe Ω_{n} as R_{n}.

The famous union-closed sets conjecture (or Frankl’s conjecture) states that for each union-closed set there is an element that is present in at least half of the sets. Unfortunately, the number of union-closed sets grows so quickly that complete enumeration is not a suitable approach for testing this conjecture. A lot is known about the structure of possible counterexamples to the union-closed sets conjecture (see [2] for a survey), so any approach to extend the knowledge on the smallest size of a possible counterexample by constructive enumeration must focus on the subset of union-closed sets with those additional structural properties (e.g., with small average size of the sets, without some subconfigurations like singletons, etc.).

Union-closed sets are closely related to Moore families. A Moore family for a universe Ω_{n} is a set of subsets of Ω_{n} that is closed under intersection and contains Ω_{n}. It is easy to see that for a union-closed set U the set U^{c} = {Ω_{n} \ A|A ∈ U} is a Moore family. For a Moore family M the set M^{c} = {Ω_{n} \ A|A ∈ M} is closed under union, but as the empty set is not necessarily contained in M, it is a union-closed set for Ω_{n} \ ⋂_{A∈M} A, which is isomorphic to a union-closed set for some Ω_{n′} with n′ ≤ n.

A set M_{n} of representatives of Moore families (with the canonical definition of isomorphism) for the universe Ω_{n} can be obtained from sets R_{0}, …, R_{n} of representatives of unionclosed sets containing the empty set as follows: M_{n} = ⋃_{i=0}^{n}{U^{c}|U ∈ R_{i}} if the complement is in each case taken in the universe Ω_{n}.

So union-closed sets correspond to Moore sets, which again characterize closure operators, and have many applications in topology, algebra and logic.

For n < 7, several authors developed enumeration algorithms for Moore families [4, 7, 8]. In the most advanced article, Colomb, Irlande, and Raynaud [4] not only counted Moore families for n ≤ 6, but they also generated representatives of isomorphism classes. For n = 7, the approach is not suitable for generating a set of representatives, and by clever use of the structure of representatives of Moore families for n = 6 they only determined the number of labeled Moore families — that is, without considering isomorphisms. In our algorithm we determine the number of labeled union-closed sets resp., labeled Moore families for n = 7 from representatives and their automorphism groups of the union-closed sets for n = 7, resp., n ≤ 7. This gives a very good independent test for the implementation in [4] as well as for our implementation. When computing the number of labeled Moore families for Ω_{7} from the number of labeled union-closed sets with n ≤ 7, for those union-closed sets with n < 7, one must take into account that for Ω_{7} isomorphic copies not only occur for the universe {1, …, n}, but for each n-element subset of {1, …, 7}.

2 The algorithm

A subset A ⊆ Ω_{n} is represented as a number b(A) given as the binary number b_{n−1} ⋯ b_{0} — possibly with leading zeros — with b_{i} = 1 if (i + 1) ∈ A and b_{i} = 0 otherwise.

We use an ordering of the subsets of Ω_{n}. For A, B ⊆ Ω_{n} we define A > B if |A| < |B| (so sets with more elements are considered smaller in this order) or |A| = |B| and b(A) > b(B). Whenever we refer to larger or smaller sets, we refer to this ordering.

The construction algorithm generates union-closed sets recursively based on the following easy lemma:

Lemma 1. If U ≠ {Ω_{n}} is a union-closed set and A is the largest non-empty element in U, then U \ {A} is also a union-closed set.

This implies that union-closed sets for universe Ω_{n} can be recursively constructed from the union-closed set {Ω_{n}, ∅} of smallest size by successively adding subsets of Ω_{n} that are larger than the largest non-empty set already present. Of course it is not assured that adding a smaller set to a union-closed set does not violate the condition that the set must be closed under unions.

In order to turn this into an efficient algorithm, two tests that are (in principle) applied to each structure generated must be very fast:

(i) The test whether the set that has been constructed by adding a new set is closed under union.

(ii) The test for isomorphisms.

We first discuss (i). A straightforward way to test (i) for a union-closed set U to which a new set A is added would be to form all unions A ∪ B with B ∈ U and test whether they are in U ∪ {A}. Although all these steps can be implemented as efficient bit-operations, their number would slow down the program. We make the following definition.

Definition 2. For a union-closed set U we define the reduced set red(U) as follows:

red(U) = {A ∈ U|A ≠ ∅ and there is no A_{1} ≠ ∅ in U, A_{1} ⊊ A}.

Lemma 3. Let U be a union-closed set for a universe Ω_{n} and let A ⊂ Ω_{n}, that is larger than any non-empty set in U. Then U ∪ {A} is closed under union if and only if A ∪ B ∈ U for all B ∈ red(U).

Proof. First assume that U ∪ {A} is closed under union and let B ∈ red(U). Then A ∪ B ∈ (U ∪ {A}) and as A is larger than B, we have A ∪ B ≠ A, so A ∪ B ∈ U.

For the other direction assume that A ∪ B ∈ U for all B ∈ red(U) and let D ∈ U.

Choose any D′ ⊂ D so that D′ ∈ red(U). Then A′ = A ∪ D′ ∈ U and therefore also A′ ∪ D ∈ U as U is closed under union, but A′ ∪ D = A ∪ D — so A ∪ D ∈ U ∪ {A} and U ∪ {A} is closed under union.

It would be inefficient to compute red(U) each time a new union-closed set is constructed, but as a new union-closed set U′ is constructed by adding a new smallest element A to U, the set red(U′) can easily be constructed from red(U) by adding A and removing elements that contain A. Nevertheless the few lines of code testing whether the potential union-closed set is closed under union take more than 50% of the total running time when computing union-closed sets for Ω_{6}, which is the largest case that can be profiled.

In order to solve problem (ii) efficiently — that is, avoid the generation of isomorphic copies — we use a combination of Read/Faradžev type orderly generation [6, 9] and the homomorphism principle (see, e.g., [1]).

Our first aim is to define a unique representative for each isomorphism class — called the canonical representative — and then only construct union-closed sets that are the canonical representatives of their class. We represent a union-closed set U with k + 1 elements A_{1} < A_{2} < ⋯ < A_{k} < ∅ as the string s(U) = b(A_{1}), …, b(A_{k}) of numbers. For a given isomorphism class of union-closed sets for a universe Ω_{n} we choose the union-closed set with the lexicographically smallest string as the representative.

It is in principle easy to test whether a given union-closed set U is the representative of its class by applying all n! possible permutations to U and comparing the strings. As n ≤ 7 this would not be extremely expensive, but due to the large number of times that this test has to be applied, it is far too expensive to construct the union-closed sets for Ω_{7}. In the sequel we describe a way how this can be optimized.

In order to increase the efficiency by making it an orderly algorithm of Read/Faradžev type, we use the canonicity test not only for structures we output, but also during the construction: non-canonical structures are neither output nor used in the construction. This only leads to a correct algorithm if we can prove that canonical representatives are constructed from canonical representatives:

Theorem 4. Let U ≠ {Ω_{n}, ∅} be a union-closed set for the universe Ω_{n} that is the canonical representative for its isomorphism class. If U = {A_{1}, A_{2}, …, A_{k}, ∅} with A_{1} < A_{2} < ⋯ < A_{k} and 1 ≤ m ≤ k, then {A_{1}, A_{2}, …, A_{m}, ∅} is also the canonical representative of its class.

Proof. We prove the result for m = k − 1. For k = m it is the assumption and for m < k − 1 it then follows by induction.

Let s(U) = (s_{1}, …, s_{k}). For a permutation Π of Ω_{n} and a union-closed set U we write Π(U) for the union-closed set obtained by replacing each element of a set in U by its image under Π. Assume that U′ = {A_{1}, A_{2}, …, A_{k−1}, ∅} is not the canonical representative of its class. So there is a permutation Π of Ω_{n} with s(Π(U′)) < s(U′). Let s(Π(U′)) = (p_{1}, …, p_{k−1}) and we have s(U′) = (s_{1}, …, s_{k−1}). Let j be the first position so that p_{j} < s_{j}. Let us now look at s(Π(U)) = (p′_{1}, …, p′_{k}) and let r be the position of Π(A_{k}) in this string. If r > j then p′_{i} = p_{i} = s_{i} for 1 ≤ i < j and p′_{j} = p_{j} < s_{j} — so there is a smaller representative for the isomorphism class of U. If r ≤ j then p′_{i} = p_{i} = s_{i} for 1 ≤ i < r and p′_{r} < p_{r} ≤ s_{r} and again we have found a smaller representative contradicting the minimality of s(U).

This theorem proves that the algorithm can reject non-canonical union-closed sets and is a correct orderly algorithm, but the cost of the canonicity test would make it impossible to determine the number of union-closed sets for Ω_{7}.

For a given union-closed set U with universe Ω_{n} and 1 ≤ m ≤ n we write U_{m} for the subset containing all sets of size k ≥ m and Π_{m}(U) for all permutations Π of Ω_{n} with the property that Π(U_{m}) = U_{m}.

Lemma 5. Let U ≠ {Ω_{n}, ∅} be a non-canonical union-closed set for the universe Ω_{n} with sets A_{1} < A_{2} < ⋯ < A_{k} < ∅, so that {A_{1}, A_{2}, …, A_{k−1}, ∅} is canonical and |A_{k}| = m. Then all permutations Π with s(Π(U)) < s(U) are in Π_{m+1}(U).

Proof. Any permutation Π not in Π_{m+1}(U) would by definition give an isomorphic but different union-closed set Π(U_{m+1}). As due to Theorem 4 s(U_{m+1}) is minimal, s(Π(U_{m+1})) would be larger and therefore also the part of the string of s(Π(U)) describing sets of size at least m + 1 would imply s(Π(U)) > s(U).

Lemma 5 speeds up the canonicity test dramatically: We start with a list of all n! permutations as Π_{n}(U). When testing canonicity of a union-closed set with the smallest set of size k < n, we only apply permutations from Π_{k+1}(U). During this application, we can already compute Π_{k}(U) by simply adding exactly those permutations to the initially empty set Π_{k}(U) that fix U. As we work with small sets, it is no problem to store and use the set of all group elements instead of just a set of generators.

The impact is immediately clear: the number of permutations that has to be computed is much smaller and as soon as some Π_{k}(U) contains only the identity — which happens very fast — no canonicity tests have to be performed, so that the total time for isomorphism checking is only about 7% of the total running time when computing union-closed sets for Ω_{6}.

2.1 The implementation

The algorithm was implemented in the computer language C. Next to an efficient algorithm, of course also implementation details are of crucial importance to be able to compute the results for Ω_{7}. We precomputed the action of all permutations on all sets, so that they could be applied very fast and used data structures that allow to check whether a set is contained in a union-closed set in constant time. Special functions were written that add sets with only one element. As no sets of smaller size are added, no updates of the automorphism groups are necessary and it turned out that at this stage it is also not efficient any more to remove sets from red(U) that are a superset of another element. Details on the implementation can best be seen in the code which can be obtained from the authors or the Journal of Integer Sequences.

2.2 Results

Tables 1 and 2 give the numbers of isomorphism classes of union-closed sets and Moore families as well as the numbers of labeled structures. Up to 5 elements the running times are less than 0.01 seconds. For n = 6 it is 8.2 seconds on a Xeon(R) CPU E5-2690 0 running with 2.90 GHz and a high load (which can make a difference for these processors). For n = 7 the jobs were run in parallel on different machines and some parts had to be divided further in order to finish, so it is hard to give precise times. Estimating the total running time from those parts that were run on the same machine used for n = 6, the total time on this type of machine should be around 10 to 12 CPU-years.

n union-closed sets  labeled union-closed sets
1  1  1
2  3  4
3  14  45
4  165  2,271
5  14,480  1,373,701
6  108,281,182  75,965,474,236
7 2,796,163,091,470,050 14,087,647,703,920,103,947

Table 1: The number of union-closed sets (sequence \underline{A108798}) and labeled union-closed sets (sequence \underline{A102894}).

n  Moore families  labeled Moore families
1  2  2
2  5  7
3  19  61
4  184  2480
5  14,664  1,385,552
6  108,295,846  75,973,751,474
7 2,796,163,199,765,896 14,087,648,235,707,352,472

Table 2: The number of Moore families (sequence \underline{A193674}) and labeled Moore families (sequence \underline{A102896}).

A union-closed set on n elements is called sparse if the average number of elements in a set — not counting the empty set — is at most \frac{n}{2}. For union-closed sets that are not sparse, the union-closed sets conjecture is trivially true. Table 3 gives the number of sparse unionclosed sets. These numbers were computed once by filtering all union-closed sets and once by an independent implementation using special bounding criteria described in [5]. Bruhn and Schaudt [3] give indications that sparse union-closed sets make up only a vanishingly small part of all union-closed sets. The numbers of sparse union-closed sets for n ≤ 7 support this. Nevertheless also for sparse union closed sets the numbers seem to grow so fast that even with specialized algorithms complete enumeration will not be possible for sizes of the universe that are interesting for the union-closed sets conjecture.

n sparse union-closed sets
1  0
2  0
3  0
4  2
5  27
6  3,133
7  5,777,931

Table 3: The number of sparse union-closed sets (sequence \underline{A299116}).

2.3 Testing

The second author [5] developed an independent implementation of the algorithm together with special bounding criteria for sparse union-closed sets. The implementation was used to generate all isomorphism classes of union-closed sets for Ω_{1}, …, Ω_{6}, and — using special bounding criteria — to confirm the numbers of isomorphism classes of sparse union-closed sets for Ω_{7}.

A further and independent confirmation of the numbers for Ω_{1}, …, Ω_{6} and also an independent confirmation for Ω_{7} was obtained by computing the number of labeled structures corresponding to each representative from the size of the automorphism group. Note that as the size of the automorphism group is known in the algorithm anyway, the additional cost for this test can be neglected. From this we computed the number of (labeled) Moore families and got complete agreement with [4] for Ω_{1}, …, Ω_{7}. Due to the completely different approaches this makes implementation errors leading to the same incorrect results in both cases extremely unlikely.

3 Acknowledgments

We thank Craig Larson for introducing us to these interesting structures and for interesting discussions. Furthermore, we thank Anastasiia Zharkova and Mikhail Abrosimov. The first version of this algorithm was intended as a hands-on example to illustrate isomorphism rejection techniques in a course they attended at Ghent University. Without their visit, this algorithm might not have been developed.

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 Science 51 (2000), 25–38.

[2] H. Bruhn and O. Schaudt, The journey of the union closed sets conjecture. Graphs and Combinatorics 31(6) (2015), 2043–2074.

[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.

[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.

[5] R. Deklerck, Een constructief algoritme voor union closed sets, Master’s thesis, Ghent University, 2016.

[6] I. A. Faradžev, Constructive enumeration of combinatorial objects, Colloques Internationaux C.N.R.S. No. 260 — Problèmes Combinatoires et Théorie 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.

[8] A. Higuchi, Lattices of closure operators, Discrete Math. 179 (1998), 267–272.

[9] R. C. Read, Every one a winner, Ann. Discrete Math. 2 (1978), 107–120.

2010 Mathematics Subject Classification: Primary 05-04; Secondary 05A15 Keywords: enumeration, Moore set, union-closed set.

(Concerned with sequences \underline{A102894}, \underline{A102896}, \underline{A108798}, \underline{A193674}, and \underline{A299116}.)

Received November 20 2017; revised version received February 5 2018. Published in Journal of Integer Sequences, February 8 2018.

Return to Journal of Integer Sequences home page.