In the late 1930's Murnaghan discovered the existence of a stabilization phenomenon for the Kronecker product of Schur functions. For n sufficiently large, the values of the Kronecker coefficients appearing in the product of two Schur functions of degree n do not depend on the first part of the indexing partitions, but only on the values of their remaining parts. We compute the exact value of n for which all the coefficients of a Kronecker product of Schur functions stabilize. We also compute two new bounds for the stabilization of a sequence of coefficients and show that they improve existing bounds of M. Brion and E. Vallejo.
We show that the Kronecker coefficients (the Clebsch-Gordan coefficients of the symmetric group) indexed by two two-row shapes are given by quadratic quasipolynomial formulas whose domains are the maximal cells of a fan. Simple calculations provide explicitly the quasipolynomial formulas and a description of the associated fan. These new formulas are obtained from analogous formulas for the corresponding reduced Kronecker coefficients and a formula recovering the Kronecker coefficients from the reduced Kronecker coefficients. As an application, we characterize all the Kronecker coefficients indexed by two two-row shapes that are equal to zero. This allowed us to disprove a conjecture of Mulmuley about the behavior of the stretching functions attached to the Kronecker coefficients.
We provide counter-examples to Mulmuley's strong saturation conjecture (strong SH) for the Kronecker coefficients. This conjecture was proposed in the setting of Geometric Complexity Theory to show that deciding whether or not a Kronecker coefficient is zero can be done in polynomial time. We also provide a short proof of the #P-hardness of computing the Kronecker coefficients. Both results rely on the connections between the Kronecker coefficients and another family of structural constants in the representation theory of the symmetric groups: Murnaghan's reduced Kronecker coefficients.
An appendix by Mulmuley introduces a relaxed form of the saturation hypothesis SH, still strong enough for the aims of Geometric Complexity Theory.
The volume function introduced by P. Milne to count the real roots of a system of polynomial equations in a box is a vector symmetric polynomial. Its expansion in the basis of monomial functions is provided. Only monomial functions of a particular kind appear in this expansion ("squarefree monomial functions"). By means of an appropriate specialization of the vector symmetric Newton identities, we derive an inductive formula to decompose the squarefree monomial functions in power sums. This formula is related to the lattice of the sub-hypergraphs of an hypergraph. As a corollary, an inductive formula to express the components of Milne's volume function in the power sums is obtained.
Tanisaki introduced generating sets for the defining ideals of the schematic intersections of the closure of conjugacy classes of nilpotent matrices with the set of diagonal matrices. These ideals are naturally labeled by integer partitions. Given such a partition $\lambda$, we define several methods to produce a reduced generating set for the associated ideal $I_{\lambda}$. For particular shapes we find nice generating sets. By comparing our sets with some generating sets of $I_{\lambda}$ arising from a work of Weyman, we find a counterexample to a related conjecture of Weyman.
Using the a noncommutative version of Chevalley's theorem due to Bergeron, Reutenauer, Rosas, and Zabrocki we compute the graded Frobenius series for their two sets of noncommutative harmonics with respect to the left action of the symmetric group (acting on variables). We use these results to derive the Frobenius series for the enveloping algebra of the derived free Lie algebra in n variables.
We study the Hopf algebra structure for the symmetric functions in noncommutative variables studied in Symmetric functions in noncommuting variables, and show how they are related to other well studied hopf algebras like the algebra of symmetric functions and the algebra of noncommutative symmetric functions of Gelfand, Krob, Lascoux, Leclerc, Retakh, and Thibon. We also find analogs of Chevalley's theorem stating that the ring of polynomials in noncommutative variables is isomorphic to the tensor product of its invariants times its coinvariants.
An extended abstract based on this results appeared at Proc. EACA'06, Universidad de Sevilla. España, (2006).
We study a family of ideals that were first introduced by De Concini and Procesi in their study of the flag variety, and that reveals to have an important role also in other contexts. These ideals of the polynomial ring are indexed by partitions of n. When the indexing partition is a hook we find a minimal set of generators for the De Concini-Procesi ideal, and we compute explicit formulas for its free minimal resolution.
An extended abstract based on this results appeared at Proc. EACA'06, Universidad de Sevilla. España, (2006).
We show that the Grothendieck bialgebra of the semi-tower of partition lattice algebras is isomorphic to the graded dual of the bialgebra studied in Invariants and coinvariants of the symmetric group in noncommutative variables. In particular this isomorphism singles out a canonical new basis of the symmetric functions in noncommutative variables which would be an analogue of the Schur function basis.
We prove that a conjecture of Fomin, Fulton, Li, and Poon, associated to ordered pairs of partitions, holds for many infinite families of such pairs. We also show that the bounded height case can be reduced to checking that the conjecture holds for a finite number of pairs, for any given height. Moreover, we propose a natural generalization of the conjecture to the case of skew shapes.
Professor François Bergeron wrote some very nice slides explaining our results to an audience of general mathematicians at Dartmouth.
An extended abstract based on this results appeared at Proc. of the FPSAC'2004. University of British Columbia, Canada. (2004)
Consider the algebra of formal power series in countably many noncommuting variables over the rationals. The subalgebra \Pi(x) of symmetric functions in noncommuting variables consists of all elements invariant under permutation of the variables and of bounded degree. We develop a theory of such functions analogous to the ordinary theory of symmetric functions. In particular, we define analogs of the monomial, power sum, elementary, and complete homogeneous, and Schur symmetric functions as well as investigating their properties.
Professor Bruce Sagan wrote some interesting slides relating symmetric functions in noncommutative variables to Stanley's chromatic polynomial. Graph coloring and symmetric functions in noncommuting variables.
An extended abstract based on this results appeared at Proc. of the FPSAC'2003. pp.288-299. Linkopings Universitet, Sweden. (2003)
A MacMahon symmetric function is a formal power series in a finite number of alphabets that is invariant under the diagonal action of the symmetric group. In this article, we give a combinatorial overview of the Hopf algebra structure of the MacMahon symmetric function relying on the construction of a Hopf algebra from any alphabet of neutral letters due to Gian-Carlo Rota and Joel Stein.
A MacMahon symmetric function is a formal power series in a finite number of alphabets that is invariant under the diagonal action of the symmetric group. We use a combinatorial construction of the different bases of the vector space of MacMahon symmetric functions found by the author to obtain their image under the principal specialization: the powers, risings and falling factorials. Then, we compute the connection coefficients of the different polynomial bases in a combinatorial way.
A MacMahon symmetric function is a formal power series
in a finite number of alphabets that is invariant under
the diagonal action
of the symmetric group. In this article, we show that
the MacMahon symmetric functions are the generating
functions for the orbits of sets of functions indexed
by partitions under the diagonal action of a Young subgroup
of a symmetric group.
We define a MacMahon chromatic symmetric function that
generalizes Stanley's chromatic symmetric function. Then,
we study some of the properties of this new function
thru its connection with the noncommutative chromatic symmetric
function of Gebhard and Sagan.
An extended abstract based on this results appeared Proc. of the FPSAC'1999, 507-518. Universitat Politècnica de Catalunya, España. (1999)
The Kronecker product of two Schur functions, is the Frobenius
characteristic of the tensor product of the irreducible
representations of the symmetric group. The coefficients of the
Kronecker product of two Schur functions in the Schur basis are
the multiplicity of the irreducible representations of the
symmetric group is such a tensor product. They are called
the Kronecker coefficients.
We use Sergeev's Formula for a Schur
function of a difference of two alphabets and the
comultiplication expansion for a Schur function to find
closed formulas for the Kronecker coefficients corresponding
hook shapes or two-row shapes.
An extended abstract based on this results appeared Proc. of the FPSAC'2000. Moscow State University, Russia. Springer-Verlag, 344-355. (2000)
A brief introduction to some recent problems in Algebraic Combinatorics.
Includes topics on total positivity, symmetric functions, and hyperplane
arrangements.
An invitation to the fascinating numbers of Euler and Catalan. After reading this articles, visit the webpage of Richard Stanley and play with the many known interpretations for the Catalan numbers. See also a long problem concerning the many interpretations for the Catalan numbers, by Richard Stanley, as well as his Catalan Addendum..
In this note we show how to add the geometric series and its derivatives, only using tools known before the creation of Calculus. We do this in a way that may have known to Jacobo Bernoulli, and is inspired by his work.
Written under the direction of Ira Gessel. Most of the results of my thesis later appeared in some of the aforementioned papers