The f-vector of the descent polytope

DOI10.1007/S00454-010-9316-6zbMATH Open1227.52005arXiv0812.1249OpenAlexW3100536503MaRDI QIDQ633209FDOQ633209

Authors: Denis Chebikin, Richard Ehrenborg 

Publication date: 31 March 2011

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: For a positive integer n and a subset S of [n-1], the descent polytope DP_S is the set of points x_1, ..., x_n in the n-dimensional unit cube [0,1]^n such that x_i >= x_{i+1} for i in S and x_i <= x_{i+1} otherwise. First, we express the f-vector of DP_S as a sum over all subsets of [n-1]. Second, we use certain factorizations of the associated word over a two-letter alphabet to describe the f-vector. We show that the f-vector is maximized when the set S is the alternating set {1,3,5, ...}. We derive a generating function for the f-polynomial F_S(t) of DP_S, written as a formal power series in two non-commuting variables with coefficients in Z[t]. We also obtain the generating function for the Ehrhart polynomials of the descent polytopes.

Full work available at URL: https://arxiv.org/abs/0812.1249

Recommendations

• The boustrophedon transform for descent polytopes
• Cyclotomic factors of the descent set polynomial
• Bijective proofs for some results on the descent polytope
• Ehrhart \(h^{\ast }\)-vectors of hypersimplices
• Descent polynomials

zbMATH Keywords

alternating setEhrhart polynomialdescent set statisticsmaximizing inequalitiesnon-commutative rational generating function

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Cites Work

• Two poset polytopes
• Title not available (Why is that?)
• Variations on descents and inversions in permutations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Permutations ayant une forme donnée
• A spectral approach to consecutive pattern-avoiding permutations
• The On-Line Encyclopedia of Integer Sequences
• Extremal problems for the Möbius function in the face lattice of the \(n\)-octahedron
• Maximizing the descent statistic
• Maximizing Möbius functions on subsets of Boolean algebras
• A probabilistic approach to the descent statistic

Cited In (5)

• Bijective proofs for some results on the descent polytope
• Random doubly stochastic tridiagonal matrices
• The Ehrhart and face polynomials of the graph polytope of a cycle
• The boustrophedon transform for descent polytopes
• \(f\)-vectors of polyhedra

Uses Software

• OEIS

This page was built for publication: The \(f\)-vector of the descent polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633209)