×

The polytope of \(m\)-subspaces of a finite affine space. (English) Zbl 1213.52012

Summary: 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 J. F. Maurras [Discrete Math. 115, No. 1–3, 283–286 (1993; Zbl 0774.51001)] and O. Anglada and J. F. Maurras [RAIRO, Oper. Res. 37, No. 4, 213–219 (2003; Zbl 1096.52001)], 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.

MSC:

52B12 Special polytopes (linear programming, centrally symmetric, etc.)
51A30 Desarguesian and Pappian geometries
90C27 Combinatorial optimization

Software:

PORTA; polymake
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[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. · Zbl 1096.52001 · doi:10.1051/ro:2004007
[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). · Zbl 0893.51001
[5] G. Bolotashvili, M. Kovalev, and E. Girlich, New facets of the linear ordering polytope. SIAM J. Discrete Math.12 (1999) 326-336. Zbl0966.90085 · Zbl 0966.90085 · doi:10.1137/S0895480196300145
[6] A. Brøndsted, An Introduction to Convex Polytopes. Graduate Texts in Mathematics, vol. 90. Springer-Verlag, New York (1983). Zbl0509.52001 · Zbl 0509.52001
[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. · Zbl 1072.52009 · doi:10.1007/s11083-004-5129-7
[10] J.-P Doignon and M. Regenwetter, An approval-voting polytope for linear orders. J. Math. Psych.41 (1997) 171-188. Zbl0892.90044 · Zbl 0892.90044 · doi:10.1006/jmps.1997.1155
[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/. · Zbl 0960.68182
[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. Zbl0774.51001 · Zbl 0774.51001 · doi:10.1016/0012-365X(93)90498-I
[14] J.H. van Lint and R.M. Wilson, A Course in Combinatorics. Cambridge University Press, Cambridge, UK (1992). Zbl0769.05001 · Zbl 0769.05001
[15] G.M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152. Springer-Verlag (1995). · Zbl 0823.52002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.