Faces of generalized permutohedra

Alex Postnikov, Victor Reiner, Lauren Williams

Research output: Contribution to journalArticle

107 Scopus citations

Abstract

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 interesting polytopes. We give several explicit formulas for h-vectors and γ-vectors involving 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 deformations of simple polytopes.

Original languageEnglish (US)
Pages (from-to)207-273
Number of pages67
JournalDocumenta Mathematica
Volume13
StatePublished - Dec 1 2008

Keywords

  • Face numbers
  • Permutohedra
  • Polytopes

Fingerprint Dive into the research topics of 'Faces of generalized permutohedra'. Together they form a unique fingerprint.

  • Cite this

    Postnikov, A., Reiner, V., & Williams, L. (2008). Faces of generalized permutohedra. Documenta Mathematica, 13, 207-273.