Home – Research – Teaching

Title

Combinatoire algébrique des arbres (in french)

Key words and phrases

Combinatorics; Algorithmics; Tree; Hopf algebra; Operad; fFee quasi-symmetric function; Tamari lattice; Robinson-Schensted correspondence; Polynomial realization.

Abstract

This thesis comes within the scope of algebraic combinatorics and deals with the construction of several combinatorial and algebraic structures on different tree species.

After defining an analogue of the plactic monoid whose equivalence classes are indexed by pairs of twin binary trees, we propose in this context an analogue of the Robinson-Schensted correspondence. From this monoid, we construct a Hopf subalgebra of the Hopf algebra of free quasi-symmetric functions whose bases are indexed by pairs of twin binary trees.

Then, we propose a combinatorial functor from the category of monoids to the category of set-operads. Using this functor, we construct several operads that involve various combinatorial objects. Through a construction that brings a noncommutative Hopf algebra from an operad, we obtain from one of the operads obtained by our construction, a Hopf algebra based on ordered forests of planar rooted trees. We propose a polynomial realization of the latter.

Finally, we establish some properties satisfied by balanced binary trees in the Tamari lattice. We show that the set of balanced binary trees is closed by interval and that the intervals of balanced binary trees have the shape of hypercubes. To enumerate these intervals, we introduce a new kind of tree grammars, namely the synchronous grammars. They allow to obtain a fixed-point functional equation for the generating series of the generated trees.

Jury

Defense

Combinatoire algébrique des arbres (in french)

At 11:00 on December 8, 2011
Room 4B05R (seminar room of LIGM)
At université Paris-Est Marne-la-Vallée, in France