L'anneau des polynômes en n variables est souvent vu de façon récursive comme l'anneau des polynômes en 1 variable à coefficients dans les polynômes à n-1 variables. Nous montrons une approche différente qui étudie l'anneau comme une somme linéaire de vecteurs d'entiers de taille n : les exposants des monômes. A partir d'opérations simples sur les vecteurs, on obtient des actions sur les polynômes. Nous définissons des opérations de différences divisées à partir desquelles nous obtenons des bases linéaires de l'anneau des polynômes. Ces bases apparaissent dans le contexte de la géométrie algébrique et peuvent être vues comme des généralisations de certaines bases des polynômes symétriques. Tout l'exposé sera illustré de calculs effectués à partir du logiciel Sage.

Les auteurs suscités ont montré que le nombre de solutions, b_{n,p} de g^p=1 dans le groupe S_n possède d'intéressante propriétés p-adique. Je montre que ce résultat équivaut à une propriété (inattendue ?) de prolongement analytique p-adique de la fonction Gamma p-adique. Ce résultat se généralise.

Au cours des années 1970, les théorèmes d'approximation fortes de Komlos, Major et Tusnady ont prouvé la convergence de marches aléatoires à sauts discrets vers des marches Browniennes, puis Borisov a étendu ce résultat aux ponts, la convergence étant obtenue après une normalisation adéquate. Cette convergence est, au sens large, de type "uniforme", c'est-à-dire valable pour tout point de la marche discrète. Nous nous intéressons à la convergence locale de la hauteur des ponts discrets, et nous obtenons asymptotiquement des résultats beaucoup plus précis que ceux de Borisov. En particulier, dans le cas des marches de type Łukasiewicz, nous sommes capables, en utilisant des méthodes d'asymptotique automatique, de pousser le dévelopement asymptotique à un ordre élevé. Ce travail a des applications potentielles en bioinformatique.
Travail en commun avec Cyril Banderier.

New uniform asymptotic approximations with error bounds are derived for a generalized total variation distance of Poisson approximation to the Poisson-binomial distribution (covering binomial distribution as special case). The method of proof is also applicable to other Poisson approximation problems, and therefore to a lot of data structures and algorithms.

Le modèle de Tetris sera le fil rouge de l’exposé. Il constitue un paradigme pour différents modèles de Systèmes à Événements Discrets, qui peuvent se voir comme des spécialisations, variations ou extensions de Tetris. Tetris constitue également le point de rencontre de deux classes de modèles mathématiquement intéressantes : les systèmes itérés d’applications topicales (max-plus dans le cas de Tetris) et les marches aléatoires sur les groupes ou monoïdes discrets (traces dans le cas de Tetris). Par ailleurs, le modèle de Tetris est intéressant en lui-même et sera étudié en tant que tel. On s’intéresse aux aspects énumératifs (combien d’empilements différents ?), à l’optimisation (à quoi ressemblent les empilements les plus denses ?) et à l’évaluation de performances (à quelle vitesse se constituent les empilements aléatoires ?).

Permutation tableaux are relatively new combinatorial objects that are in bijections with permutations. They have ben introduced in the context of algebraic combinatorics and subsequently found applications in combinatorial aspects of some particle models (like PASEP). Permutation tableaux have been studied mostly by bijective methods. In this talk, I will describe a direct, elementary approach based on probabilistic interpretation of a basic construction. This talk is partially based on results obtained jointly with Sylvie Corteel.

We consider random texts generated by a Bernoulli source. We want to count simultaneously the number of occurrences of words within a finite set of words in a random text of size n. The use of generating functions permits to construct a multivariate function counting the occurrences in texts of all size from 0 to infinity. From there several techniques give access to texts of size n. We compute the multivariate generating function

1. by the very elegant analytic inclusion-exclusion method that resorts to combinatorics.
2. by constructing the Aho-Corasick automaton recognizing the words, and translating later to generating functions. We compare the complexity of these two methods.

[Joint work with F. Bassino, J. Clément and J. Fayolle].

La compression sans perte d’un texte par anti-dictionnaire (DCA) est une technique de compression efficace introduite par Crochemore et alii à la fin des années quatre-vingt dix. Son principe repose sur la construction de l’anti-dictionnaire du texte : un dictionnaire formé de certains mots n’apparaissant pas dans le texte (mots appelés mots minimaux interdits). Après une introduction à cet algorithme, je montre que sous un modèle sans mémoire de génération des textes, le nombre moyen de mots dans l’anti-dictionnaire sur l’ensemble des textes de taille n se comporte asymptotiquement en $\frac{Kn}{h}+o(n)$, où la constante $K$ est determinée explicitement et $h$ est l’entropie du modèle probabiliste. Les outils que j’utilise proviennent de la combinatoire analytique et des probabilités.

Cet exposé portera sur la génération aléatoire d’automates finis. Les automates peuvent être vus comme des graphes orientés dont les arêtes sont étiquetées sur un alphabet fini et dont deux sous-ensembles de sommets sont distingués (l’ensemble respectivement des états initiaux et des états finals). On présentera une bijection entre l’ensemble des automates déterministes et accessibles à n états sur un alphabet fini et des diagrammes particuliers qui peuvent eux-mêmes être représentés comme les partitions d’un ensemble en n sous ensembles non-vides. Ces constructions combinatoires permettent d’estimer asymptotiquement le nombre d’automates à n états. Cette approche combinatoire a conduit à la conception d’un générateur aléatoire efficace, pour la distribution uniforme sur les automates déterministes à n états : la complexité moyenne en temps du générateur de Boltzmann associé est en O(n3/2). On montrera quelques exemples de résultats expérimentaux obtenus avec la librairie C++ REGAL dans laquelle il est implanté. [ Travail en collaboration avec Julien David et Cyril Nicaud (IGM). ]

Nous allons mettre en correspondance trois sortes d’objets : des permutations (ensemble d’excédences fixés), des orientations acycliques de graphes, et enfin des diagrammes de Young remplis de 0 et de 1 en évitant certains motifs. Les tableaux de permutations font le lien entre la première et la troisième classe d’objets, ici le motif évité est une paire de matrices d’ordre 2. En prenant une autre paire de matrices d’ordres 2, on fait élémentairement le lien entre la deuxième et la troisième classe. Reste à voir que les motifs évités sont équivalents, au sens où ils s’énumèrent de la même façon, ce qui peut se faire par récurrence mais aussi par des bijections. Selon le temps restant, nous montrerons que cette correspondance s’étend à une classe de polyominos bien plus générale que celle des diagrammes de Young.

Le problème de l’atelier de peinture est un problème simple à formuler et à comprendre, mais extrêmement riche. Par certains aspects, il relève de l’optimisation combinatoire, par d’autres, de la topologie algébrique, par d’autres encore, il est un point d’entrée dans les classes de complexité exotique comme PPA ou PPAD.

A coloring of a graph is an assignment of natural numbers to its vertices in such a way that adjacent vertices receive different colors. This well-known problem is a basic model for frequency assignment and resource allocation problems. In order to take into account particular constraints arising in practical settings, more elaborate models of vertex coloring have been defined in the literature. One of such generalized models is the list-coloring problem, which considers a prespecified set of available colors for each vertex. The list-coloring problem is NP-complete even for split graphs, interval graphs, and bipartite graphs. We consider some particular cases of the list-coloring problem: μ-coloring, where each vertex has its own upper bound for the color to be assigned, and (γ,μ)-coloring, where each vertex has its own lower and upper bounds for the color to be assigned. The μ-coloring problem arises in the context of classroom allocation to courses, where each course must be assigned a classroom which is large enough so it fits the students taking the course. We will present some polynomial time algorithms to solve these problems on classes where list-coloring is NP-complete.

The aim of the talk is to show how a difficult combinatorial problem has been recently solved using an experimental-mathematics approach combined with (rather involved) computer algebra techniques. More precisely, let $f(n,i,j)$ denote the number of lattice walks in the quarter plane which start at the origin, end at the point $(i,j)$, and consist of $n$ unit steps going either west, south-west, east, or north-east. In the early nineties, Ira Gessel conjectured that the sequence of excursions $f(n,0,0)$ is holonomic. We will present the computer-driven discovery and proof of the following generalization, obtained in August 2008 together with Manuel Kauers: the full generating series $F(t,x,y) = \displaystyle{\sum_{i,j,n \geq 0} f(n,i,j) x^i y^j t^n}$ is an algebraic function.

Dans les années 90 des simulations numériques ont révélées des propriétés intéressantes dans les ensembles aléatoires d’instances de problèmes de satisfaction de contraintes (satisfiabilité, coloriage de graphes notamment). Quand un paramètre définissant l’ensemble aléatoire (le nombre de clauses par variables) augmente la probabilité de trouver une formule satisfiable chute abruptement de 1 à 0 dans la limite des grandes tailles de formule. Ce phénomène de seuil a été l’objet d’actives recherches en informatique et en probabilités. Par ailleurs des outils (non-rigoureux) de physique statistique ont pu être appliqués à ces problèmes. Un certain nombre de résultats ont émergé de ces études, par exemple des conjectures quantitatives sur la valeur du seuil de satisfiabilité, et une image plus précise de la structure de l’ensemble des solutions des formules satisfiables. D’autres résultats de physique statistique ont un aspect plus algorithmique, que ce soit l’analyse d’algorithmes déjà existants ou la suggestion de nouvelles stratégies pour résoudre ces formules aléatoires. Dans ce séminaire j’essaierai de présenter, sans rentrer dans les détails techniques, le cadre général de ces études et certains de ces résultats.

Dans un premier temps, on présentera une méthode de génération aléatoire d’automates déterministes accessibles complets et un outil, REGAL, utilisant cette méthode. Les générateurs implantés dans REGAL permettent d’engendrer des automates de plusieurs milliers d’états et ce faisant, d’établir des conjectures crédibles sur les propriétés en moyenne des automates, ainsi que sur les algorithmes qui s’y appliquent. Dans une deuxième partie, on présentera un résultat théorique sur la complexité moyenne de l’algorithme de Moore: si la complexité dans le pire cas de l’algorithme est connu pour être en $\mathcal{O}(n^2)$, on montrera que pour un alphabet fini arbitraire et la distribution uniforme sur l’ensemble des automates déterministes accessibles complets n états, la complexité moyenne est $\mathcal{O}(n\log n)$.

Nous présentons une approche analytique du problème d’optimisation MAX-2-XORSAT basée sur la combinatoire analytique et énumérative. Dans cet exposé, nous étudions les séries génératrices liées aux configurations optimales de MAX-2-XORSAT. En combinant ces outils avec ceux d’analyse complexe, nous quantifions alors le nombre maximum de clauses satisfaisables des instances aléatoires de MAX-2-XORSAT.

Dans cet exposé, on étudie les classes de permutations, qui sont des ensembles de permutations fermés par le bas pour la relation d’ordre de motif. Je présenterai d’une part des résultats de nature algorithmique sur la recherche de motif dans les permutations, et d’autre part des résultats plutôt combinatoires sur la structure des classes de permutations. Un point commun à ces résultats est qu’ils ont été obtenus en utilisant les arbres de décomposition des permutations. Je présenterai ces objets, et illustrerai par des exemples comment ils peuvent être utilisés en combinatoire comme en algorithmique.

Historiquement, l’ADN et les protéines, aux deux extremités du dogme central de la biologie moléculaire, ont monopolisé l’attention des chercheurs en biologie, délaissant dans un premier temps l’ARN, confinée dans un rôle d’intermédiaire. Cependant, des études menées au cours de la dernière décennie sur les mécanismes de fonctionnement de ce polymère ont révélé une diversité de modes d’actions et un potentiel thérapeutique tels que deux prix Nobels ont été décernés à C. Mello/A. Z. Fire (Médecine 2006) et V. Ramakrishnan/T. A. Steitz/A. E. Yonath (Chimie 2009). À l’échelle nanométrique des interactions moléculaires, il est possible d’analyser la fonction des molécules à travers leur géométrie, ou conformation. Dans le cas de l’ARN, la conformation fonctionnelle d’un ARN résulte de phénomènes d’appariement entre des bases complémentaires, qui provoquent un repliement global de l’ARN. Par ailleurs, des contraintes stériques permettent bien souvent de limiter l’ensemble des conformations possible à des structures simples, les structures secondaires, dans lesquels les appariements considérés sont sans croisement. On assimile alors cet ensemble à un ensemble canonique "de Boltzmann", un des objets de base de la physique statistique, ce qui permet de définir une distribution de probabilité, dite de Boltzmann, sur l’ensemble des structures secondaires réalisables. L’ensemble des conformations d’un ARN est aussi assimilable à un objet combinatoire simple, analogue d’un arbre ou encore d’une séquence bien parenthésée, et pouvant être étudié grâce à l’arsenal de la combinatoire analytique. Après une introduction présentant les problématiques et challenge actuels de la bioinformatique de l’ARN, nous présenterons deux contributions à l’algorithmique des structures d’ARN, reposant sur une vision combinatoire de l’ensemble des conformations. La première consiste en une analyse et une amélioration d’un algorithme d’échantillonnage statistique pour la structure d’ARN. En se basant sur une analogie avec la génération aléatoire par la méthode dite récursive, nous pratiquons une analyse de la complexité moyenne de l’algorithme, et proposons une amélioration algorithmique basée sur un parcours "Boustrophedon" proposé par Flajolet/Zimmermann/Van Cutsem 1994. La deuxième application consiste en l’analyse d’une représentation hierarchique pour l’ensemble de Boltzmann, les RNA Shapes introduites par Giegerich/Voß/Rehmsmeier 2004.. Cette hierarchie de représentations compactes pour la structure d’ARN permet la mise en oeuvre d’approches modulaires pour l’analyse des repliements. Cependant, ces approches exigent parfois une énumération exhaustives des Shapes compatibles avec un ARN, provoquant ainsi une explosion combinatoire qu’il convient de quantifier. Pour cette raison, nous avons modélisé et énuméré celles-ci, obtenant des croissances asymptotiques en $\Theta(A^n/n^{3/2})$ pour ces représentations, avec A=1.8... (resp. A=1.3) pour la représentation la moins (resp. la plus) compacte, à comparer avec A=2.3 pour le nombre de structures secondaires de taille similaire.. Au passage, nous montrons (encore une...) bijection entre le niveau de représentation le plus compact et les mots de Motzkin. Les travaux sur les RNA-Shapes ont été menés en collaboration avec A. Lorenz et P. Clote (Boston College).

Écrivez une formule booléenne de manière aléatoire, construite avec des ensembles fixés de connecteurs et de littéraux. Quelle est la fonction booléenne « typique » qu’elle représente ? Quelle est la probabilité que la formule calcule la fonction Vrai ? Un littéral ? Ou une autre fonction donnée ? D’autres questions de nature un peu différente peuvent se poser : quelle est la complexité de la fonction booléenne représentée par cette formule aléatoire (i.e. la taille de la plus petite formule la représentant) ? Quelle est la complexité moyenne d’une fonction booléenne définie sur k variables ? Ces questions mettent en avant le problème suivant : comment définir une distribution de probabilité sur les fonctions booléennes ? Les premiers articles se posant ce genre de questions ont mis en avant deux modèles de formules booléennes aléatoires, basées sur les connecteurs binaires Et/Ou, et qui engendrent une distribution (non uniforme) sur les fonctions booléennes. Ces articles n’ont répondu que très partiellement aux premières questions que j’ai évoquées. On adapte aisément ces distributions au cas de formules construites à l’aide de l’unique connecteur Implication, un des connecteurs de base d’un point de vue logique. Ce modèle de base suscite de l’intérêt car certaines formules représentant des tautologies (formule calculant toujours Vrai) en logique classique ne sont pas des tautologies en logique intuitionniste. Dans un premier temps, j’exposerai les résultats concernant l’ensemble des fonctions booléennes construites sur l’Implication, puis j’aborderai en détail les tautologies. Dans un troisième temps, j’enrichirai le modèle de formules en utilisant plusieurs connecteurs logiques aléatoires. Enfin, je conclurai l’exposé en abordant différentes perspectives relatives à ces problèmes et sur lesquelles je travaille actuellement.

La théorie de la complexité distingue les problèmes que l’on sait résoudre en un temps polynomial en la taille des données (que l’on peut qualifier de raisonnable), des problèmes NP-complets, qui nécessitent (en l’état actuel des connaissances) un temps de résolution exponentiel en la taille des données (que l’on peut qualifier de déraisonnable). C’est pour cette raison que la communauté scientifique s’est tournée vers les algorithmes (polynomiaux) d’approximation dont la mesure de qualité se fait le plus souvent grâce au rapport d’approximation en pire cas (pour un problème de minimisation de taille, un algorithme a un rapport d’approximation de k si la taille de toute solution pouvant être retournée par l’algorithme est inférieure ou égale à k fois la taille de la solution optimale). Dans la littérature, on en vient à considérer qu’un algorithme est plus performant qu’un autre lorsqu’il possède un plus petit rapport d’approximation en pire cas. Cependant, il faut être conscient que cette mesure, désormais "classique", ne prend pas en compte la réalité de toutes les exécutions possibles d’un algorithme (elle ne considère que les exécutions menant à la plus mauvaise solution). Dans les travaux que je vais vous présenter, nous avons tenté de mieux "capturer" le comportement des algorithmes d’approximation en allant plus loin que le simple rapport d’approximation en pire cas (en nous focalisant sur le problème du Vertex Cover) : En montrant que les performances moyennes d’un algorithme peuvent être décorélées des performances en pire cas. Par exemple, nous avons montré que dans la classe des graphes spécialement conçus pour le piéger en pire cas, l’algorithme glouton "Maximum Degree Greedy" retourne, en moyenne, des solutions dont la taille tend vers l’optimum lorsque n tend vers l’infini. En évaluant les performances moyennes d’un algorithme. Nous avons prouvé que l’algorithme online présenté par Demange et Paschos en 2005 (dont le rapport d’approximation en pire cas est égal au degré maximum du graphe) est au plus 2-approché en moyenne dans n’importe quel graphe. Ce résultat, combiné à d’autres, montre que cet algorithme est "en pratique" meilleur que la plupart des algorithmes 2-approchés connus, malgré un mauvais rapport d’approximation en pire cas . En comparant les performances de différents algorithmes (analytiquement et expérimentalement). Nous avons proposé un algorithme de liste et nous avons prouvé analytiquement qu’il retourne toujours une meilleure solution que celle construite par un autre algorithme de liste récent [ORL 2006] quand ils traitent la même liste de sommets (dans certains graphes particuliers, la différence de taille peut être arbitrairement grande). Nous avons également comparé analytiquement (en utilisant des outils comme les séries génératrices) les performances moyennes de six algorithmes sur les chemins. Nous les avons ensuite expérimentées sur un grand nombre de graphes de diverses familles bien choisies. On constate dans ces études que les algorithmes 2-approchés étudiés sont ceux qui obtiennent les plus mauvaises performances en moyenne et que ceux qui ont les meilleurs comportements moyens ont de mauvais rapports d’approximation (fonction du degré max. du graphe). Tous ces résultats montrent que le rapport d’approximation en pire cas n’est pas toujours suffisant pour caractériser l’intégralité de la qualité d’un algorithme et que d’autres analyses (en moyenne notamment) doivent être effectuées pour en faire le tour.

Pour étudier un algorithme de tri classique sur /n/ nombres réels distincts, il suffit d’étudier l’algorithme sur les antécédents de /(1,2,...,n)/, i.e. sur les /n!/ énumérations des éléments de l’ensemble /{1,...,n}/. L’exécution de l’algorithme sur l’ensemble de ces /n!/énumérations permet de constater toutes les exécutions possibles de l’algorithme. Lorsque les algorithmes sont décrits à la manière des systèmes dynamiques symboliques, chaque exécution est une suite de transformations élémentaires. Afin de caractériser parmi tous les mots sur l’alphabet des transformations élémentaires, ceux qui correspondent à des traces d’exécutions, il suffit donc pour les tris classiques de considérer les traces d’exécutions sur un ensemble générique : l’ensemble des / / énumérations des éléments de l’ensemble /{1,...,n}/. Nous fournissons un cadre permettant d’exhiber de tels ensembles génériques d’entrées // pour les algorithmes de recherche de séquence génératrice optimale dans une structure présentée (les tris en sont des exemples particuliers mais cela englobe aussi les algorithmes d’Euclide de Gauss et bien d’autres). Une structure présentée est une structure munie d’un squelette pour sa présentation (ou encore son codage) : un entier pour le cardinal d’une séquence génératrice et un ensemble de mots correspondants aux relateurs. Nous nous intéressons à de tels objets munis d’un préordre, lorsqu’ils possèdent beaucoup (éventuellement une infinité) de séquences génératrices. Nous considérons les algorithmes qui partant d’une séquence génératrice quelconque retournent une séquence génératrice satisfaisant certaines propriétés vis-à-vis du préordre.

The Heisenberg-Weyl algebra, underlying most physical realizations of Quantum Theory, is considered from a combinatorial point of view. We construct a concrete model of the algebra in terms of graphs which endowed with intuitive concepts of composition and decomposition provide a rich bi-algebra structure.
It will be shown how this encompass the Heisenberg-Weyl algebra, thereby providing a straightforward interpretation of the latter as a shadow of natural constructions on graphs. We will also discuss some combinatorial methods suitable for this graphical calculus.

Renormalization of multiple zeta values for negative integers. Using Connes and Kreimer renormalization, we will show how to extend multpiple zeta functions to every complex argument so that the "quasi-abattage" relations are preserved. The values obtained for negative integers are rational. We will discuss a multi-dimensional analogue. Common work with Sylvie Paycha.

Titre : Dualité et séries formelles.
Résumé :
L'objectif de cet exposé est de montrer que, quelle que soit la topologie (séparée) de corps sur K, le dual (topologique, pour la topologie produit) de l'espace K^X des applications définies sur un ensemble X et à valeurs dans le corps K est isomorphe au sous-espace K^(X) des fonctions à support fini.
En particulier, ce résultat s'applique lorsque X est le monoïde commutatif libre sur une lettre x, où, dans ce cas, K^X n'est autre que l'ensemble des séries formelles K[[x]], et K^(X) celui des polynômes K[x].
Une conséquence de ce fait est que l'espace des endomorphismes continus (sous les hypothèses précédentes quant au choix des topologies) de K^X est isomorphe à l'espace des " matrices " dont les " lignes " sont à support fini.

Titre : Grammaires algébriques et asymptotique.
Résumé :
Nous verrons dans un premier temps comment étudier un "motif" dans un langage rationnel (=une grammaire linéaire) via la série génératrice associée à un automate. Nous donnerons une application au modèle de Schelling.
Nous verrons dans un deuxième temps les aspects asymptotiques des grammaires algébriques : Universalité du phénomène "1/ sqrt(Pi) n^3/2", pour finir sur les recherches en cours : que peut-il être dit au-delà du théorème de Drmota-Lalley-Woods.
Comme, au delà de la théorie, se cache un certain nombre de problèmes techniques, nous montrerons sur des exemples comment on peut utiliser les packages Maple algolib/combstruct/gfun de Salvy/Flajolet et al. pour faire effectivement les calculs asymptotiques, générer des structures, etc.

Titre:
Sur le plongement du complété d'un espace normé dans son complété pour une autre norme.
Soit E un espace vectoriel muni de deux normes p et q comparables, i.e., quel que soit x, p(x) est inférieur ou égal à q(x). En dépit du fait que dans cette configuration toute suite de Cauchy pour q est une suite de Cauchy pour p, on ne peut rien dire en général des relations entre les complétés de E pour p et pour q.
Dans cet exposé, une condition nécessaire et suffisante pour laquelle le complété pour q se plonge continûment (et densément) dans le complété pour p est présentée.

Titre:
Combinatoire de Catalan et des fonctions de stationnement
Au cours des dernières années, des questions soulevées en théorie des invariants de groupes, concernant les propriétés des espaces coinvariants diagonaux, ont mené à une étude fine de la combinatoire des fonctions de stationnement (parking functions) et de paramètres sur celles-ci. Nous allons présenter certains de ces développements, ainsi que des extensions qui font intervenir l'ordre de Tamari et ses extensions aux cas des chemins de Dyck généralisés.
L'emphase sera donc mise sur les problèmes combinatoires soulevés par cette étude.

Titre : Adjonction d'unité, aspect catégorique.
Laurent Poinsot
Résumé :
L'adjonction d'une unité à un semi-groupe pour constituer un monoïde, ou à un anneau pour en faire un anneau unitaire, dérive d'une construction générale, que je me propose d'exposer, dans le cadre des catégories monoïdales.
En effet, pour une catégorie monoïdale C donnée avec coproduits finis et telle que le tenseur se distribue sur le coproduit, cela résulte de l'existence d'un adjoint à gauche pour le foncteur d'oubli de la catégorie des monoïdes internes à C dans celle de ses semi-groupes internes.

I will introduce in this talk the main ingredients required to obtain a renormalizable model in quantum field theory.
After presenting the main ideas for commutative models, I will generalize this for noncommutative quantum field theory, where usual graphs are replaced by topologically richer ribbon graphs.

I will introduce in this talk the main ingredients required to obtain a renormalizable model in quantum field theory.
After presenting the main ideas for commutative models, I will generalize this for noncommutative quantum field theory, where usual graphs are replaced by topologically richer ribbon graphs.

Le produit triple de Jacobi est une identité reliant un produit infini à une somme infini, un cas particulier célèbre étant le théorème pentagonal d'Euler. Nous montrons ici une version finie consistant à dire que les sommes tronquées comptent certains chemins (ou que leur série génératrice s'écrit comme une fraction continue). Ceci est relié à des problèmes d'énumération, via certaines formules dites de Touchard-Riordan.

La formule des équerres (”hook formula”) apparaît dans le contexte des tableaux de Young et joue un rôle essentiel en combinatoire algébrique, théorie des représentations et théorie des partitions. Une nouvelle méthode, appelée technique de développement en longueur des équerres (et qui présente quelques challenges algorithmiques), permet de découvrir toute une famille de formules des équerres, pour plein de structures combinatoires, suggérant qu'un phénomène mathématique profond ne nous est pas encore pleinement révélé. Un cas particulier de ces formules a été obtenu par Nekrasov et Okounkov dans un contexte tout à fait différent. Dans le cas des arbres planaires on obtient une formule qui unifie plusieurs résultats classiques, y compris la formule de Postnikov. D’autres travaux récents liés à ce sujet par Stanley, Ono, Bessenrodt, Carde, Loubert, Potechin, Sanborn, Okada et Panova seront présentés, ainsi que des liens avec de célèbres conjectures de Ramanujan-Lehmer sur certaines formes modulaires en théorie des nombres...

Un mot circulaire est un mot fini dans lequel on suppose que la première lettre suit la dernière. On le dit admissible s'il ne contient que des 0 et des 1 sans jamais voir deux 1 de suite. Les mots circulaires admissibles renferment des structures explicites de groupes abéliens finis liés à la suite 1, 5, 16, 45, 121, 320,... par ailleurs connue pour ses propriétés combinatoires. Une application des mots circulaires admissibles est l'étude des nombres "F-adiques", qui sont un équivalent des p-adiques pour le système de numération déduit de la propriété de Fibonacci. Plus d'infos : Sloane EIS

Distances in Noncommutative Geometry.
We shall give an overview of the metric aspect of Noncommutative Geometry, underlining the link between the distance formula in Connes' theory of spectral triple and other distances in mathematics, in particular:
- the horizontal distance in sub-riemannian geometry,
- the Wasserstein distance in the theory of optimal transport.
We will also propose several physical interpretation of this distance, regarding the Higgs field in the standard modelof elementary particles, or the distance in some model of quantum spacetimes.

An algebraic Birkhoff decomposition for non perturbative renormalization.
We show how the formalism of Connes-Kreimer, initially developed for perturbative renormalization, can be partially adapted to Wilson's continuous renormalization. The combinatorics of renormalization is no longer described by the Hopf algebra of Feynman diagrams, but rather by the Hopf algebra of rooted trees with two decorations. The latest correspond to the two distinct scales at which one fixes the initial conditions of the equations of the renormalization group. In this framework, we show that the equivalent of the projection on the holomorphic part of the Birkhoff decomposition (in perturbative renormalization) is now a projection on one decoration.

The thermal time hypothesis: geometrical action of the modular group in conformal field theory with boundary.
After recalling the basis of the thermal time hypothesis of Connes and Rovelli (namely the idea that the physical flow of time is a state dependent notion, that can be retrieved from the modular group associated to the von Neumann algebra of local observables of the physical system under consideration), we present an explicit computation of the action of the modular group associated to double-cone regions of bi-dimensional Minkowski spacetime for a conformal field theory with boundary.
Starting from the covariance of the theory under the Möbius group, we show how to work out an ad-hoc state whose modular group has a pure geometrical action. We compute the Unruh temperature associated to one specific orbit. We then investigate the action of the modular group of the vacuum state, showing that it mixes the previous geometrical action with a nonlocal term. The latest mixes the components of the field in two light-like directions. From a mathematical point of view, it provides one of the first examples of an explicit computation of (the action of) the unitary cocycle intertwinning the modular group of different states on the same algebra.

On donne les notions de factorisation complète du monoïde libre et fait le lien avec les bases de Radford et leurs duales.
Si le temps le permet, on donnera le "principe d'identification locale" sur les mots de Lyndon.
Les preuves seront données et discutées complètement et les outils de preuve seront posés, détaillés et discutés interactivement en vue de la communication à différentes communautés.

Chebyshev polynomials, Hermite polynomials, Bessel functions and other families of special functions each form a basis of some Hilbert space. A Generalized Fourier Series is a series expansion in one of these bases, for instance a Chebyshev series. When such a series solves a linear differential equation, its coefficients satisfy a linear recurrence equation. We interpret this equation as the numerator of a fraction of linear recurrence operators. This interpretation lets us give a general algorithm for computing this recurrence, and a simple view of existing algorithms for several specific function families. Joint work with Bruno Salvy.

Marches aléatoires : records, lemme cyclique et convergence presque sûre. (Philippe Marchal, LAGA, Paris 13)
Dans un premier temps, nous montrerons comment montrer la convergence presque sûre des chemins de Dyck vers le Brownien. Dans un deuxième temps, nous parlerons des plus hauts points successifs (classiquement appelés "records") d'une marche aléatoire à valeurs dans R. Il existe des relations de dualité bien connues entre les records successifs ascendants et les records successifs descendants, dont la preuve se ramène essentiellement au lemme cyclique. Nous établissons de nouvelles relations liant, pour une même trajectoire, le nombre de records ascendants et le nombre de records ascendants pour la marche rétrograde.

We will illustrate the importance of von Neumann algebras in physics, emphasizing in particular their role in the algebraic formulation of quantum field theory.
We will illustrate by various examples how some characteristic properties of von Neumann algebra have a direct translation into properties of spacetime.

Étant donnée une trace définie sur l'algèbre d'Hecke du groupe symétrique Sn, la décomposition de t sur la base des caractères irréductibles fournit une mesure de probabilité sur l'ensemble Pn des partitions de taille n. Lorsque t est la trace régulière de Hq(Sn), ou plus généralement une trace de Markov, la mesure correspondante vérifie une loi des grands nombres et un théorème central limite pour la taille des lignes et des colonnes des partitions. Via l'algorithme RSK et la théorie des fonctions quasisymétriques, ces résultats peuvent être interprétés en termes de longueur des plus longs sous-mots croissants et décroissants de modèles de permutations aléatoires.

Nous construisons une sous-algèbre de Hopf de l'algèbre de Hopf des fonctions quasi-symétriques libres dont les bases sont indexées par les objets de la famille combinatoire de Baxter (i.e. permutations de Baxter, couples d'arbres binaires jumeaux, etc.). Cette construction repose sur la définition du monoïde de Baxter, analogue du monoïde plaxique et du monoïde sylvestre, et d'un algorithme d'insertion analogue à l'algorithme de Robinson-Schensted. Les propriétés algébriques de cette algèbre de Hopf sont étudiées..

On illustre l'utilité du concept de réalisation et de spécialisation d'alphabet d'une algèbre (sur des alphabets commutatifs ou non, simplement ou doublement indexés) par une (longue) série d'exemples. Les premiers se rapportent aux compositions, aux arbres binaires et aux permutations et on termine, si le temps le permet, en présentant l'exemple le plus récent, celui de l'algèbre de Connes-Kreimer.

Les automates cellulaires constituent une classe d'objets permettant de décrire, à l'aide d'une unique règle locale finie, l'évolution, potentiellement complexe, d'un système infini. L'objectif de l'exposé est d'introduire un cadre formel permettant de quantifier des propriétés parmi l'ensemble des automates cellulaires. On commencera par une présentation de tous les objets considérés. On verra ensuite notre formalisme proprement dit et ses liens avec la complexité de Kolmogorov. On évoquera enfin quelques résultats significatifs en s'intéressant d'une part aux techniques qui interviennent dans nos preuves et d'autre part aux conséquences de ces résultats sur notre compréhension des automates cellulaires.

L'objet de cet exposé est de présenter NumGfun, un module Maple consacré à la manipulation « analytique » des solutions d'équations différentielles linéaires à coefficients polynomiaux (fonctions dites D-finies ou holonomes). Les principales fonctionnalités de NumGfun concernent l'évaluation numérique des fonctions D-finies, et le calcul de bornes qui permettent de contrôler leur comportement. Je ferai une démonstration de l'utilisation de NumGfun, et je montrerai comment, à travers le calcul certifié de constantes de connection, il peut être utilisé pour étudier le comportement asymptotique de suites données par des séries génératrices D-finies.

On étudie le problème suivant: partant d'un mot w et d'un entier q, on souhaite engendrer toutes les façons possibles de partitionner w en ensemble de sous-mots fréquents. Un sous-mot est fréquent s'il possède au moins q occurrences dans la partition. Chaque mot étant associé à un nombre d'occurrences, on s'intéresse à des multiensembles de mots plutôt qu'à des ensembles de mots. Par exemple, partant du mot w=cabcba et d'un entier q=2, le multiensemble {(cb,2),(a,2)} est une solution. On présentera un algorithme qui engendre l'ensemble des solutions sans redondance et on montrera que, sauf si P=NP, la complexité de ce problème est exponentiel dans la taille de la sortie. On donnera un exemple d'une des applications possibles pour cet algorithme.

La complexité en états d'un langage rationnel est le nombre d'états de son automate minimal. Dans cet exposé nous considèrerons une distribution, où les langages finis sont donnés comme une liste de mots, et nous étudierons la complexité en moyenne des opérations rationnelles: union, concaténation et étoile. L'étude en moyenne est particulièrement intéressante quand le pire de cas est exponentiel, ce qui est le cas ici pour l'étoile et pour la concaténation. Nous prouverons notamment qu'en moyenne la complexité est de ces deux opérations est linéaire. Nous finirons l'exposé en présentant une extension de ces résultats à d’autres classes de langages. Il s'agit de travaux effectués en collaboration avec F. Bassino et C. Nicaud.

We discuss two methods based on Wilf-Zeilberger summation for the computation of Feynman parameter integrals. For the first method, the integrals are rewritten as multisums over hypergeometric terms to fit the input class of WZ-summation. These summation problems are highly nested sums with non-standard boundary conditions. They satisfy inhomogeneous recurrences containing sums of lower nested depth on the right-hand sides. These last recurrences can be solved recursively by Carsten Schneider's Sigma package. Another approach to evaluate Feynman integrals is by representing them as nested Mellin-Barnes integrals. We show how WZ-methods determine recurrences for contour integrals of this type, thus eliminating the need to find sum representations. This algorithmic technique is also applied to prove typical entries from the Gradshteyn-Ryzhik table of integrals using the Mellin transform method.

Combinatorial aspects of renormalization in quantum field theory
In this talk, we will present the main ingredients of the BPHZ renormalization of quantum field theory. Then, we will see the situation of quantum field theory on noncommutative spaces.

Algebraic structures and C*-algebras
In this talk, we will introduce the basics of the theory of C*-algebras, which correspond to noncommutative topological spaces in the noncommutative geometry picture. Then, we will see the Hochschild cohomology as a generalization of the de Rham complex of differential forms, and some applications to physics.

Date: Wed, 16 Mar 2011 10:29:36
From: Hichem.Kenniche
j'ai le plaisir de vous inviter à la soutenance de ma thèse intitulée « Réseaux de capteurs sans fil de grande taille: quelques contributions à la modélisation et à l'algorithmique » ainsi qu'au pot qui suivra. La soutenance aura lieu le vendredi 1 avril à 11h00 dans la salle B311. Le jury sera constitué de :
M. Jean Frédéric Myoupo, professeur, Université de Picardie Jules Verne, Président.
M. Yves Métivier, professeur, Université Bordeaux 1, Rapporteur.
M. Vincent Villain, professeur, Université de Picardie Jules Verne, Rapporteur.
Mme. Frédérique Bassino, professeur, Université Paris 13, Examinatrice.
M. Gérard Duchamp, professeur, Université Paris 13, Examinateur.
M. Christian Lavault , professeur, Université Paris 13, Directeur de thèse.
M. Vlady Ravelomanana, professeur, Université Paris 7, Co-encadrant.

-------------------------------------------------------------------
Résumé de la thèse :
Cette thèse est consacrée d'abord aux problèmes de modélisation des réseaux de capteurs sans fil, à savoir, comment trouver un modèle de communication réaliste. Un réseau de communication se modélise par un graphe. Le cadre de réseaux de capteurs sans fil ne va pas déroger à la règle et les capteurs, les noeuds de communication, seront modélisés par les sommets du graphe tandis que les arêtes représenteront les liens physiques de communication entre ces éléments communicants. La notion de graphe est importante car un grand nombre de paramètres employés en théorie des graphes permettent de quantifier des propriétés physique, topologiques ou des performances des réseaux modélisés. Toutefois, dans l'avenir les applications impliqueront un très grand nombre de capteurs à déployer sur de grande zones souvent inaccessibles, ce qui conduirait à un déploiement aléatoire rendant les modèles de graphes classiques obsolètes. Nous montrons que la stratégie aléatoire est la seule façon de déployer les réseaux de capteurs et par conséquent la modélisation par les graphes aléatoires géométriques et les graphe de Poisson est la plus appropriée. Nous développons ensuite nos travaux concernant la k-couverture, définie comme tout point physique de la zone de déploiement doit être couvert par au moins k noeuds actifs. Une notion très importante car nécessaire au bon fonctionnement du réseau car impliquant le connexion. Pour étudier les réseaux de capteurs aléatoires et pour pouvoir mettre à profit leurs densités afin de concevoir des protocoles qui permettent de maintenir un haut degré de couverture tout en prolongeant la durée de vie du réseau, nous étudions les limites fondamentales de la durée vie d'un réseau de capteurs que tout algorithme peut atteindre. Pour un ensemble de n points suivants un processus ponctuels de Poissons d'intensité dans une région de taille S avec chaque point couvrant un disque unité, nous donnerons des résultats concernant les valeurs requise pour garantir la k-couverture pour toute valeur de k. Nous terminons enfin par l'étude en moyenne d'algorithmes pour la recherche de stable maximal dans les graphes aléatoires. Nous examinons d'abord la performance du plus simple des algorithmes séquentiel sur deux types de graphes aléatoires. Dans le premier cas, nous considérons des graphes de Poisson, on établira que l'algorithme glouton trouve un ensemble indépendant maximal dont la loi limite est asymptotiquement normale. Dans le second cas, nous étudions le même algorithme sur les graphes d'Erdös-Rényi et montrerons que la distribution limite n'existe pas. Enfin, nous présenterons et analyserons un algorithme distribué probabiliste optimal (en temps et en bits).

"Combinatorial state sum invariants from categories"
'State sum models' are discrete functional path integrals. Using the combinatorics of the Pachner moves of the triangulation to convert a topological problem into an algebraic one, these models can be used to define manifold invariants and topological quantum field theories. Just as 3d state sum models, including quantum gravity, can be built using categories of group representations, 2-categories of 2-group representations may provide interesting state sum models for 4d quantum topology, if not quantum gravity. I will describe the construction of the first non-trivial example of a such models, based on the representations of a categorical version of the Euclidean group. I will show that this model shows up naturally in a combinatorial (state sum) reformulation of Feynman integrals for ordinary quantum field theories on 4d Euclidean spacetime.

Dans cet exposé je présenterai diverses propriétés combinatoires et algorithmiques des mots de Lyndon aléatoires. Je parlerai principalement de factorisation standard (travail avec F. Bassino et J. Clément) et de décomposition en mots de Lyndon. On verra des techniques analytiques et des techniques probabilistes pour aborder ce genre de questions. Le résultat principal est que l'on peut décomposer en mots de Lyndon en temps moyen sous-linéaire. On utilise pour cela une bonne compréhension de ce qu'est un mot aléatoire "typique" et des techniques d'algorithmique du texte.

"Aspects of group field theories"
Group field theories (GFT) provide a higher dimensional generalization of matrix models. Just as the Feynman graphs of matrix models are ribbon graphs dual to Riemann surfaces, the graphs of a D-dimensional GFT are D-stranded graphs dual to triangulated (pseudo)-manifolds. They provide a new and promising framework for the study of quantum gravity, including a sum over all topologies. I will describe several new aspects of these theories, including a dual formulation as non-commutative field theories, which provide important insights on their geometrical meaning.

The 1/N expansion in colored tensor models
Abstract: Matrix models are one of the most versatile tools in theoretical physics with applications ranging from the theory of strong interaction, to string theory, critical phenomena and two dimensional quantum gravity.
The versatility of matrix models is largely due to their topological 1/N expansion dominated by graphs with spherical topology. In higher dimensions matrix models generalize to tensor models. The ordinary tensor models are plagued by singularities and do not admit a meaningful 1/N expansion.
In this talk I will show that by adding an extra ingredient (a coloring of the fields) the tensor models become manageable and admit a 1/N expansion dominated by graphs with spherical topology in arbitrary dimension.

Glauber Dynamics is a simple Markov Chain used to sample (complex) spin distributions, such as colorings and independent sets, on graphs. We show that the mixing time of the Glauber dynamics for random k-colorings (and for the hard core model with boundary conditions) of the complete tree undergoes a phase transition around the reconstruction threshold. The central element of our result is a general technique that transforms a reconstruction algorithm into a set with poor conductance.

Divide-and-conquer recurrences are one of the most studied equations in computer science. Yet, discrete versions of these recurrences still present some challenges. The discrete nature of this recurrence (represented by quantization) introduces certain oscillations not captured by the traditional Master Theorem of divide and conquer recurrence, for example due to Akra and Bazzi who primary studied the continuous version of the recurrence. We show how powerful techniques such as Dirichlet series, Mellin-Perron formula, and (extended) Tauberian theorems of Wiener-Ikehara can be used to provide a complete and precise solution to this basic computer science recurrence. We illustrate applicability of our results on several examples including a popular and fast arithmetic coding algorithm due to Boncelet for which we estimate its average redundancy and prove the Central Limit Theorem for the phrase length. This allows us to compare the redundancy of Boncelet's algorithm to the (asymptotically) optimal Tunstall scheme. Join work with M. Drmota (TU Wien)

Dans la littérature, on considère souvent qu'un algorithme d'approximation polynomial est plus performant qu'un autre lorsqu'il possède un meilleur rapport d'approximation en pire cas. Cependant, il faut être conscient que cette mesure, désormais "classique", ne prend pas en compte la réalité de toutes les exécutions possibles d'un algorithme (elle ne considère que les exécutions menant à la plus mauvaise solution). Dans mes travaux, je me suis focalisé sur le problème du vertex cover et j'ai tenté de mieux "capturer" le comportement des ces algorithmes d’approximation en montrant que les performances moyennes d’un algorithme peuvent être décorélées des performances en pire cas, en évaluant les performances moyennes d’un algorithme et en comparant les performances de différents algorithmes (analytiquement et expérimentalement). J'ai également proposé un algorithme de liste et j'ai prouvé analytiquement qu'il retourne toujours une meilleure solution que celle construite par un autre algorithme de liste récent [ORL 2006] quand ils traitent la même liste de sommets (dans certains graphes particuliers, la différence de taille peut être arbitrairement grande). On constate dans ces études que les algorithmes 2-approchés étudiés sont ceux qui obtiennent les plus mauvaises performances en moyenne et que ceux qui ont les meilleurs comportements moyens ont de mauvais rapports d'approximation.

L'objet central de cet exposé est le graphe des flips sur les arrangements de pseudodroites avec points de contact couvrant un support donné. Il généralise les graphes de flips sur trois objets géométriques intéressants : les triangulations d'un polygone convexe, les pseudotriangulations d'un ensemble de points du plan en position générale, et les multitriangulations d'un polygone convexe. On s'intéresse en particulier à la polytopalité de ces graphes de flips. Par example, le graphe des flips sur les triangulations est le graphe de l'associahédre et le graphe des flips sur les pseudotriangulations est le graphe du polytope des pseudotriangulations. Pour les +multitriangulations, la question reste ouverte. Dans cet exposé, je rappellerai dans un premier temps les principales propriétés combinatoires de ces objets, en soulignant le lien avec les complexes des sous-mots du groupe symétrique définis par Knutson et Miller. Dans un deuxième temps, je présenterai la construction du "polytope des briques" d'un support. Son graphe est un sous-graphe du graphe des flips sur les arrangements de pseudodroites ayant ce support. Cette construction contient en particulier toutes les réalisations de l'associaèdre d'Hohlweg et Lange, qui apparaissent comme polytopes de briques de certains supports bien choisis. Travail en commun avec Francisco Santos (Université de Cantabrie).

The analysis of repetition in strings constitutes a fundamental area of combinatorics on words due to important applications to text algorithms, data compression, music analysis, and biological sequences analysis, to quote a few. The talk surveys algorithmic methods used to locate repetitive segments in strings. It discusses the notion of runs that encompasses various types of periodicities considered by different authors. The analysis of related algorithms raises interesting combinatorial questions and conjectures.

On montrera que l'algebre de Hopf de Connes et Kreimer, apparait de maniere naturelle comme construction d'algebre de Hopf provenant soit de l'operade preLie soit de l'operade NAP, que je definirais. Je donnerai d'autres exemples d'algebres de Hopf qui peuvent etre obtenus a partir de la theorie des operades.

"Next Generation Sequencing" represents a class of relatively new technologies (first results published in 2007) which enable sequencing millions of short nucleotide sequences (reads) in several days. I will briefly discuss several biological applications of "Next Generation Sequencing", such as ChIP-Seq, transcriptome sequencing, small-RNA sequencing, whole genome sequencing. I will summarize the main challenges of the primary steps data analysis: assembly or alignment of reads, normalization of read counts. If I have time I will also talk about "Next-Next Generation Sequencing" (first results published in 2010).
Références :

• Michael L. Metzker (2010) Sequencing technologies : the next generation. Nature Review Genetics
• séquence de l'ADN

On s'interesse ici a construire une bijection entre deux familles d'objets combinatoires : les ASMs et les TSSCPPs ou, selon Zeilberger, entre les triangles Gog et les triangles Magog. Jusqu'à présent, seule une bijection entre les trapèzes à une ligne était connue, et l'étape suivante, celle des trapèzes à deux lignes, semblait inaccessible. Nous proposons de résoudre ce problème grâce à l'utilisation d'un outil fondamental en combinatoire, l'involution de Schutzenberger. Cette construction laisse entrevoir la possibilité d'une solution complète du problème, en traitant les trapèzes à nombre arbitraire de lignes.

La renormalisation est l'un des outils fondamentaux de la théorie quantique des champs. En particulier, en électrodynamique quantique, on doit renormaliser la charge et la masse de l'électron.
Dans cet exposé je présenterai un modèle non linéaire simplifié, basé sur l'opérateur de Dirac et prenant en compte la polarisation du vide, pour lequel il est possible de réaliser complètement la renormalisation de charge. Il s'agit d'un résumé de travaux en collaboration avec Gravejat (Paris- Dauphine), Hainzl (Tuebingen, Allemagne), Séré (Paris-Dauphine) et Solovej (Copenhague).

I will introduce in this talk the combinatorial Connes-Kreimer Hopf algebra of Feynman graphs, celebrated structure known to encode the combinatorics of renormalization in quantum field theory (QFT). Hochschild cocyles (associated to some particular graphs) will then be defined; this allows to write down the combinatorial Dyson-Schwinger equations (recursive equations in power series written in terms of these Hochschild cocyles). It is worth emphasizing that the Dyson-Schwinger equations can play a crucial role in non-perturbative QFTs. Several explicit examples will be given to illustrate these various notions. Based on: http://arxiv.org/abs/0907.2182

Dans cet exposé, je rappelle les définitions de différents objets apparentés par leur nom et que l'on peut ranger dans la classe des "objets de Lie". J'illustrerai aussi les liens qui les unissent et présente différents théorèmes importants, en particulier dans le mouvement actuel. Nous parlerons donc, entre autres, d'algèbre de Lie, de groupe de Lie, des théorèmes de Cartier-Quillen-Milnor-Moore et de Poincaré-Birkhoff-Witt.

Information is the distinguishing mark of our era, permeating every facet of our lives. An ability to understand and harness information has the potential for significant advances. Our current understanding of information dates back to Claude Shannon's revolutionary work in 1948, resulting in a general mathematical theory of reliable communication that formalized the modern digital communication and storage principles, paved the way for the Internet, DVDs and iPods of today. While Shannon's information theory has had profound impact, its application beyond storage and communication poses foundational challenges. The National Science Foundation has just established a Science & Technology Center on the Science of Information to meet the new challenges posed by the rapid advances in networking, biology and knowledge extraction. Its missions is to develop rigorous principles guiding the extraction, manipulation, and exchange of information, integrating elements of space, time, structure, semantics and context. In this talk, after reviewing main results of Shannon, we then attempt to identify some features of information encompassing structural, spatio-temporal, and semantic facets of information. If time allows, we present one new result on a fundamental lower bound for structural compression and describe a novel algorithm achieving this lower bound for graphical structures.

The Jack superpolynomials are symmetric polynomials, involving commuting and anticommuting variables, that are orthogonal eigenfunctions of a certain integrable model known as the supersymmetric Calogero-Moser-Sutherland model.
We will discuss how the usual properties of the Jack polynomials can be extended to the Jack superpolynomial case. We will mainly focus on the fact that classes of Jack superpolynomials at special values of the coupling constant admit clusters of size at most k, that is, they vanish when k+1 variables are equal but not (conjecturally) when only k are identified (a sort of generalization of the Pauli exclusion principle).
We will also describe the connection between the super-Virasoro algebra and the vanishing of the Jack superpolynomials.

En algorithmique, on manipule très souvent des mots, notamment dans l'algorithmique du texte ; plus souvent encore, on manipule ce qu'on appelle communément des clés, notamment dans les algorithmes de tri ou de recherche, ou dans les bases de données. Dans une perspective plus réaliste, il faut vraiment considérer une clé comme une suite finie de symboles, c'est-à-dire comme un mot. On remplace alors le coût unitaire d'une comparaison entre deux clés par le coût de la comparaison entre deux mots, égal au nombre de symboles comparés. L'algorithmique générale devient alors de l'algorithmique du texte, et le processus qui produit les mots, appelé source, acquiert alors une grande importance.
Notre programme, décrit dans l'exposé, est donc le suivant :
1. Donner un sens à ce qu'on appelle une "source générale", opérer une classification des sources, en exhibant des sous-classes intéressantes, reliées notamment à des systèmes dynamiques.
2. Définir une série génératrice (de type Dirichlet) reliée canoniquement à la source et relier la classification des sources à la classification (analytique) de leurs séries de Dirichlet.
3. Exhiber une propriété importante de la source, appelée la "discipline", et, dans le cas des sources dynamiques, donner des conditions suffisantes qui entraînent la discipline.

Les quasicristaux sont des matériaux ordonnés, à l'instar des cristaux habituels, mais sans être périodiques contrairement à ces derniers. Découverts en 1982 et "officialisés" après 10 ans de controverses, ils ont contribué à relancer l'étude des pavages non périodiques, qui en sont un modèle répandu. Dans cet exposé, on s'intéresse à deux problèmes théoriques principaux de ce modèle : d'une part la caractérisation de pavages non périodiques par des contraintes locales (structure des quasicristaux), d'autre part la recherche et l'étude d'un méchanisme de formation de ces pavages qui soit physiquement plausible (croissance des quasicristaux). On donnera quelques résultats marquants ainsi que quelques pistes à explorer.

The combinatorial solution to an autonomous differential equation y´=φ(y) was shown to be the family of increasing φ-enriched trees (Leroux-Viennot). We introduce a generalization of this kind of differential equations that uses the operation of shift-plethysm instead of usual substitution. Its solution is again a family of φ-enriched trees with labels that give information related to the length of each branch.

Les substitutions (c'est-à-dire les morphismes de monoïde libre) engendrent des mots infinis qui peuvent être vus comme des développements soit de réels, soit de séries formelles de Laurent dans des corps algébriques. Dans le cas de substitutions de longueur constante (suites automatiques), les séries ainsi produites sont algébriques. Dans le cas des réels, on obtient en général des nombres transcendants. Après une première partie de survol autour de ces divers types de comportements algébriques, nous nous intéresserons aux développements dits S-adiques, où il ne s'agit plus d'itérer la même substitution, mais de composer un nombre fini de substitutions.

Cet exposé a pour but de présenter la factorisation de Schützenberger dans un cadre général. Nous présentons un théorème général qui permet de l'écrire dans le cas d'une algèbre de Lie quelconque et rappelons les outils nécessaires à sa formulation dans le cadre des structures partiellement commutatives. Nous terminerons en donnant quelques idées concernant des travaux en cours relatifs à l'aller-retour entre bases de PBW et de Radford.

Il est bien connu que l'addition dans un système de numération standard a une complexité linéaire, ce qui est trop lent pour faire un processeur arithmétique efficace. En 1961, Avizienis a donné un algorithme parallèle d'addition en base 10 avec les chiffres {-6, -5, ..., 5, 6} où la retenue ne se propage pas. On obtient ainsi une complexité (en parallèle) constante. Dans le langage de la dynamique symbolique, une telle addition est une fonction locale (sliding block code). Cette technique est utilisée pour accélérer les algorithmes de multiplication et de division.

Dans ce travail nous nous intéressons à des systèmes de numération où la base est un nombre algébrique beta, |beta|>1. Quand tous les conjugués algébriques de beta ont un module différent de 1, on peut trouver un alphabet symétrique de chiffres signés entiers sur lequel faire l'addition en parallèle. Cet algorithme est une généralisation de celui d'Avizienis.

L'algorithme d'addition est simple, mais l'alphabet obtenu est en général plus grand que nécessaire. Nous donnons des bornes inférieures sur la cardinalité minimale d'un alphabet permettant de faire l'addition en parallèle. Nous présentons ensuite une série de cas où la borne est atteinte.

Travail en collaboration avec Edita Pelantová et Milena Svobodová (CTU, Prague)

On introduira le formalisme utilisé par Okounkov et Reshetikhin pour étudier les partitions planes aléatoires, basé sur une représentation de gl(∞). Après avoir expliqué comment calculer avec ce formalisme les statistiques locales pour ces objets, on présentera le phénomène de forme limite déterministe lorsque la taille de ces objets tend vers l'infini. On discutera en particulier l'influence de la forme du « mur du fond » sur lequel s'appuie la partition plane sur ces propriétés statistiques. Travail en collaboration avec S. Mkrtchyan, N. Reshetikhin et P. Tingley.

Références :

pour le formalisme :
A. Okounkov and N. Reshetikhin, Correlation function of Schur process with application to local geometry of a random 3-dimensional Young diagram math.CO/0107056, J. Amer. Math. Soc. 16 (2003), no. 3, 581–603.

notre article :
arxiv.org/pdf/0912.3968

voir article ArXiV http://fr.arxiv.org/abs/1003.4847

Le dual topologique de l'espace des séries en un nombre quelconque, éventuellement infini, de variables non commutatives avec un corps topologique séparé de coefficients, pour la topologie produit, n'est autre que l'espace des polynômes. Il en résulte de façon immédiate que les endomorphismes continus sur les séries sont exactement les matrices infinies mais finies en ligne. Les matrices triangulaires infinies, puisque formant une algèbre de Fréchet, disposent quant à elles d'un calcul intégral et différentiel, que nous développons dans un cadre assez général, et qui permet d'établir une correspondance exponentielle-logarithme de type Lie. Nous déployons ces outils sur l'algèbre de Weyl (à deux générateurs) réalisée fidèlement comme une algèbre d'opérateurs agissant continûment sur l'espace des séries formelles (en une variable). Puis nous démontrons que chaque endomorphisme d'un espace vectoriel de dimension infinie dénombrable peut s'obtenir explicitement sous la forme de la somme d'une famille sommable en des opérateurs plus élémentaires, les opérateur d'échelle (généralisation de l'algèbre de Weyl), précisant de la sorte le théorème de densité de Jacobson. Par dualité (topologique) un résultat similaire concernant les opérateurs continus sur un espace de combinaisons linéaires infinies tombent presque gratuitement. Par ailleurs nous développons la notion d'algèbre (réduite) large d'un monoïde à zéro (obtenue par complétion de l'algèbre réduite) qui nous permet de calculer de nouvelles formules d'inversion de Möbius ainsi que des séries de Hilbert.

- Le jury : Jacques Alev, Claude Carlet , Frédéric Chapoton, Patrick Dehornoy, Gérard Duchamp, Loïc Foissy, Dominique Manchon, Frédéric Patras, Laurent Rigal et Jean-Yves Thibon.

Le problème est de construire des arbres binaires éloignés vis-à-vis de la distance de rotation, ce qui équivaut à construire des expressions parenthésées éloignées vis-à-vis de l'associativité, ou encore des triangulations de polygone éloignées vis-a-vis de l'échange de diagonales. On présentera la magnifique solution de Sleator-Tarjan-Thurston basée sur la géométrie hyperbolique, qui est optimale mais valable seulement pour une taille assez grande (non effective), ainsi qu'une méthode combinatoire basée sur une notion de séparatrice dans les associaèdres, qui est (pour le moment) non optimale, mais valable pour toute taille.

A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G is the maximum number t such that G admits a b-coloring with t colors.Several problems related to b-coloring of graphs have been introduced in the literature. Recently, the theory of b-colorings of graphs has been applied in to some clustering problems in data mining processes. In this talk, we will summarize the last algorithmic and theoretical results obtained on b-coloring and the related notions of b-perfection, b-continuity and b-monotonicity within some graph classes. This is a mix of joint works with C. Betancur, G. Duran, I. Koch, F. Maffray, J. Marenco and M. Valencia-Pabon.

Cet exposé se veut introductif et élémentaire. Je présenterai la version combinatoire du modèle physique du tas de sable comme un jeu consistant à déplacer des jetons sur les sommets d'un graphe connexe. J'introduirai et je donnerai les propriétés des configurations récurrentes de jetons, puis les bijections entre ces configurations et les arbres recouvrants du graphe. Une incursion dans les polynômes de Tutte est ensuite prévue, puis une investigation sur les algorithmes de tirage aléatoire d'arbres recouvrants. Après avoir rappelé ce panorama de travaux remontant aux années 1990-2000, quelques résultats dans des directions nouvelles seront évoqués.

Quelques articles introductifs :

Deepak Dhar (1999)
Studying Self-Organized Criticality with Exactly Solved Models
arxiv.org/abs/cond-mat/9909009

Dominique Rossin et Robert Cori
On the sandpile group of dual graphs
European Journal of Combinatorics 21 (2000) 447-459

Chip-Firing and Rotor-Routing on Directed Graphs
Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuyal Peres, James Propp and David B. Wilson
In and Out of Equilibrium 2
Progress in Probability, 2008, Volume 60, 331-364.

A λ-coloring of a graph is a function that assigns frequencies (represented by natural numbers) to its vertices in such way that if two vertices are adjacent, then their frequencies differ by at least two, and if two vertices share a common neighbor, then their frequencies must be different. Motivated by mobile wireless networks, the λ-coloring problem aims to use the minimum frequency spectrum without interferences, i.e., respecting the distances restrictions. It is known that the decision version of this problem is NP-complete even for simple classes of graphs such as bipartite graphs, split graphs, and planar graphs. In this seminar we talk about recent results in $lambda$-coloring, including efficient solution when it is restricted to the classes of split permutation graphs and (q, q-4)-graphs, q fixed. Joint work with Marcia R. Cerioli.

Given a finite family of non-empty sets F. The intersection graph of F is obtained by representing each set by a vertex, two vertices being adjacent if and only if their corresponding sets intersect. In this talk we will focus on two important intersection graph classes, namely circular-arc graphs (intersection graphs of arc on a circle) and circle graphs (intersection graphs of chords on a circle). We will present some partial characterizations by forbidden induced subgraphs for these classes. Let F be a family of graphs. A graph $G$ is said to be a probe--F graph if its vertex set can be partitioned into two sets: a set P of probe vertices and a stable set N of non-probe vertices in such a way that edges, whose endpoints belongs to N, can be added to G so that the resulting graph belongs to F. We will present some forbidden induced subgraphs characterizations for probe interval graphs and probe unit interval graphs on superclasses of cographs. Finally, we will present a complete forbidden induced subgraphs characterization of probe block graphs. This talk is based on a mix of joint works with F. Bonomo, G. Durán and M. Safe.

Considérons un arbre binaire incomplet : chaque sommet à un fils droit et/ou un fils gauche. Attribuons à la racine l'abscisse 0, et au fils gauche (resp. droit) d'un sommet d'abscisse i l'abscisse i-1 (resp. i+1), comme il se doit.

On démontre une formule produit simple donnant le nombre d'arbres binaires ayant n_i sommets d'abscisse i pour tout i.

On la démontre, on l'adapte à d'autres familles d'arbres, et on la raffine, le tout bijectivement.

Ce travail est réalisé avec Guillaume Chapuy, et motivé par les liens entre les arbres étiquetés et les cartes d'une part, la mesure ISE d'autre part.

Historically, there exist two versions of the Riordan array concept. The older one (better known as recursive matrix and introduced by Barnabei, Brini and Nicoletti) consists of bi-infinite matrices, deals with formal Laurent series and has been mainly used to study algebraic properties of such matrices. The more recent version consists of infinite, lower triangular arrays, deals with formal power series and has been used to study combinatorial problems. The name Riordan arrays has been coined in 1991 by Shapiro, Getu, Woan and Woodson with the aim of defining a class of infinite lower triangular arrays with properties analogous to those of the Pascal triangle. This concept has been successively studied by Sprugnoli in the context of the computation of combinatorial sums. Some other important aspects of the theory have been studied later by Merlini, Sprugnoli and Verri and the literature about Riordan arrays is vast and still growing. After describing the classical properties about this concept, in this talk we present some recent results concerning Riordan arrays related to binary words avoiding a pattern p and show that every Riordan array induces two characteristic combinatorial identities in three parameters n, k, m in Z which are valid in the bi-infinite realm of recursive matrices.

Dans un premier temps, on expliquera comment on produit des mots, au sens d'une source dynamique probabiliste, avec une source ``VLMC'' (Variable Length Markov Chain). Puis, pour une famille de sources VLMC associées à un ``peigne infini'', on construira le trie des suffixes correspondant. On trouvera l'asymptotique de sa hauteur et de son niveau de saturation, qui ne sont pas toujours logarithmiques. On fera le lien entre ce comportement asymptotique et les propriétés de mélange de la source.

Nous considérons la recherche d'éléments dans des structures de données multidimensionnelles (quad trees, k-d trees), en particulier lorsque certaines coordonnées ne sont pas spécifiées (partial match query). Nous supposons que les données consistent en un ensemble de points uniformes dans le carré unité. Pour ce modèle, dans une structure contenant n points, Flajolet et Puech ont montré que le nombre de noeuds C_n(U) à visiter pour répondre à une requête demandant l'ensemble des données dont la première coordonnée est x=U est tel que E[C_n]\sim κ n^β, où κ et β sont des constantes explicites. Nous développons une approche basée sur l'analyse des coûts C_n(s) pour des requêtes à x=s fixé. Nous donnons en particulier des estimations précises de la variance et de la distribution limite de C_n(s) lorsque n\to\infty. Nos résultats permettent de décrire un processus limite pour C_n(s) lorsque s varie dans (0,1).

Travail en collaboration avec Ralph Neininger et Henning Sulzbach.

On sait que les graphes distance-réguliers ou distance-birégulier se caractérisent par le fait que les distances à n'importe quel sommet réalisent de partitions équitables. Pas de panique: les termes mystérieux seront illustrés par des exemples. Qu'arrive-t-il si on prend les distances à d'autres sous-ensembles de sommets?

La percolation de paramètre p, c'est ce qui reste dans Z² quand on efface chaque arête indépendamment avec probabilité 1-p. Quand p est proche de un, il y a une composante connexe infinie. Le TASEP, ce sont des voitures qui avancent de façon aléatoire sur une seule voie, sans se doubler et sans se rentrer dedans. A priori, ça n'a rien à voir.
Le but de cet exposé est de montrer que des estimées sur le TASEP permettent d'obtenir des estimées sur certaines distances dans la composante infinie de percolation, quand p est très proche de un. (Travail avec A.-L.Basdevant et N.Enriquez).

Le but de cet exposé est d'établir des résultats énumératifs sur certaines classes de chemins et d'animaux. Ces résultats sont obtenus en appliquant la théorie des empilements de pièces développée par Viennot. Nous étudions les excursions discrètes (ou chemins de Dyck généralisés) de hauteur bornée ; nous obtenons des résultats énumératifs qui interprètent combinatoirement et étendent des résultats de Banderier, Flajolet et Bousquet-Mélou. Nous décrivons et énumérons plusieurs classes de chemins auto-évitants, dits chemins faiblement dirigés. Ces chemins sont plus nombreux que les chemins prudents qui forment la classe naturelle la plus grande jusqu'alors. Nous calculons le périmètre de site moyen des animaux dirigés, prouvant des conjectures de Conway et Le Borgne. Enfin, nous obtenons des résultats nouveaux sur l'énumération des animaux de Klarner et les animaux multi-dirigés de Bousquet-Mélou et Rechnitzer.

On part d'un opérateur montant M et d'un opérateur descendant D et on étudie le problème physique du "paquet de transfert" (l'ensemble des histoires qui mènent d'un niveau n au niveau n+k). La série génératrice de toutes ces histoires est un langage sur l'alphabet {M,D} qui se spécialise en des fractions continues doubles. D'autre part, l'histoire des réécritures d'une chaîne en M et D se retrouve dans les statistiques de placements de tours (rook numbers) sur des diagrammes de Ferrers qui donne très simplement les constantes de structures de HW. Ceci conduit aux HW-graphes et à leurs couplages qui à leur tour peuvent être déduits de la trace des calculs sur un centre infiniment engendré. Voir:

• Combinatorial Models of Creation-Annihilation Pawel Blasiak, Philippe Flajolet ([Arxiv])
• Combinatorial Algebra for second-quantized Quantum Theory P. Blasiak, G. H. E. Duchamp, A. I. Solomon, A. Horzela, K. A. Penson ([Arxiv])

Dans la première partie de l'exposé, nous présenterons quelques concepts classiques de la théorie des jeux combinatoires : définition d'un jeu, quelques exemples comme le jeu de Nim, Wythoff ou Chomp!, graphe et noyau d'un jeu, position perdante/gagnante, nim-somme, fonction de Sprague-Grundy et somme de jeux, etc.

Ensuite, nous montrerons à travers le "célèbre" jeu de Wythoff, variante du jeu de Nim, des liens existant avec la combinatoire des mots. En effet, il est assez facile de vérifier que le mot de Fibonacci abaababaab..., unique point fixe du morphisme f(a)=ab et f(b)=a, code exactement les positions perdantes du jeu de Wythoff. En outre, des liens entre les mots substitutifs engendrés par morphisme itéré et les systèmes de numération sont bien connus (la voie a été ouverte par Cobham dans son papier de 1972 sur les suites k-automatiques). Ainsi, on peut aussi caractériser les positions perdantes du jeux de Wythoff à l'aide de la numération de Zeckendorf construite sur la suite de Fibonacci 1,2,3,5,8,... Cette caractérisation repose sur des propriétés syntaxiques (testables par automate fini) des représentations dans ce système.

Partant de ces constatations, nous présenterons, dans la dernière partie de l'exposé, quelques travaux récents montrant les interactions "fructueuses" existant entre jeux combinatoires, mots infinis engendrés par morphisme et systèmes de numération associés. Nous évoquerons les questions suivantes : étant donné un mot infini comme le mot de Tribonacci point fixe du morphisme f(a)=ab, f(b)=ac, f(c)=a, peut-on définir un jeu dont les positions perdantes sont codées par ce mot ? Existe-t-il des variantes du jeu de Wythoff (on change l'ensemble des coups admissibles à jouer) possédant le même ensemble de positions perdantes ? Toute suite de Beatty homogène donne-t-elle naissance à un jeu combinatoire invariant pour lequel l'ensemble des coups disponibles ne dépend pas de la position de jeu ?

Quelques références :

A. Fraenkel, Heap Games, Numeration Systems and Sequences, Annals of Combin.. 2 (1998), 197–210.
A. Fraenkel, How to beat your Wythoff games’ opponent on three fronts, Amer. Math. Monthly 89 (1982), 353–361.
voir aussi les pages de Aviezri Fraenkel http://www.wisdom.weizmann.ac.il/~fraenkel/
E. Duchêne, M. Rigo, A morphic approach to combinatorial games : the Tribonacci case, Theor. Inform. Appl. 42 (2008), 375-393.
E. Duchêne, M. Rigo, Invariant games, Theoret. Comp. Sci. 411 (2010), 3169-3180, http://orbi.ulg.ac.be/handle/2268/35496
E. Duchêne, A. Fraenkel, R. Nowakowski, M. Rigo, Extensions and restrictions of wythoff's game preserving wythoff's sequence as set of P positions, to appear in J. Combinat. Theory Ser. A 117 (2010), 545-567, http://orbi..ulg.ac.be/handle/2268/17591

http://www.discmath.ulg.ac.be/publi.html

pour une référence "grand public" sur les jeux combinatoires, voir par exemple les notes :
Thomas S. Ferguson, UCLA, http://www.math.ucla.edu/~tom/Game_Theory/Contents.html

Enfin, pour un survol sur les numérations (avec quelques remarques sur les jeux combinatoires), cf.

M. Rigo, Numeration Systems: a Link between Number Theory and Formal Language Theory, Proceedings of Developments in Language Theory, London, Ontario, Canada (2010), Lect. Notes in Comput. Sci. 6224, 33-53 Springer-Verlag (2010), http://orbi.ulg.ac.be/handle/2268/35488

Soit R une région finie dans le plan carrelé, il y a un nombre fini de manières de la recouvrir avec des dominos. Choisissons un recouvrement au hasard de manière uniforme. Quelle est la probabilité de trouver une configuration donnée dans un endroit donné ? Dans le contexte de problèmes de recouvrement, les deux régions plates finies les plus étudiées sont probablement le rectangle (depuis Kasteleyn (1961)) et le diamant aztèque (Elkies, Kuperberg, Larsen et Propp (1992)). Ces deux cas illustrent deux extrêmes de comportement asymptotique. Les probabilités des configurations locales dans un rectangle ont été déterminées par Kenyon (1997). Nous verrons comme déterminer de manière exacte les probabilités des configurations locales dans un diamant aztèque, avec une esquisse des asymptotiques. Les résultats (et leurs preuves!) sont nettement différents de ceux du cas rectangulaire.

Soit R une région finie dans le plan carrelé, il y a un nombre fini de manières de la recouvrir avec des dominos. Choisissons un recouvrement au hasard de manière uniforme. Quelle est la probabilité de trouver une configuration donnée dans un endroit donné ? Dans le contexte de problèmes de recouvrement, les deux régions plates finies les plus étudiées sont probablement le rectangle (depuis Kasteleyn (1961)) et le diamant aztèque (Elkies, Kuperberg, Larsen et Propp (1992)). Ces deux cas illustrent deux extrêmes de comportement asymptotique. Les probabilités des configurations locales dans un rectangle ont été déterminées par Kenyon (1997). Nous verrons comme déterminer de manière exacte les probabilités des configurations locales dans un diamant aztèque, avec une esquisse des asymptotiques. Les résultats (et leurs preuves!) sont nettement différents de ceux du cas rectangulaire.

We explore the notions of summability and multipliability as they are developed classically in analysis. We give examples in combinatorics where infinite products are supplied and, using the concept of generalized sequence, we give a rigorous framework for these products. Also a contribution to F4M via the exponential formula.

Les modèles d'urnes de Pólya sont des objets très simples mais pour lesquels de nombreuses questions restent ouvertes. Depuis 2005, une approche utilisant la combinatoire analytique s'est développée (Flajolet-Gabarro-Pekari, puis Flajolet-Dumas-Puyhaubert). Nous verrons, à travers des exemples concrets, comment la combinatoire analytique permet d'appréhender ces modèles. Les exemples proposés proviendront des fonctions booléennes, des k-arbres, ainsi que des modèles de croissance de population.

Nous considérons deux processus stochastiques classiques : les urnes d'Ehrenfest, introduites en 1907 pour la théorie cinétique des gaz pour décrire les échanges de chaleur entre deux corps et le modèle d'Engset introduit en 1918 et qui est, avec le modèle d'Erlang, un des tous premiers modèles stochastiques de réseaux de communication. Nous proposons d'étudier le comportement asymptotique de la distribution des temps d'atteinte de ces deux processus lorsque le nombre de particules ou d'utilisateurs croît vers l'infini. En particulier, nous obtenons des résultats sur les temps d'atteinte de frontière. Cette étude repose sur des techniques de martingales et notamment sur une famille de martingales positives qui est l'équivalent pour le processus d'Ehrenfest des martingales exponentielles utilisées pour l'étude des marches aléatoires et du mouvement brownien.

We pursue our exploration of infinite products by examples of complete monoidal factorizations and applications to "Lie" groups which are classic in combinatorics (Riordan, Haussdorff). We construct the Faà di Bruno Hopf algebra through a very simple specialization of the exponential formula. This talk is meant to be a partial contribution to F4M sessions.

We continue our exploration of the combinatorics of groups.
Function spaces are used in order to dualize the product : typically the algebraic dual of the group algebra k[G] is the full function space k^G. In many cases, given a function φ∈ k^G, there exists no nice formula for φ(fg).
But, if we restrict φ to some subspaces, the expression of φ(fg) can be nicely split. Examples will be taken in : Faà di Bruno formula, Free group, Noncommutative Symmetric function. If time permits, we will treat some points of the theory of deformation and some combinatorial aspects of quantum groups.