Antimatroids and Balanced Pairs |
| |
Authors: | David Eppstein |
| |
Institution: | 1. Computer Science Department, University of California, Irvine, Irvine, CA, USA
|
| |
Abstract: | We generalize the $\frac{1}{3}$ – $\frac{2}{3}$ conjecture from partially ordered sets to antimatroids: we conjecture that any antimatroid has a pair of elements x,y such that x has probability between $\frac{1}{3}$ and $\frac{2}{3}$ of appearing earlier than y in a uniformly random basic word of the antimatroid. We prove the conjecture for antimatroids of convex dimension two (the antimatroid-theoretic analogue of partial orders of width two), for antimatroids of height two, for antimatroids with an independent element, and for the perfect elimination antimatroids and node search antimatroids of several classes of graphs. A computer search shows that the conjecture is true for all antimatroids with at most six elements. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|