# Zigzags on Interval Greedoids

**Minisymposium:**
GENERAL SESSION TALKS

**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.