# Ehrhart Positivity of Panhandle Matroids and the Ehrhart-Coefficient Upper-
Bound Conjecture for Paving Matroids

Danai Deligeorgaki  KTH Royal Institute of Technology,
https://www.kth.se/profile/danaide<EMAIL_ADDRESS>,  Daniel McGinnis
Department of Mathematics, Iowa State University,
https://sites.google.com/iastate.edu/danielmcginnis<EMAIL_ADDRESS>and
Andrés R. Vindas-Meléndez  Departments of Mathematics, UC Berkeley & Harvey
Mudd College, https://math.berkeley.edu/~vindas<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Panhandle matroids are a specific lattice-path matroid corresponding to
panhandle-shaped Ferrers diagrams. Their matroid polytopes are the
subpolytopes carved from a hypersimplex to form matroid polytopes of paving
matroids. It has been an active area of research to determine which families
of matroid polytopes are Ehrhart positive. We prove Ehrhart positivity for
panhandle matroid polytopes, thus confirming a conjecture of Hanely, Martin,
McGinnis, Miyata, Nasr, Vindas-Meléndez, and Yin (2023). Another standing
conjecture posed by Ferroni (2022) asserts that the coefficients of the
Ehrhart polynomial of a connected matroid are bounded above by those of the
corresponding uniform matroid. We prove Ferroni’s conjecture for paving
matroids – a class conjectured to asymptotically contain all matroids. Our
proofs rely solely on combinatorial techniques which involve determining
intricate interpretations of certain set partitions.

##  1\. Introduction

Two elemental objects in combinatorics and discrete geometry, namely matroids
and polytopes, have garnered the attention of mathematicians for years.
Matroid (base) polytopes form a bridge between these two objects. In this
paper we focus on the Ehrhart theory (i.e., the theory of integer points in
polytopes) of two types of matroid polytopes: those arising from _panhandle_
and _paving matroids_.

A _matroid_ $M$ on a finite ground set $E$ can be defined by its basis system
$\mathcal{B}$, a nonempty collection of subsets of $E$, all of the same size,
satisfying a certain _exchange condition_. Every finite collection of vectors
gives rise to a matroid whose _bases_ are its maximal independent sets. Given
a matroid $M$ with ground set $[n]=\\{1,2,\dots,n\\}$ and rank $r$, the
_matroid (base) polytope_ $\mathcal{P}_{M}$ is the convex hull in
$\mathbb{R}^{n}$ of the indicator vectors of its bases. Matroid polytopes
provide geometric insight into the structure of matroids. A panhandle matroid,
denoted $\operatorname{\mathsf{Pan}}_{r,s,n}$, is a lattice-path matroid
corresponding to panhandle-shaped Ferrers diagrams (see Figure 1). A matroid
of rank $r$ is called _paving_ if every circuit has cardinality greater than
or equal to $r$, and _sparse paving_ if it and its dual are both paving.
Paving matroids are noteworthy as it is conjectured and widely believed that
asymptotically all matroids are paving, or even sparse paving (see [MNWW11],
[PvdP15], [Oxl11, Chapter 15.5]). We refer the reader to Subsections 2.2 and
2.3 for brief background on matroids and matroid polytopes, respectively.

The _Ehrhart function_ of a polytope $P$ (i.e., the convex hull of finitely
many points) $P\subset\mathbb{R}^{d}$, is the lattice-point enumerator
$\operatorname{\mathsf{ehr}}_{P}(t):=|tP\cap\mathbb{Z}^{d}|$, where
$tP=\\{t\mathbf{x}:\ \mathbf{x}\in P\\}$ for $t\in\mathbb{Z}_{\geq 0}$.
Ehrhart proved that when $P$ is a lattice polytope (i.e., its vertices have
integer coordinates), the Ehrhart function is a polynomial in $t$ of degree
equal to the dimension of $P$, commonly known as the _Ehrhart polynomial_
[Ehr62]. The leading coefficient of the Ehrhart polynomial of a lattice
polytope $P$ is equal to its normalized volume, the second-leading coefficient
is equal to half the normalized surface area, and the constant coefficient is
1. The other coefficients of $\operatorname{\mathsf{ehr}}_{P}(t)$ are more
mystifying, and in general can be negative (see [Liu19, Section 4] for several
examples of Ehrhart polynomials with negative coefficients). Ehrhart
polynomials are an important invariant of lattice polytopes, as they encode
much of a polytope’s geometry, arithmetic, and combinatorics. As a whole,
Ehrhart theory has developed into a key topic, playing a role in and
benefiting from other areas of mathematics including, but not limited to,
number theory [Bec99, BV08, MM15], commutative algebra [CLS11, Ful93],
algebraic geometry [Mor93, Pom93], enumerative combinatorics [BR15, BS18], and
integer programming [Bar06, Bru23]. We refer the reader to Subsection 2.1 for
brief background on polytopes and Ehrhart theory.

In [DLHK09], De Loera, Haws, and Köppe conjectured that the Ehrhart polynomial
of every matroid polytope has nonnegative coefficients (i.e., they are
_Ehrhart positive_). Their conjecture was disproved by Ferroni [Fer22a], who
constructed an infinite family of matroids whose matroid polytopes are not
Ehrhart positive. Determining families of matroid polytopes that do exhibit
Ehrhart positivity is itself both a challenging and interesting problem, as
evidenced by the extensive literature (see, for example [HMM+23, FM22, Fer21,
Fer22b, FJS22, JR22, KMSRA18]). The techniques used to show Ehrhart positivity
for different polytopes vary widely. In this paper, we rely solely on
combinatorial techniques.

Volume formulas for general matroid polytopes were given by Ardila, Benedetti,
and Doker [ABD10] and Ashraf [Ash20], but their Ehrhart polynomials are not as
well understood. One example of a family of matroid polytopes for which their
Ehrhart polynomial is determined is _minimal matroids_ (i.e., matroids with
the least number of bases for their rank and ground set size among all such
connected matroids). In [Fer22b], Ferroni calculated the Ehrhart polynomial of
minimal matroid polytopes and proved that they are Ehrhart positive.
Subsequently, in [Fer22a], Ferroni used the fact that the matroid polytopes of
a sparse paving matroid could be obtained from a hypersimplex by slicing with
(geometric) hyperplanes. Each piece sliced off in this way is itself a matroid
polytope of the minimal matroid, which resulted in an explicit formula for the
Ehrhart polynomial of a sparse paving matroid polytope, for which Ferroni was
able to show is not always Ehrhart positive.

In [HMM+23], the authors extended Ferroni’s methods from sparse paving to
paving matroids and showed that the matroid polytope of any paving matroid can
be obtained from slicing pieces off from the hypersimplex using hyperplanes.
The pieces sliced off are matroid polytopes of panhandle matroids. With
combinatorial techniques, they calculated the Ehrhart function of a panhandle
matroid polytope and provided several equivalent formulas for it. One such
formula is the following:

######  Theorem 1.1 (Corollary 5.4 in [HMM+23]).

Let $1\leq r\leq s<n$. The Ehrhart polynomial of
$\mathcal{P}_{\operatorname{\mathsf{Pan}}_{r,s,n}}$ can be written as

$\operatorname{\mathsf{ehr}}_{\operatorname{\mathsf{Pan}}_{r,s,n}}(t)=\frac{n-s}{(n-1)!}\binom{t+n-s}{n-s}\varphi_{r,s,n}(t)$

where

(1)
$\varphi_{r,s,n}(t)=\sum_{i=0}^{s-r}(-1)^{i}\binom{s}{i}\sum_{\ell=0}^{s-1}(n-2-\ell)!\ell!\binom{s-1-\ell-i+t(s-r-i+1)}{s-1-\ell}\binom{s-1-i+t(s-r-i)}{\ell}.$

Though the authors presented the Ehrhart polynomial of a panhandle
matroid111For simplicity, we write “the Ehrhart polynomial of the matroid $M$”
(denoted, $\operatorname{\mathsf{ehr}}_{M}(t)$), to mean the “Ehrhart
polynomial of the matroid polytope of $M$”., its Ehrhart positivity is not
immediately evident. Observe that in the formula for
$\operatorname{\mathsf{ehr}}_{\operatorname{\mathsf{Pan}}_{r,s,n}}(t)$ given
in Theorem 1.1, since $\binom{t+n-s}{n-s}$ is a polynomial in $t$ with
positive coefficients, in order to prove the Ehrhart positivity of panhandle
matroids, it suffices to show that the polynomial $\varphi_{r,s,n}(t)$ has
positive coefficients. In [HMM+23], the authors conjectured that panhandle
matroids are Ehrhart positive [HMM+23, Conjecture 6.1], and they showed that
the positivity of $\varphi_{r,s,n}(t)$ can follow from a purely combinatorial
statement, which appears as Conjecture 3.6 in Section 3. The first main result
of this paper is to prove Conjecture 3.6, thereby proving that panhandle
matroids are Ehrhart positive.

######  Theorem 1.2.

Given positive integers $r\leq s\leq n-1$, the panhandle matroid
$\operatorname{\mathsf{Pan}}_{r,s,n}$ is Ehrhart positive.

This work is in part motivated by the fact that panhandle matroids are special
instances of other well-studied families of matroids, including Schubert
matroids, lattice-path matroids, and positroids. Panhandle matroid polytopes
are instances of the more general family of (weighted) multi-hypersimplices, a
family of alcoved polytopes considered in [LP05]. In fact, they are
polypositroids [LP20], a subclass of alcoved polytopes that are conjectured to
be Ehrhart positive [FJS22, Conjecture 6.3]. Our results also confirm this
conjecture for the class of panhandle matroid polytopes. Additionally,
panhandle matroids are notched rectangle matroids, defined in [FL23] (also
known as cuspidal matroids in [FS22]), which are conjectured to be Ehrhart
positive in both works.

We then continue to discuss a related problem to Conjecture 3.6. Ferroni posed
in [Fer22b] a conjecture asserting that for a connected matroid $M$ with rank
$r$ and $n$ elements, the Ehrhart polynomial of $\mathcal{P}_{M}$ is
coefficient-wise bounded below and above by the Ehrhart polynomial of the
corresponding minimal matroid and the uniform matroid $U_{r,n}$, respectively.
In general, the lower bound is not true as Ferroni himself proved that there
are matroids which fail to be Ehrhart positive [Fer22a] while the Ehrhart
polynomials of minimal matroids have positive coefficients [Fer22b]. The
second main result of this paper is to confirm Ferroni’s Ehrhart-coefficient
upper-bound conjecture for paving matroids.

######  Theorem 1.3.

Let $M$ be a paving matroid of rank $r$ with ground set $[n]$. Then

$\operatorname{\mathsf{ehr}}_{M}(t)\preceq\operatorname{\mathsf{ehr}}_{U_{r,n}}(t).$

The proof of this theorem relies on a general formula for the Ehrhart
polynomial of a paving matroid that was first presented in [HMM+23].
Combinatorial techniques similar to those used to validate Conjecture 3.6 are
employed to prove a sufficient condition for Theorem 1.3. We further show that
the relaxation of an Ehrhart-positive matroid is also Ehrhart positive (see
Sections 2 and 6 for relevant definitions and results, respectively).

The paper is structured as follows:

  * •

Section 2 presents background on polytopes and Ehrhart theory, along with some
basics on matroids and matroid polytopes.

  * •

In Section 3, we define ordered chain forests, which are combinatorial objects
that emerge from specific set partitions, and proceed to enumerate them, thus
serving as a stepping stone for proving Conjecture 3.6.

  * •

Section 4 is concerned with understanding each term within the summation
appearing in Conjecture 3.6. We do so by constructing a bijection between
objects defined in Section 3.

  * •

Section 5 presents the proof of Conjecture 3.6, namely that panhandle matroids
are Ehrhart positive, via an inclusion-exclusion-type argument.

  * •

In Section 6, we use the tools developed in previous sections to confirm
Ferroni’s Ehrhart-coefficient upper-bound conjecture in the case of paving
matroids.

##  2\. Background

In this section, we present a brief background on polytopes and Ehrhart
theory, as well as matroids and matroid polytopes. To aid navigation through
the paper, we conclude the section with a notation table (Table 1). We note
that some of the content in this section is borrowed from [HMM+23].

###  2.1. Polytopes and Ehrhart theory

A _lattice polytope_ $P$ is the convex hull of a finite set of points with
integer coordinates in $\mathbb{R}^{n}$. The _dimension_ of
$P\subset\mathbb{R}^{n}$ is $\dim(P)=\dim(\operatorname{aff}(P))$, where
$\operatorname{aff}(P)$ is the smallest affine subspace of $\mathbb{R}^{n}$
containing $P$. The _normalized volume_ or _relative volume_ $\mathrm{Vol}(P)$
is the volume of $P$ with respect to the lattice
$\mathbb{Z}^{n}\cap\operatorname{aff}(P)$. The _Ehrhart function_ of $P$ is
defined as

$\operatorname{\mathsf{ehr}}_{P}(t):=|tP\cap\mathbb{Z}^{n}|$

where $tP=\\{t\mathbf{x}:\ \mathbf{x}\in P\\}$ for $t\in\mathbb{Z}_{\geq 0}$.
Ehrhart showed in the early 1960s that this counting function is a polynomial
in $t$ of degree $\dim(P)$ [Ehr62]. Its leading coefficient is equal to its
normalized volume, second-leading coefficient equal to half the normalized
surface area, and constant coefficient 1 [BR15, Ehr62]. The other coefficients
of $\operatorname{\mathsf{ehr}}_{P}(t)$ are not as well understood and can be
negative.

One of the main problems in Ehrhart theory is to characterize the coefficients
that a polynomial must have in order to be the Ehrhart polynomial of a lattice
polytope. Hence, it is often of interest to study the inequalities that
Ehrhart polynomials must satisfy for certain families of polytopes. Of all the
possibilities one could consider for classes of inequalities, one of the most
actively studied is that of _Ehrhart positivity_.

######  Definition 2.1.

A lattice polytope is _Ehrhart positive_ or exhibits _Ehrhart positivity_ if
its Ehrhart polynomial has nonnegative coefficients.

While Ehrhart functions can often be calculated by combinatorial means, it is
sometimes easier to describe the Ehrhart function of a polytope than to give
an explicit polynomial expression for it. If it is not at all apparent from
the Ehrhart function formula that the coefficients of the polynomial are
positive, then the question of Ehrhart positivity arises. One hopeful
consequence of Ehrhart positivity is that the coefficients of the Ehrhart
polynomial have a combinatorial or geometric interpretation. We invite the
reader to look at [Liu19] for extended exposition on Ehrhart positivity.

###  2.2. Matroids

We briefly review matroidal definitions and relevant terminology. Although the
definition presented next is in terms of the basis system of a matroid, there
are a plethora of cryptomorphic axiomatizations of matroids. For more on
matroids, we recommend [Oxl11] and [Wel76].

######  Definition 2.2.

Let $E$ be a finite set. A _matroid basis system on ground set $E$_ is a
nonempty family $\mathcal{B}\subseteq 2^{E}$ of _bases_ satisfying the
_exchange axiom_ : for all distinct $B,B^{\prime}\in\mathcal{B}$ and all $e\in
B\setminus B^{\prime}$, there exists $e^{\prime}\in B^{\prime}\setminus B$
such that $\left(B\setminus\\{e\\}\right)\cup\\{e^{\prime}\\}\in\mathcal{B}$.
The pair $M=(E,\mathcal{B})$ defines a _matroid_. Any subset of a basis is
called an _independent set_. The _rank function_ of $M$ is defined by
$\operatorname{\operatorname{rank}}(A)=\max\\{|A\cap B|:\ B\in\mathcal{B}\\}$
for $A\subseteq E$. The number $\operatorname{\operatorname{rank}}(E)$ is
called the _rank_ of $M$, often abbreviated as $r$.

The family of independent sets of a matroid $M$ contains the same information
as the basis system, as does the rank function, thus $M$ can be defined by
specifying any of these objects. Let us summarize below some important matroid
theory notions:

  * •

A _circuit_ in $M$ is a minimal non-independent subset of $E$.

  * •

A _flat_ of $M$ is a subset $F\subseteq E$ such that
$\operatorname{\operatorname{rank}}(G)>\operatorname{\operatorname{rank}}(F)$
for every $G\supsetneq F$.

  * •

A _hyperplane_ 222This use of the word “hyperplane” is standard in matroid
theory, but unfortunately conflicts with the geometric use of “hyperplane”,
which we also use. It should be clear from context which meaning is intended.
is a flat of rank $r-1$.

  * •

The _direct sum_ of two matroids $M=(E,\mathcal{B})$ and
$M^{\prime}=(E^{\prime},\mathcal{B}^{\prime})$ on disjoint ground sets is the
matroid $M\oplus M^{\prime}$ on $E\cup E^{\prime}$ with basis system $\\{B\cup
B^{\prime}:\ B\in\mathcal{B},B^{\prime}\in\mathcal{B}^{\prime}\\}$.

  * •

A matroid is _connected_ if it cannot be written as a direct sum of two non-
empty matroids. Every matroid admits a unique decomposition as a direct sum of
connected matroids, called its _components._

  * •

A _paving matroid_ $M$ is a matroid for which every circuit has cardinality at
least $\operatorname{\operatorname{rank}}(M)$.

  * •

A _circuit-hyperplane_ is a set that is both a circuit and a hyperplane. If
$C$ is a circuit-hyperplane, then the family $\mathcal{B}\cup\\{C\\}$ is in
fact a matroid basis system of a new matroid [Oxl11, Prop.1.5.14], called the
_relaxation of $M$ at $C$_.

  * •

A hyperplane $H$ of a matroid $M$ is a _stressed hyperplane_ if every subset
of $H$ of size $r$ is a circuit.

It turns out that stressed hyperplanes are connected to paving matroids.

######  Proposition 2.3.

[FNV22, Proposition 3.16] A matroid is paving if and only if all its
hyperplanes are stressed.

######  Example 2.4.

Let $r\leq s<n$ be nonnegative integers. The following types of matroids are
commonly referenced in this paper.

  * •

The _minimal matroid_ $T_{r,n}$ is a connected matroid of size $n$ and rank
$r$ with the least number of bases possible.

  * •

The _uniform matroid_ $U_{r,n}$ on ground set $[n]$ has basis system
$\binom{[n]}{r}=\\{B\subseteq[n]:\ |B|=r\\}$, independence system
$\\{B\subseteq[n]:\ |B|\leq r\\}$, and rank function
$\operatorname{\operatorname{rank}}(A)=\min(r,|A|)$.

  * •

For a matroid $M$ with basis system $\mathcal{B}$, let
$\operatorname{Rel}_{S}(\mathcal{B}):=\mathcal{B}\cup\binom{S}{r}$, for a set
$S\subseteq E$ containing no basis. We say that $S$ _can be relaxed_ if
$\mathcal{B}\cup\binom{S}{r}$ is a matroid basis system. In this case, the
resulting matroid is called the _relaxation of $M$ at $S$_, denoted by
$\operatorname{Rel}_{S}(M)$.

######  Proposition 2.5.

[FNV22, Theorem 1.2] If $H$ is a stressed hyperplane of $M$, then $H$ can be
relaxed.

When $S$ is a circuit-hyperplane, the relaxation of a matroid $M$ at $S$
coincides with the common notion of a relaxation as in [Oxl11, Section 1.5],
and in [HMM+23, Definition 3.4] that, when $S$ is a stressed hyperplane, the
stressed-hyperplane relaxation is recovered. Throughout this article, the sets
relaxed are always stressed hyperplanes, though in principle it is possible to
relax other sets in matroids too.

The panhandle matroid, introduced in [HMM+23], plays a central role in this
article.

######  Definition 2.6.

Let $r\leq s<n$ be nonnegative integers. The _panhandle matroid_
$\operatorname{\mathsf{Pan}}_{r,s,n}$ is the matroid with ground set $[n]$ and
basis system

$\mathcal{B}=\mathcal{B}_{r,s,n}=\left\\{B\in\binom{[n]}{r}:\ |B\cap[s]|\geq
r-1\right\\}.$

Panhandle matroids are connected matroids of rank $r$ and are instances of
lattice-path matroids [BdMN03], as discussed in detail in [HMM+23, Section 4]
(Figure 1 offers a visual insight into this connection).

1234567891011$s-r+1$$n-r$$r$ Figure 1. The panhandle matroid
$\operatorname{\mathsf{Pan}}_{5,7,11}$ as a lattice-path matroid. The lattice
path shown in orange gives rise to the basis $\\{3,4,5,7,9\\}$.

We note that the minimal matroid $T_{r,n}$ is equivalent to the panhandle
matroid $\operatorname{\mathsf{Pan}}_{r,r,n}$ (where the Ferrers diagram has a
hook shape), while the uniform matroid $U_{r,n}$ can be realized as
$\operatorname{\mathsf{Pan}}_{r,n-1,n}$.

###  2.3. Matroid (base) polytopes

To every matroid, we can associate a polytope called its _matroid (base)
polytope_. Matroid polytopes encode information such as the basis system, rank
function, etc., while providing geometric insight into the structure of
matroids. The study of matroid polytopes can be traced back to Edmonds [Edm03]
and also appears in the context of combinatorial optimization [CCPS98, Fuj05].
In particular, matroid polytopes are a well-studied subclass of generalized
permutahedra [Pos09], hence, they significant from the point of view of
optimization, combinatorial Hopf theory, and combinatorial algebraic geometry.

In what follows, let $\operatorname{conv}A$ denote the convex hull of a point
set $A\subseteq\mathbb{R}^{n}$.

######  Definition 2.7.

The _matroid polytope_ of a matroid $M=(E,\mathcal{B})$ is the convex hull

$\mathcal{P}_{M}:=\operatorname{conv}\\{\mathbf{e}_{B}:B\in\mathcal{B}\\}\subset\mathbb{R}^{|E|},$

where $\mathbf{e}_{i}$ is the $i$th standard basis vector of
$\mathbb{R}^{|E|}$ and $\displaystyle\mathbf{e}_{B}=\sum_{i\in
B}\mathbf{e}_{i}$.

The polytope $\mathcal{P}_{M}$ of a matroid $M=(E,\mathcal{B})$ is always
contained in the (geometric) hyperplane
$\\{\mathbf{x}=(x_{i})\in\mathbb{R}^{|E|}:\ \sum x_{i}=r\\}$, where
$r=\text{rank}(E)$. Therefore, its dimension is strictly smaller than $|E|$.
In fact, $\dim(\mathcal{P}_{M})=|E|-c$, where $c$ is the number of components
of $M$. It has the following description in terms of inequalities [FS05,
Proposition 2.3]:

$\mathcal{P}_{M}=\bigg{\\{}(x_{1},\dots,x_{n})\in\mathbb{R}_{\geq 0}^{n}\ :\
\sum_{i=1}^{n}x_{i}=\operatorname{\operatorname{rank}}(M),\ \sum_{i\in
F}x_{i}\leq\operatorname{\operatorname{rank}}(F)\textrm{ for all flats
}F\bigg{\\}}.$

The inequality description of the matroid polytope of our central object, the
panhandle matroid, is the following:

######  Definition 2.8 (Proposition 4.4 in [HMM+23]).

Let $r\leq s<n$ be nonnegative integers. The polytope
$\mathcal{P}_{\operatorname{\mathsf{Pan}}_{r,s,n}}$ is given by

$\mathcal{P}_{\operatorname{\mathsf{Pan}}_{r,s,n}}=\\{(x_{1},\dots,x_{n})\in[0,1]^{n}\
:\ \sum_{i=1}^{n}x_{i}=r\textrm{ and }\sum_{i=s+1}^{n}x_{i}\leq 1\\}.$

######  Example 2.9.

We now present some examples that are of interest to this paper.

  * •

In [Fer22b], Ferroni computed the Ehrhart polynomial of the minimal matroid
$T_{r,n}$ and showed that all coefficients of its Ehrhart polynomial are
positive:

$\operatorname{\mathsf{ehr}}_{T_{r,n}}(t)=\frac{\binom{t+n-r}{n-r}}{\binom{n-1}{r-1}}\sum_{j=0}^{r-1}\binom{n-r-1+j}{j}\binom{t+j}{j}.$

  * •

The _hypersimplex_ $\Delta_{r,n}$, i.e., the convex hull of the $\binom{n}{r}$
points in $\mathbb{R}^{n}$ whose coordinates consist of $r$ 1’s and $n-r$ 0’s,
is the base polytope of the uniform matroid $U_{r,n}$. Katzman [Kat05,
Corollary 2.2] (see also [Sta11, Problem 4.62]) computed the Ehrhart
polynomial of the hypersimplex as

$\operatorname{\mathsf{ehr}}_{U_{r,n}}(t)=\operatorname{\mathsf{ehr}}_{\Delta_{r,n}}(t)=\sum_{j=0}^{r-1}(-1)^{j}\binom{n}{j}\binom{(r-j)t-j+n-1}{n-1}.$

  * •

In [HMM+23], the authors show that the Ehrhart polynomial for the polytope
$\mathcal{P}_{\operatorname{\mathsf{Pan}}_{r,s,n}}$ is

(2)
$\operatorname{\mathsf{ehr}}_{{\operatorname{\mathsf{Pan}}_{r,s,n}}}(t)=\sum_{i=0}^{s-r}(-1)^{i}\binom{s}{i}\sum_{\ell=0}^{s-1}\binom{t(s-r-i)+s-1-i}{s-1-\ell}\binom{t+n-s}{n-s}\binom{t}{\ell}\frac{n-s}{n-s+\ell}.$

Note that the Ehrhart polynomial expression presented in the statement of
Theorem 1.1 can be derived from Equation (2).

###  2.4. Notation

We conclude our background section with a notation table for the reader’s
reference. This table also includes notation for terms that will be defined in
later sections.

Table 1. Notation Table Symbol |  Meaning
---|---
$[n]$ |  the set $\\{1,2,\ldots,n\\}$
$T_{r,n}$ |  the minimal matroid of size $n$ and rank $r$
$U_{r,n}$ |  the uniform matroid of size $n$ and rank $r$
$\operatorname{\mathsf{Pan}}_{r,s,n}$ |  the panhandle matroid
$\mathcal{P}_{M}$ |  the matroid polytope associated to the matroid $M$
$\operatorname{\mathsf{ehr}}_{M}(t)$ |  the Ehrhart polynomial of the matroid polytope $\mathcal{P}_{M}$
$\operatorname{Rel}_{S}(M)$ |  the relaxation of a matroid $M$ at $S$
$\operatorname{\mathsf{CF}}(q,s,k)$ |  the set of naturally ordered chain forests of $[s]$ with $k$ blocks and weight $q$
$\gamma(F,\ell)$ |  the number of trailers that appear after the $\ell^{th}$ position (when writing the sequence of numbers obtained by considering the elements as they appear in the ordered chain forest $F$)
$P_{a,b}^{n}$ |  the sum of all possible products of $n$ integers lying between $a$ and $b$
$B(F)$ |  the set of blocks of and ordered chain forest $F$
$w(B)$ |  a nonnegative value assigned to a block $B$
$\operatorname{weight}(B)$ |  the weight of a block $B$
$DCF_{q}(s)$ |  the set of $A$-distinguished ordered chain forests $(F,w,A)$ of $[s]$ for some subset $A\subset[s]$ such that $|A|+\sum_{B\in B(F)}w(B)=q$

##  3\. Toward Ehrhart positivity: Combinatorial objects

We recall that in Section 6 of [HMM+23], the authors reduced the problem of
proving Ehrhart positivity for panhandle matroids (Theorem 1.2) to a purely
combinatorial problem (see Conjecture 3.6 below). We define ordered chain
forests, emerging as particular set partitions, which are intimately related
to the conjecture. Specifically, we enumerate these objects whose cardinality
can be expressed in terms of a weighted alternating sum over products
involving the sum of all possible products of integers in a certain range,
denoted $P^{n}_{a,b}$. Additionally, we introduce valued ($A$-distinguished)
ordered chain forests, which will turn out to provide an interpretation of
each term in the alternating sum.

We further note that (unordered) chain forests were presented in [HMM+23] and
are used to state Conjecture 3.6. The more general objects, which we refer to
as ordered chain forests, are introduced as they support our proof of the
conjecture.

######  Definition 3.1.

An _ordered chain forest_ of $[s]$ is an ordered partition of $[s]$ into a set
of blocks, where each block is itself internally ordered.

We write an ordered chain forest $F$ as a sequence of blocks $F=B_{1}\cdots
B_{k}$. Example 3.2 illustrates some of these definitions.

  1. (1)

The first and last element of a block is called its _leader_ and _trailer_ ,
respectively.

  2. (2)

An ordered chain forest is said to be _naturally ordered_ if the blocks are
ordered increasingly according to their leaders.

  3. (3)

The _weight of a block_ $B$, denoted $\operatorname{weight}(B)$, in an ordered
chain forest is the number of elements of the block that are less than its
leader. If an element is less than the leader of its block, we say this
element _contributes weight_ to the block.

  4. (4)

The _weight of an ordered chain forest_ is the sum of the weights of its
blocks.

######  Example 3.2.

Consider the ordered chain forests $F_{1}=[1,3][4,2][5]$ and
$F_{2}=[4,2][1,3][5]$. Observe that $F_{1}$ is naturally ordered, while
$F_{2}$ is not, and they both are distinct from one another because the
ordering of their blocks differs. Additionally, $[3,1][4,2][5]$ is distinct
from $[1,3][4,2][5]$ as well since the ordering of the elements within each
block matters. Now, consider the ordered chain forest
$F=[1,3][5,2,4][7,6][8].$ The weights of each block are 0, 2, 1, and 0,
respectively. The total weight of $F$ is 3.

Given an ordered chain forest $F=B_{1}\cdots B_{k}$ of $[s]$, for $0\leq l\leq
s-1$, we define

$\gamma(F,\ell):=\left|\left\\{j\in[k]\mid\sum_{i=1}^{j}|B_{i}|>\ell\right\\}\right|.$

In other words, if we make note of the sequence of numbers obtained by writing
the elements as they appear in $F$, then $\gamma(F,\ell)$ is the number of
trailers that appear after the $\ell^{th}$ position. For example, if
$F=[1,3][4,2][5]$, then the corresponding sequence of numbers is $1\ 3\ 4\ 2\
5$ and the trailers are 3, 2, and 5. Here, we say 1 is in the first position,
3 is in the second position, 4 is in the third position, and so on. Thus, we
have that

$\gamma(F,0)=3,\,\gamma(F,1)=3,\,\gamma(F,2)=2,\,\gamma(F,3)=2,\,\gamma(F,4)=1.$

The set of naturally ordered chain forests of $[s]$ with $k$ blocks and weight
$q$ was originally defined by Ferroni [Fer21], and is denoted by
$\operatorname{\mathsf{CF}}(q,s,k)$ in [HMM+23]. In both papers, a certain
combinatorial expression was shown to enumerate the quantity
$|\operatorname{\mathsf{CF}}(q,s,k)|$. In order to present this particular
result, we introduce the following notation.

######  Definition 3.3.

Let $a\leq b$ and $n$ be integers. We define the quantity $P_{a,b}^{n}$ as

$P_{a,b}^{n}=\sum_{a\leq i_{1}<\cdots<i_{n}\leq b}i_{1}\cdots i_{n},$

i.e., as the sum of all possible products of $n$ integers between $a$ and $b$.
We define $P^{0}_{a,b}=1$ and $P^{n}_{a,b}=0$ if $n<0$ or $n>b-a+1$. For some
choices of parameters in this paper, we sometimes encounter terms of the form
$P_{a+1,a}^{n}$. In this special case, we use the convention that
$P_{a+1,a}^{n}=1$.

This notation now allows us to enumerate the set of naturally ordered chain
forests.

######  Theorem 3.4 ([Fer21, HMM+23]).

Let $q\geq 0$, $1\leq k\leq s$ be integers. The quantity
$|\operatorname{\mathsf{CF}}(q,s,k)|$ is given by

(3)
$|\operatorname{\mathsf{CF}}(q,s,k)|=\sum_{i=0}^{q}(-1)^{i}\binom{s}{i}P^{s-k}_{-i+1,s-1-i}\binom{k-1+q-i}{k-1}.$

This was shown through a generating function approach in [Fer21] and later by
combinatorial means in [HMM+23]. Additionally, a refinement of the set
$\operatorname{\mathsf{CF}}(q,s,k)$ was defined in [HMM+23] for the purpose of
articulating a generalization of Theorem 3.4, which appears as Conjecture 3.6
below.

######  Definition 3.5.

Let $1\leq m\leq k\leq s$, $q\geq 0$, and $0\leq\ell\leq s-1$ be integers. We
denote the set of naturally ordered chain forests $F$ of $[s]$ with $k$ blocks
with$\gamma(F,\ell)=m$ and weight $q$ by
$\operatorname{\mathsf{CF}}(q,s,k,\ell,m)$.

The conjecture below states that a certain expression,which arose from an
analysis of the Ehrhart polynomials of panhandle matroids in [HMM+23],
enumerates the quantity $|\operatorname{\mathsf{CF}}(q,s,k,\ell,m)|$.

######  Conjecture 3.6 (Conjecture 6.9 in [HMM+23]).

Let $1\leq m\leq k\leq s$, $q\geq 0$, and $0\leq\ell\leq s-1$ be integers.
Then the number of naturally ordered chain forests $F$ of $[s]$ with $k$
blocks and weight $q$, such that $\gamma(F,\ell)=m$, is given by

(4)
$|\operatorname{\mathsf{CF}}(q,s,k,\ell,m)|=\sum_{i=0}^{q}(-1)^{i}\binom{s}{i}P^{s-\ell-m}_{-i+1,s-1-\ell-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\binom{k-1+q-i}{k-1}.$

We again emphasize that the contents of Section 6 in [HMM+23] show that the
truth of Conjecture 3.6 implies Theorem 1.2. In Section 5, we prove Conjecture
3.6, thus settling the Ehrhart positivity conjecture for panhandle matroids.
Although the expression appearing in Equation (4) is similar to Equation (3),
and different proofs for Equation (3) are given in [Fer21] and [HMM+23], the
methods of these two proofs do not seem to extend directly to prove Conjecture
3.6. The proof we present here is purely combinatorial, and hence more in line
with the ideas in [HMM+23]. However, our approach is novel and our proof is
substantially different. Our approach relies on the following definitions.

######  Definition 3.7.

For an ordered chain forest $F=B_{1}\cdots B_{k}$, let $B(F)$ be the set of
blocks of $F$.

  1. (1)

A _valued ordered chain forest_ is a pair $(F,w)$ where $F$ is an ordered
chain forest and $w:B(F)\longrightarrow\mathbb{Z}_{\geq 0}$ is a function
assigning a nonnegative integer value to each block.

  2. (2)

For a block $B\in B((F,w))$ of a valued ordered chain forest, we call $w(B)$
the _value_ of $B$.

  3. (3)

The _weight of a valued ordered chain forest_ $(F,w)$ is the sum of weights of
blocks that make up $(F,w)$ and $\sum_{B\in B((F,w))}w(B)$.

  4. (4)

At times we denote a valued ordered chain forest $(F,w)$ as
$(F,w)=B_{1}^{w(B_{1})}\cdots B_{k}^{w(B_{k})}$.

######  Definition 3.8.

Let $A\subset[s]$. An _$A$ -distinguished ordered chain forest_ of $[s]$ is a
pair $(F,A)$ where $F$ is an ordered chain forest, $F=B_{1}\cdots
B_{r}C_{1}\cdots C_{p}$, where $0\leq r,p\leq s$, with the following
properties:

  * •

the blocks $B_{i}$ consist only of elements in $[s]\setminus A$,

  * •

the blocks $C_{i}$ consist only of elements in $A$,

  * •

each block has weight 0, i.e., the leader of each block is also the smallest
element of the block,

  * •

the blocks $B_{1}\cdots B_{r}$ are ordered increasingly according to their
leader, and

  * •

the blocks $C_{1}\cdots C_{p}$ are ordered decreasingly according to their
leader.

A _valued $A$-distinguished ordered chain forest_ of $[s]$ is a triple
$(F,w,A)$, where $(F,A)$ is an $A$-distinguished ordered chain forest and $w$
is a function $w:B(F)\longrightarrow\mathbb{Z}_{\geq 0}$, assigning
nonnegative integer values to the blocks $B_{1},...,B_{r},C_{1},...,C_{p}$ of
$F$. We may also write $(F,w,A)$ as $(F,w,A)=(B_{1}^{w(B_{1})}\cdots
B_{r}^{w(B_{r})}C_{1}^{w(C_{1})}\cdots C_{p}^{w(C_{p})},A)$. Additionally, we
denote by $B_{A}(F)$ the set of blocks consisting only of elements in $A$,
i.e., $B_{A}(F)=\\{C_{1},\dots,C_{p}\\}$. Note that
$B_{\varnothing}(F)=\varnothing$.

######  Example 3.9.

Observe that $([1,4]^{2}[3][5,6]^{1}[2],\\{2\\})$ is a valued
$\\{2\\}$-distinguished ordered chain forest, and that
$([1,4]^{2}[3][5,6]^{1}[2],\\{2,5,6\\})$ is a valued
$\\{2,5,6\\}$-distinguished ordered chain forest.

######  Definition 3.10.

For $q\geq 0$ and $s\geq 1$, let $DCF_{q}(s)$ be the set of valued
$A$-distinguished ordered chain forests $(F,w,A)$ of $[s]$ for some
$A\subset[s]$, such that

$|A|+\sum_{B\in B(F)}w(B)=q.$

We further denote by $DCF_{q,k,\ell,m}(s)$ the set of valued $A$-distinguished
ordered chain forests $(F,w,A)\in DCF_{q}(s)$ with the additional property
that $F$ has $k$ blocks and $\gamma(F,\ell)=m$, where $1\leq m\leq k\leq s$,
$0\leq\ell\leq s-1$.

The following proposition provides a combinatorial interpretation for each
summand in Conjecture 3.6. The purpose of introducing (valued)
$A$-distinguished ordered chain forests is to properly articulate Proposition
3.11. This proposition allows us to view the expression from Conjecture 3.6
through a combinatorial lens that will support our proof.

######  Proposition 3.11.

For an integer $0\leq i\leq q$ and fixed $1\leq m\leq k\leq s$, $0\leq\ell\leq
s-1$, the $i^{\text{th}}$ term of the sum in Conjecture 3.6 can be expressed
in terms of valued $A$-distinguished ordered chain forests as follows:

(5)
$(-1)^{i}\binom{s}{i}P^{s-\ell-m}_{-i+1,s-\ell-1-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\binom{k-1+q-i}{k-1}=\sum_{A\in\binom{[s]}{i}}\sum_{(F,w,A)\in
DCF_{q,k,\ell,m}(s)}(-1)^{|B_{A}(F)|}.$

###### Proof.

Let us start by looking at the left hand side of (5), which equals

(6)
$\displaystyle\begin{split}&(-1)^{i}\binom{s}{i}P^{s-\ell-m}_{-i+1,s-\ell-1-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\binom{k-1+q-i}{k-1}\\\
=&\sum_{A\in\binom{[s]}{i}}(-1)^{i}P^{s-\ell-m}_{-i+1,s-\ell-1-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\binom{k-1+q-i}{k-1}.\end{split}$

Note that $P^{s-\ell-m}_{-i+1,s-\ell-1-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}$ is
the sum of all possible products of the form

$i_{1}\cdots i_{s-\ell-m}\cdot j_{1}\cdots j_{\ell-(k-m)},$

where

$-i+1\leq i_{1}<\cdots<i_{s-\ell-m}\leq s-\ell-1-i$

and

$s-\ell-i\leq j_{1}<\cdots<j_{\ell-(k-m)}\leq s-1-i.$

Let $i_{1}\cdots i_{s-\ell-m}\cdot j_{1}\cdots j_{\ell-(k-m)}$ be such a
product and fix an $i$-element subset $A\in\binom{[s]}{i}$. Denote by
$S=\\{i_{1},\dots,i_{s-\ell-m},j_{1},\dots,j_{\ell-(k-m)}\\}$ the set of
elements in the product. For $1\leq u\leq s-1$, let $e_{u}=s-i-u$ be the
$u^{th}$ largest element among $-i+1,\dots,s-1-i$. We define a sequence
$(a_{0},a_{1},\dots,a_{s-1})$ as follows:

  * •

$a_{0}=[\phantom{s}$

  * •

$a_{u}=e_{u}$ if $e_{u}\in S$

  * •

$a_{u}=[\phantom{s}$ if $e_{u}\notin S$.

We now show how the sequence $(a_{0},a_{1},\dots,a_{s-1})$ can be used to
construct a set of

$|i_{1}|\cdots|i_{s-\ell-m}|\cdot|j_{1}|\cdots|j_{\ell-(k-m)}|$

distinct $A$-distinguished ordered chain forests whose block lengths read from
left to right are fixed. We also demonstrate that each of the
$A$-distinguished ordered chain forests $(F,A)$ of $[s]$ that we construct
contributes the value $(-1)^{|B_{A}(F)|}$ to the product $i_{1}\cdots
i_{s-\ell-m}\cdot j_{1}\cdots j_{\ell-(k-m)}$.

If we have $a_{u}=[\phantom{s}$ for some $u$, this corresponds to starting a
block at the $(u+1)^{th}$ position. In particular, this is why
$a_{0}=[\phantom{s}$; to ensure that a block always starts at the first
position. Starting at $u=0$, we construct a family of $A$-distinguished chain
forests as follows.

  * •

If $u\leq s-1-i$ and $a_{u}=[\phantom{s}$, then we start a new block at the
$(u+1)^{th}$ position and we fill this position with the smallest element of
$[s]\setminus A$ that has not yet been allocated to a block. In particular,
since $a_{0}=[\phantom{s}$, we fill the first position with the smallest
element of $[s]\setminus A$. Note that when we start a new block at position
$(u+1)$, we end the previous block at position $u$.

  * •

If $u\leq s-1-i$ and $a_{u}\neq[\phantom{s}$, we can place any element from
$[s]\setminus A$ that has not been already allocated to a block at the
$(u+1)^{th}$ position, for which there are $a_{u}$ choices.

This process constructs the blocks containing elements of $[s]\setminus A$.
Let us now construct the blocks containing elements of $A$ from right to left.
We consider the largest index $u_{1}$ with $u_{1}\geq s-i$ such that
$a_{u_{1}}=[\phantom{s}$, and start a new block at the $(u_{1}+1)^{th}$
position. We fill this position with the smallest element of $A$. Then we may
fill in the rest of this block in $|a_{u_{1}+1}\cdots a_{s-1}|$ ways with
elements of $A$ that were not yet chosen. Each such way to fill in the block
contributes $(-1)^{s-1-u_{1}}$ to the sign of the product $i_{1}\cdots
i_{s-\ell-m}\cdot j_{1}\cdots j_{\ell-(k-m)}$ since $a_{u}<0$ for $u\geq
s-i+1$. Then we consider the second-largest $u_{2}<u_{1}$ with $u_{2}\geq s-i$
such that $a_{u_{2}}=[\phantom{s}$. We start a new block at the
$(u_{2}+1)^{th}$ position and we fill this position with the smallest element
of $A$ not yet chosen. Then we may fill in the rest of this block in
$|a_{u_{2}+1}\cdots a_{u_{1}-1}|$ ways with elements of $A$ that were not yet
chosen. Similarly, each such choice contributes $(-1)^{u_{1}-u_{2}-1}$ to the
product. We continue in this way until we have allocated all elements of $A$.

If the product $i_{1}\cdots i_{s-\ell-m}\cdot j_{1}\cdots j_{\ell-(k-m)}$ is
not zero, then $0\notin S$, so we always start a new block at the
$(s-i+1)^{th}$ position and it is filled with an element from $A$. Therefore,
the last $i$ positions are filled with elements of $A$ and each block in the
ordered chain forests constructed consists either entirely of elements in $A$
or entirely of elements in $[s]\setminus A$. The remaining conditions in
Definition 3.8 are also satisfied, i.e., the ordered chain forests constructed
are $A$-distinguished.

Additionally, as discussed a “$-1$” is contributed to the sign of the product
$i_{1}\cdots i_{s-\ell-m}\cdot j_{1}\cdots j_{\ell-(k-m)}$ every time we
choose an element in $A$ that is not the leader of a block, and in any other
case that we choose some element, it does not affect the sign of the product.
Therefore, if $B_{A}$ is the number of blocks that consist only of elements in
$A$, then the sign of $i_{1}\cdots i_{s-\ell-m}\cdot j_{1}\cdots
j_{\ell-(k-m)}$ is $(-1)^{i-B_{A}}$ since ${A\in\binom{[s]}{i}}$.

The $A$-distinguished ordered chain forests $(F,A)$ constructed in this way
all have $k$ blocks. To see that $\gamma(F,\ell)=m$, notice that in the
product $i_{1}\cdots i_{s-\ell-m}\cdot j_{1}\cdots j_{\ell-(k-m)}$ we choose
$\ell-(k-m)$ elements out of the $\ell$ elements between $s-\ell-i$ and
$s-1-i$. Hence, among the first $\ell+1$ positions, there are exactly $k-m+1$
positions that are the beginning of some block (including the first position).
Therefore, there are exactly $k-m$ blocks that end on or before the
$\ell^{th}$ position, which implies that there are exactly $m$ blocks that end
after the $\ell^{th}$ position.

Additionally, each $A$-distinguished ordered chain forest arises exactly once
from such a product. It then follows that for a fixed set
$A\in\binom{[s]}{i}$,

$(-1)^{i}P^{s-\ell-m}_{-i+1,s-\ell-1-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}$

is given by $\sum(-1)^{|B_{A}(F)|}$ where the sum is taken over all
$A$-distinguished ordered chain forests $(F,A)$ of $[s]$ where $F$ has $k$
blocks and $\gamma(F,\ell)=m$.

Finally, the quantity $\binom{k-1+q-i}{k-1}$ can be interpreted as the number
of ways to assign nonnegative values to the $k$ blocks of such
$A$-distinguished ordered chain forests $(F,A)$ whose sum of the values on the
blocks is $q-i$.

Since $q-i+|A|=q$, we have that

$(-1)^{i}P^{s-\ell-m}_{-i+1,s-\ell-1-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\binom{k-1+q-i}{k-1}=\sum_{(F,w,A)\in
DCF_{q,k,\ell,m}(s)}(-1)^{|B_{A}(F)|}.$

Summing over all subsets $A\in\binom{[s]}{i}$ completes the proof, by Equation
(6). ∎

The following example demonstrates the process of creating $A$-distinguished
ordered chain forests starting from a product, as discussed in Proposition
3.11.

######  Example 3.12.

Let $s=9$, $k=4$, $m=2$, $i=4$, $\ell=5$ and take $A=\\{1,2,3,4\\}$. Let
$(-3)\cdot(-1)\cdot 1\cdot 3\cdot 4$ be a product contributing to the sum
defining $P^{2}_{-3,-1}P^{3}_{0,4}$. The associated sequence as in the proof
of Proposition 3.11 is

$\text{{$(a_{0},...,a_{8})=$}}([\ ,\,4,\,3,\,[\ ,\,1,\,[\ ,\,-1,\,[\ ,\,-3).$

Thus, the blocks of any $A$-distinguished ordered chain forest corresponding
to this product have the following form:

$[\\_,\\_,\\_][\\_,\\_][\\_,\\_][\\_,\\_].$

The first position will be filled with $5$, the smallest element of
$[9]\setminus A$, then there are $4\cdot 3$ ways to fill in the rest of this
block with elements from $[9]\setminus(A\cup\\{5\\})=\\{6,7,8,9\\}$. The
smallest element of $[9]\setminus A$ not yet used will fill in the fourth
position, and then there is 1 way to fill in the rest of the second block with
that last element of $[9]\setminus A$ not yet chosen.

The eighth position is then filled with $1$, the smallest element of $A$, and
there are 3 ways to fill in the rest of that block with an element of
$A\setminus\\{1\\}$: specifically, the last block can be chosen among
$[1,2],[1,3],[1,4]$. Then we fill in the sixth position with the smallest
element of $A$ not yet used. Finally, there is only 1 way to fill the seventh
position with the last element of $A$.

Each $A$-distinguished ordered chain forest obtained in this way contributes
$(-1)^{2}=1$ to the sum $P^{2}_{-3,-1}P^{3}_{0,4}$ since there are two blocks
consisting only of elements in $A$.

##  4\. A bijection between ordered chain forests

Recall that the blocks of a valued $A$-distinguished ordered chain forest
$(F,w,A)$ have weight 0 by definition (see Definition 3.8). In what follows,
we define an algorithm which takes as input such chain forests $(F,w,A)$ and
outputs a valued ordered chain forest where some blocks may have non-zero
weight. We define a map $\phi$ via this algorithm, that will play a crucial
role throughout the proofs. Each element in
$\operatorname{\mathsf{CF}}(q,s,k,\ell,m)$ is in the image of some valued
$\varnothing$-distinguished ordered chain forest under $\phi$. Furthermore,
$\phi$ will allow us to relate the combinatorial interpretation from
Proposition 3.11 to the statement of Conjecture 3.6.

###  4.1. An algorithm defined on valued $A$-distinguished ordered chain
forests.

Let $(F,w,A)=(B_{1}^{\beta_{1}}\cdots
B_{r}^{\beta_{r}}C_{1}^{\gamma_{1}}\cdots C_{p}^{\gamma_{p}},A)$ be a valued
$A$-distinguished ordered chain forest of $[s]$ where the blocks $B_{i}$ are
the blocks with elements in $[s]\setminus A$ and the blocks $C_{i}$ are the
blocks with elements in $A$ $(0\leq r,p\leq s)$. We first split $(F,w,A)$ into
its _non-distinguished part_ , $(F_{1},w_{1})=B_{1}^{\beta_{1}}\cdots
B_{r}^{\beta_{r}}$, and its _distinguished part_ ,
$(F_{2},w_{2})=C_{1}^{\gamma_{1}}\cdots C_{p}^{\gamma_{p}}$.

We now define the algorithm on the the non-distinguished part $(F_{1},w_{1})$.
We initiate with a set $P=\varnothing$, which we call the set of processed
elements, and an ordered list $L$ that contains the elements in $[s]\setminus
A$ listed increasingly. At each iterative step in the algorithm, the set $P$
and the ordered list $L$ will be updated. Moreover, at each iteration, $L$
will represent an ordering on the elements of $[s]\setminus A$. We represent
this ordering with the notation $<_{L}$. We say that $a$ is smaller (resp.
larger) than $b$ according to $L$ if $a<_{L}b$ (resp. $a>_{L}b$). If we say
$a$ is smaller (resp. larger) than $b$ without specifying $L$, then we mean
that $a<b$ (resp. $a>b$) in the natural ordering.

######  Algorithm 1 (Processing valued ordered chain forests).

$\mathtt{Input}$: valued ordered chain forest $(F_{1},w_{1})$,
$P=\varnothing$, naturally-ordered list $L$ on $[s]\setminus A$.
$\mathtt{Output}$: valued ordered chain forest
$(F^{\prime}_{1},w^{\prime}_{1})$ obtained at termination of the algorithm.

  1. (1)

Find the leftmost block $B\in B(F_{1})$ for which $B$ contains an element not
in $P$ and $w_{1}(B)>0$. Let $a$ be the leading term of $B$, and let
$i_{1}<_{L}i_{2}<_{L}\cdots<_{L}i_{j}$ be the elements lying either in $B$ or
in one of the blocks to the right of $B$ (notice that $i_{1}=a$).

  2. (2)

Update the blocks in $F_{1}$ by applying the map $i_{x}\mapsto i_{x+1}$
(indices are modulo $j$) and fixing the remaining elements.

  3. (3)

Update $L$ by making $a$ the largest element, i.e., $a$ becomes the last
element of $L$.

  4. (4)

Update $P=P\cup\\{a\\}$. We say $a$ has been “ _processed_.”

  5. (5)

Update $w_{1}$ so that $w_{1}(B)=w_{1}(B)-1$.

  6. (6)

If there exists a block that contains an element not in $P$ whose value is
positive, go back to step (1), otherwise terminate.

Through this algorithm, we define the following map on the set of valued
$A$-distinguished ordered chain forests.

######  Definition 4.1.

Let $(F,w,A)=(B_{1}^{\beta_{1}}\cdots
B_{r}^{\beta_{r}}C_{1}^{\gamma_{1}}\cdots C_{p}^{\gamma_{p}}\text{{$,A$)}}$ be
an element of $DCF_{q}(s)$ with non-distinguished part
$(F_{1},w_{1})=B_{1}^{\beta_{1}}\cdots B_{r}^{\beta_{r}}$. Let
$(F_{1}^{\prime},w_{1}^{\prime})=B_{1}^{\prime\beta_{1}^{\prime}}\cdots
B_{r}^{\prime\beta_{r}^{\prime}}$ be the output of Algorithm 1. We define the
_map $\phi$_ by

$\phi((F,w,A))=(B_{1}^{\prime\beta_{1}^{\prime}}\cdots
B_{r}^{\prime\beta_{r}^{\prime}}C_{1}^{\gamma_{1}}\cdots
C_{p}^{\gamma_{p}},A).$

######  Example 4.2.

Let $(F,w,\varnothing)=([1,6,2]^{2}[3,7,5]^{1}[4],\varnothing)$ be a valued
$\varnothing$-distinguished ordered chain forest. Then, $(F_{1},w_{1})\ =\
[1,6,2]^{2}[3,7,5]^{1}[4]$ is itself the undistinguished part, and the valued
ordered chain forest, together with the sets $P$ and $L$, after each iterative
step in Algorithm 1 is described below:

  * •

$[1,6,2]^{2}[3,7,5]^{1}[4]$, $P=\varnothing$, $L=[1,2,3,4,5,6,7]$

  * •

$[2,7,3]^{1}[4,1,6]^{1}[5]$, $P=\\{1\\}$, $L=[2,3,4,5,6,7,1]$

  * •

$[3,1,4][5,2,7]^{1}[6]$, $P=\\{1,2\\}$, $L=[3,4,5,6,7,1,2]$

  * •

$[3,1,4][6,5,2][7]$, $P=\\{1,2,5\\}$, $L=[3,4,6,7,1,2,5]$

Thus, $(F^{\prime}_{1},w^{\prime}_{1})=[3,1,4][6,5,2][7]$ and
$\phi((F,w,\varnothing))=([3,1,4][6,5,2][7],\varnothing)$.

######  Example 4.3.

Let $(F,w,\\{6,8\\})=([1,5,3]^{2}[2]^{2}[4,7]^{1}[8][6]^{1},\\{6,8\\})$ be a
valued $\\{6,8\\}$-distinguished ordered chain forest. The undistinguished
part is given by $(F_{1},w_{1})=[1,5,3]^{2}[2]^{2}[4,7]^{1}$. The valued
ordered chain forest, together with the sets $P$ and $L$, after each iterative
step in Algorithm 1 is described below:

  * •

$[1,5,3]^{2}[2]^{2}[4,7]^{1}$, $P=\varnothing$, $L=[1,2,3,4,5,7]$

  * •

$[2,7,4]^{1}[3]^{2}[5,1]^{1}$, $P=\\{1\\}$, $L=[2,3,4,5,7,1]$

  * •

$[3,1,5][4]^{2}[7,2]^{1}$, $P=\\{1,2\\}$, $L=[3,4,5,7,1,2]$

  * •

$[3,1,5][7]^{1}[2,4]^{1}$, $P=\\{1,2,4\\}$, $L=[3,5,7,1,2,4]$

  * •

$[3,1,5][2][4,7]^{1}$, $P=\\{1,2,4,7\\}$, $L=[3,5,1,2,4,7]$

Thus, $(F^{\prime}_{1},w^{\prime}_{1})=[3,1,5][2][4,7]^{1}$ and
$\phi((F,w,\\{6,8\\}))=([3,1,5][2][4,7]^{1}[8][6]^{1},\\{6,8\\})$.

###  4.2. Properties of the map $\phi$

In the following, we note a few facts pertaining to Algorithm 1 that will be
used to understand $\phi$ and prove that it is a bijection (Propositions 4.9
and 4.10). These will serve as the foundations for proving Conjecture 3.6.

######  Lemma 4.4.

Let $(F,w,A)\in DCF_{q}(s)$, and let $(F_{1},w_{1})$ be its non-distinguished
part. After the $i^{th}$ iteration of the steps in Algorithm 1 with input
$(F_{1},w_{1})$, the blocks of $F_{1}$ are ordered increasingly by their
leaders according to $L_{i}$, and the leader of each block is the smallest
element of that block according to $L_{i}$.

###### Proof.

We proceed by induction. Let
$B_{1,i}^{\beta_{1,i}}\cdots{B_{k,i}^{\beta_{k,i}}}$ denote the valued ordered
chain forest and $L_{i}$ be the ordered list $L$ obtained after the $i^{th}$
iteration of the steps in Algorithm 1 with input $(F_{1},w_{1})$. By
definition, the statement of the lemma is true for
$(F_{1},w_{1})=B_{1,0}^{\beta_{1,0}}\cdots{B_{k,0}^{\beta_{k,0}}}$. Assume
that the statement is true for
$B_{1,i}^{\beta_{1,i}}\cdots{B_{k,i}^{\beta_{k,i}}}$. Let $j$ be the smallest
index such that $B_{j,i}$ contains a non-processed element and
$\beta_{j,i}>0$, and let $a$ be the leader of $B_{j,i}$. In the $(i+1)^{th}$
iteration, the blocks to the left of $B_{j,i}$ remain unchanged, hence
$B_{1,i+1},\dots,B_{j-1,i+1}$ are ordered increasingly by their leaders and
the leader of each of these blocks is the smallest element in that block
according to $L_{i+1}$. Let $u_{1}<_{L_{i}}\dots<_{L_{i}}u_{x}$ be the
elements lying either in $B_{j,i}$ or in a block to the right of $B_{j,i}$,
and consider the set $S=\\{u_{1},\dots,u_{x}\\}$. In particular, $a=u_{1}$
since all the elements $e$ lying in $B_{j,i}$ or in a block to the right of
$B_{j,i}$, are at least as large as their block leader according to $L_{i}$,
and hence at least as large as $a$ according to $L_{i}$. Then the blocks
$B_{j,i+1},\dots,B_{k,i+1}$ are obtained by applying the map $u_{y}\mapsto
u_{y+1}$ (in particular $u_{x}\mapsto a$), and $L_{i+1}$ is obtained from
$L_{i}$ by setting $a$ to be the last entry. Therefore, the relative order of
the elements of $S$ as they appear from left to right in the blocks
$B_{j,i},\dots,B_{k,i}$ according to $L_{i}$ is the same as the relative order
that these elements appear from left to right in the blocks
$B_{j,i+1},\dots,B_{k,i+1}$ according to $L_{i+1}$. Thus, the statement of the
lemma holds for
$B_{1,i+1}^{\beta_{1,i+1}}\cdots{B_{k,i+1}^{\beta_{k,{i+1}}}}$, which
completes the proof. ∎

######  Lemma 4.5.

Let $(F,w,A)\in DCF_{q}(s)$, and let $(F_{1},w_{1})$ be its non-distinguished
part. In the iterations of the steps of Algorithm 1 with input
$(F_{1},w_{1})$, the processed elements are processed in increasing order.

###### Proof.

We are interested in the case that at least two elements get processed. Let
$p_{i}$ be the element processed in the $i^{th}$ iteration ($i\geq 1$) and
assume that Algorithm 1 requires at least one more iteration of steps (1)-(6)
to terminate. Let $B_{1,i}^{\beta_{1,i}}\cdots{B_{k,i}^{\beta_{k,i}}}$ be the
valued ordered chain forest obtained after the $i^{th}$ iteration. Let $j$ be
the smallest index such that $B_{j,i}$ contains a non-processed element and
$\beta_{j,i}>0$, and let $a$ be the leader of $B_{j,i}$. Note that $a$ is not
a processed element since it is the smallest element in its block according to
$L_{i}$ by Lemma 4.4. Then $p_{i}$ is the leader of some block of the form
$B_{j^{\prime},i-1}$ where $j^{\prime}\leq j$ since if it was the leader of
some block to the right of $B_{j,i-1}$, then it would not have been the left-
most block satisfying the conditions in step (1) after the $(i-1)^{th}$
iteration of the steps in Algorithm 1 (note that if $i-1=0$, it means that no
element has been processed yet). By Lemma 4.4, the leader of $B_{j,i-1}$ is
larger or equal to $p_{i}$ according to $L_{i-1}$ (they are equal if
$j^{\prime}=j$). Since step (2) of Algorithm 1 ensures the leader of
$B_{j,i}$, $a$, is larger than the leader of $B_{j,i-1}$ according to $L_{i}$,
the fact that $a$ was not processed in the $i^{th}$ iteration implies that
$p_{i}<a$. This completes the proof. ∎

######  Lemma 4.6.

Let $(F,w,A)\in DCF_{q}(s)$, and let $(F_{1},w_{1})$ be its non-distinguished
part. After any iterative step in Algorithm 1 with input $(F_{1},w_{1})$, each
element that contributes weight to some block is a processed element.
Conversely, each processed element either contributes weight to some block or
is contained in a block with only processed elements.

###### Proof.

We proceed by induction. Let
$B_{1,i}^{\beta_{1,i}}\cdots{B_{k,i}^{\beta_{k,i}}}$ be the valued ordered
chain forest obtained after the $i^{th}$ iteration. Assume that the statement
is true for $B_{1,i}^{\beta_{1,i}}\cdots{B_{k,i}^{\beta_{k,i}}}$. Here, $i=0$
corresponds to no element having been processed yet, and we restrict to the
case that at least one element gets processed. Let $j$ be the smallest index
such that $B_{j,i}$ contains a non-processed element and $\beta_{j,i}>0$, and
let $a$ be the leader of $B_{j,i}$. Note that $a$ is not a processed element
since it is the smallest element in its block according to $L_{i}$ by Lemma
4.4. In the $(i+1)^{th}$ iteration, the blocks to the left of $B_{j,i}$ remain
unchanged, so the elements that contribute weight to one of
$B_{1,i+1},\dots,B_{j-1,i+1}$ are processed elements (if any). Let
$u_{1}<_{L_{i}}\dots<_{L_{i}}u_{x}$ be the elements lying either in $B_{j,i}$
or in a block to the right of $B_{j,i}$ and let $S=\\{u_{1},\dots,u_{x}\\}$;
in particular, $a=u_{1}$, as discussed in the proof of Lemma 4.4. Furthermore,
by Lemma 4.4, each leader of the blocks $B_{j,i},\dots,B_{k,i}$ that is not a
processed element is larger than (or equal to) $a$. Thus, if a processed
element $p\in S$ in one of the blocks $B_{j,i+1},\dots,B_{k,i+1}$ that is not
a block consisting only of processed elements, then $p$ contributes weight to
this block since its leader is larger than $a$ and $p\leq a$ by Lemma 4.5.

Additionally, if an element contributes weight to a block of an ordered chain
forest formed after some iterative step in Algorithm 1 with corresponding
ordering $L$, then by Lemma 4.4 this element must be a processed element;
otherwise the leader of this block would not be the smallest element in the
block according to $L$.

This completes the proof. ∎

If $(F,w,A)$ is a valued $A$-distinguished ordered chain forest, with non-
distinguished part $(F_{1},w_{1})$ where $\sum_{B\in B(F_{1})}w_{1}(B)=q_{1}$,
then Lemma 4.6 provides a way to recover the valued ordered chain forest
obtained after the $(i-1)^{th}$ iterative step in Algorithm 1 with input
$(F_{1},w_{1})$ from the valued ordered chain forest obtained after the
$i^{th}$ iteration. The following Lemma describes precisely how we may do
this.

######  Lemma 4.7.

Let $(F,w,A)$ be a valued $A$-distinguished ordered chain forest of $[s]$,
with non-distinguished part $(F_{1},w_{1})$ where $\sum_{B\in
B(F_{1})}w_{1}(B)=q_{1}$. Let $(F_{1,i},w_{1,i})=B_{1,i}^{\beta_{1,i}}\cdots
B_{r,i}^{\beta_{r,i}}$ be the valued ordered chain forest obtained after the
$i^{th}$ iterative step in Algorithm 1 with input $(F_{1},w_{1})$. Then the
valued ordered chain forest obtained after the $(i-1)^{th}$ iteration can be
obtained by the following process:

  1. (1)

Find the integer $j$ such that
$\sum_{u=1}^{r-j}\textrm{weight}(B_{u,i})+\sum_{u=r-j+1}^{r}|B_{u,i}|+\sum_{u=1}^{r}\beta_{u,i}=q_{1}$.
We note that the $j$ blocks $B_{r-j+1,i},\dots,B_{r,i}$ are precisely the
blocks that consist only of processed elements.

  2. (2)

Determine the set $P$ of processed elements after the $i^{th}$ iteration to
consist of the elements that contribute weight to some block together with the
elements of last $j$ blocks of $B_{1,i}^{\beta_{1,i}}\cdots
B_{r,i}^{\beta_{r,}}$. Determine $L_{i}$ to consist of the elements not in $P$
ordered naturally, followed by the elements in $P$ ordered naturally.

  3. (3)

Take the largest processed element $p$, and take the leftmost block $B_{v,i}$
$(1\leq v\leq r)$ whose leader is either greater than $p$ (in the natural
order) and not processed or less than (or equal to) $p$ and is processed.

  4. (4)

Let $u_{1}<_{L_{i}}\cdots<_{L_{i}}u_{t}$ be all the elements that appear
either in $B_{v,i}$ or in blocks to the right of $B_{v,i}$ (note that
$p=u_{t}$). Apply the map $u_{x}\mapsto u_{x-1}$ where $u_{1}\mapsto u_{t}$
(fix $F_{1}\setminus\\{u_{1},...,u_{t}\\}$).

  5. (5)

Form $L_{i-1}$ by modifying $L_{i}$ so that the ordering among the non-
processed elements (including $u_{t}$) is natural.

  6. (6)

For $u\neq v$, $\beta_{u,i-1}=\beta_{u,i}$ and $\beta_{v,i-1}=\beta_{v,i}+1$.

###### Proof.

Note that in each iterative step in Algorithm 1, the number of processed
elements increases by 1 and the weight of some block decreases by 1. This
implies that the total sum between the number of processed elements and the
sum of the values of the blocks is fixed, equaling $q_{1}$ at each iteration.
Since the blocks are ordered increasingly (by their leaders) according to
$L_{i}$ by Lemma 4.4, there is some $j$ ($0\leq j\leq r$) such that the last
$j$ blocks $B_{r-j+1},\dots,B_{r}$ consist only of processed elements, and the
remaining blocks contain some element that is not processed. By Lemma 4.6, the
processed elements either lie in one of the last $j$ blocks or contribute
weight to some block. Combining everything discussed, we have that

$\sum_{u=1}^{r-j}\textrm{weight}(B_{u,i})+\sum_{u=r-j+1}^{r}|B_{u,i}|+\sum_{u=1}^{r}\beta_{u,i}=q_{1}.$

Of the processed elements after the $i^{th}$ iteration, the largest, say $p$,
must be the element that was processed in the $i^{th}$ iteration by Lemma 4.5.
In particular, $p$ was not a processed element after the $(i-1)^{th}$
iteration. Instead, it was the leader of some block, and this block must be
$B_{v,i-1}$. Otherwise, the left-most block of $F_{1,i}$ whose leader is
either greater than $p$ (in the natural order) and not processed or less than
(or equal to) $p$ and is processed is either to the left of $B_{v,i}$ (if $p$
is the leader of a block to the left of $B_{v,i-1}$) or to the right of
$B_{v,i}$ (if $p$ is the leader of a block to the right of $B_{v,i-1}$).

Then $F_{1,i}$ was obtained by applying the map in step (2) of Algorithm 1
which is clearly reversed in step (4) of this lemma.

Finally, it is clear that $L_{i-1}$ can be formed as in step (5) and that
$\beta_{v,i-1}=\beta_{v,i}+1$ and $\beta_{u,i-1}=\beta_{u,i}$ for $u\neq v$. ∎

######  Example 4.8.

Let us follow the steps in Lemma 4.7 to determine the valued ordered chain
forest $(F_{1},w_{1})$ of weight 5 that is used as input in Algorithm 1 to
obtain the valued ordered chain forest

$(F_{1}^{\prime},w_{1}^{\prime})=[3,1,4][5,2,6][7][8]^{1}.$

The number of elements that contribute weight to some block (elements 1 and 2)
added to the sum of the values of $w_{1}^{\prime}$ over all blocks is $2+1=3$.
Since $(F_{1},w_{1})$ has weight 5, we must have exactly two processed
elements that are contained in blocks that consist only of processed elements,
which must be the rightmost blocks. In other words, the last two elements
appearing in $F_{1}^{\prime}$, namely, 7 and 8, must be processed elements.

We now perform the reverse iterations provided by Lemma 4.7 of each iterative
step in Algorithm 1, which resulted in $(F_{1}^{\prime},w_{1}^{\prime})$:

  * •

$[3,1,4][5,2,6][7][8]^{1}$, $P=\\{1,2,7,8\\}$, $L=[3,4,5,6,1,2,7,8]$

  * •

$[3,1,4][5,2,6][8]^{1}[7]^{1}$, $P=\\{1,2,7\\}$, $L=[3,4,5,6,8,1,2,7]$

  * •

$[3,1,4][5,2,6][7]^{2}[8]^{1}$, $P=\\{1,2\\}$, $L=[3,4,5,6,7,8,1,2]$

  * •

$[2,8,3]^{1}[4,1,5][6]^{2}[7]^{1}$, $P=\\{1\\}$, $L=[2,3,4,5,6,7,8,1]$

  * •

$[1,7,2]^{2}[3,8,4][5]^{2}[6]^{1}$, $P=\varnothing$, $L=[1,2,3,4,5,6,7,8]$

Therefore, $(F_{1},w_{1})=[1,7,2]^{2}[3,8,4][5]^{2}[6]^{1}$.

The fact that each iterative step in Algorithm 1 can be reversed implies that
the map $\phi$ is a bijection, and therefore has an associated inverse
$\phi^{-1}$. We also emphasize that the blocks of an element $(F,w,A)\in
DCF_{q}(s)$ and the blocks of $\phi((F,w,A))$ have the same lengths as they
appear in order. In particular, writing
$\phi((F,w,A))=(F^{\prime},w^{\prime},A)$, we have that $F$ and $F^{\prime}$
have the same number of blocks and $\gamma(F,\ell)=\gamma(F^{\prime},\ell)$
for every $0\leq\ell\leq s-1$. Thus, we have the following result.

######  Proposition 4.9.

The map $\phi:DCF_{q}(s)\longrightarrow\phi(DCF_{q}(s))$ is a bijection. In
particular, $\phi:DCF_{q,k,\ell,m}(s)\longrightarrow\phi(DCF_{q,k,\ell,m}(s))$
is a bijection, for $1\leq m\leq k\leq s$, $0\leq\ell\leq s-1$, $0\leq q$.

In fact, we can determine the image of $DCF_{q,k,\ell,m}(s)$ through $\phi$
completely, as described in the following proposition.

######  Proposition 4.10.

Let $1\leq m\leq k\leq s,\ 0\leq\ell\leq s-1,\ 0\leq q$ be integers. An
element $(F,w,A)$ is contained in $\phi(DCF_{q,k,\ell,m}(s))$ if and only if
$(F,w)=B_{1}^{\beta_{1}}\cdots B_{r}^{\beta_{r}}C_{1}^{\gamma_{1}}\cdots
C_{p}^{\gamma_{p}}$ has the following properties. For some integer $0\leq
j\leq r$,

  1. (1)

The blocks $C_{1},\dots,C_{p}$ consist only of elements in $A$, and the
remaining blocks do not contain elements in $A$. The blocks
$C_{1},\dots,C_{p}$ are ordered decreasingly according to their leaders, and
the leader of each block $C_{i}$ is the smallest element in the block.

  2. (2)

The $j$ blocks $B_{r-j+1},\dots,B_{r}$ are naturally ordered, and the leader
of each of these blocks is the smallest element in that block.

  3. (3)

The blocks $B_{1},\dots,B_{r-j}$ are naturally ordered, and
$\beta_{1}=\dots=\beta_{r-j}=0$.

  4. (4)

$\sum_{i=1}^{r-j}\textrm{weight}(B_{i})+\sum_{i=j-r+1}^{r}(|B_{i}|+\beta_{i})+|A|+\sum_{i=1}^{p}\gamma_{i}=q$.

  5. (5)

$F$ has $k$ blocks and $\gamma(F,\ell)=m$.

###### Proof.

Let $(G,v,A)=\phi^{-1}((F,w,A))$ be such that $(G,v,A)\in
DCF_{q,k,\ell,m}(s)$. We have that

$|A|+\sum_{B\in B(G)}v(B)=q.$

At each iterative step in Algorithm 1, taking as input the non-distinguished
part of $(G,v,A)$, an element is processed and the value of $v(B)$ decreases
by 1 for some block $B$$\in B(G)$. Therefore, if $P$ is the set of processed
elements when Algorithm 1 terminates with output $(F,w)$, we have that

$|P|+\sum_{i=1}^{r}\beta_{i}+|A|+\sum_{i=1}^{p}\gamma_{i}=q.$

Additionally, by Lemma 4.5, the processed elements are processed in increasing
order, so the resulting ordering $L$ is given by taking the non-processed
elements in increasing order followed by the processed elements in increasing
order. Since by Lemma 4.4, the blocks $B_{1},\dots,B_{r}$ are ordered
increasingly according to $L$, it follows that if $j$ is the number of blocks
that consist only of processed elements, then these blocks are
$B_{r-j+1},\dots,B_{r}$, and are naturally ordered by their leaders, which are
the smallest elements in their respective blocks. The remaining processed
elements contribute weight to one of the blocks $B_{1},\dots,B_{r-j}$. We also
have that $\beta_{1}=\cdots=\beta_{r-j}=0$, otherwise Algorithm 1 would not
have terminated since the blocks $B_{1},\dots,B_{r-j}$ would contain elements
which are not processed.

Therefore, we have that
$|P|=\sum_{i=1}^{r-j}\textrm{weight}(B_{i})+\sum_{i=j-r+1}^{r}|B_{i}|$, hence

$\displaystyle q=$
$\displaystyle|P|+\sum_{i=1}^{r}\beta_{i}+\sum_{i=1}^{p}\gamma_{i}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{r-j}\textrm{weight}(B_{i})+\sum_{i=j-r+1}^{r}(|B_{i}|+\beta_{i})+|A|+\sum_{i=1}^{p}\gamma_{i}.$

Thus, $(F,w,A)$ satisfies (2) – (4). Moreover, (1) and (5) follow directly
from the definitions.

On the other hand, if $(F,w,A)$ satisfies (1) – (5), then by similar lines of
reasoning, if we repeatedly apply the process described in Lemma 4.7 to
$(F,W,A)$, we will obtain an element of $DCF_{q,k,\ell,m}(s)$. ∎

We are now ready to prove Conjecture 3.6.

##  5\. Panhandle matroids are Ehrhart positive

This section contains a proof of Conjecture 3.6 (also printed below). We note
that the validity of Conjecture 3.6 was shown in [HMM+23] to imply the Ehrhart
positivity of panhandle matroids (Theorem 6.2). The proof of Conjecture 3.6
has an inclusion-exclusion flavor, utilizing the combinatorial interpretation
discussed in Proposition 3.11. In particular, Proposition 3.11 provides an
interpretation for each of the summands in Conjecture 3.6 in terms of valued
$A$-distinguished ordered chain forests. In the proof we show that most of the
summand terms cancel each other out (in a nontrivial way). The only exception
is the summand for $i=0$, which only partly cancels out. The non-canceling
part is exactly the set of ordered chain forests we are after. The proof is
presented in detail below.

######  Conjecture 3.6.

Let $1\leq m\leq k\leq s$, $q\geq 0$, and $0\leq\ell\leq s-1$ be integers.
Then the number of naturally ordered chain forests $F$ of $[s]$ with $k$
blocks and weight $q$ such that $\gamma(F,\ell)=m$ is given by

$|\operatorname{\mathsf{CF}}(q,s,k,\ell,m)|=\sum_{i=0}^{q}(-1)^{i}\binom{s}{i}P^{s-\ell-m}_{-i+1,s-1-\ell-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\binom{k-1+q-i}{k-1}.$

###### Proof of Conjecture 3.6.

Let $S$ consist of the elements
$(F^{\prime},w^{\prime},\varnothing)=\phi((F,w,\varnothing))$ in the image
$\phi(DCF_{q,k,\ell,m}(s))$, with the property that
$\sum_{i=1}^{k}\textrm{weight}(B_{i})=q$, where $F^{\prime}=B_{1}\cdots
B_{k}$. Note that since $\sum_{i=1}^{k}\textrm{weight}(B_{i})=q$, we have that
$j=0$ in item (2) of Proposition 4.10, $w^{\prime}$ is identically zero by
item (4), and the blocks are naturally ordered by item (3). Therefore, if
$\phi((F,w,\varnothing))=(F^{\prime},w^{\prime},\varnothing)$ is an element of
$S$, then in the iterations in Algorithm 1 with input $(F,w)$, there is no
appearance of a block consisting only of processed elements.

Given that $w^{\prime}$ is identically zero, we may identify
$(F^{\prime},w^{\prime},\varnothing)$ with $F^{\prime}$. Since
$F^{\prime}\in\operatorname{\mathsf{CF}}(q,s,k,\ell,m)$ by the discussion
above, and since every element of $\operatorname{\mathsf{CF}}(q,s,k,\ell,m)$
is in the image $\phi(DCF_{q,k,\ell,m}(s))$, $S$ is in bijection with
$\operatorname{\mathsf{CF}}(q,s,k,\ell,m)$. In particular,
$|S|=|\operatorname{\mathsf{CF}}(q,s,k,\ell,m)|$. We define $T$ to be the set
of elements $(F,w,\varnothing)\in DCF_{q,k,\ell,m}(s)$, such that
$\phi((F,w,\varnothing))\notin S$. Essentially, $T$ is the set of elements
$(F,w,\varnothing)$ where $\phi((F,w,\varnothing))$ has at least one block
consisting only of processed elements. By Proposition 3.11 and since $\phi$ is
a bijection on $DCF_{q,k,\ell,m}(s)$, we have that the term arising for $i=0$
in the sum in Conjecture 3.6 is equal to
$|\operatorname{\mathsf{CF}}(q,s,k,\ell,m)|+|T|.$

Thus, we have that
$\sum_{i=0}^{q}(-1)^{i}\binom{s}{i}P^{s-\ell-m}_{-i+1,s-\ell-1-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\binom{k-1+q-i}{k-1}$
is equal to

$\displaystyle\sum_{i=0}^{q}\sum_{A\in\binom{[s]}{i}}\sum_{(F,w,A)\in
DCF_{q,k,\ell,m}(s)}(-1)^{|B_{A}(F)|}$
$\displaystyle=|\operatorname{\mathsf{CF}}(q,s,k,\ell,m)|+|T|+\sum_{i=1}^{q}\sum_{A\in\binom{[s]}{i}}\sum_{(F,w,A)\in
DCF_{q,k,\ell,m}(s)}(-1)^{|B_{A}(F)|}.$

Hence, it suffices to show that

$|T|+\sum_{i=1}^{q}\sum_{A\in\binom{[s]}{i}}\sum_{(F,w,A)\in
DCF_{q,k,\ell,m}(s)}(-1)^{|B_{A}(F)|}=0.$

To this end, we define $N$ to be the set of elements $(F,w,A)\in
DCF_{q,k,\ell,m}(s)$ where $(-1)^{|B_{A}(F)|}=-1$ and $P$ to be the set of
elements $(F,w,A)$ where $(-1)^{|B_{A}(F)|}=1$ and either $(F,w,A)\in T$ or
$A\neq\varnothing$. In particular, each element in $N$ has an odd number of
blocks in its distinguished part, and each element in $P$ has an even number
of blocks in its distinguished part.

Now, we define a bijection $f:N\longrightarrow P$, which will complete the
proof since the existence of $f$ implies that the elements contributing “$+1$”
and the elements contributing “$-1$” cancel out in pairs in the sum

$|T|+\sum_{i=1}^{q}\sum_{A\in\binom{[s]}{i}}\sum_{(F,w,A)\in
DCF_{q,k,\ell,m}(s)}(-1)^{|B_{A}(F)|}.$

Let $(F,w,A)=(B_{1}^{\beta_{1}}\cdots
B_{r}^{\beta_{r}}C_{1}^{\gamma_{1}}\cdots C_{p}^{\gamma_{p}},A)$ be an element
of $N$ where the blocks $C_{1},\dots,C_{p}$ are precisely the blocks that
consist only of elements in $A$. Let
$\phi((F,w,A))=(B_{1}^{\prime\beta_{1}^{\prime}}\cdots
B_{r}^{\prime\beta_{r}^{\prime}}C_{1}^{\gamma_{1}}\cdots
C_{p}^{\gamma_{p}},A)$. We define the map $f$ via two distinguishing cases:

  1. (1)

If $j=0$ in item (2) of Proposition 4.10 applied to $\phi((F,w,A))$, or $j\geq
1$ and the leader of $C_{1}$ is greater than the leader of $B_{r}^{\prime}$,
then we define

$f((F,w,A))=\phi^{-1}((B_{1}^{\prime\beta_{1}^{\prime}}\cdots
B_{r}^{\prime\beta_{r}^{\prime}}C_{1}^{\gamma_{1}}\cdots
C_{p}^{\gamma_{p}},A\setminus C_{1})),$

where by a slight abuse of notation we associate $C_{1}$ with the set of its
elements;

  2. (2)

Otherwise, if $j\geq 1$ and the leader of $C_{1}$ is less than the leader of
$B_{r}^{\prime}$ (or $A=\varnothing$), then we define

$f((F,w,A))=\phi^{-1}((B_{1}^{\prime\beta_{1}^{\prime}}\cdots
B_{r}^{\prime\beta_{r}^{\prime}}C_{1}^{\gamma_{1}}\cdots
C_{p}^{\gamma_{p}},A\cup B_{r}^{\prime})).$

Again, we are associating $B_{r}^{\prime}$ with the set of its elements.

In the first case, $f((F,w,A))$ has 1 less block in its distinguished part,
and in the second case, $f((F,w,A))$ has 1 more block in its distinguished
part. Hence, $f((F,w,A))\in P$ in both cases. Additionally, it follows from
Proposition 4.10 that $(B_{1}^{\prime\beta_{1}^{\prime}}\cdots
B_{r}^{\prime\beta_{r}^{\prime}}C_{1}^{\gamma_{1}}\cdots
C_{p}^{\gamma_{p}},A\setminus C_{1})$ in case (1) and
$(B_{1}^{\prime\beta_{1}^{\prime}}\cdots
B_{r}^{\prime\beta_{r}^{\prime}}C_{1}^{\gamma_{1}}\cdots
C_{p}^{\gamma_{p}},A\cup B_{r}^{\prime})$ in case (2) are elements of
$\phi(DCF_{q,k,\ell,m}(s))$, i.e., $f$ is well-defined.

We now show that the map $f$ is injective. First note that if
$f((F,w,A))=f((G,v,E))$ and the distinguished parts of $(F,w,A)$ and $(G,v,E)$
have the same number of blocks, then the same case i.e., (1) or (2) in the
definition of $f$ applies to both and it follows immediately from the fact
that $\phi$ is a bijection that $(F,w,A)=(G,v,E)$. Therefore, we can assume
without loss of generality that the distinguished part of $(F,w,A)$ has $p$
blocks and the distinguished part of $(G,v,E)$ has $p-2$ blocks and that case
(1) in the definition of $f$ applies to $(F,w,A)$ and case (2) applies to
$(G,v,E)$. Then, writing

$\phi((F,w,A))=(B_{1}^{\prime\beta_{1}^{\prime}}\cdots
B_{r}^{\prime\beta_{r}^{\prime}}C_{1}^{\gamma_{1}}\cdots
C_{p}^{\gamma_{p}},A),$

where the blocks $C_{i}$ are the blocks containing elements of $A$, we have
that

$f((F,w,A))=\phi^{-1}((B_{1}^{\prime\beta_{1}^{\prime}}\cdots
B_{r}^{\prime\beta_{r}^{\prime}}C_{1}^{\gamma_{1}}\cdots
C_{p}^{\gamma_{p}},A\setminus C_{1})).$

Hence,

$\phi(f((F,w,A)))=(B_{1}^{\prime\beta_{1}^{\prime}}\cdots
B_{r}^{\prime\beta_{r}^{\prime}}C_{1}^{\gamma_{1}}\cdots
C_{p}^{\gamma_{p}},A\setminus C_{1}),$

and since $\phi(f((G,v,E)))=\phi(f((F,w,A)))$ we must have that

$\phi((G,v,E))=(B_{1}^{\prime\beta_{1}^{\prime}}\cdots
B_{r}^{\prime\beta_{r}^{\prime}}C_{1}^{\gamma_{1}}\cdots
C_{p}^{\gamma_{p}},A\setminus(C_{1}\cup C_{2})).$

By item (4) of Proposition 4.10 applied to $\phi((F,w,A))$, for $0\leq j\leq
r$, we have that

$\sum_{i=1}^{j-r}\textrm{weight}(B_{i}^{\prime})+\sum_{i=j-r+1}^{r}(|B_{i}^{\prime}|+\beta_{i}^{\prime})+|A|+\sum_{i=1}^{p}\gamma_{i}=q,$

or equivalently,

$\sum_{i=1}^{j-r}\textrm{weight}(B_{i}^{\prime})+\sum_{i=j-r+1}^{r}(|B_{i}^{\prime}|+\beta_{i}^{\prime})+(|C_{1}|+\gamma_{1})+(|C_{2}|+\gamma_{2})+|A\setminus(C_{1}\cup
C_{2})|+\sum_{i=3}^{p}\gamma_{i}=q.$

Thus, by items (4) and (2) of Proposition 4.10 applied to $\phi((G,v,E))$, we
have that there is some $j^{\prime}\geq 2$ such that the last $j^{\prime}$
blocks among
$B_{1}^{\prime\beta_{1}^{\prime}},\dots,B_{r}^{\prime\beta_{r}^{\prime}},C_{1}^{\gamma_{1}},C_{2}^{\gamma_{2}}$
of $\phi((G,v,E))$ are ordered increasingly according to their leaders. In
particular, the leader of $C_{1}$ is less than the leader of $C_{2}$. However,
the fact that these are the first two blocks in the distinguished part of
$\phi((F,w,A))$ implies that the leader of $C_{1}$ is greater than the leader
of $C_{2}$. This is a contradiction and completes the proof of the injectivity
of $f$.

Although it is possible to show directly that $f$ is a bijection, we present a
different argument to complete the proof. Let us fix suitable $s,k,l$ and
allow $m$ to vary between $1$ and $k$. For $1\leq m\leq k$, the fact that $f$
is an injection implies that, for some $p_{m}\geq 0$,

$\sum_{i=0}^{q}(-1)^{i}\binom{s}{i}P^{s-\ell-m}_{-i+1,s-\ell-1-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\binom{k-1+q-i}{k-1}=|\operatorname{\mathsf{CF}}(q,s,k,\ell,m)|+p_{m}.$

Specifically, $p_{m}=|P|-|f(N)|$. Hence, if we prove that $p_{m}=0$, then
$f(N)=P$ and it follows that $f$ is a bijection.

Summing over $m$, we have that

$\displaystyle\sum_{m=0}^{k}\sum_{i=0}^{q}(-1)^{i}\binom{s}{i}P^{s-\ell-m}_{-i+1,s-\ell-1-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\binom{k-1+q-i}{k-1}$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{q}(-1)^{i}\binom{s}{i}\sum_{m=0}^{k}\left(P^{s-\ell-m}_{-i+1,s-\ell-1-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\right)\binom{k-1+q-i}{k-1}$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{q}(-1)^{i}\binom{s}{i}P^{s-k}_{-i+1,s-1-i}\binom{k-1+q-i}{k-1}$
$\displaystyle=$
$\displaystyle\sum_{m=0}^{k}\left(|\operatorname{\mathsf{CF}}(q,s,k,\ell,m)|+p_{m}\right)$
$\displaystyle=$
$\displaystyle|\operatorname{\mathsf{CF}}(q,s,k)|+\sum_{m=0}^{k}p_{m}.$

However, we know from Equation (3) that

$|\operatorname{\mathsf{CF}}(q,s,k)|=\sum_{i=0}^{q}(-1)^{i}\binom{s}{i}P^{s-k}_{-i+1,s-1-i}\binom{k-1+q-i}{k-1},$

which implies that $\sum_{m=0}^{k}p_{m}=0$, proving that $f$ is indeed a
bijection. Therefore, the result follows. ∎

This completes the proof of Conjecture 3.6, and with it the proof of Theorem
1.2, namely, Ehrhart positivity of panhandle matroids.

##  6\. Ehrhart-coefficient upper-bound conjecture for paving matroids

Recall that $U_{r,n}$ denotes the uniform matroid with rank $r$ and $n$
elements, matroid polytope $\mathcal{P}_{U_{r,n}}$ is precisely the
hypersimplex $\Delta_{r,n}$. It is known that the Ehrhart polynomial of
$\mathcal{P}_{U_{r,n}}$ has positive coefficients [Fer21]. The uniform matroid
$U_{r,n}$ is the unique matroid with rank $r$ and $n$ elements and
$\binom{n}{r}$ bases. On the other hand, by a result of Dinolt [Din71] and
Murty [Mur71], there is a unique connected matroid, which we have referred to
as the minimal matroid and denoted $T_{r,n}$, with rank $r$ and $n$ elements
that has the minimum possible number of bases.

In what follows, for two polynomials $p(t)$ and $q(t)$ of degree $n$,
$p(t)\preceq q(t)$ means that the $d^{{th}}$-coefficient of $p(t)$ is bounded
above by the $d^{{th}}$-coefficient of $q(t)$, for every $0\leq d\leq n$. In
[Fer22b], Ferroni conjectured the following.

######  Conjecture 6.1 (Conjecture 1.5 in [Fer22b]).

For a connected matroid $M$ with rank $r$ and $n$ elements,

$\operatorname{\mathsf{ehr}}_{T_{r,n}}(t)\preceq\operatorname{\mathsf{ehr}}_{M}(t)\preceq\operatorname{\mathsf{ehr}}_{U_{r,n}}.$

It is known that the lower-bound portion of the conjecture
$\operatorname{\mathsf{ehr}}_{T_{r,n}}(t)\preceq\operatorname{\mathsf{ehr}}_{M}(t)$
is not true in general as Ferroni himself proved that there are matroids whose
Ehrhart polynomials have negative coefficients [Fer22a], while the Ehrhart
polynomials of minimal matroids have positive coefficients [Fer22b]. However,
at the time of writing, there are no counterexamples to the upper-bound
portion of the conjecture,
$\operatorname{\mathsf{ehr}}_{M}(t)\preceq\operatorname{\mathsf{ehr}}_{U_{r,n}}$.

In this section, building on the work in [HMM+23], we show that the upper-
bound portion of Conjecture 6.1 holds when $M$ is a paving matroid. In
[HMM+23], a formula for the Ehrhart polynomial of a relaxation of $M$ was
determined in terms of $\operatorname{\mathsf{ehr}}_{M}(t)$, which is
presented in the following theorem.

######  Theorem 6.2 (Theorem 5.9 in [HMM+23]).

Let $M$ be a rank $r$ matroid with ground set $[n]$ and let $H$ be a stressed
hyperplane such that $|H|=s\geq r$. Then

$\displaystyle\operatorname{\mathsf{ehr}}_{\operatorname{Rel}_{H}(M)}(t)=\operatorname{\mathsf{ehr}}_{M}(t)+\frac{n-s}{(n-1)!}\binom{t-1+n-s}{n-s}\psi_{r,s,n}(t)$

where

$\psi_{r,s,n}(t)=\sum_{i=0}^{s-r}(-1)^{i}\binom{s}{i}\sum_{\ell=0}^{s-1}(n-2-\ell)!\ell!\binom{s-2-\ell-i+t(s-r-i+1)}{s-1-\ell}\binom{s-1-i+t(s-r-i)}{\ell}.$

For our purposes, the significance of Theorem 6.2 is that it implies that if
the polynomial

$\binom{t-1+n-s}{n-s}\psi_{r,s,n}(t)$

has nonnegative coefficients for all $r\leq s\leq n-1$, then

$\operatorname{\mathsf{ehr}}_{M}(t)\preceq\operatorname{\mathsf{ehr}}_{\operatorname{Rel}_{H}(M)}(t).$

Since $\binom{t-1+n-s}{n-s}$ is a polynomial with nonnegative coefficients, it
suffices to show that $\psi_{r,s,n}(t)$ has nonnegative coefficients.

Combining the previous result and the following lemma about relaxations of
paving matroids, which follows from Propositions 2.3 and 2.5, we can deduce
that Ferroni’s upper-bound conjecture follows for the class of paving matroids
from showing the nonnegativity of $\psi_{r,s,n}(t)$.

######  Lemma 6.3 (Corollary 3.17 in [FNV22]).

Let $M$ be a paving matroid with rank $r$ on the ground set $[n]$. The uniform
matroid $U_{r,n}$ is obtained after relaxing each (stressed) hyperplane of
$M$.

In [HMM+23], it was shown that $\psi_{r,s,n}(t)$ has nonnegative coefficients
if the expression given by

(7)
$\sum_{i=0}^{q}(-1)^{i}\binom{s}{i}P^{s-\ell-m}_{-i,s-\ell-2-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\binom{k-1+q-i}{k-1}$

is nonnegative for all $k\geq 1$, $1\leq m\leq k$, $q\geq 0$ and
$0\leq\ell\leq s-1$. Thus, we have the following.

######  Observation 6.4.

If for all integers $k\geq 1$, $1\leq m\leq k$, $q\geq 0$ and $0\leq\ell\leq
s-1$, the expression

$\sum_{i=0}^{q}(-1)^{i}\binom{s}{i}P^{s-\ell-m}_{-i,s-\ell-2-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\binom{k-1+q-i}{k-1}$

is nonnegative, then for any paving matroid $M$ with rank $r$ on ground set
$[n]$, we have that

$\operatorname{\mathsf{ehr}}_{M}(t)\preceq\operatorname{\mathsf{ehr}}_{U_{r,n}}(t).$

In what follows, we state and prove Theorem 6.7, affirming that expression (7)
is nonnegative. Specifically, we give a combinatorial interpretation for this
expression similar to that given in Conjecture 3.6. Considering that the above
expression is so similar to the expression in Conjecture 3.6, many of the
arguments are analogous.

Another consequence of Theorem 6.7 is the following, which confirms Conjecture
6.2 in [HMM+23].

######  Corollary 6.5 (Conjecture 6.2 in [HMM+23]).

Let $M$ be a matroid with rank $r$ and let $H$ be a stressed hyperplane with
$|H|\geq r$. If $M$ is Ehrhart positive, then so is
$\operatorname{Rel}_{H}(M)$.

###### Proof.

Theorem 6.7 and Observation 6.4 imply that $\psi_{r,s,n}(t)$ has positive
coefficients for all $r\leq s\leq n-1$. It then follows by Theorem 6.2 that
$\operatorname{Rel}_{H}(M)(t)$ has positive coefficients. ∎

In the following definition, we introduce the combinatorial objects that
expression (7) enumerates. These objects may seem unnatural compared to the
naturally ordered chain forests from Conjecture 3.6, however, these are
precisely the objects that are relevant for the statement of Theorem 1.3. We
note that, unlike Conjecture 3.6, the authors of [HMM+23] did not conjecture a
combinatorial interpretation for expression (7). Rather, we are able to deduce
Theorem 1.3 by applying the reasoning from the proof of Conjecture 3.6 to
expression (7).

######  Definition 6.6.

Let $\operatorname{\mathsf{CF}}^{1}(q,s,k,\ell,m)$ be the number of ordered
chain forests $F$ of $[s]$ with $k$ blocks, and $\gamma(F,\ell)=m\geq 2$ with
the following properties. Writing $F=B_{1}\cdots B_{k-1}C_{1}$, we have:

  1. (1)

$1\in C_{1}$ and 1 is the leader of $C_{1}$,

  2. (2)

$\sum_{i=1}^{k-1}\textrm{weight}(B_{i})+|C_{1}|=q$,

  3. (3)

The blocks $B_{1},\dots,B_{k-1}$ are naturally ordered,

  4. (4)

The leader of the $(k-m+2)^{th}$ block is in the $(\ell+2)^{th}$ position.

We note that the reason we require $m\geq 2$ is due to the fact that if the
leader of a block is in the $(\ell+2)^{th}$ position, then some block ends at
the $(\ell+1)^{th}$ position. Hence, there are at least 2 blocks that end
after the $\ell^{th}$ position.

We prove the following theorem, which shows that the expression in question
enumerates the objects in Definition 6.6, thus proving Ferroni’s Ehrhart-
coefficient upper-bound conjecture for paving matroids.

######  Theorem 6.7.

Let $1\leq m\leq k\leq s$, $q\geq 0$, and $0\leq\ell\leq s-1$ be integers.
Then

$|\operatorname{\mathsf{CF}}^{1}(q+1,s+1,k+1,\ell,m+1)|=\sum_{i=0}^{q}(-1)^{i}\binom{s}{i}P^{s-\ell-m}_{-i,s-\ell-2-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\binom{k-1+q-i}{k-1}.$

We now outline a proof of Theorem 6.7. The proofs of the statements in this
section are analogous to those in Sections 3 and 4. Therefore, we frequently
omit the details and reference analogous results in previous sections.

######  Definition 6.8.

Let $1\leq m\leq k\leq s$, $q\geq 0$, and $0\leq\ell\leq s-1$ be integers. We
define $DCF^{1}_{q,k,\ell,m}(s)$ to be the set of valued $A$-distinguished
ordered chain forests $(F,w,A)\in DCF_{q,k,\ell,m}(s)$ that have the following
additional properties:

  1. (1)

$1\in A$,

  2. (2)

The leader of the $(k-m+2)^{th}$ block is in the $(\ell+2)^{th}$ position,

  3. (3)

For the block $B$ containing $1$, $w(B)=0$.

The following is analogous to Proposition 3.11.

######  Proposition 6.9.

Let $1\leq m\leq k\leq s$, $q\geq 0$, and $0\leq\ell\leq s-1$ be integers. Let
$T^{1}_{i}$ be the set of $i$-element subsets $A$ of $[s+1]$ such that $1\in
A$, and let $Z=DCF^{1}_{q+1,k+1,\ell,m+1}(s+1)$. Then

$\displaystyle(-1)^{i}\binom{s}{i}P^{s-\ell-m}_{-i,s-\ell-2-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}\binom{k-1+q-i}{k-1}=\sum_{A\in
T^{1}_{i+1}}\sum_{(F,w,A)\in Z}(-1)^{|B_{A}(F)|-1}.$

###### Proof.

The proof is analogous to the proof of Proposition 3.11. The quantity
$\binom{s}{i}$ is the number of ways to choose an $i+1$-element subset $A$ of
$[s+1]$ that contains 1. The quantity
$P^{s-\ell-m}_{-i,s-\ell-2-i}P^{\ell-(k-m)}_{s-\ell-i,s-1-i}$ is the sum of
all products of the form $i_{1}\cdots i_{s-\ell-m}\cdot j_{1}\cdots
j_{\ell-(k-m)}$ where

$-i\leq i_{1}<\cdots<i_{s-\ell-m}\leq s-\ell-2-i$

and

$s-\ell-i\leq j_{1}<\cdots<j_{\ell-(k-m)}\leq s-1-i.$

In particular, among the numbers between $-i$ and $s-1-i$ (inclusive) there
are precisely $k$ numbers that do not get selected to be in the product. As in
the proof of Proposition 3.11, these $k$ numbers correspond to starting a
block at a specific position. Since, in addition, the first position is always
the beginning of some block, we have $k+1$ blocks in total. Additionally,
$s-\ell-1-i$ never appears in such a product, and since this is the
$(\ell+1)^{th}$ largest element among $-i,\dots,s-1-i$, this means we will
always start a block at the $(\ell+2)^{th}$ position (again following the
proof of Proposition 3.11). Moreover, since there are $k-m$ numbers greater
than $s-\ell-1-i$ that do not appear in the product, it follows that there are
$k-m+1$ blocks (including the block starting at the first position) that come
before the block starting at the $(\ell+2)^{th}$ position. Hence, the block
starting at the $(\ell+2)^{th}$ position is the $(k-m+2)^{th}$ block.

The sign of such a product is given by $(-1)^{i+1-B_{A}}$ where $B_{A}$ is the
number of blocks that are filled with elements of $A$. Together with the
$(-1)^{i}$ term, we have that the product $(-1)^{i}i_{1}\cdots
i_{s-\ell-m}\cdot j_{1}\cdots j_{\ell-(k-m)}$ comes with the sign
$(-1)^{|B_{A}|-1}$.

Finally, the quantity $\binom{k-1+q-i}{k-1}$ is the number of ways to assign
nonnegative values to the blocks that do not contain 1. Thus, by a similar
reasoning as in the proof of Proposition 3.11, we obtain the result. ∎

The following statements are very similar to Propositions 4.9 and 4.10, and we
omit the proofs.

######  Proposition 6.10.

The map
$\phi:DCF^{1}_{q,k,\ell,m}(s)\longrightarrow\phi(DCF^{1}_{q,k,\ell,m}(s))$ is
a bijection.

######  Proposition 6.11.

An element $(F,w,A)$ is contained in $\phi(DCF^{1}_{q,k,\ell,m}(s))$ if and
only if $(F,w)=B_{1}^{\beta_{1}}\cdots
B_{r}^{\beta_{r}}C_{1}^{\gamma_{1}}\cdots\text{{$C_{p-1}^{\gamma_{p-1}}$}}C_{p}^{0}$
has the following properties: For some integer $0\leq j\leq r$,

  1. (1)

The blocks $C_{1},\dots,C_{p}$ consist only of elements in $A$, and the
remaining blocks do not contain elements in $A$. The blocks
$C_{1},\dots,C_{p}$ are ordered decreasingly according to their leaders, and
the leader of each block $C_{i}$ is the smallest element in the block.

  2. (2)

$1\in C_{p}$.

  3. (3)

The $j$ blocks $B_{r-j+1},\dots,B_{r}$ are naturally ordered, and the leader
of each of these blocks is the smallest element in that block.

  4. (4)

The blocks $B_{1},\dots,B_{r-j}$ are naturally ordered, and
$\beta_{1}=\dots=\beta_{r-j}=0$.

  5. (5)

$\sum_{i=1}^{r-j}\textrm{weight}(B_{i})+\sum_{i=j-r+1}^{r}(|B_{i}|+\beta_{i})+|A|+\sum_{i=1}^{p-1}\gamma_{i}=q$.

  6. (6)

$F$ has $k$ blocks and $\gamma(F,\ell)=m$.

  7. (7)

The leader of the $(k-m+2)^{th}$ block is in the $(\ell+2)^{th}$ position.

We now outline the proof of Theorem 6.7. Again, the proof is similar to the
proof of Conjecture 3.6, so we omit most of the details.

###### Proof of Theorem 6.7.

Let $Z=DCF^{1}_{q+1,k+1,\ell,m+1}(s+1)$. Let $S$ be the set of elements
$\phi((F,w,A))=B_{1}^{\beta_{1}}\cdots B_{k}^{\beta_{k}}C_{1}^{0}$ for some
$(F,w,A)\in DCF^{1}_{q+1,k+1,\ell,m+1}(s+1)$ where all the elements in $A$ are
contained in $C_{1}$ and $\sum_{i=1}^{k}\textrm{weight}(B_{i})+|A|=q+1$. By
Proposition 6.10, $\beta_{i}=0$ for all $i$, so we may essentially identify
$S$ with $\operatorname{\mathsf{CF}}^{1}(q+1,s+1,k+1,\ell,m+1)$. Notice that
each element $(F,w,A)$ with $\phi((F,w,A))\in S$ contributes a “$+1$” to the
sum

$\sum_{A\in T^{1}_{i+1}}\sum_{(F,w,A)\in Z}(-1)^{|B_{A}(F)|-1}$

appearing in Proposition 6.9.

Therefore, denoting $P$ to be the set of elements $(F,w,A)\in Z$ such that
$(-1)^{|B_{A}(F)|-1}=1$, and $N$ to be the set of elements $(F,w,A)\in Z$ such
that $(-1)^{|B_{A}(F)|-1}=-1$, it suffices to find a bijection $f:N\rightarrow
P\setminus\phi^{-1}(S)$. We may define $f$ in the exact same way as in the
proof of Conjecture 3.6. The fact that $f$ is an injection follows in the same
way as in the proof of Conjecture 3.6, and it is a routine check to see that
it is a bijection.

This completes the proof outline. ∎

## Acknowledgements

This work was initiated at the 2023 Graduate Research Workshop in
Combinatorics (GRWC). The authors thank the workshop organizers and the
University of Wyoming for fostering an excellent research atmosphere. We also
thank Luis Ferroni, Hsin-Chieh Liao, and Tyrrell McAllister for fruitful
conversations. Danai Deligeorgaki is partially supported by the Wallenberg
Autonomous Systems and Software Program (WASP) and by the Institute for
Mathematical and Statistical Innovation under NSF Grant No. DMS-1929348.
Daniel McGinnis is partially supported by the National Science Foundation
under DMS-839918 (RTG). Andrés R. Vindas-Meléndez is partially supported by
the National Science Foundation under Award DMS-2102921. This material is
based in part upon work supported by the National Science Foundation under
Grant No. DMS-1928930 and by the Alfred P. Sloan Foundation under grant
G-2021-16778, while Andrés R. Vindas-Meléndez was in residence at the Simons
Laufer Mathematical Sciences Institute (formerly MSRI) in Berkeley,
California, during the Fall 2023 semester.

## References

  * [ABD10] Federico Ardila, Carolina Benedetti, and Jeffrey Doker, _Matroid polytopes and their volumes_ , Discrete Comput. Geom. 43 (2010), no. 4, 841–854.
  * [Ash20] Ahmed Umer Ashraf, _Another approach to volume of matroid polytopes_ , arXiv e-prints (2020), arXiv:1812.09373.
  * [Bar06] Alexander Barvinok, _Computing the Ehrhart quasi-polynomial of a rational simplex_ , Math. Comp. 75 (2006), no. 255, 1449–1466.
  * [BdMN03] Joseph Bonin, Anna de Mier, and Marc Noy, _Lattice path matroids: enumerative aspects and Tutte polynomials_ , J. Combin. Theory Ser. A 104 (2003), no. 1, 63–94.
  * [Bec99] Matthias Beck, _The reciprocity law for Dedekind sums via the constant Ehrhart coefficient_ , Amer. Math. Monthly 106 (1999), no. 5, 459–462.
  * [BR15] Matthias Beck and Sinai Robins, _Computing the continuous discretely_ , second ed., Undergraduate Texts in Mathematics, Springer, New York, 2015, Integer-point enumeration in polyhedra, With illustrations by David Austin.
  * [Bru23] Winfried Bruns, _Polytope volume in Normaliz_ , São Paulo J. Math. Sci. 17 (2023), no. 1, 36–54.
  * [BS18] Matthias Beck and Raman Sanyal, _Combinatorial reciprocity theorems_ , Graduate Studies in Mathematics, vol. 195, American Mathematical Society, Providence, RI, 2018, An invitation to enumerative geometric combinatorics.
  * [BV08] Welleda Baldoni and Michèle Vergne, _Kostant partitions functions and flow polytopes_ , Transform. Groups 13 (2008), no. 3-4, 447–469.
  * [CCPS98] William J. Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver, _Combinatorial optimization_ , Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1998, A Wiley-Interscience Publication.
  * [CLS11] David A. Cox, John B. Little, and Henry K. Schenck, _Toric varieties_ , Graduate Studies in Mathematics, vol. 124, American Mathematical Society, Providence, RI, 2011.
  * [Din71] George W. Dinolt, _An extremal problem for non-separable matroids_ , Théorie des matroïdes (Rencontre Franco-Britannique, Brest, 1970), Lecture Notes in Math., vol. Vol. 211, Springer, Berlin-New York, 1971, pp. 31–49.
  * [DLHK09] Jesús A. De Loera, David C. Haws, and Matthias Köppe, _Ehrhart polynomials of matroid polytopes and polymatroids_ , Discrete Comput. Geom. 42 (2009), no. 4, 670–702.
  * [Edm03] Jack Edmonds, _Submodular functions, matroids, and certain polyhedra [mr0270945]_ , Combinatorial optimization—Eureka, you shrink!, Lecture Notes in Comput. Sci., vol. 2570, Springer, Berlin, 2003, pp. 11–26.
  * [Ehr62] Eugène Ehrhart, _Sur les polyèdres rationnels homothétiques à $n$ dimensions_, C. R. Acad. Sci. Paris 254 (1962), 616–618.
  * [Fer21] Luis Ferroni, _Hypersimplices are Ehrhart positive_ , J. Combin. Theory Ser. A 178 (2021), Paper No. 105365, 13.
  * [Fer22a] by same author, _Matroids are not Ehrhart positive_ , Adv. Math. 402 (2022), Paper No. 108337, 27.
  * [Fer22b] by same author, _On the Ehrhart polynomial of minimal matroids_ , Discrete Comput. Geom. 68 (2022), no. 1, 255–273.
  * [FJS22] Luis Ferroni, Katharina Jochemko, and Benjamin Schröter, _Ehrhart polynomials of rank two matroids_ , Adv. in Appl. Math. 141 (2022), Paper No. 102410, 26.
  * [FL23] Neil JY Fan and Yao Li, _On the Ehrhart polynomial of schubert matroids_ , Discrete Comput. Geom. (2023), 1–40.
  * [FM22] Luis Ferroni and Daniel McGinnis, _Lattice points in slices of prisms_ , arXiv e-prints (2022), arXiv:2202.11808.
  * [FNV22] Luis Ferroni, George Nasr, and Lorenzo Vecchi, _Stressed hyperplanes and Kazhdan–Lusztig gamma-positivity for matroids_ , International Mathematics Research Notices (2022), 1–60.
  * [FS05] Eva Maria Feichtner and Bernd Sturmfels, _Matroid polytopes, nested sets and Bergman fans_ , Port. Math. (N.S.) 62 (2005), no. 4, 437–468.
  * [FS22] Luis Ferroni and Benjamin Schröter, _Valuative invariants for large classes of matroids_ , arXiv e-prints (2022), arXiv:2208.04893.
  * [Fuj05] Satoru Fujishige, _Submodular functions and optimization_ , second ed., Annals of Discrete Mathematics, vol. 58, Elsevier B. V., Amsterdam, 2005.
  * [Ful93] William Fulton, _Introduction to toric varieties_ , Annals of Mathematics Studies, vol. 131, Princeton University Press, Princeton, NJ, 1993, The William H. Roever Lectures in Geometry.
  * [HMM+23] Derek Hanely, Jeremy L. Martin, Daniel McGinnis, Dane Miyata, George D. Nasr, Andrés R. Vindas-Meléndez, and Mei Yin, _Ehrhart theory of paving and panhandle matroids_ , Adv. Geom. 23 (2023), no. 4, 501–526.
  * [JR22] Katharina Jochemko and Mohan Ravichandran, _Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity_ , Mathematika 68 (2022), no. 1, 217–236.
  * [Kat05] Mordechai Katzman, _The Hilbert series of algebras of the Veronese type_ , Comm. Algebra 33 (2005), no. 4, 1141–1146.
  * [KMSRA18] Kolja Knauer, Leonardo Martínez-Sandoval, and Jorge Luis Ramírez Alfonsín, _On lattice path matroid polytopes: integer points and Ehrhart polynomial_ , Discrete Comput. Geom. 60 (2018), no. 3, 698–719.
  * [Liu19] Fu Liu, _On positivity of Ehrhart polynomials_ , Recent trends in algebraic combinatorics, Assoc. Women Math. Ser., vol. 16, Springer, Cham, 2019, pp. 189–237.
  * [LP05] Thomas Lam and Alexander Postnikov, _Alcoved polytopes, i_ , Discrete & Computational Geometry 38 (2005), 453–478.
  * [LP20] Thomas Lam and Alexander Postnikov, _Polypositroids_ , arXiv e-prints (2020), arXiv:2010.07120.
  * [MM15] Karola Mészáros and Alejandro H. Morales, _Flow polytopes of signed graphs and the Kostant partition function_ , Int. Math. Res. Not. IMRN (2015), no. 3, 830–871.
  * [MNWW11] Dillon Mayhew, Mike Newman, Dominic Welsh, and Geoff Whittle, _On the asymptotic proportion of connected matroids_ , European J. Combin. 32 (2011), no. 6, 882–890.
  * [Mor93] Robert Morelli, _Pick’s theorem and the Todd class of a toric variety_ , Adv. Math. 100 (1993), no. 2, 183–231.
  * [Mur71] U. S. R. Murty, _On the number of bases of a matroid_ , Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1971), Louisiana State University, Baton Rouge, LA, 1971, pp. 387–410.
  * [Oxl11] James Oxley, _Matroid theory_ , second ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011.
  * [Pom93] James E. Pommersheim, _Toric varieties, lattice points and Dedekind sums_ , Math. Ann. 295 (1993), no. 1, 1–24.
  * [Pos09] Alexander Postnikov, _Permutohedra, associahedra, and beyond_ , Int. Math. Res. Not. IMRN (2009), no. 6, 1026–1106.
  * [PvdP15] Rudi Pendavingh and Jorn van der Pol, _On the number of matroids compared to the number of sparse paving matroids_ , Electron. J. Combin. 22 (2015), no. 2, Paper 2.51, 17.
  * [Sta11] Richard P. Stanley, _Enumerative combinatorics: Volume 1_ , 2nd ed., Cambridge University Press, USA, 2011.
  * [Wel76] D. J. A. Welsh, _Matroid theory_ , LMS Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976.