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.
Years -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine
Semi-automatically filtered from a common source file.