%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2020}
\articlenumber{47}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{question}[theorem]{Question}
\newtheorem{convention}[theorem]{Convention}

\newenvironment{statement}{\begin{quote}}{\end{quote}}

\newcommand{\PER}{\operatorname{PER}}
\newcommand{\PD}{\operatorname{PD}}

\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\PPos}{\RR_{>0}}

\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}

\newcommand{\calF}{\mathcal{F}}
\newcommand{\calB}{\mathcal{B}}

\newcommand{\IN}{\ive{N}}
\newcommand{\Eh}{\widehat{E}}
\newcommand{\wh}{\widehat{w}}
\renewcommand{\dh}{\widehat{d}}
\newcommand{\Ch}{\widehat{C}}

\newcommand{\timesu}{\mathbin{\underline{\times}}}

\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
% $\verts{...}$ yields $\operatorname{V}\left( ... \right)$.
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
% $\edges{...}$ yields $\operatorname{E}\left( ... \right)$.

% Darij: I use \leq, while you use \leqslant. The following
% two lines make them look the same:
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}

% Darij: I use \subseteq, while you use \subset. The following
% line makes them look the same:
\renewcommand{\subset}{\subseteq}

\newcommand{\nuo}{\nu^{\circ}}
%% define your title in the usual way
\title{The Bhargava greedoid}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Darij Grinberg\thanks{\href{mailto:darijgrinberg@gmail.com}{darijgrinberg@gmail.com}.}\addressmark{1} \and Fedor Petrov\thanks{\href{mailto:fedyapetrov@gmail.com}{fedyapetrov@gmail.com}.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Mathematics Department, Drexel University, Philadelphia, PA, USA \\ \addressmark{2}St. Petersburg State University and St. Petersburg Department, Steklov Mathematical Institute of Russian Academy of Sciences, St. Petersburg, Russia}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{The \emph{greedoids} (as defined in 1981 by Korte and L\'{o}v\'{a}sz)
are a class of set systems similar to the matroids (but more permissive).
Inspired by Bhargava's generalized factorials, we
introduce a greedoid of maximum-perimeter subsets in a finite ultrametric
space (actually, in a somewhat more general setting than that). We prove that
it is a \emph{Gaussian elimination greedoid} over any sufficiently large
(e.g., infinite) field; this is a greedoid analogue of a representable
matroid. We establish further properties of this greedoid, generalizing two
facts shown by Bhargava. We also briefly discuss its relation to a greedoid
appearing in phylogenetics, as well as a multiset analogue.}

%% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{greedoids, generalized factorials, phylogenetic trees, Vandermonde determinant}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\addbibresource{fps20gfv.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle

\section{Introduction}

Since it was coined in 1981 by Korte and L\'{o}v\'{a}sz, the concept of a
\emph{greedoid} has seen significant developments \cite{KoLoSc91} and shown up
in multiple mathematical fields. It is a type of set system (i.e., a set of
subsets of a given ground set $E$) that can be viewed as a weakening of the
notion of a matroid; more precisely, the independent sets of a matroid form a
greedoid. In this abstract, we shall define a greedoid stemming from
Bhargava's theory of generalized factorials (in a setting significantly more
general than Bhargava's) and prove that it is a \emph{Gaussian elimination
greedoid} over any sufficiently large (e.g., infinite) field (a greedoid
analogue of a representable matroid). Roughly speaking, the sets that belong
to this greedoid are subsets of maximum perimeter (among all subsets of their
size) of an ultrametric space. (Our setup is actually more general, allowing
distances in an arbitrary ordered abelian group and allowing vertex weights to
influence the perimeters.) We shall contrast this greedoid -- which we have
dubbed the \emph{Bhargava greedoid} -- with the strong greedoid of
maximum-diversity leaf sets of a phylogenetic tree found by Moulton, Semple
and Steel in \cite{MoSeSt06}. We shall also derive analogues of some of our
results to multisets instead of sets.

The results in this abstract are proved in detail in \cite{GriPet19} and in
\cite{article}.

\section{Greedoids and strong greedoids}

We begin with some fundamental definitions.

\begin{definition}
Let $E$ be a set. A \emph{set system} on the ground set $E$ is defined
to mean a set of subsets of $E$.
\end{definition}

Greedoids -- just as matroids -- can be defined as a certain class of set systems:

\begin{definition}
Let $E$ be a finite set. A set system $\mathcal{F}$ on the ground set $E$ is
said to be a \emph{greedoid} if it satisfies the following three axioms:

\begin{enumerate}
\item[\textbf{(i)}] We have $\varnothing\in\mathcal{F}$.

\item[\textbf{(ii)}] If $B\in\mathcal{F}$ satisfies $\left\vert B\right\vert
>0$, then there exists $b\in B$ such that $B\setminus\left\{  b\right\}
\in\mathcal{F}$.

\item[\textbf{(iii)}] If $A,B\in\mathcal{F}$ satisfy $\left\vert B\right\vert
=\left\vert A\right\vert +1$, then there exists $b\in B\setminus A$ such that
$A\cup\left\{  b\right\}  \in\mathcal{F}$.
\end{enumerate}

\noindent Furthermore, $\mathcal{F}$ is said to be a \emph{strong greedoid} if
it satisfies the following axiom (in addition to \textbf{(i)}, \textbf{(ii)}
and \textbf{(iii)}):

\begin{enumerate}
\item[\textbf{(iv)}] If $A,B\in\mathcal{F}$ satisfy $\left\vert B\right\vert
=\left\vert A\right\vert +1$, then there exists $b\in B\setminus A$ such that
$A\cup\left\{  b\right\}  \in\mathcal{F}$ and $B\setminus\left\{  b\right\}
\in\mathcal{F}$.
\end{enumerate}
\end{definition}

Note that axiom \textbf{(iv)} implies axiom \textbf{(iii)}. We notice that a
greedoid $\mathcal{F}$ that is subclusive (i.e., that satisfies $\left(
A\in\mathcal{F}\ \text{and}\ B\subseteq A\right)  \Longrightarrow\left(
B\in\mathcal{F}\right)  $) is the same as a matroid (defined in terms of
independent sets).

The fruits of the first 10 years of greedoid theory are gathered in the
monograph \cite{KoLoSc91}; more has been done since. Greedoids have shown up
in phylogenetics \cite{MoSeSt06} and chip-firing theory
%\footnote{also known as the abelian sandpile model on directed graphs}
\cite{BjLoSh91}; they have also
proven to be a source of shellable simplicial complexes (\cite{BjKoLo85},
\cite[Chapter XII]{KoLoSc91}). Strong greedoids appear in \cite{KoLoSc91} under
the name \textquotedblleft Gauss greedoids\textquotedblright, albeit with a
different definition (whose equivalence to our definition is proved in
\cite{BrySha99}).

In this note, we shall concern ourselves with an even more restrictive class
of greedoids: the \emph{Gaussian elimination greedoids}. Our definition of
this class follows \cite[Section IV.2.3]{KoLoSc91}, except that we will be using vector
families instead of matrices (which is equivalent, since any matrix can be
identified with the vector family consisting of its columns):

\begin{definition}
\label{def.geg}Let $E$ be a finite set. Let\footnote{Here and in the
following, $\mathbb{N}$ denotes the set $\left\{  0,1,2,\ldots\right\}  $.}
$m\in\mathbb{N}$ satisfy $m \geq \left|E\right|$.
Let $\mathbb{K}$ be a field. For each $k\in\left\{
0,1,\ldots,m\right\}  $, let $\pi_{k}:\mathbb{K}^{m}\rightarrow\mathbb{K}^{k}$
be the canonical projection that removes all but the first $k$ coordinates of
a column vector. (That is, $\pi_{k}\left(  \left(  a_{1},a_{2},\ldots
,a_{m}\right)  ^{T}\right)  =\left(  a_{1},a_{2},\ldots,a_{k}\right)  ^{T}$.)

For each $e\in E$, let $v_{e}\in\mathbb{K}^{m}$ be a column vector. The family
$\left(  v_{e}\right)  _{e\in E}$ will be called a \emph{vector family} over
$\mathbb{K}$.

Let $\mathcal{G}$ be the following set of subsets of $E$:%
\[
\left\{  F\subseteq E\ \mid\ \text{the family }\left(  \pi_{\left\vert
F\right\vert }\left(  v_{e}\right)  \right)  _{e\in F}\in\left(
\mathbb{K}^{\left\vert F\right\vert }\right)  ^{F}\text{ is linearly
independent}\right\}  .
\]
Then, $\mathcal{G}$ is called the \emph{Gaussian elimination greedoid} of the
vector family $\left(  v_{e}\right)  _{e\in E}$.
\end{definition}

\begin{example}
\label{exa.geg.matrix2}Let $\mathbb{K}=\mathbb{Q}$ and $E=\left\{
1,2,3,4,5\right\}  $ and $m=4$.
Let $v_{1},v_{2},v_{3},v_{4},v_{5}\in\mathbb{K}^5$ be
the columns of the $5\times5$-matrix
$\left(
\begin{array}
[c]{ccccc}%
0 & 1 & 1 & 0 & 1\\
1 & 1 & 0 & 0 & 0\\
0 & 2 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 0
\end{array}
\right)$.
Then, the Gaussian elimination greedoid of the vector family $\left(
v_{e}\right)  _{e\in E}=\left(  v_{1},v_{2},v_{3},v_{4},v_{5}\right)  $ is
\[
\left\{  \varnothing,\left\{  2\right\}  ,\left\{  3\right\}  ,\left\{
5\right\}  ,\left\{  1,2\right\}  ,\left\{  1,3\right\}  ,\left\{
1,5\right\}  ,\left\{  2,3\right\}  ,\left\{  2,5\right\}  ,\left\{
1,2,3\right\}  ,\left\{  1,2,5\right\}  ,\left\{  1,2,3,5\right\}  \right\}
.
\]
For example, the $3$-element set $\left\{  1,2,5\right\}  $ belongs to this
greedoid because the corresponding family $\left(  \pi_{3}\left(
v_{e}\right)  \right)  _{e\in\left\{  1,2,5\right\}  }\in\left(
\mathbb{K}^{3}\right)  ^{\left\{  1,2,5\right\}  }$ is linearly independent
(indeed, this family consists of the vectors $\left(  0,1,0\right)  ^{T}$,
$\left(  1,1,2\right)  ^{T}$ and $\left(  1,0,1\right)  ^{T}$).
\end{example}

Any Gaussian elimination greedoid is a strong greedoid. (This is implicit in
\cite{KoLoSc91}, and not hard to prove using the Pl\"{u}cker identity; see
\cite[Section 11]{article} for details.)

If $\mathcal{F}$ is a strong greedoid, and $k\in\mathbb{N}$, then the
$k$-element sets in $\mathcal{F}$ (if they exist) are the bases of a matroid.
If $\mathcal{F}$ is a Gaussian elimination greedoid over a field $\mathbb{K}$,
then this matroid is representable over $\mathbb{K}$.

\section{\label{sect.Vultra}$\mathbb{V}$-ultra triples}

We now come to our main concept: the
\textquotedblleft$\mathbb{V}$-ultra triple\textquotedblright, a generalization
of ultrametric spaces that supports vertex weights. First, an auxiliary
notation is needed:

\begin{definition}
Let $E$ be a set. Then, $E\timesu E$ shall denote the set $\left\{  \left(
e,f\right)  \in E\times E\ \mid\ e\neq f\right\}  $.
\end{definition}

\begin{convention}
Fix a totally ordered abelian group $\left(  \mathbb{V},+,0,\leq\right)  $
(with ground set $\mathbb{V}$, group operation $+$, zero $0$ and
smaller-or-equal relation $\leq$). We shall refer to this group simply as
$\mathbb{V}$. We will use the $\sum$ sign for finite sums inside this group,
and we will denote the maximum of a subset $S$ of $\mathbb{V}$ (with respect
to the relation $\leq$) by $\max S$.
\end{convention}

For almost all examples we know, it suffices to set $\mathbb{V}$ to be the
abelian group $\mathbb{R}$, or even $\mathbb{Z}$. Nevertheless, we shall work
in full generality, as it serves to separate objects that would otherwise
easily be confused.

\begin{definition}
A \emph{$\mathbb{V}$-ultra triple} shall mean a triple $\left(  E,w,d\right)
$ consisting of:

\begin{itemize}
\item a set $E$, called the \emph{ground set} of this $\mathbb{V}$-ultra triple;

\item a map $w:E\rightarrow\mathbb{V}$;

\item a map $d:E\timesu E\rightarrow\mathbb{V}$ required to satisfy the
following axioms:

\begin{itemize}
\item \textbf{Symmetry:} We have $d\left(  a,b\right)  =d\left(  b,a\right)  $
for any two distinct elements $a$ and $b$ of $E$.

\item \textbf{Ultrametric triangle inequality:} We have $d\left(  a,b\right)
\leq\max\left\{  d\left(  a,c\right)  ,d\left(  b,c\right)  \right\}  $ for
any three distinct elements $a$, $b$ and $c$ of $E$.
\end{itemize}
\end{itemize}

If $\left(  E,w,d\right)  $ is a $\mathbb{V}$-ultra triple and $e\in E$, then
the value $w\left(  e\right)  \in\mathbb{V}$ is called the \emph{weight} of
$e$.

If $\left(  E,w,d\right)  $ is a $\mathbb{V}$-ultra triple and $e$ and $f$ are
two distinct elements of $E$, then the value $d\left(  e,f\right)
\in\mathbb{V}$ is called the \emph{distance} between $e$ and $f$.
\end{definition}

\begin{example}
\label{exa.mod-or-not-mod.d} Let $E$ be a subset of $\mathbb{Z}$. Let $m$ be
any integer. Let $\varepsilon,\alpha\in\mathbb{V}$ satisfy $\varepsilon
\leq\alpha$. Define a map $w:E\rightarrow\mathbb{V}$ arbitrarily. Define a map
$d:E\timesu E\rightarrow\mathbb{V}$ by%
\[
d\left(  a,b\right)  =%
\begin{cases}
\varepsilon, & \text{if }a\equiv b\mod m;\\
\alpha, & \text{if }a\not \equiv b\mod m
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for all }\left(  a,b\right)  \in E\timesu E.
\]
It is easy to see that $\left(  E,w,d\right)  $ is a $\mathbb{V}$-ultra triple.
\end{example}

\begin{example}
\label{exa.p-adic.d'} For this example, we set $\mathbb{V}=\mathbb{Z}$, we fix
a prime number $p$ and a subset $E$ of $\mathbb{Z}$, and we define a map
$d^{\prime}:E\mathbin{\underline{\times}}E\rightarrow\mathbb{Z}$ by setting
\[
d^{\prime}\left(  a,b\right)  =-v_{p}\left(  a-b\right)  \qquad\text{ for all
}\left(  a,b\right)  \in E\mathbin{\underline{\times}}E.
\]
Here, for any nonzero $m\in\mathbb{Z}$, we let $v_{p}\left(  m\right)  $
denote the \emph{$p$-adic valuation} of $m$ (that is, the largest nonnegative
integer $k$ such that $p^{k}\mid m$). We define the weights $w\left(
a\right)  \in\mathbb{Z}$ arbitrarily. Then, $(E,w,d)$ is an $\mathbb{V}$-ultra triple.
\end{example}

Another example of a $\mathbb{V}$-ultra triple originates in graph theory:

\begin{example}
\label{exa.phylo} Let $T$ be a tree (i.e., a connected finite undirected graph
that has no cycles). For each edge $e$ of $T$, fix some nonnegative
$\lambda\left( e\right)  \in\mathbb{V}$;
this $\lambda\left(  e\right)  $ will be called the \emph{weight} of $e$.

For any two vertices $u$ and $v$ of $T$, let \emph{$\lambda\left(  u,v\right)
$} denote the sum of the weights of all edges on the (unique) path from $u$ to
$v$. This $\lambda\left(  u,v\right)  $ generalizes the usual
(graph-theoretical) distance between $u$ and $v$ (which is obtained when
$\lambda\left(  e\right)  =1$ for each edge $e$).

Let $E$ be a subset of the vertex set of $T$. Define a map $w:E\rightarrow
\mathbb{V}$ arbitrarily. Fix any vertex $r$ of $T$, and define a map
$d:E\mathbin{\underline{\times}}E\rightarrow\mathbb{V}$ by setting
\[
d\left(  x,y\right)  =\lambda\left(  x,y\right)  -\lambda\left(  x,r\right)
-\lambda\left(  y,r\right)  \qquad\text{ for each }\left(  x,y\right)  \in
E\mathbin{\underline{\times}}E.
\]
Then, $\left(  E,w,d\right)  $ is a $\mathbb{V}$-ultra triple.
\end{example}

The notion of a $\mathbb{V}$-ultra triple generalizes the notion of an ultra
triple as defined in \cite{GriPet19} (where further examples are given). More
precisely, if $\mathbb{V}=\mathbb{R}$, then a $\mathbb{V}$-ultra triple is the
same as what is called an \textquotedblleft ultra triple\textquotedblright\ in
\cite{GriPet19}. All the definitions and results stated in \cite{GriPet19} for
ultra triples adapt easily to the more general setting of $\mathbb{V}$-ultra triples.

\begin{definition}
Let $\left(  E,w,d\right)  $ be a $\mathbb{V}$-ultra triple. Let $A$ be a
finite subset of $E$. Then, the \emph{perimeter} of $A$ (with respect to
$\left(  E,w,d\right)  $) is defined to be
\[
\operatorname*{PER}\left(  A\right)  :=\sum_{a\in A}w\left(  a\right)
+\sum_{\substack{\left\{  a,b\right\}  \subseteq A;\\a\neq b}}d\left(
a,b\right)  \in\mathbb{V}.
\]
(Here, the second sum ranges over all \textbf{unordered} pairs $\left\{
a,b\right\}  $ of distinct elements of $A$.)
\end{definition}

For example, if $A=\left\{  p,q,r\right\}  $ is a $3$-element set, then%
\[
\operatorname*{PER}\left(  A\right)  =w\left(  p\right)  +w\left(  q\right)
+w\left(  r\right)  +d\left(  p,q\right)  +d\left(  p,r\right)  +d\left(
q,r\right)  .
\]


\begin{definition}
Let $\left(  E,w,d\right)  $ be a $\mathbb{V}$-ultra triple. The
\emph{Bhargava greedoid} of $\left(  E,w,d\right)  $ is defined to be the set%
\begin{align*}
&  \left\{  A\subseteq E\ \mid\ A\text{ has maximum perimeter among all
}\left\vert A\right\vert \text{-element subsets of }E\right\} \\
&  =\left\{  A\subseteq E\ \mid\ \operatorname*{PER}\left(  A\right)
\geq\operatorname*{PER}\left(  B\right)  \text{ for all }B\subseteq E\text{
satisfying }\left\vert B\right\vert =\left\vert A\right\vert \right\}  .
\end{align*}

\end{definition}

\section{\label{sect.thm-bh-geg}The main theorem}

\begin{convention}
For this whole section, we fix a $\mathbb{V}$-ultra triple $\left(
E,w,d\right)  $ such that $E$ is finite.
\end{convention}

Our main result is the following:

\begin{theorem}
\label{thm.bh-geg}Let $\mathcal{F}$ be the Bhargava greedoid of $\left(
E,w,d\right)  $. Let $\mathbb{K}$ be a field of size $\left\vert
\mathbb{K}\right\vert \geq\left\vert E\right\vert $. Then, $\mathcal{F}$ is
the Gaussian elimination greedoid of a vector family over $\mathbb{K}$.
\end{theorem}

We shall prove a stronger fact, which will however require some more terminology:

\begin{definition}
\label{def.alpha-clique}Let $\alpha\in\mathbb{V}$. An \emph{$\alpha$-clique}
of $\left(  E,w,d\right)  $ will mean a subset $F$ of $E$ such that any two
distinct elements $a,b\in F$ satisfy $d\left(  a,b\right)  =\alpha$.
\end{definition}

\begin{definition}
\label{def.clique}A \emph{clique} of $\left(  E,w,d\right)  $ will mean a
subset of $E$ that is an $\alpha$-clique for some $\alpha\in\mathbb{V}$.
\end{definition}

Thus, any subset of $E$ having size $\leq1$ is a clique (and an $\alpha
$-clique for every $\alpha\in\mathbb{V}$).

\begin{definition}
\label{def.mcs}Let $\operatorname*{mcs}\left(  E,w,d\right)  $ denote the
maximum size of a clique of $\left(  E,w,d\right)  $.
\end{definition}

Clearly, $\operatorname*{mcs}\left(  E,w,d\right)  \leq\left\vert E\right\vert
$. Thus, the following theorem generalizes \cref{thm.bh-geg}:

\begin{theorem}
\label{thm.bh-geg-mcs}Let $\mathcal{F}$ be the Bhargava greedoid of $\left(
E,w,d\right)  $. Let $\mathbb{K}$ be a field of size $\left\vert
\mathbb{K}\right\vert \geq\operatorname*{mcs}\left(  E,w,d\right)  $. Then,
$\mathcal{F}$ is the Gaussian elimination greedoid of a vector family over
$\mathbb{K}$.
\end{theorem}

\section{Greedy permutations}

\begin{convention}
For this whole section, we fix a $\mathbb{V}$-ultra triple $\left(
E,w,d\right)  $.
\end{convention}

The notion of a greedoid owes its name to the phenomenon that (usually) when
the sets solving an optimization problem form a greedoid, then they can be
constructed efficiently by a greedy algorithm (see \cite{KoLoSc91} for some
instances). The Bhargava greedoid is no exception. Given a $\mathbb{V}$-ultra
triple $\left(  E,w,d\right)  $ and a $k\in\mathbb{N}$, the greedy algorithm
for constructing a $k$-element subset of $E$ of maximum perimeter works as one
would expect: Start with the empty set, and add elements to it one by one,
each time choosing an element that maximizes the increment it contributes to
the perimeter. This leads to sequences we call \emph{greedy permutations}:

\begin{definition}
\label{def.greed}Let $C$ be a subset of $E$, and let $m\in\mathbb{N}$. A
\emph{greedy $m$-permutation} of $C$ is a list $\left(  c_{1},c_{2}%
,\ldots,c_{m}\right)  $ of $m$ distinct elements of $C$ such that for each
$i\in\left\{  1,2,\ldots,m\right\}  $ and each $x\in C\setminus\left\{
c_{1},c_{2},\ldots,c_{i-1}\right\}  $, we have $\operatorname{PER}\left\{
c_{1},c_{2},\ldots,c_{i}\right\}  \geq\operatorname{PER}\left\{  c_{1}%
,c_{2},\ldots,c_{i-1},x\right\}  $.
\end{definition}

\begin{example}
Let $m=2$ and $E=\left\{  1,2,3,4,5\right\}  $. Let $\mathbb{V}$,
$\varepsilon$, $\alpha$ and $d$ be as in \cref{exa.mod-or-not-mod.d}.
Define $w:E\rightarrow\mathbb{V}$ such that $w\left(  a\right)  =0$ for all
$a\in E$.

Then, a pair $\left(  i,j\right)  $ of elements of $E$ is a greedy
$2$-permutation of $E$ if and only if $i\not \equiv j\mod 2$.

The pair $\left(  1,3\right)  $ is a greedy $2$-permutation of $\left\{
1,3,5\right\}  $, but not of $E$.

Also, $\left(  1,2,3,4,5\right)  $ is a greedy $5$-permutation of $E$, but
$\left(  1,2,3,5,4\right)  $ is not.
\end{example}

If $C$ is a finite subset of $E$, then a greedy $m$-permutation of $C$ exists
for each $m\in\left\{  0,1,\ldots,\left\vert C\right\vert \right\}  $.
Moreover, the greedy $m$-permutations generate all maximum-perimeter subsets
of $E$, in the sense that the following theorems (\cite[Section 4]{GriPet19}) hold:

\begin{theorem}
\label{thm.2Section a} Let $C$ be any subset of $E$, and let $m$ be a nonnegative integer.

Let $\left(  c_{1}, c_{2}, \ldots, c_{m} \right)  $ be any greedy
$m$-permutation of $C$.

Then, for each $k\in\left\{  0,1,\dots,m\right\}  $, the set $\left\{
c_{1},c_{2},\ldots,c_{k}\right\}  $ has maximum perimeter among all
$k$-element subsets of $C$ (and thus belongs to the Bhargava greedoid of
$\left(  E,w,d\right)  $).
\end{theorem}

\begin{theorem}
\label{thm.2b} Let $C$ be any finite subset of $E$, and let $m$ be a
nonnegative integer such that $\left\vert C\right\vert \geq m$. Let
$k\in\left\{  0,1,\dots,m\right\}  $.

Let $A$ be a $k$-element subset of $C$ having maximum perimeter (among the
$k$-element subsets of $C$). Then, there exists a greedy $m$-permutation
$\left(  v_{1},v_{2},\ldots,v_{m}\right)  $ of $C$ such that $A=\left\{
v_{1},v_{2},\ldots,v_{k}\right\}  $.
\end{theorem}

\section{The connection to Bhargava's $p$-orderings}

Greedy $m$-permutations generalize the notion of $P$-orderings introduced by
Manjul Bhargava in \cite[Section 2]{Bharga97} (which, in turn, has the
$p$-orderings in \cite[Section 4]{Bharga00} and \cite[Section 2]{Bharga09} as
particular cases). Bhargava already observed the possibility of such a
generalization in the paragraph after the proof of Lemma 2 in \cite{Bharga97},
but never elaborated further on it.

In this abstract, we merely outline the simplest case, in which the underlying
Dede\-kind ring is $\mathbb{Z}$. We refer to \cite[Section 9]{GriPet19} for the
general setting.

Let $\mathbb{V}$, $p$, $E$, $v_{p}\left(  m\right)  $ and $d^{\prime}$ be as
in \cref{exa.p-adic.d'}. Define a map $w:E\rightarrow\mathbb{Z}$ by
setting $w\left(  e\right)  =0$ for each $e\in E$.

Bhargava defines a \emph{$P$-ordering} of $E$ to be a sequence $\left(
a_{0},a_{1},a_{2},\ldots\right)  $ of elements of $E$ constructed recursively
as follows: For each $k\in\mathbb{N}$, we define $a_{k}$ (assuming that
$a_{0},a_{1},\ldots,a_{k-1}$ are already defined) to be an element of $E$
minimizing the quantity
\[
v_{p}\left(  \left(  a_{k}-a_{0}\right)  \left(  a_{k}-a_{1}\right)
\cdots\left(  a_{k}-a_{k-1}\right)  \right)
\]
(where we set $v_{p}\left(  0\right)  =+\infty$ and consider $+\infty$ to be
larger than any integer). In order not to be distracted by the infiniteness of
such sequences, we instead consider a finite analogue of $P$-orderings, which
we call \emph{$\left(  P,m\right)  $-orderings} (for some $m\in\mathbb{N}$);
these are defined just as $P$-orderings, except for being $m$-tuples instead
of infinite sequences.

Now, it is easy to see that if $C$ is a subset of $E$ such that $\left\vert
C\right\vert \geq m$, then a $\left(  P,m\right)  $-ordering of $C$ is the
same as a greedy $m$-permutation of $C$ (with respect to the $\mathbb{V}%
$-ultra triple $\left(  E,w,d^{\prime}\right)  $). Thus, \cite[Theorem 1 and
Lemma 2]{Bharga97} can easily be derived from the above \cref{thm.2a,thm.2b}.

The \textquotedblleft$P$-orderings of order $h$\textquotedblright\ defined in
\cite[Section 2.2]{Bharga09} can also be regarded as a particular case of
greedy $m$-permutations; we only need to modify the map $d^{\prime}$.

\section{Greedy subsequences}

Greedy $m$-permutations of a subset of a $\mathbb{V}$-ultra triple consist of
distinct elements by definition. One might wonder if there is an analogue that
allows equal entries. Of course, this requires having distances of the form
$d\left(  a,a\right)  $, which are not supported by the notion of a
$\mathbb{V}$-ultra triple; thus, we need a somewhat stronger notion:

\begin{definition}
A \emph{full $\mathbb{V}$-ultra triple} shall mean a triple $\left(
E,w,d\right)  $ consisting of:

\begin{itemize}
\item a set $E$, called the \emph{ground set} of this full $\mathbb{V}$-ultra triple;

\item a map $w:E\rightarrow\mathbb{V}$;

\item a map $d:E\times E\rightarrow\mathbb{V}$ required to satisfy the
following axioms:

\begin{itemize}
\item \textbf{Symmetry:} We have $d\left(  a,b\right)  =d\left(  b,a\right)  $
for any two elements $a$ and $b$ of $E$.

\item \textbf{Ultrametric triangle inequality:} We have $d\left(  a,b\right)
\leq\max\left\{  d\left(  a,c\right)  ,d\left(  b,c\right)  \right\}  $ for
any three elements $a$, $b$ and $c$ of $E$.
\end{itemize}
\end{itemize}
\end{definition}

If $\left(  E,w,d\right)  $ is a $\mathbb{V}$-ultra triple such that $E$ is
finite, then it is easy to see that $d$ can be extended to a map $\overline
{d}:E\times E\rightarrow\mathbb{V}$ such that $\left(  E,w,\overline
{d}\right)  $ is a full $\mathbb{V}$-ultra triple. For infinite $E$, such an
extension may or may not exist.

\begin{convention}
For the rest of this section, we fix a full $\mathbb{V}$-ultra triple $\left(
E,w,d\right)  $.
\end{convention}

We shall not consider multisets, but instead simply work with tuples: The
\emph{perimeter} of any $m$-tuple $\mathbf{a}=\left(  a_{1},a_{2},\ldots
,a_{m}\right)  \in E^{m}$ is defined as%
\[
\operatorname{PER}\left(  \mathbf{a}\right)  :=\sum_{k=1}^{m}w\left(
a_{k}\right)  +\sum_{1\leq i<j\leq m}d\left(  a_{i},a_{j}\right)  .
\]
In analogy to \cref{def.greed}, we now define:

\begin{definition}
Let $C$ be a subset of $E$, and let $m\in\mathbb{N}$. A \emph{greedy
$m$-subsequence} of $C$ is an $m$-tuple $\left(  c_{1},c_{2},\ldots
,c_{m}\right)  \in C^{m}$ such that for each $i\in\left\{  1,2,\ldots
,m\right\}  $ and each $x\in C$, we have $\operatorname{PER}\left(
c_{1},c_{2},\ldots,c_{i}\right)  \geq\operatorname{PER}\left(  c_{1}%
,c_{2},\ldots,c_{i-1},x\right)  $.
\end{definition}

Thus, a greedy $m$-subsequence may revisit elements of $C$ multiple times (but
will generally try to avoid doing so as long as it can, since the ultrametric
triangle inequality entails $d\left(  a,a\right)  \leq d\left(  a,c\right)  $
for any $a,c\in E$). We now have the following analogues of \cref{thm.2a,thm.2b} (see \cite[Section 8]{GriPet19}):

\begin{theorem}
\label{thm.multi-2a} Let $C$ be any subset of $E$, and let $m$ be a
nonnegative integer.

Let $\left(  c_{1}, c_{2}, \ldots, c_{m} \right)  $ be any greedy
$m$-subsequence of $C$.

Then, for each $k \in\left\{  0,1,\dots,m \right\}  $, the $k$-subsequence
$\left(  c_{1}, c_{2}, \ldots, c_{k} \right)  $ has maximum perimeter among
all $k$-subsequences of $C$.
\end{theorem}

\begin{theorem}
\label{thm.multi-2b} Let $C$ be any finite nonempty subset of $E$, and let $m$
be a nonnegative integer. Let $k\in\left\{  0,1,\dots,m\right\}  $.

Let $\mathbf{a}$ be any $k$-subsequence of $C$ with maximum perimeter. Then,
there exists a greedy $m$-subsequence $\left(  c_{1},c_{2},\ldots
,c_{m}\right)  $ of $C$ such that $\mathbf{a}$ is a permutation of the
$k$-tuple $\left(  c_{1},c_{2},\ldots,c_{k}\right)  $.
\end{theorem}

\section{\label{sect.proof-mcs}Proof outline for \cref{thm.bh-geg-mcs}}

Let us briefly survey how \cref{thm.bh-geg-mcs} is proved; for details,
we refer to \cite[Sections 4--9]{article}. The proofs of the combinatorial results can be
found in \cite{GriPet19}.

The proof relies on constructing a rather wide but manageable class of
$\mathbb{V}$-ultra triples and proving that their Bhargava greedoids are
Gaussian elimination greedoids, and subsequently showing that every finite
$\mathbb{V}$-ultra triple is isomorphic to one in this class. We call these
the \emph{valadic} $\mathbb{V}$-ultra triples.

To define them, we proceed as follows. We fix a field $\mathbb{K}$. Let
$\mathbb{L}$ denote the group algebra $\mathbb{K}\left[  \mathbb{V}\right]  $
of the group $\mathbb{V}$ over $\mathbb{K}$. This is a free $\mathbb{K}%
$-module with basis $\left(  t_{\alpha}\right)  _{\alpha\in\mathbb{V}}$; it
becomes a commutative $\mathbb{K}$-algebra with unity $t_{0}$ and with
multiplication given by $t_{\alpha}t_{\beta}=t_{\alpha+\beta}$ for all
$\alpha,\beta\in\mathbb{V}$. Let $\mathbb{V}_{\geq0}=\left\{  \alpha
\in\mathbb{V}\ \mid\ \alpha\geq0\right\}  $; this is a submonoid of the group
$\mathbb{V}$. Let $\mathbb{L}_{+}$ be the span of the $t_{\alpha}$ with
$\alpha\in\mathbb{V}_{\geq0}$; this is a $\mathbb{K}$-subalgebra of
$\mathbb{L}$.

\begin{example}
If $\mathbb{V}=\mathbb{Z}$ (with the usual addition and total order), then
$\mathbb{V}_{\geq0}=\mathbb{N}$. In this case, the group algebra $\mathbb{L}$
is the Laurent polynomial ring $\mathbb{K}\left[  X,X^{-1}\right]  $ in a
single indeterminate $X$ over $\mathbb{K}$ (indeed, each $t_{\alpha}$ plays
the role of $X^{\alpha}$), and its subalgebra $\mathbb{L}_{+}$ is the
polynomial ring $\mathbb{K}\left[  X\right]  $.
\end{example}

If $a\in\mathbb{L}$ is nonzero, then the \emph{order} of $a$ is defined to be
the smallest $\beta\in\mathbb{V}$ such that the coefficient of $t_{\beta}$ in
$a$ is nonzero. This order is an element of $\mathbb{V}$, and is denoted by
$\operatorname*{ord}a$. For example, $\operatorname*{ord}\left(  t_{2}%
-t_{3}+5t_{6}\right)  =2$ (if $\mathbb{V}=\mathbb{Z}$).

The following properties of orders are straightforward to check:

\begin{lemma}
\label{lem.ord.triangle}\textbf{(a)} A nonzero element $a\in\mathbb{L}$
belongs to $\mathbb{L}_{+}$ if and only if its order $\operatorname*{ord}a$ is
nonnegative (i.e., we have $\operatorname*{ord}a\geq0$).

\textbf{(b)} We have $\operatorname*{ord}\left(  -a\right)
=\operatorname*{ord}a$ for any nonzero $a\in\mathbb{L}$.

\textbf{(c)} Let $a$ and $b$ be two nonzero elements of $\mathbb{L}$. Then,
$ab$ is nonzero and satisfies $\operatorname*{ord}\left(  ab\right)
=\operatorname*{ord}a+\operatorname*{ord}b$. (In particular, $\mathbb{L}$ is
an integral domain.)

\textbf{(d)} Let $a$ and $b$ be two nonzero elements of $\mathbb{L}$ such that
$a+b$ is nonzero. Then, $\operatorname*{ord}\left(  a+b\right)  \geq
\min\left\{  \operatorname*{ord}a,\operatorname*{ord}b\right\}  $.
\end{lemma}

We can now assign a $\mathbb{V}$-ultra triple to each subset of $\mathbb{L}$:

\begin{definition}
\label{def.padic-ut}Let $E$ be a subset of $\mathbb{L}$. Define a map
$d:E\timesu E\rightarrow\mathbb{V}$ by setting%
\[
d\left(  a,b\right)  =-\operatorname*{ord}\left(  a-b\right),
\qquad \text{for all }\left(  a,b\right)  \in E\timesu E.
\]


Then, $\left(  E,w,d\right)  $ is a $\mathbb{V}$-ultra triple whenever
$w:E\rightarrow\mathbb{V}$ is a map (this follows easily from \cref{lem.ord.triangle}). Such a $\mathbb{V}$-ultra triple $\left(
E,w,d\right)  $ will be called \emph{valadic}.
\end{definition}

Now, the first half of the proof of \cref{thm.bh-geg-mcs} is showing
the theorem for valadic $\mathbb{V}$-ultra triples:

\begin{theorem}
\label{thm.poly-ut-greed}Let $E$ be a finite subset of $\mathbb{L}$. Define
$d$ as in \cref{def.padic-ut}. Let $w:E\rightarrow\mathbb{V}$ be a
map. Then, the Bhargava greedoid of the $\mathbb{V}$-ultra triple $\left(
E,w,d\right)  $ is the Gaussian elimination greedoid of a vector family over
$\mathbb{K}$.
\end{theorem}

The main tool for proving this is a slightly generalized
Vandermonde determinant:\footnote{
Here, the notation $\left(  b_{i,j}\right)  _{1\leq i\leq p,\ 1\leq
j\leq q}$ denotes the $p\times q$-matrix whose $\left(  i,j\right)  $-th entry
is $b_{i,j}$ for all $i$ and $j$.} %(see, e.g, \cite[Exercise 267]{FadSom72}):

\begin{lemma}
\label{lem.vandermonde.monic}Let $R$ be a commutative ring. For each
$j\in\left\{  1,2,\ldots,m\right\}  $, let $f_{j}\in R\left[  X\right]  $ be a
monic polynomial of degree $j-1$. Let $u_{1},u_{2},\ldots,u_{m}$ be $m$
elements of $R$. Then,
\[
\det\left(  \left(  f_{j}\left(  u_{i}\right)  \right)  _{1\leq i\leq
m,\ 1\leq j\leq m}\right)  =\prod_{m\geq i>j\geq1}\left(  u_{i}-u_{j}\right)
.
\]

\end{lemma}

\begin{proof}
[Proof of \cref{thm.poly-ut-greed} (outline).]Let $m=\left\vert
E\right\vert $. Let $\left(  c_{1},c_{2},\ldots,c_{m}\right)  $ be a greedy
$m$-permutation of $E$. For each $k\in\left\{  1,2,\ldots,m\right\}  $, define
a $\rho_{k}\in\mathbb{V}$ by%
\[
\rho_{k}=w\left(  c_{k}\right)  +\sum_{i=1}^{k-1}d\left(  c_{i},c_{k}\right)
=\operatorname*{PER}\left\{  c_{1},c_{2},\ldots,c_{k}\right\}
-\operatorname*{PER}\left\{  c_{1},c_{2},\ldots,c_{k-1}\right\}  .
\]


Consider the polynomial ring $\mathbb{L}\left[  X\right]  $. For each
$j\in\left\{  1,2,\ldots,m\right\}  $, we define a monic polynomial $f_{j}%
\in\mathbb{L}\left[  X\right]  $ by $f_{j}=\left(  X-c_{1}\right)  \left(
X-c_{2}\right)  \cdots\left(  X-c_{j-1}\right)  $. It is easy to see (using
the definition of a greedy $m$-permutation) that%
\[
t_{\rho_{j}-w\left(  e\right)  }f_{j}\left(  e\right)  \in\mathbb{L}%
_{+}\ \ \ \ \ \ \ \ \ \ \text{for every }e\in E\text{ and }j\in\left\{
1,2,\ldots,m\right\}  .
\]
This allows us to define an $a\left(  e,j\right)  \in\mathbb{L}_{+}$ by
$a\left(  e,j\right)  =t_{\rho_{j}-w\left(  e\right)  }f_{j}\left(  e\right)
$ for every $e\in E$ and $j\in\left\{  1,2,\ldots,m\right\}  $. Let
$\pi:\mathbb{L}_{+}\rightarrow\mathbb{K}$ be the $\mathbb{K}$-algebra homomorphism
that sends each $x\in\mathbb{L}_{+}$ to the coefficient of $t_{0}$ in $x$.
For each $e\in E$, define a column vector
$v_{e}\in\mathbb{K}^{m}$ by%
\[
v_{e}=\left(  \pi\left(  a\left(  e,1\right)  \right)  ,\pi\left(  a\left(
e,2\right)  \right)  ,\ldots,\pi\left(  a\left(  e,m\right)  \right)  \right)
^{T}.
\]


Using \cref{lem.vandermonde.monic},
we can see that $\mathcal{G}$ is the Gaussian elimination
greedoid of the vector family $\left(  v_{e}\right)  _{e\in E}$.
\end{proof}

The second ingredient in the proof of \cref{thm.bh-geg-mcs} is a
theorem stating that if $\left(  E,w,d\right)  $ is a $\mathbb{V}$-ultra
triple with finite ground set $E$, and if $\mathbb{K}$ is a field of size
$\left\vert \mathbb{K}\right\vert \geq\operatorname*{mcs}\left(  E,w,d\right)
$, then $\left(  E,w,d\right)  $ is isomorphic\footnote{Isomorphism between
$\mathbb{V}$-ultra triples is defined in the natural way (i.e., there must be
a bijection that forms commutative triangles with $w$ and $d$).} to a valadic
$\mathbb{V}$-ultra triple. This is proved by strong induction on $\left\vert
E\right\vert $, where the induction step involves identifying a hierachical
structure in $\mathbb{V}$-ultra triples: If $\left(  E,w,d\right)  $ is a
$\mathbb{V}$-ultra triple with $1<\left\vert E\right\vert <\infty$, then we
can define the \emph{diameter} of $\left(  E,w,d\right)  $ to be $\alpha
=\max\left(  d\left(  E\timesu E\right)  \right)  $. If we now pick a
maximum-size $\alpha$-clique $\left\{  e_{1},e_{2},\ldots,e_{m}\right\}  $ of
$\left(  E,w,d\right)  $, then the balls $B_{\alpha}^{\circ}\left(
e_{1}\right)  ,B_{\alpha}^{\circ}\left(  e_{2}\right)  ,\ldots,B_{\alpha
}^{\circ}\left(  e_{m}\right)  $ (where $B_{\alpha}^{\circ}\left(  f\right)
:=\left\{  g\in E\ \mid\ f=g\text{ or }d\left(  f,g\right)  <\alpha\right\}  $
is an open ball as defined in metric space theory) are disjoint and constitute
a set partition of $E$, and we can restrict our $\mathbb{V}$-ultra triple to
any of these balls to obtain a smaller $\mathbb{V}$-ultra triple with diameter
smaller than $\alpha$. By the induction hypothesis, each of these smaller
$\mathbb{V}$-ultra triples is isomorphic to a valadic one; by appropriately
shifting the ground sets of the latter valadic $\mathbb{V}$-ultra triples and
taking their union, we then obtain a valadic $\mathbb{V}$-ultra triple
isomorphic to $\left(  E,w,d\right)  $.

\section{A phylogenetic analogue}

In \cref{exa.phylo}, we have constructed a $\mathbb{V}$-ultra triple
$\left(  E,w,d\right)  $ for any tree $T$, any vertex $r$ of $T$, any weight
function $\lambda:\left\{  \text{edges of }T\right\}  \rightarrow\mathbb{V}$
and any map $w:E\rightarrow\mathbb{V}$. A particularly prominent instance of
this kind of data is when $T$ is an \emph{edge-weighted phylogenetic tree}
(one of the basic concepts in mathematical biology -- see, e.g.,
\cite{Warnow18}), the vertex $r$ is its root, while $E$ is the set of its
leaves. In this case, we can regard the perimeter $\operatorname*{PER}\left(
A\right)  $ of a subset $A$ of $E$ to be a measure of \textquotedblleft
broadness\textquotedblright\ of $A$. The sets in the Bhargava greedoid of
$\left(  E,w,d\right)  $ thus are the optimal solutions to a \textquotedblleft
Noah's ark\textquotedblright\ type problem: how do we choose a maximally
representative (i.e., maximally broad) small sample from the taxa (i.e., the
leaves of our phylogenetic tree)? (The weights $w\left(  e\right)  $ can come
useful if some taxa are more desirable than others.)

It turns out that a similar problem has been considered in the biology
literature (\cite{MoSeSt06} and references therein). The main difference is
that biologists define the \emph{phylogenetic diversity} of a subset $A$ of
$E$ to be the sum of the weights of all edges on the minimal subtree
connecting all leaves in $A$. This is not the same as $\operatorname*{PER}%
\left(  A\right)  $, and indeed behaves somewhat differently; for example, for
a star-shaped tree, the phylogenetic diversity grows linearly in the size of
$A$, while the perimeter grows quadratically. Nevertheless, the two concepts
are sufficiently similar that the maximum-diversity subsets (in the
biologists' sense) also form a strong greedoid; this was proved by Moulton,
Semple and Steel in 2006 \cite[Theorem 3.2]{MoSeSt06}. (The two greedoids are
generally different, and we don't know whether the latter is a Gaussian
elimination greedoid as well.)

Let us finally remark that the assignment of $\mathbb{V}$-ultra triples to
edge-weighted phylogenetic trees is not a one-way road. There is a
construction that (to some extent) inverts it: If $\left(  E,w,d\right)  $ is
a $\mathbb{V}$-ultra triple with finite ground set $E$, then the iterative
disassembling procedure we sketched at the end of \cref{sect.proof-mcs}
(which begins by splitting $E$ into a disjoint union of balls, and then
proceeds recursively by applying the same construction to these balls)
produces a tree which, if appropriately edge-weighted, encodes the
$\mathbb{V}$-ultra triple $\left(  E,w,d\right)  $. If we apply the
construction from \cref{exa.phylo} to it, we recover an isomorphic copy
of $\left(  E,w,d\right)  $. The two transformations (triple to tree and
backwards) are not literally inverse, and the precise connection is yet to be explored.

\section{Open questions}

%Several questions are left to be answered:

\begin{enumerate}[wide, labelwidth=!, labelindent=4pt]
\item Is the bound $\left\vert \mathbb{K}\right\vert \geq\operatorname*{mcs}%
\left(  E,w,d\right)  $ in \cref{thm.bh-geg-mcs} optimal?
(Details in \cite[Section 4]{article}.)

\item Does some multiset analogue of Bhargava greedoids underlie
\cref{thm.multi-2a,thm.multi-2b}?

\item Is the Moulton--Semple--Steel greedoid \cite{MoSeSt06} a
Gaussian elimination greedoid?

\item Both the Bhargava greedoid and the Moulton--Semple--Steel greedoid are
obtained by picking the subsets of $E$ maximizing a statistic (perimeter or
phylogenetic diversity). What other statistics defined
on subsets of $E$ have their maximizers form a greedoid?
\end{enumerate}

\acknowledgements{The first author thanks the Mathematisches
Forschungsinstitut Oberwolfach for its hospitality. He also thanks Alexander Postnikov for enlightening conversations.}

\printbibliography

\end{document}
