# Chain enumeration, partition lattices and polynomials with only real roots

Christos A. Athanasiadis  Department of Mathematics
National and Kapodistrian University of Athens
Panepistimioupolis
15784 Athens, Greece<EMAIL_ADDRESS>and  Katerina Kalampogia-Evangelinou
Department of Mathematics
National and Kapodistrian University of Athens
Panepistimioupolis
15784 Athens, Greece<EMAIL_ADDRESS>
(Date: January 2, 2023)

###### Abstract.

The coefficients of the chain polynomial of a finite poset enumerate chains in
the poset by their number of elements. The chain polynomials of the partition
lattices and their standard type $B$ analogues are shown to have only real
roots. The real-rootedness of the chain polynomial is conjectured for all
geometric lattices and is shown to be preserved by the pyramid and the prism
operations on Cohen–Macaulay posets. As a result, new families of convex
polytopes whose barycentric subdivisions have real-rooted $f$-polynomials are
presented. An application to the face enumeration of the second barycentric
subdivision of the boundary complex of the simplex is also included.

Mathematics Subject Classifications: 05A05, 05A18, 05E45, 06A07, 26C10

Key words and phrases. Chain polynomial, geometric lattice, partition lattice,
real-rooted polynomial, flag $h$-vector, convex polytope, barycentric
subdivision.

##  1\. Introduction

The chain polynomial of a finite poset (partially ordered set) ${\mathcal{L}}$
is defined as $p_{\mathcal{L}}(x):=\sum_{k\geq 0}c_{k}({\mathcal{L}})x^{k}$,
where $c_{k}({\mathcal{L}})$ stands for the number of $k$-element chains in
${\mathcal{L}}$ (thus, $p_{\mathcal{L}}(x)$ is the $f$-polynomial of the order
complex of ${\mathcal{L}}$). The general question which motivates this paper
is as follows.

######  Question 1.1.

For which finite posets does the chain polynomial have only real roots?

This question has been studied and proven to be very interesting and
challenging for specific classes of posets. For finite distributive lattices,
it is known to be equivalent to the poset conjecture for natural labelings,
posed in the seventies by Neggers [16] (see also [22, Conjecture 1]) and
finally disproved by Stembridge [26], after counterexamples to a more general
conjecture were found by Brändén [10]. For face lattices of convex polytopes,
it was raised by Brenti and Welker in their study of $f$-vectors of
barycentric subdivisions [12]. The question is currently open in this case and
is known to have an affirmative answer for face lattices of simplicial
(equivalently, simple) polytopes [12], cubical polytopes [4] and, by the
results of [15], polytopes of dimension at most five. Another notable result
[24, Corollary 2.9] asserts that the chain polynomial $p_{\mathcal{L}}(x)$ has
only real roots for every poset ${\mathcal{L}}$ which does not contain the
disjoint union of a three-element chain and a one-element chain as an induced
subposet.

This paper partly aims to show that Question 1.1 is very interesting for other
classes of posets as well, especially for geometric lattices (the lattices of
flats of matroids). The following statement is the main conjecture posed in
this paper (a more precise conjecture appears in Section 5).

######  Conjecture 1.2.

The chain polynomial $p_{\mathcal{L}}(x)$ has only real roots for every
geometric lattice ${\mathcal{L}}$.

Our first main result verifies this conjecture for some important geometric
lattices, such as the subspace lattice ${\mathcal{L}}_{n}(q)$ of all linear
subspaces of an $n$-dimensional vector space over the field with $q$ elements,
the partition lattice $\Pi_{n}$ [25, Section 3.1] and its standard type $B$
analogue $\Pi^{B}_{n}$ [31, Section 1.3]. The statement about uniform matroids
follows from the main result of [12] and is included for the sake of
completeness.

######  Theorem 1.3.

Conjecture 1.2 is true for

  * (a)

the subspace lattices ${\mathcal{L}}_{n}(q)$,

  * (b)

the partition lattices $\Pi_{n}$ and $\Pi^{B}_{n}$,

  * (c)

the lattices of flats of near-pencils and uniform matroids.

Conjecture 1.2 has also been verified computationally for all geometric
lattices with at most nine atoms.

Our second main result gives constructions of posets which preserve the real-
rootedness of the chain polynomial. More specifically, there are natural
operations ${\rm Pyr}$ and ${\rm Prism}$ on posets (called pyramid and prism,
see Section 2), such that if ${\mathcal{L}}$ is the face lattice of a convex
polytope ${\mathcal{P}}$, then ${\rm Pyr}({\mathcal{L}})$ and ${\rm
Prism}({\mathcal{L}})$ are the face lattices of the pyramid and the prism over
${\mathcal{P}}$, respectively. Among other applications, the following
statement implies the existence of large families of nonsimplicial, nonsimple
and noncubical polytopes in any dimension, the face lattices of which have
real-rooted chain polynomials.

######  Theorem 1.4.

If the chain polynomial of a bounded Cohen–Macaulay poset ${\mathcal{L}}$ has
only real roots, then so do the chain polynomials of the pyramid and the prism
over ${\mathcal{L}}$.

The content, methods and structure of this paper may be described as follows.
Section 2 provides basic definitions and useful background from algebraic,
enumerative and geometric combinatorics (mainly on chain enumeration in
posets) and the theory of real-rooted polynomials. Sections 3 and 4 prove
parts (a) and (b) of Theorem 1.3, respectively. The proofs depend on specific
combinatorial features of these posets and do not seem to extend easily to
other geometric lattices. They proceed by exploiting explicit combinatorial
interpretations of the flag $h$-vectors and the $h$-polynomials of the order
complexes of the posets in question. To the best of our knowledge, such
combinatorial interpretations have not appeared in the literature before for
the partition lattices $\Pi_{n}$ and $\Pi^{B}_{n}$. Part (a) of Theorem 1.3 is
easier to prove and serves as an introductory example.

Section 5 discusses Question 1.1 for some general classes of Cohen–Macaulay
posets, including that of geometric lattices, proves Theorem 1.4 and deduces
from that part (c) of Theorem 1.3 (see Proposition 5.8). Proposition 5.3
suggests that the real-rootedness of chain polynomials of geometric lattices
should perhaps be studied in connection to that of chain polynomials of face
lattices of zonotopes and oriented matroids. The proofs in Section 5 rely
heavily on results of Ehrenborg and Readdy [13] on the chain enumeration of
pyramids and prisms and of Billera, Ehrenborg and Readdy [7] on the chain
enumeration of big face lattices of oriented matroids (reviewed in Section 2).
Section 6 applies Proposition 5.3 to give an unexpected combinatorial
interpretation of the $h$-polynomial of the second barycentric subdivision of
the boundary complex of a simplex and of its associated $\gamma$-polynomial,
thus solving a problem posed in [2].

As noted already, the chain polynomial $p_{\mathcal{L}}(x)$ coincides with the
$f$-polynomial of the order complex $\Delta({\mathcal{L}})$ of a poset
${\mathcal{L}}$. The results of Sections 3, 4 and 5 are phrased in terms of
the $h$-polynomial of $\Delta({\mathcal{L}})$ instead, which is more natural
from an algebraic combinatorics point of view for the classes of posets we are
interested in.

##  2\. Preliminaries

This section includes preliminaries on notation and definitions and discusses
some of the key tools and results from chain enumeration and the theory of
real-rooted polynomials which will be used in this paper. We assume
familiarity with main objects of study in algebraic, enumerative and geometric
combinatorics, such as posets, matroids, simplicial complexes, convex
polytopes and oriented matroids; standard references are [8, 9, 18, 23, 25,
31, 32]. Any undefined terminology can be found there.

We will denote by ${\mathfrak{S}}_{n}$ the symmetric group of permutations of
$[n]:=\\{1,2,\dots,n\\}$ and by $|S|$ the cardinality of a finite set $S$.

###  2.1. Simplicial complexes and face enumeration

Given an $(n-1)$-dimensional (finite, abstract) simplicial complex $\Delta$,
the _$f$ -polynomial_ and the _$h$ -polynomial_ are defined as

$\displaystyle f(\Delta,x)$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{n}f_{i-1}(\Delta)x^{i}$ $\displaystyle h(\Delta,x)$
$\displaystyle=$ $\displaystyle(1-x)^{n}f(\Delta,\frac{x}{1-x})\ =\
\sum_{i=0}^{n}f_{i-1}(\Delta)\,x^{i}(1-x)^{n-i},$

where $f_{i-1}(\Delta)$ stands for the number of $(i-1)$-dimensional faces of
$\Delta$. The $h$-polynomial has nonnegative coefficients for all
Cohen–Macaulay simplicial complexes [23, Section II.3] (this property is meant
to be considered here over the field ${\mathbb{Q}}$ of rational numbers) and,
in particular, for all simplicial complexes of interest in this paper.
Morever, $h(\Delta,x)$ can be considered as an $x$-analogue of
$f_{n-1}(\Delta)$, to which its coefficients sum up. Since $f(\Delta,x)$ has
only real roots if and only if so does $h(\Delta,x)$, the former can be
replaced by the latter as far as real-rootedness is concerned.

###  2.2. Order complexes and chain enumeration

We will be mostly interested in order complexes of posets. The _order complex_
of a finite poset $({\mathcal{L}},\preceq)$ is defined [25, Section 3.8] as
the simplicial complex $\Delta({\mathcal{L}})$ which consists of all chains in
${\mathcal{L}}$. We have $f(\Delta({\mathcal{L}}),x)=p_{\mathcal{L}}(x)$,
where $p_{\mathcal{L}}(x)$ is the chain polynomial defined in the
introduction. To simplify notation, we set
$h_{\mathcal{L}}(x)=h(\Delta({\mathcal{L}}),x)$ throughout this paper. Thus,
$p_{\mathcal{L}}(x)$ and $h_{\mathcal{L}}(x)$ are related by the equation

$h_{\mathcal{L}}(x)\ =\ (1-x)^{n}\,p_{\mathcal{L}}\left(\frac{x}{1-x}\right),$

where $n$ is the largest cardinality of a chain in ${\mathcal{L}}$. The
polynomial $h_{\mathcal{L}}(x)$ is an $x$-analogue of the number of
$n$-element chains of ${\mathcal{L}}$, which are exactly the
$(n-1)$-dimensional faces of $\Delta({\mathcal{L}})$.

Suppose now that ${\mathcal{L}}$ has a minimum element $\hat{0}$, a maximum
element $\hat{1}$ and that it is graded of rank $n$, say with rank function
$\rho:P\rightarrow\\{0,1,\dots,n\\}$. Thus, all maximal chains in
${\mathcal{L}}$ have exactly $n+1$ elements. Following [25, Section 3.13], for
$S\subseteq[n-1]$ we denote by $\alpha_{\mathcal{L}}(S)$ the number of maximal
chains of the subposet $\\{t\in{\mathcal{L}}:\rho(t)\in
S\\}\cup\\{\hat{0},\hat{1}\\}$ of ${\mathcal{L}}$ and set

$\beta_{\mathcal{L}}(S)\ =\ \sum_{T\subseteq
S}\,(-1)^{|S-T|}\,\alpha_{\mathcal{L}}(T).$

The numbers $\beta_{\mathcal{L}}(S)$ for $S\subseteq[n-1]$ are the entries of
the _flag $h$-vector_ of ${\mathcal{L}}$. They are nonnegative if
${\mathcal{L}}$ is Cohen–Macaulay (see, for instance, [23, Theorem 4.4]) and
refine the coefficients of $h_{\mathcal{L}}(x)$, in the sense that

(1) $h_{\mathcal{L}}(x)\
=\sum_{S\subseteq[n-1]}\beta_{\mathcal{L}}(S)x^{|S|}.$

We also set
$\overline{{\mathcal{L}}}={\mathcal{L}}{\smallsetminus}\\{\hat{0},\hat{1}\\}$
and recall that
$h_{\mathcal{L}}(x)=h_{{\mathcal{L}}{\smallsetminus}\\{\hat{0}\\}}(x)=h_{{\mathcal{L}}{\smallsetminus}\\{\hat{1}\\}}(x)=h_{\overline{{\mathcal{L}}}}(x)$.

The theory of edge labelings can provide useful combinatorial interpretations
of the numbers $\beta_{\mathcal{L}}(S)$. We denote by
${\mathcal{E}}({\mathcal{L}})$ and ${\mathcal{M}}({\mathcal{L}})$ the set of
covering relations and maximal chains of ${\mathcal{L}}$, respectively. An
edge labeling of ${\mathcal{L}}$ for us will be a map
$\lambda:{\mathcal{E}}({\mathcal{L}})\rightarrow{\mathbb{Z}}$. Given a maximal
chain $C:\hat{0}=c_{0}\prec c_{1}\prec\cdots\prec c_{n}=\hat{1}$ of
${\mathcal{L}}$, such a map induces the sequence of labels

$\lambda(C)\ =\
(\lambda(c_{0},c_{1}),\lambda(c_{1},c_{2}),\dots,\lambda(c_{n-1},c_{n})).$

We denote by ${\rm Des}_{\lambda}(C)$ the set of indices $i\in[n-1]$ for which
$\lambda(c_{i-1},c_{i})\geq\lambda(c_{i},c_{i+1})$ and call $C$ _strictly
increasing_ with respect to $\lambda$ if no such index exists. By restricting
$\lambda$, all these definitions apply to the closed intervals in
${\mathcal{L}}$. We say that $\lambda$ is a _strict $R$-labeling_ if every
closed interval in ${\mathcal{L}}$ has a unique strictly increasing maximal
chain with respect to $\lambda$. Under this assumption on $\lambda$, for every
$S\subseteq[n-1]$, $\beta_{\mathcal{L}}(S)$ is equal to the number of maximal
chains $C\in{\mathcal{M}}({\mathcal{L}})$ such that ${\rm
Des}_{\lambda}(C)=S$; see [25, Section 3.14] [31, Section 3.2] for examples
and more information on $R$-labelings.

The flag $h$-vector of ${\mathcal{L}}$ is nicely encoded by the
${\mathbf{a}}{\mathbf{b}}$-index $\Psi_{\mathcal{L}}$. Given noncommuting
variables ${\mathbf{a}}$ and ${\mathbf{b}}$, this may be defined as

$\Psi_{\mathcal{L}}\ =\ \Psi_{\mathcal{L}}({\mathbf{a}},{\mathbf{b}})\
=\sum_{S\subseteq[n-1]}\beta_{\mathcal{L}}(S){\mathbf{u}}_{S},$

where ${\mathbf{u}}_{S}=u_{1}u_{2}\cdots u_{n-1}$, with

$u_{i}\ =\ \begin{cases}{\mathbf{b}},&\text{if $i\in S$}\\\
{\mathbf{a}},&\text{if $i\not\in S$},\end{cases}$

is the ${\mathbf{a}}{\mathbf{b}}$-monomial associated to $S$ in the standard
way. We note that Equation (1) may be rewritten as
$h_{\mathcal{L}}(x)=\Psi_{\mathcal{L}}(1,x)$.

###  2.3. Face lattices of polytopes

We will denote by ${\mathcal{F}}({\mathcal{P}})$ the face lattice of a
polytope ${\mathcal{P}}$. The _barycentric subdivisions_ ${\rm
sd}({\mathcal{P}})$ and ${\rm sd}(\partial{\mathcal{P}})$ of ${\mathcal{P}}$
and its boundary complex $\partial{\mathcal{P}}$ are defined as the order
complexes $\Delta({\mathcal{L}}{\smallsetminus}\\{\hat{0}\\})$ and
$\Delta(\overline{{\mathcal{L}}})$, respectively, where
${\mathcal{L}}={\mathcal{F}}({\mathcal{P}})$. In particular, the
$f$-polynomials of ${\rm sd}({\mathcal{P}})$ and ${\rm
sd}(\partial{\mathcal{P}})$ are the chain polynomials of
${\mathcal{L}}{\smallsetminus}\\{\hat{0}\\}$ and $\overline{{\mathcal{L}}}$
and their real-rootedness is equivalent to that of
$h_{\mathcal{L}}(x)=h_{{\mathcal{L}}{\smallsetminus}\\{\hat{0}\\}}(x)=h({\rm
sd}({\mathcal{P}}),x)=h_{\overline{{\mathcal{L}}}}(x)=h({\rm
sd}(\partial{\mathcal{P}}),x)$.

There is another lattice associated to any zonotope ${\mathcal{Z}}$, namely
the geometric lattice of flats of the matroid defined by the generators of
${\mathcal{Z}}$. This lattice, say ${\mathcal{L}}({\mathcal{Z}})$, is
isomorphic to the intersection lattice of the linear hyperplane arrangement
${\mathcal{H}}_{\mathcal{Z}}$ corresponding to ${\mathcal{Z}}$; the face poset
${\mathcal{F}}({\mathcal{Z}}){\smallsetminus}\\{\hat{0}\\}$ is anti-isomorphic
to the face poset of ${\mathcal{H}}_{\mathcal{Z}}$ [32, Section 7.3]. The main
result of [7] expresses the flag $h$-vector of ${\mathcal{F}}({\mathcal{Z}})$
in terms of that of ${\mathcal{L}}({\mathcal{Z}})$. Consider the linear
function
$\omega:{\mathbb{Z}}\langle{\mathbf{a}},{\mathbf{b}}\rangle\rightarrow{\mathbb{Z}}\langle{\mathbf{a}},{\mathbf{b}}\rangle$
defined as follows: if $v$ is any ${\mathbf{a}}{\mathbf{b}}$-word, then
$\omega(v)$ is obtained from $v$ by first replacing each occurrence of
${\mathbf{a}}{\mathbf{b}}$ with
$2({\mathbf{a}}{\mathbf{b}}+{\mathbf{b}}{\mathbf{a}})$ and then replacing each
of the remaining letters with ${\mathbf{a}}+{\mathbf{b}}$.

######  Theorem 2.1.

([7, Corollary 3.2]) We have
$\Psi_{{\mathcal{F}}({\mathcal{Z}})}=\omega({\mathbf{a}}\cdot\Psi_{\mathcal{L}})$
for every zonotope ${\mathcal{Z}}$, where ${\mathcal{L}}$ is the lattice of
flats of the matroid associated to ${\mathcal{Z}}$.

Given a bounded, finite poset ${\mathcal{L}}$, the _pyramid_ over
${\mathcal{L}}$ is defined as ${\rm
Pyr}({\mathcal{L}})={\mathcal{L}}\times{\mathcal{L}}_{1}$, where
${\mathcal{L}}_{1}$ is the 2-element chain. The _prism_ over ${\mathcal{L}}$,
denoted ${\rm Prism}({\mathcal{L}})$, is defined as the poset obtained by
adding a minimum element to
$({\mathcal{L}}{\smallsetminus}\\{\hat{0}\\})\times({\mathcal{L}}_{2}{\smallsetminus}\\{\hat{0}\\})$,
where ${\mathcal{L}}_{2}={\mathcal{L}}_{1}\times{\mathcal{L}}_{1}$. Then, for
every polytope ${\mathcal{P}}$, the posets ${\rm
Pyr}({\mathcal{F}}({\mathcal{P}}))$ and ${\rm
Prism}({\mathcal{F}}({\mathcal{P}}))$ are isomorphic to the face lattices of
the pyramid and the prism over ${\mathcal{P}}$, respectively. Following [13],
we consider the linear derivation
$D:{\mathbb{Z}}\langle{\mathbf{a}},{\mathbf{b}}\rangle\rightarrow{\mathbb{Z}}\langle{\mathbf{a}},{\mathbf{b}}\rangle$
defined by setting
$D({\mathbf{a}})=D({\mathbf{b}})={\mathbf{a}}{\mathbf{b}}+{\mathbf{b}}{\mathbf{a}}$.

######  Theorem 2.2.

([13, Theorem 4.4]) We have

(2) $\displaystyle 2\,\Psi_{{\rm Pyr}({\mathcal{L}})}$ $\displaystyle=$
$\displaystyle\Psi_{\mathcal{L}}\cdot({\mathbf{a}}+{\mathbf{b}})\,+\,({\mathbf{a}}+{\mathbf{b}})\cdot\Psi_{\mathcal{L}}\,+\,D(\Psi_{\mathcal{L}}),$
(3) $\displaystyle\Psi_{{\rm Prism}({\mathcal{L}})}$ $\displaystyle=$
$\displaystyle\Psi_{\mathcal{L}}\cdot({\mathbf{a}}+{\mathbf{b}})\,+\,D(\Psi_{\mathcal{L}})$

for every bounded, graded finite poset ${\mathcal{L}}$.

###  2.4. Real-rooted polynomials

A polynomial $f(x)$ with real coefficients is called _real-rooted_ if every
root of $f(x)$ is real, or $f(x)\equiv 0$.

A real-rooted polynomial $f(x)$, with roots
$\alpha_{1}\geq\alpha_{2}\geq\cdots$, is said to _interlace_ a real-rooted
polynomial $g(x)$, with roots $\beta_{1}\geq\beta_{2}\geq\cdots$, if

$\cdots\leq\alpha_{2}\leq\beta_{2}\leq\alpha_{1}\leq\beta_{1}.$

By convention, the zero polynomial interlaces and is interlaced by every real-
rooted polynomial. A sequence $(f_{0}(x),f_{1}(x),\dots,f_{m}(x))$ of real-
rooted polynomials is called _interlacing_ if $f_{i}(x)$ interlaces $f_{j}(x)$
for $0\leq i<j\leq m$. The following standard lemma (see, for instance, [11,
Section 7.8]) will be applied several times in this paper.

######  Lemma 2.3.

Let $(f_{0}(x),f_{1}(x),\dots,f_{m}(x))$ be an interlacing sequence of real-
rooted polynomials with positive leading coefficients.

  * (a)

Every nonnegative linear combination $f(x)$ of
$f_{0}(x),f_{1}(x),\dots,f_{m}(x)$ is real-rooted. Moroever, $f(x)$ interlaces
$f_{m}(x)$ and it is interlaced by $f_{0}(x)$.

  * (b)

The sequence $(g_{0}(x),g_{1}(x),\dots,g_{m+1}(x))$ defined by

$g_{k}(x)\ =\ x\sum_{i=0}^{k-1}f_{i}(x)\,+\,\sum_{i=k}^{m}f_{i}(x)$

for $k\in\\{0,1,\dots,m+1\\}$ is also interlacing.

A polynomial $f(x)=a_{0}+a_{1}x+\cdots+a_{n}x^{n}$ with real coefficients is
called _symmetric_ , with center of symmetry $n/2$, if $a_{i}=a_{n-i}$ for all
$0\leq i\leq n$. Then, $f(x)=\sum_{i=0}^{\lfloor
n/2\rfloor}\gamma_{i}x^{i}(1+x)^{n-2i}$ for some uniquely defined real numbers
$\gamma_{0},\gamma_{1},\dots,\gamma_{\lfloor n/2\rfloor}$ and
$\gamma(x)=\sum_{i=0}^{\lfloor n/2\rfloor}\gamma_{i}x^{i}$ is the _$\gamma$
-polynomial_ associated to $f(x)$. The latter is called _$\gamma$ -positive_
if $\gamma_{i}\geq 0$ for every $i$; see [2] [11, Section 7.3] for more
information on this concept.

##  3\. Subspace lattices

This section confirms Theorem 1.3 for subspace lattices. The proof essentially
follows by combining [25, Theorem 3.13.3] with [21, Theorem 5.4] but serves as
a paradigm for the proofs of the corresponding statements for the lattices
$\Pi_{n}$ and $\Pi^{B}_{n}$ in the following section, which are more involved.

Given a positive integer $n$ and a prime power $q$, let $V_{n}(q)$ be an
$n$-dimensional vector space over the field with $q$ elements. The _subset
lattice_ ${\mathcal{L}}_{n}$, known as the Boolean algebra of rank $n$, and
the _subspace lattice_ ${\mathcal{L}}_{n}(q)$ are defined [25, Example 3.1.1]
as the set of all subsets of the set $[n]$ and as the set of all linear
subspaces of $V_{n}(q)$, respectively, partially ordered by inclusion. The
posets ${\mathcal{L}}_{n}$ and ${\mathcal{L}}_{n}(q)$ are geometric lattices
of rank $n$, the latter being considered as a $q$-analogue of the former. We
recall that a _descent_ of a permutation $w\in{\mathfrak{S}}_{n}$ is an index
$i\in[n-1]$ such that $w(i)>w(i+1)$ and denote by ${\rm des}(w)$ and ${\rm
Des}(w)$ the number and the set of all descents of $w$, respectively.

The order complex $\Delta(\overline{{\mathcal{L}}}_{n})$ is isomorphic to the
first barycentric subdivision of the boundary complex of the
$(n-1)$-dimensional simplex and its $h$-polynomial
$h_{{\mathcal{L}}_{n}}(x)=h(\Delta(\overline{{\mathcal{L}}}_{n}),x)$ is known
[20, Theorem 9.1] to be equal to the $n$th Eulerian polynomial

$A_{n}(x)\ :=\,\sum_{w\in{\mathfrak{S}}_{n}}x^{{\rm des}(w)}.$

The latter is well known [11, Section 7.8.1] to have only real roots for every
$n$. As already discussed, the following statement is equivalent to part (a)
of Theorem 1.3.

######  Proposition 3.1.

The polynomial $h_{{\mathcal{L}}}(x)$ is real-rooted for every subspace
lattice ${\mathcal{L}}={\mathcal{L}}_{n}(q)$.

###### Proof.

Setting ${\mathcal{L}}:={\mathcal{L}}_{n}(q)$, we have [25, Theorem 3.13.3]

$\beta_{\mathcal{L}}(S)\ =\sum_{w\in{\mathfrak{S}}_{n}:\,{\rm
Des}(w)=S}q^{{\rm inv}(w)},$

where ${\rm inv}(w)$ is the number of pairs of indices $1\leq i<j\leq n$ for
which $w(i)>w(j)$. This formula and Equation (1) imply that
$h_{{\mathcal{L}}}(x)=A_{n}(x;q)$, where

$A_{n}(x;q)\ :=\ \sum_{w\in{\mathfrak{S}}_{n}}q^{{\rm inv}(w)}x^{{\rm
des}(w)}$

is one of the well studied $q$-analogues of $A_{n}(x)$ [25, Section 3.19]. The
fact that $A_{n}(x;q)$ is real-rooted for every positive real number $q$ was
shown in [21, Theorem 5.4]. To give a self-contained proof, we set

$A_{n,k}(x;q)\ =\sum_{w\in{\mathfrak{S}}_{n}:\,w(n)=k}q^{{\rm inv}(w)}x^{{\rm
des}(w)}$

for $k\in[n]$ and note that $A_{n}(x;q)=A_{n+1,n+1}(x;q)$ for every $n$ and
that

(4) $A_{n+1,k}(x;q)\ =\
q^{n+1-k}\left(\,\sum_{i=1}^{k-1}A_{n,i}(x;q)\,+\,x\sum_{i=k}^{n}A_{n,i}(x;q)\right)$

for $k\in[n+1]$. An application of Lemma 2.3 shows by induction on $n$ that
the sequence $(A_{n,n}(x;q),A_{n,n-1}(x;q),\dots,A_{n,1}(x;q))$ is interlacing
for all $n$ and positive $q$. As a result, $A_{n}(x;q)=A_{n+1,n+1}(x;q)$ is
real-rooted for all $n$ and positive $q$. ∎

The previous argument also shows that $A_{n}(x;q)$ interlaces $A_{n+1}(x;q)$
for all $n$ and all positive $q$. This follows from part (a) of Lemma 2.3
since, by (4), $A_{n}(x;q)=A_{n+1,n+1}(x;q)$ is a positive linear combination
of the $A_{n,k}(x;q)$ for $1\leq k\leq n$ and $A_{n,n}(x;q)=A_{n-1}(x;q)$. For
the real-rootedness of other $q$-analogues of $A_{n}(x)$, see [21, Section 5].

##  4\. Partition lattices

This section proves part (b) of Theorem 1.3. As in Section 3, we will show the
equivalent statement that $h_{\Pi_{n}}(x)$ and $h_{\Pi^{B}_{n}}(x)$ are real-
rooted for every $n\geq 1$.

###  4.1. The partition lattice.

We recall that $\Pi_{n}$ consists of all partitions of the set $[n]$,
partially ordered by reverse refinement. It is isomorphic to the intersection
lattice of the Coxeter hyperplane arrangement of type $A_{n-1}$ and, as such,
it is a geometric lattice of rank $n-1$. We will first give an explicit
combinatorial interpretation of the flag $h$-vector of $\Pi_{n}$ and will
deduce one for $h_{\Pi_{n}}(x)$. A recurrence for the entries of the former
was found by Sundaram [27, Proposition 2.16]; an additional formula appears as
[27, Proposition 2.18]. We consider the multiset

${\mathcal{A}}_{n}\ :=\
\\{1\\}\times\\{1,1,2\\}\times\\{1,1,1,2,2,3\\}\times\cdots\times\\{1,1,\dots,1,\dots,n-2,n-2,n-1\\},$

e.g., ${\mathcal{A}}_{3}=\\{(1,1),(1,1),(1,2)\\}$. We define the _descent set_
of $\sigma=(\sigma_{1},\sigma_{2},\dots,\sigma_{n-1})\in{\mathcal{A}}_{n}$ as
${\rm Des}(\sigma)=\\{i\in[n-2]:\sigma_{i}\geq\sigma_{i+1}\\}$ and denote its
cardinality by ${\rm des}(\sigma)$. The multiset ${\mathcal{A}}_{n}$ has
$\prod_{k=2}^{n}{k\choose 2}=n!\,(n-1)!/2^{n-1}$ elements, as many as the
maximal chains of $\Pi_{n}$. Moreover, one element of ${\mathcal{A}}_{n}$ has
empty descent set and $(n-1)!$ of them have descent set equal to $[n-2]$.
These facts agree with the following statement.

######  Proposition 4.1.

For every $n\geq 2$ and every $S\subseteq[n-2]$, the number
$\beta_{\Pi_{n}}(S)$ is equal to the number of elements of the multiset
${\mathcal{A}}_{n}$ with descent set equal to $n-1-S:=\\{n-1-x:x\in S\\}$. In
particular,

(5) $h_{\Pi_{n}}(x)\ =\,\sum_{\sigma\in{\mathcal{A}}_{n}}x^{{\rm
des}(\sigma)}$

for every $n\geq 2$.

To prepare for the proof, we recall [31, Section 3.2.2] the following edge
labeling of $\Pi_{n}$, due to Gessel. For a covering relation
$(x,y)\in{\mathcal{E}}(\Pi_{n})$ we define $\lambda(x,y)$ as the maximum of
$\min(B)$ and $\min(B^{\prime})$, where $y$ is obtained from $x$ by merging
the blocks $B$ and $B^{\prime}$ of $x$. The labeling
$\lambda:{\mathcal{E}}(\Pi_{n})\rightarrow\\{2,3,\dots,n\\}$ is a strict
$R$-labeling (even a strict EL-labeling). In particular, $\beta_{\Pi_{n}}(S)$
is equal to the number of maximal chains $C$ of $\Pi_{n}$ such that ${\rm
Des}_{\lambda}(C)=S$, for every $S\subseteq[n-2]$.

_Proof of Proposition 4.1_. We consider the multiset

${\mathcal{A}}^{\ast}_{n}\ :=\
\\{2,3,3,4,4,4,\dots,n,n,\dots,n\\}\times\cdots\times\\{2,3,3,4,4,4\\}\times\\{2,3,3\\}\times\\{2\\}$

and set ${\rm Des}^{\ast}(\sigma)=\\{i\in[n-2]:\sigma_{i}>\sigma_{i+1}\\}$ for
$\sigma=(\sigma_{1},\sigma_{2},\dots,\sigma_{n-1})\in{\mathcal{A}}^{\ast}_{n}$.
The bijection ${\mathcal{A}}_{n}\mapsto{\mathcal{A}}^{\ast}_{n}$ defined by

$(\sigma_{1},\sigma_{2},\dots,\sigma_{n-1})\ \mapsto\
(n+1-\sigma_{n-1},n-\sigma_{n-2},\dots,3-\sigma_{1})$

shows that for every $S\subseteq[n-2]$, the number of elements
$\sigma\in{\mathcal{A}}^{\ast}_{n}$ with ${\rm Des}^{\ast}(\sigma)=S$ is equal
to the number of elements $\sigma\in{\mathcal{A}}_{n}$ with ${\rm
Des}(\sigma)=n-1-S$. Thus, we need to show that the former is equal to
$\beta_{\Pi_{n}}(S)$.

For that, we employ Gessel’s labeling
$\lambda:{\mathcal{E}}(\Pi_{n})\rightarrow\\{2,3,\dots,n\\}$. Given a covering
relation $(x,y)\in{\mathcal{E}}(\Pi_{n})$, we list the blocks of
$x=\\{B_{1},B_{2},\dots,B_{k}\\}$ so that
$\min(B_{1})<\min(B_{2})<\cdots<\min(B_{k})$ and set $\varphi(x,y)=(i,j)$ and
$\psi(x,y)=j$, where $i<j$ and $y$ is obtained from $x$ by merging $B_{i}$
with $B_{j}$. For a maximal chain $C:\hat{0}=c_{1}\prec c_{2}\prec\cdots\prec
c_{n}=\hat{1}$ of $\Pi_{n}$ we set

$\displaystyle\widetilde{\varphi}(C)$ $\displaystyle=$
$\displaystyle(\varphi(c_{1},c_{2}),\varphi(c_{2},c_{3}),\dots,\varphi(c_{n-1},c_{n})),$
$\displaystyle\widetilde{\psi}(C)$ $\displaystyle=$
$\displaystyle(\psi(c_{1},c_{2}),\psi(c_{2},c_{3}),\dots,\psi(c_{n-1},c_{n}))$

and consider the resulting maps

$\displaystyle\widetilde{\varphi}:$ $\displaystyle{\mathcal{M}}(\Pi_{n})\
\rightarrow$ $\displaystyle{[n]\choose 2}\times{[n-1]\choose
2}\times\cdots\times{[2]\choose 2},$ $\displaystyle\widetilde{\psi}:$
$\displaystyle{\mathcal{M}}(\Pi_{n})\ \rightarrow$
$\displaystyle\\{2,3,\dots,n\\}\times\\{2,3,\dots,n-1\\}\times\cdots\times\\{2\\},$

where ${T\choose 2}$ stands for the set of 2-element subsets of $T$.

Clearly, $\widetilde{\varphi}$ is a bijection. We claim that ${\rm
Des}_{\lambda}(C)={\rm Des}^{\ast}(\widetilde{\psi}(C))$ for every
$C\in{\mathcal{M}}(\Pi_{n})$. This would imply that $\beta_{\Pi_{n}}(S)$,
which is equal to the number of chains $C\in{\mathcal{M}}(\Pi_{n})$ with ${\rm
Des}_{\lambda}(C)=S$, is also equal to the number of chains
$C\in{\mathcal{M}}(\Pi_{n})$ with ${\rm Des}^{\ast}(\widetilde{\psi}(C))=S$.
Since $\widetilde{\varphi}$ is a bijection, the latter is equal to the number
of $\sigma\in{\mathcal{A}}^{\ast}_{n}$ with ${\rm Des}^{\ast}(\sigma)=S$.

Thus, it remains to verify the claim. Equivalently, for
$(x,y),(y,z)\in{\mathcal{E}}(\Pi_{n})$, we need to verify that
$\lambda(x,y)\geq\lambda(y,z)\Leftrightarrow\psi(x,y)>\psi(y,z)$. Indeed, let
$x=\\{B_{1},B_{2},\dots,B_{k}\\}$ with
$\min(B_{1})<\min(B_{2})<\cdots<\min(B_{k})$ and suppose that $y$ is obtained
from $x$ by merging $B_{i}$ with $B_{j}$, where $i<j$. Then,
$\lambda(x,y)=\min(B_{j})$ and $\psi(x,y)=j$. Each one of the inequalities
$\lambda(y,z)\leq\min(B_{j})$ and $\psi(y,z)<j$ is equivalent to the statement
that $z$ is obtained from $y$ by merging two blocks other than
$B_{j+1},\dots,B_{k}$ and the proof follows. ∎

For small values of $n$,

$h_{\Pi_{n}}(x)\ =\ \begin{cases}1,&\text{if $n=1$}\\\ 1,&\text{if $n=2$}\\\
1+2x,&\text{if $n=3$}\\\ 1+11x+6x^{2},&\text{if $n=4$}\\\
1+47x+108x^{2}+24x^{3},&\text{if $n=5$}\\\
1+197x+1268x^{2}+1114x^{3}+120x^{4},&\text{if $n=6$}\\\
1+870x+13184x^{2}+29383x^{3}+12542x^{4}+720x^{5},&\text{if $n=7$}.\\\
\end{cases}$

The following corollary proves and strengthens Theorem 1.3.

######  Corollary 4.2.

The polynomial $h_{\Pi_{n}}(x)$ is real-rooted and it interlaces
$h_{\Pi_{n+1}}(x)$ for every $n\geq 1$.

###### Proof.

For $k\in[n-1]$ we set

$h_{n,k}(x)\ =\sum_{\sigma\in{\mathcal{A}}_{n,k}}x^{{\rm des}(\sigma)},$

where ${\mathcal{A}}_{n,k}$ is the multiset consisting of all words
$(\sigma_{1},\sigma_{2},\dots,\sigma_{n-1})\in{\mathcal{A}}_{n}$ with
$\sigma_{n-1}=k$. By Proposition 4.1,

$h_{\Pi_{n}}(x)\ =\ h_{n+1,n}(x)\ =\ \sum_{k=1}^{n-1}h_{n,k}(x)$

for every $n\geq 2$ and

$h_{n+1,k}(x)\ =\
(n+1-k)\left(\,\sum_{i=1}^{k-1}h_{n,i}(x)\,+\,x\sum_{i=k}^{n-1}h_{n,i}(x)\right)$

for $k\in[n]$. Since $(h_{n+1,n}(x),h_{n+1,n-1}(x),\dots,h_{n+1,1}(x))$ is an
interlacing sequence if and only if
$(h_{n+1,n}(x),\frac{1}{2}h_{n+1,n-1}(x),\dots,\frac{1}{n}h_{n+1,1}(x))$ has
the same property, an application of Lemma 2.3 shows by induction on $n$ that
$(h_{n,n-1}(x),h_{n,n-2}(x),\dots,h_{n,1}(x))$ is interlacing for every $n\geq
2$ and that $h_{\Pi_{n}}(x)=\sum_{k=1}^{n-1}h_{n,k}(x)$ is interlaced by
$h_{n,n-1}(x)=h_{\Pi_{n-1}}(x)$. ∎

The following conjecture has been verified for $n\leq 20$.

######  Conjecture 4.3.

The polynomial $h_{\Pi_{n}}(x)$ is interlaced by the Eulerian polynomial
$A_{n-1}(x)$ for every $n\geq 2$.

###  4.2. The partition lattice of type $B$.

We find it convenient to define $\Pi^{B}_{n}$ as the set of all partitions
$\pi$ of $\\{-n,-n+1,\dots,n\\}$ with the following properties:

  * (i)

$B\in\pi\Rightarrow(-B)\in\pi$,

  * (ii)

if $\\{i,-i\\}\subseteq B$ for some $i\in[n]$ and some block $B\in\pi$, then
$0\in B$.

For example,
$\\{\\{0,2,-2\\},\\{1,-3,5\\},\\{-1,3,-5\\},\\{4\\},\\{-4\\}\\}\in\Pi^{B}_{5}$.
The partial order on $\Pi^{B}_{n}$ is again reverse refinement. The unique
block of $\pi\in\Pi^{B}_{n}$ containing 0 is called the _zero block_. The
poset $\Pi^{B}_{n}$ is isomorphic to the intersection lattice of the Coxeter
hyperplane arrangement of type $B_{n}$ and therefore it is a geometric lattice
of rank $n$.

The proof of Theorem 1.3 for the lattice $\Pi^{B}_{n}$ parallels that for
$\Pi_{n}$. One can easily verify that $\Pi^{B}_{n}$ has exactly $(n!)^{2}$
maximal chains. We consider the multiset

${\mathcal{B}}_{n}\ :=\
\\{1\\}\times\\{1,1,1,2\\}\times\\{1,1,1,1,1,2,2,2,3\\}\times\cdots\times\\{1,1,\dots,1,\dots,n-1,n-1,n-1,n\\},$

where the $k$th factor has $2k-2i+1$ elements equal to $i$, for $1\leq i\leq
k$. We define the descent set ${\rm Des}(\sigma)\subseteq[n-1]$ and its
cardinality ${\rm des}(\sigma)$ for $\sigma\in{\mathcal{B}}_{n}$ just as for
elements of ${\mathcal{A}}_{n}$. We note that ${\mathcal{B}}_{n}$ has
$(n!)^{2}$ elements, one of which has empty descent set and $(2n-1)!!$ of
which have descent set equal to $[n-1]$. These facts agree with the following
analogue of Proposition 4.1.

######  Proposition 4.4.

For every $n\geq 1$ and every $S\subseteq[n-1]$, the number
$\beta_{\Pi^{B}_{n}}(S)$ is equal to the number of elements of the multiset
${\mathcal{B}}_{n}$ with descent set equal to $n-S$. In particular,

(6) $h_{\Pi^{B}_{n}}(x)\ =\,\sum_{\sigma\in{\mathcal{B}}_{n}}x^{{\rm
des}(\sigma)}$

for every $n\geq 1$.

The proof uses the following analogue of Gessel’s edge labeling for $\Pi_{n}$.
Let us denote by $|B|$ the set of absolute values of the elements of a set
$B\subseteq{\mathbb{Z}}$. Given a covering relation
$(x,y)\in{\mathcal{E}}(\Pi^{B}_{n})$, there exists a unique pair
$\\{B,B^{\prime}\\}$ of distinct blocks of $x$ such that

  * (i)

$\min(|B|)\in B$ and $\min(|B^{\prime}|)\in B^{\prime}$,

  * (ii)

either $B$ and $B^{\prime}$ are nonzero and $B\cup B^{\prime}$ or $(-B)\cup
B^{\prime}$ is a nonzero block of $y$, or one of $B$ and $B^{\prime}$ is the
zero block of $x$ and $B\cup B^{\prime}$ is contained in the zero block of
$y$.

We then define $\lambda(x,y)$ as the maximum of $\min(|B|)$ and
$\min(|B^{\prime}|)$ and leave to the reader to verify that the resulting map
$\lambda:{\mathcal{E}}(\Pi^{B}_{n})\rightarrow\\{1,2,\dots,n\\}$ is a strict
$R$-labeling. In particular, $\beta_{\Pi^{B}_{n}}(S)$ is equal to the number
of maximal chains $C$ of $\Pi^{B}_{n}$ such that ${\rm Des}_{\lambda}(C)=S$,
for every $S\subseteq[n-1]$.

_Proof of Proposition 4.4_. We adapt the proof of Proposition 4.1 as follows.
We consider the multiset

${\mathcal{B}}^{\ast}_{n}\ :=\
\\{1,2,2,2,3,3,3,3,3,\dots,n,n,\dots,n\\}\times\cdots\times\\{1,2,2,2,3,3,3,3,3\\}\times\\{1,2,2,2\\}\times\\{1\\},$

where the $k$th factor has $2i-1$ elements equal to $i$, for $i\in[n-k+1]$. We
set ${\rm Des}^{\ast}(\sigma)=\\{i\in[n-1]:\sigma_{i}>\sigma_{i+1}\\}$ for
$\sigma=(\sigma_{1},\sigma_{2},\dots,\sigma_{n})\in{\mathcal{B}}^{\ast}_{n}$.
The bijection ${\mathcal{B}}_{n}\mapsto{\mathcal{B}}^{\ast}_{n}$ defined by

$(\sigma_{1},\sigma_{2},\dots,\sigma_{n})\ \mapsto\
(n+1-\sigma_{n},n-\sigma_{n-1},\dots,2-\sigma_{1})$

shows that, for every $S\subseteq[n-1]$, the number of elements
$\sigma\in{\mathcal{B}}^{\ast}_{n}$ with ${\rm Des}^{\ast}(\sigma)=S$ is equal
to the number of elements $\sigma\in{\mathcal{B}}_{n}$ with ${\rm
Des}(\sigma)=n-S$. Thus, it suffices to show that the former equals
$\beta_{\Pi^{B}_{n}}(S)$.

Let us call a nonzero block $B$ of a partition $x\in\Pi^{B}_{n}$ _positive_ if
$\min(|B|)\in B$. Given a covering relation
$(x,y)\in{\mathcal{E}}(\Pi^{B}_{n})$, we let $B_{0}$ be the zero block of $x$
and list its positive blocks, say $B_{1},B_{2},\dots,B_{k}$, so that
$\min(|B_{1}|)<\min(|B_{2}|)<\cdots<\min(|B_{k}|)$. Then, some positive block
$B_{j}$ merges in $y$ either with $B_{0}$, or with $B_{i}$ or $-B_{i}$ for
some $1\leq i<j$. We set $\varphi(x,y)=(j,j)$ or $(i,j)$ or $(j,i)$ in these
cases, respectively, and $\psi(x,y)=j$. For a maximal chain
$C:\hat{0}=c_{0}\prec c_{1}\prec\cdots\prec c_{n}=\hat{1}$ of $\Pi^{B}_{n}$ we
set

$\displaystyle\widetilde{\varphi}(C)$ $\displaystyle=$
$\displaystyle(\varphi(c_{0},c_{1}),\varphi(c_{1},c_{2}),\dots,\varphi(c_{n-1},c_{n})),$
$\displaystyle\widetilde{\psi}(C)$ $\displaystyle=$
$\displaystyle(\psi(c_{0},c_{1}),\psi(c_{1},c_{2}),\dots,\psi(c_{n-1},c_{n}))$

and consider the resulting maps

$\displaystyle\widetilde{\varphi}:$ $\displaystyle{\mathcal{M}}(\Pi^{B}_{n})\
\rightarrow$ $\displaystyle[n]^{2}\times[n-1]^{2}\times\cdots\times[1]^{2},$
$\displaystyle\widetilde{\psi}:$ $\displaystyle{\mathcal{M}}(\Pi^{B}_{n})\
\rightarrow$ $\displaystyle[n]\times[n-1]\times\cdots\times[1].$

We note that $\widetilde{\varphi}$ is a bijection, verify that ${\rm
Des}_{\lambda}(C)={\rm Des}^{\ast}(\widetilde{\psi}(C))$ for every
$C\in{\mathcal{M}}(\Pi^{B}_{n})$, just as in the proof of Proposition 4.1, and
conclude that $\beta_{\Pi^{B}_{n}}(S)$ is equal to the number of elements
$\sigma\in{\mathcal{B}}^{\ast}_{n}$ with ${\rm Des}^{\ast}(\sigma)=S$ for
every $S\subseteq[n-1]$. ∎

For small values of $n$,

$h_{\Pi^{B}_{n}}(x)\ =\ \begin{cases}1,&\text{if $n=1$}\\\ 1+3x,&\text{if
$n=2$}\\\ 1+20x+15x^{2},&\text{if $n=3$}\\\ 1+111x+359x^{2}+105x^{3},&\text{if
$n=4$}\\\ 1+642x+5978x^{2}+6834x^{3}+945x^{4},&\text{if $n=5$}\\\
1+4081x+92476x^{2}+268236x^{3}+143211x^{4}+10395x^{5},&\text{if
$n=6$}.\end{cases}$

######  Corollary 4.5.

The polynomial $h_{\Pi^{B}_{n}}(x)$ is real-rooted and it interlaces
$h_{\Pi^{B}_{n+1}}(x)$ for every $n\geq 1$.

###### Proof.

For $1\leq k\leq n$ we set

$h^{B}_{n,k}(x)\ =\sum_{\sigma\in{\mathcal{B}}_{n,k}}x^{{\rm des}(\sigma)},$

where ${\mathcal{B}}_{n,k}$ is the multiset consisting of all words
$(\sigma_{1},\sigma_{2},\dots,\sigma_{n})\in{\mathcal{B}}_{n}$ with
$\sigma_{n}=k$. By Proposition 4.4,

$h_{\Pi^{B}_{n}}(x)\ =\ h^{B}_{n+1,n+1}(x)\ =\ \sum_{k=1}^{n}h^{B}_{n,k}(x)$

for every $n\geq 1$ and

$h^{B}_{n+1,k}(x)\ =\
(2n-2k+3)\left(\,\sum_{i=1}^{k-1}h^{B}_{n,i}(x)\,+\,x\sum_{i=k}^{n}h^{B}_{n,i}(x)\right)$

for $k\in[n+1]$. The result follows from these formulas as in the proof of
Corollary 4.2. ∎

The intersection lattice of the Coxeter hyperplane arrangement of type $D_{n}$
is isomorphic to the subposet $\Pi^{D}_{n}$ of $\Pi^{B}_{n}$ which consists of
all elements of the latter with zero block not of the form $\\{0,i,-i\\}$ for
any $i\in[n]$. The number of maximal chains of $\Pi^{D}_{n}$ can be shown to
equal $(n!)^{2}/2$ for every $n\geq 2$. For small values of $n$,

$h_{\Pi^{D}_{n}}(x)\ =\ \begin{cases}1+x,&\text{if $n=2$}\\\
1+11x+6x^{2},&\text{if $n=3$}\\\ 1+67x+175x^{2}+45x^{3},&\text{if $n=4$}\\\
1+397x+3143x^{2}+3239x^{3}+420x^{4},&\text{if $n=5$}\\\
1+2539x+50272x^{2}+134160x^{3}+67503x^{4}+4725x^{5},&\text{if
$n=6$}.\end{cases}$

We leave the analogue of Propositions 4.1 and 4.4 for $\Pi^{D}_{n}$ open in
this paper. Computational data suggest that the polynomial
$h_{\Pi^{D}_{n}}(x)$ is real-rooted for every $n\geq 2$ and that the sequence
$(h_{\Pi_{n+1}}(x),h_{\Pi^{D}_{n}}(x),h_{\Pi^{B}_{n}}(x))$ is interlacing for
every $n\geq 3$.

##  5\. Geometric lattices and face lattices of polytopes

This section addresses the question of real-rootedness of $h_{\mathcal{L}}(x)$
for geometric lattices, face lattices of polytopes and other classes of
posets. Moreover, it discusses connections among these questions, proves
Theorem 1.4 and deduces some partial results from that.

We recall that a finite lattice is called geometric if it is atomic and
semimodular (see [25, Section 3.3] for explanations and more information) or,
equivalently, if it is isomorphic to the lattice of flats of a matroid. For a
geometric lattice ${\mathcal{L}}$, the possible inequalities among the
coefficients of $h_{\mathcal{L}}(x)$ were studied by Nyman and Swartz [17],
who showed that

  * $\bullet$

$a_{0}\leq a_{1}\leq\cdots\leq a_{\lfloor(n-1)/2\rfloor}$, and

  * $\bullet$

$a_{i}\leq a_{n-1-i}$ for $0\leq i\leq(n-1)/2$

for every geometric lattice ${\mathcal{L}}$ of rank $n$, where
$h_{\mathcal{L}}(x)=\sum_{i=0}^{n-1}a_{i}x^{i}$ (later, these inequalities
were extended to the $h$-polynomials of $(n-1)$-dimensional simplicial
complexes having a convex ear decomposition in [29] and, more recently, to the
$h$-polynomials of all $(n-1)$-dimensional doubly Cohen–Macaulay simplicial
complexes in [1, Section 6]). To the best of our knowledge, the unimodality of
$h_{\mathcal{L}}(x)$ is open. The following conjecture, which has been
verified computationally for all geometric lattices with at most nine atoms,
is a much stronger statement.

######  Conjecture 5.1.

The polynomial $h_{\mathcal{L}}(x)$ has only real roots and is interlaced by
the Eulerian polynomial $A_{n}(x)$ for every geometric lattice ${\mathcal{L}}$
of rank $n$.

The question of real-rootedness of $h_{\mathcal{L}}(x)$ was raised by Brenti
and Welker [12, Question 1] for face lattices of convex polytopes and (in a
stronger form) by Athanasiadis and Tzanaki [6, Question 7.4] for face lattices
of more general classes of polyhedral complexes, including polyhedral balls
and doubly Cohen–Macaulay polyhedral complexes. It seems natural to pose the
following even more general question. We recall that a finite poset
${\mathcal{L}}$, having a minimum element $\hat{0}$, is said to be _lower
Eulerian_ if the closed interval $[\hat{0},x]$ in ${\mathcal{L}}$ is Eulerian
(see [25, Section 3.16] for the definition and information about Eulerian
posets) for every $x\in{\mathcal{L}}$.

######  Question 5.2.

Does $h_{\mathcal{L}}(x)$ have only real roots for every lower Eulerian
Cohen–Macaulay poset ${\mathcal{L}}$?

Special classes of lower Eulerian Cohen–Macaulay posets for which it would be
interesting to investigate this question include:

  * $\bullet$

lower Eulerian Cohen–Macaulay meet semi-lattices,

  * $\bullet$

face posets of Cohen–Macaulay regular cell complexes,

  * $\bullet$

face posets of Cohen–Macaulay polyhedral complexes,

  * $\bullet$

Gorenstein* posets,

  * $\bullet$

Gorenstein* lattices,

  * $\bullet$

face lattices of convex polytopes [12, Question 1],

  * $\bullet$

face lattices of zonotopes.

Given Equation (1), the following statement suggests that Conjecture 5.1 may
be closely related to the special case of Question 5.2 concerning face
lattices of zonotopes (more generally, of oriented matroids). We recall that
${\mathcal{F}}({\mathcal{P}})$ denotes the face lattice of a polytope
${\mathcal{P}}$. For $S\subseteq[n-1]$, we denote by ${\rm lpeak}(S)$ the
number of elements $i\in S$ for which $i-1\not\in S$, known [20, p. 298] as
the _left peaks_ of the permutation $w\in{\mathfrak{S}}_{n}$ when $S={\rm
Des}(w)$.

######  Proposition 5.3.

For every $n$-dimensional zonotope ${\mathcal{Z}}$

(7) $h_{{\mathcal{F}}({\mathcal{Z}})}(x)\
=\sum_{S\subseteq[n-1]}\beta_{\mathcal{L}}(S)\,(4x)^{{\rm
lpeak}(S)}(1+x)^{n-2{\rm lpeak}(S)},$

where ${\mathcal{L}}$ is the lattice of flats of the matroid associated to
${\mathcal{Z}}$. In particular, the polynomial
$h_{{\mathcal{F}}({\mathcal{Z}})}(x)$ has only real roots if and only if so
does $\sum_{S\subseteq[n-1]}\beta_{\mathcal{L}}(S)x^{{\rm lpeak}(S)}$.

###### Proof.

The number of occurrences of ${\mathbf{a}}{\mathbf{b}}$ in a word
${\mathbf{a}}\cdot w$ of degree $n$ in ${\mathbf{a}}$ and ${\mathbf{b}}$ is
equal to ${\rm lpeak}(S)$, where $S$ is the subset of $[n-1]$ associated to
$w$. Thus, the first statement follows by substituting ${\mathbf{a}}=1$ and
${\mathbf{b}}=x$ in the formula
$\Psi_{{\mathcal{F}}({\mathcal{Z}})}=\omega({\mathbf{a}}\cdot\Psi_{\mathcal{L}})$
of Theorem 2.1. The second statement follows from the first and the fact (see
[15, Remark 3.1.1]) that a $\gamma$-positive polynomial $\sum_{i=0}^{\lfloor
n/2\rfloor}\gamma_{i}x^{i}(1+x)^{n-2i}$ is real-rooted if and only if so is
the associated $\gamma$-polynomial $\sum_{i=0}^{\lfloor
n/2\rfloor}\gamma_{i}x^{i}$. ∎

######  Remark 5.4.

Let ${\mathcal{Z}}$ and ${\mathcal{L}}$ be as in Proposition 5.3. Setting
$x=1$ in Equation (7) shows that the number of facets of the barycentric
subdivision of ${\mathcal{Z}}$ is equal to $2^{n}$ times the number of maximal
chains of ${\mathcal{L}}$. ∎

The main result of this section, which is a stronger version of Theorem 1.4,
allows one to construct new posets with real-rooted chain polynomials from
posets known to have this property.

######  Theorem 5.5.

Let ${\mathcal{L}}$ be a bounded, graded poset of positive rank $n$.

  * (a)

We have

(8) $\displaystyle h_{{\rm Pyr}({\mathcal{L}})}(x)$ $\displaystyle=$
$\displaystyle(1+nx)h_{\mathcal{L}}(x)+(x-x^{2})h^{\prime}_{\mathcal{L}}(x),$
$\displaystyle h_{{\rm Prism}({\mathcal{L}})}(x)$ $\displaystyle=$
$\displaystyle(1+(2n-1)x)h_{\mathcal{L}}(x)+2(x-x^{2})h^{\prime}_{\mathcal{L}}(x)$
$\displaystyle=$ $\displaystyle 2h_{{\rm
Pyr}({\mathcal{L}})}(x)-(1+x)h_{\mathcal{L}}(x).$

  * (b)

Assume that ${\mathcal{L}}$ is Cohen–Macaulay. If $h_{\mathcal{L}}(x)$ is
real-rooted, then $h_{{\rm Pyr}({\mathcal{L}})}(x)$ and $h_{{\rm
Prism}({\mathcal{L}})}(x)$ are also real-rooted and each of them is interlaced
by $h_{\mathcal{L}}(x)$.

###### Proof.

Part (a) follows by substituting ${\mathbf{a}}=1$ and ${\mathbf{b}}=x$ in the
formulas of Theorem 2.2. Indeed, if $w$ is any word of degree $n-1$ in
${\mathbf{a}}$ and ${\mathbf{b}}$ having $k$ letters equal to ${\mathbf{b}}$,
then $D(w)$ can be expressed as a sum of $2n-2$ words of degree $n$ in
${\mathbf{a}}$ and ${\mathbf{b}}$, of which $2k$ have $k$ letters equal to
${\mathbf{b}}$ and $2n-2k-2$ have $k+1$ letters equal to ${\mathbf{b}}$. As a
result, Equation (2) implies that

$h_{{\rm Pyr}({\mathcal{L}})}(x)\ =\
(1+x)h_{\mathcal{L}}(x)+\delta_{n}(h_{\mathcal{L}}(x)),$

where $\delta_{n}:{\mathbb{R}}_{n-1}[x]\rightarrow{\mathbb{R}}_{n}[x]$ is the
linear map defined by $\delta_{n}(x^{k})=kx^{k}+(n-k-1)x^{k+1}$ for $0\leq
k\leq n-1$. Clearly, $\delta_{n}(h(x))=(n-1)xh(x)+(x-x^{2})h^{\prime}(x)$ for
every $h(x)\in{\mathbb{R}}_{n-1}[x]$ and Equation (8) follows. The same
argument shows that

$h_{{\rm Prism}({\mathcal{L}})}(x)\ =\
(1+x)h_{\mathcal{L}}(x)+2\,\delta_{n}(h_{\mathcal{L}}(x))$

and yields Equation ((a)).

For part (b) we rewrite Equations (8) and ((a)) as

(10) $\displaystyle\frac{h_{{\rm Pyr}({\mathcal{L}})}(x)}{(1-x)^{n+2}}$
$\displaystyle=$ $\displaystyle\frac{{\rm d}}{{\rm
d}x}\left(\,\frac{xh_{\mathcal{L}}(x)}{(1-x)^{n+1}}\right),$ (11)
$\displaystyle\frac{h_{\mathcal{L}}(x)h_{{\rm
Prism}({\mathcal{L}})}(x)}{(1-x)^{2n+3}}$ $\displaystyle=$
$\displaystyle\frac{{\rm d}}{{\rm
d}x}\left(\,\frac{x(h_{\mathcal{L}}(x))^{2}}{(1-x)^{2n+2}}\right).$

Since ${\mathcal{L}}$ is Cohen–Macaulay, $h_{\mathcal{L}}(x)$ has nonnegative
coefficients. Since the latter is assumed to be real-rooted and has constant
term equal to 1, all its roots are negative. Let $d$ be the degree of
$h_{\mathcal{L}}(x)$. Then, $d\leq n-1$ and, as it follows from part (a) and
its proof, $h_{{\rm Pyr}({\mathcal{L}})}(x)$ and $h_{{\rm
Prism}({\mathcal{L}})}(x)$ have nonnegative coefficients and degree $d+1$.
Applying Rolle’s theorem and taking into account that

$\lim_{x\rightarrow-\infty}\frac{xh_{\mathcal{L}}(x)}{(1-x)^{n+1}}\ =\
\lim_{x\rightarrow-\infty}\frac{x(h_{\mathcal{L}}(x))^{2}}{(1-x)^{2n+2}}\ =\
0$

we conclude from Equations (10) and (11) that each of $h_{{\rm
Pyr}({\mathcal{L}})}(x)$ and $h_{{\rm Prism}({\mathcal{L}})}(x)$ has $d+1$
negative roots which are interlaced by those of $h_{\mathcal{L}}(x)$ and the
proof follows. ∎

######  Corollary 5.6.

Let ${\mathcal{M}}$ and ${\mathcal{M}}^{\prime}$ be matroids with lattices of
flats ${\mathcal{L}}$ and ${\mathcal{L}}^{\prime}$, respectively. If
$h_{\mathcal{L}}(x)$ is real-rooted and ${\mathcal{M}}^{\prime}$ is obtained
by successively adding coloops to ${\mathcal{M}}$, then
$h_{{\mathcal{L}}^{\prime}}(x)$ is real-rooted as well.

###### Proof.

This follows from part (a) of Theorem 5.5, since ${\mathcal{L}}^{\prime}$ is
isomorphic to ${\rm Pyr}({\mathcal{L}})$ for every matroid
${\mathcal{M}}^{\prime}$ which can be obtained by adding one coloop to
${\mathcal{M}}$. ∎

The following corollary of Theorem 5.5 provides classes of nonsimplicial,
nonsimple and noncubical polytopes in any dimension, the barycentric
subdivisions of which have real-rooted $f$-polynomials. For instance, it
implies that any polytope which is obtained from one of dimension at most 5 by
applying successively the pyramid or the prism construction has this property.

######  Corollary 5.7.

Let ${\mathcal{P}}$ be a convex polytope. If
$h_{{\mathcal{F}}({\mathcal{P}})}(x)$ is real-rooted, then
$h_{{\mathcal{F}}({\rm Pyr}({\mathcal{P}}))}(x)$ and $h_{{\mathcal{F}}({\rm
Prism}({\mathcal{P}}))}(x)$ have the same property and each of them is
interlaced by $h_{{\mathcal{F}}({\mathcal{P}})}(x)$.

The near-pencil of rank $n$ on $m$ elements can be obtained from the rank two
uniform matroid on $m-n+2$ elements by adding $n-2$ coloops. Near-pencils and
uniform matroids are known [17, Section 3] to minimize and maximize,
respectively, the entries of the flag $h$-vector of the lattice of flats among
all matroids of given rank and number of elements. The following statement
confirms Conjecture 1.2 for the lattices of flats of these matroids and
completes the proof of Theorem 1.3. Let us denote by
${\mathcal{L}}({\mathcal{M}})$ the lattice of flats of a matroid
${\mathcal{M}}$. The Eulerian polynomial $B_{n}(x)$ can be defined (see, for
instance, [28, Sections 3.1 and 3.4]) as
$h_{{\mathcal{F}}({\mathcal{P}})}(x)$, where ${\mathcal{P}}$ is the
$n$-dimensional cube, or as

$B_{n}(x)\ =\ \sum_{w\in{\mathfrak{S}}^{\pm}_{n}}x^{{\rm des}_{B}(w)},$

where ${\mathfrak{S}}^{\pm}_{n}$ denotes (this is nonstandard notation) the
set of signed permutations of $[n]$, meaning sequences
$w=(w_{1},w_{2},\dots,w_{n})$ for which
$(|w_{1}|,|w_{2}|,\dots,|w_{n}|)\in{\mathfrak{S}}_{n}$, and ${\rm des}_{B}(w)$
is the number of indices $i\in\\{0,1,\dots,n-1\\}$ such that $w_{i}>w_{i+1}$,
where $w_{0}:=0$.

######  Proposition 5.8.

Let ${\mathcal{M}}_{m,n}$ and ${\mathcal{U}}_{m,n}$ denote the near-pencil and
the uniform matroid, respectively, of rank $n$ on $m$ elements and let
${\mathcal{F}}({\mathcal{M}}_{m,n})$ and ${\mathcal{F}}({\mathcal{U}}_{m,n})$
be the face lattices of any zonotopes with associated matroids
${\mathcal{M}}_{m,n}$ and ${\mathcal{U}}_{m,n}$, respectively.

  * (a)

The polynomials $h_{{\mathcal{L}}({\mathcal{M}}_{m,n})}(x)$ and
$h_{{\mathcal{L}}({\mathcal{U}}_{m,n})}(x)$ have only real roots. Moreover,
the latter is interlaced by the Eulerian polynomial $A_{n}(x)$.

  * (b)

The polynomials $h_{{\mathcal{F}}({\mathcal{M}}_{m,n})}(x)$ and
$h_{{\mathcal{F}}({\mathcal{U}}_{m,n})}(x)$ have only real roots. Moreover,
the latter is interlaced by the Eulerian polynomial $B_{n-1}(x)$.

###### Proof.

By definition, the near-pencil ${\mathcal{M}}_{m,n}$ is obtained by
successively adding coloops to a rank two matroid. Thus, the real-rootedness
of $h_{{\mathcal{L}}({\mathcal{M}}_{m,n})}(x)$ follows from Corollary 5.6.
Similarly, since adding a coloop to a linear matroid ${\mathcal{M}}$ with
associated zonotope ${\mathcal{Z}}$ yields a matroid whose associated zonotope
is combinatorially isomorphic to the prism over ${\mathcal{Z}}$, the real-
rootedness of $h_{{\mathcal{F}}({\mathcal{M}}_{m,n})}(x)$ follows from
Corollary 5.7.

Since the geometric lattice ${\mathcal{L}}({\mathcal{U}}_{m,n})$, with its
maximum element removed, is a simplicial poset with nonnegative $h$-vector,
the real-rootedness of $h_{{\mathcal{L}}({\mathcal{U}}_{m,n})}(x)$ is a
special case of [12, Theorem 2]. Similarly, since the zonotope associated to
the uniform matroid ${\mathcal{U}}_{m,n}$ is an $n$-dimensional cubical
polytope, the statement that $h_{{\mathcal{F}}({\mathcal{U}}_{m,n})}(x)$ is
real-rooted and interlaced by $B_{n-1}(x)$ is a special case of [4, Corollary
3.5]. Thus, it remains to show that
$h_{{\mathcal{L}}({\mathcal{U}}_{m,n})}(x)$ is interlaced by $A_{n}(x)$.

To simplify the notation, we set
${\mathcal{L}}:={\mathcal{L}}({\mathcal{U}}_{m,n})$ and recall that
$\overline{{\mathcal{L}}}$ is combinatorially isomorphic to the poset of
nonempty faces of the $(n-2)$-dimensional skeleton, say $\Delta_{m,n-1}$, of
the $(m-1)$-dimensional simplex $2^{[m]}$. As a result,
$\Delta(\overline{{\mathcal{L}}})$ is combinatorially isomorphic to the
barycentric subdivision ${\rm sd}(\Delta_{m,n-1})$ and
$h_{\mathcal{L}}(x)=h({\rm sd}(\Delta_{m,n-1}),x)$. As explained in [3] [4,
Section 1], this expression implies that

$h_{\mathcal{L}}(x)\ =\ \sum_{k=0}^{n-1}c_{k}p_{n-1,k}(x),$

where $h(\Delta_{m,n-1},x)=\sum_{k=0}^{n-1}c_{k}x^{k}$ and
$(p_{n-1,0}(x),p_{n-1,1}(x),\dots,p_{n-1,n-1}(x))$ is an interlacing sequence
of real-rooted polynomials with nonnegative coefficients, originally defined
in [12], which sum to $A_{n}(x)$. Since $\Delta_{m,n-1}$ is the one-coskeleton
of the Cohen–Macaulay simplicial complex $\Delta_{m,n}$, as explained in the
proof of [6, Theorem 6.1] we must have $1=c_{0}\leq c_{1}\leq\cdots\leq
c_{n-1}$. An application of [5, Lemma 2.2 (c)] [14, Lemma 8] then shows that
$\sum_{k=0}^{n-1}p_{n-1,k}(x)=A_{n}(x)$ interlaces
$\sum_{k=0}^{n-1}c_{k}p_{n-1,k}(x)=h_{\mathcal{L}}(x)$ and the proof follows.
∎

Computational data, along with part (b) of Proposition 5.8, suggest the
following question.

######  Question 5.9.

Is $h_{{\mathcal{F}}({\mathcal{Z}})}(x)$ interlaced by $B_{n-1}(x)$ for every
$n$-dimensional zonotope ${\mathcal{Z}}$?

##  6\. An application to the second barycentric subdivision

As already mentioned in Section 3, the $n$th Eulerian polynomial $A_{n}(x)$ is
equal to the $h$-polynomial of the first barycentric subdivision of the
boundary complex $\partial\Delta_{n}$ of the $(n-1)$-dimensional simplex
$\Delta_{n}$. As an application of results of previous sections, we now give
explicit combinatorial interpretations of the $h$-polynomial of the second
barycentric subdivision of $\partial\Delta_{n}$ and of its associated
$\gamma$-polynomial, thus answering a question raised in [2, Example 4.4].

Let us write ${\rm sd}^{2}(\Delta)={\rm sd}({\rm sd}(\Delta))$ for the second
barycentric subdivision of a simplicial complex $\Delta$. The polynomial
$h({\rm sd}^{2}(\partial\Delta_{n}),x)$ is an $x$-analogue of $(n-1)!\,n!$,
which is the number of $(n-2)$-dimensional faces (facets) of ${\rm
sd}^{2}(\Delta_{n})$. For small values of $n$,

$h({\rm sd}^{2}(\partial\Delta_{n}),x)\ =\ \begin{cases}1+x,&\text{if
$n=2$}\\\ 1+10x+x^{2},&\text{if $n=3$}\\\ 1+71x+71x^{2}+x^{3},&\text{if
$n=4$}\\\ 1+536x+1806x^{2}+536x^{3}+x^{4},&\text{if $n=5$}\\\
1+4677x+38522x^{2}+38522x^{3}+4677x^{4}+x^{5},&\text{if $n=6$}.\end{cases}$

Since $(n-1)!\,n!$ is equal to $2^{n-1}$ times the number of maximal chains of
the partition lattice $\Pi_{n}$, and the latter is equal to the number of
elements of the multiset ${\mathcal{A}}_{n}$, it is not unreasonable to expect
that the coefficients of $h({\rm sd}^{2}(\partial\Delta_{n}),x)$ count signed
elements of ${\mathcal{A}}_{n}$ by some descent-type statistic. Indeed, let us
denote by ${\mathcal{A}}^{\pm}_{n}$ the multiset of all signed elements of
${\mathcal{A}}_{n}$, meaning sequences
$\tau=(\tau_{1},\tau_{2},\dots,\tau_{n-1})$ such that
$(|\tau_{1}|,|\tau_{2}|,\dots,|\tau_{n-1}|)\in{\mathcal{A}}_{n}$. For such
$\tau\in{\mathcal{A}}^{\pm}_{n}$, let us denote by ${\rm eDes}_{B}(\tau)$ the
set of indices $i\in\\{0,1,\dots,n-2\\}$ for which

  * $\bullet$

$\tau_{i}>\tau_{i+1}$, or

  * $\bullet$

$\tau_{i}=\tau_{i+1}>0$,

where $\tau_{0}:=0$, and by ${\rm edes}_{B}(\tau)$ the cardinality of ${\rm
eDes}_{B}(\tau)$. For example, the multiset ${\mathcal{A}}^{\pm}_{3}$ consists
of the twelve signed words $(\pm 1,\pm 1)$, $(\pm 1,\pm 1)$ and $(\pm 1,\pm
2)$. There is one such word $\tau$ with ${\rm edes}_{B}(\tau)=0$, ten with
${\rm edes}_{B}(\tau)=1$ and one with ${\rm edes}_{B}(\tau)=2$.

The combinatorial interpretation provided for the coefficients
$\gamma_{n,2,i}$ in the following statement is analogous to the one provided
by Petersen [19, Proposition 4.15] [20, Section 13.2] for the coefficients of
the $\gamma$-polynomial associated to the Eulerian polynomial $B_{n}(x)$. For
$\sigma\in{\mathcal{A}}_{n}$, we denote by ${\rm lpeak}(\sigma)$ the number of
descents $i\in[n-2]$ of $\sigma$ for which either $i-1$ is an ascent of
$\sigma$, or $i=1$.

######  Proposition 6.1.

For every $n\geq 2$

(12) $\displaystyle h({\rm sd}^{2}(\partial\Delta_{n}),x)$ $\displaystyle=$
$\displaystyle\sum_{\tau\in{\mathcal{A}}^{\pm}_{n}}x^{{\rm edes}_{B}(\tau)}$
(13) $\displaystyle=$
$\displaystyle\sum_{i=0}^{\lfloor(n-1)/2\rfloor}\gamma_{n,2,i}\,x^{i}(1+x)^{n-1-2i},$

where $\gamma_{n,2,i}$ is equal to $4^{i}$ times the number of words
$\sigma\in{\mathcal{A}}_{n}$ with ${\rm lpeak}(\sigma)=i$.

###### Proof.

The poset of faces of ${\rm sd}(\partial\Delta_{n})$ is combinatorially
isomorphic to ${\mathcal{F}}({\mathcal{H}}_{n})$, where ${\mathcal{H}}_{n}$ is
the Coxeter hyperplane arrangement of type $A_{n-1}$. As a result, we have
$h({\rm sd}^{2}(\partial\Delta_{n}),x)=h({\rm
sd}({\mathcal{Z}}_{n}),x)=h_{{\mathcal{F}}({\mathcal{Z}}_{n})}(x)$, where
${\mathcal{Z}}_{n}$ is the zonotope associated to ${\mathcal{H}}_{n}$ (known
as the $(n-1)$-dimensional permutohedron). Since the geometric lattice
${\mathcal{L}}({\mathcal{H}}_{n})$ is combinatorially isomorphic to $\Pi_{n}$,
applying Proposition 5.3 to ${\mathcal{Z}}_{n}$ we get

$h({\rm sd}^{2}(\partial\Delta_{n}),x)\
=\sum_{S\subseteq[n-2]}\beta_{\Pi_{n}}(S)\,(4x)^{{\rm
lpeak}(S)}(1+x)^{n-1-2{\rm lpeak}(S)}.$

Combined with Proposition 4.1, this expression yields Equation (13). To deduce
Equation (12) from that, it suffices to show that for every
$\sigma\in{\mathcal{A}}_{n}$

(14) $\sum_{\tau\in\Sigma(\sigma)}x^{{\rm edes}_{B}(\tau)}\ =\ (4x)^{{\rm
lpeak}(\sigma)}(1+x)^{n-1-2{{\rm lpeak}(\sigma)}},$

where $\Sigma(\sigma)$ stands for the set of all words
$(\tau_{1},\tau_{2},\dots,\tau_{n-1})$ such that
$(|\tau_{1}|,|\tau_{2}|,\dots,|\tau_{n-1}|)=\sigma$. Indeed, given
$\sigma=(\sigma_{1},\sigma_{2},\dots,\sigma_{n-1})\in{\mathcal{A}}_{n}$ and
$\tau=(\tau_{1},\tau_{2},\dots,\tau_{n-1})\in\Sigma(\sigma)$ such that
$\tau_{i}=\varepsilon_{i}\sigma_{i}$ for every $i\in[n-1]$, with
$\varepsilon_{i}\in\\{-1,1\\}$, one can verify that

  * $\bullet$

$0\in{\rm eDes}_{B}(\tau)$ if and only if $\varepsilon_{1}=-1$,

  * $\bullet$

for $\sigma_{i}<\sigma_{i+1}$, we have $i\in{\rm eDes}_{B}(\tau)$ if and only
if $\varepsilon_{i+1}=-1$,

  * $\bullet$

for $\sigma_{i}\geq\sigma_{i+1}$, we have $i\in{\rm eDes}_{B}(\tau)$ if and
only if $\varepsilon_{i}=1$.

Then, the argument given for permutations $\sigma\in{\mathfrak{S}}_{n}$ in
[20, Section 13.2] applies verbatim to our situation and proves (14); the
details are left to the interested reader. ∎

Acknowledgments. This work was supported by the Hellenic Foundation for
Research and Innovation (H.F.R.I.) under the ‘2nd Call for H.F.R.I. Research
Projects to support Faculty Members & Researchers’. The authors thank Eleni
Tzanaki for her generous help with all computations (via Sage [30] and the
database of matroids, publicly available at https://www-
imai.is.s.u-tokyo.ac.jp/ ymatsu/matroid/index.html) mentioned in this paper
and Luis Feronni for useful comments.

## References

  * [1] K. Adiprasito, S.A. Papadakis and V. Petrotou, Anisotropy, biased pairings and the Lefschetz property for pseudomanifolds and cycles, arXiv:2101.07245.
  * [2] C.A. Athanasiadis, Gamma-positivity in combinatorics and geometry, Sém. Lothar. Combin.  77 (2018), Article B77i, 64pp (electronic).
  * [3] C.A. Athanasiadis, Face numbers of uniform triangulations of simplicial complexes, Int. Math. Res. Not.  2022 (2022), 15756–15787.
  * [4] C.A. Athanasiadis, Face numbers of barycentric subdivisions of cubical complexes, Israel J. Math.  246 (2021), 423–439.
  * [5] C.A. Athanasiadis, J-M. Brunink and M. Juhnke-Kubitzke, Combinatorics of antiprism triangulations, Discrete Comput. Geom.  68 (2022), 72–106.
  * [6] C.A. Athanasiadis and E. Tzanaki, Symmetric decompositions, triangulations and real-rootedness, Mathematika  67 (2021), 840–859.
  * [7] L.J. Billera, R. Ehrenborg and M. Readdy, The c-2d-index of oriented matroids, J. Combin. Theory Series A  80 (1997), 79–105.
  * [8] A. Björner, The homology and shellability of matroids and geometric lattices, in Matroid Applications (N. White, ed.), Encyclopedia of Mathematics and its Applications  40, Cambridge University Press, Cambridge, 1992, pp. 226–283.
  * [9] A. Björner, M. Las Vergnas, B. Sturmfels, N. White and G.M. Ziegler, Oriented Matroids, Encyclopedia of Mathematics and Its Applications  46, Cambridge University Press, Cambridge, 1993.
  * [10] P. Brändén, Counterexamples to the Neggers–Stanley conjecture, Electron. Res. Announc. Amer. Math. Soc.  10 (2004), 155–158 (electronic).
  * [11] P. Brändén, Unimodality, log-concavity, real-rootedness and beyond, in Handbook of Combinatorics (M. Bona, ed.), CRC Press, 2015, pp. 437–483.
  * [12] F. Brenti and V. Welker, $f$-vectors of barycentric subdivisions, Math. Z.  259 (2008), 849–865.
  * [13] R. Ehrenborg and M. Readdy, Coproducts and the cd-Index, J. Algebr. Comb.  8 (1998), 273–299.
  * [14] J. Haglund, K. Ono and D.G. Wagner, Theorems and conjectures involving rook polynomials with only real zeros, in Topics in Number Theory (University Park, PA, 1997), Math. Appl.  467, Kluwer Academic Publishers, Dordrecht, 1999, pp. 207–221.
  * [15] S.R. Gal, Real root conjecture fails for five- and higher-dimensional spheres, Discrete Comput. Geom.  34 (2005), 269–284.
  * [16] J. Neggers, Representations of finite partially ordered sets, J. Comb. Inform. Syst. Sci.  3 (1978), 113–133.
  * [17] K. Nyman and E. Swartz, Inequalities for the $h$-vectors and flag $h$-vectors of geometric lattices, Discrete Comput. Geom.  32 (2004), 533–548.
  * [18] J.G. Oxley, Matroid Theory, Oxford Graduate Texts in Mathematics  3, Oxford University Press, second edition, New York, 2011.
  * [19] T.K. Petersen, Enriched $P$-partitions and peak algebras, Adv. Math.  209 (2007), 561–610.
  * [20] T.K. Petersen, Eulerian Numbers, Birkhäuser Advanced Texts, Birkhäuser, 2015.
  * [21] C.D. Savage and M. Visontai, The $s$-Eulerian polynomials have only real roots, Trans. Amer. Math. Soc.  367 (2015), 1441–1466.
  * [22] R.P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, in Graph Theory and its Applications: East and West, Annals of the New York Academy of Sciences  576, New York Acad. Sci., New York, 1989, pp. 500–535.
  * [23] R.P. Stanley, Combinatorics and Commutative Algebra, second edition, Birkhäuser, Basel, 1996.
  * [24] R.P. Stanley, Graph colorings and related symmetric functions: ideas and applications: a description of results, interesting applications & notable open problems, Discrete Math.  193 (1998), 267–286.
  * [25] R.P. Stanley, Enumerative Combinatorics, vol. 1, Cambridge Studies in Advanced Mathematics  49, Cambridge University Press, second edition, Cambridge, 2011.
  * [26] J.R. Stembridge, Counterexamples to the poset conjectures of Neggers, Stanley, and Stembridge, Trans. Amer. Math. Soc.  359 (2007), 1115–1128.
  * [27] S. Sundaram, The homology representations of the symmetric group and Cohen–Macaulay subposets of the partition lattice, Adv. Math.  104 (1994), 225–296.
  * [28] E. Steingrímsson, Permutation statistics of indexed and poset permutations, Ph.D. thesis, MIT, 1992.
  * [29] E. Swartz, $g$-Elements, finite buildings and higher Cohen–Macaulay connectivity, J. Combin. Theory Series A  113 (2006), 1305–1320.
  * [30] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.4), 2018, https://www.sagemath.org.
  * [31] M. Wachs, Poset Topology: Tools and Applications, in _Geometric Combinatorics_ (E. Miller, V. Reiner and B. Sturmfels, eds.), IAS/Park City Mathematics Series  13, pp. 497–615, Amer. Math. Society, Providence, RI, 2007.
  * [32] G.M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics  152, Springer-Verlag, New York, 1995.


#  A Recurrent Neural Model with Attention for
the Recognition of Chinese Implicit Discourse Relations

Samuel Rönnqvist1,2,∗, Niko Schenk2,∗ and Christian Chiarcos2
1Turku Centre for Computer Science – TUCS, Åbo Akademi University, Turku,
Finland
2Applied Computational Linguistics Lab, Goethe University, Frankfurt am Main,
Germany
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

We introduce an attention-based Bi-LSTM for Chinese implicit discourse
relations and demonstrate that modeling argument pairs as a joint sequence can
outperform word order-agnostic approaches. Our model benefits from a partial
sampling scheme and is conceptually simple, yet achieves state-of-the-art
performance on the Chinese Discourse Treebank. We also visualize its attention
activity to illustrate the model’s ability to selectively focus on the
relevant parts of an input sequence.

##  1 Introduction

††∗Both first authors contributed equally to this work.

True text understanding is one of the key goals in Natural Language Processing
and requires capabilities beyond the lexical semantics of individual words or
phrases. Natural language descriptions are typically driven by an inter-
sentential coherent structure, exhibiting specific _discourse_ properties,
which in turn contribute significantly to the global meaning of a text.
Automatically detecting how meaning units are organized benefits practical
downstream applications, such as question answering (Sun and Chai, 2007),
recognizing textual entailment (Hickl, 2008), sentiment analysis (Trivedi and
Eisenstein, 2013), or text summarization (Hirao et al., 2013).

Various formalisms in terms of semantic coherence frameworks have been
proposed to account for these contextual assumptions Mann and Thompson (1988);
Lascarides and Asher (1993); Webber (2004). The annotation schemata of the
Penn Discourse Treebank (Prasad et al., 2008, PDTB) and the Chinese Discourse
Treebank (Zhou and Xue, 2012, CDTB), for instance, define discourse units as
syntactically motivated character spans in the text, augmented with relations
pointing from the second argument (_Arg2_ , prototypically, a discourse unit
associated with an explicit discourse marker) to its antecedent, i.e., the
discourse unit _Arg1_. Relations are labeled with a relation type (its sense)
and the associated discourse marker. Both, PDTB and CDTB, distinguish
_explicit_ from _implicit_ relations depending on the presence of such a
marker (e.g., _because_ / 因 ).111The set of relation types and senses is
completed by alternative lexicalizations (AltLex/discourse marker rephrased),
and entity relations (EntRel/anaphoric coherence). Sense classification for
implicit relations is by far more challenging because the argument pairs lack
the marker as an important feature. Consider, for instance, the following
example from the CDTB as implicit Conjunction:

_Arg1_ : 会谈 就 一些 原则 和 具体 问题 进行 了 深入 讨论 ， 达成 了 一些 谅解  In the talks, they
discussed some principles and specific questions in depth, and reached some
understandings

_Arg2_ : 双方 一致 认为 会谈 具有 积极 成果  Both sides agree that the talks have positive
results

Motivation: Previous work on implicit sense labeling is heavily feature-rich
and requires domain-specific, semantic lexicons Pitler et al. (2009); Feng and
Hirst (2012); Huang and Chen (2011). Only recently, resource-lean
architectures have been proposed. These promising neural methods attempt to
infer latent representations appropriate for implicit relation classification
Zhang et al. (2015); Ji et al. (2016); Chen et al. (2016). So far,
unfortunately, these models have been evaluated _only_ on four top-level
senses—sometimes even with inconsistent evaluation setups.222E.g., four binary
classifiers vs. four-way classification. Furthermore, most systems have
initially been designed for the English PDTB and involve complex, task-
specific architectures Liu and Li (2016), while discourse modeling techniques
for Chinese have received very little attention in the literature and are
still seriously underrepresented in terms of publicly available systems. What
is more, over 80% of all words in Chinese discourse relations are
implicit—compared to only 52% in English Zhou and Xue (2012).

Recently, in the context of the CoNLL 2016 shared task Xue et al. (2016), a
first independent evaluation platform beyond class level has been established.
Surprisingly, the best performing neural architectures to date are standard
_feedforward_ networks, cf. Wang and Lan (2016); Schenk et al. (2016); Qin et
al. (2016). Even though these specific models completely ignore word order
within arguments, such feedforward architectures have been claimed by
Rutherford et al. (2016) to generally outperform any thoroughly-tuned
recurrent architecture.

Our Contribution: In this work, we release the first attention-based
_recurrent_ neural sense classifier, specifically developed for Chinese
implicit discourse relations. Inspired by Zhou et al. (2016), our system is a
practical adaptation of the recent advances in relation modeling extended by a
novel sampling scheme.

Contrary to previous assertions by Rutherford et al. (2016), our model
demonstrates superior performance over traditional bag-of-words approaches
with feedfoward networks by treating discourse arguments as a joint sequence.
We evaluate our method within an independent framework and show that it
performs very well beyond standard class-level predictions, achieving state-
of-the-art accuracy on the CDTB test set.

We illustrate how our model’s attention mechanism provides means to highlight
those parts of an input sequence that are relevant for the classification
decision, and thus, it may enable a better understanding of the implicit
discourse parsing problem. Our proposed network architecture is flexible and
largely language-independent as it operates only on word embeddings. It stands
out due to its structural simplicity and builds a solid ground for further
development towards other textual domains.

##  2 Approach

Figure 1: The attention-based bidirectional LSTM network for the task of
modeling argument pairs for Chinese implicit discourse relations.

We propose the use of an attention-based bidirectional Long Short-Term Memory
(Hochreiter and Schmidhuber, 1997, LSTM) network to predict senses of
discourse relations. The model draws upon previous work on LSTM, in particular
its bidirectional mode of operation Graves and Schmidhuber (2005), attention
mechanisms for recurrent models Bahdanau et al. (2014); Hermann et al. (2015),
and the combined use of these techniques for entity relation recognition in
annotated sequences Zhou et al. (2016). More specifically, our model is a
flexible recurrent neural network with capabilities to _sequentially_ inspect
tokens and to highlight which parts of the input sequence are most informative
for the discourse relation recognition task, using the weighting provided by
the attention mechanism. Furthermore, the model benefits from a novel sampling
scheme for arguments, as elaborated below. The system is learned in an end-to-
end manner and consists of multiple layers, which are illustrated in Figure 1.

First, token sequences are taken as input and special markers (<ARG1>,
</ARG1>, etc.) are inserted into the corresponding positions to inform the
model on the start and end points of argument spans. This way, we can ensure a
general flexibility in modeling discourse units and could easily extend them
with additional context, for instance. In our experiments on implicit
arguments, only the tokens in the respective spans are considered. Note that,
unlike previous works, our approach models _Arg1_ -_Arg2_ pairs as a _joint_
sequence and does not first compute intermediate representations of arguments
separately.

Second, an input layer encodes tokens using one-hot vector representations
($t_{i}$ for tokens at positions $i\in[1,k]$), and a subsequent embedding
layer provides a dense representation ($e_{i}$) to serve as input for the
recurrent layers. The embedding layer is initialized using pre-trained word
vectors, in our case 300-dimensional Chinese Gigaword vectors Graff and Chen
(2005).333http://www.cs.brandeis.edu/~clp/conll16st/dataset.html These
embeddings are further tuned as the network is trained towards the prediction
task. Embeddings for unknown tokens, e.g., markers, are trained by
backpropagation only. Note that, tokens, markers and the pre-trained vectors
represent the only source of information for the prediction task.

For the recurrent setup, we use a layer of LSTM networks in a bidirectional
manner, in order to better capture dependencies between parts of the input
sequence by inspection of both left and right-hand-side contexts at each time
step. The LSTM holds a state representation as a continuous vector passed to
the subsequent time step, and it is capable of modeling long-range
dependencies due to its gated memory. The forward ($A^{\prime}$) and backward
($A^{\prime\prime}$) LSTMs traverse the sequence $e_{i}$, producing sequences
of vectors $h^{\prime}_{i}$ and $h^{\prime\prime}_{i}$ respectively, which are
then summed together (indicated by $\oplus$ in Figure 1).

The resulting sequence of vectors $h_{i}$ is reduced into a single vector and
fed to the final softmax output layer in order to classify the sense label $y$
of the discourse relation. This vector may be obtained either as the final
vector $h$ produced by an LSTM, or through pooling of all $h_{i}$, or by using
attention, i.e., as a weighted sum over $h_{i}$. While the model may be
somewhat more difficult to optimize using attention, it provides the added
benefit of interpretability, as the weights highlight to what extent the
classifier considers the LSTM state vectors at each token during modeling.
This is particularly interesting for discourse parsing, as most previous
approaches have provided little support for pinpointing the driving features
in each argument span.

Finally, the attention layer contains the trainable vector $w$ (of the same
dimensionality as vectors $h_{i}$) which is used to dynamically produce a
weight vector $\alpha$ over time steps $i$ by:

$\alpha=softmax(w^{T}tanh(H))$

where $H$ is a matrix consisting of vectors $h_{i}$. The output layer $r$ is
the weighted sum of vectors in $H$:

$r=H\alpha^{T}$

Partial Argument Sampling: For the purpose of enlarging the instance space of
training items in the CDTB, and thus, in order to improve the predictive
performance of the model, we propose a novel _partial sampling_ scheme of
arguments, whereby the model is trained and validated on sequences containing
both arguments, as well as _single_ arguments. A data point $(a_{1},a_{2},y)$,
with $a_{i}$ being the token sequence of argument $i$, is expanded into
$\\{(a_{1},a_{2},y),(a_{1},a_{2},y),(a_{1},y),(a_{2},y)\\}$. We duplicate bi-
argument samples $(a_{1},a_{2},y)$ (in training and development data only) to
balance their frequencies against single-argument samples.

Two lines of motivation support the inclusion of single argument training
examples, grounded in linguistics and machine learning, respectively. First,
it has been shown that single arguments in isolation can evoke a strong
expectation towards a certain implicit discourse relation, cf. Asr and Demberg
(2015) and, in particular, Rohde and Horton (2010) in their psycholinguistic
study on _implicit causality verbs_. Second, the procedure may encourage the
model to learn better representations of individual argument spans in support
of modeling of arguments in composition, cf. LeCun et al. (2015). Due to these
aspects, we believe this data augmentation technique to be effective in
reinforcing the overall robustness of our model.

Implementational Details: We train the model using fixed-length sequences of
256 tokens with zero padding at the beginning of shorter sequences and
truncate longer ones. Each LSTM has a vector dimensionality of 300, matching
the embedding size. The model is regularized by $0.5$ dropout rate between the
layers and weight decay ($2.5e^{-6}$) on the LSTM inputs. We employ Adam
optimization Kingma and Ba (2014) using the cross-entropy loss function with
mini batch size of 80.444The model is implemented in _Keras_
https://keras.io/.

CDTB Development Set |  | CDTB Test Set
---|---|---
Rank | System | % accuracy |  | Rank | System | % accuracy
1 | Wang and Lan (2016) | 73.53 |  | 1 | Wang and Lan (2016) | 72.42
2 | Qin et al. (2016) | 71.57 |  | 2 | Schenk et al. (2016) | 71.87
3 | Schenk et al. (2016) | 70.59 |  | 3 | Rutherford and Xue (2016) | 70.47
4 | Rutherford and Xue (2016) | 68.30 |  | 4 | Qin et al. (2016) | 67.41
5 | Weiss and Bajec (2016) | 66.67 |  | 5 | Weiss and Bajec (2016) | 64.07
6 | Weiss and Bajec (2016) | 61.44 |  | 6 | Weiss and Bajec (2016) | 63.51
7 | Jian et al. (2016) | 21.90 |  | 7 | Jian et al. (2016) | 21.73
| This Paper: | 93.52∗ |  |  | This Paper: | 73.01
Table 1: Non-explicit parser scores on the official CoNLL 2016 CDTB development and test sets. (∗Scores on development set are obtained through partial sampling and are not directly comparable.) Sense Label | Training | Dev’t | Test |
---|---|---|---|---
Conjunction | 5,174 | 189 | 228 |
majority class | (66.3%) | (62.8%) | (64.8%) |
Expansion | 1,188 | 48 | 40 |
EntRel | 1,099 | 50 | 71 |
Causation | 187 | 10 | 8 |
Contrast | 66 | 3 | 1 |
Purpose | 56 | 1 | 3 |
Conditional | 26 | 0 | 1 |
Temporal | 26 | 0 | 0 |
Progression | 7 | 0 | 0 |
# impl. rels | 7,804 | 301 | 352 |
Table 2: Implicit sense labels in the CDTB.

##  3 Evaluation

We evaluate our recurrent model on the CoNLL 2016 shared task
data555http://www.cs.brandeis.edu/~clp/conll16st/ which include the official
training, development and test sets of the CDTB; cf. Table 2 for an overview
of the implicit sense distribution.666Note that, in the CDTB, implicit
relations appear almost _three times more often_ than explicit relations. Out
of these, 65% appear within the same sentence. Finally, 25 relations in the
training set have two labels.

In accordance with previous setups Rutherford et al. (2016), we treat entity
relations (EntRel) as implicit and exclude AltLex relations. In the
evaluation, we focus on the _sense-only_ track, the subtask for which gold
arguments are provided and a system is supposed to label a given argument pair
with the correct sense. The results are shown in Table 1.

With our proposed architecture it is possible to correctly label 257/352
(73.01%) of implicit relations on the test set, outperforming the best
feedforward system of Wang and Lan (2016) and all other word order-agnostic
approaches. Development and test set performances suggest the robustness of
our approach and its ability to generalize to unseen data.

Ablation Study: We perform an ablation study to quantitatively assess the
contribution of two of the characteristic aspects of our model. First, we
compare the use of the attention mechanism against the simpler alternative of
feeding the final LSTM hidden vectors ($h^{\prime}_{k}$ and
$h^{\prime\prime}_{1}$) directly to the output layer. When attention is turned
off, this yields an absolute decrease in performance of 2.70% on the test set,
which is substantial and significant according to a Welch two-sample t-test
($p$ $<$ .001). Second, we independently compare the use of the partial
sampling scheme against training on the standard argument pairs in the CDTB.
Here, the absence of the partial sampling scheme yields an absolute decrease
in accuracy of 5.74% ($p$ $<$ .001), which demonstrates its importance for
achieving competitive performance on the task.

Performance on the PDTB: As a side experiment, we investigate the model’s
language independence by applying it to the implicit argument pairs of the
English PDTB. Due to computational time constraints we do not optimize
hyperparameters, but instead train the model using identical settings as for
Chinese, which is expected to lead to suboptimal performance on the evaluation
data. Nevertheless, we measure 27.09% accuracy on the PDTB test set
(surpassing the majority class baseline of 22.01%), which shows that the model
has potential to generalize across implicit discourse relations in a different
language.

Figure 2: Visualization of attention weights for Chinese characters with high
(dark blue) and low (light blue) intensities. The underlined English phrases
are semantically structure-shared by the two arguments.

Visualizing Attention Weights: Finally, in Figure 2, we illustrate the learned
attention weights which pinpoint important subcomponents within a given
implicit discourse relation. For the implicit Conjunction relation the weights
indicate a peak on the transition between the argument boundary, establishing
a connection between the semantically related terms _understandings–agree_.
Most EntRels show an opposite trend: here second arguments exhibit larger
intensities than _Arg1_ , as most entity relations follow the characteristic
writing style of newspapers by adding additional information by reference to
the same entity.

##  4 Summary & Outlook

In this work, we have presented the first attention-based recurrent neural
sense labeler specifically developed for Chinese implicit discourse relations.
Its ability to model discourse units sequentially and jointly has been shown
to be highly beneficial, both in terms of state-of-the-art performance on the
CDTB (outperforming word order-agnostic feedforward approaches), and also in
terms of insightful observations into the inner workings of the model through
its attention mechanism. The architecture is structurally simple, benefits
from partial argument sampling, and can be easily adapted to similar relation
recognition tasks. In future work, we intend to extend our approach to
different languages and domains, e.g., to the recent data sets on narrative
story understanding or question answering Mostafazadeh et al. (2016); Feng et
al. (2015). We believe that recurrent modeling of implicit discourse
information can be a driving force in successfully handling such complex
semantic processing tasks.777The code involved in this study is publicly
available at http://www.acoli.informatik.uni-frankfurt.de/resources/.

## Acknowledgments

The authors would like to thank Ayah Zirikly, Philip Schulz and Wei Ding for
their very helpful suggestions on an early draft version of the paper, and
also thank the anonymous reviewers for their valuable feedback and insightful
comments. We are grateful to Farrokh Mehryary for technical support with the
attention layer implementation. Computational resources were provided by CSC –
IT Centre for Science, Finland, and Arcada University of Applied Sciences,
Helsinki, Finland. Our research at Goethe University Frankfurt was supported
by the project ‘Linked Open Dictionaries (LiODi, 2015-2020)’, funded by the
German Ministry for Education and Research (BMBF).

## References

  * Asr and Demberg (2015) Fatemeh Torabi Asr and Vera Demberg. 2015.  Uniform Information Density at the Level of Discourse Relations: Negation Markers and Discourse Connective Omission.  In 11th International Conference on Computational Semantics (IWCS). page 118.  http://www.coli.uni-saarland.de/ fatemeh/iwcs2015.pdf.
  * Bahdanau et al. (2014) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014.  Neural Machine Translation by Jointly Learning to Align and Translate.  CoRR abs/1409.0473.  http://arxiv.org/abs/1409.0473.
  * Chen et al. (2016) Jifan Chen, Qi Zhang, Pengfei Liu, Xipeng Qiu, and Xuanjing Huang. 2016.  Implicit Discourse Relation Detection via a Deep Architecture with Gated Relevance Network.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 1: Long Papers.  http://aclweb.org/anthology/P/P16/P16-1163.pdf.
  * Feng et al. (2015) Minwei Feng, Bing Xiang, Michael R. Glass, Lidan Wang, and Bowen Zhou. 2015.  Applying deep learning to answer selection: A study and an open task.  In 2015 IEEE Workshop on Automatic Speech Recognition and Understanding, ASRU 2015, Scottsdale, AZ, USA, December 13-17, 2015. pages 813–820.  https://doi.org/10.1109/ASRU.2015.7404872.
  * Feng and Hirst (2012) Vanessa Wei Feng and Graeme Hirst. 2012.  Text-level Discourse Parsing with Rich Linguistic Features.  In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers - Volume 1. Association for Computational Linguistics, Stroudsburg, PA, USA, ACL ’12, pages 60–68.  http://www.aclweb.org/anthology/P12-1007.
  * Graff and Chen (2005) David Graff and Ke Chen. 2005.  Chinese Gigaword.  LDC Catalog No.: LDC2003T09, ISBN, 1:58563–58230.
  * Graves and Schmidhuber (2005) Alex Graves and Jürgen Schmidhuber. 2005.  Framewise phoneme classification with bidirectional LSTM and other neural network architectures.  Neural Networks 18(5-6):602–610.  https://doi.org/10.1016/j.neunet.2005.06.042.
  * Hermann et al. (2015) Karl Moritz Hermann, Tomas Kocisky, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. 2015.  Teaching machines to read and comprehend.  In Advances in Neural Information Processing Systems. pages 1693–1701.
  * Hickl (2008) Andrew Hickl. 2008.  Using Discourse Commitments to Recognize Textual Entailment.  In Proceedings of the 22nd International Conference on Computational Linguistics - Volume 1. Association for Computational Linguistics, Stroudsburg, PA, USA, COLING ’08, pages 337–344.  http://dl.acm.org/citation.cfm?id=1599081.1599124.
  * Hirao et al. (2013) Tsutomu Hirao, Yasuhisa Yoshida, Masaaki Nishino, Norihito Yasuda, and Masaaki Nagata. 2013.  Single-Document Summarization as a Tree Knapsack Problem.  In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, EMNLP 2013, 18-21 October 2013, Grand Hyatt Seattle, Seattle, Washington, USA, A meeting of SIGDAT, a Special Interest Group of the ACL. pages 1515–1520.  http://aclweb.org/anthology/D/D13/D13-1158.pdf.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long Short-Term Memory.  Neural Comput. 9(8):1735–1780.  https://doi.org/10.1162/neco.1997.9.8.1735.
  * Huang and Chen (2011) Hen-Hsen Huang and Hsin-Hsi Chen. 2011.  Chinese Discourse Relation Recognition.  In Proceedings of 5th International Joint Conference on Natural Language Processing. Asian Federation of Natural Language Processing, Chiang Mai, Thailand, pages 1442–1446.  http://www.aclweb.org/anthology/I11-1170.
  * Ji et al. (2016) Yangfeng Ji, Gholamreza Haffari, and Jacob Eisenstein. 2016.  A Latent Variable Recurrent Neural Network for Discourse-Driven Language Models.  In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Association for Computational Linguistics, San Diego, California, pages 332–342.  http://www.aclweb.org/anthology/N16-1037.
  * Jian et al. (2016) Ping Jian, Xiaohan She, Chenwei Zhang, Pengcheng Zhang, and Jian Feng. 2016.  Discourse Relation Sense Classification Systems for CoNLL-2016 Shared Task.  In Proceedings of the CoNLL-16 shared task. Association for Computational Linguistics, pages 158–163.  https://doi.org/10.18653/v1/K16-2022.
  * Kingma and Ba (2014) Diederik P. Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  CoRR abs/1412.6980.  http://arxiv.org/abs/1412.6980.
  * Lascarides and Asher (1993) Alex Lascarides and Nicholas Asher. 1993.  Temporal Interpretation, Discourse Relations and Commonsense entailment.  Linguistics and Philosophy 16(5):437–493.
  * LeCun et al. (2015) Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. 2015.  Deep learning.  Nature 521(7553):436–444.
  * Liu and Li (2016) Yang Liu and Sujian Li. 2016.  Recognizing Implicit Discourse Relations via Repeated Reading: Neural Networks with Multi-Level Attention.  In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016. pages 1224–1233.  http://aclweb.org/anthology/D/D16/D16-1130.pdf.
  * Mann and Thompson (1988) William C. Mann and Sandra A. Thompson. 1988.  Rhetorical structure theory: Toward a functional theory of text organization.  Text 8(3):243–281.
  * Mostafazadeh et al. (2016) Nasrin Mostafazadeh, Nathanael Chambers, Xiaodong He, Devi Parikh, Dhruv Batra, Lucy Vanderwende, Pushmeet Kohli, and James Allen. 2016.  A Corpus and Cloze Evaluation for Deeper Understanding of Commonsense Stories.  In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Association for Computational Linguistics, San Diego, California, pages 839–849.  http://www.aclweb.org/anthology/N16-1098.
  * Pitler et al. (2009) Emily Pitler, Annie Louis, and Ani Nenkova. 2009.  Automatic Sense Prediction for Implicit Discourse Relations in Text.  In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 2 - Volume 2. Association for Computational Linguistics, Stroudsburg, PA, USA, ACL 2009, pages 683–691.  http://www.aclweb.org/anthology/P/P09/P09-1077.pdf.
  * Prasad et al. (2008) Rashmi Prasad, Nikhil Dinesh, Alan Lee, Eleni Miltsakaki, Livio Robaldo, Aravind Joshi, and Bonnie Webber. 2008.  The Penn Discourse TreeBank 2.0.  In Proceedings, 6th International Conference on Language Resources and Evaluation. Marrakech, Morocco, pages 2961–2968.
  * Qin et al. (2016) Lianhui Qin, Zhisong Zhang, and Hai Zhao. 2016.  Shallow Discourse Parsing Using Convolutional Neural Network.  In Proceedings of the CoNLL-16 shared task. Association for Computational Linguistics, pages 70–77.  https://doi.org/10.18653/v1/K16-2010.
  * Rohde and Horton (2010) Hannah Rohde and William Horton. 2010.  Why or what next? Eye movements reveal expectations about discourse direction.  Talk at the 23rd Annual CUNY Conference on Human Sentence Processing. New York, NY.
  * Rutherford and Xue (2016) Attapol Rutherford and Nianwen Xue. 2016.  Robust Non-Explicit Neural Discourse Parser in English and Chinese.  In Proceedings of the CoNLL-16 shared task. Association for Computational Linguistics, pages 55–59.  https://doi.org/10.18653/v1/K16-2007.
  * Rutherford et al. (2016) Attapol T. Rutherford, Vera Demberg, and Nianwen Xue. 2016.  Neural Network Models for Implicit Discourse Relation Classification in English and Chinese without Surface Features.  CoRR abs/1606.01990.  http://arxiv.org/abs/1606.01990.
  * Schenk et al. (2016) Niko Schenk, Christian Chiarcos, Kathrin Donandt, Samuel Rönnqvist, Evgeny Stepanov, and Giuseppe Riccardi. 2016.  Do We Really Need All Those Rich Linguistic Features? A Neural Network-Based Approach to Implicit Sense Labeling.  In Proceedings of the CoNLL-16 shared task. Association for Computational Linguistics, pages 41–49.  https://doi.org/10.18653/v1/K16-2005.
  * Sun and Chai (2007) Mingyu Sun and Joyce Y Chai. 2007.  Discourse processing for context question answering based on linguistic knowledge.  Knowledge-Based Systems 20(6):511–526.
  * Trivedi and Eisenstein (2013) Rakshit S. Trivedi and Jacob Eisenstein. 2013.  Discourse connectors for latent subjectivity in sentiment analysis.  In Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings, June 9-14, 2013, Westin Peachtree Plaza Hotel, Atlanta, Georgia, USA. pages 808–813.  http://aclweb.org/anthology/N/N13/N13-1100.pdf.
  * Wang and Lan (2016) Jianxiang Wang and Man Lan. 2016.  Two End-to-end Shallow Discourse Parsers for English and Chinese in CoNLL-2016 Shared Task.  In Proceedings of the CoNLL-16 shared task. Association for Computational Linguistics, pages 33–40.  https://doi.org/10.18653/v1/K16-2004.
  * Webber (2004) Bonnie L. Webber. 2004.  D-LTAG: extending lexicalized TAG to discourse. Cognitive Science 28(5):751–779.  http://dblp.uni-trier.de/db/journals/cogsci/cogsci28.html.
  * Weiss and Bajec (2016) Gregor Weiss and Marko Bajec. 2016.  Discourse Sense Classification from Scratch using Focused RNNs.  In Proceedings of the CoNLL-16 shared task. Association for Computational Linguistics, pages 50–54.  https://doi.org/10.18653/v1/K16-2006.
  * Xue et al. (2016) Nianwen Xue, Hwee Tou Ng, Sameer Pradhan, Bonnie Webber, Attapol Rutherford, Chuan Wang, and Hongmin Wang. 2016.  The CoNLL-2016 Shared Task on Shallow Discourse Parsing.  In Proceedings of the Twentieth Conference on Computational Natural Language Learning - Shared Task. Association for Computational Linguistics, Berlin, Germany.
  * Zhang et al. (2015) Biao Zhang, Jinsong Su, Deyi Xiong, Yaojie Lu, Hong Duan, and Junfeng Yao. 2015\.  Shallow Convolutional Neural Network for Implicit Discourse Relation Recognition.  In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, EMNLP 2015, Lisbon, Portugal, September 17-21, 2015. pages 2230–2235.  http://aclweb.org/anthology/D/D15/D15-1266.pdf.
  * Zhou et al. (2016) Peng Zhou, Wei Shi, Jun Tian, Zhenyu Qi, Bingchen Li, Hongwei Hao, and Bo Xu. 2016\.  Attention-Based Bidirectional Long Short-Term Memory Networks for Relation Classification.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 2: Short Papers.  http://aclweb.org/anthology/P/P16/P16-2034.pdf.
  * Zhou and Xue (2012) Yuping Zhou and Nianwen Xue. 2012.  PDTB-style Discourse Annotation of Chinese Text.  In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, Jeju Island, Korea, pages 69–77.  http://www.aclweb.org/anthology-new/P/P12/P12-1008.bib.