We give a combinatorial formula for the inverses of the alternating sums of free quasi-symmetric functions of the form F_{Ω(I)} where I runs over compositions with parts in a prescribed set C. This proves in particular three special cases (no restriction, even parts, and all parts equal to 2) which were conjectured by B. C. V. Ung in [Proc. FPSAC'98, Toronto].
Get the introduction of the paper.
Download the arXiv files of the paper.
We construct unital extensions of the higher order peak algebras defined by Krob and the third author in [Ann. Comb. 9 (2005), 411-430], and show that they can be obtained as homomorphic images of certain subalgebras of the Mantaci-Reutenauer algebras of type B.
This generalizes a result of Bergeron, Nyman and the first author [Trans. AMS 356 (2004), 2781-2824.].
Get the introduction of the paper.
Download the arXiv files of the paper.
We prove a Cauchy identity for free quasi-symmetric functions and apply it to the study of various bases. A free Weyl formula and a generalization of the splitting formula are also discussed.
Get the introduction of the paper.
Download the arXiv files of the paper.
We introduce analogs of the Hopf algebra of Free quasi-symmetric functions with bases labelled by colored permutations. When the color set is a semigroup, an internal product can be introduced. This leads to the construction of generalized descent algebras associated with wreath products C∫Σn and to the corresponding generalizations of quasi-symmetric functions. The associated Hopf algebras appear as natural analogs of McMahon's multisymmetric functions.
As a consequence, we obtain an internal product on ordinary multi-symmetric functions. We extend these constructions to Hopf algebras of colored parking functions, colored non-crossing partitions and parking functions of type B.
Get the introduction of the paper.
Download the arXiv files of the paper.
We introduce a new family of noncommutative analogues of the Hall-Littlewood symmetric functions. Our construction relies upon Tevlin's bases and simple q-deformations of the classical combinatorial Hopf algebras. We connect our new Hall-Littlewood functions to permutation tableaux, and also give an exact formula for the q-enumeration of permutation tableaux of a fixed shape.
This gives an explicit formula for: the steady state probability of each state in the partially asymmetric exclusion process (PASEP); the polynomial enumerating permutations with a fixed set of {\it weak excedances} according to crossings; the polynomial enumerating permutations with a fixed set of descent bottoms according to occurrences of the generalized pattern 2-31.
Get the introduction of the paper.
Download the arXiv files of the paper.
We extend a classical construction on symmetric functions, the superization process, to several combinatorial Hopf algebras, and obtain analogs of the hook-content formula for the (q,t)-specializations of various bases.
Exploiting the dendriform structures yields in particular (q,t)-analogs of the Björner-Wachs q-hook-length formulas for binary trees, and similar formulas for plane trees.
Get the introduction of the paper.
Download the arXiv files of the paper.
We investigate several Hopf algebras of diagrams related to Quantum Field Theory of Partitions and whose product comes from the Hopf algebras WSym or WQSym respectively built on integer set partitions and set compositions. Bases of these algebras are indexed either by bipartite graphs (labelled or unlabbeled) or by packed matrices (with integer or set coefficients). Realizations on biword are exhibited, and it is shown how these algebras fit into a commutative diagram. Hopf deformations and dendriform structures are also considered for some algebras in the picture.
Get the introduction of the paper.
Download the arXiv files of the paper.
Let Mn be the n!*n! matrix indexed by permutations of the symmetric group Sn, defined by Mn(σ,τ)=1 if every descent of τ-1 is also a descent of &sigma, and Mn(σ,τ)=0 otherwise. We prove the following result, conjectured by P. Dehornoy: the characteristic polynomial Pn(x)=|xI-Mn| of Mn divides Pn+1(x) in Z[x].
Get the introduction of the paper.
Download the arXiv files of the paper.
We prove conjectures of the third author~[L. Tevlin, Proc. FPSAC'07, Tianjin] on two new bases of noncommutative symmetric functions: the transition matrices from the ribbon basis have nonnegative integral coefficients. This is done by means of two composition-valued statistics on permutations and packed words, which generalize the combinatorics of Genocchi numbers.
Get the introduction of the paper.
Download the arXiv files of the paper.
The operad of moulds is realized in terms of an operational calculus of formal integrals (continuous formal power series). This leads to many simplifications and to the discovery of various suboperads. In particular, we prove a conjecture of the first author about the inverse image of non-crossing trees in the dendriform operad. Finally, we explain a connection with the formalism of noncommutative symmetric functions.
Get the introduction of the paper.
Download the arXiv files of the paper.
We prove a q-identity in the dendriform dialgebra of colored free quasi-symmetric functions. For q=1, we recover identities due to Ebrahimi-Fard, Manchon, and Patras, in particular the noncommutative Bohnenblust-Spitzer identity.
Get the introduction of the paper.
Download the arXiv files of the paper.
We study properties of the forgotten monoid which appeared in work of Lascoux and Sch\"utzenberger and recently resurfaced in the construction of dual equivalence graphs by Assaf. In particular, we provide an explicit characterization of the forgotten classes in terms of inversion numbers and show that there are $n^2-3n+4$ forgotten classes in the symmetric group $S_n$. Each forgotten class contains a canonical element that can be characterized by pattern avoidance. We also show that the sum of Gessel's quasi-symmetric functions over a forgotten class is a 0-1 sum of ribbon-Schur functions.
Get the introduction of the paper.
Download the arXiv files of the paper.
One of the main virtues of trees is to represent formal solutions of various functional equations which can be cast in the form of fixed point problems. Basic examples include differential equations and functional (Lagrange) inversion in power series rings. When analyzed in terms of combinatorial Hopf algebras, the simplest examples yield interesting algebraic identities or enumerative results.
Get the introduction of the paper.
Download the arXiv files of the paper.
Schneps [J. Lie Theory 16 (2006), 19-37] has found surprising links between Ihara brackets and even period polynomials. These results can be recovered and generalized by considering some identities relating Ihara brackets and classical Lie brackets. The period polynomials generated by this method are found to be essentially the Kohnen-Zagier polynomials.
Get the introduction of the paper.
Download the arXiv files of the paper.
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.
Get the introduction of the paper.
Download the arXiv files of the paper.
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.
Get the introduction of the paper.
Download the arXiv files of the paper.
A result of Foata and Schützenberger 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.
Get the introduction of the paper.
Download the arXiv files of the paper.
The consideration of tensor products of $0$-Hecke algebra modules leads to natural analogs of the Bessel $J$-functions in the algebra of noncommutative symmetric functions. This provides a simple explanation of various combinatorial properties of Bessel functions.
Get the introduction of the paper.
Download the arXiv files of the paper.
We compute the noncommutative Frobenius characteristic of the natural action of the 0-Hecke algebra on parking functions, and obtain as corollaries various forms of the noncommutative Lagrange inversion formula.
Get the introduction of the paper.
Download the arXiv files of the paper.
We introduce a graded Hopf algebra based on the set of parking functions (hence of dimension (n+1)n-1 in degree n). This algebra can be embedded into a noncommutative polynomial algebra in infinitely many variables. We determine its structure, and show that it admits natural quotients and subalgebras whose graded components have dimensions respectively given by the Schr\"oder numbers (plane trees), the Catalan numbers, and powers of 3.
These smaller algebras are always bialgebras and belong to some family of di- or tri-algebras occurring in the works of Loday and Ronco.
Moreover, the fundamental notion of parkization allows one to endow the set of parking functions of fixed length with an associative multiplication (different from the one coming from the Shi arrangement), leading to a generalization of the internal product of symmetric functions. Several of the intermediate algebras are stable under this operation. Among them, one finds the Solomon descent algebra but also a new algebra based on a Catalan set, admitting the Solomon algebra as a left ideal.
Get the introduction of the paper.
Download the arXiv files of the paper.
We realize the free dendriform trialgebra on one generator, as well as several other examples of dendriform trialgebras, as sub-trialgebras of an algebra of noncommutative polynomials in infinitely many variables.
Nous réalisons la trigèbre dendriforme libre sur un générateur, et plusieurs autres exemples de trigèbres dendriformes, comme sous-trigèbres d'une algèbre de polynômes non commutatifs en une infinité de variables.
Get the introduction of the paper.
Download the arXiv files of the paper.
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.
Get the introduction of the paper.
Download the arXiv files of the paper.
We show that the notion of parkization of a word, a variant of the classical standardization, allows to introduce an internal product on each homogeneous component of the Hopf algebra of parking functions. The Catalan subalgebra is stable under this operation and contains the descent algebra of type A as a left ideal.
Get the introduction of the paper.
Download the arXiv files of the paper.
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.
Get the introduction of the paper.
Download the arXiv files of the paper.
We define graded Hopf algebras with bases labeled by various types of graphs and hypergraphs, provided with natural embeddings into an algebra of polynomials in infinitely many variables. These algebras are graded by the number of edges and can be considered as generalizations of symmetric or quasi-symmetric functions.
Nous définissons des algèbres de Hopf dont les bases sont étiquetées par divers types de graphes et hypergraphes et les réalisons comme sous-algèbres d'une algèbre de polynômes en une infinité de variables. Ces algèbres sont graduées par le nombre d'arêtes et peuvent être considérées comme des généralisations des fonctions symétriques ou quasi-symétriques.
Get the introduction of the paper.
Download the arXiv files of the paper.
If the moments of a probability measure on R are interpreted as a specialization of complete homogeneous symmetric functions, its free cumulants are, up to sign, the corresponding specializations of a sequence of Schur positive symmetric functions (fn). We prove that (fn) is the Frobenius characteristic of the natural permutation representation of Sn on the set of prime parking functions. This observation leads us to the construction of a Hopf algebra of parking functions, which we study in some detail.
Get the introduction of the paper.
Download the arXiv files of the paper.
We show that there exists at least one tower of algebras whose Grothendieck ring is the algebra of planar binary trees of Loday-Ronco.
Nous montrons qu'il existe au moins une tour d'algèbres ayant comme anneau de Grothendieck l'algèbre des arbres binaires de Loday-Ronco.
Get the introduction of the paper.
Download the ps file of the paper.
In this paper, we compute the dimensions of the graded Lie algebra dmr0 (introduced by Racinet in [S\'eries génératrices non-commutatives de polyzêtas et associateurs de {Drinfel'd}}, Ph.D. thesis, Amiens, France, 2000] up to a given degree.
These results prove that, up to this degree, the Lie algebra dmr0 is free over one element in each odd degree greater than or equal to 3, this element being the one introduced by Drinfel'd in [Quasi-Hopf algebras, Lenin Math. Jour., 1, (1990) 1419-1457] and belonging to his Lie algebra grt1. In particular, this proves, up to the same degree, that the double shuffle and regularization relations imply the associators relations, and that the formal dimension conjecture of Zagier is true.
Get the introduction of the paper.
Download the ps file of the paper.
We introduce a monoid structure on a certain set of labelled binary trees, by a process similar to the construction of the plactic monoid. This yields a new approach to the algebra of planar binary trees of Loday-Ronco.
Nous introduisons une structure de monoïde sur un ensemble d'arbres binaires étiquetés, par un procé\'edé\'e analogue à la construction du monoïde plaxique. Nous en déduisons une nouvelle approche de l'alg&egreave;bre des arbres binaires de Loday-Ronco.
Get the introduction of the paper.
Download the ps file of the paper.
A cocolouring of a graph G is a partition of the vertex set of G such that each set of the partition is either a clique or an independent set in G. Some special cases of the minimum cocolouring problem are of particular interest. We provide polynomial-time algorithms to approximate a mimimum cocolouring on graphs, partially ordered sets and sequences. In particular, we obtain an efficient algorithm to approximate within a factor of 1.71 a minimum partition of a partially ordered set into chains and antichains, and a minimum partition of a sequence into increasing and decreasing subsequences.
Get the introduction of the paper.
Download the ps file of the paper.
We present an overview of Λ-type operations on the algebra of quasi-symmetric functions.
Get the introduction of the paper.
Download the ps file of the paper.
In this paper, we provide the second part of the study of the pseudo-permutations. We first derive a complete analysis of the pseudo-permutations, based on hyperplane arrangements, generalizing the usual way of translating the permutations. We then study the module of the pseudo-permutations over the symmetric group and provide the characteristics of this action.
Get the introduction of the paper.
Download the ps file of the paper.
In this paper, we provide the first study of the sand pile model SPM(0) where we assume that all the grains are numbered with a distinct integer. We obtain a lower bound on the number of terminal sand piles by establishing a bijection between a subset of these sand piles and the set of shifted Young tableaux. We then prove that this number is at least factorial.
Get the introduction of the paper.
Download the ps file of the paper.
This paper presents a combinatorial study of the Chinese monoid, a ternary monoid related to the plactic monoid and based on the relation scheme cba~bca~cab. An algorithm similar to Schensted's algorithm yields a characterization of the equivalence classes and a cross-section theorem. We also establish a Robinson-Schensted correspondence for the Chinese monoid before computing the order of specific Chinese classes. For this work, we had to develop some new combinatorial tools. Among other things we discovered an embedding of every equivalence class in the largest one. Finally, the end of this paper is devoted to the study of conjugacy classes.
Get the introduction of the paper.
Download the ps file of the paper.
In this paper, we introduce new combinatorial objects, the pseudo-permutations, which are a generalization of the permutations. Pseudo-permutations naturally appear in various fields of Computer Science and Mathematics. We provide the first combinatorial results on these objects: we study the classical statistics of enumeration, inversions, descents and we prove that the set of all pseudo-permutations has a lattice structure.
Get the introduction of the paper.
Download the ps file of the paper.
This paper deals with the study of the center of a q-analog of the plactic algebra, the quantum pseudoplactic algebra defined by Krob and Thibon in [D. Krob and J.-Y. Thibon, Noncommutative symmetric functions IV: Quantum linear groups and Hecke algebras at q=0, J. Alg. Comb. 6 (1997), 339--376].
We prove that the center of this algebra is reduced to the algebra generated by one polynomial, the so-called quantum elementary symmetric function of maximal weight.
Get the introduction of the paper.
Download the ps file of the paper.
This paper presents a combinatorial study of the hypoplactic monoid that is the analog of the plactic monoid in the theory of noncommutative symmetric functions. After having recalled its definition using rewritings, we provide a new definition and use this one to combinatorially prove that each hypoplactic class contains exactly one quasi-ribbon word. We then prove hypoplactic analogues of classical results of the plactic monoid and, in particular, we make the study of the analogues of Schur functions.
Get the introduction of the paper.
Download the ps file of the paper.
This paper presents a study of permutations avoiding the pattern ΩN = N,N-1...,1. After having recalled the basic definitions, we prove that this set of permutations is an ideal for the weak Bruhat order and begin the study of its maximal elements. We then present an algorithm that generates these elements and find out that they can be obtained from an automaton. We finally give some asymptotics about their number.
Get the introduction of the paper.
Download the ps file of the paper.
This paper presents some relations between noncommutative symmetric functions and free Lie algebras. We show in particular how to decompose a Lie projector of Solomon's descent algebra on Dynkin's and Klyachko's bases. We illustrate these methods on the example of the Hausdorff series.
Get the introduction of the paper.
Download the ps file of the paper.
We give a simple bijective proof of the hook-length formula.
Click here for a journal version. You can also check the Third Edition of Don Knuth's "The Art of Computer Programming", Vol. 3, 1998, for a 2-page overview of the algorithm.
Here is what
Christian
Krattenthaler writes in the
Math. Reviews,
99h:05123:
"This is probably the most important recent contribution
to bijective combinatorics."
Download the ps file, of the full review.
This paper proves what was announced in Short Bijective Proof of the Hook-length Formula, Funct. Anal. Appl., vol. 26, 1992, 216-218 (I. Pak and A.V. Stoyanovsky). Download the .pdf file of the note.