\documentclass{beamer}%
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{array}
\usepackage{setspace}
\usepackage{graphicx}
\usepackage{etex}
\usepackage{amsthm}
\usepackage{color}
\usepackage{wasysym}
\usepackage[all]{xy}
\usepackage{textpos}
\usepackage{ytableau}
\usepackage{tikz}
\usepackage{url}
\usepackage{color}
\usepackage{epsfig,amsfonts,bbm,mathrsfs}
\usepackage{verbatim}
\usepackage{amsfonts}
\usepackage{hyperref}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Tuesday, March 10, 2020 04:10:26}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\definecolor{darkred}{rgb}{0.7,0,0}
\definecolor{grau}{rgb}{.5 , .5 , .5}
\definecolor{dunkelgrau}{rgb}{.35 , .35 , .35}
\definecolor{schwarz}{rgb}{0 , 0 , 0}
\definecolor{violet}{RGB}{143,0,255}
\definecolor{forestgreen}{RGB}{34, 100, 34}
\newcommand{\red}{\color{red}}
\newcommand{\darkred}{\color{darkred}}
\newcommand{\grey}{\color{grau}}
\newcommand{\green}{\color{forestgreen}}
\newcommand{\violet}{\color{violet}}
\newcommand{\blue}{\color{blue}}
\newcommand{\white}{\color{white}}
\newcommand{\bIf}{\textbf{If} }
\newcommand{\bif}{\textbf{if} }
\newcommand{\bthen}{\textbf{then} }
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\lf}[2]{{#1}^{\underline{#2}}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\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{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\newcommand{\arti}{\ar@{~>}}
\newcommand{\OO}{\operatorname {O}}
\newcommand{\Nm}{\operatorname {N}}
\newcommand{\Par}{\operatorname{Par}}
\newcommand{\Comp}{\operatorname{Comp}}
\newcommand{\Pfin}{\mathcal{P}_{\operatorname{fin}}}
\newcommand{\Mat}{\operatorname{M}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\Nplus}{\mathbb{N}_{+}}
\newcommand\arxiv[1]{{\red \href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}}
\newcommand\oeis[1]{{\red \url{https://oeis.org/#1}}}
\newcommand{\Orb}{{\mathcal O}}
\newcommand{\GL}{\operatorname {GL}}
\newcommand{\SL}{\operatorname {SL}}
\newcommand{\Or}{\operatorname {O}}
\newcommand{\im}{\operatorname {Im}}
\newcommand{\Iso}{\operatorname {Iso}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\Supp}{\operatorname{Supp}}
\newcommand{\zero}{\mathbf{0}}
\newcommand{\xx}{\mathbf{x}}
\newcommand{\ord}{\operatorname*{ord}}
\newcommand{\whitenothing}{{\white \ }}
\newcommand{\bbK}{{\mathbb{K}}}
\newcommand{\move}{\longrightarrow}
\newcommand{\moves}{\overset{*}{\longrightarrow}}
\newcommand{\movestr}{\overset{!}{\longrightarrow}}
\newcommand{\movestrs}{\overset{*!}{\longrightarrow}}
\newcommand{\rato}{\dashrightarrow}
\newcommand{\lcm}{\operatorname*{lcm}}
\newcommand{\fti}[1]{\frametitle{\ \ \ \ \ #1}}
\newenvironment{iframe}[1][]{\begin{frame} \fti{[#1]} \begin{itemize}}{\end{frame}\end{itemize}}
\newcommand{\nfr}{\vspace{10cm} \end{frame} \begin{frame}}
\setbeamertemplate{itemize/enumerate body begin}{\large}
\setbeamertemplate{itemize/enumerate subbody begin}{\large}
\setbeamertemplate{itemize/enumerate subsubbody begin}{\large}
\usetheme{Frankfurt}
\usefonttheme[onlylarge]{structurebold}
\setbeamerfont*{frametitle}{size=\normalsize,series=\bfseries}
\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{footline}[frame number]
\setbeamertemplate{itemize/enumerate body begin}{}
\setbeamertemplate{itemize/enumerate subbody begin}{\normalsize}
\beamersetuncovermixins{\opaqueness<1>{0}}{\opaqueness<2->{15}}
\newcommand{\STRUT}{\vrule width 0pt depth 8pt height 0pt}
\newcommand{\ASTRUT}{\vrule width 0pt depth 0pt height 11pt}
\let\hrefold\href
\renewcommand{\href}[2]{{\red \hrefold{#1}{#2}}}
\let\emphold\emph
\renewcommand{\emph}[1]{{\darkred \emphold{#1}}}
\newcommand{\chaptertitle}[2]{\begin{center}{\Huge \bf \sc #1.} \\ \noindent\rule[0.5ex]{\linewidth}{1pt} {\Large \bf #2} \end{center}}
\iffalse
\NOEXPAND{\chaptertitle}[2]{\begin{center}{\Huge \bf \sc #1.} \\ \noindent\rule[0.5ex]{\linewidth}{1pt} {\Large \bf #2} \end{center}}
\fi
\theoremstyle{plain}
\newtheorem{conj}[theorem]{Conjecture}
\setbeamertemplate{headline}{}
\begin{document}
\author{Darij Grinberg \\
joint work with Fedor Petrov}
\title{Gaussian elimination greedoids from ultrametric spaces}
\date{2020-03-10, Institut Mittag--Leffler}
\frame{\titlepage\textbf{slides:} {\color{red}
\url{http://www.cip.ifi.lmu.de/~grinberg/algebra/greedtalk-iml2020.pdf} }
\newline\textbf{extended abstract with further references:} {{\color{red}
\url{http://www.cip.ifi.lmu.de/~grinberg/algebra/fps20gfv.pdf}}\ \ }}
\begin{frame}
\frametitle{\ \ \ \ \ 1. Bhargava's generalized factorials: an introduction}
\chaptertitle{1}{Bhargava's generalized factorials: an introduction}
\vspace{1cm} References:
\begin{itemize}
\item
\href{http://resolver.sub.uni-goettingen.de/purl?PPN243919689_0490}{Manjul
Bhargava, \textit{$P$-orderings and polynomial functions on arbitrary subsets
of Dedekind rings}, J. reine. angew. Math. \textbf{490} (1997), 101--127.}
\item
\href{https://www.maa.org/sites/default/files/pdf/upload_library/22/Hasse/00029890.di021346.02p0064l.pdf}{Manjul
Bhargava, \textit{The Factorial Function and Generalizations}, Amer. Math.
Month. \textbf{107} (2000), 783--799.} (Recommended!)
\item
\href{https://pdfs.semanticscholar.org/611e/14159642a54d9b01c1e38bb684d6bf79efd9.pdf}{Manjul
Bhargava, \textit{On $P$-orderings, rings of integer-valued polynomials, and
ultrametric analysis}, Journal of the AMS \textbf{22} (2009), 963--993.}
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ It begins with a Vandermonde}
\begin{itemize}
\item \only<1>{\textbf{Theorem} (classical exercise)\textbf{:} \newline Let
$a_{0},a_{1},\ldots,a_{n}\in\mathbb{Z}$. Then,
\[
0!\cdot1!\cdot2!\cdot\cdots\cdot n!\mid\prod_{i>j}\left( a_{i}-a_{j}\right)
.
\]
} \pause
\only<2->{ \textbf{Theorem} (classical exercise, slightly restated)\textbf{:}
\newline Let $a_{0},a_{1},\ldots,a_{n}\in\mathbb{Z}$. Then,%
\[
\prod_{i>j}\left( i-j\right) \mid\prod_{i>j}\left( a_{i}-a_{j}\right) .
\]
} \pause
\item \only<3>{ \textbf{Hint to proof 1:} Show that%
\[
\dfrac{\operatorname*{RHS}}{\operatorname*{LHS}}=\det\left( \dbinom{a_{i}}%
{j}\right) _{i,j\in\left\{ 0,1,\ldots,n\right\} }.
\]
}
\only<4-5>{ \textbf{Hint to proof 2:} WLOG assume that $0\leq a_{0}%
{ \textbf{Hint to proof 3:} To show that $u\mid v$, it suffices to
prove that every prime $p$ divides $v$ at least as often as it does $u$.
\newline Now get your hands dirty.}
\end{itemize}
\vspace{15pc}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ What about squares?}
\begin{itemize}
\item \only<1>{\textbf{Theorem:} \newline Let $a_{0},a_{1},\ldots,a_{n}%
\in\mathbb{Z}$. Then,
\[
\dfrac{0!\cdot2!\cdot\cdots\cdot\left( 2n\right) !}{2^{n}}\mid\prod
_{i>j}\left( a_{i}^{2}-a_{j}^{2}\right) .
\]
(Typo in Bhargava corrected.)}\pause
\textbf{Theorem} (slightly restated)\textbf{:} \newline Let $a_{0}%
,a_{1},\ldots,a_{n}\in\mathbb{Z}$. Then,%
\[
\prod_{i>j}\left( i^{2}-j^{2}\right) \mid\prod_{i>j}\left( a_{i}^{2}%
-a_{j}^{2}\right) .
\]
\pause
\item \only<3>{Analogues of the 3 above proofs work (I believe). In particular,
$\dfrac{\operatorname*{RHS}}{\operatorname*{LHS}}$ is the dimension of an
$\operatorname*{Sp}\left( n\right) $-irrep. }
\end{itemize}
\vspace{15pc}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ What about cubes?}
\begin{itemize}
\item \textbf{Question:} Do we also have%
\[
\prod_{i>j}\left( i^{3}-j^{3}\right) \mid\prod_{i>j}\left( a_{i}^{3}%
-a_{j}^{3}\right) \ ?
\]
\pause
\item \textbf{Answer:} No. For example, $n=2$ and $\left( a_{0},a_{1}%
,a_{2}\right) =\left( 0,1,3\right) $. \pause
\item So what is
\[
\gcd\left\{ \prod_{i>j}\left( a_{i}^{3}-a_{j}^{3}\right) \ \mid
\ a_{0},a_{1},\ldots,a_{n}\in\mathbb{Z}\right\} \ ?
\]
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ More generally...}
\begin{itemize}
\item \textbf{General question} (Bhargava, 1997)\textbf{:} Let $S$ be a set of
integers. What is%
\[
\gcd\left\{ \prod_{i>j}\left( a_{i}-a_{j}\right) \ \mid\ a_{0},a_{1}%
,\ldots,a_{n}\in S\right\} \ ?
\]
And when is it attained? \pause
\item Enough to work out each prime $p$ separately, because:
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ $p$-valuation}
\begin{itemize}
\item Let $p$ be a prime.
\item For each nonzero $n\in\mathbb{Z}$, let \emph{$v_{p}\left( n\right) $}
(the \emph{$p$-valuation} of $n$) be the highest $k\in\mathbb{N}$ such that
$p^{k}\mid n$.
(We use $\mathbb{N} := \set{0,1,2,\ldots}$.)
\item Set $v_{p}\left( 0\right) =+\infty$. \pause
\item \textbf{Rules for }$p$\textbf{-valuations:}%
\[%
\begin{tabular}
[c]{cc|cc}%
$v_{p}\left( 1\right) =0;$ & \ \ \ & \ \ \ & $v_{p}\left( ab\right)
=v_{p}\left( a\right) +v_{p}\left( b\right) ;$\\
$v_{p}\left( p^{k}\right) =k;$ & & & $v_{p}\left( a+b\right) \geq
\min\left\{ v_{p}\left( a\right) ,v_{p}\left( b\right) \right\} .$%
\end{tabular}
\]
\pause
\item \only<3>{ Define the \emph{$p$-distance $d_{p}\left( a,b\right) $}
between two integers $a$ and $b$ by%
\[
d_{p}\left( a,b\right) =-v_{p}\left( a-b\right) .
\]
Then, the last rule rewrites as%
\[
d_{p}\left( a,c\right) \leq\max\left\{ d_{p}\left( a,b\right)
,d_{p}\left( b,c\right) \right\} .
\]
}
\only<4>{ Two integers $u$ and $v$ satisfy $u\mid v$ if and only if%
\[
v_{p}\left( u\right) \leq v_{p}\left( v\right) \qquad\text{for each prime
}p.
\]
Thus, checking divisibility is reduced to a \textquotedblleft
local\textquotedblright\ problem. }
\end{itemize}
\vspace{10pc}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Equivalent restatement of the problem}
\begin{itemize}
\item \only<1>{ \textbf{Equivalent problem:} Let $S$ be a set of integers. Let
$p$ be a prime. What is%
\[
\min\left\{ v_{p}\left( \prod_{i>j}\left( a_{i}-a_{j}\right) \right)
\ \mid\ a_{0},a_{1},\ldots,a_{n}\in S\right\} \ ?
\]
And when is it attained?}
\only<2>{\textbf{Equivalent problem:} Let $S$ be a set of integers. Let $p$ be
a prime. What is%
\[
\min\left\{ \sum_{i>j}v_{p}\left( a_{i}-a_{j}\right) \ \mid\ a_{0}%
,a_{1},\ldots,a_{n}\in S\right\} \ ?
\]
And when is it attained?}
\only<3-4>{\textbf{Equivalent problem:} Let $S$ be a set of integers. Let $p$
be a prime. What is%
\[
\max\left\{ \sum_{i>j}d_{p}\left( a_{i},a_{j}\right) \ \mid\ a_{0}%
,a_{1},\ldots,a_{n}\in S\right\} \ ?
\]
And when is it attained?} \pause \pause \pause
\item We can WLOG assume that $a_{0},a_{1},\ldots,a_{n}$ are distinct.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Bhargava's greedy algorithm}
\begin{itemize}
\item Bhargava solved this problem using the following \emph{greedy
algorithm}: \pause
\begin{itemize}
\item Pick $a_{0}\in S$ arbitrarily.\pause
\item Pick $a_{1}\in S$ to maximize $d_{p}\left( a_{0},a_{1}\right)
$.\pause
\item Pick $a_{2}\in S$ to maximize $d_{p}\left( a_{0},a_{2}\right)
+d_{p}\left( a_{1},a_{2}\right) $.\pause
\item Pick $a_{3}\in S$ to maximize $d_{p}\left( a_{0},a_{3}\right)
+d_{p}\left( a_{1},a_{3}\right) +d_{p}\left( a_{2},a_{3}\right) $.\pause
\item $\ldots$ (Ad infinitum, or until $S$ is exhausted.)\pause
\end{itemize}
\item Thus, the choice of $a_{n}$ tactically maximizes $\sum_{n\geq i>j}%
d_{p}\left( a_{i},a_{j}\right) $ for fixed $a_{0},a_{1},\ldots,a_{n-1}$.
(Thus \textquotedblleft greedy\textquotedblright.) But is it strategically
optimal? \pause
\item \textbf{Theorem (Bhargava):} Yes. Any such sequence $\left( a_{0}%
,a_{1},a_{2},\ldots\right) $ will always maximize $\sum_{n\geq i>j}%
d_{p}\left( a_{i},a_{j}\right) $ for each $n$.\pause
\item \textbf{Note:} There is such a sequence for each prime $p$, but there
might not be such a sequence that works for all $p$ simultaneously.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ A cryptic hint}
\begin{itemize}
\item Bhargava, 1997:
\begin{enumerate}
\item[\ ] \textquotedblleft\textit{We note that the above results (i.e.
Theorem 1, Lemmas 1 and 2) do not rely on any special properties of }%
$P$\textit{ or }$R$\textit{; they depend only on the fact that }$R$\textit{
becomes an ultrametric space when given the }$P$\textit{-adic metric. Hence
these results could be viewed more generally as statements about certain
special sequences in ultrametric spaces. For convenience, however, we have
chosen to present these statements only in the relevant context. In
particular, we note that our proof of Theorem 1 shall be a purely algebraic
one, involving no inequalities.}\textquotedblright
\end{enumerate}
(Theorem 1 is a slight generalization of the above Theorem.)\pause
\item In other news, the properties of $d_{p}$ are all that is needed.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ 2. Ultra triples}
\chaptertitle{2}{Ultra triples}
\vspace{1cm} References:
\begin{itemize}
\item \href{https://arxiv.org/abs/1909.01965}{Darij Grinberg, Fedor Petrov,
\textit{A greedoid and a matroid inspired by Bhargava's p-orderings},
arXiv:1909.01965}.
\item \href{https://arxiv.org/abs/2001.05535}{Darij Grinberg, \textit{The
Bhargava greedoid as a Gaussian elimination greedoid}, arXiv:2001.05535}.
\item \href{https://doi.org/10.1007/s00012-003-1806-4}{Alex J. Lemin,
\textit{The category of ultrametric spaces is isomorphic to the category of
complete, atomic, tree-like, and real graduated lattices LAT*}, Algebra
univers. \textbf{50} (2003), pp. 35--49}.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Ultra triples}
\begin{itemize}
\item If $E$ is any set, then
\[
{\color{darkred} E\mathbin{\underline{\times}}E } :=\left\{ \left(
e,f\right) \in E\times E\ \mid\ e\neq f\right\} .
\]
\pause
\item \textbf{Definition:} An \emph{ultra triple} is a triple $\left(
E,w,d\right) $ consisting of:
\begin{itemize}
\item a set $E$, called the \emph{ground set} (its elements are called
\emph{points});\pause
\item a map $w:E\rightarrow\mathbb{R}$ that assigns to each point $e$ some
number $w \left( e\right) \in\mathbb{R}$ that we call its \emph{weight}%
;\pause
\item a map $d:E\mathbin{\underline{\times}}E\rightarrow\mathbb{R}$ that
assigns to any two distinct points $e$ and $f$ a number $d\left( e,f\right)
\in\mathbb{R}$ that we call their \emph{distance},\pause
\end{itemize}
satisfying the following axioms:
\begin{itemize}
\item \textbf{Symmetry:} $d\left( a,b\right) =d\left( b,a\right) $ for any
distinct $a,b\in E$;\pause
\item \textbf{Ultrametric triangle inequality:} $d\left( a,b\right) \leq
\max\left\{ d\left( a,c\right) ,d\left( b,c\right) \right\} $ for any
distinct $a,b,c\in E$.\pause
\end{itemize}
\item \only<7>{More generally, we can replace $\mathbb{R}$ by any totally
ordered abelian group $\mathbb{V}$.} \pause
We will only consider ultra triples with \textbf{finite} ground set $E$.
\newline(Bhargava's $E$ is infinite, but results adapt easily.)
\end{itemize}
\vspace{8pc}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Ultra triples, examples: 1 (congruence)}
\begin{itemize}
\item \only<1>{\textbf{Example:} Let $E\subseteq\mathbb{Z}$ and $n\in
\mathbb{Z}$. Define a map $w:E\rightarrow\mathbb{R}$ arbitrarily. Define a map
$d:E\mathbin{\underline{\times}}E\rightarrow\mathbb{R}$ by%
\[
d\left( a,b\right) =%
\begin{cases}
0, & \text{if }a\equiv b\mod n;\\
1, & \text{if }a\not \equiv b\mod n
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for all }\left( a,b\right) \in
E\mathbin{\underline{\times}}E.
\]
Then, $\left( E,w,d\right) $ is an ultra triple.}
\only<2>{\textbf{Example:} Let $E\subseteq\mathbb{Z}$ and $n\in\mathbb{Z}$.
Define a map $w:E\rightarrow\mathbb{R}$ arbitrarily. Define a map
$d:E\mathbin{\underline{\times}}E\rightarrow\mathbb{R}$ by%
\[
d\left( a,b\right) =%
\begin{cases}
\varepsilon, & \text{if }a\equiv b\mod n;\\
\alpha, & \text{if }a\not \equiv b\mod n
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for all }\left( a,b\right) \in
E\mathbin{\underline{\times}}E,
\]
where $\varepsilon$ and $\alpha$ are fixed reals with $\varepsilon\leq\alpha$.
Then, $\left( E,w,d\right) $ is an ultra triple.}
\end{itemize}
\vspace{15.1127pc}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Ultra triples, examples: 2 ($p$-adic distance)}
\begin{itemize}
\item Let $p$ be a prime. Let $E\subseteq\mathbb{Z}$. Define the weights
$w\left( e\right) \in\mathbb{R}$ arbitrarily. Then, $\tup{E, w, d_p}$ is an
ultra triple.
Here, $d_{p}$ is as before:
\[
d_{p}\left( a,b\right) =-v_{p}\left( a-b\right) .
\]
\item This is the case of relevance to Bhargava's problem! \\
Thus, we call such a triple $\tup{E, w, d_p}$ a \emph{Bhargava-type ultra triple}.\pause
\item Lots of other distance functions also give ultra triples: Compose
$d_{p}$ with any weakly increasing function $\mathbb{R}\rightarrow\mathbb{R}$.
For example,
\[
d_{p}^{\prime}\left( a,b\right) =p^{-v_{p}\left( a-b\right) }.
\]
\pause
\item More generally, we can replace $p^{0},p^{1},p^{2},\ldots$ with any
unbounded sequence $r_{0}\mid r_{1}\mid r_{2}\mid\cdots$ of integers.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Ultra triples, examples: 3 (Linnaeus)}
\begin{itemize}
\item Let $E$ be the set of all living organisms. Let%
\[
d\left( e,f\right) =%
\begin{cases}
0, & \text{if }e=f;\\
1, & \text{if }e\text{ and }f\text{ belong to the same species;}\\
2, & \text{if }e\text{ and }f\text{ belong to the same genus;}\\
3, & \text{if }e\text{ and }f\text{ belong to the same family;}\\
\ldots &
\end{cases}
\]
Then, $\left( E,w,d\right) $ is an ultra triple (for any $w:E\rightarrow
\mathbb{R}$). \pause
\item More generally, any \textquotedblleft nested\textquotedblright\ family
of equivalence relations on $E$ gives a distance function for an ultra triple.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Ultra triples, examples: 4 (Darwin)}
\begin{itemize}
\item Let $T$ be a (finite, undirected) tree. For each edge $e$ of $T$, let
$\lambda\left( e\right) \geq0$ be a real. We shall call this real the
{\emph{weight}} of $e$. \pause
\item For any vertices $u$ and $v$ of $T$, let {\color{darkred}\emph{$\lambda
\left( u,v\right) $}} denote the sum of the weights of all edges on the
(unique) path from $u$ to $v$. \pause
\item Fix any vertex $r$ of $T$. Let $E$ be any subset of the vertex set of
$T$. Set%
\[
d\left( x,y\right) =\lambda\left( x,y\right) -\lambda\left( x,r\right)
-\lambda\left( y,r\right) \quad\text{ for each }\left( x,y\right) \in
E\mathbin{\underline{\times}}E.
\]
Then, $\left( E,w,d\right) $ is an ultra triple for any $w:E\rightarrow
\mathbb{R}$. \pause
\item \only<4>{\textbf{Hint to proof:} Use the well-known fact
(\textquotedblleft four-point condition\textquotedblright) saying that if
$x,y,z,w$ are four vertices of $T$, then the two largest of the three numbers
\[
\lambda\left( x,y\right) +\lambda\left( z,w\right) ,\quad\lambda\left(
x,z\right) +\lambda\left( y,w\right) ,\quad\lambda\left( x,w\right)
+\lambda\left( y,z\right)
\]
are equal.} \pause
This is particularly useful when $T$ is a \emph{phylogenetic tree} and $E$ is
a set of its leaves. \pause
Actually, this is the general case: Any (finite) ultra triple can be
translated back into a phylogenetic tree. It is ``essentially'' an inverse
operation. \newline(The idea is not new; see, e.g., Lemin 2003.)
\end{itemize}
\vspace{8.03pc}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Perimeters in ultra triples}
\begin{itemize}
\item Let $\left( E,w,d\right) $ be an ultra triple, and $S\subseteq E$ be
any subset. Then, the \emph{perimeter} of $S$ is defined to be%
\[
{\color{darkred} \operatorname*{PER}\left( S\right) }
\ \ :=\ \ \underbrace{\sum_{x\in S}w\left( x\right) }_{\left\vert
S\right\vert \text{ addends}}\ \ +\ \ \underbrace{\sum_{\substack{\left\{
x,y\right\} \subseteq S;\\x\neq y}}d\left( x,y\right) }_{\dbinom{\left\vert
S\right\vert }{2}\text{ addends}}.
\]
\pause
\item \only<2>{Thus,%
\begin{align*}
\operatorname*{PER}\varnothing & =0;\\
\operatorname*{PER}\left\{ x\right\} & =w\left( x\right) ;\\
\operatorname*{PER}\left\{ x,y\right\} & =w\left( x\right) +w\left(
y\right) +d\left( x,y\right) ;\\
\operatorname*{PER}\left\{ x,y,z\right\} & =w\left( x\right) +w\left(
y\right) +w\left( z\right) \\
& \ \ \ \ \ \ \ \ \ \ +d\left( x,y\right) +d\left( x,z\right) +d\left(
y,z\right) .
\end{align*}
} \pause
\textbf{Bhargava's problem (generalized):} Given an ultra triple $\left(
E,w,d\right) $ and an $n\in\mathbb{N}$, find the maximum perimeter of an
$n$-element subset of $E$, and find the subsets that attain it.
(The $n$ here corresponds to the $n+1$ before.) \pause
\item \only<4>{For $E\subseteq\mathbb{Z}$ and $w\left( e\right) =0$ and
$d_{p}\left( a,b\right) =-v_{p}\left( a-b\right) $, this is Bhargava's
problem.}
\only<5>{For Linnaeus or Darwin ultra triples, this is a \textquotedblleft
Noah's Ark\textquotedblright\ problem: What choices of $n$ organisms maximize
biodiversity? \newline A similar problem has been studied in:
\href{https://doi.org/10.1016/j.jtbi.2006.12.021}{Vincent Moulton, Charles
Semple, Mike Steel, \textit{Optimizing phylogenetic diversity under
constraints}, J. Theor. Biol. \textbf{246} (2007), pp. 186--194}. }
\end{itemize}
\vspace{8.1206pc}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ 3. Solving the problem}
\chaptertitle{3}{Solving the problem}
\vspace{1cm} References:
\begin{itemize}
\item \href{https://arxiv.org/abs/1909.01965}{Darij Grinberg, Fedor Petrov,
\textit{A greedoid and a matroid inspired by Bhargava's p-orderings},
arXiv:1909.01965}.
\item \href{https://arxiv.org/abs/2001.05535}{Darij Grinberg, \textit{The
Bhargava greedoid as a Gaussian elimination greedoid}, arXiv:2001.05535}.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Greedy permutations: definition}
\begin{itemize}
\item Fix an ultra triple $\left( E,w,d\right) $. \pause
\item Let $m\in\mathbb{N}$. A \emph{greedy $m$-permutation} of $E$ is a list
$\left( c_{1},c_{2},\ldots,c_{m}\right) $ of $m$ distinct elements of $E$
such that for each $i\in\left\{ 1,2,\ldots,m\right\} $ and each $x\in
E\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\} .
\]
\pause
\item In other words, a greedy $m$-permutation of $E$ is what you obtain if
you try to greedily construct a maximum-perimeter $m$-element subset of $E$,
by starting with $\varnothing$ and adding new points one at a time.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Greedy permutations: examples}
\begin{itemize}
\item Recall our four examples of ultra triples. \pause
\item In Example 1 (congruence modulo $n$), a greedy $m$-permutation is one in
which all congruence classes (that appear in $S$) are \textquotedblleft
represented as equitably as possible\textquotedblright. \pause
\item In Example 2 ($p$-adic valuation), the greedy $m$-permutations for
$\left( E,w,d_{p}\right) $ are exactly the sequences $\left( a_{0}%
,a_{1},a_{2},\ldots\right) $ constructed by Bhargava (or, rather, their
initial segments). \pause
Note: The greedy $m$-permutations for $\left( E,w,d_{p}^{\prime}\right) $
are different. The values of $d\left( e,f\right) $ matter, not just their
relative order!
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Greedy permutations: theorems}
\begin{itemize}
\item \textbf{Proposition:} For any $m\in\mathbb{N}$ with $m\leq\left\vert
E\right\vert $, there is a greedy $m$-permutation of $E$.\pause
\item \textbf{Theorem (Petrov, G.):} Let $\left( c_{1},c_{2},\ldots
,c_{m}\right) $ be any greedy $m$-permutation of $E$. Let $k\in\left\{
0,1,\dots,m\right\} $.
Then, the set $\left\{ c_{1},c_{2},\ldots,c_{k}\right\} $ has maximum
perimeter among all $k$-element subsets of $E$.\pause
\item In Example 2, this yields that Bhargava's greedy algorithm correctly
finds $\max\sum_{n\geq i>j}d_{p}\left( a_{i},a_{j}\right) $. \pause
\item \textbf{Theorem (Petrov, G.):} Let $m,k\in\mathbb{N}$ with $\left\vert
E\right\vert \geq m\geq k$. Let $A$ be a $k$-element subset of $E$ that has
maximum perimeter among all such.
Then, there exists a greedy $m$-permutation $\left( c_{1},c_{2},\ldots
,c_{m}\right) $ of $E$ such that $A=\left\{ c_{1},c_{2},\ldots
,c_k\right\} $. \pause
\item \textbf{Exercise:} Use this to prove{%
\[
\prod_{i>j}\left( i-j\right) \mid\prod_{i>j}\left( a_{i}-a_{j}\right)
\qquad\text{and}\qquad\prod_{i>j}\left( i^{2}-j^{2}\right) \mid\prod
_{i>j}\left( a_{i}^{2}-a_{j}^{2}\right) .
\]
}
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ 4. Greedoids}
\chaptertitle{4}{Greedoids}
\vspace{1cm} References:
\begin{itemize}
\item \href{https://doi.org/10.1007/978-3-642-58191-5}{Bernhard Korte,
L\'{a}szl\'{o} Lov\'{a}sz, Rainer Schrader, \textit{Greedoids}, Algorithms and
Combinatorics \#4, Springer 1991}.
\item \href{https://doi.org/10.1017/CBO9780511662041.009}{Anders Bj\"orner,
G\"unter M. Ziegler, \textit{Introd. to Greedoids}, in: Neil White (ed.),
\textit{Matroid applications}, CUP 1992}.
\item \href{https://arxiv.org/abs/1909.01965}{Darij Grinberg, Fedor Petrov,
\textit{A greedoid and a matroid inspired by Bhargava's p-orderings},
arXiv:1909.01965}.
\item \href{https://arxiv.org/abs/2001.05535}{Darij Grinberg, \textit{The
Bhargava greedoid as a Gaussian elimination greedoid}, arXiv:2001.05535}.
\item \href{https://doi.org/10.1006/eujc.1998.0287}{Victor Bryant, Ian Sharpe,
\textit{Gaussian, Strong and Transversal Greedoids}, Europ. J. Comb.
\textbf{20} (1999), pp. 259--262}.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Greedoids: introduction}
\begin{itemize}
\item So the maximum-perimeter $k$-element subsets in an ultra triple are not
just a random bunch of sets: They are accessible by a greedy algorithm.
\pause
\item This is characteristic of a \emph{greedoid} -- a \textquotedblleft
noncommutative analogue\textquotedblright\ of a matroid. \pause
\item Matroids have several \textquotedblleft cryptomorphic\textquotedblright%
\ definitions. \pause
(\textquotedblleft Cryptomorphism\textquotedblright\ = isomorphism of species,
to my understanding.) \pause
\item For greedoids, we will give two cryptomorphic definitions: one as
languages, one as set systems. See Korte/Lov\'{a}sz/Schrader for details.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Greedoids as languages}
\begin{itemize}
\item A \emph{language} on a set $E$ means a set $\mathcal{L}$ of finite
tuples of elements of $E$.
\item A tuple $\alpha=\left( \alpha_{1},\alpha_{2},\ldots,\alpha_{k}\right)
\in E^{k}$ is \emph{simple} if $\alpha_{1},\alpha_{2},\ldots,\alpha_{k}$ are distinct.
\item A language $\mathcal{L}$ on $E$ is \emph{simple} if it consists of
simple tuples. \pause
% \item \only<2>{The \emph{concatenation} $\alpha\beta$ of two tuples
% $\alpha=\left( \alpha_{1},\alpha_{2},\ldots,\alpha_{k}\right) $ and
% $\beta=\left( \beta_{1},\beta_{2},\ldots,\beta_{\ell}\right) $ is the tuple
% $\left( \alpha_{1},\alpha_{2},\ldots,\alpha_{k},\beta_{1},\beta_{2}%
% ,\ldots,\beta_{\ell}\right) $.} \pause
\item A \emph{greedoid language} on a set $E$ means a simple language $\mathcal{L}$
on $E$ such that
\begin{itemize}
\item[1.] The empty tuple $\left( {}\right) \in\mathcal{L}$.
\item[2.] If $\alpha\beta\in\mathcal{L}$, then $\alpha\in\mathcal{L}$.
\end{itemize}
\only<2>{
\begin{itemize}
\item[3.] (to be revealed...)
\end{itemize}
Here,
\begin{itemize}
\item The \emph{concatenation} $\alpha\beta$ of two tuples
$\alpha=\left( \alpha_{1},\alpha_{2},\ldots,\alpha_{k}\right) $ and
$\beta=\left( \beta_{1},\beta_{2},\ldots,\beta_{\ell}\right) $ is the tuple
$\left( \alpha_{1},\alpha_{2},\ldots,\alpha_{k},\beta_{1},\beta_{2}%
,\ldots,\beta_{\ell}\right) $.
\end{itemize}
}
\pause
\begin{itemize}
\item[3.] If $\alpha,\beta\in\mathcal{L}$ with $\left\vert \alpha\right\vert
>\left\vert \beta\right\vert $, then there exists an entry $x$ of $\alpha$
such that $\beta x\in\mathcal{L}$.
\end{itemize}
Here,
\begin{itemize}
\item any $x\in E$ is identified with the $1$-tuple $\left( x\right) $.
\item $\left\vert \alpha\right\vert $ denotes the length of a tuple $\alpha$.
\pause
\end{itemize}
\item This is analogous to the definition of a matroid (as a system of
independent sets), but using \textquotedblleft ordered sets\textquotedblright%
\ (i.e., simple tuples) instead of sets.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Greedoids as set systems}
\begin{itemize}
\item A \emph{set system} on a set $E$ means a set of subsets of $E$.
\item A \emph{greedoid} on a set $E$ means a set system $\mathcal{F}$ on $E$
such that
\begin{itemize}
\item[1.] We have $\varnothing\in\mathcal{F}$.
\item[2.] 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}%
$.\pause
\item[3.] 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}$. \pause
\end{itemize}
\item There is a canonical bijection%
\begin{align*}
\left\{ \text{greedoid languages}\right\} & \rightarrow\left\{
\text{greedoids}\right\} ,\\
\mathcal{L} & \mapsto\left\{ \operatorname*{set}\alpha\ \mid\ \alpha
\in\mathcal{L}\right\} ,
\end{align*}
where $\operatorname*{set}\left( \alpha_{1},\alpha_{2},\ldots,\alpha
_{k}\right) :=\left\{ \alpha_{1},\alpha_{2},\ldots,\alpha_{k}\right\} $.
\pause
\item In the reverse direction, send a greedoid $\mathcal{F}$ to the set of
all simple tuples $\alpha=\left( \alpha_{1},\alpha_{2},\ldots,\alpha
_{k}\right) $ such that all $\left\{ \alpha_{1},\alpha_{2},\ldots,\alpha
_{m}\right\} $ with $m\leq k$ belong to $\mathcal{F}$.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Greedoids, examples: 1 (matroids)}
\begin{itemize}
\item Let $M$ be a matroid on a ground set $E$. Then,
\[
\left\{ \text{independent sets of }M\right\}
\]
is a greedoid on $E$.
We shall call this a \emph{matroid greedoid}.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Greedoids, examples: 2 (Gaussian elimination)}
\begin{itemize}
\item Let $A$ be an $m\times n$-matrix over a field $\mathbb{K}$. Let
$E=\left\{ 1,2,\ldots,n\right\} $. Then,%
\[
\left\{ F\subseteq E\ \mid\ \text{we have }\left\vert F\right\vert \leq
n\text{ and }\det\left( \operatorname*{sub}\nolimits_{\left\{ 1,2,\ldots
,\left\vert F\right\vert \right\} }^{F}A\right) \neq0\right\}
\]
is a greedoid on $E$, where $\operatorname{sub}_F^G A$ means the
submatrix of $A$ with rows indexed by $F$ and columns indexed by $G$. \pause
\item This is called a \emph{Gaussian elimination greedoid} over $\mathbb{K}$.
\pause
\item For example, if $\mathbb{K}=\mathbb{Q}$ and $m=5$ and $n=5$ and
$A=\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 this Gaussian elimination greedoid is%
\begin{align*}
& \Big\{\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\} \Big\}.
\end{align*}
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Greedoids, examples: 3 (order ideals)}
\begin{itemize}
\item Let $P$ be a finite poset. Let $J$ be the set of all \emph{order ideals}
of $P$ (that is, of all subsets $I$ of $P$ such that $\left( b\in I\right)
\wedge\left( a\leq b\right) \Longrightarrow\left( a\in I\right) $).
\item Then, $J$ is a greedoid on $P$.
We shall call this an \emph{order ideal greedoid}. \pause
\item The corresponding greedoid language consists of all linear extensions of
all order ideals of $P$.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ The Bhargava greedoid}
\begin{itemize}
\item Back to our setting: For any ultra triple $\left( E,w,d\right) $,
define%
\begin{align*}
\mathcal{B}\left( E,w,d\right) & =\left\{ A\subseteq E\ \mid\ A\text{ has
maximum perimeter among}\right. \\
& \ \ \ \ \ \ \ \ \ \ \left. \text{ 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 }\right. \\
& \ \ \ \ \ \ \ \ \ \ \left. \ \text{all }B\subseteq E\text{ satisfying
}\left\vert B\right\vert =\left\vert A\right\vert \right\} .
\end{align*}
We call this the \emph{Bhargava greedoid} of $\left( E,w,d\right) $.
\pause
\item \textbf{Theorem (G., Petrov):} This Bhargava greedoid $\mathcal{B}%
\left( E,w,d\right) $ is a greedoid indeed.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Strong greedoids: definition}
\begin{itemize}
\item Recall: A \emph{greedoid} on a set $E$ means a set system $\mathcal{F}$
on $E$ such that
\begin{itemize}
\item[1.] We have $\varnothing\in\mathcal{F}$.
\item[2.] 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[3.] 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}$. \pause
\end{itemize}
\item A \emph{strong greedoid} on $E$ means a greedoid $\mathcal{F}$ on $E$
that also satisfies
\begin{itemize}
\item[4.] 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}$. \pause
\end{itemize}
\item \only<3>{\textbf{Remark:} Axiom 4. implies axiom 3.}
\only<4-5>{\textbf{Remark:} In axiom 3., we can replace the condition
\textquotedblleft$\left\vert B\right\vert =\left\vert A\right\vert
+1$\textquotedblright\ by the weaker \textquotedblleft$\left\vert B\right\vert
>\left\vert A\right\vert $\textquotedblright; the axiom stays equivalent. }
\only<5>{But we cannot do the same in axiom 4. (it would become much
stronger, forcing $\mathcal{F}$ to be a matroid greedoid).}
\only<6>{Strong greedoids are also known as \textquotedblleft\emph{Gauss
greedoids}\textquotedblright\ (not to be confused with Gaussian elimination
greedoids).}
\end{itemize}
\vspace{10pc}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Strong greedoids: examples}
\begin{itemize}
\item All matroid greedoids (Example 1 above) are strong greedoids. \pause
\item All Gaussian elimination greedoids (Example 2 above) are strong
greedoids. \pause
(\textbf{Proof idea:} Pl\"{u}cker relations for determinants can be
used.)\pause
\item \textbf{Not} all order ideal greedoids (Example 3 above) are strong
greedoids. \pause
\item \textbf{Theorem (Bryant, Sharpe):} Let $\mathcal{F}$ be a strong
greedoid, and $k \in\mathbb{N}$. Then, the $k$-element sets that belong to
$\mathcal{F}$ are the bases of a matroid (unless there are none of them).
\pause \newline If $\mathcal{F}$ is a Gaussian elimination greedoid, then the
latter matroid is representable.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Gaussianity of the Bhargava greedoid}
\begin{itemize}
\item \textbf{Theorem (G., Petrov):} The Bhargava greedoid $\mathcal{B}\left(
E,w,d\right) $ of any ultra triple $\left( E,w,d\right) $ is a strong
greedoid. \pause
\item \textbf{Theorem (G.):} Let $\left( E,w,d\right) $ be an ultra triple.
Let $\mathbb{K}$ be any field of size $\left\vert \mathbb{K}\right\vert
\geq\left\vert E\right\vert $.
Then, the Bhargava greedoid $\mathcal{B}\left( E,w,d\right) $ is (up to
renaming the elements of $E$) a Gaussian elimination greedoid over
$\mathbb{K}$. \pause
\item Note that this Theorem yields the previous one, which is thus
proved twice. \pause
\item \only<4>{\textbf{Stronger theorem (G.):} Let $\left( E,w,d\right) $ be
an ultra triple. Let $\mathbb{K}$ be any field of size $\left\vert
\mathbb{K}\right\vert \geq\operatorname*{mcs}\left( E,w,d\right) $, where
$\operatorname*{mcs}\left( E,w,d\right) $ is the \emph{maximum clique size}
of $E$ (that is, the maximum size of a subset $C\subseteq E$ such that
$d\mid_{C\mathbin{\underline{\times}}C}$ is constant). \newline Then, the
Bhargava greedoid $\mathcal{B}\left( E,w,d\right) $ is (up to renaming the
elements of $E$) a Gaussian elimination greedoid over $\mathbb{K}$.} \pause
\textbf{Converse theorem (G.):} Assume that the map $w$ is constant. Let
$\mathbb{K}$ be a field. Then, the Bhargava greedoid $\mathcal{B}\left(
E,w,d\right) $ is (up to renaming the elements of $E$) a Gaussian elimination
greedoid over $\mathbb{K}$ \textbf{if and only if} $\left\vert \mathbb{K}%
\right\vert \geq\operatorname*{mcs}\left( E,w,d\right) $.
\end{itemize}
\vspace{10.0375pc}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ A few words about the proofs, 1}
\begin{itemize}
\item We have a combinatorial proof that $\mathcal{B}\left( E,w,d\right) $
is a strong greedoid (using what we call \textquotedblleft
projections\textquotedblright). \pause
\item But the theorem about $\mathcal{B}\left( E,w,d\right) $ being a
Gaussian elimination greedoid requires a different approach. Here are its main
ideas: \pause
\item \textbf{1st step:} If $\left( E,w,d\right) $ is a Bhargava-type
ultra triple $\left(
E,w,d_{p}\right) $ for some prime $p$ and some $E\subseteq\mathbb{Z}$, then
we can explicitly find a matrix $A$ over $\mathbb{F}_{p}$ that gives
$\mathcal{B}\left( E,w,d\right) $ as its Gaussian elimination greedoid.
\only<4>{ Even better, this matrix $A$ is the projection of a matrix $\widetilde{A}$
over $\mathbb{Z}$ that satisfies%
\[
v_{p}\left( \det\left( \operatorname*{sub}\nolimits_{\left\{ 1,2,\ldots
,\left\vert F\right\vert \right\} }^{F}\widetilde{A}\right) \right) =\left( \text{max.
possible perimeter}\right) -\operatorname*{PER}\left( F\right)
\]
for each subset $F$ of $E$. \pause
(The matrix $\widetilde{A}$ is a Vandermonde-like matrix, with
entries $\dfrac{1}{p^{\text{something}}}\left( a_{i}-e_{1}\right) \left(
a_{i}-e_{2}\right) \cdots\left( a_{i}-e_{j}\right) $.)} \pause
\item \textbf{2nd step:} So we know how to deal with Bhargava-type ultra
triples. It would be nice if any ultra triple was isomorphic to one of them!
\pause
I'm not sure this is true, but I can prove something close that suffices:
\end{itemize}
\vspace{9pc}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ A few words about the proofs, 2}
\begin{itemize}
\item \textbf{2nd step, continued:} Replace $\mathbb{Z}$ by an arbitrary
valuation ring with value group $\mathbb{R}$, and replace $v_p$ by its
valuation.\pause
Construct the natural analogue of the Bhargava-type
$\left( E,w,d_{p}\right) $ in this setting. \pause
A similar argument shows that its Bhargava greedoid is a Gaussian elimination
greedoid.\pause
Actually, let's not complicate our life: It suffices to find \textbf{one}
valuation ring that works -- e.g., the monoid ring of the additive monoid
$\mathbb{R}_{+}$ over $\mathbb{K}$. (Think of it as a polynomial ring that
allows non-integer exponents.)\pause
\item \textbf{3rd step:} Prove that every ultra triple $\left( E,w,d\right)
$ with $\left\vert \mathbb{K}\right\vert \geq\operatorname*{mcs}\left(
E,w,d\right) $ is isomorphic to a generalized Bhargava-type ultra triple in this monoid
ring over $\mathbb{K}$.\pause
(The proof proceeds by strong induction, decomposing the ultra triple into
smaller ones. Iterating this decomposition again reveals the connection to
phylogenetic trees.)
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Questions}
\begin{itemize}
\item If $w$ is constant, then we have a necessary and sufficient condition
for $\mathcal{B}\left( E,w,d\right) $ to be a Gaussian elimination greedoid
over $\mathbb{K}$.
What about the general case? ($\left\vert \mathbb{K}\right\vert \geq
\operatorname*{mcs}\left( E,w,d\right) $ is still sufficient, but no longer
necessary.)\pause
\item {\href{https://doi.org/10.1016/j.jtbi.2006.12.021}{Moulton, Semple and
Steel} define phylogenetic diversity (for a set of leaves of a phylogenetic
tree) somewhat similarly to our perimeter, yet differently. Still, they show
that their maximum-diversity subsets form a strong greedoid (not the same as
ours).}
Is this greedoid a Gaussian elimination greedoid, too?\pause
\item It is not too hard to define a multiset analogue of greedoids (e.g., by
lifting the \textquotedblleft simple\textquotedblright\ requirement on
greedoid languages). How much of the theory adapts?
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Bonus problem}
\chaptertitle{}{Bonus problem: stalagmic greedoids}
\vspace{1cm} References:
\begin{itemize}
\item to be written (contact me).
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Bonus problem: stalagmic greedoids}
\begin{itemize}
\item \textbf{Proposition (G., easy consequence of known facts):}
Let $E$ and $U=\left\{ u_{1},u_{2},\ldots,u_{n}\right\} $ be two disjoint
finite sets (with $u_{1},u_{2},\ldots,u_{n}$ distinct).
Let $\mathcal{B}$ be the set of bases of a matroid on ground set $E\cup U$.
Assume that $\left\{ u_{1},u_{2},\ldots,u_{n}\right\} \in\mathcal{B}$. Let%
\[
\mathcal{F}=\left\{ F\subseteq E\ \mid\ \left\vert F\right\vert \leq n\text{
and }F\cup\left\{ u_{\left\vert F\right\vert +1},u_{\left\vert F\right\vert
+2},\ldots,u_{n}\right\} \in\mathcal{B}\right\} .
\]
Then, $\mathcal{F}$ is a strong greedoid on ground set $E$. \pause
\item We call such a greedoid $\mathcal{F}$ \emph{stalagmic}. \pause
\item It is easy to see that matroid greedoids and Gaussian elimination
greedoids are stalagmic. \pause
\item \textbf{Question:} Is every strong greedoid stalagmic?\pause
\item \textbf{If no}, then we have a new class of greedoids at our hands,
which we can try to axiomatically characterize. \pause
\item \textbf{If yes}, then we have found a machine for deriving properties of
strong greedoids from properties of matroids.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{\ \ \ \ \ Thank you!}
\begin{itemize}
\item \textbf{Fedor Petrov} for getting this started by answering
\href{https://mathoverflow.net/questions/314130/}{my MathOverflow question
\#314130}.
\item \textbf{Alexander Postnikov} for interesting conversations.
\item \textbf{you} for your patience and typo hunting.
\end{itemize}
\end{frame}
\end{document}