\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{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%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}
\definecolor{lightgreen}{RGB}{14, 140, 14}
\newcommand{\red}{\color{red}}
\newcommand{\darkred}{\color{darkred}}
\newcommand{\grey}{\color{grau}}
\newcommand{\green}{\color{forestgreen}}
\newcommand{\lightgreen}{\color{lightgreen}}
\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{\GEG}{\operatorname{GEG}}
\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\colstrut{\vphantom{\dfrac{a}{w}}} % Vertical buffer space.
\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\vspace{-1.5pc}}
\title{From the Vandermonde determinant to generalized factorials to
greedoids and back}
\date{2022, New York Number Theory Zoom Seminar}
% \\ {\bf \red This talk is being recorded!}}

\frame{\titlepage\textbf{slides:} {\color{red}
\url{http://www.cip.ifi.lmu.de/~grinberg/algebra/greedtalk-ny2022.pdf} }
\newline\textbf{extended abstract with further references:} {{\color{red}
\url{http://www.cip.ifi.lmu.de/~grinberg/algebra/fps20gfv.pdf}}}
\newline\textbf{solutions to exercises:} {at the end of the slides}}

% Abstract: A classical result in elementary number theory says that the
% product of the pairwise differences between any given n + 1 integers
% is divisible by the product of the pairwise differences between 0, 1,
% ..., n. In the late 90s, Manjul Bhargava developed this much further
% into a theory of "generalized factorials", in particular giving a
% quasi-algorithm for finding the gcd of the products of the pairwise
% differences between any n + 1 integers in S, where n is a given number
% and S is a given set of integers.
% In this talk, I will explain why this is actually a combinatorial
% question in disguise, and how to answer it in full generality (joint
% work with Fedor Petrov). The general setting is a finite set E
% equipped with weights (every element of E has a weight) and distances
% (any two distinct elements of E have a distance), where the distances
% satisfy the ultrametric triangle inequality. The question is then to
% find a subset of E of given size that has maximum perimeter (i.e., sum
% of weights of elements plus their pairwise distances). It turns out
% that all such subsets form a "strong greedoid" -- a type of set system
% particularly adapted to optimization. Even better, this greedoid is a
% "Gaussian elimination greedoid" -- which, roughly speaking, means that
% the problem reduces to linear algebra.
% If time allows, I will briefly discuss another closely related
% greedoid coming from a rather similar problem in phylogenetics. (This
% is mostly due to Manson, Moulton, Semple and Steel.)

\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 \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)
.
\]
(Here and in the following, $\prod\limits_{i>j}$ means $\prod\limits_{n \geq i>j \geq 0}$.)
\end{itemize}

\vspace{15pc}
\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ It begins with a Vandermonde}

\begin{itemize}
\item \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)  .
\]
(Here and in the following, $\prod\limits_{i>j}$ means $\prod\limits_{n \geq i>j \geq 0}$.)
\pause

\item For example:
\[
1 \mid 1 ;
\]
\pause
\[
1 = 1-0 \mid a_1 - a_0 ;
\]
\pause
\[
2 = \tup{1-0} \tup{2-1} \tup{2-0} \mid \tup{a_1 - a_0} \tup{a_2 - a_1} \tup{a_2 - a_0} ;
\]
\pause
\begin{align*}
12 = & \tup{1-0} \tup{2-1} \tup{2-0} \tup{3-2} \tup{3-1} \tup{3-0} \\
& \mid \tup{a_1 - a_0} \tup{a_2 - a_1} \tup{a_2 - a_0}
       \tup{a_3 - a_2} \tup{a_3 - a_1} \tup{a_3 - a_0};
\end{align*}
and so on.

\end{itemize}

\vspace{15pc}
\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ It begins with a Vandermonde: proofs}

\begin{itemize}
\item \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 \textbf{Hint to proof 1:} Show that \vspace{-0.7pc}
\[
\dfrac{\operatorname*{RHS}}{\operatorname*{LHS}}
=\det\left(  \dbinom{a_{i}}{j}\right)%
_{i,j\in\left\{  0,1,\ldots,n\right\}  }
=
\det \begin{pmatrix}
\binom{a_0}{0} & \binom{a_0}{1} & \cdots & \binom{a_0}{n} \colstrut\\
\binom{a_1}{0} & \binom{a_1}{1} & \cdots & \binom{a_1}{n} \\
\vdots & \vdots & \ddots & \vdots \\
\binom{a_n}{0} & \binom{a_n}{1} & \cdots & \binom{a_n}{n}
\end{pmatrix} .
\] \pause
\only<3>{%
This might remind you of the Vandermonde determinant, which
says that \vspace{-0.7pc}
\[
\prod_{i>j}\left(  a_{i}-a_{j}\right)
=\det\left(  a_i^j
\right)  _{i,j\in\left\{  0,1,\ldots,n\right\}  }
=
\det \begin{pmatrix}
a_0^0 & a_0^1 & \cdots & a_0^n \colstrut\\
a_1^0 & a_1^1 & \cdots & a_1^n \\
\vdots & \vdots & \ddots & \vdots \\
a_n^0 & a_n^1 & \cdots & a_n^n
\end{pmatrix} .
\]
}%
\only<4>{%
Both are particular cases of the general ... \\
\textbf{Theorem:} If $a_0, a_1, \ldots, a_n$ are
numbers, and $P_0, P_1, \ldots, P_n$ are polynomials
with $\deg P_j \leq j$ for each $j$, then
\[
\det \tup{ \tup{P_j\tup{a_i} }_{i, j \in \set{0,1,\ldots,n}} }
= \ell_0 \ell_1 \cdots \ell_n \prod_{i>j}\left(  a_{i}-a_{j}\right) ,
\]
where $\ell_j$ is the $x^j$-coefficient of $P_j$.
{\footnotesize [\textbf{Exercise 1:} Prove this!]}
}
\end{itemize}

\vspace{15pc}
\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ It begins with a Vandermonde: proofs}

\begin{itemize}
\item \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)  .
\]

\item \textbf{Hint to proof 2:} WLOG assume $0\leq a_{0}%
<a_{1}<\cdots<a_{n}$.
\only<1>{ \\
(Otherwise, move each $a_i$ preserving $a_i
\operatorname{mod}\operatorname*{LHS}$.)}
\newline
\only<2>{
Consider an array of $n+1$ left-justified rows with lengths
$a_0 - 0, a_1 - 1, \ldots, a_n - n$ from bottom to top: \\
e.g., if $n = 3$ and $\tup{a_0, a_1, \ldots, a_n} = \tup{2, 4, 5, 7}$,
then it is
\[
\ydiagram{4,3,3,2} \ .
\phantom{\qquad \tup{\text{a ``semistandard tableau''}}}
\]
}
\only<3->{
Now fill this array with numbers $\in \left\{1, 2, \ldots, n+1\right\}$
that \textbf{increase weakly along rows}
and \textbf{increase strictly down columns}, e.g.:
\[
\begin{ytableau}
1 & 1 & 2 & 4 \\
2 & 2 & 3 \\
3 & 4 & 4 \\
4
\end{ytableau}
\qquad \tup{\text{a ``semistandard tableau''}}. \vspace{-0.5pc}
\]
}
\only<4-5>{The number of such fillings
is $\dfrac{\operatorname*{RHS}}{\operatorname*{LHS}}$. \\
(``Weyl's character formula'' in type A; see
\href{https://mathoverflow.net/questions/106606/new-formula-for-counting-ssyts}{MathOverflow question \#106606}.)}
\only<5>{\textbf{Question:} Bijective proof?}
\end{itemize}

\vspace{15pc}
\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ It begins with a Vandermonde: proofs}

\begin{itemize}
\item \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)  .
\]


\item \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} (Bhargava?)\textbf{:} \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)  .
\]
{\footnotesize [\textbf{Exercise 2:} Prove that
$\dfrac{0!\cdot2!\cdot\cdots\cdot\left(  2n\right)  !}{2^{n}}
= \prod\limits_{i>j}\left(  i^{2}-j^{2}\right)$, so this is really
a restatement!]} \vspace{1pc}
\pause


\item \only<3>{Analogues of the 3 above proofs work (I believe). \\
{\footnotesize [\textbf{Exercise 3:} Check this!]}}
\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\}  \ ?
\]
\pause

\item Already for $n = 6$, there is no choice of
$a_0, a_1, \ldots, a_n$ that attains the gcd
(such as $0,1,\ldots,n$ was for first powers
and for squares).

\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. Fix $n \geq 0$. What is
\[
\gcd\left\{  \prod_{i>j}\left(  a_{i}-a_{j}\right)  \ \mid\ a_{0},a_{1}%
,\ldots,a_{n}\in S\right\}  \ ?
\]
\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. Set ${\darkred \mathbb{N}} := \set{0,1,2,\ldots}$.

\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$.

\item Set $v_{p}\left(  0\right)  =+\infty$. \pause

\only<2>{\item \textbf{Examples:}
\[
\begin{tabular}[c]{cc|cc}
$v_3 \left(18\right) = 2;$ & \ \ \  & \ \ \  & $v_3 \left(17\right) = 0  ;$\\
$v_2 \left(14\right) = 1;$ &  &  & $v_2 \left( 16 \right) = 4 .$
\end{tabular}
\]}
\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<4-5>{ 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<5>{The $p$-distance is not very geometric: For instance, $2$ is
closer to $p+2$ than to $1$, and even closer to $p^2+2$. \\
Cf. the \href{https://en.wikipedia.org/wiki/Solenoid_(mathematics)\#p-adic_solenoids}{$p$-adic solenoid}.
Also, \href{http://chronologia.org/en/math_impressions/poster018.html}{artistic rendition by Fomenko}.}

\only<6>{ 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-2>{ \textbf{Equivalent problem:} Let $S$ be a set of integers. Let
$p$ be a prime. Fix $n \geq 0$. 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\}  \ ?
\]}
\only<2>{And when is it attained?}

\only<3>{\textbf{Equivalent problem:} Let $S$ be a set of integers. Let $p$ be
a prime. Fix $n \geq 0$. 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<4-5>{\textbf{Equivalent problem:} Let $S$ be a set of integers. Let $p$
be a prime. Fix $n \geq 0$. 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 \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 \only<7-14>{\textbf{Example:} $p = 2$ and $S = \set{1,2,3,4,5,6}$.}
\only<8>{
\[
\begin{tikzpicture}
\draw[] (0, 1) ellipse (1 and 2);
\draw[] (4, 1) ellipse (1 and 2);
\draw[] (-1, 1) -- (1, 1);
\draw[] (0, 1) -- (0, 3);
\draw[] (3, 1) -- (5, 1);
\draw[] (4, 1) -- (4, 3);
\tikzstyle{every node} = [circle]
\node (a) at (0, 0) {3};
\node (b) at (-0.5, 2) {1};
\node (c) at (0.5, 2) {5};
\node (d) at (3.5, 2) {2};
\node (e) at (4.5, 2) {6};
\node (f) at (4, 0) {4};
\end{tikzpicture}
\]
}
\only<9>{
\[
\begin{tikzpicture}
\draw[] (0, 1) ellipse (1 and 2);
\draw[] (4, 1) ellipse (1 and 2);
\draw[] (-1, 1) -- (1, 1);
\draw[] (0, 1) -- (0, 3);
\draw[] (3, 1) -- (5, 1);
\draw[] (4, 1) -- (4, 3);
\tikzstyle{every node} = [circle]
\node (a) at (0, 0) {3};
\node (b) at (-0.5, 2) {1};
\node (c) at (0.5, 2) {5};
\node (d) at (3.5, 2) {\red 2};
\node (e) at (4.5, 2) {6};
\node (f) at (4, 0) {4};
\end{tikzpicture}
\]
}
\only<10>{
\[
\begin{tikzpicture}
\draw[] (0, 1) ellipse (1 and 2);
\draw[] (4, 1) ellipse (1 and 2);
\draw[] (-1, 1) -- (1, 1);
\draw[] (0, 1) -- (0, 3);
\draw[] (3, 1) -- (5, 1);
\draw[] (4, 1) -- (4, 3);
\tikzstyle{every node} = [circle]
\node (a) at (0, 0) {3};
\node (b) at (-0.5, 2) {1};
\node (c) at (0.5, 2) {\red 5};
\node (d) at (3.5, 2) {\red 2};
\node (e) at (4.5, 2) {6};
\node (f) at (4, 0) {4};
\end{tikzpicture}
\]
}
\only<11>{
\[
\begin{tikzpicture}
\draw[] (0, 1) ellipse (1 and 2);
\draw[] (4, 1) ellipse (1 and 2);
\draw[] (-1, 1) -- (1, 1);
\draw[] (0, 1) -- (0, 3);
\draw[] (3, 1) -- (5, 1);
\draw[] (4, 1) -- (4, 3);
\tikzstyle{every node} = [circle]
\node (a) at (0, 0) {3};
\node (b) at (-0.5, 2) {1};
\node (c) at (0.5, 2) {\red 5};
\node (d) at (3.5, 2) {\red 2};
\node (e) at (4.5, 2) {6};
\node (f) at (4, 0) {\red 4};
\end{tikzpicture}
\]
}
\only<12>{
\[
\begin{tikzpicture}
\draw[] (0, 1) ellipse (1 and 2);
\draw[] (4, 1) ellipse (1 and 2);
\draw[] (-1, 1) -- (1, 1);
\draw[] (0, 1) -- (0, 3);
\draw[] (3, 1) -- (5, 1);
\draw[] (4, 1) -- (4, 3);
\tikzstyle{every node} = [circle]
\node (a) at (0, 0) {\red 3};
\node (b) at (-0.5, 2) {1};
\node (c) at (0.5, 2) {\red 5};
\node (d) at (3.5, 2) {\red 2};
\node (e) at (4.5, 2) {6};
\node (f) at (4, 0) {\red 4};
\end{tikzpicture}
\]
}
\only<13>{
\[
\begin{tikzpicture}
\draw[] (0, 1) ellipse (1 and 2);
\draw[] (4, 1) ellipse (1 and 2);
\draw[] (-1, 1) -- (1, 1);
\draw[] (0, 1) -- (0, 3);
\draw[] (3, 1) -- (5, 1);
\draw[] (4, 1) -- (4, 3);
\tikzstyle{every node} = [circle]
\node (a) at (0, 0) {\red 3};
\node (b) at (-0.5, 2) {\red 1};
\node (c) at (0.5, 2) {\red 5};
\node (d) at (3.5, 2) {\red 2};
\node (e) at (4.5, 2) {6};
\node (f) at (4, 0) {\red 4};
\end{tikzpicture}
\]
}
\only<14>{
\[
\begin{tikzpicture}
\draw[] (0, 1) ellipse (1 and 2);
\draw[] (4, 1) ellipse (1 and 2);
\draw[] (-1, 1) -- (1, 1);
\draw[] (0, 1) -- (0, 3);
\draw[] (3, 1) -- (5, 1);
\draw[] (4, 1) -- (4, 3);
\tikzstyle{every node} = [circle]
\node (a) at (0, 0) {\red 3};
\node (b) at (-0.5, 2) {\red 1};
\node (c) at (0.5, 2) {\red 5};
\node (d) at (3.5, 2) {\red 2};
\node (e) at (4.5, 2) {\red 6};
\node (f) at (4, 0) {\red 4};
\end{tikzpicture}
\]
} \pause \pause \pause \pause\pause \pause \pause \pause

Thus, the choice of $a_{n}$ tactically (near-sightedly)
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 ``greedy''.) But is it strategically optimal? \pause

\item \textbf{Theorem (Bhargava):} Yes. That is: \\
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
isn't always such a sequence that works for all $p$ simultaneously.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Prime numbers be gone}

\begin{itemize}
\item In his first (1997) paper on the subject, Bhargava already noticed
that $p$ is a red herring: The properties of $d_{p}$ are all that is needed.

\begin{enumerate}
\item[\ ] {\footnotesize
\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}

{\footnotesize (Theorem 1 is a slight generalization of the above Theorem.)}
\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$.

\only<1-2>{\vphantom{empty line}\\\vphantom{empty line}\\\vphantom{empty line}}
\only<1>{
\[
\begin{tikzpicture}
\draw[] (0, 0) -- (2, 1);
\draw[] (2, 1) -- (2, 0);
\draw[] (3, 0) -- (2, 1);
\draw[] (2, 1) -- (1, 3);
\draw[] (1, 3) -- (0, 1);
\draw[] (0, 3) -- (1, 3) node [midway, above] {$\phantom{1}$};
\tikzstyle{every node} = [circle]
\node [fill=white] (t) at (0, 0) {$t$};
\node [fill=white] (u) at (2, 0) {$u$};
\node [fill=white] (v) at (3, 0) {$v$};
\node [fill=white] (s) at (2, 1) {$s$};
\node [fill=white] (q) at (0, 1) {$q$};
\node [fill=white] (r) at (0, 3) {$r$};
\node [fill=white] (p) at (1, 3) {$p$};
\end{tikzpicture}
\]
}
\only<2>{
\[
\begin{tikzpicture}
\draw[] (0, 0) -- (2, 1) node [midway, above] {$2$};
\draw[] (2, 1) -- (2, 0) node [midway, left] {$1$};
\draw[] (3, 0) -- (2, 1) node [midway, right] {$1$};
\draw[] (2, 1) -- (1, 3) node [midway, right] {$3$};
\draw[] (1, 3) -- (0, 1) node [midway, left] {$3$};
\draw[] (0, 3) -- (1, 3) node [midway, above] {$1$};
\tikzstyle{every node} = [circle]
\node [fill=white] (t) at (0, 0) {$t$};
\node [fill=white] (u) at (2, 0) {$u$};
\node [fill=white] (v) at (3, 0) {$v$};
\node [fill=white] (s) at (2, 1) {$s$};
\node [fill=white] (q) at (0, 1) {$q$};
\node [fill=white] (r) at (0, 3) {$r$};
\node [fill=white] (p) at (1, 3) {$p$};
\end{tikzpicture}
\]
}
\pause\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$.

\only<3>{
\[
\begin{tikzpicture}
\draw[ultra thick] (0, 0) -- (2, 1) node [midway, above] {$2$};
\draw[] (2, 1) -- (2, 0) node [midway, left] {$1$};
\draw[] (3, 0) -- (2, 1) node [midway, right] {$1$};
\draw[ultra thick] (2, 1) -- (1, 3) node [midway, right] {$3$};
\draw[ultra thick] (1, 3) -- (0, 1) node [midway, left] {$3$};
\draw[] (0, 3) -- (1, 3) node [midway, above] {$1$};
\tikzstyle{every node} = [circle]
\node [fill=white] (t) at (0, 0) {$t$};
\node [fill=white] (u) at (2, 0) {$u$};
\node [fill=white] (v) at (3, 0) {$v$};
\node [fill=white] (s) at (2, 1) {$s$};
\node [fill=white] (q) at (0, 1) {$q$};
\node [fill=white] (r) at (0, 3) {$r$};
\node [fill=white] (p) at (1, 3) {$p$};
\end{tikzpicture}
\]
\[
\Longrightarrow \qquad
\lambda\tup{q,t} = 3+3+2 .
\]
}
\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<5>{\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. {\footnotesize [\textbf{Exercise 4:} Prove this!]}} \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 {\footnotesize \textbf{Exercise 5:} 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 I will now define greedoids. \\
Warning: some abstraction to follow.

\end{itemize}
\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Greedoids}

\begin{itemize}
\item A \emph{set system} on a set $E$ means a set of subsets of $E$. \pause

\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}$. \pause

\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 \textbf{Example:} $E = \set{1, 2, 3, 4, 5}$ and
\only<5>{
\begin{align*}
\mathcal{F}
&= \left\{ \colstrut\varnothing, \set{1}, \set{2}, \set{5}, \set{1, 2},
           \set{1, 5}, \set{2, 5},
   \right. \\
&  \left. \quad\qquad
           \set{4, 5}, \set{1, 2, 3}, \set{1, 2, 5},
           \set{2, 4, 5}, \set{3, 4, 5} \colstrut
   \right\} .
\end{align*}
}
\only<6>{
\begin{align*}
\mathcal{F}
&= \left\{ \colstrut \varnothing, \set{1}, \set{2}, \set{5}, \set{1, 2},
           \set{1, 5}, \set{2, 5},
   \right. \\
&  \left. \quad\qquad
           \set{4, 5}, {\blue \set{1, 2, 3}}, \set{1, 2, 5},
           \set{2, 4, 5}, \set{3, 4, 5} \colstrut
   \right\} .
\end{align*}
Check axiom 2. for $B = {\blue \set{1, 2, 3}}$!
}
\only<7>{
\begin{align*}
\mathcal{F}
&= \left\{ \colstrut \varnothing, \set{1}, \set{2}, \set{5}, {\lightgreen \set{1, 2}},
           \set{1, 5}, \set{2, 5},
   \right. \\
&  \left. \quad\qquad
           \set{4, 5}, {\blue \set{1, 2, 3}}, \set{1, 2, 5},
           \set{2, 4, 5}, \set{3, 4, 5} \colstrut
   \right\} .
\end{align*}
Axiom 2. holds for $B = {\blue \set{1, 2, 3}}$, since we can
take $b = 3$.
}
\only<8>{
\begin{align*}
\mathcal{F}
&= \left\{ \colstrut \varnothing, \set{1}, \set{2}, \set{5}, \set{1, 2},
           \set{1, 5}, \set{2, 5},
   \right. \\
&  \left. \quad\qquad
           \set{4, 5}, \set{1, 2, 3}, \set{1, 2, 5},
           {\blue \set{2, 4, 5}}, \set{3, 4, 5} \colstrut
   \right\} .
\end{align*}
Check axiom 2. for $B = {\blue \set{2, 4, 5}}$!
}
\only<9>{
\begin{align*}
\mathcal{F}
&= \left\{ \colstrut \varnothing, \set{1}, \set{2}, \set{5}, \set{1, 2},
           \set{1, 5}, {\lightgreen \set{2, 5}},
   \right. \\
&  \left. \quad\qquad
           {\lightgreen \set{4, 5}}, \set{1, 2, 3}, \set{1, 2, 5},
           {\blue \set{2, 4, 5}}, \set{3, 4, 5} \colstrut
   \right\} .
\end{align*}
Axiom 2. holds for $B = {\blue \set{2, 4, 5}}$, since we can take
$b = 4$ or $b = 2$.
}
\only<10>{
\begin{align*}
\mathcal{F}
&= \left\{ \colstrut \varnothing, \set{1}, \set{2}, \set{5}, \set{1, 2},
           {\blue \set{1, 5}}, \set{2, 5},
   \right. \\
&  \left. \quad\qquad
           \set{4, 5}, \set{1, 2, 3}, \set{1, 2, 5},
           {\blue \set{2, 4, 5}}, \set{3, 4, 5} \colstrut
   \right\} .
\end{align*}
Check axiom 3. for $A = {\blue \set{1, 5}}$ and $B = {\blue \set{2, 4, 5}}$!
}
\only<11>{
\begin{align*}
\mathcal{F}
&= \left\{ \colstrut \varnothing, \set{1}, \set{2}, \set{5}, \set{1, 2},
           {\blue \set{1, 5}}, \set{2, 5},
   \right. \\
&  \left. \quad\qquad
           \set{4, 5}, \set{1, 2, 3}, {\lightgreen \set{1, 2, 5}},
           {\blue \set{2, 4, 5}}, \set{3, 4, 5} \colstrut
   \right\} .
\end{align*}
Axiom 3. holds for $A = {\blue \set{1, 5}}$ and $B = {\blue \set{2, 4, 5}}$,
since we can take $b = 2$.
}
\only<12>{
\begin{align*}
\mathcal{F}
&= \left\{ \colstrut \varnothing, \set{1}, \set{2}, \set{5}, \set{1, 2},
           \set{1, 5}, \set{2, 5},
   \right. \\
&  \left. \quad\qquad
           {\blue \set{4, 5}}, \set{1, 2, 3}, \set{1, 2, 5},
           {\blue \set{2, 4, 5}}, \set{3, 4, 5} \colstrut
   \right\} .
\end{align*}
Check axiom 3. for $A = {\blue \set{4, 5}}$ and $B = {\blue \set{2, 4, 5}}$!
}
\only<13>{
\begin{align*}
\mathcal{F}
&= \left\{ \colstrut \varnothing, \set{1}, \set{2}, \set{5}, \set{1, 2},
           \set{1, 5}, \set{2, 5},
   \right. \\
&  \left. \quad\qquad
           {\blue \set{4, 5}}, \set{1, 2, 3}, \set{1, 2, 5},
           {\green \set{2, 4, 5}}, \set{3, 4, 5} \colstrut
   \right\} .
\end{align*}
Axiom 3. holds for $A = {\blue \set{4, 5}}$ and $B = {\blue \set{2, 4, 5}}$,
since we can take $b = 2$.

(More generally, Axiom 3. always holds if $A \subseteq B$.)
}

\end{itemize}
\vspace{15pc}
\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Greedoids, examples: 1 (matroids)}

\begin{itemize}
\item If you have seen matroids:

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}_{\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}$.
We denote it by \emph{$\GEG(A)$}.
\only<2>{\\
\footnotesize [\textbf{Exercise 6:} Prove that it is a greedoid!]}
\pause

\item For example, if $\mathbb{K}=\mathbb{Q}$ and $m=5$ and $n=5$ and
\only<3,7>{
$A=
\begin{pmatrix}
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{pmatrix}$}%
\only<4>{
$A=
\begin{pmatrix}
0 & {\lightgreen 1} & 1 & 0 & {\lightgreen 1}\\
1 & {\lightgreen 1} & 0 & 0 & {\lightgreen 0}\\
0 & 2 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 0
\end{pmatrix}$}%
\only<5>{
$A=
\begin{pmatrix}
{\lightgreen 0} & {\lightgreen 1} & {\lightgreen 1} & 0 & {\lightgreen 1}\\
{\lightgreen 1} & {\lightgreen 1} & {\lightgreen 0} & 0 & {\lightgreen 0}\\
{\lightgreen 0} & {\lightgreen 2} & {\lightgreen 1} & 0 & {\lightgreen 1}\\
{\lightgreen 1} & {\lightgreen 0} & {\lightgreen 1} & 0 & {\lightgreen 0}\\
0 & 0 & 0 & 0 & 0
\end{pmatrix}$}%
\only<6>{
$A=
\begin{pmatrix}
0 & 1 & {\red 1} & 0 & {\red 1}\\
1 & 1 & {\red 0} & 0 & {\red 0}\\
0 & 2 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 0
\end{pmatrix}$}%
, then
\only<4>{
\[
{\lightgreen \set{2, 5} \in \GEG(A), \qquad \text{ since }
\det\left(  \operatorname{sub}_{\set{1, 2}  }^{\set{2, 5}}A\right)  \neq0 .}
\]
}
\only<5>{
\[
{\lightgreen \set{1, 2, 3, 5} \in \GEG(A), \qquad \text{ since }
\det\left(  \operatorname{sub}_{\set{1, 2, 3, 4}  }^{\set{1, 2, 3, 5}}A\right)  \neq0 .}
\]
}
\only<6>{
\[
{\red \set{3, 5} \notin \GEG(A), \qquad \text{ since }
\det\left(  \operatorname{sub}_{\set{1, 2}  }^{\set{3, 5}}A\right)  = 0 .}
\]
}
\only<7>{
\begin{align*}
\GEG(A) &=  \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}
\vspace{15pc}
\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$. [\textbf{Exercise 7:} Prove this!]

We shall call this an \emph{order ideal greedoid}. \pause


\item \textbf{Example:} If $P$ is the poset with Hasse diagram
\[
\xymatrix{
& 4 \are[dl] \are[dr] \\
2 \are[dr] & & 3 \are[dl] \\
& 1
}
\]
then
\[
G = \set{ \colstrut \varnothing, \set{1}, \set{1,2}, \set{1,3}, \set{1,2,3}, \set{1,2,3,4} } .
\]
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Greedoids, examples: 4 (complements of subtrees)}

\begin{itemize}
\item Let $T$ be a tree with vertex set $V$.
Let $G$ be the set of all subsets $U \subseteq V$
such that the induced subgraph on $V \setminus U$ is
connected (i.e., no vertex in $U$ lies on the path
between two vertices in $V \setminus U$).

\item Then, $G$ is a greedoid on $V$. [\textbf{Exercise 8:} Prove this!] \pause


\item \textbf{Example:} If $T$ is the tree
\[
\xymatrix@R=0.9pc{
1 \are[dr] \\
& 3 \are[r] & 4 \are[r] & 5 \\
2 \are[ur]
}
\]
then
\begin{align*}
G &=
\left\{ \colstrut \varnothing, \set{1}, \set{2}, \set{5}, \set{1, 2},
           \set{1, 5}, \set{2, 5}, \set{4, 5},
   \right. \\
&  \left. \quad\qquad
           \set{1, 2, 3}, \set{1, 2, 5},
           \set{2, 4, 5}, \set{1, 2, 3, 4},
   \right. \\
&  \left. \quad\qquad
           \set{1, 2, 3, 5},
           \set{1, 2, 4, 5}, \set{1, 3, 4, 5},
           \set{2, 3, 4, 5} \colstrut
   \right\} .
\end{align*}
\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
{\footnotesize [\textbf{Exercise 9:} Show that the order ideal greedoid
of a finite poset $P$ is a strong greedoid if and only if $P$
is a disjoint union of subsets $P_0, P_1, P_2, \ldots$ such that
any two elements $p \in P_i$ and $q \in P_j$ satisfy $p < q$
if and only if $i < j$.]}
\pause

\item \textbf{Not} all greedoids from trees (Example 4 above) are strong
greedoids.
{\footnotesize [\textbf{Exercise 10:} Show that the greedoid of a tree $T$
is a strong greedoid if and only if $T$ is a star.]}
\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).
\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 all ultra triples were isomorphic to some
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 the
``polynomial ring'' $\mathbb{K}\left[t\right]$, except that all
powers $t^a$ with $a \in \mathbb{R}_+$ are allowed (not just for
integer $a$). \\
\only<1>{For example,
\[
3 + 2t^{0.5} - 7t^{0.8} + 4t^{3.2} \qquad \text{lies in this ring.}
\]
}
\pause
Replace $v_p$ by $v_t$ (which sends any polynomial to the lowest
exponent of $t$ that appears in it). \\
\only<2>{For example,
\[
v_t\tup{3t^{0.2} + 2t^{0.5} - 7t^{0.8} + 4t^{3.2}} = 0.2 .
\]
}
\pause


Construct the natural analogue of % the Bhargava-type
$\left(  E,w,d_{p}\right)  $ in this setting. \pause


Shows that its Bhargava greedoid is a Gaussian elimination
greedoid.
(This is analogous to the 1st step.)\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
``polynomial ring''.\pause


(The proof proceeds by strong induction, decomposing the ultra triple into
smaller ones. Iterating this decomposition again reveals the connection to
phylogenetic trees.) \pause

\item \textbf{Note:} In proving the general case, we had to come back
to our original example, the (generalized) Vandermonde determinant!
\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{\ \ \ \ \ 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{Melvyn Nathanson} for the invitation.

\item \textbf{you} for your patience and typo hunting.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Hints to Exercise 1}

{\footnotesize

\textbf{Exercise 1:} Prove the following \textbf{Theorem:} If $a_{0}%
,a_{1},\ldots,a_{n}$ are numbers, and $P_{0},P_{1},\ldots,P_{n}$ are
polynomials with $\deg P_{j}\leq j$ for each $j$, then
\[
\det\left(  \left(  P_{j}\left(  a_{i}\right)  \right)  _{i,j\in\left\{
0,1,\ldots,n\right\}  }\right)  =\ell_{0}\ell_{1}\cdots\ell_{n}\prod
_{i>j}\left(  a_{i}-a_{j}\right)  ,
\]
where $\ell_{j}$ is the $x^{j}$-coefficient of $P_{j}$.

\textbf{Hints to solution:}

\only<1>{One approach is by root identification: WLOG
assume that $\ell_{0}=\ell_{1}=\cdots=\ell_{n}=1$ (that is, the polynomials
$P_{j}$ are monic), and consider both the $a_{i}$'s and the remaining
coefficients of all $P_{j}$'s as indeterminates. Argue that $\det\left(
\left(  P_{j}\left(  a_{i}\right)  \right)  _{i,j\in\left\{  0,1,\ldots
,n\right\}  }\right)  $ is a polynomial of total degree $\leq n\left(
n-1\right)  /2$ that vanishes whenever two of the $a_{i}$'s are equal. A
standard divisibility argument then finishes the job.}

\only<2>{
Another approach is explicit: Write each $P_{j}$ as $P_{j}\left(  X\right)
=\sum_{k=0}^{j}\ell_{j,k}X^{k}$ (so that $\ell_{j,j}=\ell_{j}$), and observe
that%
\[
\left(  P_{j}\left(  a_{i}\right)  \right)  _{i,j\in\left\{  0,1,\ldots
,n\right\}  }=\underbrace{\left(
\begin{array}
[c]{cccc}%
a_{0}^{0} & a_{0}^{1} & \cdots & a_{0}^{n}\\
a_{1}^{0} & a_{1}^{1} & \cdots & a_{1}^{n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n}^{0} & a_{n}^{1} & \cdots & a_{n}^{n}%
\end{array}
\right)  }_{\substack{\text{Vandermonde matrix}\\\text{with known
determinant}}}\cdot\underbrace{\left(
\begin{array}
[c]{cccc}%
\ell_{0,0} & \ell_{1,0} & \cdots & \ell_{n,0}\\
0 & \ell_{1,1} & \cdots & \ell_{n,1}\\
\vdots & \vdots & \ddots & \vdots\\
0 & 0 & \cdots & \ell_{n,n}%
\end{array}
\right)  }_{\substack{\text{triangular matrix}\\\text{with determinant}%
\\\ell_{0,0}\ell_{1,1}\cdots\ell_{n,n}=\ell_{0}\ell_{1}\cdots\ell_{n}}}.
\]

See Theorem 2 in
{\red \url{https://www.cip.ifi.lmu.de/~grinberg/hyperfactorialBRIEF.pdf}}
for a more self-contained variant of this proof.}
}
\vspace{9pc}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Hints to Exercise 2}

{\footnotesize

\textbf{Exercise 2:} Prove that $\dfrac{0!\cdot2!\cdot\cdots\cdot\left(
2n\right)  !}{2^{n}}=\prod\limits_{n\geq i>j\geq0}\left(  i^{2}-j^{2}\right)
$ for any $n\geq0$.

\textbf{Hints to solution:}
\begin{align*}
\prod\limits_{n\geq i>j\geq0}\left(  i^{2}-j^{2}\right)   &  =\prod_{i=1}%
^{n}\ \ \prod_{j=0}^{i-1}\underbrace{\left(  i^{2}-j^{2}\right)  }_{=\left(
i-j\right)  \left(  i+j\right)  }=\prod_{i=1}^{n}\ \ \underbrace{\prod
_{j=0}^{i-1}\left(  i-j\right)  \left(  i+j\right)  }_{\substack{=\left(
2i\right)  !/2\\\text{(check this!)}}}\\
&  =\prod_{i=1}^{n}\left(  \left(  2i\right)  !/2\right)  =\dfrac
{2!\cdot4!\cdot\cdots\cdot\left(  2n\right)  !}{2^{n}}=\dfrac{0!\cdot
2!\cdot\cdots\cdot\left(  2n\right)  !}{2^{n}}.
\end{align*}

}
\vspace{9pc}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Hints to Exercise 3}

{\footnotesize

\textbf{Exercise 3:} Prove Bhargava's theorem: 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)  .
\]


\textbf{Hints to solution:} We can imitate each of the three proofs of
$\prod_{i>j}\left(  i-j\right)  \mid\prod_{i>j}\left(  a_{i}-a_{j}\right)  $.

\vspace{0.5pc}

\only<1>{\textbf{Analogue of proof 1:} For each $a\in\mathbb{R}$ and $k\in\mathbb{N}$,
define%
\[
\dbinom{a}{k}^{\prime}:=\dfrac{\left(  a\left(  a+1\right)  \left(
a+2\right)  \cdots\left(  a+k-1\right)  \right)  \cdot\left(  a\left(
a-1\right)  \left(  a-2\right)  \cdots\left(  a-k+1\right)  \right)  }%
{k\cdot\left(  2k-1\right)  !}%
\]
(read the fraction as $1$ if $k=0$). This is an even polynomial in $a$ of
degree $2k$ with leading coefficient $\dfrac{2}{\left(  2k\right)  !}$ (or $1$
if $k=0$). Thus, it is a polynomial in $a^{2}$ of degree $k$ with leading
coefficient $\dfrac{2}{\left(  2k\right)  !}$ (or $1$ if $k=0$). Hence,
Exercise 1 yields%
\[
\det\left(  \left(  \dbinom{a_{i}}{j}^{\prime}\right)  _{i,j\in\left\{
0,1,\ldots,n\right\}  }\right)  =\prod_{k=1}^{n}\dfrac{2}{\left(  2k\right)
!}\cdot\prod_{i>j}\left(  a_{i}^{2}-a_{j}^{2}\right)  .
\]
}

\only<2>{
\vspace{0.5pc}

However, for any $a\in\mathbb{Z}$, we have%
\[
\dbinom{a}{k}^{\prime}=\dbinom{a+k}{2k}+\dbinom{a+k-1}{2k}\in\mathbb{Z}%
\]
(check this!). Thus, the determinant on the LHS is an integer, so the RHS is
an integer too. In other words, $\prod_{k=1}^{n}\dfrac{\left(  2k\right)
!}{2}\mid\prod_{i>j}\left(  a_{i}^{2}-a_{j}^{2}\right)  $. Now use Exercise 2.}

\only<3>{
\vspace{0.5pc}

\textbf{Analogue of proof 2:} The number $\dfrac{\operatorname*{RHS}%
}{\operatorname*{LHS}}$ counts a variant of semistandard tableaux called
\emph{King tableaux}. See Exercise 24.42 in
\href{https://mat.uab.cat/~pitsch/ReadingSeminar/Fulton-Harris.pdf}{Fulton/Harris,
\textit{Representation Theory: A First Course}, 2004} for a proof that
$\dfrac{\operatorname*{RHS}}{\operatorname*{LHS}}$ is the dimension of an
irreducible representation of $\mathfrak{so}_{2\left(  n+1\right)  }\left(
\mathbb{C}\right)  $, and see
\href{https://doi.org/10.1006/jabr.1994.1064}{Robert A. Proctor, \textit{Young
Tableaux, Gelfand Patterns, and Branching Rules for Classical Groups}, 1994}
for the notion of tableaux that is counted by this dimension. (Thanks to
Travis Scrimshaw for the latter reference.)

\vspace{0.5pc}

\textbf{Analogue of proof 3:} This becomes a lot easier using the results of
Chapter 2 (see Exercise 5 below).}

}
\vspace{9pc}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Hints to Exercise 4}

{\footnotesize

\textbf{Exercise 4:} Let $T$ be a tree. Let $x,y,z,w$ be four vertices of $T$.
Prove that the two largest of the three numbers
\[
\lambda\left(  x,y\right)  +\lambda\left(  z,w\right)  ,\qquad\lambda\left(
x,z\right)  +\lambda\left(  y,w\right)  ,\qquad\lambda\left(  x,w\right)
+\lambda\left(  y,z\right)
\]
are equal.

\textbf{Hints to solution:} This is a well-known fact known as the
\textbf{four-point condition}, although few authors bother to prove it. Three
proofs can be found in \href{https://www.cip.ifi.lmu.de/~grinberg/t/17s/}{my
Spring 2017 graph theory course}, where it was exercise 6 on midterm \#2.
\href{https://www.cip.ifi.lmu.de/~grinberg/t/17s/mt2s-pevzner.pdf}{Sasha
Pevzner's solution} is probably the nicest. The idea is to induct on the size
of $T$; in the induction step, remove a leaf from $T$ and distinguish cases
based on how many of $x,y,z,w$ are equal to this leaf.

}
\vspace{9pc}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Hints to Exercise 5}

{\footnotesize

\textbf{Exercise 5:} 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)  .
\]
using greedy $m$-permutations.

\textbf{Hints to solution:} Let $p$ be a prime. Let $E$ be a finite subset of
$\mathbb{Z}$ that contains $0,1,\ldots,n$ as well as $a_{0},a_{1},\ldots
,a_{n}$. Equip this set $E$ with the $p$-adic distance $d=d_{p}$ and the zero
weight function $w$ (so that $w\left(  e\right)  =0$ for all $e\in E$). Thus,
$\left(  E,w,d\right)  $ is an ultra triple.

Check that the tuple $\left(  0,1,\ldots,n\right)  $ is a greedy $\left(
n+1\right)  $-permutation of $E$ (this uses the fact that binomial
coefficients are $\in\mathbb{Z}$). Hence, by the first Petrov-G. result, the
set $\left\{  0,1,\ldots,n\right\}  $ has maximum perimeter among all $\left(
n+1\right)  $-element subsets of $E$. Thus, $\operatorname*{PER}\left\{
0,1,\ldots,n\right\}  \geq\operatorname*{PER}\left\{  a_{0},a_{1},\ldots
,a_{n}\right\}  $. In other words, $v_{p}\left(  \prod_{i>j}\left(
i-j\right)  \right)  \leq v_{p}\left(  \prod_{i>j}\left(  a_{i}-a_{j}\right)
\right)  $. Since this holds for all primes $p$, we thus conclude that
$\prod_{i>j}\left(  i-j\right)  \mid\prod_{i>j}\left(  a_{i}-a_{j}\right)  $.

A similar argument shows that $\prod_{i>j}\left(  i^{2}-j^{2}\right)
\mid\prod_{i>j}\left(  a_{i}^{2}-a_{j}^{2}\right)  $. Here, we need to show
that the tuple $\left(  0^{2},1^{2},\ldots,n^{2}\right)  $ is a greedy
$\left(  n+1\right)  $-permutation of $E$. (Again, use binomial coefficients.)

}
\vspace{9pc}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Hints to Exercise 6}

{\footnotesize

\textbf{Exercise 6:} Prove that the Gaussian elimination greedoid of a matrix
is a greedoid.

\textbf{Hints to solution:} Even better, we'll show that it is a strong
greedoid (defined near the end of the talk). So we need to verify Axioms 1, 2
and 4 (since Axiom 3 follows from 4).

Axiom 1 is obvious. Axiom 2 follows from Laplace expansion.
For Axiom 4, we need the
following determinantal identity:

\textbf{Pl\"{u}cker identity (one of many):} Let $n$ be a positive integer.
Let $X$ be an $n\times\left(  n-1\right)  $-matrix, and $Y$ an $n\times
n$-matrix. Let $i\in\left\{  1,2,\ldots,n\right\}  $. Then,%
\[
\det\left(  X_{\sim i,\bullet}\right)  \det Y=\sum_{q=1}^{n}\left(  -1\right)
^{n+q}\det\left(  X\mid Y_{\bullet,q}\right)  \det\left(  Y_{\sim i,\sim
q}\right)  .
\]
Here,

\begin{itemize}
\item $X_{\sim i,\bullet}$ means the matrix $X$ without its $i$-th row;

\item $\left(  X\mid Y_{\bullet,q}\right)  $ means the matrix $X$ with the
$q$-th column of $Y$ appended to it on the right;

\item $Y_{\sim i,\sim q}$ means the matrix $Y$ without its $i$-th row and its
$q$-th column.
\end{itemize}

See the Appendix in
\textit{\href{https://arxiv.org/abs/2001.05535}{\textit{The Bhargava greedoid
as a Gaussian elimination greedoid}}} for details.

The easiest way to prove the Pl\"{u}cker identity is to expand $\det\left(
X\mid Y_{\bullet,q}\right)  $ along the last column and use $Y\cdot
\operatorname*{adj}Y=\det Y\cdot I_{n}$.

}
\vspace{9pc}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Hints to Exercise 7}

{\footnotesize

\textbf{Exercise 7:} 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)  $).

Prove that $J$ is a greedoid on $P$.

\textbf{Hints to solution:} Axioms 1 and 2 are easy. For Axiom 3, let $A$ and
$B$ be two order ideals of $P$ satisfying $\left\vert B\right\vert =\left\vert
A\right\vert +1$. We must prove that there exists $b\in B\setminus A$ such
that $A\cup\left\{  b\right\}  $ is again an order ideal of $P$.

This is easy: Just let $b$ be a minimal element of $B\setminus A$.

}
\vspace{9pc}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Hints to Exercise 8}

{\footnotesize

\textbf{Exercise 8:} Let $T$ be a tree with vertex set $V$. Let $G$ be the set
of all subsets $U \subseteq V$ such that the induced subgraph on $V \setminus
U$ is connected (i.e., no vertex in $U$ lies on the path between two vertices
in $V \setminus U$).

Prove that $G$ is a greedoid on $V$.

\textbf{Hints to solution:} It is best to restate Axioms 1, 2, 3 in terms of
the complements $\overline{A}$ of the sets $A$. Thus, we must prove:

\begin{enumerate}
\item The induced subgraph on $V\setminus\varnothing$ is connected.

\item If a proper subset $\overline{B}\subseteq V$ is such that the induced
subgraph on $\overline{B}$ is connected, then there exists $b\notin%
\overline{B}$ such that the induced subgraph on $\overline{B}\cup\left\{
b\right\}  $ is again connected.

\item If $\overline{A},\overline{B}\subseteq V$ are such that the induced
subgraphs on $\overline{A}$ and on $\overline{B}$ are both connected, and if
$\left\vert \overline{B}\right\vert =\left\vert \overline{A}\right\vert -1$,
then there exists $b\in\overline{A}\setminus\overline{B}$ such that the
induced subgraph on $\overline{A}\setminus\left\{  b\right\}  $ is connected.
\end{enumerate}

Item 1 is obvious. For item 2, just add a neighbor of a $\overline{B}$-vertex
that is not in $\overline{B}$. For item 3, observe that the induced subgraph
on $\overline{A}$ is itself a tree. Call this tree $T^{\prime}$. Each vertex
of a tree lies on a path connecting two leaves (why?). Thus, if all leaves of
$T^{\prime}$ were contained in $\overline{B}$, then $\overline{A}$ would be
contained in $\overline{B}$, contradicting $\left\vert \overline{B}\right\vert
=\left\vert \overline{A}\right\vert -1$. Hence, there exists a leaf of
$T^{\prime}$ that doesn't lie in $\overline{B}$. Let $b$ be such a leaf.

}
\vspace{9pc}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Hints to Exercise 9}

{\footnotesize

\textbf{Exercise 9:} Show that the order ideal greedoid of a finite poset $P$
is a strong greedoid if and only if $P$ is a disjoint union of subsets
$P_{0},P_{1},P_{2},\ldots$ such that any two elements $p\in P_{i}$ and $q\in
P_{j}$ satisfy $p<q$ if and only if $i<j$.

\textbf{Hints to solution:}
\only<1>{$\Longrightarrow:$ Assume that the greedoid is a
strong greedoid.

For each $i\geq0$, let $P_{i}$ be the set of all $p\in P$ with the following
property: The largest chain of $P$ with largest element $p$ has exactly $i+1$
elements. (Thus, $P_{0}$ consists of the minimal elements of $P$.)

We must show that any two elements $p\in P_{i}$ and $q\in P_{j}$ satisfy $p<q$
if and only if $i<j$. The \textquotedblleft only if\textquotedblright\ part is
clear, so we need to prove the \textquotedblleft if\textquotedblright\ part.
We prove it by strong induction on $j$. So fix a $j$ and two elements  $p\in
P_{i}$ and $q\in P_{j}$ such that $i<j$. We must show that $p<q$, assuming
that the same has been showed \textquotedblleft for all smaller $j$%
's\textquotedblright.

Let $r$ be the second-highest element of a maximum-length chain ending in $q$;
thus, $r\in P_{j-1}$. If $i<j-1$, then the induction hypothesis yields $p<r$,
hence $p<r<q$, and
we are done. Hence, WLOG we don't have $i<j-1$. Thus, $i=j-1$ and $r\in
P_{j-1}=P_{i}$.

Let $J:=P_{0}\cup P_{1}\cup\cdots\cup P_{i}$. This is an order ideal of $P$.
So is $J\setminus\left\{  r\right\}  $ (why?). So is $\left(  J\setminus
\left\{  p\right\}  \right)  \cup\left\{  q\right\}  $ unless $p<q$ (why?).
Thus, unless $p<q$, then Axiom 4 of a strong greedoid (applied to
$A=J\setminus\left\{  r\right\}  $ and $B=\left(  J\setminus\left\{
p\right\}  \right)  \cup\left\{  q\right\}  $) yields that there is some
$b\in\left\{  q,r\right\}  $ such that $\left(  J\setminus\left\{  r\right\}
\right)  \cup\left\{  b\right\}  $ and $\left(  \left(  J\setminus\left\{
p\right\}  \right)  \cup\left\{  q\right\}  \right)  \setminus\left\{
b\right\}  $ are order ideals. But this is easily seen to be false. Hence, we
must have $p<q$, and the induction is complete.}

\only<2>{$\Longleftarrow:$ Straightforward (characterize the order ideals of this
disjoint union).}

}
\vspace{9pc}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ \ Hints to Exercise 10}

{\footnotesize

\textbf{Exercise 10:} Show that the greedoid of a tree $T$ is a strong
greedoid if and only if $T$ is a star.

\textbf{Hints to solution:} $\Longrightarrow:$ Assume that the greedoid is a
strong greedoid. If $T$ has a path $u-v-w-t$ of length $3$, then the two sets
$A=V\setminus\left\{  u,v\right\}  $ and $B=V\setminus\left\{  t\right\}  $
contradict Axiom 4 of strong greedoids. Thus, $T$ has no path of length $3$.
This easily yields that $T$ is a star (just pick any path $u-v-w$ of length
$2$ and argue that each vertex $\neq v$ must be a neighbor of $v$).

$\Longleftarrow:$ Straightforward.

}
\vspace{9pc}

\end{frame}

\end{document}