Search

The m-Tamari lattice of F. Bergeron is an analogue of the clasical Tamari order defined on objects counted by Fuss-Catalan numbers, such as m-Dyck paths or (m+1)-ary trees. On another hand, the Tamari order is related to the product in the Loday-Ronco Hopf algebra of planar binary trees. We introduce new combinatorial Hopf algebras based on (m+1)-ary trees, whose structure is described by the m-Tamari lattices. In the same way as planar binary trees can be interpreted as sylvester classes of permutations, we obtain (m+1)-ary trees as sylvester classes of what we call m-permutations. These objects are no longer in bijection with decreasing (m+1)-ary trees, and a finer congruence, called metasylvester, allows us to build Hopf algebras based on these decreasing trees. At the opposite, a coarser congruence, called hyposylvester, leads to Hopf algebras of graded dimensions (m+1)^{n-1}, generalizing noncommutative symmetric functions and quasi-symmetric functions in a natural way. Finally, the algebras of packed words and parking functions also admit such m-analogues, and we present their subalgebras and quotients induced by the various congruences., Comment: 51 pages

The Hopf algebra of word-quasi-symmetric functions ($\WQSym$), a noncommutative generalization of the Hopf algebra of quasi-symmetric functions, can be endowed with an internal product that has several compatibility properties with the other operations on $\WQSym$. This extends constructions familiar and central in the theory of free Lie algebras, noncommutative symmetric functions and their various applications fields, and allows to interpret $\WQSym$ as a convolution algebra of linear endomorphisms of quasi-shuffle algebras. We then use this interpretation to study the fine structure of quasi-shuffle algebras (MZVs, free Rota-Baxter algebras...). In particular, we compute their Adams operations and prove the existence of generalized Eulerian idempotents, that is, of a canonical left-inverse to the natural surjection map to their indecomposables, allowing for the combinatorial construction of free polynomial generators for these algebras., Comment: 18 pages

We construct explicit polynomial realizations of some combinatorial Hopf algebras based on various kind of trees or forests, and some more general classes of graphs, ranging from the Connes-Kreimer algebra to an algebra of labelled forests isomorphic to the Hopf algebra of parking functions, and to a new noncommutative algebra based on endofunctions admitting many interesting subalgebras and quotients., Comment: 20 pages

We extend to several combinatorial Hopf algebras the endomorphism of symmetric functions sending the first power-sum to zero and leaving the other ones invariant. As a transformation of alphabets, this is the (1-E)-transform, where E is the exponential alphabet, whose elementary symmetric functions are e_n=1/n!. In the case of noncommutative symmetric functions, we recover Schocker's idempotents for derangement numbers [Discr. Math. 269 (2003), 239]. From these idempotents, we construct subalgebras of the descent algebras analogous to the peak algebras and study their representation theory. The case of WQSym leads to similar subalgebras of the Solomon-Tits algebras. In FQSym, the study of the transformation boils down to a simple solution of the Tsetlin library in the uniform case., Comment: 33 pages

Descents in permutations or words are defined from the relative position of two consecutive letters. We investigate a statistic involving patterns of k consecutive letters, and show that it leads to Hopf algebras generalizing noncommutative symmetric functions and quasi-symmetric functions., Comment: 8 pages

The hyperdeteminants considered here are the simplest analogues of determinants for higher rank tensors which have been defined by Cayley, and apply only to tensors with an even number of indices. We have shown in a previous article that the calculation of certain multidimensional integrals could be reduced to the evaluation of hyperdeterminants of Hankel type. Here, we carry out this computation by purely algebraic means in the cases of Selberg's and Aomoto's integrals.

We propose several constructions of commutative or cocommutative Hopf algebras based on various combinatorial structures, and investigate the relations between them. A commutative Hopf algebra of permutations is obtained by a general construction based on graphs, and its non-commutative dual is realized in three different ways, in particular as the Grossman-Larson algebra of heap ordered trees. Extensions to endofunctions, parking functions, set compositions, set partitions, planar binary trees and rooted forests are discussed. Finally, we introduce one-parameter families interpolating between different structures constructed on the same combinatorial objects., Comment: 29 pages, LaTEX; expanded and updated version of math.CO/0502456

We realize several combinatorial Hopf algebras based on set compositions, plane trees and segmented compositions in terms of noncommutative polynomials in infinitely many variables. For each of them, we describe a trialgebra structure, an internal product, and several bases., Comment: 12 pages, LaTEX, to be presented at FPSAC'06

A result of Foata and Schutzenberger states that two statistics on permutations, the number of inversions and the inverse major index, have the same distribution on a descent class. We give a multivariate generalization of this property: the sorted vectors of the Lehmer code, of the inverse majcode, and of a new code (the inverse saillance code), have the same distribution on a descent class, and their common multivariate generating function is a flagged ribbon Schur function., Comment: 17 pages, LaTex; Minor correction in the proof of Lemma 6.5; one reference added

After reformulating the representation theory of 0-Hecke algebras in an appropriate family of Yang-Baxter bases, we investigate certain specializations of the Ariki-Koike algebras, obtained by setting q=0 in a suitably normalized version of Shoji's presentation. We classify the simple and projective modules, and describe restrictions, induction products, Cartan invariants and decomposition matrices. This allows us to identify the Grothendieck rings of the towers of algebras in terms of certain graded Hopf algebras known as the Mantaci-Reutenauer descent algebras, and Poirier quasi-symmetric functions. We also describe the Ext-quivers, and conclude with numerical tables., Comment: 46 pages, LaTEX

We propose several constructions of commutative or cocommutative Hopf algebras based on various combinatorial structures, and investigate the relations between them. A commutative Hopf algebra of permutations is obtained by a general construction based on graphs, and its non-commutative dual is realized in three different ways, in particular as the Grossman-Larson algebra of heap ordered trees. Extensions to endofunctions, parking functions, set partitions, planar binary trees and rooted forests are discussed. Finally, we introduce one-parameter families interpolating between different structures constructed on the same combinatorial objects., Comment: 18 pages, LaTEX

We investigate the representation theory of certain specializations of the Ariki-Koike algebras, obtained by setting $q=0$ in a suitably normalized version of Shoji's presentation. We classify the simple and projective modules, and describe restrictions, induction products, Cartan invariants and decomposition matrices. This allows us to identify the Grothendieck rings of the towers of algebras in terms of certain graded Hopf algebras known as the Mantaci-Reutenauer descent algebras, and Poirier Quasi-symmetric functions., Comment: 12 pages; LaTEX

We introduce a monoid structure on the set of binary search trees, by a process very similar to the construction of the plactic monoid, the Robinson-Schensted insertion being replaced by the binary search tree insertion. This leads to a new construction of the algebra of Planar Binary Trees of Loday-Ronco, defining it in the same way as Non-Commutative Symmetric Functions and Free Symmetric Functions. We briefly explain how the main known properties of the Loday-Ronco algebra can be described and proved with this combinatorial point of view, and then discuss it from a representation theoretical point of view, which in turns leads to new combinatorial properties of binary trees., Comment: 49 pages

We study the invariant theory of trilinear forms over a three-dimensional complex vector space, and apply it to investigate the behaviour of pure entangled three-partite qutrit states and their normal forms under local filtering operations (SLOCC). We describe the orbit space of the SLOCC group $SL(3,\C)^{\times 3}$ both in its affine and projective versions in terms of a very symmetric normal form parameterized by three complex numbers. The parameters of the possible normal forms of a given state are roots of an algebraic equation, which is proved to be solvable by radicals. The structure of the sets of equivalent normal forms is related to the geometry of certain regular complex polytopes., Comment: 19 pages, revtex4, three figures; revised version

We obtain a complete and minimal set of 170 generators for the algebra of $SL(2,\C)^{\times 4}$-covariants of a binary quadrilinear form. Interpreted in terms of a four qubit system, this describes in particular the algebraic varieties formed by the orbits of local filtering operations in its projective Hilbert space. Also, this sheds some light on the local unitary invariants, and provides all the possible building blocks for the construction of entanglement measures for such a system., Comment: 14 pages, IOP macros; slightly expanded version

We describe explicitly the algebra of polynomial functions on the Hilbert space of four qubit states which are invariant under the SLOCC group $SL(2,{\mathbb C})^{4}$. From this description, we obtain a closed formula for the hyperdeterminant in terms of low degree invariants., Comment: 5 pages, revtex4; some typos corrected

We investigate the simplest class of hyperdeterminants defined by Cayley in the case of Hankel hypermatrices (tensors of the form $A_{i_1i_2... i_k}=f(i_1+i_2+...+i_k)$). It is found that many classical properties of Hankel determinants can be generalized, and a connection with Selberg type integrals is established. In particular, Selberg's original formula amounts to the evaluation of all Hankel hyperdeterminants built from the moments of the Jacobi polynomials. Many higher-dimensional analogues of classical Hankel determinants are evaluated in closed form. The Toeplitz case is also briefly discussed. In physical terms, both cases are related to the partition functions of one-dimensional Coulomb systems with logarithmic potential., Comment: 32 pages, LaTex, IOP macros

Chen's lemma on iterated integrals implies that certain identities involving multiple integrals, such as the de Bruijn and Wick formulas, amount to combinatorial identities for Pfaffians and hafnians in shuffle algebras. We provide direct algebraic proofs of such shuffle identities, and obtain various generalizations. We also discuss some Pfaffian identities due to Sundquist and Ishikawa-Wakayama, and a Cauchy formula for anticommutative symmetric functions. Finally, we extend some of the previous considerations to hyperpfaffians and hyperhafnians., Comment: 28 pages, LaTex. Minor typos corrected, two references added

We define two-parameter families of noncommutative symmetric functions and quasi-symmetric functions, which appear to be the proper analogues of the Macdonald symmetric functions in these settings., Comment: 13 pages, LaTex

This article is devoted to the study of several algebras which are related to symmetric functions, and which admit linear bases labelled by various combinatorial objects: permutations (free quasi-symmetric functions), standard Young tableaux (free symmetric functions) and packed integer matrices (matrix quasi-symmetric functions). Free quasi-symmetric functions provide a kind of noncommutative Frobenius characteristic for a certain category of modules over the 0-Hecke algebras. New examples of indecomposable $H_n(0)$-modules are discussed, and the homological properties of $H_n(0)$ are computed for small $n$. Finally, the algebra of matrix quasi-symmetric functions is interpreted as a convolution algebra., Comment: 46 pages, LaTex, epsf macros

We exhibit a vertex operator which implements multiplication by power-sums of Jucys-Murphy elements in the centers of the group algebras of all symmetric groups simultaneously. The coefficients of this operator generate a representation of ${\cal W}_{1+\infty}$, to which operators multiplying by normalized conjugacy classes are also shown to belong. A new derivation of such operators based on matrix integrals is proposed, and our vertex operator is used to give an alternative approach to the polynomial functions on Young diagrams introduced by Kerov and Olshanski., Comment: 23 pages, LaTex. Minor typos corrected

Starting from known $q$-analogues of ordinary SU(n) tensor products multiplicities, we introduce $q$-analogues of the fusion coefficients of the WZW conformal field theories associated with SU(n). We conjecture combinatorial interpretations of these polynomials, which can be proved in special cases. This allows us to derive in a simple way various kinds of branching functions, the simplest ones being the characters of the minimal unitary series of the Virasoro algebra. We also obtain $q$-analogues of the dimensions of spaces of nonabelian theta functions., Comment: 12 pages, Latex, epsf and iop macros. Extended abstract of a talk presented by J.-Y. T. at the conference "Symmetry and Structural Properties of Condensed Matter" (Zajackowo, August 27-September 2, 1998)

We give a combinatorial algorithm for computing Zelevinsky's involution of the set of isomorphism classes of irreducible representations of the affine Hecke algebra $\H_m(t)$ when $t$ is a primitive $n$th root of 1. We show that the same map can also be interpreted in terms of aperiodic nilpotent orbits of $\Zb/n\Zb$-graded vector spaces., Comment: 17 pages, Latex, epsf macros

We study the restrictions of simple modules of Ariki-Koike algebras $\H_m(\v)$ with set of parameters $\v= (\zeta;\zeta^{v_0},... ,\zeta^{v_{l-1}})$, where $\zeta$ is an $n$th root of unity, to their subalgebras $\H_{m-j}(\v)$. Using a theorem of Ariki and the crystal basis theory of Kashiwara, we relate this problem to the calculation of tensor product multiplicities of highest weight irreducible representations of the affine Lie algebra $A_{n-1}^{(1)}$. These multiplicities have a combinatorial description in terms of higher level paths or highest-lift multipartitions. This enables us to solve the Jantzen-Seitz problem for Ariki-Koike algebras, that is, to determine which irreducible representations of $\H_m(\v)$ restrict to irreducible representations of $\H_{m-1}(\v)$. From a combinatorial point of view, this problem is identical to that of computing the tensor product of an $A_{n-1}^{(1)}$-module of level $l$ and one of level 1. We also consider natural generalisations of the Jantzen-Seitz problem corresponding to the product of a level $l$ module by a level $l'>1$ module, and from the commutativity of tensor products, we deduce a remarkable symmetry between the generalised Jantzen-Seitz conditions and the sets of parameters of the Ariki-Koike algebras., Comment: 35 pages, Latex, epsf macros

We use the Fock space representation of the quantum affine algebra of type $A^{(2)}_{2n}$ to obtain a description of the global crystal basis of its basic level 1 module. We formulate a conjecture relating this basis to decomposition matrices of spin symmetric groups in characteristic $2n+1$., Comment: 18 pages, Latex, epsf and iop macros (ioplppt.sty). Revised version, to appear in J. Phys. A. Some typos corrected, and some comments added in the introduction

We show that the quantum straightening algorithm for Young tableaux and Young bitableaux reduces in the crystal limit $q \mapsto 0$ to the Robinson-Schensted algorithm., Comment: LaTeX file with eepic pictures, 23 pages

We give an expression of the $q$-analogues of the multiplicities of weights in irreducible $\sl_{n+1}$-modules in terms of the geometry of the crystal graph attached to the corresponding $U_q(\sl_{n+1})$-modules. As an application, we describe multivariate polynomial analogues of the multiplicities of the zero weight, refining Kostant's generalized exponents., Comment: LaTeX file with epic, eepic pictures, 17 pages, November 1994, to appear in Lett. Math. Phys

This paper presents a noncommutative theory of symmetric functions, based on the notion of quasi-determinant. We begin with a formal theory, corresponding to the case of symmetric functions in an infinite number of independent variables. This allows us to endow the resulting algebra with a Hopf structure, which leads to a new method for computing in descent algebras. It also gives unified reinterpretation of a number of classical constructions. Next, we study the noncommutative analogs of symmetric polynomials. One arrives at different constructions, according to the particular kind of application under consideration. For example, when a polynomial with noncommutative coefficients in one central variable is decomposed as a product of linear factors, the roots of these factors differ from those of the expanded polynomial. Thus, according to whether one is interested in the construction of a polynomial with given roots or in the expansion of a product of linear factors, one has to consider two distinct specializations of the formal symmetric functions. A third type appears when one looks for a noncommutative generalization of applications related to the notion of characteristic polynomial of a matrix. This construction can be applied, for instance, to the noncommutative matrices formed by the generators of the universal enveloping algebra $U(gl_n)$ or of, Comment: 111 pages