2013-2014
Vendredi 4 juillet : Paul Dorbec
Titre : Une introduction à la théorie des jeux combinatoires (2/2)
Résumé :
Cf. (1)
Remarque du secrétaire, après discussion avec l'orateur : ce dernier fera les rappels nécessaires pour permettre à tous de suivre cette séance, qu'ils aient assisté ou non à la première.
Mercredi 25 juin : (Petite École de Combinatoire) Vincent Delecroix
Titre : Sage (6) : contribuer à Sage
Résumé : Cf. (1) ou http://wiki.sagemath.org/GroupeUtilisateursBordeaux
Mardi 24 juin : (Petite École de Combinatoire) Vincent Delecroix
Titre : Sage (5) : C/C++ dans Python (et Sage)
Résumé : Cf. (1) ou http://wiki.sagemath.org/GroupeUtilisateursBordeaux
Vendredi 13 juin : Philippe Duchon
Titre : Arbres binaires, permutations et ordres d'insertion
Résumé :
On dispose d'une formule très simple pour le nombre d'ordres d'insertion donnant un arbre binaire de forme donnée (ou, de manière équivalente : pour le nombre d'étiquetages des nœuds d'un arbre binaire par les entiers de 1 à sa taille, de manière croissante le long des branches).
Mais cette formule ne se traduit pas naturellement en un algorithme de génération aléatoire simple.
Je décrirai deux algorithmes de génération aléatoire uniforme de tels ordres :
l'un est asymptotiquement optimal en bits aléatoires, mais nécessite de manipuler de grands nombres.
Le second, basé sur une bijection, permet de ne travailler qu'avec des entiers allant jusqu'à la taille de l'arbre, mais n'est pas optimal en bits aléatoires.
Mardi 3 juin : (Petite École de Combinatoire) Vincent Delecroix
Titre : Sage (4) : combinatoire
Résumé : Cf. (1) ou http://wiki.sagemath.org/GroupeUtilisateursBordeaux
Lundi 26 mai : Steve Melczer http://www.sfu.ca/~srm9/, Simon Fraser University, Vancouver, Canada
Titre : Asymptotic Lattice Path Enumeration Using Diagonals
Résumé : Combining the kernel method with multivariate generating function analysis, we determine general formulas for the dominant asymptotics of counting sequences of walks restricted to the first orthant. The step sets under consideration are symmetric with respect to each axis, which is a strong condition, however the resulting formulas are very straightforward. The exponential growth of each model is given by the number of steps, while the sub-exponential growth depends only on the dimension of the underlying lattice and the number of steps moving forward in each coordinate. These expressions are derived by analyzing the singular variety of a multivariate rational function whose diagonal counts the lattice paths in question.
Vendredi 23 mai : Fedor Pakovich http://www.math.bgu.ac.il/~pakovich/, Ben-Gurion University of the Negev http://in.bgu.ac.il/en/Pages/default.aspx, Israël
Titre : On semi-conjugate rational functions
Résumé : A classification of commuting rational functions, that is of rational solutions of the functional equation A(X) =X(A), was obtained in the beginning of the past century by Fatou, Julia, and Ritt. In the talk we will present a solution of a more general problem of description of semi-conjugate rational functions, that is of rational solutions of the functional equation A(X) =X(B) in terms of groups acting properly discontinuously on the Riemann sphere or complex plane.
Mardi 20 mai : (Petite École de Combinatoire) Vincent Delecroix
Titre : Sage (3) : graphes et programmation linéaire
Résumé : Cf. (1) ou http://wiki.sagemath.org/GroupeUtilisateursBordeaux
Mardi 6 mai : (Petite École de Combinatoire) Vincent Delecroix
Titre : Sage (2) : utilisation plus avancée et programmation
Résumé : Cf. (1) ou http://wiki.sagemath.org/GroupeUtilisateursBordeaux
Vendredi 18 avril (Petite École de Combinatoire) Vincent Delecroix
Titre : Sage (1)
Résumé :
Sage (http://sagemath.org) est un logiciel libre de mathématiques.
Dans cette séance nous installerons Sage sur les machines des participants (si ce n'est pas déjà fait) et nous verrons la prise en main des différents modes.
Cf. http://wiki.sagemath.org/GroupeUtilisateursBordeaux
Vendredi 11 avril : Paul Dorbec
Titre : Une introduction à la théorie des jeux combinatoires (1/2)
Résumé : Un jeu combinatoire est un jeu à deux joueurs, sans hasard, à information complète, et qui se termine toujours par la victoire d'un joueur. En d'autres termes, un jeu combinatoire est un jeu dont on devrait connaître l'issue avant le début du jeu. Dans cet exposé, nous verrons ce que sont les jeux combinatoires, quelles sont les questions que l'on se pose, comment on essaye d'y répondre et pourquoi c'est difficile. Éventuellement, pour faire plaisir aux combinatoriciens maladifs, nous compterons quelques jeux !
Vendredi 4 avril : Adrien Boussicault
Titre : Les tableaux boisés de Baxter 2/2
Fridays, March 28th: Adrien Boussicault
Title: Les tableaux boisés de Baxter 1/2
Abstract:
Les permutations de Baxter tordues sont les permutations qui évitent les motifs 3-14-2 et 2-41-3.
Il existe de nombreux objets combinatoires en bijection avec eux : des triplets de chemins, des pavages du rectangle, des paires d'arbres jumeaux.
Dans cet exposé, nous proposons de revisiter toutes ces constructions en utilisant le point de vue des tableaux boisés.
Nous allons montrer que les tableaux boisés contiennent une partie de toutes ces constructions.
Il offre ainsi un cadre simple et unifié pour mettre en correspondance tous ces objets et pour redémontrer simplement quelques formules d'énumération.
Enfin, si le temps le permet, nous verrons aussi que l'algorithme d'insertion des tableaux boisés nous permet de proposer de nouvelles approches pour énumérer les permutations de Baxter tordues.
Ce travail a été réalisé en collaboration avec J.-C. Aval, M. Bouvel, O. Guibert et M. Silimbani.
Friday, February 21th: Mireille Bousquet-Mélou
Title: Chemins de l'espace confinés dans un octant
Abstract:
Ces dernières années, l'étude des chemins du plan confinés dans le quart de plan positif a occupé un certain nombre de combinatoristes, mais aussi de probabilistes, et mené à des résultats souvent attrayants.
Au centre de ceux-ci, une jolie classification : la série génératrice de ces chemins est holonome (= différentiellement finie) si et seulement si un certain groupe, construit à partir de l'ensemble des pas autorisés, est fini.
Il est naturel de se demander ce qui, de ce résultat et des méthodes utilisées pour le prouver, survit lorsqu'on passe en dimension trois.
C'est ce qu'on fera dans cet exposé.
Travail en commun avec Alin Bostan (INRIA Saclay), Manuel Kauers (RISC Linz) et Steve Melczer (SFU Vancouver).
Friday, February 7th: Jérôme Casse
Title: Automates cellulaires probabilistes à loi invariante markovienne
Abstract:
Un automate cellulaire probabiliste (ACP) à 2 voisins sur la ligne est un algorithme probabiliste qui transforme un mot bi-infini w au temps t sur un alphabet A en un autre mot bi-infini w' au temps (t+1) de telle sorte que la probabilité de la lettre w'(i) ne dépend que des lettres w(i) et w(i+1).
De plus, les transformations des lettres du mot sont synchrones, indépendantes et de même loi.
Ainsi, lorsque l'on part d'une configuration aléatoire (ou non), on peut itérer notre ACP et nous demander s'il existe une loi invariante ou non.
Un résultat classique, dû à Toom & al., affirme que la chaîne de Markov de noyau de transition M est invariante ssi M satisfait un système d'équation algébrique dépendant de l'automate.
Dans le cas d'un alphabet à deux lettres, cette condition se simplifie : il suffit de la seule donnée de l'automate pour savoir s'il possède une chaîne de Markov invariante (la condition porte seulement sur l'automate, pas sur M) [Beliaev & al.].
Une question se pose alors : ne pourrait-on pas obtenir une condition semblable dans le cas d'un alphabet avec plus de 2 lettres ?
Nous montrerons que la réponse est oui.
De plus, cette réponse nous fournit également la chaîne de Markov invariante.
L'approche utilisée est algébrique et permet aussi d'adapter le résultat obtenu aux automates à 2 voisins sur le tore, étendant ainsi les résultats de Mireille Bousquet-Mélou sur les modèles de gaz sur le tore.
Vendredi 31 janvier : Jean-François Marckert
Titre : Probabilité que n points soient en position convexe dans un disque
Résumé :
Mettez n points au hasard dans un domaine D compact du plan, selon la loi uniforme sur D.
Quelle est la probabilité que ces points soient en position convexe ?
Autrement dit, quelle est la probabilité qu'ils forment l'ensemble des sommets d'un polygone convexe ?
Cette question posée en 1865 par Sylvester a été résolue dans le cas où D est un parallélogramme ou un triangle par Valtr en 1996 et 1997, résultats retrouvés par Buchta en 2009.
Les résultats sont simples, et s'écrivent sous la forme de quotients de produits de coefficients binomiaux.
Dans cet exposé, j'essaierai d'expliquer les approches de ces auteurs, et l'on verra pourquoi il s'agit ici de questions de combinatoire, quoique de nature continue.
Bien sûr, le titre de l'exposé sera également illustré par un nouveau résultat, par une nouvelle formule, et par une approche également combinatoire, quoique continue et probabiliste.
Vendredi 17 janvier : Vincent Delecroix
Titre :
Mesures Markov-uniformes sur la droite, le plan et les arbres
(travail en cours avec Irène Marcovici)
Résumé : La distribution uniforme sur les mots de taille fixée d'un langage régulier (dont l'automate est fortement connexe) tend vers une mesure sur les mots infinis lorsque la taille des mots grandit. Cette mesure est appelée mesure de Parry. Cette mesure peut être caractérisée par une propriété dite de Markov uniforme ou encore par le fait qu'elle maximise l'entropie. Cette première propriété peut être mise à profit pour faire de la génération aléatoire uniforme de mots finis dans le langage (cf. exposés de P. Duchon et A. Boussicault). Dans le plan, regardant des mots 2-dimensionnels avec une condition de type fini sur les voisins, il peut y avoir plusieurs mesures qui maximisent l'entropie ! En particulier la convergence des mesures uniformes sur des mots carrés n'est pas donnée. Dans le cas des arbres, sur lesquels la notion d'entropie ne fait plus sens, les mesures Markov uniformes existent encore ! Dans certains cas, ces mesures sont des extrema locaux du f-invariant (qui s'apparente à une limite de l'entropie libre de Bethe). Nous verrons également qu'en général les mesures uniformes sur les motifs finis ne convergent plus forcément. On conjecture cependant un comportement « cyclique » que je tacherai d'expliquer.
Vendredi 10 janvier : Romaric Duvignau
Titre : Un nouvel arbre de génération pour les permutations, préservant les points fixes
Résumé : Nous décrivons un nouvel arbre de génération uniforme pour les permutations, ayant la propriété que, pour la majorité des permutations, tous leurs descendants ont le même nombre de points fixes ; notre arbre est optimal en ce sens. Grâce à cet arbre, nous obtenons un nouvel algorithme de génération aléatoire uniforme de dérangements, algorithme qui nécessite, en moyenne, n+o(n) appels à un générateur de nombres aléatoires ; ainsi qu'une méthode combinatoire de simulation exacte de la loi de Poisson de paramètre 1, et de la loi Binomiale(n,1/n) dans un contexte particulier.
Vendredi 20 décembre : Philippe Nadeau, Institut Camille Jordan de l'université Lyon 1, http://math.univ-lyon1.fr/~nadeau/
Titre : Longueur des éléments pleinement commutatifs et algèbres de Temperley-Lieb généralisées
Résumé :
Un élément d'un groupe de Coxeter W est dit « pleinement commutatif » si deux quelconques de ses décompositions réduites peuvent toujours être liées par une suite de commutations de lettres adjacentes.
Ces éléments ont été étudiés en détail par J. Stembridge dans le cas où W est fini, et dans un travail commun avec R. Biagioli et F. Jouhet dans le cas W affine.
Ils indicent naturellement des algèbres généralisant celle de Temperley-Lieb.
Nous étudierons ici la longueur de ces éléments pour un groupe de Coxeter quelconque, et montrerons que la série génératrice correspondante est rationnelle.
Nous classifierons aussi les groupes de Coxeter pour lesquels la suite énumérant ces éléments selon la longueur est ultimement périodique.
Ces résultats permettent de comprendre la fonction de croissance dans les algèbres de Temperley-Lieb.
Vendredi 13 décembre : Nicolas Bonichon
Titre : Sur la L1-réalisabilité des triangulations
Résumé : On dit qu’une triangulation T (carte planaire dont toutes les faces internes sont des triangles) est Delaunay réalisable s’il existe un nuage de points P tel que la triangulation de Delaunay associée à ce nuage de point est égale à T. Dans cet exposé nous nous intéressons à la Delaunay réalisabilité des triangulations pour la norme L1. Nous présenterons des conditions nécessaires puis des conditions suffisantes pour qu’une triangulation soit L1-Delaunay réalisable. Les résultats présentés font intervenir un représentant de la famille des objets comptés par Baxter.
Vendredi 6 décembre : Robert Cori
Titre : Calcul du rang des configurations pour certaines familles de graphes (Cliques, Roues)
Résumé :
Une configuration sur un graphe est définie par des valeurs entières (positives ou non) attribuées à tous ses sommets.
Une configuration est équivalente à une effective si par une suite d'éboulements (dans le modèle du tas de sable) on peut aboutir à une configuration sans aucune valeur négative.
Le rang d'une configuration u est un de moins que le plus petit degré (somme des valeurs des sommets) d'une configuration qui soustraite de u donne une configuration qui n'est pas équivalente à une effective.
Ce rang est difficile à calculer en général, on étudiera deux exemples où un algorithme de calcul simple existe.
Le premier concerne les graphes complets, il permet d'obtenir une formule élégante pour la série génératrice décrivant les degrés et rangs.
Le second est celui des graphes ayant la forme d'une roue (cycle dont tous les sommets sont reliés à un sommet central), pour ce cas seules des conjectures seront proposées.
(travail en commun avec Yvan Le Borgne)
Vendredi 29 novembre : Alexandre Zvonkine
Titre : Quoi de neuf sur les arbres pondérés ?
Résumé : Un arbre pondéré est un arbre plan bicolorié dont les arêtes sont munies de poids entiers positifs. Le degré d'un sommet est ainsi défini comme la somme des poids des arêtes incidentes à ce sommet. L'intérêt de ces arbres s'explique par le fait qu'ils correspondent aux polynômes complexes ayant certaines propriétés extrémales. Nous nous intéressons aux invariants combinatoires de l'action du groupe de Galois sur les polynômes en question. Le plus simple de ces invariants est l'assortiment de degrés des sommets de l'arbre. Une nouveauté : pour tous les arbres qui sont uniques pour leur assortiment de degrés, les polynômes correspondants (qui sont du surcroît à coefficients rationnels) sont calculés. Un invariant plus difficile à déceler est le groupe de monodromie. Une nouveauté : tous les groupes de monodromie primitifs sont classifiés (à part certains cas triviaux, ils sont en nombre fini). Parfois, on observe des invariants de type « diophantien » : un exemple sera montré où l'étude d'une orbite de Galois se réduit à l'équation de Pell. Enfin, si le temps le permet, on ajoutera quelques mots sur l'énumération des arbres pondérés.
Vendredi 22 novembre : Xavier Viennot
Titre : Canopée des arbres binaires et intervalles genevois de l'associaèdre (2/2)
Résumé : Cf. (1/2)
Vendredi 15 novembre : Xavier Viennot
Titre : Canopée des arbres binaires et intervalles genevois de l'associaèdre (1/2)
Résumé : L'associaèdre est un polyèdre dont les sommets sont en bijection avec les arbres binaires de taille donnée. De nombreux travaux récents lui sont consacrés, en particulier sur les intervalles du treillis de Tamari sous-jacent. Nous rappelons la notion de canopée d'un arbre binaire, qui est l'analogue pour les arbres binaires de la forme (suite des montées et descentes) des permutations. Nous étudions le comportement de cette notion de canopée relativement à l'ordre de Tamari. Certains intervalles apparaissent. Leur taille est donnée par certains déterminants de Kreweras. Une extension à deux paramètres de ces déterminants vient d'être donnée par Olya Mandelstam, résolvant un problème du classique modèle du TASEP en physique des systèmes dynamiques. Si le temps le permet, nous envisagerons le comportement de ces considérations lors du plongement de l'associaèdre dans le permutoèdre, polyèdre dont les sommets sont en bijection avec les permutations.
Vendredi 8 novembre : Mireille Bousquet-Mélou
Titre : Coins Nord-Est dans les chemins du quart de plan
Résumé :
Au cours des travaux sur les permutations triables par deux piles (présentés au GT il y a quelques semaines) sont apparues des conjectures portant sur la combinatoire des chemins du quart de plan, pondérés par le nombre de coins Nord-Est (c'est-à-dire de facteurs NW et ES).
On fera le point sur ces conjectures, et sur ce qu'on est en état de prouver dans le même sens.
Le tout suggère qu'une jolie combinatoire nous échappe encore.
Cet exposé ne demande pas d'avoir suivi celui sur les permutations triables par deux piles.
(travail en commun avec Michael Albert, Dunedin, Nouvelle-Zélande)
Vendredi 25 octobre : Adrien Boussicault
Titre : Génération aléatoire uniforme dans les langages rationnels (suite)
Résumé :
Dans le précédent exposé, Philippe nous a montré comment il était possible de générer aléatoirement et uniformément un mot tiré d’un langage rationnel particulier.
Il a utilisé pour cela une marche aléatoire biaisée dans un graphe.
Il a montré que, pour déterminer les bonnes probabilités à mettre sur les arêtes de ce graphe, il fallait résoudre un système d’équations particulier.
Dans cet exposé, nous allons montrer comment il est possible de réduire la résolution du système à une équation algébrique particulière en utilisant l’algorithme de McNaughton-Yamada.
Nous montrerons aussi que la solution du système existe toujours et qu’elle est unique, et nous donnerons une interprétation combinatoire de la solution à l’aide des séries de chemins dans le graphe.
Vendredi 18 octobre : Mireille Bousquet-Mélou
Titre : Permutations triables par deux piles en parallèle
Résumé :
On sait depuis certains travaux de Knuth que si on dispose d'une pile, on peut trier Cn permutations de longueur n, où Cn est le énième nombre de Catalan.
C'est facile à voir, car chaque permutation triable ne peut être triée que d'une façon possible, et les « mots de tri » sont les mots de Dyck.
Et si on a deux piles, placées en parallèle ?
Combien de permutations de longueur n peut-on trier ?
Les choses se compliquent, car il y a en général plusieurs façons de trier une permutation (triable).
Toutefois, on peut décrire un ensemble de mots de tri canoniques, en bijection avec les permutations triables, et on réussit à les dénombrer — du moins à caractériser leur série génératrice par un système d'équations —.
Les mots de tri sont maintenant des chemins de Dyck en dimension 2, c'est-à-dire des chemins dans le quart de plan.
L'étude du comportement asymptotique du nombre de permutations triables repose sur des conjectures, qui résistent, portant sur le dénombrement de ces chemins pondérés par le nombre de virages NW et ES.
Travail est en commun (et en cours, et depuis 2008) avec Michael Albert, de Dunedin, Nouvelle-Zélande.
Pour les « anciens » du groupe, il n'y a pas grand lien avec les permutations triables par deux piles à la West-Zeilberger.
Vendredi 4 octobre : Philippe Duchon
Titre : Génération aléatoire uniforme dans les langages rationnels
Résumé :
Les algorithmes de génération de mots aléatoires uniformes (de longueur n fixée) dans un langage rationnel, langage typiquement décrit par un automate, abondent dans la littérature.
Les meilleurs ont comme point commun de travailler en temps linéaire ou quasi linéaire après un pré-calcul qui revient, d'une manière ou d'une autre, à compter combien il existe de mots de différentes longueurs ; ce pré-calcul est donc à refaire, ou à affiner, si la longueur des mots qu'on engendre change.
La voie que nous explorons, consiste à trouver, dans le graphe orienté défini par l'automate du langage, une marche aléatoire biaisée qui donne « presque » des mots uniformes ; le « presque » étant contrôlé par un rejet.
On obtiendrait alors un algorithme de génération aléatoire (exactement) uniforme, dont la complexité moyenne serait linéaire, après un pré-calcul qui aurait la propriété remarquable de ne pas dépendre de la longueur des mots à engendrer.
Sans surprise pour les habitués, les suites de comptages sont remplacées par des évaluations de séries génératrices.
Dans ce travail en cours avec Adrien Boussicault, on montrera que ce programme peut être mené à bien au moins dans le cas particulier où le graphe orienté défini par l'automate est fortement connexe.
Le cas de graphes non fortement connexes reste ouvert, ou en cours, selon qu'on est optimiste ou non.
Vendredi 20 septembre : Mireille Bousquet-Mélou
Titre : Compression d'arbres
Résumé :
Il est classique de compresser des arbres en DAG (graphes acycliques orientés) en identifiant les sommets auxquels le même sous-arbre est attaché.
Combien de place a-t-on ainsi gagné, en termes de nombre de sommets ou d'arêtes ?
Flajolet, Sipala et Steyaert ont énoncé en 1990 des résultats (hélas sans preuve) sur ces questions.
Par exemple, un arbre binaire à n sommets donnerait, en moyenne, un DAG de taille n/sqrt(log n), et cela semble être le cas pour de nombreuses autres familles d'arbres.
On expliquera pourquoi ce résultat est vrai, et envisagerons quelques variations sur ce thème.
Travail en commun avec Markus Lohrey et Eric Noeth, Leipzig.
Vendredi 13 septembre : Bétréma
Titre : Permutations polonaises
Résumé : Les permutations polonaises (terminologie personnelle) sont celles qui sortent de la « trieuse à une pile », elles ont été étudiées par Mireille Bousquet-Mélou (FPSAC 1998) et Mathilde Bouvel en a parlé ici au printemps. Je présenterai un algorithme simple qui factorise toute permutation en produit de permutations polonaises, et montrerai que cette factorisation est unique si elle est de longueur minimale. N. B. : dans cet exposé il s'agit du produit dans le monoïde des mots (concaténation), et non du produit usuel des permutations (composition).