\documentclass[12pt]{article}
\usepackage{amsfonts,amssymb}
\addtolength{\textwidth}{2cm}
\addtolength{\textheight}{3cm}
\addtolength{\oddsidemargin}{-1cm}
\addtolength{\topmargin}{-2cm}

\newcommand{\s}{{\succeq}}
\newcommand{\R}{{\mathbb R}}
\renewcommand{\a}{{\alpha}}
\renewcommand{\b}{{\beta}}
\newcommand{\pg}{{\preceq_{\pi}}}
\newcommand{\A}{{\cal A}}
\newcommand{\p}{{\preceq}}
\newcommand{\Q}{{\cal Q}}
\renewcommand{\P}{{\cal P}}
\newcommand{\proof}{\noindent{\em Proof: }}
\newcommand{\ra}{\rightarrow}
\newcommand{\m}{\medskip}
\newcommand{\B}{\bigskip}
\newcommand{\qed}{\hspace{\fill}$\square$}

\renewcommand{\theequation}{\thesection.\arabic{equation}}
\newtheorem{theorem}[equation]{Theorem}
\newtheorem{lemma}[equation]{Lemma}
\newtheorem{prop}[equation]{Proposition}
\newtheorem{cor}[equation]{Corollary}
\newenvironment{remark}{\noindent\refstepcounter{equation}
{\bf Remark \theequation}}{\m}
\newenvironment{example}{\noindent\refstepcounter{equation}
{\bf Example \theequation}}{\m}
\newenvironment{question}{\noindent\refstepcounter{equation}
{\bf Question \theequation}}{\m}
\title{A Framework for the Greedy Algorithm}
\author{A. Vince\\Department of
Mathematics \\
University of Florida \\
Gainesville, FL 32611, USA \\
{\tt vince@math.ufl.edu}}
\date{}
\begin{document}

\maketitle

\begin{abstract} The classical setting for the greedy algorithm
is the theory of matroids.  Given a set system $M$ the greedy
algorithm correctly solves the associated optimization problem for all
weight functions if and only if $M$ is a matroid.  There are, however,
set systems $M$ that are not matroids, for which the greedy algorithm
nevertheless correctly solves the optimization problem - but not for
every weight function.  This is the case, for example, for the
symmetric matroids of Bouchet \cite{bou}, symplectic matroids of
Borovik, Gelfand and White \cite{BGW} and, more generally, the Coxeter
matroids of Gelfand and Serganova \cite{GS1,GS2}.  Our intention is to
put the greedy algorithm into a simple framework that includes such
examples, as well as ordinary matroids.  For any pair $(P, \P)$
consisting of a finite set $P$ together with a set $\P$ of partial
orderings of $P$, we define the concepts of {\it greedy set} and {\it
admissible function}.  On greedy sets, the greedy algorithm correctly
solves the naturally associated optimization problem for all
admissible functions.  Indeed, when $\P$ consists of linear orders,
the greedy sets are characterized by this property.  A geometric
condition sufficient for a set to be greedy is given in terms of roots
and the greedy polytope.

\smallskip\centerline{\bf R\'esum\'e}
Le cadre classique pour l'algorithme ``greedy'' est la th\'eorie des
matro\"{\i}des. Etant donn\'e un syst\`eme d'ensembles $M$,  l'algorithme
``greedy'' r\'esoud correctement le probl\`eme d'optimisation associ\'e pour
toute fonction de poids si et seulement si $M$ est un matro\"{\i}de.
Il existe cependant des syst\`emes d'ensembles $M$ qui ne sont pas des
matro\"{\i}des et pour lesquels l'algorithme ``greedy'' r\'esoud le probl\`eme
d'optimisation, mais pas pour toutes les fonctions de poids. Par exemple, c'est
le cas pour  les  matro\"{\i}des sym\'etriques de Bouchet \cite{bou}, les
matro\"{\i}des symplectiques  de Borovik, Gelfand et White \cite{BGW}, et plus
g\'en\'eralement les matro\"{\i}des de Coxeter  de Gelfand et Serganova
\cite{GS1,GS2}. Notre but est de placer l'algorithme ``greedy'' dans un cadre
plus simple qui comprend tous ces exemples, en plus des matro\"{\i}des
standards. Pour toute paire $(P, \P)$ d'un ensemble fini $P$ et d'un ensemble
$\P$ d'ordres  partiels sur $P$, nous d\'efinissons le concept {\it d'ensemble 
``greedy''} et de {\it fonctions admissibles}. Sur les ensembles ``greedy'',
d'algorithme ``greedy'' resoud correctement le probl\`eme d'optimisation
naturellement associ\'e pour toute fonction admissibles. En effet, si $\P$ est
l'ensemble des ordres lin\'eaires, alors les ensembles ``greedy'' sont
caract\'eris\'es par cette propri\'et\'e. Une condition g\'eom\'etrique
suffisante pour que l'ensemble soit ``greedy'' est donn\'ee en termes de racines
et de polytopes ``greedy''.
\end{abstract}


\section{Introduction} \label{intro}
Perhaps the best known algorithm in combinatorial optimization is the
greedy algorithm.  The classical MAXIMAL (MINIMAL) SPANNNING TREE
problem, for example, is solved by the greedy algorithm: Given a
finite graph $G$ with weights on the edges, find a spanning tree of
$G$ with maximum (minimum) total weight.  At each step in the greedy
algorithm that solves this problem, there is set of edges $T$
comprising the partial tree; an edge $e$ of maximum weight among the
edges not in $T$ (the greedy choice) is added to $T$ so long as $T+e$
contains no cycle.

A natural context in which to place the greedy algorithm is that of a
matroid.  Consider a pair $(P, \cal I)$ consisting of a finite set $P$
together with a nonempty collection $\cal I$ of subsets of $P$, called
{\it independent sets}, closed under inclusion.  There is a natural
combinatorial optimization problem associated with this pair.  Given a
weight function $f: P \rightarrow \R$, extend the {\it
weight} to subsets $A \subseteq P$ by defining $f(A) = \sum_{a\in A}
f(a)$.  \B

\underline{{\bf OPTIMIZATION PROBLEM.}} \,\, Given a weight
function $f: P \rightarrow \R$, find an independent set with the
greatest weight. \B

The {\it greedy algorithm} for this optimization problem is simply: \B

\underline{{\bf GREEDY ALGORITHM}}

\begin{tabbing}
xxx\=xxx\=\kill
$I = \emptyset$ \\
{\bf while} $P \neq \emptyset$ {\bf do} \\
\>remove from $P$ an element $a$ of largest weight. \\
\>{\bf if} $I\cup\{a\}$ is independent {\bf then} \\
\>\>$I =  I\cup\{a\}$ \\
\>{\bf end}\\
{\bf end} \\
\end{tabbing}

\vskip -.5cm
It is well known that the following statements are equivalent for the
pair $M = (P, \cal I)$.  Here $\cal B$ denotes the set of bases of
$M$, a {\it basis} being a maximum independent set.

\begin{enumerate}
\item $M$ is a matroid.
\item The greedy algorithm correctly solves the combinatorial
optimization problem associated with $M$ for any positive weight function
$f: P \rightarrow \R$.
\item Every basis has the same cardinality and, for every linear
ordering $\p$ on $P$, there exists a $B \in \cal B$ such that for any
$A \in \cal B$, if we write $B = (b_1,b_2,\dots,b_k)$ and $A=(a_1,
a_2, \dots, a_k)$ with the elements of $B$ and $A$ both in
increasing order, then $a_i\, \p \,b_i$ for all $i$.  This ordering
on $k$-element subsets of $X$ is called the {\it Gale order}.
\end{enumerate}

In the spanning tree problem, the set $P$ consists of the set of
edges of $G$ and the independent sets are the acyclic subsets of
edges. Many well known optimization problems, including the spanning
tree problem, can be put into the framework of matroids.  Texts by
Lawler \cite{lawler} and by Papadimitriou and Steiglitz \cite{pap}
contain numerous examples.

Matroids are characterized by the property that the greedy algorithm
correctly solves the optimization problem for any weight function.
There are, however, non-matroids, for which the greedy algorithm
correctly solves the optimization problem - but not for every weight
function.  This is the case for the symmetric matroids \cite{bou}, the
sympletric matroids \cite{BGW} and, more generally, the Coxeter
matroids of Gelfand and Serganova \cite{GS1,GS2}.  It is our intenton
in this paper to put the greedy algorithm into a simple framework that
includes such examples.

The basic notion is that of a pair $(P, \P)$ consisting of a finite
set $P$ together with a set $\P$ of partial orderings of $P$.  In
Section 2 the concepts of greedy set and admissible function are
defined and examples are given.  When $P = \{1,2, \dots , n\}$ and
$\P$ is the set of all linear orderings of $P$, the greedy sets are
exactly the bases of matroids.  Many of the pairs $(P, \P)$ of interest are
obtained by letting a group act on the poset $P$.  This group case is
introduced in Section 3.  In Section 4 we prove that, for greedy sets,
the greedy algorithm correctly solves the naturally associated
optimization problem for all admissible functions.  Indeed, when $\P$
contains only linear orders, the greedy sets are characterized by this
property.  In fact, it is proved in Section 4 that there is
essentially no loss of generality in assuming that $\P$ contains only
linear orders.  The results of Section 4 naturally lead to the problem
of effectively characterizing greedy sets.  A geometric approach via
roots and the greedy polytope is considered in Section 5.  It is
proved that if every edge of the polytope of a collection $L$ is
parallel to a root, then $L$ is a greedy set.

\section{Greedy sets} \label{greedy}
\setcounter{equation}{0}

Consider a pair $(P,\P)$ consisting
of a finite set $P$ and a set $\P$ of partial orderings of $P$.  A
subset $M \subseteq P$ will be called a {\it greedy set} for the pair
$(P,\P)$ if $M$ has a unique maximum for every ordering in $\P$.

Let $P_k$ denote the collection of $k$-element subsets of $P$.  Each
partial order on $P$ induces a partial order on $P_k$, namely the Gale
order.  If $A,B \in P_k$, then $A \,\p \, B$ in the {\it Gale order}
if there are orderings $A=(a_1, a_2, \dots, a_k)$ and $B =
(b_1,b_2,\dots,b_k)$ of the two sets such that $a_i\, \p \,b_i$ for
all $i$.  If $\p$ is an ordering in $\P$, then the same notation $A
\,\p \, B$ will be used for sets $A, B \in P_k$ related in the Gale
order.  The set of Gale orderings induced on $P_k$ by the orderings in
$\P$ will be denoted $\P_k$.  A greedy set for the pair $(P_k, \P_k)$
will be referred to as a {\it rank} $k$ {\it greedy set} for $(P,\P)$.

A weight function $f : P \rightarrow \R$ is called {\it compatible}
with a partial order $\p$ on $P$ if $f(a) < f(b)$ whenever
$a \,\prec \, b$.  (The notation $a \prec b$ means $a \,\p\, b$ but $a
\neq b$.)  A weight function $f$ is said to be {\it admissible} for
$(P,\P)$ if $f$ is compatible with some partial order in $\P$.  An
admissible weight function $f$ for $(P,\P)$ can be extended to an
admissible weight function $f: P_k \rightarrow \R$ for $(P_k, \P_k)$
by defining
$$f(A) = \sum_{a\in A} f(a).$$

\noindent That this function is indeed admissible is the statement of
the corollary below.  The first proposition below is obvious from the
definitions of greedy set and admissible weight function.

\begin{prop} \label{max} If $M \subseteq P$ is a greedy
set for $(P,\P)$ and $f$ is an admissible weight function, then $f$
attains a unique maximum on $M$.  \qed
\end{prop}

\begin{prop} \label{weight} Let $P$ be a partially ordered set
and $P_k$ the set of all $k$-element subsets of $P$ with the Gale
order.  For any $A,B \in P_k$ we have $B \,\p \, A$ if and only if $f
(B) \leq f (A)$ for every weight function $f$ compatible with the
order on $P$.
\end{prop}

\proof Assume that $B \,\p \, A$.  Then there are orderings $A = (
a_1, a_2, \dots, a_k )$ and $B = ( b_1, b_2, \dots, b_k )$ such that
$b_i \, \p \, a_i$, and hence $f(b_i) \leq f(a_i)$, for $1\leq i \leq
k$.  Therefore $f(B) = \sum_{b\in B} f(b) \leq \sum_{a\in A} f(a) =
f(A)$.

Conversely assume that it is not the case that $B \,\p \, A$.  We will
construct a function $f$ that is compatible with the order on $P$ but
$f(B) > f (A)$.  For each element $a \in A$, let $B_a = \{ x\in B
\, | \, x \p a \}$.  Now $B \,\p\, A$ in the Gale order if and only if
there is a set of distinct representatives of the sets $B_a, a \in A$.
Hence there is not such set of representatives, and, by Philip Hall's
theorem on distinct representatives, there must be a set $A' \subseteq
A$ such that $|g(A')| < |A'|$, where $g(A) = \cup \{B_a \, | \, a\in
A'\}$.  Now define $f(x) = 0$ for $x \in A' \cup g(A')$ and $f(x) = 1$
for $x \in B \smallsetminus g(A')$.  For this function $f(B) = \sum_{b\in B}
f(x) = |B \smallsetminus g(A')| > |A \smallsetminus A'| \geq
\sum_{a\in A} f(x) = f(A)$.  It is easy to see that this function $f$ can be
extended and perturbed slightly to be compatible with the order on $P$
and to retain the property that $f (B) > f(A)$.  \qed \m

{\bf Remark.} By the same reasoning as in the proof above, it is also
true that, for any $A,B \in P_k$, we have $B \,\prec \, A$ if and only
if $f (B) < f(A)$ for every weight function $f$ compatible with the
order on $P$.  \m

\begin{cor}  If $f: P \rightarrow \R$ is admissible for $(P, \P)$,
then $f: P_k \rightarrow \R$ is admissible for $(P_k, \P_k)$. \qed
\end{cor}
\B

\begin{example} \label{mat} {\bf Matroids.}   Let $P = [n] =
\{ 1, 2, \dots, n\}$ and let $\P$ be the set of all linear orderings
of $P$.  Then clearly every weight function $f : P \rightarrow \R$
is admissible.  By definition, a rank $k$ greedy set $M$ is a
collection of $k$-element subsets of $P$ such that, for every linear
ordering of $[n]$, there is a unique maximum in $M$ in the induced
Gale ordering on $P_k$.  But this is exactly the third
characterization of matroid given in the introduction.  In other
words, $M$ is a rank $k$ greedy set for $(P,\P)$ if and only if $M$ is
the set of bases of a rank $k$ matroid.
\end{example}
\B

\begin{example} \label{symp} {\bf Symplectic matroids.}  Let
$[n]^* = \{1^*, \dots, n^*\}$ and let $P = [n]\cup[n]^*$.  By
convention $i^{**} = i$.  Let $\P$ be the set of all linear orderings
$\leq$ of $P$ with the property that $i \leq j$ if and only if $j^*
\leq i^*$ for any $i,j \in P$.  Equivalently, the pair $i$ and $i^*$
appear symmetrically in the order.  For example, with $n = 3$ one such
order is $2 < 1^* < 3 < 3^* < 1 < 2^*$.  Consequently the
admissible weight functions include all weights $f : P \rightarrow \R$
 such that $f(i^*) = -f(i)$ for each $i \in [n]$.
A symmetric matroid of
Bouchet \cite{bou} is exactly a rank $n$ greedy set $L$ for the pair
$(P, \P)$ with the additional property that $A \cap A^* = \emptyset$
for each $A \in L$.  More generally, the rank $k$ greedy sets, $0\leq
k \leq n$, satisfying this same property are exactly the symplectic
matroids of Borovik, Gelfand and White \cite{BGW}.  The significance
of the added assumption will be discussed in the next section.
\end{example}

\section{The Group Case} \label{group}
\setcounter{equation}{0}

Let $P$ be a partially ordered set and $G$ a transitive group of
permutations of $P$.  If $\p$ denotes the order on $P$ and $\pi \in
G$, let $\pg$ denote the order defined by $a \,\pg\, b$ if $\pi ^{-1}a\,
\p \, \pi ^{-1}b$.  For rank $k$ subsets, the corresponding Gale order
will likewise be denoted $A\, \pg \,B$.  This shifted order will be
called the $\pi$-{\it order}.  Let $\P = \P(G)$ be the set of all
$\pi$-orders on $P$ for $\pi \in G$.  For example, if $P = [n]$ with the
order $1 < 2 < \cdots < n$, then $\P$ is the set of all orders $\pi(1)
< \pi (2) < \cdots < \pi(n)$ where $\pi \in G$.  The pair
$(P, \P(G))$ is referred to as the {\it group case}.

Although $G$ acts transitively on $P$, the induced action of $G$ on
$P_k$ may not be transitive.  There will therefore be situations
where attention will be restricted to a
single orbit $Q_k$ of $G$ acting on $P_k$.  The rank $k$ greedy sets
of $(P, \P(G))$ will then be restricted to being contained in a set $Q_k$
on which $G$ acts transitively.   \B

\begin{example} \label{matg} {\bf Matroids.}
If $P = [n]$ with the linear order $1 \,\prec\, 2\, \prec\, \cdots\,
\prec n$, and $S_n$ is the symmetric group consisting of all
permutations of $[n]$, then the greedy sets for $(P, \P(S_n))$ are
exactly the ordinary matroids of Example~\ref{mat}.
\end{example}
\B

\begin{example} \label{sympg} {\bf Symplectic matroids.}
Let $P = [n]\cup[n]^*$ with the linear order $1 \,\prec\, 2\, \prec\,
\cdots\, \prec n\, \prec n^* \, \prec \cdots \prec \, 2^* \, \prec \,
1^*$, and let $G = B_n$ be the permutation group whose generators are
all transpositions of the form $(i \,i^*)$ and all involutions of the
form $(i\,j)(i^* \, j^*)$.  The group $B_n$ is called the {\it
symplectic group}.  Note that the set of all $k$-element sets $A$ with
the property that $A \cap A^* = \emptyset$ comprises a single orbit of
$G$ acting on $P_k$; call this orbit $Q_k$.  Then the greedy sets $L
\subseteq Q_k)$ for $(P, \P (G))$ are exactly the symplectic matroids
of Example~\ref{symp} above.
\end{example}
\B

\begin{example} \label{cyc} {\bf Cyclic case.}  Let $P = [n]$
be a poset with the order $1 \, \prec 2\, \prec \, \cdots \,\prec n$,
and let $G$ be the cycle group acting on $[n]$ and generated by the
cycle $(1 \, 2 \, \cdots \, n)$.  For example, $3\prec 4\prec 1\prec
2$ is a cyclic ordering for $n=4$.  A collection $L$ of $k$-element
subsets of $P$ is a greedy set if and only if $L = \{A_1, A_2, \dots
,A_m\}$ where $A_i = \{a_{i1}, \dots , a_{ik} \}$ and $a_{11} \p
a_{21} \p \cdots \p a_{m1} \p a_{12} \p a_{22} \p \cdots \a_{m2} \p
\cdots \p a_{1k} \p a_{2k} \p \cdots \p \a_{mk}$.  This
characterization is easily proved by induction.
\end{example}
\B

\begin{example} \label{bipart} {\bf Bipartite case.}  Let $P = [n]\cup
[n]^*$ and let $\P$ consist of any linear order such that either all
the unstarred elements preceed the starred elements or all the starred
elements preceed the unstarred elements.  This is the group case
where, if $[n]$ and $[n]^*$ are considered as vertex sets of the two
parts of a complete bipartite graph $K_{n,n}$, then the group is the
automorphism group of $K_{n,n}$.
\end{example}

\section{The Greedy Algorithm} \label{alg}
\setcounter{equation}{0}

Naturally associated to the pair $(P,\P)$ is the following
optimization problem.   \B

\underline{{\bf OPTIMIZATION PROBLEM}} \,\, Given an admissible weight
function $f: P \rightarrow \R$ and a set $L \subseteq P_k$, find an
element of $L$ that maximizes the induced weight function $f : P_k
\rightarrow \R$. \B

Given $L \subseteq P_k$, call a subset $I\subseteq P$ {\it independent
with respect to} $L$ if $I$ is a subset of some element of $L$.  The
{\it greedy algorithm}, given explicitely in the introduction,
applied to this optimization problem, merely chooses the largest weight
element at each stage subject to the condition that the resulting set
is independent with respect to $L$.

\begin{theorem} \label{algtheorem1} Let $(P, \P)$ be a pair consisting
of a collection $\P$ of orderings of the finite set $P$.  If $L
\subseteq P_k$ is a rank $k$ greedy set, then the greedy algorithm
correctly solves the optimization problem for every admissible weight
function $f: P \rightarrow \R$.
\end{theorem}

\proof Assume that $L$ is a greedy set and that $f$ is compatible with
some order, say $\p$, in $\P$.  Since $L$ is a greedy set, it contains
a unique set $A$ that is maximum with respect to the Gale order.  We
claim that the greedy algorithm selects this set $A$.  Suppose,
instead that $B$ is chosen where $B \, \p \, A$.  Order the sets $A =
( a_1, a_2, \dots, a_k )$ and $B = ( b_1, b_2, \dots, b_k )$ so that
the elements of $B$ appear in the order selected by the greedy
algorithm and $b_i \, \p \, a_i$ for $1\leq i \leq k$.  Assume that
$a_i = b_i$ for $1\leq i < j$, but $a_j \neq b_j$.  Then $b_j \,\prec \,
a_j$ implies, by the compatibility of $f$, that $f(b_j) < f(a_j)$.  But
this contradicts the fact that, at this stage, the greedy
algorithm chose $b_j$.  \qed \B

In the case that $\P$ contains only linear orderings of $P$, the
greedy sets are actually characterized by the property that the greedy
algorithm correctly solves the optimization problem for every
admissible weight function.  The assumption that $\P$ contains only
linear orderings of $P$ is a reasonable one in light of
Theorem~\ref{linear} below.

\begin{theorem} \label{algtheorem2} Let $\P$ be a set of linear orderings
of $P$ and $L \subseteq P_k$.  Then the greedy algorithm correctly
solves the optimization problem for every admissible weight function
if and only if $L$ is a greedy set.
\end{theorem}

\proof In one direction, this result is a corollary of
Theorem~\ref{algtheorem1}.  To prove it in the other direction, assume
that $L$ is not a greedy set.  Then there exists an order on $P$,
say $\p$, for which $L$ does not attain a unique maximum.  Since
$\p$ is a linear ordering of $P$, order the elements in each set in $L$
in decreasing order.  Let $A$ denote the lexicographically
maximum element of $L$, and let $B \neq A$ be a set in $L$ that is a
maximum with respect to Gale order.  According to
Proposition~\ref{weight} there exists a weight function compatible
with $\p$ such that $f(B) > f(A)$.  On the other hand, the greedy
algorithm chooses $A$.  \qed \B

It is desirable to choose $\P$ so that there are many admissible weight
functions and many rank $k$ greedy sets.  Then the greedy algorithm
will correctly solve a large collection of optimization problems.
Unfortunately, these two objectives - many admissible functions and
many greedy sets - are often contradictory.  If $(P,\P)$ and $(P,\Q)$
have the same collection of admissible functions, but, for each $k$,
each rank $k$ greedy set for $(P,\P)$ is a rank $k$ greedy set for
$(P,\Q)$, then clearly it is preferable, for algorithmic purposes, to
use $(P,\Q)$ rather than $(P,\P)$.

\begin{theorem}\label{linear}  For any pair $(P,\P)$ there is a pair
$(P, \Q)$ such that
\begin{enumerate}
\item $\Q$ contains only linear orders;
\item $(P,\P)$ and $(P,\Q)$ have the same admissible functions; and
\item for each $k$, each rank $k$ greedy set for $(P,\P)$ is already
a rank $k$ greedy set for $(P,\Q)$.
\end{enumerate}
\end{theorem}

\proof Let $\Q$ be the collection of all linear extensions of the
orders in $\P$.  Clearly condition (1) is satisfied.  Concerning
condition (2) assume that weight function $f$ is admissible for
$(P,\Q)$.  Then $f$ is compatible with some linear ordering $\leq$ in
$\Q$ and hence is also compatibale with any ordering in $\P$ having
$\leq$ as a linear extension.  Therefore $f$ is admissible for
$(P,\P)$.  Conversely assume that $f$ is admissible for $(P,\P)$.
Then $f$ is compatible with some ordering $\p$ in $\P$.  Assume that
the elements of $\{x_1, x_2, \dots , x_n\}$ of $P$ are indexed such
that $f(x_1) \leq f(x_2) \leq \cdots \leq f(x_n)$.  Then, by
definition, the linear order $x_1 < x_2 < \cdots < x_n$ is a linear
extension of $\p$ and $f$ is compatible with this linear order.
Therefore $f$ is admissible for $(P,\Q)$.

Concerning condition (3) assume that $M$ is a rank $k$ greedy set for
$(P,\P)$.  To show that $M$ must also be a greedy set for $(P,\Q)$,
let $\leq$ be any linear order in $\Q$.  Then $\leq$ is a linear
extension of some order $\p$ in $\P$.  Since $M$ is greedy for
$(P,\P)$, there is a unique maximum set $A = (a_1, \dots , a_k)$ in
$M$ such that, for any $B = (b_1, \dots , b_k)$, we have $b_i \, \p \,
a_i$ for all $i$ for some ordering of the elementsof $A$ and $B$.
Because $\leq$ is a linear extension of $\p$, it is also true that
$b_i \leq a_i$ for all $i$.  Therefore $A$ is also the unique maximum
with respect to the Gale order relative to $\leq$.  So $M$ is a greedy
set for $(P,\Q)$.  \qed \B

The following examples are chosen to be simple and to demonstrate
the theory for non-matroid greedy sets.
 \B

\begin{example} \label{symp2} {\bf Symplectic matroids.}  This is a
continuation of Example~\ref{symp} of Section 2.  Consider the case $n
= 3$.    It is not hard to check that the set
$$M = \{12^*, 13, 2^*3^*, 1^*3^* \}$$
is a rank 2 greedy set.  Take the particular function $f: [3]\cup[3]^*
\rightarrow \R$ defined by $f(1) = 1; f(2) = 2; f(3) = 3; f(3^*) = 4;
f(2^*) = 5; f(1^*) = 6$.  This is an admissible function because it is
compatible with the ordering $1 \,\prec\, 2\, \prec\, 3\, \prec 3^* \,
\prec  \, 2^* \, \prec \, 1^*$.  The greedy
algorithm applied to $M$ chooses the set $1^*3^*$ whose total weight
is 10, greater than that of any other set in $M$.

On the other hand, for the function $f(1) = 4; f(2) = 2; f(3) = 3;
f(3^*) = 1; f(2^*) = 5; f(1^*) = 6$, which is not admissible, the
greedy algorithm again chooses the set $1^*3^*$ whose total weight is
7, but the total weight of $12^*$ is $9$.  The greedy algorithm fails
in this case.  Note that the collection $M$ is not an ordinary matroid on the
set $[3]\cup[3]^*$.
\end{example}
\B

\begin{example} \label{cyc2} {\bf Cyclic case.}  This is a continuation
of Example~\ref{cyc} of Section 3.  Consider the case $n=4$, and take
the admissible weigh function $f(1) = 3; f(2) = 4; f(3) = 1; f(4) = 2$.
The set
$$M = \{13, 24 \}$$ is a greedy set for $(P,\P)$.   The greedy
algorithm chooses $13$ whose weight is 6, greater than the other
element of $M$.  On the other hand, for the weight function $f(1) = 1;
f(2) = 3; f(3) = 5; f(4) = 4$, which is not admissible, the greedy
algorithm fails for $M$.
\end{example}
\B

\begin{example} \label{bipart2} {\bf Bipartite case.}   This is a
continuation of Example~\ref{bipart} of Section 3.  Consider the case
$n=2$; clearly
$$M = \{12, 1^*2^* \}$$
is a greedy set.  An admissible function is one for which either $f(i)
< f(j)$ for every unstarred $i$ and starred $j$ or $f(i) < f(j)$ for
every starred $i$ and unstarred $j$.  As a simple example, let $f(1) =
1; f(2) = 2; f(1^*) = 3; f(2^*) = 4$.  Then $f$ is admissible, and the
greedy algorithm chooses $1^*2^*$ which has total weight 7 compared to
the total weight 3 of $12$.  On the other hand the function $f(1) = 3;
f(2) = 4; f(1^*) = 1; f(2^*) = 5$, is not admissible.  The greedy
algorithm chooses $1^*2^*$ which has total weight 6, although $12$ has
greater total weight 7.
\end{example}

\section{Roots and Polytopes} \label{tope}
\setcounter{equation}{0}

In light of Theorems~\ref{algtheorem1} and \ref{algtheorem2}, it is
important to have an efficient method to determine whether a
collection $L \subseteq P_k$ is a greedy set.  If $(P,\P)$ is such
that $|P| = n$ and $\P$ consists of $N$ linear orderings of $P$, then
$N$ may well be exponential as a function of $n$.  If $L$ is a
collection of $k$-element subsets of $P$, then it will take no less
than exponential time to check, using the definition, whether $L$ is a
greedy set.  An alternative procedure is sought that is polynomial in
$n$ and the cardinality of $L$.  In the matroid case, any one of many
cryptomorphic definitions of matroid can be used to do this; that is
one of the nice properties of matroids.  For ordinary and symplectic
matroids, the associated matroid polytope \cite{SVZ1} furnishes an
efficient procedure to determine whether a set is greedy.  For the
general case, we have the geometric approach of Theorem~\ref{root} and
the remarks that follow it.

Because of Theorem~\ref{linear}, it will be assumed throughout this
section that $P = [n]$ and $\P$ contains only linear orders.  Each
linear order $\prec$ in $\P$ can be denoted by the permutation $\pi$
for which $\pi(1) \, \prec \, \pi(2) \, \prec \, \dots \, \prec \,
\pi(n)$.  Given the pair $(P, \P)$, we will associate a polytope
$\Delta (L)$ to each subset $L \subseteq P_k$ as follows.  Let $\bf
{\epsilon}_1, \ldots, {\bf \epsilon}_n$ be the canonical orthonormal
basis for $n$-dimensional Euclidean space $\R^n$.  For any $k$-element
subset $A$ of $P$, set
$$
{\bf \delta}_A = \sum_{i \in A} {\bf \epsilon}_i. \eqno(1)
$$
Let $\Delta(L)$ be the convex hull of the points $\{{\bf \delta}_A \,|
\, A \in L\}$.  Notice that $\Delta (L)$ lies in the (n-1)-dimensional
hyperplane in $\R^n$ with equation $\sum_{i=1}^n x_i = k$.  \B

A vector ${\bf v} = (x_1,x_2, \dots, x_n) \in \R^n$ will be called
$\pi$-{\it admissible} for $(P,\P)$ if $0 \, < \, x_{\pi 1} \, < \,
x_{\pi 2} \, < \, \dots \, < \, x_{\pi n}$.  A vector that is
$\pi$-admissible for some $\pi \in \P$ will simply be called {\it
admissible}.

\begin{theorem} \label{adm} A subset $L \subseteq \P_k$ is a rank $k$
greedy set for $(P,\P)$ if and only if, for each admissible vector
${\bf v}$, the linear function $f_{\bf v}({\bf x}) = \langle {\bf x},
{\bf v} \rangle$ attains a maximum on $\Delta(L)$ at a unique vertex.
\end{theorem}

\proof If ${\bf v} = (x_1, \dots , x_n)$, then
$$f_{{\bf v}}(\delta_A) = \sum_{i \in A} x_i.$$
Notice that, for $A,B \in P_k$ and $\pi \in \P$, we have, by
Proposition~\ref{weight} and the remark following it, that $A \, \prec
\, B$ in the $\pi$-Gale order if and only if $f(A) < f(B)$ for all
positive weight functions $f$ compatible with $\prec_{\pi}$.  This
is equivalent to $\sum_{i\in A} f(i) < \sum_{i\in B} f(i)$ for all
positive weight function such that $0 < f(\pi 1) < f(\pi 2) < \cdots
< f(\pi n)$.  But this, in turn, is the same as
$f_{{\bf v}}(\delta_A) = \sum_{i \in A} x_i = \sum_{i \in B} x_i =
f_{{\bf v}}(\delta_B)$ for all $\pi$-admissible vectors ${\bf v}$.
Thus the linear function $f_{\bf v}({\bf x}) = \langle {\bf
x}, {\bf v} \rangle$ attains a maximum on $\Delta(L)$ at a unique
vertex for each admissible vector ${\bf v}$ if and only if there is a
unique $\pi$-Gale maximum in $L$ for each $\pi \in \P$.  But the
latter condition is the definition of greedy set. \qed \B

Define a {\it root} of $(P, \P)$ as a vector ${\bf r} = \pm (x_1,x_2,\dots
,x_n)$ that satisfies the following properties.
\begin{enumerate}
\item $x_i = 0, 1$ or $-1$ for all $i$,
\item $\sum_{i=1}^n x_i = 0$, and
\item $\sum_{i=1}^m x_{\pi i} \geq 0$ for every $\pi \in \P$ and for
each $m = 1, \dots, n$.
\end{enumerate}

In particular, note that $\epsilon_i-\epsilon_j$ is a root of any pair
$(P, \P)$ for all $i\neq  j$.  Our definition  of root of $(P, \P)$ is
meant as a  generalization of the root system  of a Coxeter group.  In
the group case, we refer  to a root of $(P,  \P(G))$ as a root of $G$.
The group acts on the  set of roots, as well as  on the set of
admissible  vectors.  The roots in the  following examples are easy to
compute.  \B

\begin{example}  For either the symmetric group $S_n$ or the
alternating group $A_n$ acting on $[n]$, the roots are $R = \{
\epsilon_i-\epsilon_j \,| \, i\neq j \}$.
\end{example}
\B

\begin{example}  For the cyclic group $Z_n$ of Example~\ref{cyc}
acting on $[n]$, the roots are $\{ \pm \sum_{j=1}^{2m} (-1)^j
\epsilon_{i_j} \}$, where $i_1 < i_1 < \cdots < i_{2m}$.  In other
words, $+1$ and $-1$ alternate in the vector ${\bf r}$.  For
example, with $n=5$, the vector $(1, 0, -1, 1, -1)$ is a root while
$(1, -1, 0, -1, 1)$ is not.
\end{example}
\B

\begin{example}  For the symplectic group $B_n$ of Example~\ref{sympg}
acting on $[n] \cup [n]^*$ the roots are $R \cup \{\epsilon_i +
\epsilon_j - \epsilon_{i^*} + \epsilon_{j^*} \, | \, i\neq j, j^* \}$.
For example, for $n=3$, the vector $(1, -1, 0, 0, 1, -1)$ is a root.
\end{example}
\B

\begin{example}  For the bipartite group of Example~\ref{bipart}
acting on $[n] \cup [n]^*$, let $\epsilon = \epsilon_1 + \cdots +
\epsilon_n$ and $\epsilon ^* = \epsilon_{1^*} + \cdots +
\epsilon_{n^*}$.  The roots are $R \cup \{\epsilon, \epsilon ^* \} $.
\end{example}
\B

\begin{lemma} \label{lem}  Let ${\bf r}$ be a vector satisfying conditions
(1) and (2) in the definition of root.  Then ${\bf r}$ is a root if
and only if ${\bf r}^{\perp}$ contains no admissible vector.
\end{lemma}

\proof Assume that ${\bf r} = (y_1, \dots ,y_n)$ is orthogonal to some
admissible vector ${\bf v} = (x_1, \dots ,x_n)$.  Since ${\bf v}$ is
admissible, there is a $\pi \in \P$ such that $0 \, < \, x_{\pi 1} \,
< \, x_{\pi 2} \, < \, \dots \, < \, x_{\pi n}$.  We have
$\sum_{i=1}^n x_{\pi i} y_{\pi i} = \sum_{i=1}^n x_i y_i = 0$.  Let $A
= \{ i \, | \, y_{\pi i} = +1\}$ and $B = \{ i \, | \, y_{\pi i} =
-1\}$.  Then $\sum_{i\in A} x_{\pi i} = \sum_{i\in B} x_{\pi i}$.
Assume, by way of contradiction, that ${\bf r}$ is a root.  Condition
(3) in the definition of root implies (without loss of generality)
that there is a bijection $\phi$ from $A$ onto $B$ so that $\phi(i) >
i$.  But this implies that $\sum_{i\in A} x_{\pi i} < \sum_{i\in B}
x_{\pi i}$, a contradiction.

Conversely, assume that ${\bf r} = (y_1, \dots ,y_n)$ is not a root.
We use the same notation $A$ and $B$ as above.  Without loss of
generality we can ignore the 0 entries in ${\bf r}$ and assume that $A
\cup B = [n]$ and that $1 \in A$.  Define a bijection $\phi$ from $A$
to $B$ recursively as follows.  Let $\phi(1)$ be the least element of
$B$.  Having defined $\phi(i)$ for $i < j$, define
$\phi(j)$ as the least element of $B$ not already in the image of
$\phi$.  Let $C = \{ i\in A \, | \, \phi(i) > i\} \cup \{ \phi(i) \in B \, |
\,  \phi(i) > i\}$ and $D = \{ i\in A \, | \, \phi(i) < i\}
\cup \{ \phi(i) \in B \, |  \, \phi(i) < i\}$.  Since ${\bf r}$ is
not a root, $C$ and $D$ are nonempty.  An admissible vector ${\bf v} =
(x_1, \dots ,x_n)$ can now be chosen so that $\sum_{i\in C} x_iy_i$
and $\sum_{i\in D} x_iy_i$ take arbitrary positive and negative values,
respectively.  In particular, an admissible vector ${\bf v}$ can be chosen so
that $\langle {\bf r}, {\bf v} \rangle = \sum_{i\in C\cup D} x_iy_i = 0$.
\qed \B

\begin{theorem} \label{root}  Let $\P$ be a collection of linear orderings
of a finite set $P$ and let $L \subseteq \P_k$.  If every edge of $\Delta
(L)$ is parallel to a root, then $L$ is a greedy set for $(P,\P)$.
\end{theorem}

\proof Assume that $L$ is not a greedy set.  By Theorem~\ref{adm}
there exists an admissible vector ${\bf v} = (x_1, \dots,
x_n)$ such that the linear function $f_{\bf v}$ achieves its maximum on at
least two vertices of $\Delta (L)$.  Since $\Delta (L)$ is convex,
$f_{\bf v}$ achieves its maximum on some edge ${\bf e}$ of $\Delta
(L)$.  Therefore $\langle {\bf e}, {\bf v} \rangle = 0$.  By
Lemma~\ref{lem}, ${\bf e}$ is not parallel to a root.  \qed \B

Unfortunately the converse of Theorem~\ref{root} is, in general,
false.  There exist greedy sets $L$ for which the polytope $\Delta
(L)$ has non-root edges.  As an example, consider the cyclic group
$Z_5$ acting on the poset $[5] = \{ 1,2,3,4,5\}$.  This is the group
case $n=5$ in Example~\ref{cyc}.  If
$$L = \{ 12, 23, 34, 15, 35 \},$$ then $L$ is a greedy set:  The
(Gale) maximum is 35 for the order 12345; 15 for the order 23451; 12
for the order 34512; 23 for the order 45123; and 34 for the order
51234.  It is easy to check that the segment joining $\delta_{12}$ and
$\delta_{34}$ is an edge ${\bf e}$ of $\Delta(L)$ but that ${\bf e} =
(1,1,-1,-1,0)$ is not a root because condition (3) in the definition
fails.  \B

Recall from Section 3 that in the group case it is
natural to require that $L$ be contained in a single orbit $Q_k \subseteq
P_k$ under the action of $G$.  This is, however, not the case in the
above example; $L$ is not contained in a single orbit of $P_2$ under
the action of $Z_5$.  This motivates the following question.
\B

\begin{question} \label{ques} Let $G$ is a permutation group acting
on $P$, and let $Q_k$ be an orbit of $G$ acting on $P_k$.
Is it true that $L \subseteq \Q_k$ is a rank $k$ greedy set for $(P,
\P(G))$ if and only if every edge of $\Delta (L)$ is parallel to a
root of $G$?
\end{question}
\B

In certain cases the question can be answered in the affirmative.  An
edge of a polytope $\Delta$ in $\R^n$ will be called {\it supporting}
if it is contained in a supporting hyperplane of $\Delta$ that is
orthogonal to an admissible vector.  According to Lemma~\ref{lem}, an
edge not parallel to a root must be orthogonal to some admisssible
vector; so it is possible for such an edge to be supporting.  On the
other hand, an edge that is parallel to a root cannot be supporting.
A set $L \subseteq P_k$  is called {\it supporting} if each edge
of $\Delta(L)$ is either supporting or parallel to a root.

\begin{theorem}  Let $\P$ be a collection of linear orderings
of a finite set $P$.  Assume that $L \subseteq P_k$ is supporting.
Then $L$ is a greedy set for $(P,\P)$ if and only if every edge of
$\Delta (L)$ is parallel to a root.
\end{theorem}

\proof In one direction the statement follows directly from
Theorem~\ref{root}.  Conversely, assume that some edge ${\bf e}$ of
$\Delta (L)$ is not parallel to a root.  Because $L$ is
supporting, there is an admissible vector ${\bf v}$ such that
${\bf e}$ is contained in a supporting hyperplane of $\Delta (L)$ that is
orthogonal to ${\bf v}$.  This implies that the linear function
$f_{\bf v}({\bf x}) = \langle {\bf x}, {\bf v} \rangle$ attains a
maximum at both endpoints of the edge ${\bf e}$.  By Theorem~\ref{adm},
$L$ is not a greedy set.  \qed \B

Let $G$ be a permutation group acting on $P$, and let $Q_k$ be an orbit under the induced
action of $G$ on $P_k$.  Sometimes it is the case that any  $L \subseteq Q_k$ is supporting.
This is so, for example, if each vector determined by a point on the boundary of
$\Delta (Q_k)$ is either admissible or orthogonal to a root.  It can be shown that
this is the case for ordinary and symplectic matroids.
In general, it is not the case that any  $L \subseteq Q_k$ is supporting.
Again consider the cyclic group $Z_5$ acting on
$[5]$.  If
$$L = \{ 12, 23, 34, 51 \},$$
then $L$ is a greedy set, but the edge ${\bf e} = (1,1,-1,-1,0)$
joining $\delta_{12}$ and $\delta_{34}$ in $\Delta (L)$ is not a root
and is not supporting.  For ${\bf e}$ to be supporting, there would
have to exist an admissible vector ${\bf v} = (x_1, \dots,x_n)$ such
that $x_1+x_2 = x_3+x_4$.  This would imply that either $x_2 < x_3 < x_4 <
x_5 < x_1$ or $x_4 < x_5 < x_1 < x_2 < x_3$.  In the first case, the
vertex $\delta_{51}$ lies outside the hyperplane containing ${\bf e}$;
in the second case the vertex $\delta_{23}$ lies outside the hyperplane
containing ${\bf e}$.  So there does not exist a supporting
hyperplane of  $\Delta (L)$ containing ${\bf e}$.

\begin{thebibliography}{9}

\bibitem{BGW} A.\, Borovik, I.\, Gelfand and N.\, White,
Symplectic matroids, preprint.

\bibitem{bou} A.\, Bouchet, Greedy algorithm and symmetric matroids,
Mathemataical Programming {\bf 38} (1987), 147--159.

\bibitem{gale} D.\, Gale, Optimal assignments in an
ordered set: an application of matroid theory, J. Combinatorial
Theory {\bf 4} (1968), 1073-1082.

\bibitem{GS1} I.\,  M.\, Gelfand and
V.\, V.\, Serganova, On a general definition of a matroid and a
greedoid, Soviet Math. Dokl., {\bf 35} (1987), 6-10.

\bibitem{GS2} I.\, M.\, Gelfand and V.\, V.\, Serganova,
Combinatorial geometries and torus strata on homogeneous compact
manifolds, Russian Math. Surveys {\bf 42}  (198)7 133-168.

\bibitem{lawler} E.\,Lawler, {\em Combinatorial Optimization, Networks
and Matroids}, Holt, Rinehart and Winston, New York (1976).

\bibitem{pap} C.\,H.\ Papadimitriou and K.\,Steiglitz, {\em
Combinatorial Optimization - Algorithms and Complexity}, Prentice-Hall,
Inc. Holt, Englewood Cliffs, New Jersey (1982).

\bibitem{SVZ1} V. \,V.\, Serganova, A.\, Vince and A.\, Zelevinsky,
A geometric characterization of Coxeter matroids,
Annals of Combinatorics, to appear.

\bibitem{SVZ2} V. \,V.\, Serganova, A.\, Vince and A.\, Zelevinsky,
The greedy algorithm and Coxeter matroids, preprint.

\end{thebibliography}

\end{document}

