Convex hulls of orbits of representations of finite groups and combinatorial optimization (Q1263669)

The authors study the combinatorial structure of convex hulls of orbits in the representations of symmetric groups. It is shown that up to some exceptions, the convex hull of these orbits of a common point is an exponentially complicated polytope: its number of higher-dimensional faces grows not slower than \(2^ n\). The reason of study of such a problem goes back to the tasks of combinatorial optimization, and particularly, to the so called \(\pi\)-assignment problem (problem 1) and the problem of validity of assignment (problem 2). In view of the growth of the number of faces estimated, problem 1 is of \({\mathcal N}{\mathcal P}\)- hardness, and problem 2 is of \({\mathcal N}{\mathcal P}\)-completeness.