Résumé: (travail réalisé avec Einar Steingrimmson, Göteborg, Suède)
Dans un article publié en 2000, Backelin, West et Xin ont défini une transformation Φ* qui détruit récursivement toutes les sous-suites décroissantes de longueur k d'une permutation (k est fixé). Cette transformation s'obtient en itérant une transformation élémentaire Φ qui détruit UNE sous-suite décroissante de longueur k.
Ces deux transformations peuvent être étendues à des objets plus généraux que les permutations : des placements de tours sur des diagrammes de Ferrers. Le trio BWX s'est servi de Φ* pour démontrer que, pour tout n, Sn(12...k τ)=Sn(k...21 τ), où Sn(π) est le nombre de permutations évitant le motif π.
Le résultat principal de notre travail est que, très curieusement, la transformation itérée Φ* commute avec l'inversion des permutations (alors que ça n'est pas le cas de la transformation élémentaire Φ). Plus généralement, elle commute avec la symétrie diagonale des placements de tours.
Un corollaire est l'analogue du résultat de BWX pour les involutions : In(12...k τ)=In(k...21 τ), avec des notations évidentes.
La preuve que nous avons donnée comporte une idée agréable et quinze pages d'horreur. Je ne montrerai que la première partie... La conclusion est que la transformation Φ* DOIT pouvoir être décrite d'une façon plus agréable, peut-être en lien avec la bijection de Schensted ou avec une généralisation d'icelle aux placements de tours.
Bref, quelques mystères et du pain sur la planche si certains auditeurs veulent y regarder d'un peu près (et sèchent temporairement sur Razumov and Co.)
Résumé: La famille des cartes bien-ordonnées est une famille de cartes planaires telle que tout graphe planaire connexe admette au moins une telle carte. Nous montrons que le nombre de cartes bien-ordonnées à n sommets est d'au plus 24.91n. Une conséquence directe de ce résultat est une borne supérieure sur le nombre de graphes planaires non-étiquetés à n sommets.
Ce résultat est ensuite utilisé pour montrer qu'asymptotiquement presque tous les graphes planaires ont entre 1.85n et 2.44n arêtes.
De plus nous obtenons un algorithme de codage des graphes planaires non-étiquetés utilisant au plus 4.91 bits par sommet et 2.82 bits par arête.
Finalement, nous verrons comment les techniques utilisées nous permettent d'obtenir une analyse en moyenne de la surface des dessins produits par deux algorithmes de dessin de graphes.
Ce travail a été réalisé en collaboration avec Nicolas Hanusse, Cyril Gavoille, Dominique Poulalhon et Gilles Schaeffer.
Résumé: Les notions de tableaux de Young, correspondance de Robinson-Schensted, congruence et monoïde plactique, sont bien connues et classiques en combinatoire algébrique. F.Hivert, J.C.Novelli et J.Y.Thibon ont récemment introduit un analogue de ces notions pour les arbres binaires avec la congruence sylvestre et le monoïde sylvestre. Ces notions correspondent à un analogue pour les arbres binaires de la correspondance de Robinson-Schensted. Cet analogue est basé sur la combinatoire des arbres binaires de recherche.
En 1978, J.Françon, J.Vuillemin et l'orateur avaient introduit la structure de données "pagode" pour représenter efficacement les files de priorités. La combinatoire sous-jacente à ces structures permet d'introduire un analogue pour les arbres binaires du célèbre jeu de taquin (pour les tableaux de Young) de M.P.Schützenberger.
Une extension de ce jeu de taquin pour les arbres binaires permet alors de retrouver l'algèbre de Loday-Ronco. Un algorithme inspiré de l'algorithmique des pagodes représentant les files de priorité permet alors de calculer directement le produit de deux arbres binaires dans cette algèbre. Ces algorithmes contiennent la bijection exposée il y a quelques temps par l'orateur pour dénombrer les arbres binaires ayant un "profil" (ou "forme" donnée), et conduisant à une formule de Kreweras avec un déterminant binomial.
Rappelons que l'algèbre de Loday-Ronco joue un certain rôle en physique quantique (renormalisation, graphes de Feynman, ...) comme l'ont montré récemment C. Brouder et A. Frabetti.
Résumé: Une algèbre de Hopf "combinatoire" est un espace d'objets dans lequel on peut composer et décomposer les objets, ces deux actions étant mutuellement compatibles.
Il y a 30 ans, Joni et Rota montraientt l'importance de la structure d'algèbre de Hopf en combinatoire en présentant une douzaine d'exemples de structures d'algèbres de Hopf en combinatoire (près de la moitié relatifs à des ensembles partiellement ordonnés).
Depuis, les recherches et les résultats se sont succédés et semblent même s'accélérer sur les dernières années. Je me propose de présenter plusieurs exemples récents d'algèbres de Hopf en combinatoire:
Résumé: On considère des familles de configurations de boucles compactes ayant un couplage des liaisons extérieures fixé.
En particulier, on s'intéresse aux couplages donnés par un nombre croissant m d'arches parallèles et on montre que le nombre des configurations associées est polynomial en m. Ceci démontre 2 conjectures de Zuber et une version asymptotique de la conjecture de Razumov et Stroganov sur les composantes du vecteur propre d'un certain hamiltonien.
Résumé: Michel Mendès-France a défini les tableaux cantoriens comme les tableaux carrés sur un alphabet, tels qu'aucune ligne n'apparaît dans le permanent. Nous considérons le problème du calcul efficace du nombre de tels tableaux sur l'alphabet binaire, et de taille n x n pour n petit.
Par exemple, si n=8, le nombre de tableaux est 264 et nous calculons en 8 secondes que 13896810621 x 28 parmi eux sont cantoriens. Le calcul efficace dépend de trois transformations préservant la propriété cantorienne.
Résumé: Le problème de la validation temporelle d'une application temps-réel consiste à garantir qu'en toutes circonstances, elle sera apte à réagir dans les temps aux évènements qui se présenteront, et ce quelle que soit la durée de fonctionnement. Ce problème est habituellement abordé de deux manières : le mode hors ligne et le mode en ligne. Notons qu'un ordonnanceur en ligne doit systématiquement être validé par une analyse hors ligne, qui repose sur des simulations.
Ces deux approches ont motivé un très grand nombre de travaux dans la communauté temps-réel. Une première direction d'étude a consisté à étudier la puissance des différentes méthodes. Ainsi, s'il existe des algorithmes en lignes optimaux (i.e. capables d'exhiber une solution dès qu'il en existe) dans le cas de tâches indépendantes, il est prouvé qu'il n'est pas possible d'obtenir une politique d'ordonnancement en ligne dès que l'on est en présence de ressources critiques. La simulation devient donc indispensable pour valider les systèmes réels dans lesquels communications et ressources sont omniprésentes. D. Geniet a mis en place, à partir de la technique des produits synchronisés d'Arnold et Nivat une méthodologie hors ligne de validation des systèmes de tâches communiquant et partageant des ressources.
Chaque tâche périodique τi est associée à un automate booléen dont les caractéristiques numériques (nombre d'états et de transitions) dépendent directement des caractéristiques temporelles de τi. Le langage accepté par cet automate est l'ensemble des comportements valides (i.e. indéfiniment prolongeables en respectant les contraintes temporelles) de la tâche.
Notre travail a consisté à prolonger cette méthodologie au cas des tâches apériodiques. La décision de la possibilité d'ordonnancer une tâche apériodique activée à l'instant t repose sur une connaissance suffisante, à l'instant t, de la répartition des périodes d'inactivité des différents processeurs à notre disposition. Dans notre modèle, nous implémentons cette capacité à connaître l'avenir par le biais de fonctions génératrices associées aux états de l'automate modélisant le système formé par l'ensemble des tâches périodiques de l'application. De plus, il nous a été possible de prolonger la modularité du modèle initial en l'enrichissant de fonctions génératrices.
Résumé: Le "nombre de Strahler" est un paramètre, initialement défini sur les arbres binaires, et destiné à décrire la complexité de la forme d'un basin fluvial. Il peut également être interprété comme le nombre de registres nécessaires pour évaluer une expression arithmétique.
En nous inspirant de cette interprétation, nous définissons un paramètre analogue sur tout arbre enraciné; ce paramètre a été utilisé avec succès pour évaluer la "complexité" d'objets arborescents de grande taille.
Nous montrons que le calcul de ce paramètre peut être réalisé en temps linéaire sur tout arbre, et que le "ratio de branchement" d'une famille d'arbres simplement engendrée, au degré borné, a le même comportement que dans le cas des arbres binaires: il converge vers 4.
(Transparents) Résumé: Le modèle du tas de sable a été introduit par Bak, Tang et Wiesenfeld il y a plus de 15 ans pour rendre compte de la notion d'auto-organisation vers la criticalité. Dans sa version la plus simple, ce modèle se définit sur une grille 2D dont les cases contiennent un certain nombre de particules. Une règle locale d'évolution permet de définir une notion d'éboulement. La distribution des avalanches suit alors une loi puissance caractéristique des phénomènes complexes. Alors que ce modèle se généralise très bien à un graphe quelconque, la distribution des avalanches a été très peu étudiée dans ce cas plus général. Celle-ci peut être déterminée par l'étude des propriétés de certaines configurations dites récurrentes.
On se propose ici d'étudier cette distribution pour quelques familles de graphes (les arbres, les cycles, les graphes complets et les graphes lollypop). Le plan sera le suivant:
Résumé: Dans le prolongement d'un exposé datant de 2001, je présenterai un travail en commun avec Philippe Flajolet, Guy Louchard et Gilles Schaeffer.
Comme alternative à la génération aléatoire "classique" d'objets combinatoires, où l'on se fixe une taille d'objets, pour ensuite s'efforcer d'obtenir un objet aléatoire parmi ceux ayant cette taille, nous proposons d'engendrer des objets suivant une distribution répartie sur toute la classe d'objets considérés, de telle sorte que la taille des objets obtenus est elle-même aléatoire; un paramètre réel permet de "contrôler" la taille moyenne des objets, et de "favoriser" les gros objets. Une caractéristique importante de ces distributions "boltzmanniennes" est que des objets de même taille ont toujours la même probabilité: ainsi, conditionné par la taille, l'objet obtenu est uniforme. Pour des objets construits par union, produit, suites, et ensembles ou cycles (dans le cas étiqueté), ce modèle permet d'obtenir des objets de grande taille en temps moyen linéaire, avec un pré-calcul qui demande l'évaluation numérique de séries génératrices et non la manipulation de grandes tables de grands entiers.
Dans un deuxième temps, on s'intéresse, du point de vue théorique, à la complexité, exprimée en nombre de bits aléatoires, de ces algorithmes de génération aléatoire. Il s'agit d'un travail en cours, dont l'ambition est de montrer que, pour de nombreuses classes d'objets (mais pas toutes), la génération d'un grand objet utilisera presque toujours un nombre linéaire de bits aléatoires et ne demandera qu'une précision raisonnable sur les constantes numériques.
Résumé: Dans leurs récents papiers, A. Kuba et M. Nivat ont introduit un modèle de projection avec absorption. Dans ce cas les projections selon une direction ne sont pas données par le nombre de points qui se trouvent sur des lignes parallèles à cette direction mais par des sommes pondérées avec des coefficients. Les auteurs ont montré que, si ces coefficients satisfont une récurrence similaire à celle des nombres de Fibonacci, les projections horizontale et verticale ne sont pas suffisantes pour garantir l'unicité de la solution. Au contraire on montre que les seules projections horizontales, considerées pourtant dans les deux sens, sont suffisantes pour garantir l'unicité de la solution et permettent aussi de définir un algorithme linéaire pour la reconstruction.
Résumé: We review techniques to obtain the asymptotic behaviour of exactly solvable two-dimensional polygon models, counted by perimeter and area. This is used for a numerical analysis of unsolved models like self-avoiding polygons and the planar random loop boundary. In these models, we find the Airy distribution as limit distribution for the area of a loop.
Résumé: Quand on empile des segments sur une bande de largeur n de telle sorte qu'ils forment une demi-pyramide, on retrouve des bijections classiques avec les chemins de Dyck de hauteur maximale n. Quand ces chemins de Dyck se terminent a la hauteur maximale, on peut trouver une bijection avec une modèle combinatoire de gravitation quantique lorentzienne, qui est simplement une triangulation de l'espace-temps. Je présenterai ces bijections pour démontrer que le nombre de segments dans l'empilement est égal à la courbure de la triangulation.
Les empilements de taille bornée peuvent être construits en utilisant le lemme d'inversion. Mais, la récurrence qui donne l'empilement trivial est à n termes. En oubliant les bijections, on peut construire des triangulations d'une manière itérative, d'où on trouve des récurrences a 3 termes avec lesquelles on peut décrire la fonction génératrice par une forme close. Je vais montrer les récurrences et comment la forme close nous donne un espoir d'expliquer les récurrences à 3 termes dans un contexte d'empilements et alors d'écrire les récurrences à n termes sous une forme plus simple. Ceci nous donnerait un moyen d'énumérer tout type d'empilement de segments selon la largeur et le nombre de segments, et pas seulement la longueur totale des segments.
Résumé: We address different types of combinatorial problems which have at their heart the same symmetric function computation, namely the scalar product of symmetric functions. Gessel showed that this operation is D-finite preserving. We make this operation effective with the aid of Groebner bases in the algebra of differential operators.
The first incarnation of the scalar product we consider is as a key part of an automatic asymptotic enumeration scheme, which is quite general in nature. The end result is asymptotic formulas for families of combinatorial structures satisfying certain kind of regularity. The second application of the scalar product illustrates how to use of symbolic calculation to determine the Kronecker product of two generating series of symmetric functions.
Résumé: Soit une partition Λ de n, la cellule bilatère associée est l'ensemble des permutations dont l'image par la correspondance de Robinson-Schensted est de forme Λ.
On montre que l'ensemble des permutations de longueur (i.e., nombre d'inversions) minimale dans une cellule bilatère est l'ensemble des éléments de longueur maximale de sous-groupes de Young conjugués. On donnera une interprétation combinatoire en définissant des tableaux particuliers, les tableaux lisibles par colonnes, qui sont en bijection avec les éléments de longueur maximale des sous-groupes de Young.
Résumé: Nous considérons des chemins dirigés avec pas horizontaux et verticaux qui vivent dans une région donnée, bornée par deux autres chemins du même type qui ne se coupent pas.
Si on regarde les pas horizontaux de notre chemin, il y a deux types de pas qui sont spéciaux: ceux qui touchent la borne inférieure, appelés minima, ou supérieures, appelés maxima.
Nous verrons une bijection - en fait, une involution - qui transforme le chemin en un autre, et telle que le nombre de minima du chemin original soit le nombre de maxima du chemin transformé, et vice versa.
On considère un marcheur sur le plan coupé, à savoir, le plan privé de son demi-axe x négatif. Notre marcheur démarre à l'origine du plan, et fait des pas pris dans un ensemble donné. Par exemple, l'ensemble de pas {(1,1), (1,-1), (-1,1), (-1,-1)} contient les pas nord-est, nord-ouest, sud-est, sud-ouest.
Son chemin va se terminer au point de l'axe x positif, le plus proche possible de l'origine. Dans l'exemple ci-dessus, c'est le point (2,0).
Notre marcheur ne doit pas retourner à l'origine, et il ne doit pas toucher l'axe x négatif, ce qui veut dire qu'aucun des pas ne doit se terminer sur ce demi-axe. Par contre, s'il y a un pas dans l'ensemble avec une composante verticale supérieure ou égale à deux, le marcheur peut traverser l'axe.
La question, posée par Mireille Bousquet-Mélou, est la suivante: la série génératrice qui compte ces chemins, est-elle algébrique?
Nous verrons que, si l'ensemble des pas est un produit cartésien, la série génératrice est algébrique, si et seulement si le marcheur ne peut pas sauter l'axe négatif, ce qui était la condition conjecturée par Mireille.
Résumé: Les q-analogues des fonctions de Bessel sont des objets rencontrés depuis longtemps par le groupe de combinatoire bordelais (travaux de Delest, Fedou, Lalanne, ...). Cet exposé s'adresse surtout aux "nouveaux", mais les "anciens" pourront aussi se rafraîchir la mémoire. Je reprend avec une touche de nouveauté certains résultats anciens et quelques autres inédits.
Les fonctions de Bessel, et aussi certains de leurs q-analogues apparaissent dans plusieurs résolutions exactes de modèles provenant de la physique statistique: polyominos parallélogrammes (polygones en escalier), modèle SOS (chemin en interaction avec un mur) et aussi de la physique quantique (gravitation quantique Lorentzienne en dimension 2). Il s'agit d'articles de R.Brak, T.Guttmann, T.Prellberg, A.Owczarek, S.Whittington (pour la physique statistique) et J.Ambjorn, R.Loll, P.Di Francesco, E.Guitter, C.Kristjansen (pour la gravitation quantique).
Je montrerai que ces trois apparitions ont une explication "bijective" commune en utilisant le modèle des empilements de segments. Il s'agit d'un travail de l'orateur, avec contributions de M.Bousquet-Mélou et W.James. Je parlerai enfin d'une formule relative à certains polymères modélisés par des chemins avec interactions mutuelles entre voisins.
Résumé: There is a nice invertible linear transformation that takes the polynomial nd to the Eulerian polynomial Ad. The same transformation takes the chromatic polynomial of an arbitrary graph to a polynomial P(G) that can be given a combinatorial interpretation related to that for the descent statistic associated to Ad.
Using this interpretation, we define a monomial ideal in a certain Stanley-Reisner ring and an associated simplicial complex C. The monomials in K are in one-to-one correspondence with the proper colorings of G and the h-vector of C is essentially equal to P(G).
I will explain the combinatorial ideas underlying this construction, and try to give a glimpse of what the ideal and complex (might) say about the graph. I will try to avoid technicalities but explain the necessary background.
Résumé: Many enumeration problems cannot be exactly solved. Self-avoiding walks and polygons in dimension ≥2 are well-known examples. In that case it is desirable to have enumerations of as many objects as possible. That is to say, p_n may denote the number of polygons of perimeter (or area) n. We wish to determine p_n for n as large as possible. Unfortunately, direct enumeration is a problem of exponential complexity, that rapidly becomes intractable. The Finite Lattice Method, while still of exponential complexity, reduces the growth rate. The Corner Transfer Matrix method, introduced by Baxter, offers the possibility of exp(n1/2) complexity. We will describe both these methods.