I'm in Karlsruhe for Graph Drawing 2006. The first day had many interesting talks; my own (in the session on tree drawing) seemed to go well, and I've put the slides online here.

( Non-crossing configurations and partial cube flip graphs )

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.

From any partition of n, one can get a partition of n - 1, by subtracting one from the last value in the partition and removing it if it becomes zero. Connecting any two partitions related in this way forms an infinite tree, in which the nodes on level n represent the partitions of n:

( Read more... )

On the other hand, there's another way to form a finite tree out of the partitions of n only: from any partition with two or more values in it, form a shorter partition in which the largest two values in the partition have been replaced by their sum, and connect the pairs of partitions so related.

( Read more... )

It looks like a depth first preorder traversal of this tree should provide an efficient generator for partitions in reverse colexicographic order, and a depth first post-order traversal of the reversed tree should generate partitions in colexicographic order. Terminating these traversals early would list the partitions using only values larger than some cutoff, or the partitions that use at least one value below the cutoff. The maximum value in a partition decreases as we progress down the tree, so we can list all partitions that have maximum larger than some cutoff by traversing the subtree they form. Breadth first traversal would list partitions in order by their length, but I don't know how to do this in a way that's efficient both in time and in space; iterative deepening (or the equivalent self-recursive BFS) doesn't work so well because the tree has too many of its nodes too close to the root. Instead, to list partitions in order by their length, efficiently, one can use Hindenburg's algorithm described by Knuth for listing partitions of each possible length, separately, but unfortunately I don't know of a nice way of relating this to tree traversals...

Today's mail included the latest fascicle of Knuth's AOCP volume 4, so rather than getting any real work done I had some fun implementing the partition generation algorithms he lists; I added the resulting implementation to PADS. Knuth gives a nonrecursive algorithm for listing all partitions of n in revlex order, in constant time per partition, but doesn't seem to mention the similarly efficient recursive algorithm, which I first encountered two years ago, and which can be trivially modified to produce either lex or revlex order. Unless it's buried in the exercises somewhere... I included both algorithms in my implementation. Note that the ASPN version of the recursive algorithm takes O(n) time per partition, because it copies the list each time, but this can easily be reduced to O(1) per partition as I do in the new implementation.

I also added a readme file putting PADS into the public domain, and a tarball for easier downloading of the whole library.