2002-07: Expected rank in antimatroids

DIMACS TR: 2002-07

Expected rank in antimatroids

Authors: Gary Gordon

ABSTRACT
We consider a probabilistic antimatroid $A$ on the ground set $E$, where each element $e \in E$ may succeed with probability $p_e$. We focus on the expected rank $ER(A)$ of a subset of $E$ as a polynomial in the $p_e$. General formulas hold for arbitrary antimatroids, and simpler expressions are valid for certain well-studied classes, including trees, rooted trees, posets, and finite subsets of the plane. We connect the Tutte polynomial of an antimatroid to $ER(A)$. When $S$ is a finite subset of the plane with no three points collinear, we derive an expression for the expected rank which has surprising symmetry properties. Corollaries include new formulas involving the beta invariant of subsets of $S$ and new proofs of some known formulas.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-07.ps.gz

DIMACS Home Page