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

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

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

\usepackage{lipsum}
\setlength{\headheight}{16pt} %added to avoid \vbox error
\usepackage{mathtools}
\usepackage{tikz}
\usepackage{amsmath}

\theoremstyle{plain}
   \newtheorem{theorem}{Theorem}[section]
   \newtheorem{proposition}[theorem]{Proposition}
   \newtheorem{lemma}[theorem]{Lemma}
   \newtheorem{corollary}[theorem]{Corollary}
   \newtheorem{problem}[theorem]{Problem}
   \newtheorem{conjecture}[theorem]{Conjecture}
   \newtheorem{question}[theorem]{Question}
\theoremstyle{definition}
   \newtheorem{definition}[theorem]{Definition}
   \newtheorem{example}[theorem]{Example}
   \newtheorem{exercise}[theorem]{Exercise}
   \newtheorem{notation}[theorem]{Notation}
\theoremstyle{remark}
   \newtheorem{remark}[theorem]{Remark}

\newcommand{\NN}{\mathbb{N}}
\newcommand{\zz}{\mathbf{z}}
\newcommand{\ww}{\mathbf{w}}
\newcommand{\xx}{\mathbf{x}}
\newcommand{\yy}{\mathbf{y}}
\newcommand{\uu}{\mathbf{u}}
\newcommand{\vv}{\mathbf{v}}
\newcommand{\ee}{\mathbf{e}}

\renewcommand{\aa}{\mathbf{a}}
\newcommand{\one}{\hat{1}}
\newcommand{\zero}{\hat{0}}
\newcommand{\LL}{\mathscr{L}}
\newcommand{\SSS}{\mathscr{S}}
\newcommand{\MM}{\mathcal{M}}
\newcommand{\PO}{\mathbb{P}}
\newcommand{\FQ}{\text{FQSym}}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\BB}{\mathcal{B}}
\newcommand{\VV}{\mathcal{V}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\EE}{\mathcal{E}}
\newcommand{\FF}{\mathcal{F}}
\newcommand{\PP}{\mathcal{P}}
\newcommand{\GG}{\mathcal{G}}
\newcommand{\HHH}{\overline{\mathcal{H}}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RRR}{\mathcal{R}}
\newcommand{\CCC}{\mathcal{C}}
\newcommand{\PR}{\mathbb{R}\{t\}}
\newcommand{\PC}{\mathbb{C}\{t\}}
\newcommand{\SNN}{\text{SNN}}
\newcommand{\CM}{\mathbb{C}_{ {MA}}}
\newcommand{\CMS}{\mathbb{C}_{ {MAS}}}
\newcommand{\sym}{\mathfrak{S}}
\newcommand{\ps}{\text{ps}_q^1}
\renewcommand{\mod}{\mathop{\rm \ mod}}
\renewcommand{\Im}{{\rm Im}}
\renewcommand{\Re}{{\rm Re}}
\newcommand{\FQS}{\text{FQSym}}
\newcommand{\PF}{\mathrm{PF}}
\newcommand{\TP}{\mathrm{TP}}

\DeclareMathOperator{\sd}{sd}
\DeclareMathOperator{\Des}{Des}
\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\inv}{inv}

%% define your title in the usual way
\title[Chain polynomials of generalized paving matroids]{Chain polynomials of generalized paving matroids}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Petter Brändén and Leonardo Saud Maia Leite]{Petter Brändén\thanks{\href{mailto:pbranden@kth.se}{pbranden@kth.se}. Petter Brändén is a Wallenberg Academy Fellow supported by the Knut and Alice Wallenberg Foundation, and the Göran Gustafsson foundation.}\addressmark{1} \and Leonardo Saud Maia Leite\thanks{\href{mailto:lsml@kth.se}{lsml@kth.se}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden}

%% put the date of submission here
\received{April 2nd, 2024}

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

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We prove that the chain polynomial of the lattice of flats of a paving matroid is real-rooted, and we define a class of matroids called \textit{generalized paving matroids}. Generalized paving matroids associated to subspace lattices are shown to have real-rooted chain polynomials, by a study of a $q$-analog of the subdivision operator.  We finish by studying single element extensions, and prove that the chain polynomials of the lattice of flats of single element extensions of $U^n_n$ and $U^{n-1}_n$ are real-rooted.}

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

%% put your keywords here, or comment this out if you don't have them yet
\keywords{matroid, chain polynomial, geometric lattice, real-rootedness}

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

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

\begin{document}
\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
The chain polynomial of a finite poset $P$ is defined as
\begin{equation}
\label{chainpol}
    c_P(t) \coloneqq \sum_{k \geq 0} c_k (P) t^k,
\end{equation}
where $c_k (P)$ is the number of $k$-element chains in $P$. The chain polynomials of posets in several important classes have been proven to be real-rooted. For example face lattices of simplicial \cite{brenti2008f} and cubical polytopes \cite{athanasiadis2021face}, $(3+1)$-free posets \cite[Corollary 2.9]{stanley1998graph}, and for some classes of distributive lattices \cite{brenti1989,wagner1992enumeration}, but not all \cite{stembridge2007counterexamples}. In \cite{athanasiadis2022chain} the authors asked for which posets the chain polynomial is real-rooted. In particular the following conjecture was formulated. 

\begin{conjecture}
\cite[Conjecture 1.2]{athanasiadis2022chain}
\label{conj1}
    The chain polynomial $c_\mathcal{L}(t)$ is real-rooted for every geometric lattice $\mathcal{L}$.
\end{conjecture}

This conjecture can bee seen as a member of a family of recent conjectures about the real-rootedness of Kazhdan-Lusztig polynomials \cite{elias2016kazhdan, gedeon2016kazhdan} and Chow ring Poincar\'e polynomials \cite{ferroni2022valuative, stevens2021real} associated matroids arising in the emerging Hodge theory of matroids \cite{huh2022combinatorics}. 

% Ben Elias, Nicholas Proudfoot, and Max Wakefield, The Kazhdan-Lusztig polynomial of a matroid, Adv. Math. 299 (2016), 36–70.
% Luis Ferroni and Benjamin Schro ̈ter, Valuative invariants for large classes of matroids. arXiv:2208.04893.
% Katie Gedeon, Nick Proudfoot and Ben Young, Kazhdan-Lusztig polynomials of matroids: a survey of results and conjectures. S ́eminare Lotharingien Combinatoire 78 (2017).
% Matthew Stevens, Real-rootedness conjectures in matroid theory. 2021, Thesis Stanford University, https://mcs0042.github.io/bachelor.pdf.
% June Huh, Combinatorics and Hodge theory. Proc. Int. Cong. Math. 1 (2022).





In~\cite{athanasiadis2022chain}, Athanasiadis and Kalampogia-Evangelinou proved Conjecture~\ref{conj1} for the subspace lattices $\mathcal{L}_n(q)$, for the partition lattices $\Pi_n$ and $\Pi_n^B$, and for the lattice of flats of near-pencils and uniform matroids. 
%It is known that every geometric lattice corresponds to the lattice of flat of a finite matroid, so we focus in the study of matroids to approach Conjecture~\ref{conj1}.

The purpose of this paper is to verify Conjecture~\ref{conj1} for further classes of geometric lattices. We prove Conjecture~\ref{conj1} for the lattice of flats of paving matroids, a class of matroids which is conjectured to correspond to almost all finite matroids. We define a new class of matroids, called \textit{generalized paving matroids}, that includes the class of paving matroids and we prove Conjecture~\ref{conj1} for generalized paving matroids associated to subspace lattices. In the process we extend the well studied \emph{subdivision operator} $\EE$  (see \cite{branden2015unimodality,brenti2008f}) to subspace lattices, and prove several real-rootedness results concerning these generalized subdivision operators. We finish the paper by studying single-element extensions and proving that the chain polynomials of the lattice of flats of single-element extensions of some uniform matroids are real-rooted.


\section{Interlacing polynomials}
In this section we collect a few results and terminology that will be needed in subsequent sections, for proofs we refer to \cite{branden2015unimodality}. 

Let $f,g \in \mathbb{R}[t]$ be real-rooted polynomials with nonnegative coefficients and of degrees $r$ and $s$, respectively. Let $x_r \leq \cdots \leq x_2 \leq x_1$ be the zeros of $f$, and let $y_s \leq \cdots \leq y_2 \leq y_1$ be the zeros of $g$. We say that $g$ \textit{interlaces} $f$ (written $g \preceq f$) if either $r = s$ and
$$
y_s \leq x_r \leq \cdots \leq y_2 \leq x_2 \leq y_1 \leq x_1 
$$
or $r = s+1$ and
$$
x_r \leq y_s \leq x_{r-1} \leq \cdots \leq y_2 \leq x_2 \leq y_1 \leq x_1.
$$


We say that a sequence of polynomials $f_1, f_2, \ldots, f_m \in \mathbb{R}[t]$ is \textit{interlacing} if $f_i \preceq f_j$ whenever $i < j$.

%We will now state some well known results about interlacing polynomials, see~\cite{branden2015unimodality}:

\begin{proposition}\label{cone}
Let $f,g,h \in \mathbb{R}[t]$. 
\begin{enumerate}
\item If $f \preceq g$ and $f \preceq h$, then $f \preceq a g + b h$ for all $a,b \geq 0$. 
\item If $g \preceq f$ and $h \preceq f$, then $a g + b h \preceq f$ for all $a,b \geq 0$.
\end{enumerate}
\end{proposition}

\begin{proposition}\label{lemma2.3}
    Let $f_0, f_1, \ldots, f_m \in \mathbb{R}[t]$ be an interlacing sequence of real-rooted polynomials with positive leading coefficients.
    \begin{enumerate}
        \item Every nonnegative linear combination $f$ of $f_0, f_1, \ldots, f_m$ is real-rooted, and $f_0 \preceq f \preceq f_m$;
        \item If we define
        $$
        g_k  \coloneqq t \sum_{i=0}^{k-1} f_i + \sum_{i=k}^{m} f_i,
        $$
        for $k = 0, 1, \ldots, m$, then $\{ g_i \}_{i=0}^m$ is interlacing.
    \end{enumerate}
\end{proposition}

\begin{proposition}\label{ends}
    Let $f_1, \ldots, f_m \in \mathbb{R}[t]$. If $f_1 \preceq f_2 \preceq \cdots \preceq f_m$ and $f_1 \preceq f_m$, then $f_i \preceq f_j$ for all $i \leq j$.
\end{proposition}

\begin{lemma}\label{f-vers}
Suppose $f_0, f_1, \ldots, f_n$ is an interlacing sequence of polynomials of degree $d$, such that for each $0\leq j \leq n$, the polynomial $f_j$ has nonnegative leading coefficient and all zeros in the interval $[-1,0]$. Then the  sequence $g_0, g_1, \ldots, g_{n+1}$ defined by 
$$
g_k= t\sum_{j=0}^{k-1}f_j+ (1+t) \sum_{j=k}^nf_j, 
$$
is interlacing. 
\end{lemma}

\begin{proof}
Let $h_j(t)= (1-t)^df_j(t/(1-t))$ and $r_j(t) = (1-t)^{d+1}g_j(t/(1-t))$. Then $\{h_j\}_{j=0}^n$ is an interlacing sequence of polynomials with nonnegative coefficients. Moreover, 
$$
r_j = t\sum_{j=0}^{k-1}h_j+  \sum_{j=k}^nh_j,
$$
and hence $\{r_j\}_{j=0}^{n+1}$ is interlacing by Proposition \ref{lemma2.3}. Since $g_j= (1+t)^{d+1}r_j(t/(1+t))$, the lemma follows.
\end{proof}

\section{Generalized subdivision operators}
Let $P$ be a  locally finite  and graded poset with a least element $\zero$,  such that 
$[\zero, x]$ is isomorphic to $[\zero, y]$ whenever $x$ and $y$ have the same rank. Define a linear operator $\EE_P : \RR[t] \to \RR[t]$ by $\EE_P(1)= 1$, and 
$$
\EE_P(t^n)= \sum_{j = 1}^n |\{\zero <x_1<\cdots < x_j=x \}|\cdot t^j = \frac t {(1+t)^2} \cdot c_{[\zero,x]}(t),
$$
where $x$ is any element in $P$ of rank $n$. Let further $\RRR_P : \RR[t] \to \RR[t]$ be the linear operator defined by 
$$
\RRR_P(t^n) = \sum_{k=0}^n r_{n,k}t^k,
$$
where $r_{n,k}$ is the number of elements in $[\zero, x]$ of rank $k$, where $x$ is any element in $P$ of rank $n$. Hence, for $n \geq 1$, 
\begin{equation}\label{fundE}
\EE_P(t^n) = t \EE_P \big( \RRR_P(t^n) - t^n\big) \ \  \mbox{ and } \ \ (1+t) \EE_P(t^n)= t\EE_P(\RRR_P(t^n)). 
\end{equation}



If $P$ is a Boolean lattice, then $\EE_P$ is the \emph{subdivision operator} $\EE$,  which has the property that 
$$
\EE(f_\Delta(t)) = f_{\sd(\Delta)}(t),
$$
for any simplicial complex $\Delta$, where $f_\Delta$ is the $f$-polynomial of $\Delta$ and 
$\sd(\Delta)$ is the barycentric subdivision of $\Delta$, see \cite{branden2015unimodality,brenti2008f}. The subdivision operator is important in proving real-rootedness for polynomials associated to simplicial complexes, posets or Ehrhart theory \cite{branden2015unimodality}. In this section we will generalize and refine the following result to subspace lattices 
$\mathcal{L}_n(q)$. 
\begin{proposition}\cite[Section 4]{branden2006linear}
\label{basis}
    The sequence  $\{\EE\left(t^{i}(t+1)^{d-i}\right) \}_{i=0}^d$ is interlacing.
\end{proposition}


Let $\mathcal{L}(q)$ be the inverse limit, as $n \to \infty$, of the subspace lattices $\mathcal{L}_n(q)$ of all subspaces of $\mathbb{F}_q^n$,  where $\mathbb{F}_q$ is a finite field with $q$ elements. Denote by $\EE_q$, the linear operator $\EE_{\mathcal{L}(q)}$. 
Hence 
\begin{equation}\label{fundEq}
\EE_q(t^n) = t \EE_q \big( G_n(t) - t^n\big),  
\end{equation}
where $G_n(t)  = \sum_{k=0}^n {\binom n k}_{\!  q} t^k$, and ${\binom n k}_{\!  q}$, $0\leq k \leq n$, are the \emph{Gaussian polynomials} which may be defined recursively by ${\binom n 0}_{\!  q}=1$, and 
\begin{equation}\label{qbin}
{\binom n k}_{\! \! \! q} = q^k {\binom {n-1} {k}}_{\! \! \! q}+{\binom {n-1} {k-1}}_{\! \! \! q}, 
\end{equation}
see \cite[Section 1.7]{stanley2011enumerative}. Henceforth we let $q$ be any real number greater or equal to $1$. 

\begin{lemma}\label{q-rec}
Let $n$ be a nonnegative integer. Then 
\begin{equation}\label{q-eq1}
\EE_q(t^kG_{n+1-k}(t))= t\sum_{j=0}^{k-1}\EE_q(t^jG_{n-j}(qt))+ (1+t)\sum_{j=k}^{n}\EE_q(t^jG_{n-j}(qt)), \ \ \ \ 0\leq k \leq n+1, 
\end{equation}
and 
\begin{equation}\label{q-eq2}
\EE_q(t^kG_{n-k}(qt))= \EE_q(t^kG_{n-k}(t))+(q^{n-k}-1)\EE_q(t^{k+1}G_{n-(k+1)}(t)), \ \ \ \ 0\leq k \leq n.
\end{equation}
\end{lemma}

\begin{proof}
The identity \eqref{qbin} 
implies 
%$$
%G_{n+1}(t)-t^{n+1} = \sum_{j=0}^{n} t^j G_{n-j}(qt), 
%$$
%and hence 
\begin{equation}\label{gnuq}
t^kG_{n+1-k}(t) -t^{n+1} = \sum_{j=k}^{n} t^j G_{n-j}(qt).
\end{equation}
By \eqref{fundEq} and \eqref{gnuq}, 
$$
\EE_q(t^{n+1})= t\EE_q(G_{n+1}(t)-t^{n+1})= t \sum_{j=0}^{n} \EE_q(t^j G_{n-j}(qt)),
$$
which combined with \eqref{gnuq} gives \eqref{q-eq1}. 

\noindent Similarly, the identity 
\begin{equation}\label{altqbin}
q^k{\binom n k}_{\! \! \! q} = {\binom {n} k}_{\! \! \! q}+(q^n-1){\binom {n-1} {k-1}}_{\! \! \! q}
\end{equation}
implies \eqref{q-eq2}. 
\end{proof}



The following theorem generalizes Theorem \ref{basis} to any $q \geq 1$. 
\begin{theorem}
\label{q-E}
    Let $n$ be a nonnegative integer. The sequence of polynomials  $\{\EE_q(t^kG_{n-k}(t))\}_{k=0}^n$ is interlacing. Moreover all zeros of $\EE_q(t^kG_{n-k}(t))$ lie in the interval $[-1,0]$. 
\end{theorem}
\begin{proof}
The proof is by induction over $n$, the case $n=0$ being trivial. 

Suppose true for $n-1\geq 0$. Since $\{\EE_q(t^kG_{n-k}(t))\}_{k=0}^n$ is interlacing, we have by \eqref{q-eq2} and \cite[Corollary 8.6]{branden2015unimodality} that $\{\EE_q(t^kG_{n-k}(qt))\}_{k=0}^n$ is interlacing. Moreover \eqref{q-eq2} implies  
$$
\EE_q(t^kG_{n-k}(t)) \prec \EE_q(t^kG_{n-k}(qt)) \prec \EE_q(t^{k+1}G_{n-k-1}(t)), 
$$
so that all zeros of $\EE_q(t^kG_{n-k}(qt))$ are in the interval $[-1,0]$. The lemma now follows by induction from \eqref{q-eq1} and Lemma \ref{f-vers}. 
\end{proof}

\begin{corollary}\label{poscoe}
Suppose $f= \sum_{k=0}^d h_k t^k G_{d-k}$, where $h_k \geq 0$ for all $0\leq k \leq d$. Then $\EE_q(f)$ is real-rooted and 
$\EE_q(G_d) \prec \EE_q(f) \prec \EE_q(t^d)$. 
\end{corollary}
\begin{proof}
Follows immediately from Proposition \ref{lemma2.3} and Theorem \ref{q-E}. 
\end{proof}


For $d \leq n$, let $G_{n,k}^d$ be the polynomial obtained from $t^kG_{n-k}(t)$ by removing 
all terms $t^j$, where $j>d$. 

\begin{lemma}\label{knd}
Let $d$ be a nonnegative integer. 
\begin{itemize}
\item[(a)]  If $n \geq d$, then $\{\EE_q(G_{n,k}^d)\}_{k=0}^d$ is interlacing. 
\item[(b)]  If $0 \leq k \leq d$, then $\{\EE_q(G_{n,k}^d)\}_{n=d}^\infty$ is interlacing. 
\end{itemize}
\end{lemma}
\begin{proof}
We first prove (a) by induction over $n \geq d$, the case $n=d$ being Theorem \ref{q-E}. Assume true for $n$. Equations \eqref{gnuq} and \eqref{altqbin} imply 
$$
t^kG_{n+1-k}-t^{n+1} =  t^kG_{n-k}+ \sum_{j=k+1}^{n} q^{n+1-j} t^{j} G_{n-j}, 
$$
and thus
$$
\EE_q(G_{n+1,k}^d) = \EE_q(G_{n,k}^d)+ \sum_{j=k+1}^{d} q^{n+1-j} \EE_q(G_{n,j}^d), 
$$
which by \cite[Corollary 8.6]{branden2015unimodality} proves that $\{\EE_q(G_{n+1,k}^d)\}_{k=0}^d$ is interlacing, and that $\EE_q(G_{n,k}^d) \prec \EE_q(G_{n+1,k}^d)$. This proves (a) by induction.

\noindent Notice that 
$$
\lim_{n \to \infty} \frac {\EE_q(G_{n,k}^d)}{ {\binom {n-k} d }_{\! q}}= \EE_q(t^d), 
$$
and that $\EE_q(G_{d,k}^d) \prec \EE_q(t^d)$ by Theorem \ref{q-E}. Hence (b) now follows from Proposition \ref{ends}. 


%As in the proof of \eqref{q-eq2} it follows that 
%$$
%\EE_q(q^{-k}G_{n,k}^d(qt))=  \EE_q(G_{n,k}^d(t)) + (q^{n-k}-1)\EE_q(G_{n,k+1}^d(t)). 
%$$
%Hence $\{\EE_q(q^{-k}G_{n,k}^d(qt))\}_{k=0}^d$ is interlacing. Also \eqref{gnuq} implies 
%$$
%\EE_q(G_{n+1,k}^d(t)) = \sum_{j=k}^n \EE_q(q^{-k}G_{n,k}^d(qt)). 
%$$
\end{proof}

The next theorem generalizes a recent result \cite{athanasiadis2023two} of Athanasiadis and Kalampogia-Evangelinou  from Boolean lattices to subspace lattices.
Suppose $P$ is a graded poset, and $S=\{0=s_0<s_1<s_2<\cdots\} \subseteq \NN$. Consider the rank selected poset $P_S := \{ x \in P : \rho(x) \in S\}$.  Define a linear operator $T_S : \RR[t] \to \RR[t]$ by 
$$
T_S(t^k) = \begin{cases}
0 &\mbox{ if } k \not \in S, \\
t^i &\mbox{ if } k=s_i.
\end{cases}
$$

\begin{theorem}
Let $n$ be a positive integer, and let $S$ be a subset of $\NN$ containing $0$. The sequence$\{\EE_{P} ( T_S(t^kG_{n-k}))\}_{k=0}^n$ is interlacing, where $P= \mathcal{L}(q)_S$. In particular the chain polynomial of $\mathcal{L}_n(q)_S$ is real-rooted. 
\end{theorem}

\begin{proof}
The proof is omitted in this extended abstract.    
\end{proof}

\section{Generalized paving matroids}
\label{gen-pav-mat}
Recall that a geometric lattice $\mathcal{L}$  of rank $d+1$ is the lattice of flats of a paving matroid on $E$ if and only if 
\begin{itemize}
    %\item $E$ is the flat of rank $d+1$;
    \item the set $\mathcal{H}$ of hyperplanes of $\mathcal{L}$ form a $d$-\emph{partition}, i.e., $|H| \geq d$ for each $H \in \mathcal{H}$, and for each set $S$ of size $d$ there exists a unique $H \in \mathcal{H}$ such that $S \subseteq H$;
    \item the flats of rank $k \leq d-1$ are the sets of size $k$ of the Boolean lattice on $E$.
\end{itemize}

For example, if $\mathcal{P} = \binom{[n]}{d}$, then $\mathcal{P}$ is a $d$-partition of $[n]$ and, hence, there is a paving matroid whose set of hyperplanes is $\mathcal{H}_1 = \binom{[n]}{d}$. Another example, a $2$-partition of $[7]$, is $\mathcal{H}_2 = \{ \{1,2,4\}, \{1,3,7\}, \{1,5,6\}, \{3,4,6\}, \{2,6,7\}, \{4,5,7\}, \{2,3\}, \{2,5\}, \{2,3\}, \{3,5\}\}$.

We will now generalize this construction to any geometric lattice, and prove that the chain polynomials of the lattice of flats of generalized paving matroids associated to subspace lattices and Boolean lattices are real-rooted. 

Let $\mathcal{L}$ be a geometric lattice with rank function $\rho$ on a ground set $E$. Suppose $d \geq 1$, and  suppose $\mathcal{H} \subset \mathcal{L}$ satisfies  
    \begin{itemize}%[leftmargin=*]
        \item[(a)] $\rho(H)\geq d$ for each $H \in \mathcal{H}$, 
        %\item $r(F_1 \wedge F_2) <d$ for all $F_1, F_2 \in \mathcal{H}$, and 
        \item[(b)] for each $F \in \mathcal{L}$ with $\rho(F)= d$, there exists a unique $H \in \mathcal{H}$ such that $F \leq H$. 
    \end{itemize}
    
Let $\mathcal{L}(\mathcal{H})$ be the graded meet semi-lattice of rank $d+1$, 
$$
\mathcal{L}(\mathcal{H})= \{ F \in \mathcal{L}(\mathcal{H}) : \rho(F)\leq d-1\} \cup \mathcal{H} \cup \{E\}. 
$$

\begin{lemma}\label{d-part}
    $\mathcal{L}(\mathcal{H})$ is a geometric lattice with set of hyperplanes $\mathcal{H}$. 
\end{lemma}
\begin{proof}
       Let $\rho'$ be the rank function of $\mathcal{L}(\mathcal{H})$, and let $\vee$ and $\vee'$ (respectively, $\wedge$ and $\wedge'$) be the joins (respectively, the meets) in $\mathcal{L}$ and $\mathcal{L}(\mathcal{H})$, respectively. We will prove that $\mathcal{L}(\mathcal{H})$ is $(1)$ a lattice, $(2)$ atomistic and $(3)$ semimodular:
       \begin{enumerate}[leftmargin=*]
           \item \textbf{$\mathcal{L}(\mathcal{H})$ is a lattice -} Since $\mathcal{L}(\mathcal{H})$ is a finite meet semi-lattice with a largest element, then, by \cite[Proposition 3.3.1]{stanley2011enumerative}, it is a lattice;
           \item \textbf{$\mathcal{L}(\mathcal{H})$ is atomistic -} Let $F \in \mathcal{L}(\mathcal{H})$. If $\rho'(F) \leq d-1$, then, by definition of $\mathcal{L}(\mathcal{H})$, if $F = \bigvee_i F_i$, then $F = \bigvee_i' F_i$. If $\rho'(F) = d$, then there exist a unique $G \in \mathcal{L}$ such that $\rho(G) = d$ and $G \leq F$. Since $G = \bigvee_i G_i$ for atoms $G_i \in \mathcal{L}$, then $F = \bigvee_i' G_i$.  Finally, if $F=E$, then $F$ is the join of two elements in $\mathcal{H}$ and hence a join of atoms, by the above; 
           \item \textbf{$\mathcal{L}(\mathcal{H})$ is semimodular -} Let $F,G \in \mathcal{L}(\mathcal{H})$. We want to prove that
           \begin{equation}
           \label{smod}
                \rho'(F) + \rho'(G) \geq \rho' (F \vee ' G) + \rho' (F \wedge ' G).
           \end{equation}
           There are three different cases to deal with:
           \begin{itemize}[leftmargin=*]
                \item \textbf{$F$ and $G$ are in $\mathcal{H}$.} Then $\rho' (F) = \rho' (G) = d$, $\rho' (F \vee ' G) = d + 1$ and $\rho' (F \wedge ' G) \leq d-1$, which implies \eqref{smod};
                \item \textbf{$F$ is not in $\mathcal{H}$ and $G$ is in $\mathcal{H}$.} If $F \leq' G$, then there is nothing to prove. Otherwise, $\rho' (F \wedge ' G) \leq \rho' (F) - 1$ and $F \vee' G = E$, and  \eqref{smod} holds;
                \item \textbf{$F$ and $G$ are not in $\mathcal{H}$.} We may assume $F$ and $G$ are smaller than $E$. Then 
                  \begin{align*}
                    \rho'(F)+\rho'(G) &= \rho(F) + \rho(G) \geq  \rho (F \vee G) + \rho (F \wedge G) \\
                     &=  \rho (F \vee G) + \rho'(F \wedge' G). 
                \end{align*}
Hence it remains to prove 
\begin{equation}\label{fpf}
\rho'(F \vee' G) \leq \rho (F \vee G). 
\end{equation}
If $\rho (F \vee G) \leq d-1$, then $F \vee G=F \vee' G$ and so \eqref{fpf} holds. If $\rho (F \vee G) = d$, then there exists $H \in \mathcal{H}$ such that $F \vee G \leq H$, and hence $\rho'(F \vee' G) \leq d$. If $\rho (F \vee G) \geq d+1$, then \eqref{fpf} holds since $\rho'(E)=d+1$.  

            \end{itemize}
        \end{enumerate}
\end{proof}
    
If $\mathcal{L}$ is the Boolean algebra, then the lattices $\mathcal{L}(\mathcal{H})$ are precisely the lattices of flats of paving matroids. 

Notice that 
\begin{equation}\label{gprec}
c_{\mathcal{L}(\mathcal{H})}(t) = c_{\mathcal{L}^d}(t) + t \sum_{H \in \mathcal{H}} c_{[\zero, H]^d}(t), 
\end{equation}
where $\mathcal{L}^d=\{F \in \mathcal{L} : \rho(F) \leq d-1\} \cup \{E\}$ is the truncation of $\mathcal{L}$ to rank $d$. 

The next theorem verifies Conjecture \ref{conj1} for the lattice of flats of paving matroids and generalized paving matroids associated to  subspace lattices. 
\begin{theorem}\label{mainthm}
Suppose $\mathcal{L}$ is a subspace lattice $\mathcal{L}_n(q)$ or a Boolean lattice, and that $\mathcal{H}$ satisfies (a) and (b). Then $c_{\mathcal{L}(\mathcal{H})}(t)$ is real-rooted and $c_{\mathcal{L}^d}(t) \prec c_{\mathcal{L}(\mathcal{H})}(t)$. 
\end{theorem}

\begin{proof}
Clearly, 
$$
c_{\mathcal{L}^d}(t)= (1+t)\cdot \EE_q(G_{n, d-1}^{d-1} (t)) \ \ \mbox{ and } \ \ c_{[\zero, H]^d}(t)= (1+t)\cdot \EE_q(G_{m, d-1}^{d-1} (t)),
$$
where $m \leq n$, and $q=1$ for the Boolean case. The theorem now follows from Proposition~\ref{cone},  Lemma \ref{knd} and \eqref{gprec}. 

\end{proof}


\section{Single-element extensions}
\label{SEE}

Let $N$ be a matroid with ground set $E$. Recall that, if $T \subset E$, then the \textit{deletion of $T$ in $N$} is $N \symbol{92} T$, the matroid on $E \symbol{92} T$ with independent sets given by 
$$
\{ I : \text{$I$ is independent in $N$ and $I \cap T = \varnothing$}\}.
$$

In this case, $N$ is called an \textit{extension} of $N \symbol{92} T$. For the particular case when $|T| = 1$, we call $N$ a \textit{single-element extension} of $N \symbol{92} T$.

A \textit{modular cut} $\mathcal{M}$ of a matroid $M$ is a set of flats of $M$ that satisfies the following:
\begin{enumerate}
    \item[(i)] if $F \in \mathcal{M}$ and $F'$ is a flat of $M$ containing $F$, then $F' \in \mathcal{M}$;
    \item[(ii)] if $F_1, F_2 \in \mathcal{M}$ and $r(F_1) + r(F_2) = r(F_1 \cup F_2) + r(F_1 \cap F_2)$, then $F_1 \cap F_2 \in \mathcal{M}$.
\end{enumerate}

There is a one-to-one correspondence between the modular cuts of a matroid $M$ and single-element extensions of $M$, see \cite[Chapter 7.2]{oxley2006matroid}. Hence, for each modular cut $\mathcal{M}$ of $M$ we can associate a single-element extension $M +_\mathcal{M} e$ of $M$, where $e$ is an element not in the ground set of $M$, whose lattice of flats fall into the three following disjoint classes (see \cite[Corollary 7.2.]{oxley2006matroid}):
\begin{enumerate}
    \item[(i)] flats $F$ of $M$ that are not in $\mathcal{M}$;
    \item[(ii)] sets $F \cup e$, where $F$ is a flat of $M$ that is in $\mathcal{M}$;
    \item[(iii)] sets $F \cup e$, where $F$ is a flat of $M$ that is not in $\mathcal{M}$ and $F$ is not contained in a member $F'$ of $\mathcal{M}$ of rank $r(F) +1$.
\end{enumerate}

Moreover, we can use this construction to determine all matroids: any matroid $M$ is obtained from a uniform matroid $U_n^n$ by a sequence of single-element extensions.

For example, consider the uniform matroid $U_3^3$. Then, $\mathcal{M}_1 = [[1],[3]]$ and $\mathcal{M}_2 = [[2],[3]]$ are modular cuts. The lattices of flats of $U_3^3$, $U_3^3 +_{\mathcal{M}_1} 4$ and $U_3^3 +_{\mathcal{M}_2} 4$ are given as follows:

\begin{center}
    \includegraphics[scale=0.79]{FPSAC.png}
\end{center}

\begin{lemma}
\label{thr5.1}
    Conjecture~\ref{conj1} is true for all matroids of ranks 1, 2 or 3.
\end{lemma}
\begin{proof}
    The result is trivial for matroids of ranks 1 and 2. For matroids of rank 3, its lattice of flats is given by
    \begin{center}
        \begin{tikzpicture}[line cap=round,line join=round,x=1.0cm,y=1.0cm]
            \clip(-1,-1.5) rectangle (1.0,2.0);
            \begin{scriptsize}
                \draw[color=blue] (0,1.6) node {$\hat{1}$};
                \draw [fill=blue] (0.,1.3) circle (2.5pt);
                \draw [line width=2.pt] (0,1.2)-- (0,0.9);
                \draw[color=blue] (0,0.7) node {2-flats};
                \draw [line width=2.pt] (0,0.4)-- (0,0.1);
                \draw[color=blue] (0,-0.1) node {1-flats};
                \draw [line width=2.pt] (0,-0.3)-- (0,-0.6);
                \draw [fill=blue] (0.,-0.6) circle (2.5pt);
                \draw[color=blue] (0,-0.9) node {$\hat{0}$};
            \end{scriptsize}
        \end{tikzpicture}
    \end{center}
    and, hence, its chain polynomial is $c_\mathcal{L}(t) = [1 + (m_1 + m_2)t + et^2](1+t)^2$, where $m_i$ is the number of $i$-flats and $e$ is the number of edges between 1-flats and 2-flats. Since $e \leq m_1 m_2$, then $c_\mathcal{L}(t)$ is real-rooted.
\end{proof}

Now, consider uniform matroids $U^n_n$, $n \geq 4$. The lattice of flats of $\mathcal{M}$ is $B_n$. So, if $\mathcal{M}$ is a modular cut of $U^n_n$ (and, in general, a modular cut of $U^r_n$), then $\mathcal{M} = \emptyset$ or $\mathcal{M} = [X, [n]]$, where $X \subseteq [n]$. Hence, every flat of the lattice of flats of $U^n_n +_\mathcal{M} \{ n+1 \}$ fall into one of the following disjoint classes:
\begin{enumerate}
    \item [(i)] $F \subset \{1, \ldots, n, n+1\}$ such that $\{1, \ldots, m, n+1 \}$ is not a subset of $F$. In this case, the rank of $F$ is $|F|$;
    \item [(ii)] $F \subset \{1, \ldots, n, n+1\}$ such that $\{1, \ldots, m, n+1\} \subseteq F$. In this case, the rank of $F$ is $|F| - 1$.
\end{enumerate}

%Recall that the \textit{direct product} of the posets $(X_1, \leq_1), \ldots, (X_n, \leq_n)$ is the poset $(X, \leq)$, where
%$$
%X = X_1 \times \cdots \times X_n
%$$
%and
%$$
%(x_1, \ldots, x_n) \leq (y_1, \ldots, y_n) \Leftrightarrow x_i \leq_i y_i, \text{ } i=1, \ldots, n.
%$$

It follows that $U^n_n +_\mathcal{M} \{ n+1 \}$ is isomorphic to the direct product $U^m_{m+1} \times U_{n-m}^{n-m}$. 

\begin{lemma}\cite[Theorem 7.6]{branden2015unimodality}
\label{lemma1}
    If all zeros of $\mathcal{E}(f)$ and $\mathcal{E}(g)$ lie in the interval $[-1,0]$, then so does $\mathcal{E}(fg)$.
\end{lemma}

\begin{lemma}
\label{lemma2}
    Let $P$ and $Q$ be two posets with a least and a greatest element such that $|P|, |Q| \geq 2$, and define
    $$
        \hat{c}_P(t) = \frac t {(1+t)^2} \cdot c_P(t).
    $$
    Then
    $$
        \hat{c}_{P \times Q} = \hat{c}_{P} \diamond \hat{c}_{Q} \coloneqq \mathcal{E} (\mathcal{E}^{-1}(\hat{c}_{P}) \mathcal{E}^{-1}(\hat{c}_{Q})).
    $$
\end{lemma}
\begin{proof}
    Omitted in the long abstract.
\end{proof}

\begin{lemma}[\cite{branden2006linear}]
\label{lemma3}
    If
    $$
        f(x) = \sum_{k=0}^d h_k x_k (1+x)^{d-k}
    $$
    has $h_k \geq 0$ for all $0 \leq k \leq d$, then all zeros of $\mathcal{E}(f)$ are real, simple and located in $[-1,0]$. In particular, the $h$-polynomial of a Cohen-Macaulay poset is real-rooted.
\end{lemma}

Now, we can prove the following:

\begin{theorem}
    If the $h$-polynomials of the order complexes of the posets $P$ and $Q$ have nonnegative coefficients, then the chain polynomial of $P \times Q$ is real-rooted.
\end{theorem}
\begin{proof}
    It follows directly from Lemmas \ref{lemma3}, \ref{lemma1} and \ref{lemma2}.
\end{proof}

\begin{corollary}
\label{SEE-thr}
    The chain polynomial of $U^n_n +_\mathcal{M} \{ n+1 \}$ is real-rooted for any modular cut of $U^n_n$.
\end{corollary}

\begin{proof}
    As mentioned before, $U^n_n +_\mathcal{M} \{ n+1 \}$ is isomorphic to $U^m_{m+1} \times U_{n-m}^{n-m}$. So, by Lemma~\ref{lemma2},
    $$
        \hat{c}_{\mathcal{L} (U^n_n +_\mathcal{M} \{ n+1 \})} = \hat{c}_{\mathcal{L} (U^m_{m+1})} \diamond \hat{c}_{\mathcal{L} (U_{n-m}^{n-m})}.
    $$
    By Theorem~\ref{q-E}, $c_{\mathcal{L} (U^m_{m+1})}$ and $c_{\mathcal{L} (U_{n-m}^{n-m})}$ are real-rooted. So, by Lemma~\ref{lemma1}, $c_{\mathcal{L}(U^n_n +_\mathcal{M} \{ n+1 \})}$ is real-rooted.
\end{proof}

\begin{corollary}
\label{SEE-cor}
    The chain polynomial of $U^{n-1}_n +_\mathcal{M} \{ n+1 \}$ is real-rooted for any modular cut of $U^{n-1}_n$.
\end{corollary}
    
\begin{proof}
    First, observe that $U^{n-1}_n$ is a truncation of $U^n_n$ and that modular cuts of $U^{n-1}_n$ are also intervals. Let $\mathcal{\hat{M}} = [[m], [n]]$ be a modular cut of $U^{n-1}_n$ and $\mathcal{M} = [[m], [n]]$ be a modular cut of $U^n_n$. So $U^{n-1}_n +_\mathcal{\hat{M}} \{ n+1 \}$ is a truncation of $U^n_n +_\mathcal{M} \{ n+1 \}$. Hence, if $\mathcal{H}$ is the set of hyperplanes of $U^n_n +_\mathcal{M} \{ n+1 \} = U^m_{m+1} \times U_{n-m}^{n-m}$, then $H \in \mathcal{H}$ if and only if $H = A \times [n-m]$ or $H = [m+1] \times B$, where $A \in \mathcal{A}$ is a hyperplane of $U^m_{m+1}$ and $B \in \mathcal{B}$ is a hyperplane of $U_{n-m}^{n-m}$. So,
    \begin{align*}
        \hat{c}_{\mathcal{L}(U^{n-1}_n +_\mathcal{\hat{M}} \{ n+1 \})}(t) &= \hat{c}_{\mathcal{L}(U^n_n +_\mathcal{M} \{ n+1 \})}(t) - t \sum\limits_{H_i \in \mathcal{H}} \hat{c}_{[\emptyset, H_i]}(t) \\
                                                                    &= \hat{c}_{\mathcal{L} (U^m_{m+1})} \diamond \hat{c}_{\mathcal{L} (U_{n-m}^{n-m})}(t) - t \sum\limits_{A_i \in \mathcal{A}} \hat{c}_{[\emptyset, A_i \times [n-m]]}(t) \\
                                                                    & - t \sum\limits_{B_j \in \mathcal{B}} \hat{c}_{[\emptyset, [m+1] \times B_j]}(t) \\
                                                                    &= \hat{c}_{\mathcal{L} (U^m_{m+1})} \diamond \hat{c}_{\mathcal{L} (U_{n-m}^{n-m})}(t) - t \sum\limits_{A_i \in \mathcal{A}} \hat{c}_{[\emptyset, A_i]}(t) \diamond \hat{c}_{\mathcal{L} (U_{n-m}^{n-m})}(t) \\
                                                                    & - t \sum\limits_{B_j \in \mathcal{B}} \hat{c}_{\mathcal{L} (U_{m+1}^{m})}(t) \diamond \hat{c}_{[\emptyset, B_j]}(t).
    \end{align*}
    Since $\hat{c}_{[\emptyset, A_i]}(t) \preceq \hat{c}_{\mathcal{L} (U^m_{m+1})}(t)$ for all $A_i \in \mathcal{A}$ and $\hat{c}_{[\emptyset, B_j]}(t) \preceq \hat{c}_{\mathcal{L} (U_{n-m}^{n-m})}(t)$ for all $B_j \in \mathcal{B}$,  
    $$
        \hat{c}_{[\emptyset, A_i \times [n-m]]}(t) \preceq \hat{c}_{\mathcal{L} (U^m_{m+1})} \diamond \hat{c}_{\mathcal{L} (U_{n-m}^{n-m})}(t), \text{ for all } A_i \in \mathcal{A}
    $$
    and
    $$
        \hat{c}_{[\emptyset, [m+1] \times B_j]}(t) \preceq \hat{c}_{\mathcal{L} (U^m_{m+1})} \diamond \hat{c}_{\mathcal{L} (U_{n-m}^{n-m})}(t), \text{ for all } B_j \in \mathcal{B}.
    $$
    by \cite[Theorem 3]{branden2004operators}. Hence $\hat{c}_{\mathcal{L}(U^{n-1}_n +_\mathcal{\hat{M}} \{ n+1 \})}(t)$ is real-rooted.
\end{proof}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography
\end{document}
