Abstract
With respect to a fixedn-element ordered setP, thegeneralized permutahedron Perm(P) is the set of all ordered setsP ∩L, whereL is any permutation of the elements of the underlyingn-element set. Considered as a subset of the extension lattice of ann-element set,Perm(P) is cover-preserving. We apply this to deduce, for instance, that, in any finite ordered setP, there is a comparability whose removal will not increase the dimension, and there is a comparability whose addition toP will not increase its dimension.
We establish further properties about the extension lattice which seem to be of independent interest, leading for example, to the characterization of those ordered setsP for which this generalized permutahedron is itself a lattice.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Avann, S. P.,The lattice of natural partial orders, Aequationes Math.8 (1972), 95–102.
Björner, A.,Orderings of Coxeter groups, Amer. Math. Soc. Contemp. Math.34 (1984), 175–195.
Brualdi, R. A. andJung, H. C.,On the poset of all posets on n elements, 1991, preprint.
Dean, R. A. andKeller, G.,Natural partial orders, Canad. J. Math.20 (1968), 535–554.
Dushnik, B. andMiller, E. W.,Partially ordered sets, Amer. J. Math.63 (1941), 600–610.
Eades, P., Hickey, M. andRead, R. C.,Some Hamilton paths and a minimal change algorithm, J. Assoc. Comp. Mach.31 (1984), 19–29.
Guilbaud, G. T. andRosenstiehl, P.,Analyse algébrique d'un scrutin, Math. et Science Humaines4 (1963), 9–33. [Reprinted in B. Monjardet,Treillis d'ordre, inOrdres Totaux Finis, Gauthier-Villars, Paris, 1971, pp. 29–45.
Kelly, D.,Removable pairs in dimension theory, inUnsolved Problems, Order1 (1984), 217–218.
Kelly, D. andTrotter, W. T.,Dimension theory for ordered sets, inOrdered Sets (I. Rival, ed.), Reidel, 1982, pp. 171–211.
Pouzet, M. andRival, I.,Structural arithmetic of the extension lattice of an order, Technical Report TR-91-11, University of Ottawa.
Pruesse, G. andRuskey, F.,Generating the linear extensions of certain posets by transpositions, SIAM J. Discrete Math.4 (1991), 413–422.
Ruskey, F.,Adjacent interchange generation of combinations, J. Algorithms4 (1988), 162–180.
Ruskey, F.,Research problem 90, Discrete Math.70 (1988), 111–112.
Ruskey, F.,Transposition generation of alternating permutations, Order6 (1989), 227–233.
Author information
Authors and Affiliations
Additional information
Dedicated to the memory of Alan Day
Supported in part by PRC Mathématiques-Informatique (France) and NSERC (Canada).
Supported in part by DFG (Germany) and NSERC (Canada).
Supported in part by NSERC (Canada).
Rights and permissions
About this article
Cite this article
Pouzet, M., Reuter, K., Rival, I. et al. A generalized permutahedron. Algebra Universalis 34, 496–509 (1995). https://doi.org/10.1007/BF01181874
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01181874