## 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