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, is an antimatroid iff:

- is
*closed under unions*, that is:
- is a
*nonempty* *accesible*:

For example, following family is an antimatroid:

From now, I will denote the largest set, being also a superset of every other one in the family, as (so in previous example, ).

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 , there exists , that is also an antimatroid.

The proof given is constructive (I will omit it here). In fact, it gives us construction of a deterministic function .

This theorem gives us already two powerful properties to generate every possible antimatroid:

- Starting with powerset, we can, by eliminating sets, be able to generate every possible antimatroid, all the time operating only on antimatroids.
- We can eliminate duplicates, by verifying at every step , if , and discarding otherwise (it will be generated from other 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 .

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:

for n=2:

But can we do better, and calculate following values (n=6, n=7)?

I will provide more details soon! (part 2)

### Like this:

Like Loading...

Pingback: Enumeration of Antimatroids, part II | ParaCombinatorics

Pingback: Enumeration of Antimatroids, part IV | ParaCombinatorics