# Antimatroids and Balanced Pairs

I have a new preprint out, "Antimatroids and Balanced Pairs", arXiv:1302.5967.

A partially ordered set (or almost equivalently a directed acyclic graph) can often be used as a concise representation of a much larger set of linear orderings on a set of elements (the linear extensions of the partial order or the topological orderings of the DAG). But my feeling is that, in many cases where this has been done, it is worthwhile to consider generalizing partial orders to antimatroids, and generalizing the linear extensions of the partial order to the basic words of an antimatroid. In this way, you get to represent sets of orderings that would not be possible to represent by partial orders, while still retaining enough structure to be able to prove interesting things about these sets. (My older preprint "Learning Sequences" is related, but sort of the opposite, as it is instead about using sets of linear orderings to represent antimatroids.)

This paper is part of this program of replacing partial orders by antimatroids. It considers the 1/2–2/3 conjecture, an unsolved problem about partial orders according to which, if you choose a linear extension at random, then there should be a pair of elements that are nearly equally likely to be in either possible order relative to each other. Of course, it's not any easier to prove this for antimatroids than it is for partial orders, but as far as I can tell it's also true when generalized in this way. The paper provides proofs that several types of antimatroids obey the conjecture, along the way simplifying the proofs of some of the results on partial orders that it generalizes, and it reports on a computer search (using the algorithms I described here) by which I verified that all antimatroids on six or fewer elements obey the conjecture.