David Eppstein – Publications

Publications with Veitt Wiechert

• Antimatroids and balanced pairs.
  D. Eppstein.
  arXiv:1302.5967.
  Order 31 (1): 81–99, 2014. Erratum (with V. Wiechert).

  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.