\documentclass[finalversion]{FPSAC2025}
\articlenumber{131}


\usepackage{cleveref}

\newtheorem*{Theorem}{Theorem}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem*{open problem}{Open Problem}

%MathShortcuts
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}

\newcommand{\set}[2]{\left\{ #1 \;|\; #2 \right\}}
\newcommand{\bigset}[2]{\left\{ #1 \;\big|\; #2 \right\}}

\def\cB{\mathcal{B}}
\def\cE{\mathcal{E}}
\def\cF{\mathcal{F}}
\def\cL{\mathcal{L}}
\def\cS{\mathcal{S}}

%Permutations
\newcommand{\Sym}{{\mathfrak{S}}}
\newcommand{\Perm}{\operatorname{Sym}}
\newcommand{\des}{\operatorname{des}}
\newcommand{\Des}{\operatorname{Des}}
\newcommand{\id}{\operatorname{id}}

%Polynomials and statistics
\newcommand{\Chow}{\operatorname{\underline{H}}}
\newcommand{\Chowaug}{\operatorname{H}}
\newcommand{\Eulerian}{\operatorname{E}}

%Matroids and Lattice of flats
\newcommand{\rk}{\operatorname{rk}}

%TextShortcuts
\newcommand{\Dfn}[1]{\emph{\bfseries #1}}

%Paper
\title[The Chow and augmented Chow polynomials of Uniform Matroids]{The Chow and augmented Chow polynomials \\ of Uniform Matroids}

\author[E.~Hoster]{\texorpdfstring{Elena Hoster\thanks{\href{mailto:elena.hoster@rub.de}{elena.hoster@rub.de}}\addressmark{1}}{Elena Hoster}}
\address{\addressmark{1}Fakultät für Mathematik, Ruhr-Universität Bochum, Germany}

\received{13.11.2024}

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

\abstract{
    We provide explicit combinatorial formulas for the Chow polynomial and for the augmented Chow polynomial of uniform matroids, thereby proving a conjecture by Ferroni.
    These formulas refine existing formulas by Hampe and by Eur, Huh, and Larson, 
    offering a combinatorial interpretation of the coefficients based on Schubert matroids.
    As a byproduct, we count Schubert matroids by rank, number of loops, and cogirth.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Chow polynomials, augmented Chow polynomials, uniform matroids, Schubert matroids}

\usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{bibliography.bib}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\maketitle

\section{Introduction and main results}
\label{sec: intro}

The Chow polynomial $\Chow_M(x)$ and the augmented Chow polynomial~$\Chowaug_M(x)$ of a matroid~$M$ are the Hilbert--Poincaré series of the Chow ring and of the augmented Chow ring, respectively. 
These polynomials are known to be unimodal, palindromic, and $\gamma$-positive,
as proven in~\cite{Ferroni2024}.
Both polynomials are also conjectured to be real-rooted, which is only known for the augmented Chow polynomials of \emph{uniform matroids} \cite{Ferroni2024}.
A second proof of the $\gamma$-positivity, along with a combinatorial formula for the~$\gamma$-expansion of both~$\Chow_M(x)$ and~$\Chowaug_M(x)$, 
is provided in \cite{stump2024chowaugmentedchowpolynomials}.

\medskip
Let $U_{k,n}$ be the uniform matroid on ground set $[n] = \{1,\dots , n\}$ and of rank $k$, 
with bases being all $k$-element subsets.
As shown in \cite[Theorem 1.11]{Ferroni2024}, the coefficients of the Chow polynomial and of the augmented Chow polynomial of an arbitrary loopless matroid~$M$ are term-wise maximized when $M$ is a uniform matroid.

\medskip
This paper proves a conjecture by Ferroni regarding the coefficients in the case of uniform matroids and provides a monomial expansion for their Chow and augmented Chow polynomials. 
\begin{theorem}[{\Cite[Conjecture]{Priv_Comm_Ferroni}}]
    \label{thm: Ferroni}
    The Chow polynomial and the augmented Chow polynomial of the uniform matroid $U_{k,n}$ are given by
    \begin{align*}
    \Chow_{U_{k,n}} (x)
    &=
    \sum_{m = 0}^{k-1}
    \# \big\{ \substack{\text{loopless Schubert matroids on the ground set } [n] \\ \text{of rank $m+1$ and cogirth greater than } n-k } \ \big\}
    \cdot x^{m} \, \\
     \Chowaug_{U_{k,n}} (x)
    &=
    \sum_{m = 0}^{k}
    \# \big\{ \substack{\text{\phantom{loop} Schubert matroids\phantom{less} on the ground set } [n] \\ \text{of rank \phantom{+}$m$\phantom{1} and cogirth greater than } n-k } \ \big\} 
    \cdot x^{m} \,.
    \end{align*}
\end{theorem}

\Citeauthor{Hampe_2017} showed in \Cite{Hampe_2017} that the Chow polynomial of the Boolean matroid~$U_{n,n}$ is the~$h$-vector of the permutahedron, the \emph{$n$-th Eulerian polynomial} $A_n(t)$.
Moreover, he showed that the~\emph{$k$-th Eulerian number} counts loopless Schubert matroids on $n$ elements of rank $k$.
Likewise, \Citeauthor{eur2023stellahedralgeometrymatroids} proved in \Cite{eur2023stellahedralgeometrymatroids} that the augmented Chow polynomial of~$U_{n,n}$ is the~$h$-vector of the stellahedron, the~\emph{$n$-th binomial Eulerian polynomial~$\widetilde{A}_n(x)$}.
Here, the coefficients count Schubert matroids of corresponding rank but are not necessarily loopless. 
\Cref{thm: Ferroni} refines both of these representations.

In \Cite{Hameister_2021}, \Citeauthor{Hameister_2021} give a combinatorial formula for the Chow polynomial of the~{$q$-uniform} matroid~$U_{k,n}(q)$ on ground set $[n]$, the $q$-analog of the uniform matroid which becomes~$U_{k,n}$ for~$q = 1$.
This formula is particularly useful in the cases~$k=n$ and~$k = n-1$.
It provides~${x\cdot \Chow_{U_{n-1,n}}(x) = d_n(x)}$, where~$d_n(x)$ denotes the~$n$-th \emph{derangement polynomial}.
More recently, \Citeauthor{liao2024chowringsaugmentedchow} extended this result to the augmented Chow polynomial in \Cite[Theorem 4.7]{liao2024chowringsaugmentedchow}, giving~$\Chowaug_{U_{n-1,n}}(x) = A_n(x)$.

\medskip
We prove \Cref{thm: Ferroni} using combinatorial arguments.
In particular, we provide a combinatorial formula on the number of Schubert matroids on a fixed ground set, according to their \emph{rank}, \emph{cogirth}, and number of \emph{loops}.

\subsection{Main results}
For any nonempty subset $I \subseteq \{1,\dots,  n\}$, consider the disjoint partition of~$I = I_1 \cup \dots \cup I_s$ into maximal consecutive subsets such that $\min(I_j) < \min(I_{j+1})$.
Define the multinomial coefficient
\[
\binom{n}{\Delta I} = \binom{n}{\min(I_1) - 1, \min(I_2)-\min(I_1), \min(I_3)-\min(I_2), \dots , \min(I_s)-\min(I_{s-1})} ,
\]
which takes the differences of these minima of adjacent subsets.
For $I=\{\}$ being the empty set, we set $\binom{n}{\Delta I} = 1$.

\begin{example}
    The set $I = \{2,3,5,7,8\}$ is partitioned into $\{2,3\}\cup\{5\}\cup\{7,8\}$, the multinomial coefficient is
    \[
    \binom{n}{\Delta I} = \binom{n}{2-1, 5-2, 7-5} = \binom{n}{1,3,2} = \frac{n!}{1!\ 3!\ 2!\ (n-6)!} \,
    \]
    for $n \geq 8$.
\end{example}

A \Dfn{descent} in a sequence of integers $a=(a_1,\dots , a_m)$ is a position $i$ such that $a_i > a_{i+1}$. The \Dfn{descent set} of $a$ is the set of descents,~$\Des(a)=\set{i\in \{1,\dots, m-1\}}{ a_i > a_{i+1} }$. Its size gives the number of descents, denoted by~$\des(a)$.
This notation also applies to permutations when written in one-line notation.
Let~$\Eulerian(m,D)$ denote the number of permutations in~$\Sym_m$ that have descent set~$D$.\\
Define $\mathsf{nc}(m)$ to be the set of all subsets of $\{1,\dots , m\}$ that contain \textbf{n}o \textbf{c}onsecutive integers.

\begin{theorem}
    \label{thm: Chow four ways}
    The Chow polynomial of the uniform matroid $U_{k,n}$ is given by any of the following expansions:
    \begin{align}
        \Chow_{U_{k,n}} (x) 
        &= \quad
        \sum_{ \substack{I \subseteq \{1,\dots,k\} \\ 1 \in I } } \ \binom{n}{\Delta I} \ x^{\vert I \vert - 1} \label{eq: Chow monomial} \\
        &=
        \quad
        \sum_{ \substack{ D \in \mathsf{nc}(k-1) \\ 1\notin D } } \quad \Eulerian(n,D) \ \ \cdot x^{\vert D \vert } \cdot (1 + x)^{k - 1 -2\cdot \vert D \vert } \label{eq: Chow Eulerian gamma}    \\
        &= 
        \sum_{ \substack{ \sigma \in \Sym_k \\ \Des(\sigma) \in \mathsf{nc}(k-1) \\ \sigma(1) < \sigma(2) } } 
        \binom{n - \sigma(k)}{k - \sigma(k)} \cdot x^{\des(\sigma)} 
        \cdot (1 + x)^{k - 1 -2\cdot \des(\sigma)} \label{eq: Chow binom gamma} \,.
    \end{align}
\end{theorem}

We deduce \Cref{eq: Chow Eulerian gamma,eq: Chow binom gamma} from the $\gamma$-expansion given in \Cite[Theorem 1.1]{stump2024chowaugmentedchowpolynomials}.
We then prove \eqref{eq: Chow monomial} by comparing the coefficients with \eqref{eq: Chow Eulerian gamma}.

\medskip
In the same way, we get a similar version of \Cref{thm: Chow four ways} for the augmented case. 

\begin{theorem}
    \label{thm: Chow aug four ways}
    The augmented Chow polynomial of the uniform matroid $U_{k,n}$ is given by any of the following expansions:
    \begin{align}
        \Chowaug_{U_{k,n}} (x)
        &= \quad \sum_{ \substack{I \subseteq \{1,\dots,k\} } } \ \binom{n}{\Delta I} \ x^{\vert I \vert } \label{eq: Chow aug monomial} \\
        &=
        \quad 
        \sum_{ \substack{ D \in \mathsf{nc}(k-1) } } \quad \Eulerian(n,D) \quad \cdot x^{\vert D \vert } \cdot (1 + x)^{k -2\cdot \vert D \vert } \label{eq: Chow aug Eulerian gamma} \\
        &=
        \sum_{ \substack{ \sigma \in \Sym_k \\ \Des(\sigma) \in \mathsf{nc}(k-1) } }
        \binom{n - \sigma(k)}{k - \sigma(k)} \cdot x^{\des(\sigma)} 
        \cdot (1 + x)^{k -2\cdot \des(\sigma)} \nonumber \,.
    \end{align}
\end{theorem}

The $\gamma$-expansions given in \eqref{eq: Chow Eulerian gamma} and \eqref{eq: Chow aug Eulerian gamma} are also covered in \Cite{liao2024equivariantgammapositivitychowrings}.

\begin{remark}[Multivariate analogues]
    \label{rem: multi version}
    In \Cref{sec: proofs}, we define the multivariate Chow polynomial and the multivariate augmented Chow polynomial as multivariate versions of $\Chow_{M}(x)$ and of~$\Chowaug_{M}(x)$.
    We prove \Cref{thm: Chow four ways,thm: Chow aug four ways}
    by proving their multivariate analogs.
\end{remark}

We show in \Cref{sec: proofs}, how to translate \Cref{thm: Ferroni} into \eqref{eq: Chow monomial} and \eqref{eq: Chow aug monomial}.
Thereby, 
\begin{itemize}
    \item $I \subseteq [n]$ indexes a set of Schubert matroids,
    \item $1\in I$ ensures that these are loopless, and 
    \item $\max (I) \leq k$ ensures that their cogirth is greater than $n-k$.
\end{itemize}

\begin{example}
    We compute the Chow polynomial of $U_{3,5}$ using all given ways in \Cref{thm: Chow four ways}. 
    Using \eqref{eq: Chow monomial}, we get 
    \begin{align*}
        \Chow_{U_{3,5}}(x) 
        =&
        \binom{5}{0} \cdot x^{\vert \{1\} \vert -1} 
        + \binom{5}{0} \cdot x^{\vert \{1,2\} \vert -1}
        + \binom{5}{0,2} \cdot x^{\vert \{1,3\} \vert -1}
        + \binom{5}{0} \cdot x^{\vert \{1,2,3\} \vert -1} \\
        =&
        1 + x + 10x + x^2 \,, \\
        \intertext{using \eqref{eq: Chow Eulerian gamma}, we get }
        \Chow_{U_{3,5}}(x) 
        =&
        \Eulerian(5,\{ \}) \cdot x^{ 0 } \cdot (1+x)^{ 2-2\cdot 0 }
        + \Eulerian(5,\{ 2 \}) \cdot x^{ 1 } \cdot (1+x)^{ 2-2\cdot 1 } \\
        =&
        (1+x)^2 +  9x \,, \\
        \intertext{and \eqref{eq: Chow binom gamma} finally gives}
        \Chow_{U_{3,5}}(x) 
        =&
        \underbrace{\binom{5 - 3}{3 - 3} \cdot x^{0} \cdot (1+x)^{2} }_{\sigma = 123}
        + \underbrace{\binom{5 - 2}{3 - 2} \cdot x^{1} \cdot (1+x)^{0}}_{\sigma = 132}
        + \underbrace{\binom{5 - 1}{3 - 1} \cdot x^{1} \cdot (1+x)^{0}}_{\sigma = 231} \\
        =&
        \binom{2}{0} \cdot (1+x)^2 
        + \binom{3}{1} \cdot x 
        + \binom{4}{2} \cdot x \\
        =&
        (1+x)^2 + 3x + 6x \,.
    \end{align*}
    All three polynomials coincide with~$\Chow_{U_{3,5}}(x) = 1 + 11x + x^2$.
\end{example}

The following corollary was proven in \Cite{Ferroni2024}. We reprove the results by ordering the sets~$I$ within the monomial expansions \eqref{eq: Chow monomial} and \eqref{eq: Chow aug monomial}, according to the minimum of their last maximal consecutive subset $I_s$, where $I=I_1 \cup \dots \cup I_s$ is the partition into maximal consecutive subsets.

\begin{corollary}[{\Cite[Theorem 1.9]{Ferroni2024}}] 
    \label{cor: chow via derangements}
    We have 
    \begin{align*}
        \Chow_{U_{k,n}}(x) 
          &= \phantom{1+ x\cdot } \sum_{j = 0}^{k-1} \binom{n}{j} \ d_j(x) \ (1 + x + \dots + x^{k-1-j}) \,, \\
        \Chowaug_{U_{k,n}} (x) 
          &= 1+ x \cdot \sum_{j = 0}^{k-1} \binom{n}{j} \ A_j(x) \ (1 + x + \dots + x^{k-1-j}) \,,
    \end{align*}
    where $d_j(x)$ is the $j$-th derangement polynomial, and $A_j(x)$ is the $j$-th Eulerian polynomial.
\end{corollary}

Note that \Cref{thm: Chow four ways,thm: Chow aug four ways} hold at the level of multivariate polynomials as already mentioned in \Cref{rem: multi version}.
An analogue of \Cref{cor: chow via derangements} does not seem to hold.

\medskip
Write
\[
\Chow_{U_{k,n}} (x) = \sum_{i = 0}^{k-1} \underline{c }_{\ k,n}^{(i)} \ x^i
\quad \text{and} \quad
\Chowaug_{U_{k,n}} (x) = \sum_{i = 0}^{k} c_{k,n}^{(i)} \ x^i \,.
\]
The formulas that we get from the monomial expansions \eqref{eq: Chow monomial} and \eqref{eq: Chow aug monomial} for the coefficients $\underline{c }_{\ k,n}^{(m)}$ and $c_{\ k,n}^{(m)}$ indicate, 
that the coefficients give the size of a set.
The sequences~$(c_{k,n}^{(1)})_{n\geq k}$ for fixed $k$ are sums of binomials.
In the non-augmented case, we get a connection to \Dfn{Grassmannian permutations}. A permutation $w\in \Sym_n$ is called Grassmannian if it has at most one descent.

\begin{corollary}
    For $k\geq 2$, the coefficient $\underline{c }_{\ k,n}^{(1)}$ is the number of Grassmannian permutations of length~$n$ avoiding a (fixed) permutation $\sigma \in \Sym_k$ with $\des(\sigma) = 1$.
\end{corollary}
\begin{proof}
    This follows by \Cite[Theorem 3.3]{GilTomasko}, which provides the same formula for the number of Grassmannian permutations of length~$n$ avoiding a (fixed) permutation~$\sigma \in \Sym_k$ with~$\des(\sigma) = 1$ as we get for $\underline{c }_{\ k,n}^{(1)}$.
\end{proof}

This leads to the following open problem:

\begin{open problem}
    Describe $\underline{c }_{\ k,n}^{(m)}$ and $c_{\ k,n}^{(m)}$ as sizes of sets of permutations of length $n$ according to certain restrictions.
\end{open problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Background}
\label{sec: background}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{\texorpdfstring{$R$}{R}-labeling}
Let $P = (P, \leq)$ be a finite graded poset of rank $n$ with minimal element $\widehat{0}$ and maximal element $\widehat{1}$.
The set of edges of $P$ is denoted by~$\cE(P)$.
For a labeling~$\lambda : \cE(P) \to \ZZ$~and for a maximal chain $\cF = \{ \widehat{0} = F_0 < F_1 < \dots < F_n = \widehat{1} \}$, 
let $\lambda_\cF = (\lambda_1,\dots , \lambda_n)$ with~$\lambda_i = \lambda( F_{i-1} < F_i )$ be its edge-labeling sequence . 
We call~$\lambda$ an \Dfn{$R$-labeling} 
if every interval of~$P$ admits a unique maximal chain $\cF$ with strictly increasing edge-labeling sequence~$\lambda_\cF = ( \lambda_1 < \lambda_2 < \dots < \lambda_n)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Matroids}
    Let $M$ be a matroid on the ground set $E$ and with bases $\cB$.    
    We recall some definitions and notations for matroids.
    The \Dfn{rank}~$\rk(M)$ of $M$ is the size of any basis of~$M$.
    The set of flats of $M$ ordered by inclusion forms a geometric lattice of rank $\rk(M)$, the \Dfn{lattice of flats} denoted by~$\cL(M)$.
    The \Dfn{dual matroid}~$M^\ast$ of $M$ is the matroid on the same ground set $E$ and with bases~$\set{ E\setminus B }{ B \in \cB}$.
    An element $x\in E$ is a \Dfn{loop} in $M$ if it is not contained in any basis.
    A \Dfn{coloop} in $M$ is a loop in the dual matroid $M^\ast$.
    A \Dfn{circuit} $C\subseteq E$ is a dependent set of~$M$, such that~$C \setminus \{x\}$ is independent for all~$x\in C$. 
    The \Dfn{girth} of $M$ is the cardinality of the smallest circuit,
    and the \Dfn{cogirth} of $M$ is the girth of $M^\ast$.
    
    \medskip
    Let $[n] = \{1,\dots , n\}$, and let $\binom{[n]}{k}$ be the set of all subsets of $[n]$ that have size~$k$. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
\subsubsection{Uniform matroids}
    For $n\geq k$, the \Dfn{uniform matroid} $U_{k,n}$ is the matroid on the ground set $[n]$ with set of bases~$\binom{[n]}{k}$.
    Its lattice of flats $\cL(U_{k,n})$ consists of all subsets of size smaller than~$k$ together with the maximal element $[n]$, ordered by inclusion.
    
\subsubsection{Schubert matroids}
    We use the definition of Schubert matroids given in \Cite{Ferroni_2023} for the fixed ground set $[n]$.
    For~$\pi \in \Sym_n$, let $\leq_{\pi}$ be the total order on $[n]$ given by the one-line notation of~$\pi$, that is
    \[ \pi(1) \leq_\pi \pi(2) \leq_\pi \dots \leq_\pi \pi(n) \,. \]
    If~$\pi = \id$ is the identity permutation, this gives the usual total order $1 < 2 < \dots < n$.
    For subsets~$I = \{i_1 < \dots < i_k\}, J=\{j_1 < \dots < j_k\} \subseteq [n]$ with~$\vert I \vert = \vert J \vert$, 
    we write
    \[
    I \leq_\pi J \quad \text{ if } i_m \leq_\pi j_m \text{ for each } m \in \{1,\dots , k\} \,.
    \]
    For a set $I \in \binom{[n]}{k}$, and for a permutation $\pi\in \Sym_n$, 
    the \Dfn{Schubert matroid} $\cS_{I,\pi}$ is the matroid on the ground set $[n]$ with bases
    \[
        \bigset{ J \in \binom{[n]}{k} }{ I \leq_\pi J } \,.
    \]
    Schubert matroids are a special class of \emph{lattice path matroids}, sometimes also called \emph{nested matroids}~\cite{Hampe_2017}, \emph{generalized Catalan matroids}~\cite{Bonin_2003} or \emph{shifted matroids}~\cite{ardila2002catalanmatroid}.
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Sketches of proofs of the main results}
\label{sec: proofs}

In this section, we introduce multivariate versions of the Chow polynomial and of the augmented Chow polynomial which become the usual polynomials when all variables are set equal.
We then derive \Cref{thm: Chow four ways} and \Cref{thm: Chow aug four ways} from their multivariate analogs.
In \Cref{sec: Schubert matroids}, we study Schubert matroids to translate \Cref{thm: Ferroni} into \eqref{eq: Chow monomial} and \eqref{eq: Chow aug monomial}.
The main tool for this translation is \Cref{thm: SM counting when restricted} in which we count Schubert matroids on a fixed ground set, according to rank, cogirth, and the number of loops.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Multivariate Chow and augmented Chow polynomials}

The lattice of flats $\cL(M)$ of a matroid $M$ always admits an $R$-labeling \Cite[Proposition 2.2]{MR0354473}.
Fix such an $R$-labeling $\lambda$, then, by \Cite[Theorem 1.1]{stump2024chowaugmentedchowpolynomials}, the Chow polynomial of $M$ is given by
\begin{equation}
    \label{eq: Chow gamma exp Stump}
    \Chow_{M} (x)
    = \sum_{ \cF } x^{ \des(\lambda_\cF ) } \cdot (1 + x)^{\rk(M) { - 1} -2\cdot \des(\lambda_\cF)} \,,
\end{equation}
where the sum ranges over all maximal chains $\cF$ whose edge-labeling sequence~$\lambda_\cF$
has no consecutive descents, $\Des(\lambda_\cF) \in \mathsf{nc}(k-1)$, and with $1\notin \Des(\lambda_\cF)$.

The augmented Chow polynomial of $M$ is given by
\begin{equation}
    \label{eq: augChow gamma exp Stump}
    \Chowaug_{M} (x)
    = \sum_{ \cF } x^{ \des(\lambda_\cF ) } \cdot (1 + x)^{\rk(M) -2\cdot \des(\lambda_\cF)} \,,
\end{equation}
where the sum ranges over all maximal chains $\cF$ whose edge-labeling sequence~$\lambda_\cF$
has no consecutive descents, $\Des(\lambda_\cF) \in \mathsf{nc}(k-1)$.

Define the \Dfn{multivariate Chow polynomial} of $M$ by
\begin{align*}
    \Chow_M (\boldsymbol{x})
    =&
    \sum_{ \substack{ \cF \\ 1 \notin \Des(\lambda_F)  } } \left(\prod_{i\in \Des(\lambda_\cF)} x_i \right) \cdot  
    \left(\prod_{ \substack{i \in \{1,\dots , k-1 \} \\ i,i+1 \notin \Des(\lambda_\cF) } } (1+x_i) \right) &&\in \NN [x_1,\dots , x_{\rk(M)-1}]
\intertext{and define the \Dfn{multivariate augmented Chow polynomial} of~$M$ by}
    \Chowaug_M (\boldsymbol{x})
    =&\quad \
    \sum_{ \cF } \quad \left(\prod_{i\in \Des(\lambda_\cF)} x_i \right) \cdot  
    \left(\prod_{ \substack{i \in \{0,\dots , k-1 \} \\ i,i+1 \notin \Des(\lambda_\cF) } } (1+x_i) \right) &&\in \NN [x_0,\dots , x_{\rk(M)-1}] \,.
\end{align*}
Here, both sums range over all maximal chains $\cF$ in~$\cL(M)$ such that $\Des(\lambda_\cF) \in \mathsf{nc}(k-1)$ contains no consecutive elements.
Setting all $x_i = x$, we get back the usual Chow and augmented Chow polynomials of $M$, respectively, as given in \eqref{eq: Chow gamma exp Stump} and \eqref{eq: augChow gamma exp Stump}.
\medskip

The motivation for the multivariate versions is combinatorial, see \Cref{rem: comb multi version}.
Since both the Chow polynomial and the augmented Chow polynomial arise as Hilbert series of a graded ring, a natural question is whether the given multivariate polynomials can be interpreted as multigraded Hilbert series.

\begin{remark}[A combinatorial natural choice for the multivariate version]
    \label{rem: comb multi version}
    Chow polynomials and augmented Chow polynomials are evaluations of the \emph{Poincaré-extended $\boldsymbol{ab}$-index},
    which is a polynomial in the variable~$y$ with coefficients in the non-commutative ring $\ZZ\langle \boldsymbol{a},\boldsymbol{b}\rangle$.
    This polynomial was introduced in \Cite{poincareextended}
    and encodes the positions of ascents and descents of edge-labeling sequences of maximal chains.
    By applying the evaluation approach from~\Cite[Theorem 2.6]{stump2024chowaugmentedchowpolynomials} to the identity given in~\Cite[Corollary 2.11]{poincareextended} and distinguishing descents by their position, we derive the multivariate forms presented here.
\end{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Uniform matroids}
An $R$-labeling on $\cL(M)$ can be constructed by any total order on the atoms of $\cL(M)$,
see~\Cite[Proposition 2.2]{MR0354473}.
For the uniform matroid $U_{k,n}$, the usual total order $1< \dots< n $ yields the $R$-labeling $\lambda$, defined by 
\begin{equation}
    \label{eq: R labeling uniform matroid}
    \lambda(S \prec T) = \min( T\setminus S ) \,.
\end{equation}
In particular, the entries in the sequence $\lambda_\cF = (\lambda_1,\dots , \lambda_k)$ for a maximal chain~$\cF$ in~$\cL(U_{k,n})$ are all different.

Applying this $R$-labeling to the definition of the multivariate Chow polynomial and of the multivariate augmented Chow polynomial results in the following proposition.

\begin{proposition}
    \label{prop: Chow and augChow uniform gamma exp}
    The multivariate Chow polynomial of the uniform matroid $U_{k,n}$ is given by
    \begin{align*}
        \Chow_{U_{k,n}} (\boldsymbol{x})
        &= \quad
        \sum_{ \substack{ D \in \mathsf{nc}(k-1) \\ 1\notin D } } \quad 
        \Eulerian(n,D) \quad \ 
        \cdot \left(\prod_{i\in D} x_i \right) 
        \cdot \left(\prod_{ \substack{i \in \{1,\dots , k-1 \} \\ i,i+1 \notin D } } (1+x_i) \right) \\
        &= 
        \sum_{ \substack{ \sigma \in \Sym_k \\ \Des(\sigma) \in \mathsf{nc}(k-1) \\ \sigma(1) < \sigma(2) } } 
        \binom{n - \sigma(k)}{k - \sigma(k)} 
        \cdot \left(\prod_{i\in \Des(\sigma)} x_i \right) 
        \cdot \left(\prod_{ \substack{i \in \{1,\dots , k-1 \} \\ i,i+1 \notin \Des(\sigma) } } (1+x_i) \right) \,
    \end{align*}
    and the multivariate augmented Chow polynomial of the uniform matroid $U_{k,n}$ is given by
    \begin{align*}
        \Chowaug_{U_{k,n}} (\boldsymbol{x})
        &= \quad
        \sum_{ \substack{ D \in \mathsf{nc}(k-1) } } \quad 
        \Eulerian(n,D) \quad \ 
        \cdot \left(\prod_{i\in D} x_i \right) 
        \cdot \left(\prod_{ \substack{i \in \{0,\dots , k-1 \} \\ i,i+1 \notin D } } (1+x_i) \right) \\
        &= 
        \sum_{ \substack{ \sigma \in \Sym_k \\ \Des(\sigma) \in \mathsf{nc}(k-1) } } 
        \binom{n - \sigma(k)}{k - \sigma(k)} 
        \cdot \left(\prod_{i\in \Des(\sigma)} x_i \right) 
        \cdot \left(\prod_{ \substack{i \in \{0,\dots , k-1 \} \\ i,i+1 \notin \Des(\sigma) } } (1+x_i) \right) \,.
    \end{align*}
\end{proposition}

\begin{theorem}
    \label{thm: multi Chows monomial}
    The multinomial Chow polynomial and the multinomial augmented Chow polynomial of the uniform matroid $U_{k,n}$ are given by
    \begin{align*}
        \Chow_{U_{k,n}}(\boldsymbol{x}) 
        &= \sum_{\substack{I \subseteq \{1,\dots,k\} \\ 1 \in I }} 
        \binom{n}{ \Delta I } \prod_{i\in I\setminus \{1\}} x_{i-1} \,,
        \quad\text{and} \\
        \Chowaug_{U_{k,n}}(\boldsymbol{x}) 
        &= \sum_{\substack{I \subseteq \{1,\dots,k\} }} 
        \binom{n}{ \Delta I } \ \ \prod_{i\in I} \ x_{i-1} \,.
    \end{align*}
\end{theorem}
\begin{proof}[Sketch of the proof]
    We only sketch the proof for the non-augmented case.
    For positive integers $k \leq n$, let
    \begin{align*}
        F_{k,n}(\boldsymbol{x}) 
        &= \sum_{\substack{I \subseteq \{1,\dots,k\} \\ 1 \in I }} 
        \binom{n}{ \Delta I } \prod_{i\in I\setminus \{1\}} x_{i-1} \,.
    \end{align*}
    Comparing coefficients, we show that~$F_{k,n}(\boldsymbol{x})=\Chow_{U_{k,n}} (\boldsymbol{x})$.
    Fix a subset~$S \subseteq \{1,\dots, k-1\}$.
    The coefficient of $\boldsymbol{x}^S = \prod_{i\in S} x_i$ in $F_{k,n}(\boldsymbol{x})$ and in~$\Chow_{U_{k,n}}(\boldsymbol{x})$, respectively, is given by
    \begin{align*}
        [\boldsymbol{x}^S] F_{k,n} (\boldsymbol{x}) = \binom{n}{\Delta \{1\}\cup(S + 1)} 
        \qquad \text{ and } \qquad
        [\boldsymbol{x}^S] \Chow_{U_{k,n}} (\boldsymbol{x}) =  \sum_{ D } \Eulerian (n,D) 
    \end{align*}
    where $S + 1 = \set{s+1}{s \in S}$, 
    and where the sum on the right ranges over all subsets~$D \subseteq \{ \min (S_1) ,\dots \min (S_j) \}$ with $1\notin D$.
    The right-hand side is
    \begin{align*}
      [\boldsymbol{x}^S] \Chow_{U_{k,n}} (\boldsymbol{x})
      &=  \sum_{ \substack{D \subseteq \{ \min (S_1) ,\dots \min (S_j) \} \\ 1\notin D } } 
        \Eulerian (n,D) \\
      &= \# \bigset{ w\in \Sym_n }{ \Des(w) \subseteq \{ \min (S_1) ,\dots \min (S_j) \} } \\
      &= \binom{ n }{ \min (S_1) , \min (S_2) - \min (S_1) , \dots , \min (S_{j}) - \min (S_{j-1}) , n - \min (S_j) } \,,
    \end{align*}
    which equals the coefficient of $\boldsymbol{x}^S$ in $F_{k,n}(\boldsymbol{x})$.
\end{proof}

\begin{proof}[Proof of \Cref{thm: Chow four ways,thm: Chow aug four ways}]
    This follows by setting $x_i = x$ in \Cref{prop: Chow and augChow uniform gamma exp} and \Cref{thm: multi Chows monomial}.
\end{proof} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Schubert matroids}
\label{sec: Schubert matroids}
Recall \Citeauthor{Priv_Comm_Ferroni}'s conjecture stated in \Cref{thm: Ferroni}, saying that the coefficient of $x^m$ in the Chow and in the augmented Chow polynomials of the uniform matroid $U_{k,n}$ are given by
\begin{align*}
    [x^m] \Chow_{U_{k,n}}(x)
    &=
    \# \big\{ \substack{\ \text{loopless Schubert matroids on the ground set } [n] \\ \text{of rank $m+1$ and cogirth greater than } n-k }  \ \big\} 
    \quad
    \text{for } 0\leq m \leq k-1 \,,  \\
    [x^m] \Chowaug_{U_{k,n}}(x)
    &=
    \# \big\{ \ \substack{\text{\phantom{loop} Schubert matroids\phantom{less} on the ground set } [n] \\ \text{of rank \phantom{+}$m$\phantom{1} and cogirth greater than } n-k } \ \big\} \quad
    \text{for } 0\leq m \leq k \,.
\end{align*}
In this section, we study the Schubert matroid on the fixed ground set $[n]$ to determine the values of the right-hand side.
\medskip

The Schubert matroid $\cS_{I,\pi}$ for $I \in \binom{[n]}{k}$ and $\pi \in \Sym_n$ has bases $\set{J\in \binom{[n]}{k}}{I\leq_\pi J }$.
The rank of $\cS_{I,\pi}$ is $k$, the size of the set $I$, 
but its loops and cogirth depend on both~$I$ and~$\pi$.

\begin{proposition}
    \label{prop: Schubert matroid props}
    Let $n\geq k$ be positive integers, and let $I\subseteq \{1,\dots, n\}$ and $\pi\in \Sym_n$.
    Let~$\min_\pi (I)$ denote the minimal, and let $\max_\pi (I)$ denote the maximal element in $I$ with respect to the order $\leq_\pi$.
    \begin{enumerate}
        \item $\cS_{I,\pi}$ has loops $\{\pi(1), \pi(2), \dots , \pi( m - 1) \}$ where $\pi(m) = \min_\pi (I)$.
        \item $\cS_{I,\pi}$ has cogirth $n+1- c$ where $\pi(c) = \max_\pi (I)$.
        \item $\cS_{I,\pi} = \cS_{\pi^{-1}(I),\id}$ with~$\pi^{-1}(I) = \set{\pi^{-1}(i)}{i\in I}$.
    \end{enumerate}
\end{proposition}
\begin{proof}[Sketch of the proof]
    An element $x\in [n]$ is a loop in $\cS_{I,\pi}$ if $x$ is smaller than every element in $I$, which proves the first statement.
    The third statement follows immediately by the definition of the total order.
    The second statement follows from the observation, 
    that the cogirth of $\cS_{I,\pi}$ is greater than $n-c$ if and only if $\max_\pi(I) \leq \pi(c)$.
\end{proof}

\begin{theorem}
    \label{thm: SM counting when restricted}
    The number of Schubert matroids on the ground set $[n]$ of rank $m$, with $\ell$ loops, and having cogirth $n+1-k$ is 
    \[
        \sum_{ \substack{I \subseteq \{\ell + 1,\dots , k\} \\ \ell + 1 , k \in I \\ \vert I \vert = m } } \binom{n}{\Delta I} \,.
    \]
\end{theorem}

\begin{proof}[Sketch of the proof]
By \Cref{prop: Schubert matroid props}, the number of Schubert matroids on the ground set~$[n]$ of rank~$m$, with~$\ell$ loops, and having cogirth~$n-k$ is
\begin{align*}
    \label{eq: Chow monomial orbit}
    \sum_{ \substack{I \subseteq \{\ell + 1,\dots,k\} \\ \ell + 1, k \in I \\\vert I \vert = m } } \#\set{\cS_{\pi(I),\pi}}{\pi \in \Sym_n} \,.
\end{align*}
The group $\Sym_n$ acts on the set of Schubert matroids by~$\tau \ast \cS_{I,\pi} = \cS_{\tau(I), \tau \pi}$.
By the orbit-stabilizer theorem and by Lagrange's theorem, we have
\[
\# \set{ \cS_{\pi(I),\pi} }{ \pi \in \Sym_n} = \frac{n!}{ \# \set{\pi\in \Sym_n}{ \cS_{\pi(I),\pi} = \cS_{I,\id} } } \,.
\]
A permutation~$\pi\in \Sym_n$ satisfies $\cS_{\pi(I),\pi} = \cS_{I,\id}$ if and only if it can be written as a product of permutations $\pi = \pi^{(0)} \pi^{(1)} \cdots \pi^{(s)}$ such that for~$j\in \{0,\dots , s\}$
\begin{align*}
    \pi^{(j)} &\in \Perm(\{m_j, m_j+1, \dots, m_{j+1}-1\}) 
    \quad \text{with } 
    m_j = 
    \begin{cases}
        1, & j = 0, \\
        \min(I_j), & 1 \leq j \leq s-1, \\
        n+1, & j = s,
    \end{cases} 
\end{align*} 
where~$I = I_1 \cup \dots \cup I_s \subseteq [n]$ is the disjoint partition into maximal consecutive subsets such that $\min(I_j) < \min(I_{j+1})$.
Thus, the multinomial coefficient $\binom{n}{\Delta I}$ gives the size of the orbit~$\set{ \cS_{\pi(I),\pi} }{ \pi \in \Sym_n}$.
\end{proof}

We deduce \Cref{thm: Ferroni} from \Cref{thm: SM counting when restricted}.

\begin{proof}[Proof of \Cref{thm: Ferroni}]
    This is an immediate consequence of \Cref{thm: SM counting when restricted}, as the polynomials coincide with the monomial expansions given in \Cref{thm: Chow four ways} and \Cref{thm: Chow aug four ways}.
\end{proof}

\begin{example}
    Let $I = \{2,3,5,7,8\}=\{2,3\}\cup\{5\}\cup\{7,8\}$. 
    The stabilizer of the Schubert matroid $\cS_{I,\id}$ on the ground set $[n]$, for $n\geq 8$, is isomorphic to
    \begin{align*}
        \Perm(\{1\}) \times \Perm(\{2,3,4\}) \times \Perm(\{5,6\}) \times \Perm(\{7,\dots , n\}) 
                \cong \
        \Sym_1 \times \Sym_3 \times \Sym_2 \times \Sym_{n-6} \,.
    \end{align*}
    Thus, the size of the orbit $\set{ \cS_{\pi(I),\pi} }{ \pi \in \Sym_n}$ equals the multinomial coefficient $\binom{n}{\Delta I}$, that is
    \[
    \# \set{ \cS_{\pi(I),\pi} }{ \pi \in \Sym_n} 
    = \frac{n!}{ \# ( \Sym_1 \times \Sym_3 \times \Sym_2 \times \Sym_{n-6} ) }
    = \frac{n!}{1!\ 3!\ 2!\ (n-6)!}
    =  \binom{n}{\Delta I} \,.
    \]
\end{example}

\acknowledgements{
    The author would like to thank Luis Ferroni for bringing Chow polynomials to her attention, sharing his conjecture, and providing valuable feedback during the writing of this paper.
    She also wishes to thank Christian Stump for helpful discussions and his supervision throughout this research.
    Additionally, the author acknowledges Hsin-Chieh Liao for his insightful comments on the first version of the paper.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\printbibliography

\end{document}