# Enumeration of Antimatroids, part I

Recently I found an interesting problem: enumeration of possible antimatroids over finite set.

From combinatorial point of view, an antimatroid is a family of sets, with special properties.
Following the wikipedia definition, $F$ is an antimatroid iff:

• $F$ is closed under unions, that is: $\forall_{u,v \in F} u \cup v \in F$
• $F$ is a nonempty accesible: $\forall_{u \in F} ((u = \emptyset) \vee (\exists_{a \in u} u \setminus \{a\} \in F))$

For example, following family is an antimatroid:
$\{\{\},\{0\},\{2\},\{0,1\},\{0,2\},\{1,2\},\{0,1,2\}\}$
From now, I will denote the largest set, being also a superset of every other one in the family, as $S$ (so in previous example, $S=\{0,1,2\}$).

Just as matroids are generalization of antichains, antimatroids are generalization of chains.

As explained in blognote, one can prove usefull theorems about antimatroids:

Theorem:
For every antimatroid $F \not= 2^S$, there exists $u \not\in F$, that $F\cup u$ is also an antimatroid.

The proof given is constructive (I will omit it here). In fact, it gives us construction of a deterministic function $u = add(F)$.
This theorem gives us already two powerful properties to generate every possible antimatroid:

1. Starting with powerset, we can, by eliminating sets, be able to generate every possible antimatroid, all the time operating only on antimatroids.
2. We can eliminate duplicates, by verifying at every step $F' = F \setminus u$, if $u = add(F')$, and discarding $F'$ otherwise (it will be generated from other $F$ anyway)

We can use facts 1 and 2 to construct and search via DFS a tree containing every possible antimatroid.

Example of DFS tree for $n=3$.

According to the blogpost already cited, it is enough for enumeration up to n=5, giving results:

1, 1, 3, 22, 485, 59386

for n=0:
$\{\{\}\}$
for n=1:
$\{\{\},\{0\}\}$
for n=2:
$\{\{\},\{0\},\{0,1\}\}$
$\{\{\},\{1\},\{0,1\}\}$
$\{\{\},\{0\},\{1\},\{0,1\}\}$

But can we do better, and calculate following values (n=6, n=7)?
I will provide more details soon! (part 2)