An antimatroid (also called a learning space) is a family of sets closed under union, such that for every nonempty set in the family there is an element that can removed to produce another set in the family. It turns out that, for any antimatroid A except powersets, there is a set S on the same elements that can be added to A to make a larger augmented antimatroid.

( Proof sketch )

This proof can be turned into a deterministic algorithm for choosing a specific augmentation out of all the possible ones. If one considers the augmented antimatroid to be the parent of the original antimatroid, this parent relation forms a tree with the powerset at its root:



We can then generate all the possible antimatroids using reverse search, which is just a fancy phrase for an algorithm that explores a tree like this one by reversing the parent relation. The time per antimatroid generated, over a k-element universe, is polynomial in 2^k, not bad since the number of antimatroids generated is double-exponential in k.

I implemented this in Python, from which I generated the 22 families in the tree of 3-element antimatroids above, matching some hand calculations I'd done previously. My program also found 485 antimatroids over 4 elements and 59386 over 5 elements, but I am a little distrustful of these numbers since the program is intricate and painful to debug. Unfortunately I couldn't find anything about this enumeration problem in the OEIS or with Google, so I'm at a bit of a loss for how to check these results; I suppose I could at least enumerate all 2¹⁶ 4-element set families and test which ones are antimatroids.

If the pattern of number of antimatroids being roughly 2^2k - 1 holds, the program as it stands should be able to list all 6-element antimatroids in about a month of laptop time, but I suspect reimplementation in a faster language and/or running it on a faster machine should speed that up significantly, to closer to a single day.

ETA 6/19: This much shorter program for brute-force testing all 2¹⁶ 4-element set families produces exactly the same output as my reverse search, so I am now much more confident in the reverse search results.

ETA2 6/20: Now up on the OEIS.

Golly is a cross-platform cellular automaton simulator that incorporates hashlife algorithms, allowing it to simulate most Game of Life patterns for astronomical numbers of generations quickly. Version 1.0 was just released, and now also incorporates Python scripting, allowing the construction of astronomically complex patterns via modular high level programming rather than bit-at-a-time copy and pasting.

For instance, here is bricklayer.py, a pattern first found by David Bell in 2002 that is formed by combining two p22 oscillators to make a gun, combining three p22 guns to make a p154 gun, and combining two p154 guns with a p7 glider reflector and a messy small Life pattern called "lumps of muck". By itself, lumps of muck forms two subpatterns that, individually, would themselves turn back into LoM again, but unfortunately interfere with each other creating a mess. The streams of gliders from the two guns and reflector repeatedly hit the back subpattern, creating a block and allowing the other subpattern to grow without interference, effectively pushing the LoM forward diagonally at each step. It ends up forming two long diagonal sequences of blocks, with the guns at one end of the sequence, the LoM on the other, and the gliders running down the middle.

( Python )

And here it is in the previously standard form for such patterns, a run-length-encoded text file:

( RLE )

If you want to see the pattern itself within Golly, either one works equally well, but I think you can see which one is more human readable and modifiable as source code.

This is making me think the push-pull replicator-based spaceships that should exist in HighLife and B368/S12578 may be within reach of construction now...