The bidirectional ballot polytope

MaRDI QIDQ5384297zbMATH OpenFDO

Authors Steven J. Miller, Carsten Peterson, Carsten Sprunger, Roger van Peski

Publication date 21 June 2019

Full work available at URL https://arxiv.org/abs/1708.02399, http://math.colgate.edu/~integers/s81/s81.pdf

zbMATH Keywords

bidirectional ballot polytopebidirectional ballot sequence

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Arithmetic combinatorics; higher degree uniformity (11B30)

Abstract: A bidirectional ballot sequence (BBS) is a finite binary sequence with the property that every prefix and suffix contains strictly more ones than zeros. BBS's were introduced by Zhao, and independently by Bosquet-M{'e}lou and Ponty as $(1,1)$-culminating paths. Both sets of authors noted the difficulty in counting these objects, and to date research on bidirectional ballot sequences has been concerned with asymptotics. We introduce a continuous analogue of bidirectional ballot sequences which we call bidirectional gerrymanders, and show that the set of bidirectional gerrymanders form a convex polytope sitting inside the unit cube, which we refer to as the bidirectional ballot polytope. We prove that every $(2n-1)$-dimensional unit cube can be partitioned into $2n-1$ isometric copies of the $(2n-1)$-dimensional bidirectional ballot polytope. Furthermore, we show that the vertices of this polytope are all also vertices of the cube, and that the vertices are in bijection with BBS's. An immediate corollary is a geometric explanation of the result of Zhao and of Bosquet-M{'e}lou and Ponty that the number of BBS's of length $n$ is $Theta(2^n/n)$.

Recommendations

• Analysis of bidirectional ballot sequences and random walks ending in their maximum
• \(q\)-generalization of a ballot problem
• Four Proofs of the Ballot Theorem
• scientific article; zbMATH DE number 4168687
• Two new bijections on lattice paths

Cites work

• A geometric perspective on the MSTD question
• Analysis of bidirectional ballot sequences and random walks ending in their maximum
• Constructing MSTD sets using bidirectional ballot sequences
• Culminating paths
• Integrable 2D Lorentzian gravity and random walks
• Many sets have more sums than differences
• Sets characterized by missing sums and differences
• When almost all sets are difference dominated

Cited in

(2)

• A geometric perspective on the MSTD question
• Analysis of bidirectional ballot sequences and random walks ending in their maximum

This page was built for publication: The bidirectional ballot polytope

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