The facets and the symmetries of the approval-voting polytope

DOI10.1016/J.JCTB.2004.04.001MaRDI QIDQ1880786zbMATH OpenOpenAlexFDO

Authors Jean-Paul Doignon, Samuel Fiorini

Publication date 1 October 2004

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2004.04.001

\(0/1\)-polytope automorphism group finite poset Johnson graph partial ordering

Combinatorics of partially ordered sets (06A07) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Symmetry properties of polytopes (52B15)

Review text

For a finite set \(S\) of cardinality \(n\geq 2\), let \(P(S)\) denote its power set. For any finite set \(I\), the vector space \(R^I\) has one coordinate per element of \(I\), and the coordinate corresponding to \(i\in I\) is denoted by \(x_i\). More generally, for each subset \(J\) of \(I\), \(x(J)\) is defined as the formal sum of the coordinates \(x_j\) in \(R^I\) with \(j\in J\). The characteristic vector of \(J\) is the vector \(v_J\) in \(R^I\) whose \(i\)th coordinate equals 1 for \(i\in J\), and 0 for \(i\not\in J\). With \(I=P (S)\), the approval-voting polytope is the convex hull of the characteristic vectors of all complete chains in \(P(S)\) (which are defined with the help of subsets of \(S\), partially ordered by inclusion). The authors prove that the facets of approval-voting polytopes correspond in a natural way to certain antichains in a power set (meaning that, in contrast to the above complete chains, for any pair of distinct subsets none is included in the other). They derive also further interesting results about these interesting \(0/1\)-polytopes.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: The facets and the symmetries of the approval-voting polytope

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