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.
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 problemCitations:
Zbl 1085.52005Online Encyclopedia of Integer Sequences:
Triangle of Eulerian numbers T(n,k) (n >= 1, 1 <= k <= n) read by rows.T(n, k) = Sum_{j=k..n} binomial(n, j)*E1(j, j-k), where E1 are the Eulerian numbers A173018. Triangle read by rows, T(n, k) for 0 <= k <= n.
Triangular array of Motzkin polynomial coefficients.
T(n,k) = binomial(n,2*k)*binomial(2*k,k) for 0 <= k <= n, triangle read by rows.
Triangle T(n,k) (n >= 1, 0 <= k <= floor((n-1)/2)) read by rows, where T(n,k) = (k+1)T(n-1,k) + (2n-4k)T(n-1,k-1).
