L'image de fond est un animal dirigé aléatoire. Consultez le programme 1996-97.
Fonctions harmoniques sur le graphe orienté, infini, et gradué, du triangle de Pascal.
Le graphe a pour sommets (de niveau n) les couples (k,n), avec 0 <= k <= n; deux arcs sont issus de (k,n), vers (k,n+1) et (k+1,n+1). Une fonction f, définie sur les sommets, est dite harmonique si :
Par définition, la donnée d'une fonction harmonique est équivalente à la donnée de la suite de ses moments, s(n) = f(0,n), qui est positive et complètement croissante, ie : la suite des différences de s(n) est positive, de même que la suite des différences de différences, et ainsi de suite.
Les fonctions harmoniques sur ce réseau forment un espace convexe, dont le bord (ensemble des points extrêmaux) est constitué des fonctions f(k,n)=p^k*q^(n-k), où p est un paramètre compris entre 0 et 1, avec q=1-p.
Si gamma(a,b) désigne le nombre de chemins de a vers b, et si l'on fixe b, la fonction a -> gamma(a,b)/gamma(0,b) est une fonction quasi-harmonique : elle est harmonique, sauf en b. Les fonctions extrêmales sont obtenues comme limites des précédentes, lorsque b=(k(n),n) s'éloigne à l'infini, avec lim k(n)/n = p.
Unicité de la fonction harmonique sur un graphe stationnaire. Cas des chemins dans un arbre régulier (infini). Graphe des idéaux d'un ensemble partiellement ordonné P : le triangle de Pascal correspond au cas où P est constitué de deux copies disjointes de N (ensemble des entiers naturels), le treillis de Young à celui où P = N x N. Représentations d'une limite inductive de groupes.
Polynômes symétriques, en particulier polynômes de Schur ; exemples de fonctions harmoniques sur le treillis de Young ; liste des fonctions harmoniques extrêmales : elles dépendent de trois paramètres, deux suites positives décroissantes \alpha et \beta, et un nombre positif \gamma tels que \sum \alpha_i + \sum \beta_i + \gamma = 1.
Les fonctions harmoniques indécomposables (ou extrêmales) correspondent aux homomorphismes entre l'anneau des fonctions symétriques et R (anneau des réels). La formule de Jacobi-Trudi entraîne que le calcul de ces homomorphismes est équivalent à celui des suites totalement positives, problème résolu par Schoenberg et autres vers 1950.
Chapitre IV : applications à la biologie.
I propose to begin with the Gessel-Viennot formula for counting lattice paths in terms of binomial determinants, show an application to Hodge's formula for the Hilbert functions of classical Schubert varieties, and then the extension of the formula for counting lattice path with turns (the work of Krattenthaler et al) and applcations to enumeration of Young bitableaux or Hilbert functions of determinantal ideals. If time permits, I may also mention some recent work of Krattenthaler and myself on using lattice path techniques to determine the so called a-invariant of det'l rings.
There is a recent, wonderful book by Roth and Sotomayor on matching theory from an econometric point of view. I will discuss some of the major points of this theory, which includes some surprising and mathematically appealing results, and also mention recent work by Johan Karlander (KTH) and myself on matchings in a labor market where some of the agents are, in a certain sense, moral while some are immoral!
Voir Stable matching in an assignment model with both "rigid" and "flexible" agents (draft) par Johan Karlander et Kimmo Eriksson (8 pages en format dvi, 30K).
Assume we are given a permutation matrix. Shadow all squares to the right of each dot and below each dot in the permutaion matrix. Now, some areas are left white. The set of right-down corners of these areas is called the essential set of the permutation. This definition was made in 1992 by algebraic geometer W. Fulton. He gave a characterization of the essential set for so called vexillary permutations and asked for a general characterization. In an article with Kimmo Eriksson, we solve this problem of a characterization. We also went on and studied enumerative properties of the essential set and found that it was a good tool for examining some questions concerning forbidden patterns in permutations and permutation statistics.
L'énumération selon le périmètre des polygones (non-intersectants) tracés sur un réseau est un célèbre problème ouvert en combinatoire et en physique statistique [1]. La difficulté de la question (seuls des résultats asymptotiques non rigoureux --- mais très vraisemblables --- sont connus) a conduit à l'étude de sous-familles de polygones, en particulier celle des polygones convexes. En 1984, la série génératrice selon le périmètre des polygones convexes tracés sur le réseau carré a été donnée par Delest et Viennot [2].
Nous présentons une méthode, une idée plutôt, qui permet d'énumérer les polygones convexes sur les réseaux carré et cubique, et serait également applicable pour un réseau hypercubique de dimension quelconque [3]. Sur réseau carré, la méthode utilisée permet d'interpréter combinatoirement la forme de l'expression obtenue par Delest et Viennot. Le résultat concernant le réseau cubique est nouveau.
[1] N. Madras et G. Slade, The self-avoiding walk, in Probabilities and its applications, Birkhauser 1993 (Boston).
[2] M.-P. Delest et G. Viennot, Algebraic languages and polyominoes enumeration, Theoret. Comput. Sci. 34 (1984) 169--206.
[3] M. Bousquet-Mélou et Anthony J. Guttmann, Enumeration of three-dimensional convex polygons.
Eric Sopena, sopena@labri.u-bordeaux.fr, gère le groupe de travail frère : "Mots et graphes, combinatoire algorithmique", le vendredi à 15h30.