The boustrophedon transform for descent polytopes

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

Review text

For a word \(\mathbf{v} = \mathbf{v}_1\mathbf{v}_2\cdots\mathbf{v}_{n-1}\) of length \(n-1\) in the letters \(\mathbf{x}\) and \(\mathbf{y}\) the descent polytope \(\mathrm{DP}_{\mathbf{v}}\) is defined by \[ \mathrm{DP}_{\mathbf{v}} = \{ (x_1,\ldots,x_n)\in [0,1]^n : x_i\leq x_{i+1}\text{ if } {\mathbf{v}_i} = {\mathbf{x}}\text{ and }x_i\geq x_{i+1}\text{ if } {\mathbf{v}_i} = {\mathbf{y}} \}. \] In [\textit{D. Chebikin} and the first author, Discrete Comput. Geom. 45, No. 3, 410--424 (2011; Zbl 1227.52005), Corollary 2.5], it was shown that the number of \(i\)-dimensional faces of \(\mathrm{DP}_{\mathbf{v}}\) is maximized for the alternating word \(\mathbf{v}\). This paper provides an alternative way to compute the \(f\)-vector of \(\mathrm{DP}_{\mathbf{v}}\) by using a method reminiscent of the boustrophedon transform \(\mathbb{N}^n \rightarrow {\mathbb{N}}^{n+1}\) defined by \((p_1,p_2,\ldots,p_n)\mapsto (0,p_1,p_1+p_2,\ldots,p_1+\cdots+p_n)\) and \((p_1,p_2,\ldots,p_n)\mapsto (p_1+\cdots+p_n,p_2+\cdots+p_n,\ldots,p_n,0)\), from which one can immediately obtain the result from Chebikin and the first author [loc. cit.], that the \(f\)-vector of \(\mathrm{DP}_{\mathbf{v}}\) is componentwise maximized for the alternating word \(\mathbf{v}\).

Recommendations

Cites work

Cited in

(4)

This page was built for publication: The boustrophedon transform for descent polytopes

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