\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\red}{{\mbox{red}}}
\newtheorem{algo}{Algorithm}
\begin{center}
\vskip 1cm{\LARGE\bf Generation of Union-Closed Sets and \\
\vskip 0.1in
Moore Families} \\
\vskip 1cm
\large
Gunnar~Brinkmann and Robin Deklerck\\
Applied Mathematics, Computer Science and Statistics\\
Ghent University\\
Krijgslaan 281 S9\\
B9000 Ghent\\
Belgium\\
\href{mailto:gunnar.brinkmann@ugent.be}{\tt gunnar.brinkmann@ugent.be}\\
\href{mailto: robindeklerck@skynet.be}{\tt robindeklerck@skynet.be}.
\end{center}
\vskip .2 in
\begin{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\le 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.
\end{abstract}
\section{Introduction}
All sets in this article are finite. A {\it union-closed set\/}
is a set ${\cal U}$ of sets
with the property that for all $A,B\in {\cal U}$ we have $A\cup
B\in {\cal U}$. We call $\Omega_{{\cal U}}=\bigcup_{A\in {\cal U}}A$ the
{\it universe\/}
of ${\cal U}$. Two union-closed sets with universe $\Omega_{{\cal U}}$, resp., $\Omega_{{\cal U}'}$
are defined to be {\it isomorphic\/} if there is a bijective mapping
$\Omega_{{\cal U}} \to \Omega_{{\cal U}'}$ inducing a bijection between the
union-closed sets.
As we are mainly interested in isomorphism classes, we may assume
$\Omega_U= \Omega_n=\{1,\ldots ,n\}$ for some $n$. While the whole
universe
$\Omega_U$ is by definition an element of a union-closed set ${\cal 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 $\Omega_n$
as well as the empty set. We denote a set containing one representative
of each isomorphism class of union-closed sets with universe $\Omega_n$ as ${\cal R}_n$.
The famous {\em union-closed sets conjecture} (or {\em 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 \cite{UCSsurvey} 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 {\em Moore families}. A Moore family
for a universe $\Omega_n$ is a set of subsets of $\Omega_n$
that is closed under intersection and contains $\Omega_n$. It is easy to
see that for a union-closed set ${\cal U}$ the set ${\cal U}^c=\{\Omega_n\setminus A | A \in {\cal U}\}$
is a Moore family. For a Moore family ${\cal M}$ the set ${\cal M}^c=\{\Omega_n\setminus A | A \in {\cal M}\}$
is closed under union, but as the empty set is not necessarily contained in ${\cal M}$, it is a
union-closed set for $\Omega_n\setminus \bigcap_{A\in \cal M} A$, which is isomorphic to a union-closed set for some
$\Omega_{n'}$ with $n'\le n$.
A set ${\cal M}_n$ of representatives of Moore families (with the
canonical definition of isomorphism) for the universe $\Omega_n$ can be
obtained from sets $ {\cal R}_0, \ldots , {\cal R}_n$ of representatives
of union-closed sets containing the empty set as follows:
${\cal M}_n=\bigcup_{i=0}^n \{ {\cal U}^c | {\cal U}\in {\cal R}_i\}$
if the complement is in each case taken in the universe $\Omega_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 \cite{Moorefamilies7, Moorefamilies6,Moorefamilies5}.
In the most advanced article,
Colomb, Irlande, and Raynaud \cite{Moorefamilies7}
not only counted Moore families for $n\le 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\le 7$.
This gives a very good independent test
for the implementation in \cite{Moorefamilies7} as well as for our implementation.
When computing the number of labeled Moore families for $\Omega_7$ from the
number of labeled union-closed sets with $n\le 7$, for those union-closed sets with $n< 7$,
one must take into account that for $\Omega_7$ isomorphic copies not only occur for
the universe $\{1,\ldots ,n\}$, but for each $n$-element subset of $\{1,\ldots ,7\}$.
\section{The algorithm}
A subset $A \subseteq \Omega_n$ is represented as a number
$b(A)$ given as the binary number $b_{n-1}\cdots b_0$ --- possibly with leading zeros --- with $b_i=1$
if $(i+1)\in A$ and $b_i=0$ otherwise.
We use an ordering of the subsets of $\Omega_n$. For $A,B \subseteq \Omega_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 {\em larger} or {\em smaller} sets, we refer
to this ordering.
The construction algorithm generates union-closed sets recursively based on
the following easy lemma:
\begin{lemma}
If ${\cal U} \not= \{\Omega_n\}$ is a union-closed set and $A$ is the largest
non-empty element
in ${\cal U}$, then ${\cal U}\setminus \{A\}$ is also a union-closed set.
\end{lemma}
This implies that union-closed sets for universe $\Omega_n$ can be recursively constructed
from the union-closed set $\{\Omega_n,\emptyset\}$ of smallest size by successively adding subsets of $\Omega_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:
\begin{description}
\item[(i)] The test whether the set that has been constructed by adding a new set
is closed under union.
\item[(ii)] The test for isomorphisms.
\end{description}
We first discuss (i). A straightforward way to test (i) for a union-closed set ${\cal U}$ to which a new
set $A$ is added would be to form all unions $A\cup B$ with $B\in {\cal U}$ and test whether
they are in ${\cal U}\cup \{A\}$. Although all these steps can be
implemented as efficient bit-operations, their number would slow down
the program. We make the following definition.
\begin{definition}
For a union-closed set ${\cal U}$ we
define the reduced set $\red({\cal U})$ as follows:
$$\red({\cal U})=\{ A\in {\cal U} | A\not= \emptyset \mbox{ and there is no }A_1\not= \emptyset \mbox{ in } {\cal U}, A_1\subsetneq A\}.$$
\end{definition}
\begin{lemma}
Let ${\cal U}$ be a union-closed set for a universe $\Omega_n$ and let $A\subset \Omega_n$,
that is larger than any non-empty set in ${\cal U}$.
Then ${\cal U}\cup \{A\}$ is closed under union if and only if
$A\cup B\in {\cal U}$ for all $B\in \red({\cal U})$.
\end{lemma}
\begin{proof}
First assume that ${\cal U}\cup \{A\}$ is closed under union
and let $B\in \red({\cal U})$.
Then $A\cup B\in ({\cal U}\cup \{A\})$ and
as $A$ is larger than $B$, we have $A\cup B \not= A$, so $A\cup B\in {\cal U}$.
For the other direction assume that
$A\cup B\in {\cal U}$ for all $B\in \red({\cal U})$ and let
$D\in {\cal U}$.
Choose any $D'\subset D$ so that $D'\in \red({\cal U})$. Then $A'=A\cup D'\in {\cal U}$
and therefore also $A'\cup D \in {\cal U}$ as ${\cal U}$ is closed under union, but
$A'\cup D = A\cup D$ --- so $A\cup D\in {\cal U}\cup \{A\}$ and
${\cal U}\cup \{A\}$ is closed under union.
\end{proof}
It would be inefficient to compute $\red({\cal U})$ each time a new union-closed set is constructed,
but as a new union-closed set ${\cal U}'$ is constructed by adding a new smallest element $A$ to
${\cal U}$, the set $\red({\cal U}')$ can easily be constructed from $\red({\cal 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 $\Omega_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{\v z}ev type orderly generation
\cite{Fa76, Read78} and the homomorphism principle (see, e.g., \cite{B98}).
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 ${\cal U}$ with $k+1$ elements $A_1j$ then $p'_i=p_i=s_i$ for $1\le i s({\cal U})$.
\end{proof}
Lemma~\ref{lem:homomorph} speeds up the canonicity test dramatically:
We start with a list of all $n!$ permutations as $\Pi_n({\cal U})$.
When testing canonicity of a union-closed set with the smallest set of size $k