The facets and the symmetries of the approval-voting polytope
type: Item
instance of: scholarly article
title: The facets and the symmetries of the approval-voting polytope
zbMATH Open document ID: 1060.52005
author: Jean-Paul Doignon
author: Samuel Fiorini
published in: Journal of Combinatorial Theory. Series B
publication date: 2004-10-01T00:00:00Z
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.
reviewed by: Horst Martini
Mathematics Subject Classification ID: 52B12
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 52B15
zbMATH DE Number: 2104545
zbMATH Keywords: finite poset
zbMATH Keywords: \(0/1\)-polytope
zbMATH Keywords: partial ordering
zbMATH Keywords: Johnson graph
zbMATH Keywords: automorphism group
MaRDI profile type: Publication
full work available at URL: j.jctb.2004.04.001
OpenAlex ID: W2036922239
cites work: Q4398864
cites work: Q3992965
cites work: On certain polytopes associated with graphs
cites work: Combinatorial optimization. Packing and covering
cites work: Q4949858
cites work: A decomposition theorem for partially ordered sets
cites work: An approval-voting polytope for linear orders
cites work: On the combinatorial structure of the approval-voting polytope
cites work: A random utility model for approval voting
cites work: Q5609153
cites work: Anti-blocking polyhedra
cites work: Q5685113
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Eine Eigenschaft der Atome endlicher Graphen
cites work: On the facial structure of set packing polyhedra
cites work: Q4871778
cites work: Q4004146
cites work: Connectivity of transitive graphs
cites work: Lectures on Polytopes
DOI: 10.1016/J.JCTB.2004.04.001
description: scientific article; zbMATH DE number 2104545