Faces of generalized permutohedra

By Alexander Postnikov, Victor Reiner, Lauren K. Williams. Documenta Mathematica, 2006

374 citations recorded by the source corpus.

The aim of the paper is to calculate face numbers of simple generalized permutohedra, and study their f-, h- and γ- vectors. These polytopes include permutohedra, associahedra, graph- associahedra, simple graphic zonotopes, nestohedra, and other inter- esting polytopes. We give several explicit formulas for h-vectors and γ-vectors involv- ing descent statistics. This includes a combinatorial interpretation for γ-vectors of a large class of generalized permutohedra which are flag simple polytopes, and confirms for them Gal's conjecture on the nonnegativity of γ-vectors. We calculate explicit generating functions and formulae for h- polynomials of various families of graph-associahedra, including those corresponding to all Dynkin diagrams of finite and affine types. We also discuss relations with Narayana numbers and with Simon New- comb's problem. We give (and conjecture) upper and lower bounds for f-, h-, and γ-vectors within several classes of generalized permutohedra. An appendix discusses the equivalence of various notions of deforma- tions of simple polytopes.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/57e90dc1a26279b9418b0f4fcef34281549d2653

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

HOPF MONOIDS IN THE CATEGORY OF SPECIES (2012, background): “es. A set species P is ﬁnite if the set P[I] is ﬁnite for each ﬁnite set I. It is positive if P[∅] = ∅. The Cauchy product of set species P and Q is the set species P·Q deﬁned by (P ·Q)[I] := a I=S⊔T (55) P[S]×Q[T], where ×denotes the cartesian product of sets. The Cauchy product turns Spinto a mono”
Toric Topology (2012, methodology): “The resulting family of simple polytopes was called nestohedra in [190] because of its connection to nested sets considered by De Concini and Procesi [73] in the context of subspace arrangements.”
Unimodality, log-concavity, real-rootedness and beyond (2015, background): “real{rooted for all n;r2N. This conjecture remains open for all 3 rn 3, see [18]. More generally, if AS n, then the polynomial X ˇ2Sn S(ˇ)2A xdes(ˇ) is {nonnegative. Postnikov, Reiner and Williams [81] modied the Zn 2-action to prove Gal’s conjecture (see Conjecture 3.6) for so called chordal nestoh”
Algebraic and Geometric Methods in Enumerative Combinatorics (2014, background): “X e2E x e= r(E); X e2S x er(S) for EˆS: The facets are characterized in [FS05]. 14.(Generalized permutahedra) There are several interesting result on various classes of generalized permutahedra; see [PRW08]. 5.3 Counting faces The f-vector of a d-polytope Pis f P = (f 0;f 1;:::;f d 1;f d) where f i ”
Stellahedral geometry of matroids (2022, background): “We remark that the stellahedron Π 𝐸 is a realization of the graph associahedron of the star graph with the set of endpoints E ; see, for example, [PRW08, §10.4].”
On the cohomology and their torsion of real toric objects (2013, background): “There is an important subclass of the set of nestohedra, called graph associahedra (See [6], [13], or [14]).”
Scattering forms and the positive geometry of kinematics, color and the worldsheet (2017, background): “which belong in the much larger class of generalized permutohedra studied by Postnikov [51, 52].”
Hopf Monoids and Generalized Permutahedra (2017, background): “Figure 5 illustrates this informal description; for details on these points of view, see [62].”
Gamma-positivity in combinatorics and geometry (2017, background): “(Postnikov–Reiner–Williams [97]) For every connected, chordal building set B on the ground set [n]”