Zigzags on Interval Greedoids

Yulia Kempner
Holon Institute of Technology

Vadim E. Levit
Ariel University



Content: The pivot operation, i.e., exchanging exactly one element in a basis, is one of the fundamental algorithmic tools in linear algebra. Korte and Lov\'{a}sz introduced a combinatorial analog of this operation for bases of greedoids. Let $X,Y$ be two bases of a greedoid $(U,\mathcal{F})$ such that $\left\vert X-Y\right\vert =1$ and $X\cap Y\in\mathcal{F}$. Then $X$ can be obtained from $Y$ by \textit{a pivot operation} where the element $y\in Y-X$ is pivoted out and the element $x\in X-Y$ is pivoted in. We extend this definition to all feasible sets of the same cardinality and introduce \textit{lower and upper zigzags} comprising these sets. A \textit{zigzag} is a sequence of feasible sets $P_{0},P_{1},...,P_{2m}$ such that: \emph{(i)} these sets have only two different cardinalities; \emph{(ii)} any two consecutive sets in this sequence differ by a single element. Zigzag structures allow us to give new metric characterizations of some subclasses of interval greedoids including antimatroids and matroids.

Back to all abstracts