Determining the automorphism group of the linear ordering polytope. (English) Zbl 1006.20002
This paper studies the automorphism group of the linear ordering polytope on \(n\) elements. It is shown that this group is isomorphic to \(\mathbb{Z}_2\times\text{Sym}(n+1)\).
Reviewer: Sándor Fekete (Berlin)
MSC:
| 20B25 | Finite automorphism groups of algebraic, geometric, or combinatorial structures |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
| 52B12 | Special polytopes (linear programming, centrally symmetric, etc.) |
| 52B15 | Symmetry properties of polytopes |
Software:
LOLIBReferences:
| [1] | G. Bolotashvili, M. Kovalev, E. Girlich, New facets of the linear ordering polytope, SIAM J. Discrete Math. 12 (1999) 326-336.; G. Bolotashvili, M. Kovalev, E. Girlich, New facets of the linear ordering polytope, SIAM J. Discrete Math. 12 (1999) 326-336. · Zbl 0966.90085 |
| [2] | T. Christof, G. Reinelt, Low-dimensional linear ordering polytopes, Technical report, Institut für Angewandte Mathematik, Universität Heidelberg, 1997.; T. Christof, G. Reinelt, Low-dimensional linear ordering polytopes, Technical report, Institut für Angewandte Mathematik, Universität Heidelberg, 1997. |
| [3] | Doignon, J.-P.; Regenwetter, M., An approval-voting polytope for linear orders, J. Math. Psych., 41, 171-188 (1997) · Zbl 0892.90044 |
| [4] | J.-P. Doignon, M. Regenwetter, On the combinatorial structure of the approval-voting polytope, Department of Mathematics, Université Libre de Bruxelles, 1999, in preparation.; J.-P. Doignon, M. Regenwetter, On the combinatorial structure of the approval-voting polytope, Department of Mathematics, Université Libre de Bruxelles, 1999, in preparation. · Zbl 1027.91024 |
| [5] | S. Fiorini, On the partial order polytope, preprint, Department of Mathematics, Université Libre de Bruxelles, 1998.; S. Fiorini, On the partial order polytope, preprint, Department of Mathematics, Université Libre de Bruxelles, 1998. |
| [6] | Fraleigh, J. B., A First Course in Abstract Algebra (1994), Addison-Wesley: Addison-Wesley Reading |
| [7] | E. Girlich, M. Kovalev , V. Nalivaiko, A note on an extension of facet-defining digraphs, preprint 23/98, Faculty of Mathematics, Universität Magdeburg, 1998.; E. Girlich, M. Kovalev , V. Nalivaiko, A note on an extension of facet-defining digraphs, preprint 23/98, Faculty of Mathematics, Universität Magdeburg, 1998. |
| [8] | Goemans, M. X.; Hall, L. A., The strongest facets of the acyclic subgraph polytope are unknown, (Cunningham, W. H.; McCormick, S. T.; Queyranne, M., Integer Programming and Optimization. Integer Programming and Optimization, Lecture Notes in Computer Science 1084 (1996), Springer: Springer Berlin), 415-429 · Zbl 1415.90135 |
| [9] | Grötschel, M.; Jünger, M.; Reinelt, G., Acyclic subdigraph and linear orderings: polytopes, facets and a cutting plane algorithm, (Rival, I., Graphs and Order: The Role of Graphs in the Theory of Ordered Sets and Its Applications. Graphs and Order: The Role of Graphs in the Theory of Ordered Sets and Its Applications, NATO ASI Series C: Mathematical and Physical Sciences, Vol. 147 (1985), Reidel: Reidel Dordrecht), 217-264 · Zbl 0565.90044 |
| [10] | Koppen, M., Random utility representation of binary choice probabilities: Critical graphs yeilding critical necessary conditions, J. Math. Psych., 19, 21-39 (1995) · Zbl 0897.92045 |
| [11] | Leung, J.; Lee, J., More facets from fences for linear ordering and acyclic subgraph polytope, Discrete Appl. Math., 50, 185-200 (1994) · Zbl 0817.52017 |
| [12] | R. Müller, A.S. Schulz, The interval order polytope of a digraph, in: Integer Programming and Combinatorial Optimization, eds. E. Balas and J. Clausen, Lecture Notes in Computer Science 920, Springer, Berlin, 1995, pp. 50-64.; R. Müller, A.S. Schulz, The interval order polytope of a digraph, in: Integer Programming and Combinatorial Optimization, eds. E. Balas and J. Clausen, Lecture Notes in Computer Science 920, Springer, Berlin, 1995, pp. 50-64. · Zbl 1498.05117 |
| [13] | Reinelt, G., The Linear Ordering Problem: Algorithms and Applications, Number 8 in Research and exposition in mathematics (1985), Heldermann Verlag: Heldermann Verlag Berlin · Zbl 0565.68058 |
| [14] | Reinelt, G., A note on small linear-ordering polytopes, Discrete Comput. Geom., 10, 67-78 (1993) · Zbl 0784.90063 |
| [15] | Ziegler, G. M., Lectures on Polytopes (1995), Springer: Springer Berlin · 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.
