Faces of generalized permutohedra. (English) Zbl 1167.05005

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.


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


Zbl 1085.52005
Full Text: arXiv EuDML EMIS