Tag Archives: Antimatroid

Enumeration of Antimatroids, part IV

I promise to finish this topic with this post! (part 1, part 2, part 3)

We ended with a rather efficient (but still double exponential) code that gave us hope to extend the sequence a little bit further. So, what can we improve? Constant, a little, by efficient parallelisation.
Continue reading


Enumeration of Antimatroids, part III

Let us continue the fun we had before here.

How do we speed up the calculation? Well, we need to limit somehow the space on which we perform the search.
Very obvious way is to eliminate the symmetries. Every permutation \pi \in S_n : \{0,1\ldots,n-1\} \to \{0,1\ldots,n-1\} induces a natural transformation on sets (and sets of sets, like antimatroids, …). For example:
\sigma = (120) = \{ 0 \to 1; 1 \to 2; 2 \to 0 \}
working on :
F = \{ \{\}, \{0\}, \{0,1\}, \{0,2\}, \{0,1,2\} \}
\sigma(F) = \{ \{\}, \{1\}, \{1,2\}, \{1,0\}, \{1,2,0\} \} = \{ \{\}, \{1\}, \{1,2\}, \{0,1\}, \{0,1,2\} \}
Continue reading

Enumeration of Antimatroids, part II

As explained before, we would like to extend the following sequence A119770 (don’t click, it will spoil all the fun!):
1, 1, 3, 22, 485, 59386, ...
Continue reading

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:
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.
Continue reading