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, ).
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.
According to the blogpost already cited, it is enough for enumeration up to n=5, giving results:
1, 1, 3, 22, 485, 59386
But can we do better, and calculate following values (n=6, n=7)?
I will provide more details soon! (part 2)