The -subspace polytope is defined as the convex hull of the characteristic vectors of all -dimensional subspaces of a finite affine space. The particular case of the hyperplane polytope has been investigated by Maurras (1993) and Anglada and Maurras (2003), who gave a complete characterization of the facets. The general -subspace polytope that we consider shows a much more involved structure, notably as regards facets. Nevertheless, several families of facets are established here. Then the group of automorphisms of the -subspace polytope is completely described and the adjacency of vertices is fully characterized.
Mots-clés : convex polytope, finite affine space, $m$-subspace polytope
@article{RO_2007__41_3_317_0,
author = {Christophe, Julie and Doignon, Jean-Paul},
title = {The polytope of $m$-subspaces of a finite affine space},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {317--344},
publisher = {EDP-Sciences},
volume = {41},
number = {3},
year = {2007},
doi = {10.1051/ro:2007026},
mrnumber = {2348086},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2007026/}
}
TY - JOUR AU - Christophe, Julie AU - Doignon, Jean-Paul TI - The polytope of $m$-subspaces of a finite affine space JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2007 SP - 317 EP - 344 VL - 41 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2007026/ DO - 10.1051/ro:2007026 LA - en ID - RO_2007__41_3_317_0 ER -
%0 Journal Article %A Christophe, Julie %A Doignon, Jean-Paul %T The polytope of $m$-subspaces of a finite affine space %J RAIRO - Operations Research - Recherche Opérationnelle %D 2007 %P 317-344 %V 41 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2007026/ %R 10.1051/ro:2007026 %G en %F RO_2007__41_3_317_0
Christophe, Julie; Doignon, Jean-Paul. The polytope of $m$-subspaces of a finite affine space. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 317-344. doi : 10.1051/ro:2007026. http://www.numdam.org/articles/10.1051/ro:2007026/
[1] , Quelques polyèdres combinatoires bien décrits. Ph.D. thesis, Université de la Méditerranée Aix-Marseille II, Faculté des Sciences de Luminy (2004).
[2] and, Enveloppe convexe des hyperplans d'un espace affine fini. RAIRO Oper. Res. 37 (2003) 213-219. | Numdam | Zbl
[3] , Geometric Algebra. Wiley Classics Library. John Wiley & Sons Inc., New York (1988). | MR | Zbl
[4] and, Projective Geometry: from foundations to applications. Cambridge University Press, Cambridge (1998). | MR | Zbl
[5] ,, and, New facets of the linear ordering polytope. SIAM J. Discrete Math. 12 (1999) 326-336. | Zbl
[6] , An Introduction to Convex Polytopes. Graduate Texts in Mathematics, vol. 90. Springer-Verlag, New York (1983). | MR | Zbl
[7] , PORTA - a POlyhedron Representation Transformation Algorithm. version 1.3.2 (1999), written by T. Christof, maintained by A. Loebel and M. Stoer, available at http://www.informatik.uni-heidelberg.de/groups/comopt/software/PORTA/.
[8] , Le polytope des sous-espaces d'un espace affin fini. Ph.D. thesis, Université Libre de Bruxelles, 2006. Accessible on line at http://theses.ulb.ac.be:8000/ETD-db/collection/available/ULBetd-01222007-165129/ro.html
[9] , and, The biorder polytope. Order 21 (2004) 61-82. | Zbl
[10] and, An approval-voting polytope for linear orders. J. Math. Psych. 41 (1997) 171-188. | MR | Zbl
[11] and, POLYMAKE: a software package for analyzing convex polytopes. Version 1.4 (Dec. 2000), available at url http://www.math-tu-berlin.de/diskregeom/polymake/. | Zbl
[12] , Convex Polytopes, Graduate Texts in Mathematics, vol. 221. Springer-Verlag, New York, second edition (2003). | MR | Zbl
[13] , The line-polytope of a finite affine plane. Discrete Math. 115 (1993) 283-286. | MR | Zbl
[14] and, A Course in Combinatorics. Cambridge University Press, Cambridge, UK (1992). | MR | Zbl
[15] , Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152. Springer-Verlag (1995). | MR | Zbl
Cité par Sources :
