The Polytope of m-Subspaces of a Finite Affine Space

Julie Christophe; Jean-Paul Doignon

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 3, page 317-344
  • ISSN: 0399-0559

Abstract

top
The m-subspace polytope is defined as the convex hull of the characteristic vectors of all m-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 m-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 m-subspace polytope is completely described and the adjacency of vertices is fully characterized.

How to cite

top

Christophe, Julie, and Doignon, Jean-Paul. "The Polytope of m-Subspaces of a Finite Affine Space." RAIRO - Operations Research 41.3 (2007): 317-344. <http://eudml.org/doc/250126>.

@article{Christophe2007,
abstract = { The m-subspace polytope is defined as the convex hull of the characteristic vectors of all m-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 m-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 m-subspace polytope is completely described and the adjacency of vertices is fully characterized. },
author = {Christophe, Julie, Doignon, Jean-Paul},
journal = {RAIRO - Operations Research},
keywords = {Convex polytope; finite affine space; m-subspace polytope; convex polytope; -subspace polytope},
language = {eng},
month = {8},
number = {3},
pages = {317-344},
publisher = {EDP Sciences},
title = {The Polytope of m-Subspaces of a Finite Affine Space},
url = {http://eudml.org/doc/250126},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Christophe, Julie
AU - Doignon, Jean-Paul
TI - The Polytope of m-Subspaces of a Finite Affine Space
JO - RAIRO - Operations Research
DA - 2007/8//
PB - EDP Sciences
VL - 41
IS - 3
SP - 317
EP - 344
AB - The m-subspace polytope is defined as the convex hull of the characteristic vectors of all m-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 m-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 m-subspace polytope is completely described and the adjacency of vertices is fully characterized.
LA - eng
KW - Convex polytope; finite affine space; m-subspace polytope; convex polytope; -subspace polytope
UR - http://eudml.org/doc/250126
ER -

References

top
  1. O. Anglada, 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. O. Anglada and J.F. Maurras, Enveloppe convexe des hyperplans d'un espace affine fini. RAIRO Oper. Res.37 (2003) 213–219.  
  3. E. Artin, Geometric Algebra. Wiley Classics Library. John Wiley & Sons Inc., New York (1988).  
  4. A. Beutelspacher and U. Rosenbaum, Projective Geometry: from foundations to applications. Cambridge University Press, Cambridge (1998).  
  5. G. Bolotashvili, M. Kovalev, and E. Girlich, New facets of the linear ordering polytope. SIAM J. Discrete Math.12 (1999) 326–336.  
  6. A. Brøndsted, An Introduction to Convex Polytopes. Graduate Texts in Mathematics, vol. 90. Springer-Verlag, New York (1983).  
  7. T. Christof, PORTA – a POlyhedron Representation Transformation Algorithm. version 1.3.2 (1999), written by T. Christof, maintained by A. Loebel and M. Stoer, available at .  URIhttp://www.informatik.uni-heidelberg.de/groups/comopt/software/PORTA/
  8. J. Christophe, 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. J. Christophe, J.-P. Doignon and S. Fiorini, The biorder polytope. Order21 (2004) 61–82.  
  10. J.-P Doignon and M. Regenwetter, An approval-voting polytope for linear orders. J. Math. Psych.41 (1997) 171–188.  
  11. E. Gawrilow and M. Joswig, POLYMAKE: a software package for analyzing convex polytopes. Version 1.4 (Dec. 2000), available at url http://www.math-tu-berlin.de/diskregeom/polymake/.  
  12. B. Grünbaum, Convex Polytopes, Graduate Texts in Mathematics, vol. 221. Springer-Verlag, New York, second edition (2003).  
  13. J.F. Maurras, The line-polytope of a finite affine plane. Discrete Math.115 (1993) 283–286.  
  14. J.H. van Lint and R.M. Wilson, A Course in Combinatorics. Cambridge University Press, Cambridge, UK (1992).  
  15. G.M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152. Springer-Verlag (1995).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.