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.

antimatroids1

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)

 

Advertisements

2 responses to “Enumeration of Antimatroids, part I

  1. Pingback: Enumeration of Antimatroids, part II | ParaCombinatorics

  2. Pingback: Enumeration of Antimatroids, part IV | ParaCombinatorics

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s