Joseph Ben Geloun - Computational Complexity in Column Sums of Symmetric Group Character (...)

The character table of the symmetric group $S_n$, of permutations of n objects, is of fundamental interest in theoretical physics, combinatorics as well as computational complexity theory. We investigate the implications of an identity, which has a geometrical interpretation in combinatorial topological field theories, relating the column sum of normalised central characters of $S_n$, to a sum of structure constants of multiplication in the centre of the group algebra of $S_n$. The identity leads to the proof that a combinatorial computation of the column sum belongs to complexity class #P. The sum of structure constants has an interpretation in terms of the counting of branched covers of the sphere. This allows the identification of a tractable subset of the structure constants related to genus zero covers. We use this subset to prove that the column sum for a conjugacy class labelled by partition λ is non-vanishing if and only if the permutations in the conjugacy class are even. This leads to the result that the determination of the vanishing or otherwise of the column sum is in complexity class P. Joseph Ben Geloun (LIPN – Paris XIII) === Find this and many more scientific videos on https://www.carmin.tv/ - a French video platform for mathematics and their interactions with other sciences offering extra functionalities tailored to meet the needs of the research community. ===