NSF PAR Search | NSF Public Access Repository

We prove that deciding the vanishing of the character of the symmetric group is C=P-complete. We use this hardness result to prove that the square of the character is not contained in #P, unless the polynomial hierarchy collapses to the second level. This rules out the existence of any (unsigned) combinatorial description for the square of the characters. As a byproduct of our proof we conclude that deciding positivity of the character is PP-complete under many-one reductions, and hence PH-hard under Turing-reductions.

Ian G. Macdonald: Works of Art; Hochschild Polytopes; Toric and Permutoric Promotion; Smirnov Words and the Delta Conjectures; The Poincaré-extended ab-Index; Colored Permutation Statistics by Conjugacy Class; Upho Lattices and Their Cores; Pattern Heights and The Minimal Power of q in a Kazhdan-Lusztig Polynomial; Rowmotion Markov Chains; Enumerating The Faces of Split Matroid Polytopes; From Higher Bruhat Orders to Steenrod Cup-i Coproducts; On The Size of Bruhat Intervals; Vines and MAT-Labeled Graphs; Configuration Spaces and Peak Representations; A determinantal Point Process Approach to Scaling and Local Limits of Random Young Tableaux; Generalized Heawood Graphs and Triangulations of Tori; The Somewhere-To-Below Shuffles in The Symmetric Group and Hecke Algebras; Dyck Combinatorics in p-Kazhdan-Lusztig Theory; A Framework Unifying Some Bijections for Graphs and Its Connection to Lawrence Polytopes; Shi Arrangements and Low Elements in Coxeter Groups; Universal Plücker Coordinates for the Wronski Map and Positivity in Real Schubert Calculus; Wilting Theory of Flow Polytopes; Character Factorisations, z-Asymmetric Partitions, and Plethysm; Inhomogeneous Particle Process Defined by Canonical Grothendieck Polynomials; Chow Rings of Matroids as Permutation Representations; Diagram Model for The Okada Algebra and Monoid; Stanley Chromatic Functions and a Conjecture in The Representation Theory of Unipotent Groups; Regular Schur Labeled Skew Shape Posets and Their 0-Hecke Modules; Acyclonestohedra; Determinant of The Distance Matrix of a Tree; Pop-Stack for Cambrian Lattices; The Characteristic Quasi-Polynomials for Exceptional Well-Generated Complex Reflection Groups; Macdonald Characters from a New Formula for Macdonald Polynomials; Antichains in The Representation Theory of Finite Lattices; On The Scaling of Random Tamari Intervals and Schnyder Woods of Random Triangulations (with an Asymptotic D-Finite Trick); Extended Schur Functions and Bases Related by Involutions; Supersolvable Posets and Fiber-Type Arrangements; Levi-Spherical Varieties and Demazure Characters; Non-Symmetric Cauchy Kernels, Demazure Measures, and LPP; Tamari Intervals and Blossoming Trees; Eulerian Polynomials for Digraphs; Framed Polytopes and Higher Categories; Poset Polytopes and Pipe Dreams: Toric Degenerations and Beyond; On The f-Vectors of Poset Associahedra; Rational Catalan Numbers for Complex Reflection Groups; Brewing Fubini-Bruhat Orders; From Geometry to Generating Functions: Rectangulations and Permutations; Growth Diagrams for Schubert RSK; A Signed e-Expansion of The Chromatic Symmetric Function and Some New e-Positive Graphs; All Kronecker Coefficients are Reduced Kronecker Coefficients; Quasipartition and Planar Quasipartition Algebras; Invariant Theory for The Face Algebra of The Braid Arrangement; The Newton Polytope of The Kronecker Product; 0-Whirling and Rowmotion Dynamics on The Chain of V's Poset; A Whitney Polynomial for Hypermaps; The Doubly Asymmetric Simple Exclusion Process, The Colored Boolean Process, and The Restricted Random Growth Model; From Coloured Permutations to Hadamard Products and Zeta Functions; Murnaghan-Type Representations of the Elliptic Hall Algebra; Plane Partitions and Rowmotion on Rectangular and Trapezoidal Posets; Projective Dimension of Weakly Chordal Graphic Arrangements; Realizing the s-Permutahedron via Flow Polytopes; Monomial Expansions for q-Whittaker and Modified Hall-Littlewood Polynomials; Extremal Weight Crystals over Affine Lie Algebras of Infinite Rank; Lascoux Polynomials and Gelfand-Zetlin Patterns; Chain Polynomials of Generalized Paving Matroids; A Galois Structure on The Orbit of Large Steps Walks in The Quadrant; Locally Invariant Vectors in Representations of Symmetric Groups; Excedance quotients, Quasisymmetric Varieties, and Temperley-Lieb algebras; Combinatorial Properties of Triangular Partitions; Asymptotics of Bounded Lecture-Hall Tableaux; Shuffle Theorems and Sandpiles; Real Matroid Schubert Varieties, Zonotopes, and Virtual Weyl Groups; Chromatic Functions, Interval Orders, and Increasing Forests; Crystals for Variations of Decomposition Tableaux; Triangular (q, t)-Schröder Polynomials and Khovanov-Rozansky Homology; qtRSK*: A Probabilistic Dual RSK Correspondence for Macdonald Polynomials; An Extended Generalization of RSK via The Combinatorics of Type A Quiver Representations; Pattern-Avoiding Polytopes and Cambrian Lattices; A Consistent Sandpile Torsor Algorithm for Regular Matroids; Asymptotics of Bivariate Algebraico-Logarithmic Generating Functions; Two-Row Set-Valued Tableaux: Catalan+k Combinatorics; Skein Relations for Punctured Surfaces; Charmed Roots and The Kroweras Complement; Fragmenting any Parallelepiped into a Signed Tiling; Ehrhart Polynomials, Hecke Series, and Affine Buildings; Cluster Algebras and Tilings for The m = 4 Amplituhedron; Quasisymmetric Expansion of Hall-Littlewood Symmetric Functions; Geometry of C-Matrices for Mutation-Infinite Quivers; Higher Specht Polynomials and Tableaux Bijections for Hessenberg Varieties; Charge Formulas for Macdonald Polynomials at t = 0 from Multiline Queues and Diagrams; Slit-Slide-Sew Bijections for Constellations and Quasiconstellations; Crystal Chute Moves on Pipe Dreams; A Regular Unimodular Triangulation of the Matroid Base Polytope; Analogues of Two Classical Pipedream Results on Bumpless Pipedreams; Asymptotic Log-Concavity of Dominant Lower Bruhat Intervals via Brunn-Minkowski Inequality; Combinatorics of Boundary Algebras; The Commutant of Divided Difference Operators, Klyachko's Genus, and the comaj Statistic; Jack Derangements; Framing Lattices and Flow Polytopes; On The Sum of The Entries in a Character Table; Vertex Models for The Product of a Schur and Demazure Polynomial; On The f-Vectors of Flow Polytopes for The Complete Graph; Counting Unicellular Maps under Cyclic Symmetries; Weak Bruhat Interval 0-Hecke Modules in Finite Type; The Monoid Representation of Upho Posets and Total Positivity; Shards for The Affine Symmetric Group; Kromatic Quasisymmetric Functions

Ram, Arun; Macdonald, Ian G; Pilaud, Vincent; Poliakova, Daria; Defant, Colin; Madhukara, Rachana; Thomas, Hugh; Iraci, Alessandro; Nadeau, Philippe; Vanden_Wyngaerd, Anna; et al (September 2024, Séminaire lotharingien de combinatoire)

Gaetz, Christian (Ed.)

Full Text Available

Search for: All records