# 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, ...

But first, let us fix the universum to be: $S = \{0,1,\ldots,n-1\}$.

Ok, so how do we start? By… ignoring the observation (2). Basically, the procedure to generate the unique father in the DFS tree looks very costly:

Proof sketch: Let U be the union of the sets in A, and by removing elements one at a time from U find T and x such that the sets between T u {x} and U form a powerset but the sets between T and U do not. If U \ {x} is in A, then one can continue recursively in the subantimatroid between T and U \ {x}; otherwise we can choose S to be a one-element extension of the largest set in A between T and U \ {x}.

(Ok, I admit, I am lazy and it looks complicated..)

So, if we have no way to prevent duplicates, we have to detect them by ourselves. So we will traverse the DAG of antimatroids (it is no longer a tree) with a BFS algorithm. We will process at one time every antimatroid of size $k$, and generate all of size $k-1$, starting with the maximal one, of size $2^n$ (minimal possible size is $n+1$, and there are $n!$ different minimal ones).

DAG of antimatroids for $n=3$.(tree edges in bold)

So, let’s do some coding here!
Every antimatroid will be represented just as a bitmask, with $N=2^n$ bits. If we want to crank $n=6,7$, we need 128-bit type. Some architectures and C++ compilers have them, but I was in unfortunate position not to have. So I quickly wrote

class u128
{
public:
unsigned long long low;
unsigned long long high;
...


with all important bitset functions, |, &, ~, …
(looking from a perspective, I could use bitset, but what’s done was done..)

Our structure of a program would be:

u128 seed;
for(int i=0;i
vector L(1,seed); //one bitmask with N bits on
unsigned long long ans = 0;
while(!L.empty())
{
ans += L.size();
cerr << L.size() << endl;
L = onestep(L);
}
cout << ans << endl;


So, only part missing is the magic of onestep().

How do we process single antimatroid?
We could just try to remove every possible bit, and test if the candidate is a valid antimatroid after this.
But this seems like a unnecessary effort, so let us just try and generate every valid candidate for removal at once (preferably in one big bitmask).
So we should look for bits that are on, but:

1. when removed, would violate set union closedness
2. or, would violate accessibility

We can solve (1) considering minimal generating set for given family of sets that makes one anitmatroid.
If we consider following operations on family of sets:
$S(F) = \{ u \cup v : u \in F, v \in F, u \not\subseteq v, u \not\supseteq v \}$ (every set that can be obtained as nontrivial sum of two sets from F)
$S'(F) = S(F) \cup F$ (as above, but also the trivial ones)
then minimal fixed point of operation $S'$ is closure under set sum. (it really mean iterating $S'(S'(S'(\ldots S'(F)\ldots )))$ until nothing new can be added)

So given any family of sets, we can take a closure. And it works other way around:
$H = F - S(F)$ will be minimal generating set (I’ll omit proof).

In terms of code:

u128 mask;
for(int I=1;I<N-1;I++)
if(S.getbit(I))
for(int J=1;J<I;J++)
if(S.getbit(J))
if((I|J) != I && (I|J) != J)


Ok, so for (2), we can precompute, for every pair of values between $0, N$, if they differ on just one bit. In fact, we can generate it as a boolean matrix $N\times N$:

vector pred(N);
vector succ(N);
for(int I=0;I<N;I++)
for(int i=0;i
if(I & (1<<i))
pred[I].setbit(I & ~(1<<i));
else
succ[I].setbit(I | (1<<i));


pred[I][J] keeps information if J is smaller by exactly one bit than I, and succ[I][J] if J is larger by one bit than I.

We can think of this in terms of supporting relation.
If bits I and J are on in S, and I is smaller by 1 bit than J, then I is supporting J. In a valid antimatroid (mask), every set (bit) has to be supported, except from $\{\}$ (0th bit).
It is easy to test if given bitmask S passes the condition (2):

u128 succ_closure;
for(int I=0;I<N;I++)
if(S.getbit(I))
succ_closure |= succ[I];
succ_closure.setbit(0);
assert((succ_closure & S) == S);


(if we consider succ as a matrix, vector (S) $\times$ matrix (succ) multiplication, but instead of $+, \times$, we have $\vee, \wedge$)

It is a little bit harder to get every position that could violate supporting condition. First, we need to generate every position, that is supported by exactly one other position. How to do this? Well, we could get every position that is supported by at least one position, and substract all that are supported by more than one:

u128 f1,f2;
for(int I=0;I<N;I++)
if(S.getbit(I))
{
f2 |= succ[I] & f1;
f1 |= succ[I];
}
u128 R = f1 & ~f2 & S;


Now, R contains all the bits supported by exactly one other bit.
What to do next? Well, now we will use the prev matrix, with the same vector $\times$ matrix binary multiplication.

for(int I=0;I<N;I++)
if(R.getbit(I))


After all of this trickery, mask should contain only bits that are OK to switch off to get smaller antimatroid. Now we can happily iterate over them, and put those masks into hashtable, that will eliminate all the duplicates for us.

Let us see how is it running!

For $n=5$, it gives:

$time ./run1 59386 real 0m1.723s user 0m0.756s sys 0m0.912s  So, it gave correct answer (yes, I verified, for all smaller $n$ it was also correct!) Can we try it with $n=6$? $time ./run1
133059751

real	17m26.972s
user	16m54.863s
sys	0m9.221s


So we have another term!
Also, interesting are the numbers of antimatroid of fixed size (we get them here as a byproduct of computation).
 1 6 30 75 240 690 1806 4070 8370 15600 27960 47712 80190 130710 209220 325830 493986 729210 1046220 1454400 1959540 2561607 3245430 3973170 4698510 5367570 5947746 6408015 6751640 6976140 7111290 7157832 7132710 7015665 6813540 6509370 6135150 5686830 5190030 4635450 4043220 3415980 2790720 2181120 1627260 1150770 777330 500760 310380 183980 105240 58020 30960 15960 8010 3960 1800 720 

We start with 1 antimatroid of size 64, and end with 720=6! antimatroids of size 7.

Can we try this approach to get the answer for $n=7$? Not really.
If we use some numerology of double exponential growth we expect here, we can observe that the logarithm of answer grows exponentially, by 1.7 at each step. That gives expected answer around $\approx 6\cdot 10^{13}$. With some huge CPU available it could be doable, but the problem lies in ability to store groups of 128bit = 16byte bitmasks containing around $10^{12}$ elements at once.
In following post I will show how to work around it!

(Sourcecode used above is available here.)