A $\beta$ Invariant for Greedoids and Antimatroids

Gary Gordon

Abstract


We extend Crapo's $\beta $ invariant from matroids to greedoids, concentrating especially on antimatroids. Several familiar expansions for $\beta (G)$ have greedoid analogs. We give combinatorial interpretations for $\beta (G)$ for simplicial shelling antimatroids associated with chordal graphs. When $G$ is this antimatroid and $b(G)$ is the number of blocks of the chordal graph $G$, we prove $\beta (G)=1-b(G)$.


Full Text: PDF