Showing 1–39 of 39 results for author: Hivert, F

Power Quotients of Plactic-like Monoids

Authors: Antoine Abram, Florent Hivert, James D. Mitchell, Jean-Christophe Novelli, Maria Tsalakou

Abstract: In this paper we describe the quotients of several plactic-like monoids by the least congruences containing the relations $a^{σ(a)} = a$ with $σ(a)\ge 2$ for every generator $a$. The starting point for this description is the recent paper of Abram and Reutenauer about the so-called stylic monoid which happens to be the quotient of the plactic monoid by the relations $a^2 = a$ for every letter $a$.… ▽ More In this paper we describe the quotients of several plactic-like monoids by the least congruences containing the relations $a^{σ(a)} = a$ with $σ(a)\ge 2$ for every generator $a$. The starting point for this description is the recent paper of Abram and Reutenauer about the so-called stylic monoid which happens to be the quotient of the plactic monoid by the relations $a^2 = a$ for every letter $a$. The plactic-like monoids considered are the plactic monoid itself, the Chinese monoid, and the sylvester monoid. In each case we describe: a set of normal forms, and the idempotents; and obtain formulae for their size. △ Less

Submitted 24 June, 2024; originally announced June 2024.

Comments: In Proceedings GASCom 2024, arXiv:2406.14588

Journal ref: EPTCS 403, 2024, pp. 12-17

Diagram model for the Okada algebra and monoid

Authors: Florent Hivert, Jeanne Scott

Abstract: It is well known that the Young lattice is the Bratelli diagram of the symmetric groups expressing how irreducible representations restrict from $S_N$ to $S_{N-1}$. In 1988, Stanley discovered a similar lattice called the Young-Fibonacci lattice which was realized as the Bratelli diagram of a family of algebras by Okada in 1994. In this paper, we realize the Okada algebra and its associated monoid… ▽ More It is well known that the Young lattice is the Bratelli diagram of the symmetric groups expressing how irreducible representations restrict from $S_N$ to $S_{N-1}$. In 1988, Stanley discovered a similar lattice called the Young-Fibonacci lattice which was realized as the Bratelli diagram of a family of algebras by Okada in 1994. In this paper, we realize the Okada algebra and its associated monoid using a labeled version of Temperley-Lieb arc-diagrams. We prove in full generality that the dimension of the Okada algebra is $n!$. In particular, we interpret a natural bijection between permutations and labeled arc-diagrams as an instance of Fomin's Robinson-Schensted correspondence for the Young-Fibonacci lattice. We prove that the Okada monoid is aperiodic and describe its Green relations. Lifting those results to the algebra allows us to construct a cellular basis of the Okada algebra. } △ Less

Submitted 25 April, 2024; originally announced April 2024.

Comments: Submitted to FPSAC 2024

MSC Class: 05E05 (primary); 05E10; 16G99; 20M99; 20C30 ACM Class: G.2.1

Controlling the C3 super class linearization algorithm

Authors: Florent Hivert, Nicolas M. Thiéry

Abstract: C3 is an algorithm used by several widely used programming languages such as Python to support multiple inheritance in object oriented programming (OOP): for each class, C3 computes recursively a linear extension of the poset of all its super classes (the Method Resolution Order, MRO) from user-provided local information (an ordering of the direct super classes). This algorithm can fail if the loc… ▽ More C3 is an algorithm used by several widely used programming languages such as Python to support multiple inheritance in object oriented programming (OOP): for each class, C3 computes recursively a linear extension of the poset of all its super classes (the Method Resolution Order, MRO) from user-provided local information (an ordering of the direct super classes). This algorithm can fail if the local information is not consistent. For large hierarchies of classes, as encountered when modeling hierarchies of concepts from abstract algebra in the SageMath computational system, maintaining consistent local information by hand does not scale and leads to unpredictable C3 failures. This paper reports on the authors' work to analyze and circumvent this maintenance nightmare. First, we discovered through extensive computer exploration that there exists posets admitting no consistent local information; we exhibit the smallest one which has 10 elements. Then, we provide and analyze an algorithm that, given a poset and a linear extension, automatically builds local information for C3 in such a way that guarantees that it will never fail, at the price of a slight relaxation of the hypotheses. This algorithm has been used in production in SageMath since 2013. △ Less

Submitted 23 January, 2024; originally announced January 2024.

Comments: 15 pages

MSC Class: 06A06; 68N15

Journal ref: Order, 07/2022, pages 1-16

Non-ambiguous trees: new results and generalisation (Full version)

Authors: Bérénice Delcroix-Oger, Florent Hivert, Patxi Laborde-Zubieta, Jean-Christophe Aval, Adrien Boussicault

Abstract: We present a new definition of non-ambiguous trees (NATs) as labelled binary trees. We thus get a differential equation whose solution can be described combinatorially. This yields a new formula for the number of NATs. We also obtain q-versions of our formula. We finally generalise NATs to higher dimension. We present a new definition of non-ambiguous trees (NATs) as labelled binary trees. We thus get a differential equation whose solution can be described combinatorially. This yields a new formula for the number of NATs. We also obtain q-versions of our formula. We finally generalise NATs to higher dimension. △ Less

Submitted 24 March, 2021; v1 submitted 12 March, 2021; originally announced March 2021.

Comments: full version of arXiv:2103.07294. European Journal of Combinatorics, Elsevier

Minimal generating sets for matrix monoids

Authors: F. Hivert, J. D. Mitchell, F. L. Smith, W. A. Wilson

Abstract: In this paper, we determine minimal generating sets for several well-known monoids of matrices over semirings. In particular, we find minimal generating sets for the monoids consisting of: all $n\times n$ boolean matrices when $n\leq 8$; the $n\times n$ boolean matrices containing the identity matrix (the reflexive boolean matrices) when $n\leq 7$; the $n\times n$ boolean matrices containing a per… ▽ More In this paper, we determine minimal generating sets for several well-known monoids of matrices over semirings. In particular, we find minimal generating sets for the monoids consisting of: all $n\times n$ boolean matrices when $n\leq 8$; the $n\times n$ boolean matrices containing the identity matrix (the reflexive boolean matrices) when $n\leq 7$; the $n\times n$ boolean matrices containing a permutation (the Hall matrices) when $n \leq 8$; the upper, and lower, triangular boolean matrices of every dimension; the $2 \times 2$ matrices over the semiring $\mathbb{N} \cup \{-\infty\}$ with addition $\oplus$ defined by $x\oplus y = \max(x, y)$ and multiplication $\otimes$ given by $x\otimes y = x + y$ (the max-plus semiring); the $2\times 2$ matrices over any quotient of the max-plus semiring by the congruence generated by $t = t + 1$ where $t\in \mathbb{N}$; the $2\times 2$ matrices over the min-plus semiring and its finite quotients by the congruences generated by $t = t + 1$ for all $t\in \mathbb{N}$; and the $n \times n$ matrices over $\mathbb{Z} / n\mathbb{Z}$ relative to their group of units. △ Less

Submitted 10 August, 2021; v1 submitted 18 December, 2020; originally announced December 2020.

Comments: 35 pages (added/updated references)

MSC Class: 20M20

The $0$-Rook Monoid and its Representation Theory

Authors: Joël Gay, Florent Hivert

Abstract: We show that a proper degeneracy at $q=0$ of the $q$-deformed rook monoid of Solomon is the algebra of a monoid $R_n^0$ namely the $0$-rook monoid, in the same vein as Norton's $0$-Hecke algebra being the algebra of a monoid $H_n^0 = H^0(A_{n-1})$ (in Cartan type~$A_{n-1}$). As expected, $R_n^0$ is closely related to the latter: it contains the $H^0(A_{n-1})$ monoid and is a quotient of… ▽ More We show that a proper degeneracy at $q=0$ of the $q$-deformed rook monoid of Solomon is the algebra of a monoid $R_n^0$ namely the $0$-rook monoid, in the same vein as Norton's $0$-Hecke algebra being the algebra of a monoid $H_n^0 = H^0(A_{n-1})$ (in Cartan type~$A_{n-1}$). As expected, $R_n^0$ is closely related to the latter: it contains the $H^0(A_{n-1})$ monoid and is a quotient of $H^0(B_{n})$. We give a presentation for this monoid as well as a combinatorial realization as functions acting on the classical rook monoid itself. On the way we get a Matsumoto theorem for the rook monoid a result which was conjectured by Solomon. The $0$-rook monoid shares many combinatorial properties with the Hecke monoid: its Green right preorder is an actual order, and moreover a lattice (analogous to the right weak order) which has some nice combinatorial, and geometrical features. In particular the $0$-rook monoid is J-trivial. Following Denton-Hivert-Schilling-Thiéry, it allows us to describe its representation theory including the description of the simple and projective modules. We further show that $R_n^0$ is projective on $H_n^0$ and make explicit the restriction and induction functors along the inclusion map. We finally give a (partial) associative tower structures on the family of $(R_n^0)$ and we discuss its representation theory. △ Less

Submitted 28 October, 2019; v1 submitted 25 October, 2019; originally announced October 2019.

Comments: 77 pages, 41 figures

MSC Class: 05E10; 05E15; 20C08; 05B15; 05A05

Signaletic operads

Authors: Florent Hivert, Vincent Pilaud

Abstract: We introduce $k$-signaletic operads and their Koszul duals, generalizing the dendriform, diassociative and duplicial operads (which correspond to the $k=1$ case). We show that the Koszul duals of the $k$-signaletic operads act on multipermutations and that the resulting algebras are free, thus providing combinatorial models for these operads. Finally, motivated by these actions on multipermutation… ▽ More We introduce $k$-signaletic operads and their Koszul duals, generalizing the dendriform, diassociative and duplicial operads (which correspond to the $k=1$ case). We show that the Koszul duals of the $k$-signaletic operads act on multipermutations and that the resulting algebras are free, thus providing combinatorial models for these operads. Finally, motivated by these actions on multipermutations, we introduce similar operations on multiposets which yield yet another relevant operad obtained as Manin powers of the $L$-operad. △ Less

Submitted 23 May, 2024; v1 submitted 5 June, 2019; originally announced June 2019.

Comments: 101 pages, 20 figures. Version 2: Many presentation improvements following referee advices

MSC Class: 18D50; 16T30; 05E15; 05C05; 68Q42

Multiple Lie Derivatives and Forests

Authors: Florent Hivert, Nefton Pali

Abstract: We obtain a complete time expansion of the pull-back operator generated by a real analytic flow of real analytic automorphisms acting on analytic tensor sections of a manifold. Our expansion is given in terms of multiple Lie derivatives. Motivated by this expansion, we provide a rather simple and explicit estimate for higher order covariant derivatives of multiple Lie derivatives acting on smooth… ▽ More We obtain a complete time expansion of the pull-back operator generated by a real analytic flow of real analytic automorphisms acting on analytic tensor sections of a manifold. Our expansion is given in terms of multiple Lie derivatives. Motivated by this expansion, we provide a rather simple and explicit estimate for higher order covariant derivatives of multiple Lie derivatives acting on smooth endomorphism sections of the tangent bundle of a manifold. We assume the covariant derivative to be torsion free. The estimate is given in terms of Dyck polynomials. The proof uses a new result on the combinatorics of rooted labeled ordered forests and Dyck polynomials. △ Less

Submitted 21 June, 2018; originally announced June 2018.

Comments: 27 pages

Journal ref: Advances in Mathematics, 354, (2019), 28 pp

Non-ambiguous trees: new results and generalisation

Authors: Jean-Christophe Aval, Adrien Boussicault, Berenice Delcroix-Oger, Florent Hivert, Patxi Laborde-Zubieta

Abstract: We present a new definition of non-ambiguous trees (NATs) as labelled binary trees. We thus get a differential equation whose solution can be described combinatorially. This yield a new formula for the number of NATs. We also obtain q-versions of our formula. And we generalize NATs to higher dimension. We present a new definition of non-ambiguous trees (NATs) as labelled binary trees. We thus get a differential equation whose solution can be described combinatorially. This yield a new formula for the number of NATs. We also obtain q-versions of our formula. And we generalize NATs to higher dimension. △ Less

Submitted 30 November, 2015; originally announced November 2015.

Comments: Extended abstract

A set-operad of formal fractions and dendriform-like sub-operads

Authors: Frédéric Chapoton, Florent Hivert, Jean-Christophe Novelli

Abstract: We introduce an operad of formal fractions, abstracted from the Mould operads and containing both the Dendriform and the Tridendriform operads. We consider the smallest set-operad contained in this operad and containing four specific elements of arity two, corresponding to the generators and the associative elements of the Dendriform and Tridendriform operads. We obtain a presentation of this oper… ▽ More We introduce an operad of formal fractions, abstracted from the Mould operads and containing both the Dendriform and the Tridendriform operads. We consider the smallest set-operad contained in this operad and containing four specific elements of arity two, corresponding to the generators and the associative elements of the Dendriform and Tridendriform operads. We obtain a presentation of this operad (by binary generators and quadratic relations) and an explicit combinatorial description using a new kind of bi-colored trees. Similar results are also presented for related symmetric operads. △ Less

Submitted 29 June, 2013; originally announced July 2013.

Comments: 31 pages

Exploring the tree of numerical semigroups

Authors: Jean Fromentin, Florent Hivert

Abstract: In this paper we describe an algorithm visiting all numerical semigroups up to a given genus using a well suited representation. The interest of this algorithm is that it fits particularly well the architecture of modern computers allowing very large optimizations: we obtain the number of numerical semigroups of genus g 67 and we confirm the Wilf conjecture for g 60. In this paper we describe an algorithm visiting all numerical semigroups up to a given genus using a well suited representation. The interest of this algorithm is that it fits particularly well the architecture of modern computers allowing very large optimizations: we obtain the number of numerical semigroups of genus g 67 and we confirm the Wilf conjecture for g 60. △ Less

Submitted 14 September, 2015; v1 submitted 16 May, 2013; originally announced May 2013.

Comments: 14 pages

A multivariate "inv" hook formula for forests

Authors: Florent Hivert, Victor Reiner

Abstract: Bjoerner and Wachs provided two q-generalizations of Knuth's hook formula counting linear extensions of forests: one involving the major index statistic, and one involving the inversion number statistic. We prove a multivariate generalization of their inversion number result, motivated by specializations related to the modular invariant theory of finite general linear groups. Bjoerner and Wachs provided two q-generalizations of Knuth's hook formula counting linear extensions of forests: one involving the major index statistic, and one involving the inversion number statistic. We prove a multivariate generalization of their inversion number result, motivated by specializations related to the modular invariant theory of finite general linear groups. △ Less

Submitted 18 July, 2011; originally announced July 2011.

MSC Class: 05A15; 05A10

The biHecke monoid of a finite Coxeter group and its representations

Authors: Florent Hivert, Anne Schilling, Nicolas M. Thiéry

Abstract: For any finite Coxeter group W, we introduce two new objects: its cutting poset and its biHecke monoid. The cutting poset, constructed using a generalization of the notion of blocks in permutation matrices, almost forms a lattice on W. The construction of the biHecke monoid relies on the usual combinatorial model for the 0-Hecke algebra H_0(W), that is, for the symmetric group, the algebra (or mon… ▽ More For any finite Coxeter group W, we introduce two new objects: its cutting poset and its biHecke monoid. The cutting poset, constructed using a generalization of the notion of blocks in permutation matrices, almost forms a lattice on W. The construction of the biHecke monoid relies on the usual combinatorial model for the 0-Hecke algebra H_0(W), that is, for the symmetric group, the algebra (or monoid) generated by the elementary bubble sort operators. The authors previously introduced the Hecke group algebra, constructed as the algebra generated simultaneously by the bubble sort and antisort operators, and described its representation theory. In this paper, we consider instead the monoid generated by these operators. We prove that it admits |W| simple and projective modules. In order to construct the simple modules, we introduce for each w in W a combinatorial module T_w whose support is the interval [1,w]_R in right weak order. This module yields an algebra, whose representation theory generalizes that of the Hecke group algebra, with the combinatorics of descents replaced by that of blocks and of the cutting poset. △ Less

Submitted 9 May, 2013; v1 submitted 6 December, 2010; originally announced December 2010.

Comments: v2: Added complete description of the rank 2 case (Section 7.3) and improved proof of Proposition 7.5. v3: Final version (typo fixes, picture improvements) 66 pages, 9 figures Algebra and Number Theory, 2013. arXiv admin note: text overlap with arXiv:1108.4379 by other authors

MSC Class: 20M30; 20F55 (Primary) 06D75; 16G99; 20C08 (Secondary)

Journal ref: Algebra and Number Theory Vol. 7 (2013), No. 3, 595-671

On the representation theory of finite J-trivial monoids

Authors: Tom Denton, Florent Hivert, Anne Schilling, Nicolas M. Thiéry

Abstract: In 1979, Norton showed that the representation theory of the 0-Hecke algebra admits a rich combinatorial description. Her constructions rely heavily on some triangularity property of the product, but do not use explicitly that the 0-Hecke algebra is a monoid algebra. The thesis of this paper is that considering the general setting of monoids admitting such a triangularity, namely J-trivial monoi… ▽ More In 1979, Norton showed that the representation theory of the 0-Hecke algebra admits a rich combinatorial description. Her constructions rely heavily on some triangularity property of the product, but do not use explicitly that the 0-Hecke algebra is a monoid algebra. The thesis of this paper is that considering the general setting of monoids admitting such a triangularity, namely J-trivial monoids, sheds further light on the topic. This is a step to use representation theory to automatically extract combinatorial structures from (monoid) algebras, often in the form of posets and lattices, both from a theoretical and computational point of view, and with an implementation in Sage. Motivated by ongoing work on related monoids associated to Coxeter systems, and building on well-known results in the semi-group community (such as the description of the simple modules or the radical), we describe how most of the data associated to the representation theory (Cartan matrix, quiver) of the algebra of any J-trivial monoid M can be expressed combinatorially by counting appropriate elements in M itself. As a consequence, this data does not depend on the ground field and can be calculated in O(n^2), if not O(nm), where n=|M| and m is the number of generators. Along the way, we construct a triangular decomposition of the identity into orthogonal idempotents, using the usual Möbius inversion formula in the semi-simple quotient (a lattice), followed by an algorithmic lifting step. Applying our results to the 0-Hecke algebra (in all finite types), we recover previously known results and additionally provide an explicit labeling of the edges of the quiver. We further explore special classes of J-trivial monoids, and in particular monoids of order preserving regressive functions on a poset, generalizing known results on the monoids of nondecreasing parking functions. △ Less

Submitted 4 March, 2011; v1 submitted 17 October, 2010; originally announced October 2010.

Comments: 41 pages; 4 figures; added Section 3.7.4 in version 2; incorporated comments by referee in version 3

MSC Class: 20M30; 16G99; 20C08; 06F05

Journal ref: Seminaire Lotharingien de Combinatoire, B64d (2011), 44 pp

Formal Proof of SCHUR Conjugate Function

Authors: Franck Butelle, Florent Hivert, Micaela Mayero, Frédéric Toumazet

Abstract: The main goal of our work is to formally prove the correctness of the key commands of the SCHUR software, an interactive program for calculating with characters of Lie groups and symmetric functions. The core of the computations relies on enumeration and manipulation of combinatorial structures. As a first "proof of concept", we present a formal proof of the conjugate function, written in C. This… ▽ More The main goal of our work is to formally prove the correctness of the key commands of the SCHUR software, an interactive program for calculating with characters of Lie groups and symmetric functions. The core of the computations relies on enumeration and manipulation of combinatorial structures. As a first "proof of concept", we present a formal proof of the conjugate function, written in C. This function computes the conjugate of an integer partition. To formally prove this program, we use the Frama-C software. It allows us to annotate C functions and to generate proof obligations, which are proved using several automated theorem provers. In this paper, we also draw on methodology, discussing on how to formally prove this kind of program. △ Less

Submitted 28 April, 2010; originally announced April 2010.

Comments: To appear in CALCULEMUS 2010

The biHecke monoid of a finite Coxeter group

Authors: Florent Hivert, Anne Schilling, Nicolas M. Thiéry

Abstract: The usual combinatorial model for the 0-Hecke algebra of the symmetric group is to consider the algebra (or monoid) generated by the bubble sort operators. This construction generalizes to any finite Coxeter group W. The authors previously introduced the Hecke group algebra, constructed as the algebra generated simultaneously by the bubble sort and antisort operators, and described its represent… ▽ More The usual combinatorial model for the 0-Hecke algebra of the symmetric group is to consider the algebra (or monoid) generated by the bubble sort operators. This construction generalizes to any finite Coxeter group W. The authors previously introduced the Hecke group algebra, constructed as the algebra generated simultaneously by the bubble sort and antisort operators, and described its representation theory. In this paper, we consider instead the monoid generated by these operators. We prove that it has |W| simple and projective modules. In order to construct a combinatorial model for the simple modules, we introduce for each w in W a combinatorial module whose support is the interval [1,w] in right weak order. This module yields an algebra, whose representation theory generalizes that of the Hecke group algebra. This involves the introduction of a w-analogue of the combinatorics of descents of W and a generalization to finite Coxeter groups of blocks of permutation matrices. △ Less

Submitted 11 December, 2009; originally announced December 2009.

Comments: 12 pages, 1 figure, submitted to FPSAC'10

MSC Class: 20M30 (Primary); 16G99; 20C08; 06F05 (Secondary)

Journal ref: DMTCS proc AN (2010) 307-318

The (1-E)-transform in combinatorial Hopf algebras

Authors: F. Hivert, J. -G. Luque, J. -C. Novelli, J. -Y. Thibon

Abstract: 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… ▽ More 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. △ Less

Submitted 2 December, 2009; v1 submitted 1 December, 2009; originally announced December 2009.

Comments: 33 pages

Journal ref: J. Algebraic Combin. 33 (2011), 277-312

Deformation of symmetric functions and the rational Steenrod algebra

Authors: Florent Hivert, Nicolas M. Thiéry

Abstract: In 1999, Reg Wood conjectured that the quotient of Q[x_1,...,x_n] by the action of the rational Steenrod algebra is a graded regular representation of the symmetric group S_n. As pointed out by Reg Wood, the analog of this statement is a well known result when the rational Steenrod algebra is replaced by the ring of symmetric functions; actually, much more is known about the structure of the quo… ▽ More In 1999, Reg Wood conjectured that the quotient of Q[x_1,...,x_n] by the action of the rational Steenrod algebra is a graded regular representation of the symmetric group S_n. As pointed out by Reg Wood, the analog of this statement is a well known result when the rational Steenrod algebra is replaced by the ring of symmetric functions; actually, much more is known about the structure of the quotient in this case. We introduce a non-commutative q-deformation of the ring of symmetric functions, which specializes at q=1 to the rational Steenrod algebra. We use this formalism to obtain some partial results. Finally, we describe several conjectures based on an extensive computer exploration. In particular, we extend Reg Wood's conjecture to q formal and to any q complex not of the form -a/b, with a in {1,...,n} and b a positive natural number. △ Less

Submitted 16 December, 2008; originally announced December 2008.

MSC Class: 05E99 (Primary); 55S10 (Secondary)

Journal ref: In Invariant theory in all characteristics, volume 35 of CRM Proc. Lecture Notes, pages 91-125. Amer. Math. Soc. Providence, RI, 2004

Inversion of some series of free quasi-symmetric functions

Authors: Florent Hivert, Jean-Christophe Novelli, Jean-Yves Thibon

Abstract: 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]. 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]. △ Less

Submitted 25 September, 2008; originally announced September 2008.

Comments: 6 pages

Journal ref: European Journal of Combinatorics 31 (2010), 29-33

Noncommutative Symmetric Functions VII: Free Quasi-Symmetric Functions Revisited

Authors: Gerard H. E. Duchamp, Florent Hivert, Jean-Christophe Novelli, Jean-Yves Thibon

Abstract: 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. 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. △ Less

Submitted 26 September, 2008; v1 submitted 25 September, 2008; originally announced September 2008.

Comments: 21 pages, Latex, 2 figures

Journal ref: Annals of Combinatorics 15 (2011), 655-673

Hecke group algebras as quotients of affine Hecke algebras at level 0

Authors: Florent Hivert, Anne Schilling, Nicolas M. Thiéry

Abstract: The Hecke group algebra $HW_0$ of a finite Coxeter group $W_0$, as introduced by the first and last author, is obtained from $W_0$ by gluing appropriately its 0-Hecke algebra and its group algebra. In this paper, we give an equivalent alternative construction in the case when $W_0$ is the classical Weyl group associated to an affine Weyl group $W$. Namely, we prove that, for $q$ not a root of un… ▽ More The Hecke group algebra $HW_0$ of a finite Coxeter group $W_0$, as introduced by the first and last author, is obtained from $W_0$ by gluing appropriately its 0-Hecke algebra and its group algebra. In this paper, we give an equivalent alternative construction in the case when $W_0$ is the classical Weyl group associated to an affine Weyl group $W$. Namely, we prove that, for $q$ not a root of unity, $HW_0$ is the natural quotient of the affine Hecke algebra through its level 0 representation. We further show that the level 0 representation is a calibrated principal series representation for a suitable choice of character, so that the quotient factors (non trivially) through the principal central specialization. This explains in particular the similarities between the representation theory of the classical 0-Hecke algebra and that of the affine Hecke algebra at this specialization. △ Less

Submitted 16 December, 2008; v1 submitted 23 April, 2008; originally announced April 2008.

Comments: 21 pages; 4 figures v2: improved presentation, 23 pages v3: final proofreading, to appear in Journal of Combinatorial Theory Series A

MSC Class: 20C08; 05E15

Journal ref: Journal of Combinatorial Theory, Series A 116 (2009) 844-863

The Hecke group algebra of a Coxeter group and its representation theory

Authors: Florent Hivert, Nicolas M. Thiéry

Abstract: Let W be a finite Coxeter group. We define its Hecke-group algebra by gluing together appropriately its group algebra and its 0-Hecke algebra. We describe in detail this algebra (dimension, several bases, conjectural presentation, combinatorial construction of simple and indecomposable projective modules, Cartan map) and give several alternative equivalent definitions (as symmetry preserving ope… ▽ More Let W be a finite Coxeter group. We define its Hecke-group algebra by gluing together appropriately its group algebra and its 0-Hecke algebra. We describe in detail this algebra (dimension, several bases, conjectural presentation, combinatorial construction of simple and indecomposable projective modules, Cartan map) and give several alternative equivalent definitions (as symmetry preserving operator algebra, as poset algebra, as commutant algebra, ...). In type A, the Hecke-group algebra can be described as the algebra generated simultaneously by the elementary transpositions and the elementary sorting operators acting on permutations. It turns out to be closely related to the monoid algebras of respectively nondecreasing functions and nondecreasing parking functions, the representation theory of which we describe as well. This defines three towers of algebras, and we give explicitly the Grothendieck algebras and coalgebras given respectively by their induction products and their restriction coproducts. This yields some new interpretations of the classical bases of quasi-symmetric and noncommutative symmetric functions as well as some new bases. △ Less

Submitted 20 November, 2008; v1 submitted 9 November, 2007; originally announced November 2007.

Comments: v2: 30 pages, 2 figures, extended proof of Prop. 3.25, update of citations, typo and grammar fixes v3: final version: typos and encoding fixes

MSC Class: 16G99 (Primary) 05E05; 20C08 (Secondary)

Sur une conjecture de Dehornoy

Authors: Florent Hivert, Jean-Christophe Novelli, Jean-Yves Thibon

Abstract: Let M_n be the n! * n! matrix indexed by permutations of S_n, defined by M_n(sigma,tau)=1 if every descent of tau^{-1} is also a descent of sigma, and M_n(sigma,tau)=0 otherwise. We prove the following result, conjectured by P. Dehornoy: the characteristic polynomial P_n(x)=|xI-M_n| of M_n divides P_{n+1}(x) in Z[x]. Let M_n be the n! * n! matrix indexed by permutations of S_n, defined by M_n(sigma,tau)=1 if every descent of tau^{-1} is also a descent of sigma, and M_n(sigma,tau)=0 otherwise. We prove the following result, conjectured by P. Dehornoy: the characteristic polynomial P_n(x)=|xI-M_n| of M_n divides P_{n+1}(x) in Z[x]. △ Less

Submitted 25 October, 2007; originally announced October 2007.

Comments: 4 pages, in French

MSC Class: 20F36; 05A15

Journal ref: C. R. Math. Acad. Sci. Paris 346 (2008), no. 7-8, 375--378

Permutation statistics related to a class of noncommutative symmetric functions and generalizations of the Genocchi numbers

Authors: Florent Hivert, Jean-Christophe Novelli, Lenny Tevlin, Jean-Yves Thibon

Abstract: 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. 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. △ Less

Submitted 2 October, 2007; originally announced October 2007.

Comments: 13 pages

MSC Class: 05E05; 15A15; 16W30

Journal ref: Selecta Math. (N.S.) 15 (2009), no. 1, 105--119

An operational calculus for the Mould operad

Authors: Frédéric Chapoton, Florent Hivert, Jean-Christophe Novelli, Jean-Yves Thibon

Abstract: 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 noncommutati… ▽ More 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. △ Less

Submitted 18 October, 2007; v1 submitted 1 October, 2007; originally announced October 2007.

Comments: 16 pages, one reference added and minor changes in v2

MSC Class: 18D50; 05E

Trees, functional equations, and combinatorial Hopf algebras

Authors: Florent Hivert, Jean-Christophe Novelli, Jean-Yves Thibon

Abstract: 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. 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. △ Less

Submitted 19 January, 2007; originally announced January 2007.

Comments: 14 pages, LaTEX

Journal ref: European J. Combin. 29 (2008), no. 7, 1682--1695

Random patterns generated by random permutations of natural numbers

Authors: G. Oshanin, R. Voituriez, S. Nechaev, O. Vasilyev, F. Hivert

Abstract: We survey recent results on some one- and two-dimensional patterns generated by random permutations of natural numbers. In the first part, we discuss properties of random walks, evolving on a one-dimensional regular lattice in discrete time $n$, whose moves to the right or to the left are induced by the rise-and-descent sequence associated with a given random permutation. We determine exactly th… ▽ More We survey recent results on some one- and two-dimensional patterns generated by random permutations of natural numbers. In the first part, we discuss properties of random walks, evolving on a one-dimensional regular lattice in discrete time $n$, whose moves to the right or to the left are induced by the rise-and-descent sequence associated with a given random permutation. We determine exactly the probability of finding the trajectory of such a permutation-generated random walk at site $X$ at time $n$, obtain the probability measure of different excursions and define the asymptotic distribution of the number of "U-turns" of the trajectories - permutation "peaks" and "through". In the second part, we focus on some statistical properties of surfaces obtained by randomly placing natural numbers $1,2,3, >...,L$ on sites of a 1d or 2d square lattices containing $L$ sites. We calculate the distribution function of the number of local "peaks" - sites the number at which is larger than the numbers appearing at nearest-neighboring sites - and discuss some surprising collective behavior emerging in this model. △ Less

Submitted 27 September, 2006; originally announced September 2006.

Comments: 16 pages, 5 figures; submitted to European Physical Journal, proceedings of the conference "Stochastic and Complex Systems: New Trends and Expectations" Santander, Spain

Representation theories of some towers of algebras related to the symmetric groups and their Hecke algebras

Authors: Florent Hivert, Nicolas M. Thiéry

Abstract: We study the representation theory of three towers of algebras which are related to the symmetric groups and their Hecke algebras. The first one is constructed as the algebras generated simultaneously by the elementary transpositions and the elementary sorting operators acting on permutations. The two others are the monoid algebras of nondecreasing functions and nondecreasing parking functions.… ▽ More We study the representation theory of three towers of algebras which are related to the symmetric groups and their Hecke algebras. The first one is constructed as the algebras generated simultaneously by the elementary transpositions and the elementary sorting operators acting on permutations. The two others are the monoid algebras of nondecreasing functions and nondecreasing parking functions. For these three towers, we describe the structure of simple and indecomposable projective modules, together with the Cartan map. The Grothendieck algebras and coalgebras given respectively by the induction product and the restriction coproduct are also given explicitly. This yields some new interpretations of the classical bases of quasi-symmetric and noncommutative symmetric functions as well as some new bases. △ Less

Submitted 23 August, 2006; v1 submitted 17 July, 2006; originally announced July 2006.

Comments: 12 pages. Presented at FPSAC'06 San-Diego, June 2006 (minor explanation improvements w.r.t. the previous version)

MSC Class: 16G99 (Primary) 05E05 (Secondary)

Commutative combinatorial Hopf algebras

Authors: F. Hivert, J. -C. Novelli, J. -Y. Thibon

Abstract: 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.… ▽ More 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. △ Less

Submitted 10 May, 2006; originally announced May 2006.

Comments: 29 pages, LaTEX; expanded and updated version of math.CO/0502456

Journal ref: J. Algebraic Combin. 28 (2008), no. 1, 65--95

Multivariate generalizations of the Foata-Schutzenberger equidistribution

Authors: F. Hivert, J. -C. Novelli, J. -Y. Thibon

Abstract: 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, an… ▽ More 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. △ Less

Submitted 10 May, 2006; v1 submitted 2 May, 2006; originally announced May 2006.

Comments: 17 pages, LaTex; Minor correction in the proof of Lemma 6.5; one reference added

On the distribution of surface extrema in several one- and two-dimensional random landscapes

Authors: F. Hivert, S. Nechaev, G. Oshanin, O. Vasilyev

Abstract: We study here a standard next-nearest-neighbor (NNN) model of ballistic growth on one- and two-dimensional substrates focusing our analysis on the probability distribution function $P(M,L)$ of the number $M$ of maximal points (i.e., local ``peaks'') of growing surfaces. Our analysis is based on two central results: (i) the proof (presented here) of the fact that uniform one--dimensional ballisti… ▽ More We study here a standard next-nearest-neighbor (NNN) model of ballistic growth on one- and two-dimensional substrates focusing our analysis on the probability distribution function $P(M,L)$ of the number $M$ of maximal points (i.e., local ``peaks'') of growing surfaces. Our analysis is based on two central results: (i) the proof (presented here) of the fact that uniform one--dimensional ballistic growth process in the steady state can be mapped onto ''rise-and-descent'' sequences in the ensemble of random permutation matrices; and (ii) the fact, established in Ref. \cite{ov}, that different characteristics of ``rise-and-descent'' patterns in random permutations can be interpreted in terms of a certain continuous--space Hammersley--type process. For one--dimensional system we compute $P(M,L)$ exactly and also present explicit results for the correlation function characterizing the enveloping surface. For surfaces grown on 2d substrates, we pursue similar approach considering the ensemble of permutation matrices with long--ranged correlations. Determining exactly the first three cumulants of the corresponding distribution function, we define it in the scaling limit using an expansion in the Edgeworth series, and show that it converges to a Gaussian function as $L \to \infty$. △ Less

Submitted 19 May, 2006; v1 submitted 22 September, 2005; originally announced September 2005.

Comments: 25 pages, 12 figures

Yang-Baxter bases of 0-Hecke algebras and representation theory of 0-Ariki-Koike-Shoji algebras

Authors: F. Hivert, J. -C. Novelli, J. -Y. Thibon

Abstract: 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 matri… ▽ More 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. △ Less

Submitted 27 June, 2005; originally announced June 2005.

Comments: 46 pages, LaTEX

Journal ref: Advances in Mathematics 205 (2006), 504-548

Commutative Hopf algebras of permutations and trees

Authors: F. Hivert, J. -C. Novelli, J. -Y. Thibon

Abstract: 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.… ▽ More 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. △ Less

Submitted 22 February, 2005; originally announced February 2005.

Comments: 18 pages, LaTEX

Representation theory of the 0-Ariki-Koike-Shoji algebras

Authors: F. Hivert, J. -C. Novelli, J. -Y. Thibon

Abstract: 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 i… ▽ More 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. △ Less

Submitted 13 July, 2004; originally announced July 2004.

Comments: 12 pages; LaTEX

The Algebra of Binary Search Trees

Authors: F. Hivert, J. -C. Novelli, J. -Y. Thibon

Abstract: 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 Func… ▽ More 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. △ Less

Submitted 15 January, 2004; v1 submitted 9 January, 2004; originally announced January 2004.

Comments: 49 pages

Journal ref: Theoret. Computer Sci., 339 (2005), 129-165

The peak algebra and the Hecke-Clifford algebras at $q=0$

Authors: Nantel Bergeron, Florent Hivert, Jean-Yves Thibon

Abstract: Using the formalism of noncommutative symmetric functions, we derive the basic theory of the peak algebra of symmetric groups and of its graded Hopf dual. Our main result is to provide a representation theoretical interpretation of the peak algebra and its graded dual as Grothendieck rings of the tower of Hecke-Clifford algebras at $q=0$. Using the formalism of noncommutative symmetric functions, we derive the basic theory of the peak algebra of symmetric groups and of its graded Hopf dual. Our main result is to provide a representation theoretical interpretation of the peak algebra and its graded dual as Grothendieck rings of the tower of Hecke-Clifford algebras at $q=0$. △ Less

Submitted 30 October, 2003; v1 submitted 15 April, 2003; originally announced April 2003.

Comments: Final version, 17 pages, LaTex, 1 PDF figure, graphicx

Journal ref: J. Combin. Theory Ser. A 107 (2004), no. 1, 1-19

An analogue of the plactic monoid for binary search trees

Authors: Florent Hivert, Jean-Christophe Novelli, Jean-Yves Thibon

Abstract: 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 leads to a new interpretation of the algebra of planar binary trees of Loday-Ronco. 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 leads to a new interpretation of the algebra of planar binary trees of Loday-Ronco. △ Less

Submitted 24 June, 2002; originally announced June 2002.

Comments: 4 pages, LaTex, French

Noncommutative symmetric functions and quasi-symmetric functions with two and more paramters

Authors: F. Hivert, A. Lascoux, J. -Y. Thibon

Abstract: 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. 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. △ Less

Submitted 22 June, 2001; originally announced June 2001.

Comments: 13 pages, LaTex

Noncommutative symmetric functions VI: Free quasi-symmetric functions and related algebras

Authors: G. Duchamp, F. Hivert, J. -Y. Thibon

Abstract: 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 F… ▽ More 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. △ Less

Submitted 9 May, 2001; originally announced May 2001.

Comments: 46 pages, LaTex, epsf macros

Journal ref: International Journal of Algebra and Computation 12 (2002), 671-717