\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram}
\OneNumberAllTheorems
%\usepackage{bbm}
\DeclarePairedDelimiter\abs{\lvert}{\rvert}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%special letters
%blackboardboldface
\newcommand{\0}{\mathbf{0}}
\newcommand{\T}{\intercal} % T for transpose
%\newcommand{\kk}{\mathbbm{k}}
\newcommand{\kk}{\Bbbk}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
%calligraphic
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{T}}
%boldface
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfL}{\mathbf{L}}
%\fraktur
\newcommand{\frC}{\mathfrak{C}}
%matroids
\newcommand{\matroid}[1]{M(#1)}
\newcommand{\dual}[1]{{#1}^{*}} % dual matroid
\newcommand{\dualM}{\dual{M}} % dual to M
\newcommand{\rank}[1]{r_{#1}} % matroid rank function
\newcommand{\rankdual}[1]{\rank{}^*} % dual matroid rank
\newcommand{\rankdualM}{\rankdual{M}} % rank of M dual
\newcommand{\tutte}[1]{\cT_{#1}} % tutte polynomial of #1
\DeclareMathOperator{\im}{Im} % image of homomorphism
\DeclareMathOperator{\Hilb}{Hilb} % Hilbert series
% transversal matroids
\newcommand{\repn}[1]{V({#1})} % representation of transversal matroid
\newcommand{\A}[1]{A({#1})} % elements of S contained in A_{#1}
\newcommand{\nnZ}{\ZZ_{\geq 0}} % nonnegative ingegers
\newcommand{\nnZd}{\nnZ^d} % nonnegative d-tuples of integers
\newcommand{\nnR}{\RR_{\geq 0}} % nonnegative reals
\newcommand{\nnRd}{\nnR^d} % nonnegative d-orthant
\newcommand{\multicomplex}[1]{\frM_{#1}} %multicomplex
\newcommand{\multicomplexA}{\multicomplex{A}} % multicomplex of M-parking functions associated to presentation A
\newcommand{\nonparking}[1]{\mathcal{N}(#1)} % monomial ideal of non-M-parking functions
\newcommand{\submod}[1]{f_{#1}} % submodular function defined by composition of |A(J)| with rank of dual matroid
\newcommand{\PM}[1]{\frC({#1})} % polymatroid
\newcommand{\PMA}{\PM{A}} % polymatroid associated to set system A
\newcommand{\Oh}[1]{\mathfrak{O}(A)} % Oh's generalized permutahedron
%algebra
\newcommand{\polyyn}{\kk[y_1,\ldots,y_n]}
\newcommand{\polyx}{\kk\left[x_j\colon j\in {[d]}\right]} % polynomial ring in x_1,...x_d
\newcommand{\polyy}{\kk\left[y_s\colon s\in S\right]} % polynomial ring in y_1,...y_S
\newcommand{\SRI}[1]{\cS(#1)} % stanley reisner ideal
\newcommand{\pIdeal}[1]{\cI(#1)} % power ideal
\newcommand{\pAlgebra}[1]{\cP(#1)} % power algebra
\newcommand{\sfalgebra}[1]{\cF_{#1}} % square free algebra
\newcommand{\row}{r} % linear form defined by a row of a matrix
\newcommand{\ringH}[1]{\Phi_{#1}}
\newcommand{\cIdeal}[1]{\cJ(#1)} % cocircuit ideal
\newcommand{\cAlgebra}[1]{\cD(#1)} % algebra defined by the cocircuit ideal
\newcommand{\lPower}[1]{{\ell_{#1}}^{\rho_{#1}}} % power of linear form defining hyperplane
\newcommand{\lPowerH}{\lPower{H}} % ditto
\newcommand{\gl}[2]{\bfG\bfL_{#1}(#2)}
\newcommand{\glk}[1]{\gl{#1}{\kk}}
\newcommand{\glnk}{\glk{n}}
% geometry/simplicial complexes
\DeclareMathOperator{\Span}{span} % linear span
% definitions color
\definecolor{darkblue}{rgb}{0,0,0.7} % darkblue color
\newcommand{\darkblue}{\color{darkblue}} % darkblue command
\newcommand{\defn}[1]{\emph{\darkblue #1}} % emphasis of a definition
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur
\author{\firstname{Camilo} \lastname{Sarmiento}}
\address{Universidad del Norte\\
Departamento de Matem\'aticas y Estad\'istica\\
Barranquilla\\
Colombia}
\dedicatory{To the memory of Abdelrhman Elkasapy\\(17.12.1983--13.01.2017)}
\email{csarmiento10@gmail.com}
%%%%% Sujet
\keywords{transversal matroids, power ideals, polymatroids, parking functions}
\subjclass{05E40, 05E45, 05B35, 52B40}
%%%%% Gestion
\DOI{10.5802/alco.57}
\datereceived{2018-05-28}
\daterevised{2018-12-13}
\dateaccepted{2018-12-25}
%%%%% Titre et résumé
\title[On power ideals of transversal matroids]{On power ideals of transversal matroids and their ``parking functions''}
\begin{abstract}
To a vector configuration one can associate a polynomial ideal generated by powers of linear forms, known as a power ideal, which exhibits many combinatorial features of the matroid underlying the configuration.
In this note we observe that certain power ideals associated to transversal matroids are, somewhat unexpectedly, monomial. Moreover, the (monomial) basis elements of the quotient ring defined by such a power ideal can be naturally identified with the lattice points of a remarkable convex polytope: a polymatroid, also known as generalized permutohedron. We dub the exponent vectors of these monomial basis elements ``parking functions'' of the corresponding transversal matroid.
We highlight the connection between our investigation and Stanley--Reisner theory, and relate our findings to Stanley's conjectured necessary condition on matroid $h$-vectors.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
Polynomial ideals generated by powers of linear forms, often called \defn{power ideals}, appear in a number of mathematical contexts (see~\cite{AP10} and the references therein.)
This paper is concerned with a family of power ideals associated to a vector configuration. These were originally introduced in the context of multivariate approximation theory, mainly as a tool to study the space spanned by the local polynomial pieces of a box spline and their derivatives~\cite{dBDR91}.
Such power ideals are known to strongly reflect combinatorial aspects of the underlying vector configuration (see e.g. Theorem~\ref{thm:tutteHilbert} below), and have generated renewed interest in recent years, owing to their rich geometry and combinatorics and to their relevance in subjects as varied as the cohomology of homogeneous manifolds and Cox rings (see~\cite{AP10, DP11, HR11} and the references therein.)
We delay a precise definition until Section~\ref{sec:pIdeals}.
In~\cite{PS04} Postnikov and Shapiro introduced and investigated a class of power ideals associated to graphs.
Their definition essentially coincides with the one from multivariate approximation theory, although they were apparently unaware of such developments.
Alongside they introduced a monomial ideal associated to a graph, and showed that both power and monomial ideals of a graph define graded quotient rings with the same Hilbert function, and vector space dimension equal to the number of spanning trees of the graph.
Remarkably, the standard basis elements modulo the monomial ideal also form a basis for the quotient ring defined by the power ideal; their exponent vectors received the name ``$G$-parking functions'', as they specialize to the renowned parking functions.
$G$-parking functions turn out to be intimately related to the chip-firing game on a graph, and have attracted much attention (see~\cite{BS13} and the references therein).
The motivation for this note is an attempt of the author to extend the methods of Postnikov and Shapiro beyond graphs.
For this purpose, an obvious candidate to contemplate is a class of vector configurations associated to transversal matroids (see Section~\ref{sec:transmats} for definitions).
Thus our subject matter is a family of power ideals associated to transversal matroids, with a focus on monomial bases for the quotient rings they define.
Our first main result is that, surprisingly, no monomial basis for such a power ideal needs to be constructed, in the first place: the power ideals we consider are monomial (Theorem~\ref{thm:powerismono}). A priori, this property is rather unexpected for power ideals of arbitrary vector configurations, as their generators comprise powers of linear forms of varying degrees and supports. By way of example, the smallest graph whose corresponding power ideal is not monomial is the graph with 4 vertices and 5 edges (see~\cite[Example~3.2]{PS04}).
Secondly, the exponent vectors of the standard monomials modulo such a (monomial) power ideal can be readily identified with the lattice points of a polymatroid (a.k.a. generalized permutahedron), a convex polytope defined by a submodular function (Corollary~\ref{cor:polymatroidmonomials}).
We illustrate both results in Example~\ref{ex:pIdealTransMat} below.
By a (largely ad hoc) parking interpretation of such nonnegative integer vectors, and in analogy with the $G$-parking functions of Postnikov and Shapiro, we have dubbed them ``$A$-parking functions'' associated to the set system $A$ defining the transversal matroid (see Remark~\ref{rem:Parking}).
We emphasize however that a chip-firing-like interpretation of $A$-parking functions is missing. This stands in contrast with $G$-parking functions, which arise as \emph{superstable configurations} in the chip-firing terminology.
\begin{exam}
\label{ex:pIdealTransMat}
Let $\kk=\RR$ and $V\subset \RR^3$ be the vector configuration consisting of the columns of the following matrix:
\[
\begin{pmatrix}1&
{2}&
0&
0&
0&
0&
{7}&
0&
{9}&
{10}\\
0&
{4}&
0&
0&
0&
{36}&
{49}&
{64}&
0&
0\\
0&
{8}&
{27}&
{64}&
{125}&
{216}&
0&
0&
0&
0\\
\end{pmatrix}.
\]
Such vector configuration gives a representation for the transversal matroid defined by the set system $A=(\{1,2,7,9,10\},\{2,6,7,8\},\{2,3,4,5,6\})$. Its corresponding power ideal $\pIdeal{V}\subset\RR[x_1,x_2,x_3]$ is generated by the following powers of linear forms:
\begin{gather*}
({-2 {x}_{2}+{x}_{3}})^{6}, ({{x}_{2}})^{4}, ({-6 {x}_{2}+{x}_{3}})^{6}, ({{x}_{3}})^{5},
({-2 {x}_{1}+{x}_{2}})^{6}, ({-8 {x}_{1}+6 {x}_{2}-{x}_{3}})^{8},\\ ({-28 {x}_{1}+4 {x}_{2}+5
{x}_{3}})^{8}, ({-4 {x}_{1}+{x}_{3}})^{8}, ({{x}_{1}})^{5},
({-7 {x}_{1}+{x}_{2}})^{6}, ({-42
{x}_{1}+6 {x}_{2}-{x}_{3}})^{8}.
\end{gather*}
A Gr\"obner basis computation with Macaulay2~\cite{M2} shows that $\pIdeal{V}$ is in fact monomial, since it is generated by the following monomials:
\begin{equation*}
{x}_{2}^{4},\ {x}_{3}^{5},\ {x}_{1}^{5},\ {x}_{2}^{2} {x}_{3}^{4},\ {x}_{2}^{3}
{x}_{3}^{3},\ {x}_{1}^{3} {x}_{2}^{3},\ {x}_{1}^{4} {x}_{2}^{2},\ {x}_{1}^{3}
{x}_{2} {x}_{3}^{4},\ {x}_{1}^{4} {x}_{3}^{4},\ {x}_{1}^{3} {x}_{2}^{2}
{x}_{3}^{3},\ {x}_{1}^{4} {x}_{2} {x}_{3}^{3}.
\end{equation*}
There are 70 monomials modulo $\pIdeal{V}$, whose exponent vectors are the lattice points of the following polytope:
\[ \begin{aligned} \PMA:=\left\{ (q_1,q_2,q_3)^\T\in\nnR^3 \colon \begin{array}{l} q_1\leq 4,\ q_2\leq 3,\ q_3\leq 4,\\ q_1+q_2\leq5,\ q_1+q_3\leq 7,\ q_2+q_3\leq 5,\\ q_1+q_2+q_3\leq 7 \end{array} \right\} \end{aligned} \]%\[
%\begin{aligned}
%\PMA:=\left\{(q_1,q_2,q_3)^\T\in\nnR^3 \right.\colon & q_1\leq 4,\ q_2\leq 3,\ q_3\leq 4,\\ & %q_1+q_2\leq5,\ q_1+q_3\leq 7,\ q_2+q_3\leq 5,\\ &\left. q_1+q_2+q_3\leq 7\right\},
%\end{aligned}
%\]
and are depicted in Figure~\ref{fig:Polymatroid}. A 3d model of this polytope, generated with Polymake~\cite{polymake:2000}, is available as an ancillary PDF file for the arXiv version.
\begin{figure}[htbp]
\begin{minipage}[c]{0.3\textwidth}
\centering
\includegraphics[width=\textwidth]{173-figures/aPolymatroidInkscape}
\end{minipage}%
\begin{minipage}[c]{0.6\textwidth}
\caption{Polytope whose lattice points correspond to the exponent vectors of the standard monomial basis modulo the power ideal $\pIdeal{V}$ from Example~\ref{ex:pIdealTransMat}. Exponents of different degrees are shown in different colors to aid in visualization.}
\label{fig:Polymatroid}
\end{minipage}
\end{figure}
\end{exam}
Key to our results are the classical Hall's marriage theorem, its generalization to independent transversals of a set system by Rado, and a generalization of the latter to polymatroids by McDiarmid. We refer the reader to the books of Lov\'asz and Plummer~\cite{LP86} and of Schrijver~\cite{Schr03} for a comprehensive account of these topics.
The power ideal associated to a vector configuration $V$ defines a graded ring whose Hilbert function is known to coincide with the $h$-vector of the (abstract) simplicial complex of subsets $T$ of~$V$ such that $\Span(V\setminus T)=\Span(V)$ (cf. Remark~\ref{rem:conjStanley}).
In this light, we believe that power ideals of vector configurations are most naturally regarded in the framework of Stanley--Reisner theory of matroids; we expand on this point of view in Section~\ref{sec:SRtheory}. In particular, our findings imply a proof of Stanley's conjecture for the class of $h$-vectors of cotransversal matroids, different (but cognate, after all) from an earlier one by Oh~\cite{Oh13}. This connection, and the relation with Oh's work, is spelled out in Remark~\ref{rem:conjStanley}.
The outline of the paper is as follows. Sections~\ref{sec:pIdeals} and~\ref{sec:transmats} collect some elementary notions and results concerning vector configurations and transversal matroids, respectively.
Section~\ref{sec:mainresult} presents our main results mentioned above, namely Theorem~\ref{thm:powerismono} and Corollary~\ref{cor:polymatroidmonomials}. Finally, Section~\ref{sec:SRtheory} is a brief excursion into Stanley--Reisner theory of matroids, intended to frame our investigation on power ideals.
\begin{nota*}
In this note we only consider finite sets and collections, so we will drop explicit mention of the hypothesis ``finite'' throughout. Given a positive integer $n$, we use the notation $[n]:=\{1,\ldots,n\}$. Given a set $S$, $|S|$ denotes the cardinality of $S$, and $2^S$ stands for the power set of $S$, that is, the set of subsets of $S$. The set of nonnegative reals is denoted by $\nnR$ and the set of nonnegative integers by $\nnZ$. Given an element $q=(q_1,\ldots,q_d)\in\nnZ^d$, we write $x^q$ for the monomial in $\polyx$ with \defn{exponent vector} $q$, that is, $x^q:=\prod_{j\in[d]}x_j^{q_j}$.
\end{nota*}
\section{Vector configurations, their matroids and their power ideals}
\label{sec:pIdeals}
Let $\kk$ be a field. A \defn{vector configuration} over $\kk$ is a labeled collection $V=(v_s\colon s\in S)$ of (not necessarily distinct) vectors in $\kk^d$, for some $d\in\nnZ$.
Such a vector configuration defines a \defn{matroid} $\matroid{V}$ on the ground set $S$, whose structure is determined by its \defn{rank function} $\rank{\matroid{V}}\colon 2^S \to \nnZ$, defined by the rule:
\[
T \mapsto \dim_\kk\Span(v_s\colon s\in T),\quad \text{for }T\subseteq S.
\]
Matroids arising from vector configurations in such a way are said to be \defn{representable \textup{(}over~$\kk$\textup{)}}.
We largely adopt matroid theory notation from Oxley's book~\cite{Oxl11}, to which we refer the reader for undefined terminology.
Aspects relating to the \defn{Tutte polynomial} can be consulted in~\cite{Bjo92}.
\emph{Caveat:} Since this note is exclusively concerned with representable matroids, we will often commit the following abuse of notation. In referring to the groundset of a matroid $\matroid{V}$ (or to subsets or elements thereof), we will interchangeably mean the label set $S$ or the vector collection $V$ (or subsets or elements thereof).
In the following, we write $M:=M(V)$ and $r:=\rank{\matroid{V}}$, and assume without loss of generality that $\Span(V)=\kk^d$, so the \defn{rank} of $M$ equals $d$. Let $H$ be a \defn{hyperplane} of\footnote{By the caveat, $H$ may thus refer to a subset of $V$ or to the corresponding index subset of $S$.} $M$, \defn{$\ell_H$} be any linear form vanishing on $\Span(H)$ and \defn{$\rho_H:=|V\setminus H|$}.
\begin{defi}
The \defn{power ideal of $V$} is the following ideal of $\polyx$:
\begin{equation*}
\pIdeal{V}:= \left(\lPowerH\colon H\text{ hyperplane of }V\right).
\end{equation*}
The \defn{power algebra of $V$} is the quotient $\pAlgebra{V}:=\polyx/\pIdeal{V}$.
\end{defi}
Clearly, $\pAlgebra{V}$ is a graded $\kk$-algebra. We write $\pAlgebra{V}_k$ for its \defn{$k$-th graded component}, so that $\pAlgebra{V}=\bigoplus_{k\in\nnZ} \pAlgebra{V}_k$, and $\Hilb(\pAlgebra{V};z):=\sum_{k\in\nnZ }\dim_\kk \pAlgebra{V}_kz^k$ for its \defn{Hilbert series}.
Many enumerative invariants of a matroid $M$ arise as specializations of the Tutte polynomial $\tutte{M}(x,y)$. It occupies a special position in the present context because of the following theorem, which illustrates the combinatorial nature of power ideals.
\begin{theorem}[\cite{AP10,dBDR91,HR11}]
\label{thm:tutteHilbert}
$\displaystyle\Hilb(\pAlgebra{V};z):=z^{|S|-d}\tutte{M}\left(1,{z}^{-1}\right).$
\end{theorem}
Following Ardila~\cite[Chapter~4]{Ard03} and Postnikov and Shapiro~\cite[Section~9]{PS04}, the power ideal of $V$ can be presented as the ideal of relations of a certain ``squarefree algebra''.
Concretely, denote by $\sfalgebra{V}$ the quotient of $\polyy$ by the relations:
\begin{align*}
y_s^2\quad &\text{for }s\in S,\\
\prod_{s\in T}y_s \quad &\text{for }T\subseteq S\text{ cocircuit of }M,
\end{align*}
and consider the $\kk$-algebra homomorphism $\ringH{V}\colon \polyx\to\sfalgebra{V}$ defined by:
\[
\ringH{V}\colon x_j \mapsto \row_j:=\sum_{s\in S}(v_s)_jy_s,
\]
where $(v_s)_j$ denotes the $j$-th coordinate of vector $v_s\in V$.
\begin{lemma}[{\cite[Corollary~10.5]{PS04}}]
\label{lem:powerkernel}
$\displaystyle
\ker \ringH{V}=\pIdeal{V}.
$
\end{lemma}
We postpone the proof of Lemma~\ref{lem:powerkernel} to Section~\ref{sec:SRtheory}, to highlight the relation between power ideals and Stanley--Reisner theory.
\section{Transversal matroids and their vector configurations}
\label{sec:transmats}
Let $A$ be a \defn{set system} on a ground set $S$, that is, a labeled collection of nonempty subsets of a set~$S$.
We use the notation $A=(\A{j}\colon j \in [d])$, where $d$ is a positive integer and $\A{j}\subseteq S$ for $j\in [d]:=\{1,\ldots, d\}$. Given $J\subseteq [d]$ we write $\A{J}:=\bigcup_{j\in J} \A{j}$.
A \defn{partial transversal} of $A$ is a subset $T\subseteq S$ whose elements belong to distinct members of $A$, that is, such that $T=\{s_j\colon j\in J\}$ for some $J\subseteq [d]$, where $s_j\in \A{j}$ for each $j\in J$.
The partial transversals of $A$ constitute the independent sets of a matroid $\matroid{A}$ on the ground set $S$~\cite{Bru87}.
Matroids arising from set systems in such a way are known as \defn{transversal matroids}\footnote{Transversal matroids can be equivalently defined in terms of matchings on bipartite graphs (see e.g.~\cite[Section 1.6]{Oxl11}). We opt for the set system point of view throughout.}.
By removing subsets in $A$ if necessary, we may assume in the following that the rank of $\matroid{A}$ equals $d$; that this entails no loss of generality follows from~\cite[Lemma~5.1.1]{Bru87}.
It is well known that every transversal matroid is representable over a \emph{large enough} field. Let $\kk$ be such a field, and for every $j\in[d]$ and $s\in S$ define scalars $v(s,j)\in \kk$ such that $v(s,j)=0$ if and only if $s\notin \A{j}$, and the nonzero $v(s,j)$'s are \emph{sufficiently generic}.
For every $s\in S$ define the vector $v_s:=(v(s,j)\colon j\in [d])^\T\in\RR^d$.
The resulting vector configuration $\repn{A}:=(v_s\colon s\in S)$ represents $\matroid{A}$ over $\RR$, that is, $\matroid{\repn{A}}=\matroid{A}$~\cite[Theorem~5.4.7]{Bru87}.
We refer the reader to~\cite{Atk72} or~\cite[Section~5.4]{Bru87} for further details on this construction. %
Underlying this representation of transversal matroids is the following existence statement of partial transversals in the case when $|S|=d$. For future reference, we have supplemented it with the celebrated \defn{Hall's marriage theorem}, which asserts the equivalence of statements~\ref{it:transv} and~\ref{it:hall} below.
\begin{theorem}[{\cite[Theorem~8.2.1]{LP86}}]
\label{thm:hallsthm}
Let $A=(\A{j}\colon j \in [d])$ be a set system with $|S|=d$. Denote by $\det(\repn{A})$ the determinant of the $d\times d$ matrix whose columns are given by the vectors in $\repn{A}$. The following statements are equivalent:
\begin{enumerate}[label=(\alph*),ref=\thelemm(\alph*)]
\item \label{it:transv} $A$ has a partial transversal of size $d$.
\item \label{it:nonzerodet} $\det(\repn{A})\neq 0$.
\item \label{it:hall} $|\A{J}|\geq |J|$ for every $J\subseteq [d]$.
\end{enumerate}
\end{theorem}
\section{Main result}
\label{sec:mainresult}
To present our main result, we fix a rank-$d$ set system $A=(\A{j}\colon j \in [d])$ on $S$, along with a representation $\repn{A}:=(v_s\colon s\in S)\subset\kk^d$, as constructed in Section~\ref{sec:transmats}.
To lighten notation, we set $V:=\repn{A}$, $M:=\matroid{A}=\matroid{\repn{A}}$. Let $\dual{M}$ denote the rank-$(|S|-d)$ matroid on $S$ dual to $M$, and $\rankdual{}$ be its rank function.
\begin{theorem}
\label{thm:powerismono}
The power ideal $\pIdeal{V}\subset\polyx$ is a monomial ideal.
\end{theorem}
Our proof of Theorem~\ref{thm:powerismono} proceeds directly, by identifying the monomial ideal $\nonparking{A}\subset\polyx$ that $\pIdeal{V}$ is equal to.
To this end, we introduce a set function $\submod{A}\colon 2^{[d]}\to\nnZ$ defined by the rule:
\begin{align*}
J\mapsto \rankdualM(A(J)),\quad\text{ for }J\subseteq [d].
\end{align*}
It is not difficult to see that $\submod{A}(I\cap J)+\submod{A}(I\cup J)\leq \submod{A}(I)+\submod{A}(J)$ holds for every $I,J\subseteq [d]$, so that $\submod{A}$ is a \defn{submodular function} (see e.g.~\cite[Section~44.1a]{Schr03}). Like every submodular function, $\submod{A}$ defines a convex polytope known as a \defn{polymatroid}.
\begin{defi}
The \defn{parking polymatroid} of $A$ is the polymatroid $\PMA$ defined by $\submod{A}$, that is, the convex polytope in $\RR^d$ defined as follows:
\[
\PMA:=\left\{q\in\nnRd \colon \sum_{j\in J} q_j \leq \submod{A}(J)\text{ for every }J\subseteq [d]\right\}.
\]
\end{defi}
\begin{defi}
The \defn{parking ideal} of $A$ is the ideal $\nonparking{A}$ of $\polyx$ defined by the monomials $\{x^q\colon q\in \nnZd,\ q\notin \PMA\}$.
\end{defi}
\begin{rema}
\label{rem:Parking}
It is natural to consider the following ``parking'' interpretation of the lattice points of $\PMA$.
A parking lot offers a set $S$ of labeled parking spots for cars of $d$ different brands, subject to the peculiar rule that cars of brand $j\in [d]$ may only occupy parking spots $\A{j}\subseteq S$.
A number of cars totalling $q_i+1>0$ cars of brand $i$, for $i\in[d]$, arrive to park in this parking lot.
We say that the tuple $q=(q_1,\ldots,q_d)\in\nnZd$ is an \defn{``$A$-parking function''} if all the cars manage to park while observing the parking lot's rule.
To relate this to the polymatroid $\PMA$, let $A=(\A{j}\colon j \in [d])$ be the set system defined by the parking rule (we assume that $A$ has rank $d$; that is, we neglect car brands which may not park at all.)
Notice that if $q\in\nnZd$ is an ``$A$-parking function'', then a collection of cars comprising $q_i\geq 0$ cars of brand $i$, for $i\in[d]$, can park in a subset $T\subset S$ of the parking spots, in such a way that at least one car of each brand can still find a parking spot among the remaining ones $S\setminus T$.
In other words, $S\setminus T$ contains a partial transversal of size $d$ or, equivalently, $T$ is an independent set of $\dualM$.
Thus $q\in\nnZd$ is an ``$A$-parking function'' if and only if $A$ has a $q$-transversal that is independent in $\dualM$, where a \defn{$q$-transversal of $A$} is defined as a subset $T=T_1\cup\ldots\cup T_d\subseteq S$, such that $T_j\subseteq \A{j}$, $|T_j|=q_j$ and $T_j\cap T_{j'}=\emptyset$ for $j,j' \in [d]$ distinct.
By Rado's theorem for polymatroids (see~\cite[Section~44.6g]{Schr03}), $A$ has a $q$-transversal that is independent in $\dualM$ if and only if $q\in\PMA$, that is, \mbox{if and only~if}
\[
\sum_{j\in J}q_j\leq \rankdualM\left( \A{J}\right)=\submod{A}(J), \quad \text{holds for all }J\subseteq[d].
\]
This parking analogy was distilled in the course of proving Proposition~\ref{pro:qtransv}.
Together with the work of Postnikov and Shapiro on power ideals and parking functions associated to graphs~\cite{PS04}, it motivated the chosen names for $\PMA$ and $\nonparking{A}$.
We should point out, however, that the term ``$A$-parking function'' is chiefly understood as a nickname, because a chip-firing-like interpretation for it is currently unavailable.
It is a prominent problem in combinatorics to find variations and higher dimensional analogs of the chip-firing game on graphs.
\end{rema}
\begin{exam}
To illustrate the parking interpretation in Remark~\ref{rem:Parking} above, let $A=(\{1,2,7,9,10\},\{2,6,7,8\},\{2,3,4,5,6\})$ as in Example~\ref{ex:pIdealTransMat}. Then $q=(3,1,3)\in\nnZ^3$ is an $A$-parking function. For instance, 4 cars of brand 1 could park in lots 1, 2, 9 and 10, 2 cars of brand 2 could park in lots 7 and 8, and 4 cars of brand 3 could park lots 3, 4, 5 and 6. Accordingly, $\ringH{V}(x^q)=0$, as asserted in Proposition~\ref{pro:qtransv}.
\end{exam}
\begin{proposition}
$\pIdeal{V}\subseteq \nonparking{A}$.
\end{proposition}
\begin{proof}
Let $H\subset S$ be a hyperplane of $M$ and $\ell_H\in\polyx$ be an associated linear form defined as in Section~\ref{sec:pIdeals}.
Let $J\subseteq[d]$ be the subset of indices of the nonvanishing coefficients of $\ell_H$ and $q\in\nnZd$ be the exponent vector of a monomial in ${\ell_H}^{\rho_H}$.
We claim that $\sum_{j\in J}q_j>\submod{A}(J)$, so that $x^q\in\nonparking{A}$.
Assume $\Span(H)=\Span(\{v_{i_1},\ldots,v_{i_{d-1}}\})$ for some vectors $v_{i_1},\ldots,v_{i_{d-1}}\in V$. Then $\ell_H$ can be written as the determinant of the matrix with columns given by the vectors $v_{i_1},\ldots,v_{i_{d-1}}$ and the vector $(x_1,\ldots,x_d)^\T$:
\[
\ell_H=\det\begin{pmatrix}
v_{i_1} & \cdots & v_{i_{d-1}} & x_1 \\
\kern.6em\vline & & \kern.6em\vline & \vdots \\
\kern.6em\vline & &\kern.6em\vline & x_d
\end{pmatrix}\in\polyx,
\]
and by Theorem~\ref{thm:hallsthm} it follows that its $j$-th coefficient is nonzero if and only if the set system
$\left(\A{j'}\cap H\colon j'\in [d]\setminus\{j\}\right)$ has a partial transversal of size $d-1$.
By Hall's marriage theorem (cf. Theorem~\ref{thm:hallsthm}), this observation implies that $|J'|\leq|\A{J'}\cap H|$ whenever $J'\not\supseteq J$. Similarly, $|J|>|\A{J}\cap H|$ necessarily holds, because otherwise there would be some $j\in [d]\setminus J$ such that the set system $\left(\A{j'}\cap H\colon j'\in [d]\setminus\{j\}\right)$ has a partial transversal of size $d-1$, which contradicts the characterization of the vanishing coefficients of $\ell_H$. % to see this more evidently, think about the transposed set system. If J is a partial transversal, it can be extended to one of size d-1 containing J, which gives the contradiction
Now, since the $j$-th coefficient of $\ell_H$ vanishes whenever $j\notin J$, clearly $\ell_H(v_s)=0$ whenever $s\notin \A{J}$, and hence $S\setminus \A{J}\subseteq H$. Thus we find $|\A{J}|=|\A{J}\cap H|+|S\setminus H|=|\A{J}\cap H|+\rho_H$, which implies the inequality
\begin{equation}
\label{eq:hyperplane}
|\A{J}|<|J|+\sum_{j\in [d]}q_j=|J|+\sum_{j\in J}q_j.
\end{equation}
On the other hand, $\rankdual{}$ can be written in terms $\rank{}$ as follows (cf.~\cite[Proposition~2.1.9]{Oxl11}):
\[
\rankdualM(T)=\rank{}(S\setminus T)-\rank{}(S)+|T|\text{ for }T\subseteq S.
\]
Also, we know that the rank function of the transversal matroid defined by $A$ is given by (cf.~\cite[Proposition~4.2.3]{Bru87}):
\[
\rank{}(T)=\min \{|\A{J'}\cap T|+d-|J'|\colon J'\subseteq [d]\} \text{ for }T\subseteq S.
\]
Combining the first equality evaluated at $\A{J}$ with the second one evaluated at $S\setminus \A{J}$, we obtain the following inequality:
\begin{equation}
\label{eq:dualrank}
\rankdualM(\A{J})\leq |\A{J}|-|J|.
\end{equation}
Equations~\eqref{eq:hyperplane} and~\eqref{eq:dualrank} then yield our claim that $\sum_{j\in J}q_j>\rankdualM(\A{J})$.
\end{proof}
\begin{proposition}
\label{pro:qtransv}
$\nonparking{A}\subseteq \ker \ringH{V}$.
\end{proposition}
\begin{proof}
Let $q\in\nnZd$ be such that $x^q\in \nonparking{A}$. The squarefree monomials in the expansion of the image $\ringH{A}(x^q)\in \sfalgebra{V}$ can be seen as $q$-transversals of $A$, as defined in Remark~\ref{rem:Parking}. Since $q\notin \PMA$, no such $q$-transversal is independent in $\dualM$ or, equivalently, every such $q$-transversal is divisible by $\prod_{s\in T}y_s$ for some cocircuit $T$ of $M$. Thus $\ringH{A}(x^q)=0$.
\end{proof}
\begin{coro}
\label{cor:polymatroidmonomials}
$\{x^q\colon q\in\PMA\cap \nnZd\}$ forms a basis for $\pAlgebra{V}$.
\end{coro}
\section{Connection with Stanley--Reisner theory}
\label{sec:SRtheory}
Throughout this section, let $V=(v_s\colon s\in S)\subset \kk^d$ be a vector configuration which spans $\kk^d$ and $M=\matroid{V}$ be its rank-$d$ matroid.
As in~\cite[Chapter~4]{Ard03} and~\cite[Section~9]{PS04}, our proof of Lemma~\ref{lem:powerkernel} draws upon a vector space of polynomials associated to $V$ whose dimension can be calculated easily.
To introduce it, let $v_s(x):=\sum_{j\in [d]} (v_s)_j x_j\in\polyx$.
\begin{defi}
The \defn{cocircuit ideal of $V$} is following the ideal of $\polyx$:
\[
\cIdeal{V}=\left(\prod_{s\in T} v_s(x)\colon T\subseteq S\text{ cocircuit of }M\right)
\]
The \defn{cocircuit algebra of $V$} is the quotient $\cAlgebra{V}:=\polyx/\cIdeal{V}$.
\end{defi}
It is well-known that $\cAlgebra{V}$ has the same Hilbert series as $\pAlgebra{V}$ (see e.g.~\cite{Ber10,DM85,HR11}). We give a proof of this fact based on Theorem~\ref{thm:tutteHilbert} and on some elementary results in Stanley--Reisner theory. %We start by recalling the pertinent definitions.
\begin{defi}
The \defn{Stanley--Reisner ideal of $M$} is the ideal $\SRI{M}\subseteq \polyy$ generated by the monomials $\left\{\prod_{s\in T} y_s\right\}$, as $T\subseteq S$ ranges over the circuits of $M$.
The \defn{Stanley--Reisner ring of $M$} is the quotient ring $\kk[M]:=\polyy/\SRI{M}$.
\end{defi}
The following Lemma collects the preliminary results from Stanley--Reisner theory needed in the sequel. These are adaptations of more general statements to the particular context of representable matroids, relevant for our purposes.
\goodbreak
\begin{lemma}\label{lem:preliminarySR} \ \\*[-1.2em]
\begin{enumerate}[label=(\alph*), ref=\thelemm(\alph*)]
\item \label{it:lsop} The following $d$ linear forms are a linear system of parameters for $\kk[M]$ \textup{(\cite[Lemma~III.2.4]{Sta96})}:
\[
\theta_j:=\sum_{s\in S} (v_s)_jy_s,\quad j\in[d].
\]
\item $\Hilb{\kk[M]/(\theta_1,\ldots,\theta_d)}=z^d\tutte{M}(z^{-1},1)$ \textup{(\cite[Equation~(7.10) ff.]{Bjo92}, \cite[Theorem~A3]{DP08})}.
\item \label{it:spanningset} The quotient ring $\kk[M]/(\theta_1,\ldots,\theta_d)$ is spanned by the monomials $\{\prod_{s\in T}y_s\}$, where $T$ ranges over the independent sets of $M$ \textup{(\cite[Theorem~III.2.5~ff.]{Sta96})}.
\end{enumerate}
\end{lemma}
\begin{theorem}
\label{thm:isomorphism}
Let $W=\left(w_s\colon s\in S\right)\subset\kk^{n-d}$ be such that $\matroid{W}=\dual{M}$, and $\theta_i:=\sum_{s\in S}(w_s)_iy_s$, for $ i\in[n-d]$, be the corresponding linear system of parameters for $\kk[\dual{M}]$ from Lemma~\ref{it:lsop}. Then $\cAlgebra{V}\cong\kk[\dual{M}]/(\theta_1,\ldots,\theta_{n-d})$.
In particular, $\Hilb(\cAlgebra{V};z)=z^{n-d}\tutte{M}\left(1,{z}^{-1}\right)$, and $\cAlgebra{V}$ is spanned as a $\kk$-vector space by the products $
\{\prod_{s\in T} v_s(x)
\}$, where $T$ ranges over independent subsets of $\dualM$.
\end{theorem}
\begin{proof}
For notational convenience, let us first identify the common ground set $S$ of $M$ and $\dualM$ with $[n]$, and assume without loss of generality that the set $\{1,2,\ldots, d\}\subset[n]$ is a basis of $M$, so $\{d+1,\ldots,n\}$ is a basis of $\dualM$.
Let $g^{-1}\in\glnk$ be a transformation acting on $\polyyn$ as $g^{-1}\colon y_{d+i}\mapsto \theta_i$ for $1\leq i\leq n-d$. We choose $g^{-1}$ so that it has the following matrix form when expressed in the basis $\{y_1,\ldots,y_n\}$:
\[
g^{-1}=\begin{pmatrix}
B_1 & &\0_{d\times(n-d)}\\
w_1 & \ldots & w_n\\
\kern.6em\vline & & \kern.6em\vline%\\
%\kern.6em\vline & & \kern.6em\vline
\end{pmatrix}, \text{ so that }%
g=\begin{pmatrix}
v_1^\T \rule[.5ex]{3em}{0.4pt}\ & \0_{d\times(n-d)} \\
\vdots & \\
v_n^\T \rule[.5ex]{3em}{0.4pt}\ & B_2
\end{pmatrix} ,
\]
where $\0_{d\times(n-d)}$ denotes a $d\times(n-d)$ matrix of zeros, and $B_1\in\kk^{d\times d},B_2\in\kk^{(n-d)\times (n-d)}$ are suitable nonsingular matrices (which exist, by our assumption that $\{1,\ldots,d\}$ is a basis of $M$, and are uniquely determined). It follows that $g\cdot \kk[\dualM]/(\theta_1,\ldots,\theta_{n-d})\cong \cAlgebra{V}$, which establishes the isomorphism. The remaining statement follows by acting with $g$ on the spanning set in Lemma~\ref{it:spanningset}.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{lem:powerkernel}]
Clearly, the ideal of relations $\ker \ringH{V}\subset\polyx$ of the squarefree algebra $\im(\ringH{V})$ contains the power ideal $\pIdeal{V}$.
Indeed, the linear form $\ell_H$ associated to a hyperplane $H$ of $V$ maps to a linear form $\ringH{V}(\ell_H)\in\sfalgebra{V}$ with $s$-th coefficient equal to $\ell_H(v_s)$, which vanishes if and only if $v_s\in H$. It follows that the nonvanishing coefficients of $\ringH{V}(\ell_H)$ are indexed by elements in the complement of $H$ in $V$, which is a cocircuit $T$ of $V$. Since the only squarefree term of $\ringH{V}(\lPowerH)$ is a scalar multiple of $\prod_{s\in T}y_s$, we get $\lPowerH\in\ker \ringH{V}$. In particular, this implies the following inequality, understood coefficientwise:
\begin{equation}
\label{eq:hilbIneq}
\Hilb(\im(\ringH{V});z)\leq\Hilb(\pAlgebra{V};z).
\end{equation}
To prove the containment $\ker \ringH{V}\subseteq \pIdeal{V}$, we reproduce the linear-algebraic argument in~\cite[Chapter~4]{Ard03} and~\cite[Section~9]{PS04} to establish the equality of the dimensions of the graded components of $\im(\ringH{V})$ and $\cAlgebra{V}$. Then, by Theorems~\ref{thm:tutteHilbert} and~\ref{thm:isomorphism}, inequality~\eqref{eq:hilbIneq} holds with equality, so $\ker \ringH{V}= \pIdeal{V}$.
By Theorem~\ref{thm:isomorphism}, the $k$-th graded component $\cAlgebra{V}_k$ of $\cAlgebra{V}$ is spanned by the products
\[
\prod_{s\in T} v_s(x):=\prod_{s\in T} \left(\sum_{j\in [d]} (v_s)_j x_j\right),
\]
where $T\subseteq S$ ranges over subsets with $|T|=k$ and $\rank{}(S\setminus T)=d$. On the other hand, the $k$-th graded component $\im(\ringH{V})_k$ of $\im(\ringH{V})$ is spanned by the products
\[
%r^q=
\prod_{j\in [d]}r_j^{q_j}:=\prod_{j\in [d]} \left(\sum_{s\in S}(v_s)_jy_s\right)^{q_j},
\]
where $q\in\nnZd$ ranges over exponent vectors with $\sum_{j\in[d]}q_j=k$.
Given $T\subseteq S$ with $|T|=k$ and $\rank{}(S\setminus T)=d$, and $q\in\nnZd$ with $\sum_{j\in[d]}q_j=k$, denote by $\lambda_{T,q}\in\kk$ the coefficient of $x^q$ in the expansion of $\prod_{s\in T}v_s(x)$ and by $\mu_{T,q}\in\kk$ the coefficient of $\prod_{s\in T}y_s$ in the expansion of $\prod_{j\in [d]}r_j^{q_j}$. Then $\lambda_{T,q}=\mu_{T,q}$. The claim follows since the dimension of $\cAlgebra{V}_k$ (resp. $\im(\ringH{V})_k$) is given by the rank of the matrix with rows labeled by $\{T\subseteq S\colon |T|=k,\ \rank{}(S\setminus T)=d\}$, columns labeled by $\{q\in\nnZd\colon \sum_{j\in[d]}q_j=k\}$, and entries $\lambda_{T,q}$ (resp. $\mu_{T,q}$).
\end{proof}
\begin{rema}
\label{rem:conjStanley}
A remarkable result in Stanley--Reisner theory (cf.~\cite[Corollary~II.3.2]{Sta96})
is that the coefficients of the Hilbert series:
\[
\Hilb\left(\kk[\dualM]/(\theta_1,\ldots,\theta_{n-d});z\right)=h_0+h_1z+\cdots+h_{n-d}z^{n-d}
\]
are nonnegative integer which coincide with the entries of the \defn{$h$-vector} $(h_0,\ldots,h_{n-d})$ of the \defn{independence complex} of $\dualM$.
The study of numerical properties of $h$-vectors (such as log-concavity or unimodality) and of other combinatorial invariants of matroids is an active subject of research that has experienced major breakthroughs in recent years (e.g.~\cite{AHK18,Huh15}).
In this regard, Stanley conjectured in 1977 that $h$-vectors of matroids are \defn{pure $O$-sequences} (cf.~\cite[Conjecture~III.3.6]{Sta96}).
This means that given a matroid $h$-vector $(h_0,h_1,\ldots)$, there exists an order ideal of monomials $\cQ\subset\kk[x_1,\ldots,x_{h_1}]$ such that $\cQ$ contains exactly $h_k$ monomials of degree $k$, for $k\in\nnZ$, and its maximal monomials with respect to divisibility have all the same degree.
This conjecture has attracted considerable attention, but is only known to hold in few special cases (see~\cite{CKV14,Mer01,Oh13} and the references therein).
It is well-known (and not difficult to prove) that the integer points of a polymatroid can be regarded as the exponent vectors of a pure order ideal of monomials (see e.g.~\cite[Theorem~44.5]{Schr03}). Therefore, in light of Theorem~\ref{thm:tutteHilbert} and Lemma~\ref{lem:preliminarySR}, Corollary~\ref{cor:polymatroidmonomials} implies that Stanley's conjecture holds for the family of matroids dual to transversal matroids, known as \defn{strict gammoids} or \defn{cotransversal matroids}.
This fact had already been established by Oh in~\cite{Oh13}, and his proof also relied on associating a polymatroid to a set system. Interestingly, it turns out that Oh's polymatroid is almost equivalent to $\PMA$, even though our point of view is completely different.
To see this, associate to every element $s\in S$ the indicator function $g_s\colon 2^{[d]}\to \nnZ$, given by the rule:
\[
J\mapsto \begin{cases}
1& \text{if } s\in \A{J}\\
0& \text{else}
\end{cases},\quad \text{ for }J\subseteq [d],
\]
and note that the $g_s$'s are \defn{nondecreasing} submodular functions. Thus their sum $g_A:=\sum_{s\in S}g_s=|\A{J}|$ is nondecreasing and submodular as well, and by~\cite[Theorem~44.6]{Schr03}, the polymatroid $\Oh{A}\subset\nnZd$ associated to $g_A$ is the one constructed in~\cite{Oh13} (modulo affine projection). We leave to the reader the easy verification that the so-called \defn{base points} of $\Oh{A}$ from~\cite{Oh13} correspond to the image of $\PMA\cap \nnZd$ under the shift $q\mapsto q+(1,\ldots,1)$.
\end{rema}
\begin{rema}
\label{rem:bettis}
Extensive computations suggest that the Betti diagrams of the power ideal and the cocircuit ideal associated to a transversal matroid (via the representation in Section~\ref{sec:transmats}) coincide, although we have failed to prove so.
It is indeed reasonable to expect such an equality to hold, given that it has been observed in the graph case as well.
Concretely, it is conjectured in~\cite{PS04} that the power ideal and the monomial ideal (known as ``$G$-parking function ideal'') associated to a graph $G$ have equal Betti diagrams.
On the other hand, Mohammadi and Shokrieh have shown in~\cite[Lemma~10.4]{MS16} that the Betti diagram of the latter monomial ideal coincides with that of the Stanley--Reisner ring of the corresponding \defn{cographic} matroid (which equals the Betti diagram of a certain cocircuit ideal associated to~$G$, by Theorem~\ref{thm:isomorphism}).
To the best of our knowledge, equality of the Betti diagrams is wide open in the graph case. We leave the corresponding statement for transversal matroids as a conjecture.
\end{rema}
\longthanks{The author would like to thank Thomas Kahle for stimulating conversations, which eventually sparked the author's interest in matroids, Stanley--Reisner theory, power ideals and related objects. He is also very grateful for the valuable comments and suggestions of two anonymous referees, which led to an improvement of the note. Computations with SageMath~\cite{sagemath}, Macaulay2~\cite{M2} and Polymake~\cite{polymake:2000} were essential for this work. The author would like to sincerely thank their developers and contributors.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{amsplain-ac}
%\bibliography{sample-ALCO}
\bibliography{ALCO_Sarmiento_173}
\end{document}