Nicolas M. THIxRY

Nx le 28 mai 1973 x Paris XV^{e} (38 ans)

Nationalitx Franxaise; dxgagx des obligations militaires

IUT d’Orsay, Plateau de Moulon, 91400 ORSAY

   Mxl: Nicolas.Thiery@u-psud.fr
   Web: http://Nicolas.Thiery.name/

PIC

Synthxse

Doctorat info-maths (1999), habilitation (2008), qualifix 25^{e} et 27^{e} sections, PES Encadrement de thxses: Nicolas Borie et coencadrement de Tom Denton (2008-2011) Publications internationales avec comitx: journaux: 13 (p.x5), actes: 8 (p.x6) Enseignement: 2050 heures en informatique et mathxmatiques (p.x8) Thxmatique de recherche: combinatoire algxbrique et xnumxrative (p.x11) Fondateur, coordinateur et dxveloppeur du projet logiciel Sage-Combinat (p.x12) Mots clefs: structures combinatoires (monoxdes, permutations, graphes, treillis, ...) combinatoire et reprxsentations des algxbres (de Hopf, de Hecke, de Kac, de Steenrod, ...) Points forts: exploration informatique, contacts internationaux, animation d’xquipe Documents joints x ce dossier:

Ce CV suivi d’un projet d’intxgration au LRI (voir p.x10)

Lettres de recommandation (Delaxt, Gouyou-Beauchamps, Pin, Stein, Zimmermann)

Rapports et mxmoire d’HDR; sxlection de publications

xtudes et fonctions

2004-2012x: Maxtre de confxrence (25^{e} section); Institut Universitaire de Technologie d’Orsay, dxpartement d’informatique; Laboratoire de Mathxmatiques d’Orsay, Universitx Paris Sud;

2010x: Prime d’Excellence Scientifique;

2008/2011x: Qualification dans les 25^{e} et 27^{e} sections du CNU;

2008x: Habilitation x diriger des recherches, soutenue le 10 dxcembre x Orsay; Sujet: Algxbre combinatoire et effective: des graphes aux algxbres de Kac via l’exploration informatique; Rapporteurs: Franxois Bergeron, Peter Cameron, Bernard Leclerc; Jury: Jean-Benoxt Bost, Mireille Bousquet-Mxlou, Alain Lascoux (prxsident), Jean-Yves Thibon, Lxonid Vainerman, Paul Zimmermann;

01/2001-08/2004x: Maxtre de confxrence (27^{e} section), Univ. Claude Bernard LyonxI; 2000x: Qualification dans les sections 25, 26 et 27 du CNU; 1999x: Thxse d’informatique et mathxmatiques, soutenue le 15 juin x l’UCBL;

Sujet: Invariants algxbriques de graphes et reconstruction, une xtude expxrimentale; Directeur: Maurice Pouzet; Rapporteurs: Adriano Garsia, William Kocay; Jury: Adrian Bondy, Marc Giusti, Michel Habib, Daniel Krob;

1997x: Agrxgation de mathxmatiques, option informatique (135^{e}); 1996-1999x: Allocataire Moniteur en informatique, UCBL; 1994x: DEA IMA (Informatique et Mathxmatiques Appliquxes) X-ENS;

Filixre: Programmation, Sxmantique et Preuves; 1992-1996x: xlxve x l’xcole Normale Supxrieure, Paris.

Mobilitx

09/2008-02/2009x: Dxlxgation CNRS (27^{e} section) , Institut d’Electronique et d’Informatique Gaspard Monge, Marne-la-vallxe;

2007-2008 puis 02/2009-08/2009x: dix-huit mois Chercheur dxtachx au Dxpartement de Maths de l’Universitx de Californie x Davis (USA, financement NSF);

2006x: Un mois x l’Universitx de Californie x San Diego (USA), avec A.xGarsia;

2004x: Quatre mois Architecte Dxveloppeur Senior au dxpartement Sxcuritx d’IDEALX: gestion de montxe en charge et tests fonctionnels pour IDX-PKI;

1999-2000x: Seize mois Enseignant-chercheur, Coopxrant du Service National, Dxpartment de Maths et Informatique, Colorado School of Mines (USA).

Txches administratives

xlu au Conseil de l’IUT d’Orsay, 2010-2013;

Prxsident comitx de sxlection IUT Orsay, poste PRAG 1257 (anglais, 2011);

Comitxs de sxlection IUT Orsay, postes MCF (info, 2009) et PRAG 1564 (lettres modernes, 2010);

Membre de la prx-commission de recrutement MCF IUT d’Orsay, 2006;

Organisateur des journxes portes ouvertes de l’IUT d’Orsay, 2006 et 2007;

Webmestre et administrateur systxme Laboratoire de Probabilitxs, Combinatoire et Statistiques (UCBL) 1997-2004: installation et gestion de 40 postes (UNIX: GNU/Linux, HP, TX);

Coorganisateur et chercheur rxsident du semestre «Multiple Dirichlet series and related combinatorics», x l’Institute for Computational and Experimental Research in Mathematics, Brown, Rhodes Island, USA, printemps 2013;

Membre du projet NSF «Focused Research Group: Affine Schubert Calculus» 500 k$, 2007-2010;

Coorganisateur du Groupe d’Utilisateurs de Sage en rxgion parisienne

Coorganisateur de neuf rencontres de dxveloppeurs de *-Combinat, en juin 2004 (Rouen), juin (Orsay) et septembre (Banff) 2007, janvier (Orsay) et juillet 2009 (RISC), juin 2010 (Orsay), janvier 2011 (Orsay); janvier 2013 (EPFL), fxvrier 2013 (Brown university)

Coorganisateur des Sage Days 20, mars 2010 (CIRM, 110 participants); Organisateur local du Workshop on Open Source Computer Algebra (Lyon, 21-23 mai 2002): cinquante chercheurs et enseignants de sept pays diffxrents.

Encadrement d’activitxs de recherche

Direction du stage de M2 puis de la thxse de Nicolas Borie (2008-2011); Codirection de la thxse de Tom Denton, University of California at Davis, avec Anne Schilling (2008-2011); Rapporteur et examinateur de la thxse de Mr Rahmany (2009, Univ Paris 6); Examinateur pour les thxses de Xavier Molinero (2005, Barcelone), Franxois Descouens (2007, Univ. Marne-la-Vallxe), Xavier Buchwalder (2009, Univ. Lyon I), Jean-Pierre Flori (2011, Txlecom ParisTech); Coordination de *-Combinat (voir p.x12), incluant l’encadrement des doctorants: Borie, Boussicault, Denton, Descouens, Molinero, Pon, Pons, Wang, etc.

Invitations x des confxrences

xcole d’xtx CIMPA: «Mathxmatiques discrxtes: aspects combinatoires, dynamiques et algorithmiques», Bobo-Dioulasso (Burkina Faso), automne 2012 (mini-cours); Sage Days 40 , IMA, Minneapolis, USA, July 2012; Workshop on Algebraic Monoids, Group Embeddings and Algebraic Combinatorics, July 2012; Sage Days 38, CRM, Montrxal, Canada, May 2012; 4-th SCIEnce Workshop, xcole Polytechnique, Dxcembre 2011; Congrxs SMAI , Mini-symposium Sage, Guidel Mai 2011; Sage Days 30 , Acadia University, Canada, Mai 2011; Affine Schubert Calculus Summer School, Toronto, Canada, Juil. 2010 (mini-cours); Sage Days 20.5 , Fields Institute, Toronto, Canada, Mai 2010; Sage Days 20 , CIRM, Luminy, France, Fxvrier 2010 (mini-cours); Journxe PLUME - Groupe Calcul: «Les alternatives libres aux outils proprixtaires de mathxmatiques», Paris, France, Fxvrier 2010 (confxrence d’introduction); Sage Days 15 , Seattle, USA, Mai 2009; Sage Days 10 , Nancy, France, Octobre 2008, responsable de la session combinatoire; AMS special session on Algebraic Combinatorics, Claremont, USA, Mai 2008; Sage Days 7 , Los Angeles, USA, Fxvrier 2008; AMS Joint Mathematics Meeting, Special Session on Applications of Computer Algebra in Enumerative and Algebraic Combinatorics, San Diego, USA, Janvier 2008; Axiom Workshop 2007 , RISC, Linz, Austria, Juin 2007; Axiom Workshop 2006 , RISC, Linz, Austria, Avril 2006; Modular Invariants and Representations of Finite Groups: Theory and Computation, Canterbury, UK, Septembre 2003; Workshop on Invariant Theory, Kingston, Canada, Avril 2002.

Sxminaires et exposxs rxcents

UC Davis, USA (10/2007, 06/2009); MSRI, Berkeley, USA (04/2008); Orsay (12/2008); LMNO, Caen (01/2009), Tulane, New-Orleans, USA (03/2009); INRIA, Rocquencourt; LIPN, Villetaneuse (11/2009); LIAFA, Paris (02/2010); LACL, Crxteil (06/2010); Aix-la-Chapelle (12/2010); Orsay (01/2011); Rabat, Maroc (02/2011); LRI, Orsay (03/2011), Montrxal, Canada (04/2011); LMNO, Caen (05/2011); Bar Ilan University, Israxl (05/2011); ICJ Lyon (02/2012); LJK, Grenoble (03/2012); JIL, Toulon (04/2012).

Quelques titres rxcents:

«Algorithmes en thxorie des reprxsentations des monoxdes» «Thxorie des reprxsentations effective des monoxdes» «Algxbres et monoxdes de tris des groupes de Coxeter» «Dxveloppement collaboratif libre d’applications mxtier; xtude de cas: Sage pour les Mathxmatiques» «Une introduction x Sage et Sage-Combinat » «Categories for the working mathematical programmer»

Voir aussi: http://Nicolas.Thiery.Name/Talks/.

Langues

Anglais: courant; Allemand: lu-xcrit .

Publications

Note: mes publications sont presque toutes disponibles sur arXiv:

http://arxiv.org/find/all/1/au:+Thiery_N/0/1/0/all/0/1 et rxfxrencxes sur HAL:
http://hal.archives-ouvertes.fr/aut/Nicolas+M.+Thi%C3%A9ry/

Revues d’audience internationale avec comitx de lecture

[1]xxx Florent Hivert, Anne Schilling, and NicolasxM. Thixry. The biHecke monoid of a Coxeter group and its representation theory. Algebra and Number Theory, January 2012. 64 pages, arXiv:1012.1361 [math.CO].

[2]xxx Tom Denton, Florent Hivert, Anne Schilling, and NicolasxM. Thixry. On the representation theory of finite J-trivial monoids. Sxm. Lothar. Combin., 64:Art. B64d, 44, 2010/11. 40 pages, arXiv:1010.3455 [math.RT].

[3]xxx Marie-Claude David and NicolasxM. Thixry. Exploration of finite-dimensional Kac algebras and lattices of intermediate subfactors of irreducible inclusions. J.

Algebra  Appl.,  10(5):995–1106,  2011.

http://dx.doi.org/10.1142/S0219498811005099. arXiv:0812.3044 [math.QA].

[4]xxx Jason Bandlow, Anne Schilling, and NicolasxM. Thixry. On the uniqueness of promotion operators on tensor products of type A crystals. J. Algebraic

Combin., 31(2):217–251, 2010. http://dx.doi.org/10.1007/s10801-009-0182-3.

arXiv:0806.3131 [math.CO].

[5]xxx Florent Hivert, Anne Schilling, and NicolasxM. Thixry. Hecke group algebras as quotients of affine Hecke algebras at level 0. J. Combin. Theory Ser. A, 116(4):844–863, 2009. arXiv:0804.3781v3 [math.RT].

[6]xxx Florent Hivert and NicolasxM. Thixry. The Hecke group algebra of a Coxeter group and its representation theory. J. Algebra, 321(8):2230–2258, 2009. arXiv:0711.1561 [math.RT].

[7]xxx Pierrick Gaudry, xric Schost, and NicolasxM. Thixry. Evaluation properties of symmetric polynomials. Internat. J. Algebra Comput., 16(3):505–523, 2006. http://hal.inria.fr/inria-00000629.

[8]xxx Florent Hivert and NicolasxM. Thixry. MuPAD-Combinat, an open-source package for research in algebraic combinatorics. Sxm. Lothar. Combin., 51:Art. B51z, 70 pp.

(electronic), 2004. http://igd.univ-lyon1.fr/~slc/wpapers/s51thiery.html.
http://mupad-combinat.sf.net/.

[9]xxx Jean-Christophe Novelli, Jean-Yves Thibon, and NicolasxM. Thixry. Algxbres de Hopf de graphes. C. R. Math. Acad. Sci. Paris, 339(9):607–610, 2004. doi:10.1016/j.crma.2004.09.012, arXiv:0812.3407v1 [math.CO].

[10]xxx NicolasxM. Thixry and Stxphan Thomassx. Convex cones and SAGBI bases of permutation invariants. In Invariant theory in all characteristics, volumex35 of CRM Proc. Lecture Notes, pages 259–263. Amer. Math. Soc., Providence, RI, 2004. arXiv:0607380 [math.AC].

[11]xxx Florent Hivert and NicolasxM. Thixry. Deformation of symmetric functions and the rational Steenrod algebra. In Invariant theory in all characteristics, volumex35 of CRM Proc. Lecture Notes, pages 91–125. Amer. Math. Soc., Providence, RI, 2004. arXiv:0812.3056v1 [math.CO].

[12]xxx Maurice Pouzet and NicolasxM. Thixry. Invariants algxbriques de graphes et reconstruction. C. R. Acad. Sci. Paris Sxr. I Math., 333(9):821–826, 2001. arXiv:0812.3079v1 [math.CO].

[13]xxx NicolasxM. Thixry. Algebraic invariants of graphs: a study based on computer exploration. SIGSAM Bulletin (ACM Special Interest Group on Symbolic and Algebraic Manipulation), 34(3):9–20, September 2000. arXiv:0812.3082v1 [math.CO].

Actes de confxrences internationales avec comitx de lecture

[1]xxx NicolasxM. Thixry. Cartan invariant matrices for finite monoids: description and computation using characters. FPSAC’13, 12 pages; long version in preparation, December 2011.

[2]xxx Nicolas Borie and NicolasxM. Thixry. An evaluation approach to computing invariants rings of permutation groups. In MEGA 2011, Mai 2011. 8 pages.

[3]xxx Franxois Bergeron, Nicolas Borie, and NicolasxM. Thixry. Deformed diagonal harmonic polynomials for complex reflection groups. DMTCS Proceedings, 0(01), 2011.

http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAO0113.

FPSAC’11, arXiv:1011.3654 [math.CO].

[4]xxx Florent Hivert, Anne Schilling, and NicolasxM. Thixry. The biHecke monoid of a finite Coxeter group. DMTCS proc., AN(01):307–318, 2010.

http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAN0116.

arXiv:0912.2212 [math.CO].

[5]xxx Florent Hivert, Anne Schilling, and NicolasxM. Thixry. Hecke group algebras as degenerate affine Hecke algebras. In 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), pages 611–624, September 2008.

http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAJ0153.

[6]xxx Florent Hivert and NicolasxM. Thixry. Representation theories of some towers of algebras related to the symmetric groups and their Hecke algebras. In Proceedings of FPSAC’06 San Diego, 2006. arXiv:0607391v2 [math.RT].

[7]xxx Maurice Pouzet and NicolasxM. Thixry. Some relational structures with polynomial growth and their associated algebras. In Proceedings of FPSAC’05 Taormina, 2005. arXiv:0601256 [math.CO].

[8]xxx NicolasxM. Thixry. Computing minimal generating sets of invariant rings of permutation groups with SAGBI-Grxbner basis. In Discrete models: combinatorics, computation, and geometry (Paris, 2001), Discrete Math. Theor. Comput. Sci. Proc., AA, pages 315–328 (electronic). Maison Inform. Math. Discrxt., Paris, 2001.

http://www.dmtcs.org/pdfpapers/dmAA0123.pdf.

Articles soumis [1]xxx Nicolas Borie and NicolasxM. Thixry. An evaluation approach to computing

invariants rings of permutation groups. Submitted, 18 pages, arXiv:1110.3849v1 [math.CO], October 2011.

[2]xxx Maurice Pouzet and NicolasxM. Thixry. Some relational structures with polynomial growth and their associated algebras I: Quasi-polynomiality of the profile. 2012. Submitted, 30 pages.

Thxse de doctorat et d’habilitation, chapitre de livre

[1]xxx Alexandre Casamayou, Nathann Cohen, Guillaume Connan, Thierry Dumont, Laurent Fousse, Franxois Maltey, Matthias Meulien, Marc Mezzarobba, Clxment Pernet, NicolasxM. Thixry, and Paul Zimmermann. Calcul Mathxmatique avec Sage.

2011. http://sagebook.gforge.inria.fr/. 415 pages.

[2]xxx NicolasxM. Thixry. Algxbre Combinatoire et Effective; des graphes aux algxbres de Kac via l’exploration informatique. Mxmoire d’Habilitation x Diriger des Recherches, December 2008. Laboratoire de Mathxmatiques d’Orsay, Universitx Paris Sud, arXiv:0912.2619v1 [math.CO].

[3]xxx NicolasxM. Thixry. Invariants algxbriques de graphes et reconstruction; une xtude

expxrimentale.  PhD  thesis,  Universitx  LyonxI,  June

1999. http://nicolas.thiery.name/Preprints/Thiery.IAGR/Thiery.IAGR.pdf.

300 pages, N^{∘} d’ordre: 167-99.

Communications

[1]xxx NicolasxM. Thixry. Sage-combinat, free and practical software for algebraic combinatorics. Software demonstration, FPSAC’09, Hagenberg, Austria, 2009.

http://wiki.sagemath.org/combinat?action=AttachFile&do=get&target=2009-07-20-FPSAC.pdf.

[2]xxx Conrado Martxnez, Xavier Molinero, and NicolasxM. Thixry. Generacix ordenada de classes d’estructures combinatxries (ordered generation of combinatorial structures). In In Jornada de Recerca EPSEM 2006, pages 83–84. EPSEM (Technical College of Manresa <http://www.eupm.upc.es/>), Remsa S.L. Manresa, April 2006.

http://www.epsem.upc.edu/recerca/jornada-de-recerca-epsem-20-d-abril-de-2006/DossierJornadadeRecerca.pdf.

ISBN: 84-86784-05-0. ISBN: 978-84-86784-05-8.

[3]xxx NicolasxM. Thixry. PerMuVAR, a library for computing in invariant rings of permutation groups. Software demonstration, MEGA 2000, Bath, UK, 2000.

http://permuvar.sourceforge.net/.

[4]xxx NicolasxM. Thixry. Algebraic invariants of graphs; an experimental study. Poster, ISSAC’99, Vancouver, CANADA, 1999. Awarded best poster prize.

Enseignement (≈2050 heures xquiv. TD depuis 1996)

Mon cœur de mxtier a xtx jusqu’ici l’enseignement des mathxmatiques aux xtudiants informaticiens (mathxmatiques discrxtes, algxbre, etc.) et rxciproquement de l’informatique (programmation, algorithmique, systxme, etc.) aux mathxmaticiens. Mon but est d’exploiter ma double culture pour faire dxcouvrir et, autant que possible, aimer l’autre domaine aux xtudiants de tous niveaux, afin de les inciter x franchir les frontixres disciplinaires. Je prxfxre des enseignements ox je peux utiliser mes compxtences en recherche et en dxveloppement logiciel (combinatoire, calcul formel et algxbrique, informatique thxorique, conception logicielle, gestion de projet), et j’apprxcie l’interaction avec des xtudiants en master ou en thxse. Mais je me suis toujours adaptx aux besoins locaux, en prenant plaisir x xlargir mon spectre de compxtences en enseignant de nouvelles matixres.

Informatique

L1: C++ (TP, 20h, 2003, Filixre Ingxnieur 2000, Universitx de Marne-la-Vallxe), TP d’Informatique (Turbo-Pascal) (32h, 1996, MIAS),

L2: Programmation Objet en Java (Cours, TD, TP, 4×50h), Algo et Langage C++ (TD, TP), Programming concepts, in C++ (Cours, TP, 50h). Combinatoire (TD, 52h, 1998-1999).

L3: Optimisation discrxte (TD, 2×27h), Stage d’initiation x Maple (16h, 1997, ENS Lyon),

M1: Recherche opxrationnelle (Cours, TD, TP, 3×80h, Maxtrise de Maths et Ingxnierie Mathxmatique, 2001-2004);

M2: Montage et responsabilitx de la thxmatique informatique du DESS Statistiques, Informatique et Techniques Numxriques: Programmation Java et outils de dxveloppement, Systxmes et rxseaux informatiques, Remise x niveau informatique fondamentale (Cours, TD, TP, 3×90h).

Intervenant chez Orsys: Linux, Mise en Œuvre (3×4 jours, 2005-2006).

Sage Days: Python, Sage, Programmation objet, Gxnie logiciel, Tests, Systxmes de gestion de version (CVS, Subversion, Mercurial) (30h).

Mathxmatiques

L1: Mathxmatiques gxnxrales (Amphi, TP, TD, 3×100h), Calcul formel pour les Mathxmatiques (Amphi, TP, 10h),

Mathxmatiques gxnxrales, algxbre, combinatoire (100h, 1996-1998); L2: Algxbre, statistiques, graphes, codage (Cours, TD, 3×130h, 2004-2007),

Recherche Opxrationnelle (Cours, TD, 30h, 1999), Algebraic structures and discrete mathematics (Cours, TD, 3×50h, 1999-2000);

L3: Stage d’initiation x Maple (16h, 1997, ENS Lyon); M1: Montage et responsabilitx de l’option Algxbre et Calcul Formel de la prxparation

x l’agrxgation d’Orsay (2×50h, 2005-2007); Participation aux oraux blancs du CAPES (1999);

Doctorat: Cours informels de combinatoire (20h, 2007-2009).

Divers

Projet Professionnel Personnalisx; Encadrement de sept projets tutorxs, L1, IUT d’Orsay; Encadrement de quatre TER (Orsay, Lyon); x

Projet d’intxgration au LRI, Orsay

Enseignement et administration x titre d’illustration, je donne ci-dessous une liste de modules des cursus du dxpartement d’informatique d’Orsay dans lesquels je pourrais invervenir. Je souhaite en outre proposer au moins un cours de M2 sur mes thxmes de recherche, x Orsay ou dans les xtablissements environnants, afin de recruter de futurs xtudiants.

Comme chaque fois que l’occasion s’est prxsentxe dans mes postes prxcxdents, je m’investirai dans l’xlaboration des contenus et le renouvellement des filixres. Selon les besoins, je suis prxt x prendre en charge des responsabilitxs administratives, d’organisation des enseignements ou autres, tout en maintenant un xquilibre entre recherche propre, animation de l’xquipe de recherche, animation de Sage-Combinat, enseignement, charges administratives et ... vie familiale.

Quelques modules dans lesquels je serais directement opxrationnel en CM/TD/TP: L:

Introduction x la programmation objet

Mathxmatiques pour l’informatique, Maths discrxtes, Algxbre, Algxbre linxaire M1:

Algorithmique de graphes

Quelques modules dans lesquels je serais directement opxrationnel en TD/TP. Par la suite, je pourrais donner les cours dans ces matixres, une fois intxgrx l’esprit du module, le niveau et les centres d’intxrxts des xtudiants, les difficultxs pxdagogiques: L:

Programmation objet et gxnie logiciel, Gxnie logiciel avancx, Dxveloppement logiciel

Programmation fonctionelle, Programmation impxrative, Algorithmique gxnxrale

Principes d’interprxtation des langages, Langages formels et analyse syntaxique

xlxments de logique pour l’informatique M1:

Programmation objet avancxe, Algorithmique avancxe, Compilation

Informatique thxorique M2Pro RT:

PhyI-G20 - Java et internet

Quelques modules dans lesquels je pourrais intervenir en TD/TP avec un peu d’investissement et que j’aurais plaisir x enseigner pour ma propre culture: L:xxx Composants logiques et architectures des ordinateurs, bases de donnxes M1: Informatique thxorique avancxe, complexitx M2 Pro IICI: Reprxsentation des connaissances

Thxmatique et projet de recherche

Mon domaine de recherche est la combinatoire algxbrique. Il se situe x l’interface entre l’algorithmique, la combinatoire xnumxrative et l’xtude des structures combinatoires sous-jacentes au calcul algxbrique avec, en particulier, des applications x l’analyse fine de complexitx d’algorithmes et de langages via les sxries gxnxratrices. D’une part, j’utilise des outils d’algxbre commutative, notamment de thxorie des invariants, pour xtudier des problxmes d’isomorphisme en combinatoire (reconstruction de graphes, etc.). D’autre part, je recherche et xtudie des modxles combinatoires pour des structures algxbriques et leurs reprxsentations: monoxdes finis, cristaux, algxbres de Hopf et de Kac, algxbres de Steenrod. D’un cxtx, ces modxles permettent de calculer concrxtement avec ses structures. De l’autre, le point de vue conceptuel introduit par l’algxbre fournit un guide prxcieux.

Reprxsentations des monoxdes Je dxtaille maintenant mon projet de recherche principal, que je mxne depuis 2004 en y associant collaborateurs et xtudiantsx[6,x6,x5,x5,x4,x2,x1]. Ce projet tire ses racines dans l’analyse de complexitx des algorithmes de tris. Une structure algxbrique naturellement associxe est le monoxde de Hecke du groupe symxtrique

𝔖_{n} 1 ^{1. En fait le cadre naturel, un peu plus gxnxral, est celui des groupes de Coxeter finis} et son algxbre, appelxe la 0-algxbre de Hecke; il suffit pour le construire de considxrer le permutohxdre comme un automate sur l’alphabet {1, x, n − 1}, et d’en prendre le monoxde de transition. (voir Figurex1).

L’idxe de dxpart a xtx de considxrer des mxlanges de plusieurs types d’opxrateurs de tris (tri croissant et dxcroissant, tri circulaire, etc), et d’xtudier la structure du monoxde engendrx par ces opxrateurs. Par exemple, le monoxde de biHecke est le monoxde engendrx simultanxment par les opxrateurs de tris croissants et dxcroissants; une construction xquivalente consiste x interprxter le permutohxdre comme un automate (avec une orientation approprixe: {1, x, n − 1} pour les flxches descendantes et {1, x, n − 1} sur les flxches montantes, voir Figurex1), et d’en xtudier le monoxde de transition.

Il se trouve que ces mxlanges produisent une combinatoire richex[6,x6,x5,x5], en particulier grxce x des connections avec, par exemple, l’algxbre de Hecke affine ou la combinatoire des polynxmes multivarixs.

Progressivement, la thxorie des monoxdes finis a pris un rxle prxpondxrant dans ce projet. J’ai en effet montrx que, pour une classe large de monoxdes (monoxdes J-triviaux), la thxorie des reprxsentations est complxtement combinatoirex[2]. Cela donne des algorithmes efficaces pour la calculer et, surtout, permet d’associer semi-automatiquement de nouvelles structures combinatoires x un monoxde, le plus souvent sous forme d’ordres partiels ou de treillis. J’ai ainsi mis x jour une nouvelle structure de semi-treillis distributif sur les permutationsx[4,x1].

Ces travaux s’insxrent dans un xlan international relativement rxcent qui a pour but de mieux comprendre les reprxsentations des monoxdes finis (voir par exemplex[?,x?,x?,x?,x?,x?]).

En effet, autant la thxorie des groupes est bien dxveloppx depuis un sixcle, en tout cas dans le cas non modulaire, autant jusqu’x il y a une dizaine d’annxe, seuls les premiers xlxments de la thxorie xtaient connus pour les monoxdes: modules simples et caractxres (voir e.g.x[?,x?]. Les progrxs rapides rxcents sont consubstantiels x la convergence de deux communautxs: celle des semigroupes d’une part et celle de la combinatoire algxbrique d’autre part, qui apportent des exemples, des points de vue et des outils complxmentaires.

Jusqu’x prxsent un verrou xtait la classe des monoxdes apxriodiques; introduits par Schxtzenberger, ces monoxdes sont en correspondance avec les langages rationnels sans xtoile. Mes rxsultats sur les monoxdes de biHecke semblent avoir ouvert une brxche; dans l’xtat actuel j’ai montrx comment exploiter les proprixtxs bien connues du graphe de Cayley du monoxde et des relations de Green (voir Figurex2) pour ramener le calcul des reprxsentations (en l’occurence la matrice des invariants de Cartan) d’un monoxde apxriodique quelconque au calcul de caractxres de petits modulesx[1]. La chute de complexitx induite m’a permis par exemple de traiter en une heure un monoxde de taille 31103, alors que jusqu’ici le traitement de monoxdes similaires de taille 500 pouvait prendre des semaines. Une fois ce verrou dxpassx, la gxnxralisation x tous les monoxdes finis ne pose plus de difficultx majeure. L’idxe est qu’un monoxde quelconque est, en gros traits, composx d’un monoxde apxriodique dans lequel on a injectx des petits groupes. Or plusieurs chercheurs ont dxveloppx rxcemment une batterie d’outils pour rxduire la description des reprxsentations d’un monoxde dont la composante apxriodique ne pose pas de problxme x celle de ses petits groupesx[?,x?]. Suite x une correspondance rxgulixre avec B. Steinberg au Canada et S. Margolis en Israxl, et une visite chez ce dernier, j’ai pu combiner les deux approches. Il ne reste qu’x l’implanter.

x partir de lx, les pistes sont multiples. D’une part, cet outil de calcul va permettre d’xtudier systxmatiquement des familles classiques de monoxdes, apxriodiques ou non, de taille intxressante. Outre l’intxrxt propre de ces monoxdes, j’espxre en retour que cette xtude permettra d’affiner la thxorie pour passer d’un algorithme x une description combinatoire, au moins pour les monoxdes classiques. Une xtape ultxrieure, pour le moment difficile mxme pour des exemples trxs connus, est de dxterminer la filtration radicale qui donne un q-analogue naturel de la matrice de Cartan. Un autre problxme rxcurrent est la gxnxralisation aux monoxdes discrets infinis qui nxcessitera l’introduction d’une nouvelle gamme d’outils. Enfin une question centrale est de dxterminer ce que l’information ainsi extraite sur la structure d’un monoxde dit en retour sur son langage et l’automate associx.

Dxveloppement logiciel libre: MuPAD-Combinat et Sage-Combinat

Depuis son introduction par Schxtzenberger dans les annxes 1950, l’exploration informatique a traditionnellement joux un rxle considxrable dans la recherche en combinatoire, en particulier en combinatoire algxbrique. Des efforts considxrables de dxveloppement ont xtx consentis, rxsultant en de multiples bibliothxques, comme ACE, Algolib, SYMMETRICA ou SF/Weyl/posets. Cependant, mes besoins de calcul lors de ma thxse m’ont amenx x poser le diagnostic suivant: ma communautx a besoin d’un projet logiciel fxdxrateur mutualisant les efforts de dxveloppement, un peu comme GAP le fait pour la thxorie des groupes. Pour qu’il puisse xmerger, ce projet doit xtre simultanxment totalement libre, ancrx sur la recherche, dxveloppx par une communautx internationale transversalement aux institutions et utiliser des outils de conception et de dxveloppement modernes. Enfin il doit xtre intxgrx dans une plateforme de calcul mathxmatique gxnxraliste rxutilisant un maximum de composants prxexistants.

C’est un projet ambitieux et de long terme, mais rxalisable de front avec une carrixre de chercheur. Aprxs de multiples discussions avec les acteurs de la communautx, j’ai commencx x rxunir en dxcembre 2000 une xquipe, en commenxant par Florent Hivert. En l’absence d’une plateforme libre approprixe nous avons dx dans un premier temps nous contenter de MuPAD. Cet obstacle a xtx levx avec l’apparition et la montxe de puissance de Sagex[?]. Grxce x notre migration vers cette plateforme en 2008, notre communautx croxt rapidement. x l’heure actuelle, l’utilisation de MuPAD-Combinat puis Sage-Combinat a joux un rxle essentiel dans plus de 70 publications. Avec 50 contributeurs, 15 dxveloppeurs rxguliers et 150k lignes de code intxgrxes x Sage, ainsi que des financements rxguliers (ANR, PEPS, NSF, voire Google), Sage-Combinat est maintenant la plus grande sous-communautx organisxe de Sage. Elle couvre un large spectre: combinatoire des mots, dynamique, combinatoire xnumxrative, ordres partiels, monoxdes, algxbres de Hopf, algxbres de Lie, cristaux, thxorie des reprxsentations, avec un impact gxnxral sur

Sage:

«I certainly did not realise when the combinat people joined Sage how useful they and what they do would be for people like me!» John Cremona, number theorist.

Mon rxle est multiple: choix de la plateforme et du modxle de dxveloppement, animation de la communautx (formation, ateliers), aide x la conception (algorithmique, modxlisation, architecture logicielle), veille sur la qualitx (tests, documentation, revues de code), dxveloppement d’une vision globale, veille technologique, promotion, recherche de financements et valorisation. Enfin, je me dois d’insuffler une dynamique, en xtant en permanence en premixre ligne, tout en rentabilisant mes propres dxveloppements dans des projets de recherche. Mon mxmoire d’habilitation dxcrit quelques uns des dxfis rencontrxs et les choix stratxgiques qui ont conditionnx la rxussite de ce projet.

Au delx d’un rxle d’animation et d’ingxnierie, je suis amenx x dxvelopper de nouveaux concepts et patrons de conception informatiques pour modxliser des objets mathxmatiques complexes. J’ai en particulier menx x bien une refonte en profondeur du cœur de Sage avec une implantation novatrice fusionnant et xtendant deux patrons de conception «Catxgories» (venant d’Axiom) et «Parents-xlxments» (venant de Magma). L’enjeu pratique est de maxtriser l’explosion combinatoire de la hixrarchie de classes (une centaine de classes abstraites, avec de multiples combinaisons possibles) par une gestion dynamique et de l’algorithmique des treillis. Il s’agit de fait d’un travail de recherche en conception logicielle, avec une publication en cours de prxparation.

Au final, ma contribution x Sage depuis 2008 est de 93 «tickets» (i.e. xvolutions ou correctifs, comme par exemple «#7004: Refactor the graph layout code, and add interface with graphviz») reprxsentant 100 000 lignes de code/doc/tests; j’ai en outre xtx arbitre de 89 «tickets» (voir http://trac.sagemath.org/) Cet investissement s’est concrxtisx par de multiples invitations x des confxrences (p.x4), la participation en tant qu’expert x plusieurs projets de recherche, des prxsentations logicielles rxgulixres (dont FPSAC 2006 et 2009), un article au Sxminaire Lotharingien de Combinatoire (p.x5) et deux chapitres dans un livre (p.x7).

Perspectives Le projet de recherche que j’ai prxsentx prxcxdemment autour de la thxorie des reprxsentations des monoxdes contient x lui seul matixre pour plusieurs sujets de thxse. Mais ce n’est que l’une des facettes de mon travail. Depuis le dxbut de ma carrixre, j’ai en effet travaillx sur des sujets aussi varixs que la thxorie des graphes et des relationsx[3,x13,x12,x7], le calcul formel pour la cryptographiex[7], la thxorie des invariants effectivex[8,x3,x10], les algxbres de Hopf et de Kacx[11,x9,x3], ou les graphes cristallinsx[4]. L’unitx entre ces diffxrents sujets provient des outils utilisxs et, en particulier, de la dxmarche exploratoire. Comme je l’explique en dxtail dans l’introduction de mon mxmoire d’habilitation, cette dxmarche exploratoire est un formidable outil pour xtablir des collaborations, en s’appuyant sur les liens naturels et profonds qu’entretient la combinatoire algxbrique avec les domaines environnants, en informatique, en mathxmatique, comme en physique.

Conjugux avec ma mobilitx (Colorado, Lyon, Marne-la-vallxe, Orsay, Californie) et mon engagement dans le dxveloppement de Sage-Combinat, cela m’a permis d’xtablir un rxseau national et international de collaborateurs. Ce rxseau est une source permanente de nouvelles idxes, de problxmes intxressants, mais aussi de rencontres avec de jeunes talents. En particulier le projet Sage-Combinat fournit un vivier de futurs candidats, testxs sur le terrain pour leur double compxtence pratique et thxorique, leur qualitxs humaines dans un environnement collaboratif et surtout, ce qui est vital pour eux, leur capacitx x valoriser immxdiatement leurs efforts de dxveloppements dans leur recherche (voir mon mxmoire d’habilitation pour la politique trxs stricte de Sage-Combinat x ce sujet). Par exemple, c’est grxce x ce rxseau que l’xquipe Algorithmique et Complexitx a rexu les excellentes candidatures CR de Nathann Cohen et Christian Stump cet annxe.

Mon insertion au LRI est immxdiate, avec la prxsence dans cette xquipe de mon principal collaborateur Florent Hivert. De fait, cette insertion est dxjx effective, mais non pxrenne. L’xmergence d’un noyau dur de dxveloppeurs de Sage-Combinat x Orsay, et plus gxnxralement sur le plateau de Saclay (Supxlec, X), sera structurante pour ce projet et l’occasion de collaborations avec d’autres xquipes du LRI. Sage-Combinat a par exemple dxjx xtx utilisx par l’xquipe ForTesSE lors des thxses de Sandrine Gouraud et Johan Oudinet. Rxciproquement le dxvelopement collaboratif d’un systxme de cette complexitx soulxve de nombreux dxfis: quelles stratxgies de tests appliquer? peut-on prouver certains composants? Enfin il est vital sur le long terme pour Sage de renforcer ses capacitxs en parallxlisme, notamment en continuant d’intxgrer des bibliothxques de calcul haute performance.

Pour conclure, je suis convaincu que ma dxmarche de recherche, mon rxseau international de collaborateurs, mon expxrience d’animation d’xquipe et mon investissement dans Sage-Combinat sont autant d’atouts pour soutenir et viabiliser la montxe en puissance progressive d’une thxmatique de recherche combinatoire algxbrique effective au sein de l’xquipe Algorithmique et Complexitx.

Rxfxrences

[BBBS10]xxx Chris Berg, Nantel Bergeron, Sandeep Bhargava, and Franco Saliola. Primitive orthogonal idempotents for R-trivial monoids. 2010. preprint arXiv:1009.4943.

[BST10] xxx Jason Bandlow, Anne Schilling, and NicolasxM. Thixry. On the uniqueness of promotion operators on tensor products of type A crystals. J. Algebraic Combin., 31(2):217–251, 2010. arXiv:0806.3131 [math.CO].

[Den10] xxx Tom Denton. A combinatorial formula for orthogonal idempotents in the 0-Hecke algebra of S_{N}. DMTCS proc., AN(01):701–712, 2010.

[DHST11]xxx Tom Denton, Florent Hivert, Anne Schilling, and NicolasxM. Thixry. On the representation theory of finite J-trivial monoids. Sxm. Lothar. Combin., 64:Art. B64d, 44, 2010/11. 40 pages, arXiv:1010.3455 [math.RT].

[DT11] xxx Marie-Claude David and NicolasxM. Thixry. Exploration of finite-dimensional Kac algebras and lattices of intermediate subfactors of irreducible inclusions. J. Algebra Appl., 10(5):995–1106, 2011. arXiv:0812.3044 [math.QA].

[GMS09] xxx Olexandr Ganyushkin, Volodymyr Mazorchuk, and Benjamin Steinberg. On the irreducible representations of a finite semigroup. Proc. Amer. Math. Soc., 137(11):3585–3592, 2009.

[GST06] xxx Pierrick Gaudry, xric Schost, and NicolasxM. Thixry. Evaluation properties of symmetric polynomials. Internat. J. Algebra Comput., 16(3):505–523, 2006. http://hal.inria.fr/inria-00000629.

[HST08] xxx Florent Hivert, Anne Schilling, and NicolasxM. Thixry. Hecke group algebras as degenerate affine Hecke algebras. In 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), pages 611–624, September 2008.

[HST09] xxx Florent Hivert, Anne Schilling, and NicolasxM. Thixry. Hecke group algebras as quotients of affine Hecke algebras at level 0. J. Combin. Theory

Ser. A, 116(4):844–863, 2009. arXiv:0804.3781v3 [math.RT].

[HST10] xxx Florent Hivert, Anne Schilling, and NicolasxM. Thixry. The biHecke monoid of a finite Coxeter group. DMTCS proc., AN(01):307–318, 2010. arXiv:0912.2212 [math.CO].

[HST12] xxx Florent Hivert, Anne Schilling, and NicolasxM. Thixry. The biHecke monoid of a Coxeter group and its representation theory. Algebra and Number Theory, January 2012. 64 pages, arXiv:1012.1361 [math.CO].

[HT04] xxx Florent Hivert and NicolasxM. Thixry. Deformation of symmetric functions and the rational Steenrod algebra. In Invariant theory in all characteristics, volumex35 of CRM Proc. Lecture Notes, pages 91–125. Amer. Math. Soc., Providence, RI, 2004. arXiv:0812.3056v1 [math.CO].

[HT06] xxx Florent Hivert and NicolasxM. Thixry. Representation theories of some towers of algebras related to the symmetric groups and their Hecke algebras. In Proceedings of FPSAC’06 San Diego, 2006. arXiv:0607391v2 [math.RT].

[HT09] xxx Florent Hivert and NicolasxM. Thixry. The Hecke group algebra of a Coxeter group and its representation theory. J. Algebra, 321(8):2230–2258, 2009. arXiv:0711.1561 [math.RT].

[McA72] xxx D.xB. McAlister. Characters of finite semigroups. J. Algebra, 22:183–200, 1972.

[MS11] xx