×

Convex hulls of orbits of representations of finite groups and combinatorial optimization. (English. Russian original) Zbl 0688.20006

Funct. Anal. Appl. 22, No. 3, 224-225 (1988); translation from Funkts. Anal. Prilozh. 22, No. 3, 66-67 (1988).
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.
Reviewer: E.Kryachko

MSC:

20C30 Representations of finite symmetric groups
90C27 Combinatorial optimization
52Bxx Polytopes and polyhedra
20B35 Subgroups of symmetric groups
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs (1982). · Zbl 0503.90060
[2] L. Lovasz, An Algorithmic Theory of Numbers, Graphs and Convexity, SIAM, Philadelphia (1986).
[3] G. D. James, The Representation Theory of the Symmetric Group, Springer-Verlag, Berlin (1978). · Zbl 0393.20009
[4] V. V. Emelichev, M. M. Kovalev, and M. K. Kravtsov, Polytopes, Graphs, and Optimization, Cambridge Univ. Press (1984). · Zbl 0523.52002
[5] M. B. Gromova, The Analysis of Operations and Statistical Modeling, Leningrad State Univ. (1974), pp. 3-15.
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.