Subdivisions of shellable complexes Hlavacek, Max; Solus, Liam
Journal of combinatorial theory. Series A,
02/2022, Volume:
186
Journal Article
Peer reviewed
Open access
In geometric, algebraic, and topological combinatorics, the unimodality of combinatorial generating polynomials is frequently studied. Unimodality follows when the polynomial is (real) stable, a ...property often deduced via the theory of interlacing polynomials. Many of the open questions on stability and unimodality of polynomials pertain to the enumeration of faces of cell complexes. In this paper, we relate the theory of interlacing polynomials to the shellability of cell complexes. We first derive a sufficient condition for stability of the h-polynomial of a subdivision of a shellable complex. To apply it, we generalize the notion of reciprocal domains for convex embeddings of polytopes to abstract polytopes and use this generalization to define the family of stable shellings of a polytopal complex. We characterize the stable shellings of cubical and simplicial complexes, and apply this theory to answer a question of Brenti and Welker on barycentric subdivisions for the well-known cubical polytopes. We also give a positive solution to a problem of Mohammadi and Welker on edgewise subdivisions of cell complexes. We end by relating the family of stable line shellings to the combinatorics of hyperplane arrangements. We pose related questions, answers to which would resolve some long-standing problems while strengthening ties between the theory of interlacing polynomials and the combinatorics of hyperplane arrangements.
This extended abstract is a summary of a recent paper which studies the enumeration of faces of subdivisions of cell complexes. Motivated by a conjecture of Brenti and Welker on the real-rootedness ...of the h-polynomial of the barycentric subdivision of the boundary complex of a convex polytope, we introduce a framework for proving real-rootedness of h-polynomials for subdivisions of polytopal complexes by relating interlacing polynomials to shellability via the existence of so-called stable shellings. We show that any shellable cubical, or simplicial, complex admitting a stable shelling has barycentric and edgewise subdivisions with real-rooted h-polynomials. Such shellings are shown to exist for well-studied families of cubical polytopes, giving a positive answer to the conjecture of Brenti and Welker in these cases. The framework of stable shellings is also applied to answer to a conjecture of Mohammadi and Welker on edgewise subdivisions in the case of shellable simplicial complexes.
The Ehrhart polynomial ehrP(n) of a lattice polytope P counts the number of integer points in the n-th dilate of P. The f∗-vector of P, introduced by Felix Breuer in 2012, is the vector of ...coefficients of ehrP(n) with respect to the binomial coefficient basis (Formula presented.), where d = dimP. Similarly to h/h∗-vectors, the f∗-vector of P coincides with the f-vector of its unimodular triangulations (if they exist). We present several inequalities that hold among the coefficients of f∗-vectors of polytopes. These inequalities resemble striking similarities with existing inequalities for the coefficients of f-vectors of simplicial polytopes; e.g., the first half of the f∗-coefficients increases and the last quarter decreases. Even though f∗-vectors of polytopes are not always unimodal, there are several families of polytopes that carry the unimodality property. We also show that for any polytope with a given Ehrhart h∗-vector, there is a polytope with the same h∗-vector whose f∗-vector is unimodal.
There is a well-known bijection between parking functions of a fixed length and maximal chains of the noncrossing partition lattice which we can use to associate to each set of parking functions a ...poset whose Hasse diagram is the union of the corresponding maximal chains. We introduce a decomposition of parking functions based on the largest number omitted and prove several theorems about the corresponding posets. In particular, they share properties with the noncrossing partition lattice such as local self-duality, a nice characterization of intervals, a readily computable Möbius function, and a symmetric chain decomposition. We also explore connections with order complexes, labeled Dyck paths, and rooted forests.
Signed Poset Polytopes Beck, Matthias; Hlavacek, Max
arXiv.org,
11/2023
Paper, Journal Article
Open access
Stanley introduced in 1986 the order polytope and the chain polytope for a given finite poset. These polytopes contain much information about the poset and have given rise to important examples in ...polyhedral geometry. In 1993, Reiner introduced signed posets as natural type-B analogues of posets. We define and study signed order and chain polytopes. Our results include convex-hull and halfspace descriptions, unimodular triangulations, Ehrhart \(h^*\)-polynomials and their relations to signed permutation statistics, and a Gorenstein characterization of signed order and chain polytopes.
Given a recurrence sequence
H
, with
H
n
=
c
1
H
n
-
1
+
⋯
+
c
t
H
n
-
t
where
c
i
∈
N
0
for all
i
and
c
1
,
c
t
≥
1
, the generalized Zeckendorf decomposition (gzd) of
m
∈
N
0
is the unique ...representation of
m
using
H
composed of blocks lexicographically less than
σ
=
(
c
1
,
⋯
,
c
t
)
. We prove that the gzd of
m
uses the fewest number of summands among all representations of
m
using
H
, for all
m
, if and only if
σ
is weakly decreasing. We develop an algorithm for moving from any representation of
m
to the gzd, the analysis of which proves that
σ
weakly decreasing implies summand minimality. We prove that the gzds of numbers of the form
v
0
H
n
+
⋯
+
v
ℓ
H
n
-
ℓ
converge in a suitable sense as
n
→
∞
; furthermore we classify three distinct behaviors for this convergence. We use this result, together with the irreducibility of certain families of polynomials, to exhibit a representation with fewer summands than the gzd if
σ
is not weakly decreasing.
In geometric, algebraic, and topological combinatorics, the unimodality of combinatorial generating polynomials is frequently studied. Unimodality follows when the polynomial is (real) stable, a ...property often deduced via the theory of interlacing polynomials. Many of the open questions on stability and unimodality of polynomials pertain to the enumeration of faces of cell complexes. In this paper, we relate the theory of interlacing polynomials to the shellability of cell complexes. We first derive a sufficient condition for stability of the \(h\)-polynomial of a subdivision of a shellable complex. To apply it, we generalize the notion of reciprocal domains for convex embeddings of polytopes to abstract polytopes and use this generalization to define the family of stable shellings of a polytopal complex. We characterize the stable shellings of cubical and simplicial complexes, and apply this theory to answer a question of Brenti and Welker on barycentric subdivisions for the well-known cubical polytopes. We also give a positive solution to a problem of Mohammadi and Welker on edgewise subdivisions of cell complexes. We end by relating the family of stable line shellings to the combinatorics of hyperplane arrangements. We pose related questions, answers to which would resolve some long-standing problems while strengthening ties between the theory of interlacing polynomials and the combinatorics of hyperplane arrangements.
The Ehrhart polynomial $\text{ehr}_P(n)$ of a lattice polytope $P$ counts the
number of integer points in the $n$-th integral dilate of $P$. The $f^*$-vector
of $P$, introduced by Felix Breuer in ...2012, is the vector of coefficients of
$\text{ehr}_P(n)$ with respect to the binomial coefficient basis $
\left\{\binom{n-1}{0},\binom{n-1}{1},...,\binom{n-1}{d}\right\}$, where $d =
\dim P$. Similarly to $h/h^*$-vectors, the $f^*$-vector of $P$ coincides with
the $f$-vector of its unimodular triangulations (if they exist). We present
several inequalities that hold among the coefficients of $f^*$-vectors of
polytopes. These inequalities resemble striking similarities with existing
inequalities for the coefficients of $f$-vectors of simplicial polytopes; e.g.,
the first half of the $f^*$-coefficients increases and the last quarter
decreases. Even though $f^*$-vectors of polytopes are not always unimodal,
there are several families of polytopes that carry the unimodality property. We
also show that for any polytope with a given Ehrhart $h^*$-vector, there is a
polytope with the same $h^*$-vector whose $f^*$-vector is unimodal.
The Ehrhart polynomial \(\text{ehr}_P(n)\) of a lattice polytope \(P\) counts the number of integer points in the \(n\)-th integral dilate of \(P\). The \(f^*\)-vector of \(P\), introduced by Felix ...Breuer in 2012, is the vector of coefficients of \(\text{ehr}_P(n)\) with respect to the binomial coefficient basis \( \left\{\binom{n-1}{0},\binom{n-1}{1},...,\binom{n-1}{d}\right\}\), where \(d = \dim P\). Similarly to \(h/h^*\)-vectors, the \(f^*\)-vector of \(P\) coincides with the \(f\)-vector of its unimodular triangulations (if they exist). We present several inequalities that hold among the coefficients of \(f^*\)-vectors of polytopes. These inequalities resemble striking similarities with existing inequalities for the coefficients of \(f\)-vectors of simplicial polytopes; e.g., the first half of the \(f^*\)-coefficients increases and the last quarter decreases. Even though \(f^*\)-vectors of polytopes are not always unimodal, there are several families of polytopes that carry the unimodality property. We also show that for any polytope with a given Ehrhart \(h^*\)-vector, there is a polytope with the same \(h^*\)-vector whose \(f^*\)-vector is unimodal.