Atlantic Graph Theory Seminar

Speaker: Andrew Beveridge, Macalester College

Title: Approval Ballot Triangles

Time: Wednesday, February 14, 3.30pm Atlantic time

Bertrand’s Ballot Problem enumerates the number of ways to count ballots so that candidate 1 never trails candidate 2. We generalize this problem by considering an approval ballot election between $n$ candidates. In an approval ballot election, each voter endorses a subset of candidates, rather than voting for just one person. The general approval ballot problem becomes: how many ways can the ballots be counted so that candidate $k$ never trails candidate $k+1$? This formulation yields a family of binary triangular arrays, called approval ballot triangles (ABTs), that are in bijection with totally symmetric self-complementary plane partitions. We show that ABTs unify three different TSSCPP families of triangular arrays. We then further the connection between TSSCPPs and ballot problems by giving a decomposition of a strict-sense ballot into a list of sequentially compatible ABTs