The f-Vector of the Descent Polytope

Denis Chebikin, Richard Ehrenborg

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


For a positive integer n and a subset S⊆[n-1], the descent polytope DP S is the set of points (x1,...,xn) in the n-dimensional unit cube [0,1]n such that xi≥xi+1 if i∈S and xi≤xi+1 otherwise. First, we express the f-vector 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,...}∩[n-1]. We derive a generating function for FS(t), written as a formal power series in two non-commuting variables with coefficients in ℤ[t]. We also obtain the generating function for the Ehrhart polynomials of the descent polytopes.

Original languageEnglish
Pages (from-to)410-424
Number of pages15
JournalDiscrete and Computational Geometry
Issue number3
StatePublished - Apr 2011


  • Alternating set
  • Descent set statistics
  • Ehrhart polynomial
  • Maximizing inequalities
  • Non-commutative rational generating function

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'The f-Vector of the Descent Polytope'. Together they form a unique fingerprint.

Cite this