The facets and the symmetries of the approval-voting polytope (Q1880786): Difference between revisions

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.