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

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 , and generate all of size , starting with the maximal one, of size (minimal possible size is , and there are different minimal ones).

So, let’s do some coding here!

Every antimatroid will be represented just as a bitmask, with bits. If we want to crank , 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:

- when removed, would violate
*set union closedness* - 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:

(every set that can be obtained as nontrivial sum of two sets from F)

(as above, but also the trivial ones)

then minimal fixed point of operation is *closure* under set sum. (it really mean iterating until nothing new can be added)

So given any family of sets, we can take a closure. And it works other way around:

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) mask.setbit(I|J); mask = S & ~mask;

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

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) matrix (succ) multiplication, but instead of , we have )

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 matrix binary multiplication.

for(int I=0;I<N;I++) if(R.getbit(I)) mask = mask & ~pred[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 , 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 it was also correct!)

Can we try it with ?

$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 ? 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 . With some huge CPU available it could be doable, but the problem lies in ability to store groups of 128bit = 16byte bitmasks containing around elements at once.

In following post I will show how to work around it!

(Sourcecode used above is available here.)

Pingback: Enumeration of Antimatroids, part I | ParaCombinatorics

Pingback: Enumeration of Antimatroids, part III | ParaCombinatorics

Pingback: Enumeration of Antimatroids, part IV | ParaCombinatorics

I think you should replace < with < in several places in the article (and & instead of &), because the code looks messed up!

…and the damn coder of this comments plugin also didn’t get html entities correctly. Obviously I’ve meant & l t ; and & a m p ;

Can you point me to where should I replace and from what to what? ‘ ‘& l t’ or ‘& l t’ -> ‘<' ?

And I admit, the editor messes it constantly, if you save a draft without properly closing enviroment, evertything inside is processed and '<' is replaced with '& l t' and so on..