Faces of generalized permutohedra. (English) Zbl 1167.05005

Postnikov, Alex; Reiner, Victor; Williams, Lauren

Doc. Math. 13, 207-273 (2008).

Authors’ abstract: The aim of the paper is to calculate face numbers of simple generalized permutohedra, and study their \(f\)-, \(h\)-, and \(\gamma\)-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 \(\gamma\)-vectors involving descent statistics. This includes a combinatorial interpretation for \(\gamma\)-vectors of a large class of generalized permutohedra which are flag simple polytopes, and confirms for them S. R. Gal’s conjecture [Discrete Comput. Geom. 34, No. 2, 269-284 (2005; Zbl 1085.52005)] on the nonnegativity of \(\gamma\)-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 Newcomb’s problem. (Newcomb’s problem is the problem of counting permutations of a multiset with a given number of descents.)
We give (and conjecture) upper and lower bounds for \(f\)-, \(h\)-, and \(\gamma\)-vectors within several classes of generalized permutohedra.
An appendix discusses the equivalence of various notions of deformations of simple polytopes.

Reviewer: Astrid Reifegerste (Magdeburg)

MSC:

05A15	Exact enumeration problems, generating functions
52B05	Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)

Keywords:

polytopes; face numbers; permutohedra; associahedra; graphic zonotopes; nestohedra; generating functions; Dynkin diagrams; Narayana numbers; Newcomb’s problem

Citations:

Zbl 1085.52005