Geometry, complexity, and combinatorics of permutation polytopes

DOI10.1016/0097-3165(93)90086-NzbMath0789.05095MaRDI QIDQ690026

Shmuel Onn

Publication date: 2 December 1993

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

zbMATH Keywords

partitionssymmetric groupstability numberoriented matroidpermutation matricesbistochastic matricestraveling salesman polytopecomputational complexitiesorbit polytopepermutation polytopeYoung polytopes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial identities, bijective combinatorics (05A19) Permutations, words, matrices (05A05) Combinatorial aspects of representation theory (05E10) Modular representations and characters (20C20) Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15) Stochastic matrices (15B51)

Related Items

A unified FFT-based approach to maximum assignment problems related to transitive finite group actions, Polytopes of roots of type A_N, Classification of affine symmetry groups of orbit polytopes, On permutation polytopes, Permutation polytopes and indecomposable elements in permutation groups, Determination of social laws for multi-agent mobilization, Inscribed Tverberg‐type partitions for orbit polytopes, Affine symmetries of orbit polytopes, An effective solution to convex 1-body \(N\)-representability, Exploiting symmetry in integer convex optimization using core points, \(k\)-neighborly faces of the Boolean quadric polytopes, Pattern-avoiding polytopes, Good Clusterings Have Large Volume, ORBITOPES, Faces of Birkhoff Polytopes, The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes, Linear-shaped partition problems, Two graph isomorphism polytopes, Permutohedra and minimal matrices, Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes, Hilbert series of group representations and Gröbner bases for generic modules

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hamiltonicity in (0-1)-polyhedra
• Convexity in oriented matroids
• On the diameter of convex polytopes
• Fiber polytopes
• Convex polyhedra of doubly stochastic matrices. II: Graph of Omega sub(n)
• The representation theory of the symmetric groups
• Convex hulls of orbits of representations of finite groups and combinatorial optimization
• The Hirsch conjecture is true for (0,1)-polytopes
• On the Assignment Polytope
• Results and problems in the theory of doubly-stochastic matrices
• The travelling salesman problem and a class of polyhedra of diameter two
• The adjacency relation on the traveling salesman polytope is NP-Complete
• An Inequality