David Eppstein – Publications

Publications with Veitt Wiechert

Antimatroids and balanced pairs.
D. Eppstein.
arXiv:1302.5967.
Order 31 (1): 81–99, 2014, doi:10.1007/s11083-013-9289-1. Erratum (with V. Wiechert), doi:10.1007/s11083-014-9335-7.

We generalize the 1/3-2/3 conjecture, according to which every partial order should have a pair of items that are nearly equally likely to appear in either order in a random linear extension, to antimatroids, and we prove it for several specific types of antimatroid.