Liste des événements uniques du groupe Combinatoire Énumérative et Algébrique


2018-07-14(REPORTÉ)
10:45-11:45
076
 Plus d'infos  


2018-07-14(ANNULÉ)
10:45-11:45
076
 Plus d'infos  


2018-06-08
10:45-11:45
076
 Plus d'infos  


2018-05-18
09:30-10:30
076
 Plus d'infos  


2018-05-18
10:45-11:45
076
 Plus d'infos  


2018-04-27
10:45-11:45
076
 Plus d'infos  


2018-03-16
10:45-11:45
076
 Plus d'infos  


2018-03-02
10:45-11:45
076
 Plus d'infos  


2018-02-16
10:45-11:45
076
 Plus d'infos  


2018-02-09.../...
10:45-11:45
076
 Plus d'infos  


2018-02-02.../...
10:45-11:45
076
 Plus d'infos  


2018-01-19.../...
10:45-11:45
076
 Plus d'infos  


2018-01-12
10:45-11:45
076
 Plus d'infos  


2017-12-22A bijection for essentially 4-connected toroidal triangulations
10:45-11:45
076
.../...
 Plus d'infos  


2017-12-15Une extension des triangles de Pascal et de Sierpinski aux mots finis
10:45-11:45
076
Le coefficient binomial binomial(u,v) de deux mots u et v est défini comme le nombre de fois que le mot v apparaît comme sous-suite du mot u. Par exemple, binomial(abbab,ab)=4. Il étend de manière naturelle le coefficient binomial de deux entiers. Ce concept a été largement étudié depuis plus d'une trentaine d'années (consulter, par exemple, les travaux de Simon et Sakarovitch). Dans cet exposé, je parlerai des recherches effectuées dans le cadre de ma thèse : j'exposerai les grandes idées qui ont mené à une extension des triangles de Pascal et de Sierpinski à ces coefficients. Je donnerai également un aperçu des résultats obtenus jusqu'ici et liés à ces généralisations.
Il s'agit d'un travail en commun avec Julien Leroy (Université de Liège) et Michel Rigo (Université de Liège).
 Plus d'infos  


2017-12-08Analogues discrets des intégrales de Macdonald-Mehta.
09:30-10:30
076
Je regarderai certaines discrétisations des intégrales de Macdonald-Mehta. Il y a dix familles de telles intégrales qui se calculent en formes closes. J'esquisserai les idées des preuves de ces identités. Elles deviennent respectivement des identités pour des caractères de groupes classiques, de la combinatoire de chemins deux à deux disjoints, et d'une formule de transformation pour des séries hypergéométriques elliptiques.
Il s'agit d'un travail en commun avec Richard Brent and Ole Warnaar.
 Plus d'infos  


2017-12-08Automates cellulaires probabilistes à mémoire deux : une riche zoologie
10:45-11:45
076
Je présenterai un famille d'automates cellulaires probabilistes à mémoire deux, dont l'introduction est motivée par l'étude de modèles issus de la physique statistique (modèle à 8 sommets, TASEP...). Nous donnons les conditions que doivent satisfaire les probabilités de transition pour que l'ACP ait une distribution invariante de forme produit, et montrons que dans ce cas, la dynamique est ergodique. L'étude des propriétés de réversibilité multi-directionnelle de ces ACP permet alors d'exhiber d'autres valeurs des paramètres pour lesquelles la distribution invariante peut être calculée explicitement, bien qu'elle n’ait pas une forme simple.
Il s'agit d'un travail en collaboration avec Jérôme Casse.
 Plus d'infos  


2017-12-01Processus de Fibonacci sur Z résistants à la localisation
10:45-11:45
076
Dans une série d’articles datant de 2015 et de 2016, Holroyd et Liggett ont étudié l’existence de processus de coloration sur le chemin infini Z ayant la propriété de k-dépendance, c’est-à-dire l’indépendance des distributions de probabilités des ensembles de variables aléatoires à distance au moins k les uns des autres. Ces processus de coloration induisent un processus binaire que nous avons baptisé « processus de Fibonacci » sur Z. Holroyd et Liggett ont également étudié ce processus de Fibonacci sous l’angle de la 1-dépendance.
Nous avons étudié chez ces processus de Fibonacci une propriété a priori plus faible que la 1-dépendance, en lien avec les algorithmes distribués quantiques, que nous avons appelé la 1-localisabilité. Cette propriété s’est avérée être distincte de la 1-dépendance mais nous avons démontré qu'un des résultats clés de Holroyd et Liggett, à savoir l’inexistence d’une 3-coloration reste vrai même si l’on exige que celle-ci soit non pas 1-dépendante mais 1-localisable. De plus, en étudiant la 1-localisabilité, nous avons découvert des liens avec les nombres de Catalan et certaines de leurs propriétés.
 Plus d'infos  


2017-11-24Simulation à mémoire finie de lois de probabilités continues
10:45-11:45
076
On s'intéresse ici à la question de savoir quelles lois de probabilités à densité (sur [0,1]) peuvent être simulées en n'utilisant qu'une mémoire bornée. Assez naturellement, on se ramène à considérer des automates probabilistes qui écrivent le développement (binaire, ou plus généralement, D-aire) d'un réel aléatoire.
Dans ce modèle, on dispose de deux résultats : Knuth et Yao ont prouvé en 1976 que les seules distribution à densité analytique qui peuvent être simulées, sont en fait à densité polynomiale ; et Vatan a caractérisé en 2001 les densités polynomiales qui sont simulables. Je propose une nouvelle preuve du résultat de Vatan, qui a l'avantage d'être constructive (on a un algorithme qui, partant de la densité, construit un automate qui la simule), mais aussi de caractériser les densités simulables parmi celles qui sont seulement polynomiales par morceaux.
 Plus d'infos  


2017-11-10Recherche exhaustive des pentagones convexes pavant le plan.
10:45-11:45
076
Quand on cherche à caractériser les formes convexes pouvant paver le plan (en s’autorisant les rotations et miroirs), seul le cas des pentagones restait ouvert. De 1918 à 2015, 15 différents types de pentagones pouvant paver le plan ont été découverts. Je présente une recherche exhaustive de tous les pentagones convexes pavant le plan, qui permet de clore cette question. La preuve se sépare en deux parties : la première montre, en utilisant la compacité, qu'on peut se limiter à un ensemble de 371 familles, et la seconde est une recherche exhaustive informatisée, pour chacune des 371 familles, qui ne trouve aucun nouveau type de pentagones que les 15 types connus.
 Plus d'infos  


2017-11-10Dissections du carré avec des triangles de surfaces presque égales
09:30-10:30
076
Le théorème de Monsky de 1970 stipule qu'un carré ne peut pas être découpé en un nombre impair "n" de triangles ayant la même aire. La preuve de Monsky ne fournit pas une borne inférieure pour la différence minimale entre les aires des triangles. Durant l'exposé, nous explorerons ce problème de minimisation en géométrie. D'une part, nous donnons une borne inférieure doublement exponentielle à l'aide d'une technique provenant de géométrie semi-algébrique réelle. D'autre part, nous obtenons une première borne supérieure superpolynomiale pour ce problème, dérivée d'une construction explicite faisant intervenir la suite de Thue-Morse.
Ces travaux ont été faits en collaboration avec Günter Rote et Günter Ziegler.
 Plus d'infos  


2017-10-27Cribles, de la théorie des nombres aux polygones auto-évitants.
10:45-11:45
076
Dans cet exposé nous présenterons une introduction à l’utilisation de cribles pour l’énumération asymptotique des polygones auto-évitants sur les réseaux régulier du plan. Partant de principes généraux valides pour tous les graphes, nous montrerons que de tels cribles ne peuvent fonctionner que sur les graphes infinis transitifs. Cette conclusion découlera d’un résultat simple que nous prouverons concernant la fraction asymptotique du nombre de chemins multiples d’un cycle simple donné, illustrant également la correspondance profonde entre la combinatoire des randonnées (c’est-à-dire des empilements de cycles simples) et la théorie des nombres. Finalement, nous obtiendrons une équation satisfaite asymptotiquement par la fonction dénombrant les polygones auto-évitants du réseau carré et soulignerons la difficulté qui reste à surmonter. Nous présenterons en outre quelques applications inattendues du crible en théorie des nœuds et même en biologie.
 Plus d'infos  


2017-10-20Théorèmes arithmétiques démontrés par Théorie des Langages.
10:45-11:45
076
On montre une méthode pour démontrer des théorèmes en Théorie Élémentaire des Nombres en utilisant des propriétés des mots de Dyck.
 Plus d'infos  


2017-10-13When are right-angled Artin groups similar?
10:45-11:45
076
Right-angled Artin groups arise naturally in different branches of mathematics and computer science. In this talk we will introduce the class of right-angled Artin groups and discuss when they are algebraically, geometrically and logically similar, or, more formally, when they are commensurable, quasi-isometric and universally equivalent.
 Plus d'infos  


2017-10-06Calcul du nombre géométrique d'intersection d'une courbe
10:45-11:45
076
Comment reconnaître si une courbe tracée sur une surface peut être déformée continûment en une courbe simple, c'est-à-dire sans croisement ? Plus généralement, comment calculer le nombre minimal de croisements parmi toutes les déformations continues de cette courbe ? Après quelques rappels historiques, je présenterai un point de vue algorithmique sur cette question et montrerai que des techniques élémentaires empruntées à la théorie géométrique des groupes permettent d'y répondre efficacement.
 Plus d'infos  


2017-10-06Motzkin tunnel polynomials
09:30-10:30
076
We define a sequence of polynomials associated with Motzkin paths and explore their properties. In particular we show that such polynomials satisfy a recurrence relation and present a remarkable symmetry.
We study in detail many different specializations of these polynomials that turn out to be sequences of great interest in combinatorics, such as Schroeder numbers, Fibonacci numbers, q-Catalan polynomials, Narayana polynomials.
 Plus d'infos  


2017-10-02--- information sur le changement des outils de gestion des listes de diffusion ---
10:15-10:15
---

[english follows]

Bonjour à tous,
Ce courriel inhabituel n'est pas une annonce de groupe de travail ou de petite
école mais une information sur le changement, a priori transparent pour tous,
d'outil de gestion de listes de diffusion.
En effet, j'ai décidé de basculer les deux listes de diffusion gérées
auparavant par GAEL (le logiciel du LaBRI de gestion des séminaires,
https://www.labri.fr/intranet/gt/script/index.php) et dorénavant par les
outils de l'université de Bordeaux (labri.cea-gt@diff.u-bordeaux.fr et
labri.cea-pec@diff.u-bordeaux.fr ont été créées pour cela ; pour information,
j'ai aussi remplacé @labri.fr par @u-bordeaux.fr).
Je garde cependant GAEL pour que les exposés soient affichées sur les
écrans du LaBRI (et soient enregistrés dans le système d'information du LaBRI).
Vous allez recevoir ce matin deux courriels envoyés par evtmaster@labri.fr
intitulé [GAEL] : Désinscription du groupe : Combinatoire Énumérative et
Algébrique (puis celui de la Petite École de Combinatoire) vous informant
votre désinscription du groupe faite par un responsable du groupe
(c'est-à-dire moi). Vous pouvez ignorer ce message.
En revanche, ce mercredi 4 octobre matin (après-demain), vous devriez
normalement recevoir deux annonces pour le groupe de travail Combinatoire
Énumérative et Algébrique de ce vendredi 6 octobre (exposés de Marilena
Barnabei de 9h30 à 10h30 puis de Francis Lazarus de 10h45 à 11h45). J'ai
sollicité quelques-uns d'entre-nous (Jean-Christophe Aval, Bétréma, Nicolas
Bonichon, Vincent Delecroix ; merci à eux) pour tester la procédure, et cela
devrait fonctionner.
Amitiés,
Olivier, secrétaire du GT CÉA et de la PÉC.

Hello everybody,
This unusual e-mail is not an announcement of workgroup; we just change the
management tool of mailing lists.
Indeed, I decided to replace both mailing lists managed previously by GAEL
(the software of the LaBRI of management of the seminaries,
https://www.labri.fr/intranet/gt/script/index.php) by the tools of the
university of Bordeaux (labri.cea-gt@diff.u-bordeaux.fr and
labri.cea-pec@diff.u-bordeaux.fr were created for it).
I keep however GAEL so that announcements are shown on the screens of the
LaBRI.
You will receive this morning two e-mails sent by evtmaster@labri.fr entitled
"[GAEL] : Désinscription du groupe : Combinatoire Énumérative et Algébrique"
(and then the same for "Petite École de Combinatoire") informing you your
unsubscription of the group made by a person in charge of the group (me!). You
can ignore this message.
On the other hand, on Wednesday, October 4th morning, you should receive two
announcements for the workgroup Combinatoire Énumérative and Algebraic of this
Friday, October 6th (talks of Marilena Barnabei from 9:30 am till 10:30 am and
then of Francis Lazarus from 10:45 am till 11:45 am). I requested a few of us
(Jean-Christophe Aval, Bétréma, Nicolas Bonichon, Vincent Delecroix; thanks!)
to test the procedure, and it should work.
Best regards,
Olivier, secretary of the seminaries CÉA and PÉC.

 Plus d'infos  


2017-09-29Les maules (2e partie) : m-Tamari et au delà Tamari(v)
10:45-11:45
076
Nous reprenons la notion de « maule » introduite dans l’exposé précédent. Toute partie du réseau carré engendre un maule par un processus dynamique de particules sauteuses.
Le treillis de Tamari défini sur les arbres peut aussi se définir sur les chemins de Dyck. Ceci permet une extension (pour m entier) donnée par F. Bergeron, appelée m-Tamari, en liaison avec des considérations profondes d’algèbre. Des conjectures difficiles ont été résolues par M. Bousquet-Mélou et ses coauteurs. Un problème resté ouvert était de donner une extension pour tout nombre m rationnel b/a. Celle-ci a été donnée dans un travail commun de l’orateur avec L.-F. Préville-Ratelle et en fait beaucoup plus généralement, pour tout chemin v formé de pas Nord et Est (voir Trans. AMS, 2017).
Nous montrons ici qu’un tel treillis Tamari(v) est également un maule, ce qui permet d'en donner une nouvelle définition beaucoup plus simple. Comme pour le premier exposé, le concept de tableaux alternatifs joue un rôle central, mais avec d’autres bijections. Ces tableaux alternatifs permettent aussi de faire le lien avec le travail très récent de C. Ceballos, A. Padrol et C. Sarmiento, donnant une réalisation géométrique de Tamari(v) étendant le très classique associaèdre associé au Tamari classique. Il est également amusant de pouvoir définir grâce aux maules un nouveau treillis YTam(?,v), « mélange » des treillis de Young Y(?) (voir le premier exposé) et de Tamari(v).
 Plus d'infos  


2017-09-22Les maules (1re partie) : Young, pavages et Tamari dans le même panier
10:45-11:45
076
Nous introduisons une nouvelle famille d’ensembles partiellement ordonnés, que je propose d’appeler « maule ». Toute partie du réseau carré engendre un maule par un processus dynamique de particules sauteuses.
Trois treillis (lattices) bien connus sont des maules : les diagrammes de Ferrers Y(?) inclus dans un diagramme ? donné (partie du treillis de Young), certains pavages sur réseau triangulaire (ou partitions planes) et le très classique treillis de Tamari défini par une notion de « rotation » sur les arbres binaires. Il en résulte ainsi une nouvelle définition du treillis de Tamari.
Curieusement, le concept de tableau alternatif joue un rôle central dans ce travail. De tels tableaux ont été introduits dans un tout autre contexte : le modèle très classique du PASEP (partially asymmetric exclusion process) en physique des systèmes dynamiques. Ces tableaux et leurs avatars ont fait l’objet de nombreux travaux au sein du groupe Combinatoire du LaBRI.

P.-S. : « maule » est un mot Mapuche, (se prononce « ma-ou-lé ») qui désigne la région Maule au Chili, ainsi que le fleuve qui le traverse, (cf. https://fr.wikipedia.org/wiki/Région_du_Maule) région où ce travail a été effectué, grâce à l’invitation de Luc Lapointe de l’Université de Talca.
 Plus d'infos  


2017-07-21Autour des méandres
10:45-11:45
076
Un méandre est une courbe fermée qui coupe une droite ; et l'on s'intéresse aux méandres pour lesquels on a fixé le nombre d'intersections entre la droite et ledit méandre. Je me suis penché sur le comptage, la génération, et certaines statistiques des méandres, ainsi que sur leur vitesse de croissance.
 Plus d'infos  


2017-07-06Récurrence Topologique à blobs et cartes farcies
10:45-11:45
050 (amphithéâtre du LaBRI)
Dans cet exposé, je présenterai les outils de récurrence topologique utilisés pour l'étude des modèles de tenseurs aléatoires présentés dans https://arxiv.org/abs/1612.04624.
Dans un souci de pédagogie, les résultats des travaux de Gaëtan Borot et Sergei Shadrin (https://arxiv.org/abs/1307.4957 et https://arxiv.org/abs/1502.00981) serviront de base à la présentation. Je reverrai les modèles de cartes farcies et la récurrence topologique généralisée que ces modèles satisfont. En effet certains modèles de tenseurs aléatoires peuvent être compris à l'aide de ce type de cartes. Enfin, si le temps le permet, je montrerai comment passer des modèles de tenseurs aléatoires aux modèles de cartes farcies.
 Plus d'infos  


2017-06-30Un nouveau lien entre l’algèbre de descentes du groupe hyperoctaèdral, les tableaux de dominos et les fonctions quasisymétriques de Chow.
10:45-11:45
076
Introduite par Solomon dans son article de 1976, l’algèbre de descentes d’un groupe de Coxeter fini a reçu une attention significative au cours des années passées. Gessel a montré dans le cas du groupe symétrique que ses constantes de structure donnent la table de comultiplication de la base fondamentale des fonctions quasisymétriques. Nous montrons que cette propriété implique en réalité plusieurs relations connues liées à la correspondance Robinson-Schensted-Knuth et certaines de ses généralisations. Ceci donne un nouveau lien entre ces résultats et la théorie des fonctions quasisymétriques et permet d’obtenir de nouvelles formules plus avancées faisant intervenir les coefficients de Kronecker. Par ailleurs en utilisant la théorie des fonctions quasisymétriques de type B introduite par Chow nous pouvons étendre notre méthode au cas du groupe hyperoctaédral et démontrer de nouvelles formules.
 Plus d'infos  


2017-06-16Calculer l'entropie des pavages mélangeants
10:45-11:45
076
Les pavages (ou sous-décalages) correspondent à des assignations d'états à chaque sommet d'une grille Z^d soumises à des contraintes locales. L'entropie d'un espace de pavage est un paramètre pertinent pour diverses communautés : en théorie de l'information (d=1), comme capacité d'un canal de communication ; en mathématiques, comme principal invariant de conjugaison ; en physique statistique (d=2 ou 3), comme entropie thermodynamique du système modélisé. Est-il possible de calculer (algorithmiquement) l'entropie d'un espace de pavages défini par des contraintes fournies en entrée ?
Pour des contraintes en nombre fini (pavage de type fini) et en dimension 1, l'entropie est calculable par une méthode algébrique classique. Le cas de la dimension supérieure s'est révélé beaucoup plus difficile, l'entropie de beaucoup d'exemples simples étant encore indéterminée. En 2007, il a été prouvé que l'entropie en dimension 2 n'est pas calculable en général. Des travaux plus récents ont montré que l'entropie redevient calculable sous des hypothèses de mélange, c'est-à-dire d'indépendance des motifs situés à une certaine distance. Où se situe la limite entre les cas calculable et incalculable ?
En introduisant une notion de taux de mélange, nous montrons l'existence d'un seuil en fonction de ce taux où la difficulté du problème passe de calculable à incalculable, sans pouvoir le déterminer exactement. Pour une famille plus large de pavages soumis à un nombre infini de contraintes, nous parvenons à déterminer exactement le seuil correspondant, et conjecturons que sa position est la même dans le cas fini.
Ces travaux sont en collaboration avec Silvère Gangloff.
 Plus d'infos  


2017-06-09Enumeration in Thompson's group F
10:45-11:45
076
Just over 50 years ago, Richard Thompson introduced the group F in an attempt to find a counter example to the Von-Neumann conjecture. On the one hand, F can be simply understood as a group of pairs of binary trees, or even more simply by its group presentation, yet in many ways, F is still very mysterious. Perhaps the biggest unknown question about F is whether it is `amenable', which, among other things, would answer Thompson's original question of whether it disproves the Von-Neumann conjecture. The amenability of F is one of those questions which tends to get a claimed solution each year, except that the claimed answer changes each time. I will describe combinatorially what it means for F to be amenable, and the results of my numerical work with Tony Guttmann on this question.
 Plus d'infos  


2017-05-12Fonctions zêta sur les graphes
10:45-11:45
076
Diverses extensions de la fonction zêta de Riemann ont été proposées pour tout graphe, comme la fonction zêta de Ihara-Selberg. Deux évaluations de cette fonction ont été données par Bass. Giscard et Rochet ont proposé une nouvelle approche de ce sujet avec la théorie des empilements de pièces. Un des lemmes de base de la théorie est le lemme logarithmique. Je montrerai comment ce lemme permet de donner une approche bijective des formules de Bass.
 Plus d'infos  


2017-05-05Déterminants, empilements et chemins ne se coupant pas (2)
10:45-11:45
076
Un Lemme très classique en combinatoire (Lemme LGV) relie les configurations sur un graphe sans circuits de chemins ne se coupant pas à un calcul de déterminant. Une extension aux graphes généraux a été étudiée par divers auteurs : Lalonde (1990) donnant une interprétation combinatoire de l'identité de Jacobi en algèbre linéaire (reliant les mineurs d'une matrice à ceux de la matrice inverse), des preuves bijectives par involution sur certaines configurations de chemins : Lalonde (1996), Fomin (2001), Talaska (2012) et enfin par Carrozza, Krajewski, Tanasa (1996) avec le calcul des variables et intégrales de Grassmann utilisées en physique quantique. Après un rappel de deux lemmes de base sur les empilements, j'exposerai le théorème de Lalonde, en termes d'empilements de cycles et de chemins, avec une nouvelle preuve bijective par involution, duquel découle toutes les interprétations précédentes.
Pour plus de détails, voir la vidéo et les transparents, chapitre 4c du cours : http://www.xavierviennot.org/coursIMSc2017/Ch_4.html.
 Plus d'infos  


2017-04-28Déterminants, empilements et chemins ne se coupant pas (1)
10:45-11:45
076
Un Lemme très classique en combinatoire (Lemme LGV) relie les configurations sur un graphe sans circuits de chemins ne se coupant pas à un calcul de déterminant. Une extension aux graphes généraux a été étudiée par divers auteurs : Lalonde (1990) donnant une interprétation combinatoire de l'identité de Jacobi en algèbre linéaire (reliant les mineurs d'une matrice à ceux de la matrice inverse), des preuves bijectives par involution sur certaines configurations de chemins : Lalonde (1996), Fomin (2001), Talaska (2012) et enfin par Carrozza, Krajewski, Tanasa (1996) avec le calcul des variables et intégrales de Grassmann utilisées en physique quantique. Après un rappel de deux lemmes de base sur les empilements, j'exposerai le théorème de Lalonde, en termes d'empilements de cycles et de chemins, avec une nouvelle preuve bijective par involution, duquel découle toutes les interprétations précédentes.
Pour plus de détails, voir la vidéo et les transparents, chapitre 4c du cours : http://www.xavierviennot.org/coursIMSc2017/Ch_4.html.
 Plus d'infos  


2017-04-07Polynômes chromatiques des graphes et empilements de pièces
10:45-11:45
076
Un théorème classique de R. Stanley en théorie des graphes donne une interprétation de la valeur pour (-1) du polynôme chromatique d'un graphe en terme d'orientations acycliques. Nous redémontrons ce théorème en utilisant la théorie des empilements de pièces et donnons une extension en introduisant la notion de série chromatique d'un graphe. Enfin nous évoquerons quelques développements récents reliant l'interprétation des coefficients du polynôme chromatique, la théorie des empilements et les algèbres de Lie partiellement commutatives.
Références : Chapitre 5a du cours 2017 de combinatoire bijective de X.V. Transparents et vidéos sur le site du cours : http://www.xavierviennot.org/coursIMSc2017/Ch_5.html.
 Plus d'infos  


2017-03-31À petits pas dans le quadrant : algébricité différentielle
10:45-11:45
178
La « méthode des invariants » a été inventée par Tutte pour compter des cartes proprement coloriées. On montrera d'abord qu'on peut la recycler pour résoudre de manière uniforme tous les modèles algébriques de marches dans le quadrant (y compris le modèle difficile de Gessel).
Ensuite, on adaptera la notion d'invariants à un contexte plus analytique pour démontrer que certains modèles dans le quadrant, quoique non-différentiellement finis, sont différentiellement algébriques (i.e., satisfont une ED polynomiale).

Travail en commun avec Olivier Bernardi et Kilian Raschel.
 Plus d'infos  


2017-03-17Simulation à mémoire finie de lois de probabilités
10:45-11:45
076
La question de la simulation exacte de lois de probabilités sur les réels est généralement étudiée sous un modèle « arithmétique » où on calcule de manière exacte sur des réels. Dans cet exposé, on se place au niveau « bit à bit », et on se demande ce qui peut être simulé si on n'a qu'une mémoire finie.
On est alors naturellement amené à considérer des automates qui tirent à pile ou face et qui écrivent des mots, qu'on espère infinis, et qu'on interprète comme le développement de réels ; la question est donc de savoir quelles distributions sont simulables de la sorte.
Le modèle est essentiellement celui considéré par Knuth et Yao en 1976, et pour lequel ils ont montré un résultat intrigant : si une loi simulable a une densité qui est une fonction analytique, alors cette densité est en fait polynomiale - ce qui exclut de fait de nombreuses lois usuelles.
Je présenterai le modèle et le résultat de Knuth et Yao, mais aussi un résultat plus nouveau de classification : étant donné un automate, on peut dire s'il simule une loi à atomes, ou à densité, ou une loi plus « méchante ». Je montrerai aussi des exemples qui interdisent une généralisation trop forte du résultat de Knuth et Yao.
 Plus d'infos  


2017-03-03Une généralisation d-dimensionnelle des mots de Christoffel 2/2
10:45-11:45
076
Nous rappellerons le résultat de Brlek, Lachaud, Provençal, Reutenauer (2009) qui relie le concept de convexité en géométrie discrète avec des notions connues en combinatoires des mots notamment les mots de Lyndon, la factorisation de Lyndon et les mots de Christoffel. Nous nous intéresserons aux généralisations d-dimensionnelles de ce résultat (une question ouverte). Nous présenterons une généralisation d-dimensionnelle des mots de Christoffel développée en collaboration avec Christophe Reutenauer.
 Plus d'infos  


2017-02-17Propriétés de quelques fractions continues de Hurwitz
10:45-11:45
076
On considère les fractions continues qui sont définies par une suite des termes formée par mélange périodique d'une suite constante et d'une suite arithmétique. On propose une formule close pour des sous-suites de la suite des convergents. La preuve utilise des séries de Laurent formelles et des identités sur les coefficients binomiaux qui se démontrent de manière combinatoire. En passant à la limite on obtient des formules closes qui font intervenir des fonctions de Bessel et des polynômes de Fibonacci. Les cas spéciaux fameux incluent les nombres e et tan(1).
 Plus d'infos  


2017-02-10Une généralisation d-dimensionnelle des mots de Christoffel 1/2
10:45-11:45
076
Nous rappellerons le résultat de Brlek, Lachaud, Provençal, Reutenauer (2009) qui relie le concept de convexité en géométrie discrète avec des notions connues en combinatoires des mots notamment les mots de Lyndon, la factorisation de Lyndon et les mots de Christoffel. Nous nous intéresserons aux généralisations d-dimensionnelles de ce résultat (une question ouverte). Nous présenterons une généralisation d-dimensionnelle des mots de Christoffel développée en collaboration avec Christophe Reutenauer.
 Plus d'infos  


2017-01-12.../...
10:45-11:45
076
 Plus d'infos  


2016-12-16Indépendance asymptotique de la décomposition en cycles pour des paires de permutations contraintes par une équation de commutateur
10:30-11:30
076
Fixons des entiers k_1, k_2, ..., k_m plus grands ou égaux à 2. On s'intéresse aux paires de permutations (s,t) de S_n telles que la décomposition en cycles de [s,t] = s t s^-1 t^-1 est faite exactement de cycles de longueur k_1, k_2, ..., k_m et de points fixes (i.e. des cycles de longueur 1). La raison de cet intérêt est que le nombre de telles paires compte certaines cartes combinatoires et leur asymptotique au premier ordre est guidée par le volume de certains espaces de modules algébriques.
J'essaierai de donner quelques motivations à l'étude de ces quantités mais surtout j'expliquerai pourquoi la décomposition en cycle de s est asymptotiquement indépendante de celle de t (résultat que je ne sais pas encore démontrer combinatoirement).
 Plus d'infos  


2016-12-02Antipode et hypergraphe
10:45-11:45
076
[en collaboration avec Carolina Benedetti]
Calculer des formules d'antipodes pour différentes algèbres de Hopf combinatoires est un problème classique mais difficile à résoudre. Récemment, de nombreux résultats dans ce sens ont été trouvés pour diverses algèbres de Hopf combinatoires [Humpert-Martin, Benedetti-Sagan, Aguiar-Ardila]. Une motivation pour trouver de telles formules réside dans leur interprétation géométrique potentielle, ou dans leur utilisation pour obtenir des informations concernant les invariants combinatoires des objets en jeu. Un exemple de ceci est l'algèbre de Hopf des graphes G. Humpert et Martin dérivent la formule antipode et l'utilisent pour mieux comprendre le célèbre théorème couleur (-1) de Stanley : le polynôme chromatique d'un graphe évalué à -1 est, à signe près, le nombre d'orientations acycliques du graphe. Du côté géométrique, un résultat remarquable d'Aguiar et Ardila montre que cet antipode est codé dans le vecteur -f du zonotope graphique correspondant au graphe donné.
Nous montrons qu'un cadre plus général pour étudier cela est donné par les hypergraphes.
 Plus d'infos  


2016-11-25 Comptage de couplages parfaits sans croisements (d'après Ruiz-Vargas et Welzl)
10:45-11:45
076
Prenons un nombre pair, 2n, de points dans le plan, en position convexe. Le nombre de couplages parfaits de ces 2n points qui ne présentent pas de croisements d'arêtes (si celles-ci sont tracées par des segments), est bien connu : c'est le n-ième nombre de Catalan.
Mais que se passe-t-il si, au lieu d'être en position convexe, les points sont « presque » en position convexe : 2n-1 sont en position convexe, et le dernier se trouve à l'intérieur du polygone ? La réponse dépend alors des positions de tous les points, mais Ruiz-Vargas et Welzl ont démontré une élégante formule d'énumération qui ne fait intervenir que les positions des points par rapport à un petit nombre de droites. Je présenterai la preuve de ce résultat, et essaierai de discuter de la possibilité d'exploiter une telle formule pour faire de la génération aléatoire.
 Plus d'infos  


2016-11-18Une approche unifiante en probabilité non commutative
10:45-11:45
076
En théorie non commutative des probabilités, un espace de proba est une algèbre (non commutative) sur laquelle est définie une forme linéaire, jouant le rôle de l'espérance. Il a été montré par Speicher qu'il existe exactement trois notions d'indépendance universelles dans ce contexte :
* l'indépendance tensorielle, qui n'est autre que l'indépendance statistique classique,
* l'indépendance libre, qui a été introduite par Voiculescu et appliquée aux matrices aléatoires,
* l'indépendance Booléenne.
Un problème de matrices aléatoires plus général que cela considéré par Voiculescu permet de définir une notion plus riche d'espace de probabilité non commutative, dans lequel les opérations algébriques ne sont pas seulement les polynômes, mais également des opérations encodées par des graphes. Ces espaces sont munis d'une notion d'indépendance qui unifie les trois notions ci-dessus.
Dans cet exposé introductif, je présenterai la combinatoire qui est derrière ces notions généralisées de probabilités non commutatives. Nous utiliserons des transformations de Möbius et nous verrons pourquoi les arbres sont des graphes plus importants que les autres pour les grandes matrices aléatoires.
 Plus d'infos  


2016-11-04Les billards polygonaux et les surfaces de translation de type infini
10:45-11:45
076
Dans cet exposé on explique en termes élémentaires une construction qui associe à chaque billard polygonal une surface « plate » où le mouvement de la boule devient un flot linéaire. On expliquera la topologie de la surface qu'on obtient et, si le temps le permet, quelques problèmes de comptage associés au billard.
 Plus d'infos  


2016-10-21Marches aléatoires dans des cônes : exposants critiques.
10:45-11:45
076
Le modèle combinatoire des marches dans des cônes connaît actuellement un essor considérable. Dans cet exposé nous parlerons de marches à grands pas, en dimension quelconque et de marches avec des poids. Nous nous concentrerons sur les exposants critiques qui apparaissent dans les asymptotiques :
(1) des nombres d'excursions (marches reliant deux points fixés en un nombre donné de pas tout en restant dans un cône), (2) des nombres de marches de longueur prescrite.
Nous présenterons les travaux fondateurs de Denisov et Wachtel répondant à (1) ainsi que des résultats partiels et des conjectures liés à (2). Nous évoquerons des énoncés nouveaux de non-D-finitude des séries génératrices de comptage.
Il s'agit de résultats correspondant à des travaux en cours avec Julien Courtiel, Steve Melczer et Marni Mishna d'une part, Rodolphe Garbit et Sami Mustapha d'autre part.
 Plus d'infos  


2016-09-30Algorithmes d'insertion pour les tableaux de dominos décalés
10:45-11:45
076
Les tableaux de dominos classiques donnent une description combinatoire du produit de deux fonctions de Schur. De manière analogue, les tableaux de dominos décalés ont été introduits par Z. Chemli en 2016 dans le but de décrire le produit de deux fonctions Q-Schur (ou P-Schur). Dans mon exposé, je montrerai comment on peut définir un algorithme d'insertion (bijectif) à la Robinson-Schensted prenant en argument un mot bicolore et produisant deux tableaux de dominos décalés. J'en présenterai aussi l'algorithme inverse. Diverses conséquences seront évoquées : une règle de type Littlewood-Richardson pour les fonctions Q-Schur, le lien avec le super monoïde plaxique décalé, ...
Il s'agit d'un travail en collaboration avec Zakaria Chemli.
 Plus d'infos  


2016-09-23Chemins à grands pas dans le quadrant
10:45-11:45
076
L'énumération des chemins du quadrant formés de petits pas (c'est-à-dire de pas aux 8 plus proches voisins) est maintenant bien comprise. En particulier, leur série génératrice est différentiellement finie (solution d'une ED linéaire à coefficients polynomiaux) si et seulement si un certain groupe de transformations rationnelles, associé à l'ensemble des pas autorisés, est fini.
Il n'est pas du tout évident d'étendre à des marches à pas plus grands les méthodes qui ont permis cette classification. Guy Fayolle et Kilian Raschel ont décrit les difficultés qu'il faut attendre si on essaie de généraliser l'approche par analyse complexe (qui est très puissante dans le cas de petits pas). Dans cet exposé, je présenterai quelques progrès de l'approche algébrique via des séries formelles, dont la portée est de toutes façons limitée au cas de groupes finis.
(travail en commun avec Alin Bostan et Steve Melczer)
 Plus d'infos  


2016-09-09Un codage pour les triangulations du tore.
10:45-11:45
076
Dans le cas planaire, les triangulations sont en bijection avec un certain type d'arbres bourgeonnants. Cette bijection repose sur l'étude des bois de Schnyder et a de nombreuses implications intéressantes : codage optimal, sampling uniforme en temps linéaire, dessin sur une grille... Nous généralisons ce résultat au cas des triangulations du tore. La plupart des propriétés planaires sont conservées ; néanmoins, quelques propriétés ont un sens assez différent que nous discuterons. Ce travail a pour but d'être généralisé aux surfaces quelconques ; il est aussi intéressant de voir quels sont les nouveaux problèmes soulevés.
 Plus d'infos  


2016-07-08Simplicial rook graphs: algebraic and combinatorial properties
10:45-11:45
178
A few years ago, Jeremy L. Martin and Jennifer D. Wagner introduced the simplicial rook graphs SR(d,n) as the graph whose vertices are the lattice points in the n-th dilate of the standard simplex in R^d, with two vertices adjacent if they differ in exactly two coordinates. Martin and Wagner proved that SR(3,n) has integral eigenvalues and determined other interesting properties of these graphs. In this talk, I will describe our work proving some conjectures made by Martin and Wagner as well as determining other algebraic and combinatorial facts about these graphs.
This is joint work with Andries Brouwer (TU, Eindhoven, The Netherlands), Willem Haemers (Tilburg University, The Netherlands) and Jason Vermette (Missouri Baptist Univ., USA).
 Plus d'infos  


2016-07-01 Une curiosité sur une permutation opérant sur les sous-ensembles à n éléments de {1, 2, ..., 2n+1}.
10:00-11:00
076
On définit une permutation sur les sous-ensembles à n éléments de {1, 2, ..., 2n+1} qui fait intervenir des mots de Dyck et le Lemme cyclique. On a constaté une régularité dans les cycles de cette permutation. On prouve cette régularité dans certains cas, elle reste pourtant une conjecture dans le cas général. Un lien avec les pliages d'une bande de timbres-poste et avec les méandres sera évoqué. L'espoir de l'orateur est que des idées nouvelles éclosent des échanges avec l'auditoire.

Cet exposé résulte d'un travail en commun avec Niccolò Castronuovo (Bologne).
 Plus d'infos  


2016-06-17Arbres non-ambigus : nouveaux résultats et généralisation (2/2)
10:45-11:45
076
Dans l'exposé 1/2, je fais mention d'une nouvelle statistique sur les arbres binaires comptant le nombre d'équerres d'un arbre. Je commencerai l'exposé par donner une bijection qui envoie cette statistique vers la statistique sur les arbres ordonnés, comptant les nœuds ayant un fils qui est une feuille. La deuxième partie de mon exposé portera sur l'obtention d'une q-version de la formule des équerres, comptant le nombre d'arbres non-ambigus ayant un arbre binaire fixé. La méthode se base sur un article de 2008 de Hivert, Novelli et Thibon, dans lequel ils mettent en place une machinerie pour redémontrer une q-version de la formule des équerres, comptant le nombre d'arbres décroissants ayant un arbre binaire fixé.
 Plus d'infos  


2016-06-10Arbres non-ambigus : nouveaux résultats et généralisation (1/2)
10:45-11:45
076
Les arbres non-ambigus ont initialement été définis comme des dessins particuliers d'arbres binaires sur le quadrillage. Mais on peut également les voir comme des tableaux boisés de forme rectangulaire. Dans ce dernier cadre, Steingrímsson et Williams ont montré qu'ils sont en bijection avec les permutations dont toutes les excédences (strictes) sont au début. Ehrenborg and Steingrímsson avaient prouvé une formule alternante pour énumérer ces permutations particulières.
Dans cet exposé je vais donner une nouvelle définition des arbres non-ambigus en terme d'arbres binaires étiquetés croissants le long des arêtes gauches, et indépendamment, le long des arêtes droites. Grâce à cette nouvelle vision, on prouve bijectivement une « nouvelle » formule énumérative qui a la bonne propriété d'être à termes positifs, et on trouve une formulation compacte de la série génératrice doublement exponentielle des arbres non-ambigus. Je terminerai l'exposé par la présentation d'une généralisation des arbres non-ambigus à toutes dimensions finies.
 Plus d'infos  


2016-06-03Sur les orientations bipolaires des cartes
10:45-11:45
076
Les cartes planaires, étudiées depuis les années 60 par Tutte — puis beaucoup d'autres — sont désormais bien comprises. En particulier, 20 ou 30 ans après les premiers travaux récursifs de Tutte, de belles bijections sont venues expliquer la simplicité de ses formules d'énumération. Plus tard, ces bijections ont ouvert la voie à l'étude des grandes cartes aléatoires, vues comme des espaces métriques.
Les cartes équipées d'une structure restent plus mystérieuses. Pour beaucoup de structures, par exemple les colorations propres, l'énumération a été faite, mais pas de façon bijective. Et les propriétés asymptotiques des grandes cartes structurées restent à élucider.
Dans cet exposé, on traitera des cartes équipées d'une orientation bipolaire, en montrant qu'elles ont une combinatoire particulièrement riche, qui permet notamment de les dénombrer.
Cet exposé bouche-trou est basé pour partie sur des travaux pas tout jeunes avec Nicolas Bonichon et Éric Fusy (vers 2008), et pour une autre partie sur des travaux en cours avec le même Éric Fusy et Kilian Raschel.
 Plus d'infos  


2016-05-27Collages maximaux d'octaèdres
10:45-11:45
076
Les graphes à arêtes proprement colorées avec (D+1) couleurs sont duaux aux triangulations dites colorées (ayant les faces colorées) de pseudo-variétés en dimension D. Nous étudions en 3 dimensions des familles obtenues en collant des octaèdres, une généralisation des quadrangulations. J'introduirai une bijection entre de tels graphes et certaines cartes combinatoires à arêtes colorées. Ces dernières généralisent la représentation des hypercartes à l'aide de cartes biparties introduite par Walsh, en remplaçant les sommets correspondant aux hyper-arêtes par des structures plus compliquées.
Nous nous intéressons au nombre de cycles bicolores des graphes initiaux car ils contiennent l'information sur la courbure de la pseudo-variété triangulée. Je montrerai donc comment identifier et compter les graphes qui maximisent le nombre de cycles bicolores à nombre d'octaèdres fixé.
 Plus d'infos  


2016-05-20Calcul de Grassmann et combinatoire
10:45-11:45
076
Le calcul de Grassmann, basé sur des variables anti-commutantes, joue un rôle important en physique théorique. Je montrerai comment celui-ci peut par ailleurs être mis à profit pour adresser des questions purement combinatoires. Nous verrons en particulier comment démontrer le lemme de Lindström-Gessel-Viennot dans le cas général de graphes avec cycles.
 Plus d'infos  


2016-05-13Sur le modèle du tas de sable dans un graphe biparti complet
10:45-11:45
076
Le modèle du tas de sable étudié notamment par Dhar est un modèle de diffusion discret de grains sur les sommets d'un graphe. Ce modèle capture des notions classiques sur le graphe : les états dits récurrents sont en bijection avec les arbres couvrants, le nombre de grains sur ces états est relié à l'activité externe définie par Tutte... Même dans le cas de graphes fortement symétriques comme les graphes complets ou bipartis complets, cela conduits à des notions non-triviales.
Par exemple, avec Dukes, nous avions observé que dans le cas d'un graphe complet, le paramètre bounce introduit par Haglund dans une description des q,t-Catalan peut s'interpréter dans la version parallèle du test de récurrence de Dhar pour un état du modèle. Une adaptation de cette remarque aux graphes bipartis complets nous avait conduit à la définition de q,t-Narayana. Rejoins par Aval, D'Adderio et Hicks nous avions prouvé que ces nombres étaient très proche de q,t-analogues également introduits par Haglund avec des motivations plus algébriques.
L'objectif du jour sera le calcul du rang, un paramètre introduit par Baker et Norine en 2007 dans un analogue pour les graphes d'un théorème de Riemman-Roch. Ce paramètre est annoncé comme NP-complet sur les graphes. Avec Cori, nous avions proposé dans le cas des graphes complets un algorithme glouton de complexité arithmétique linéaire. Je présenterai son adaptation au cas des graphes bipartis complets que j'ai obtenu en collaboration avec D'Adderio.
 Plus d'infos  


2016-04-01Treillis de relations binaires
10:45-11:45
076
Nous définissons une structure de treillis sur les relations binaires qui peut être vue comme une généralisation de l'ordre faible sur les permutations. Le treillis que l'on obtient contient comme sous-poset (et parfois sous-treillis) de nombreux treillis liés à la combinatoire de l'ordre faible, de l'ordre de Tamari et des treillis Cambriens. La motivation de ce travail est l'étude de ces treillis qui peuvent souvent être interprétés comme des algèbres de Hopf et des polytopes.
 Plus d'infos  


2016-03-18Préserver le nombre de cycles de longueur k dans une permutation uniforme de taille croissante
10:45-11:45
076
Dans cet exposé, je vous présenterai un nouvel arbre de génération uniforme pour les permutations qui préserve le nombre de k-cycles entre toute permutation et ses enfants dans l'arbre (à l'exception d'une petite proportion non évitable de taille optimale).
L'arbre que je vais décrire aura la propriété que lors d'une descente dans l'arbre, si le nombre de k-cycles reste constant pendant k niveaux consécutifs, alors le reste de la descente ne parcourra que des permutations avec ce même nombre de k-cycles. Cette propriété additionnelle permet d'obtenir des algorithmes efficaces pour la génération de permutations (permutations uniformes avec un nombre de k-cycles fixé) et de variables aléatoires de Poisson.
Ce travail en collaboration avec Ph. Duchon généralise un précédent arbre avec des propriétés similaires traitant le cas k=1.
 Plus d'infos  


2016-03-04Uniformisation de l'aléa en dynamique symbolique
10:45-11:45
076
Une transformation d'un espace est dite randomisante si son itération tend à uniformiser la distribution des configurations de cet espace. Plus précisément, quand on fixe la mesure de probabilité initiale non uniforme (la distribution initiale), l'itération de la transformation fait converger cette mesure vers la mesure uniforme.
De tels comportements ont été remarqués expérimentalement dans certains automates cellulaires et sous-décalages de dimension 2. Dans cet exposé, je présenterai nos récentes avancées dans l'étude des causes et des limites de ces phénomènes, qui nous ont amenées à la première preuve rigoureuse de leur existence. Cette preuve repose sur le fort contenu algébrique des systèmes considérés qui donne à leur évolution temporelle une structure géométrique autosimilaire. Dans un sous-décalage particulier (celui de Ledrappier), nous obtenons des changements surprenants de dynamique directionnelle suivant la direction considérée.
 Plus d'infos  


2016-02-19Réalisation des associaèdres de graphes par des éventails de compatibilité
10:45-11:45
076
L’associaèdre est un polytope dont le treillis des faces encode la combinatoire des dissections d’un polygone convexe du plan. Il a été généralisé dans de nombreuses directions. Parmi elles on trouve ce qu’on appelle les associaèdres généralisés en lien avec les algèbres amassées d’une part, et les associaèdres de graphe d’autre part. Essayer de construire un grand nombre de représentants géométriquement non équivalents de ces polytopes produit de jolis problèmes combinatoires. Les réaliser par un éventail complet (un ensemble de cônes polyédrals qui couvrent l’espace ambiant) est un premier pas moins fort que par des polytopes, mais déjà de nature géométrique. Dans un article de Ceballos, Santos et Ziegler, Francisco Santos propose une construction de nombreux associaèdres (classiques) non équivalents. Cette construction commence par celle d’un éventail qui se révèle être basé sur les vecteurs dénominateurs dans le cadre des algèbres amassées. Dans cet exposé, je présenterai la construction d’éventails réalisant les associaèdres de graphes, qui dans le cas de l’associaèdre classique est celle de Francisco Santos. La construction, spécifiée au cas de l’associaèdre d’un cycle (cycloèdre) étend le résultat de Francisco Santos à l’associaèdre de type B, avec toujours une interprétation en terme de vecteurs dénominateurs, qui permet dans les deux cas d’obtenir une réalisation polytopale. J’insisterai surtout sur l’aspect combinatoire de la construction.
(travail avec Vincent Pilaud arXiv:1501.07152)
 Plus d'infos  


2016-02-12Asymptotic expansion for random tensor models
10:45-11:45
076
Three-dimensional random tensor models are a natural generalization of the celebrated matrix models. The associated tensor graphs can be classified with respect to a particular integer or half-integer, the degree.
I will present in this talk a combinatorial analysis of the general term of the asymptotic expansion in N, the size of the tensor, of a particular random tensor model, the so-called multi-orientable model. I will then present some enumerative results and show which are the dominant configurations of a given degree; several examples will also be given.
 Plus d'infos  


2016-02-12The shifted domino tableaux
09:30-10:30
076
In 1995, Carré and Leclerc studied a bijection due to Stanton and White between domino tableaux and pairs of Young tableaux. They gave an easier description of this bijection that highlights the role of the diagonals of tableaux. This allows them to extend the plactic monoid of Lascoux and Schützenberger to dominoes, hence, define the super plactic monoid. They show that each class of the super plactic monoid is represented by a unique domino tableau, and propose a new combinatorial description of the product of two Schur functions using domino tableaux, which gives a new expression of the Littlewood-Richardson rule coefficients in terms of domino tableaux.
In a recent work, we defined new combinatorial objects called the shifted domino tableaux, these objects can be seen as a shifted analog of domino tableaux or as an extension of shifted Young tableaux. The purpose of this extension is to develop a theory of shifted domino tableaux parallel to the theory of domino tableaux and shed lights on the combinatorial properties of Q-Schur and P-Schur functions. In this talk I will introduce the shifted domino tableaux, present a bijection between shifted domino tableaux and pairs of shifted Young tableaux, and discuss some results.
 Plus d'infos  


2016-02-05Regular edge colored graphs of positive degree
10:45-11:45
076
Regular edge colored graphs are dual to triangulations of pseudo manifolds in any dimension. They can be classified with respect to a non negative integer, the degree, much like maps which are classified by the genus. In this talk I will introduce the degree, discuss the (regular, edge colored) graphs of degree zero, and present the exact enumeration of connected rooted, regular, edge colored graphs of fixed degree.
 Plus d'infos  


2016-02-05The Schutzenberger involution over Dyck paths
09:30-10:30
076
We describe a map Gamma from the set of Dyck paths of given semilength to itself that is the analog of the Schützenberger involution on standard Young tableaux. Afterwards, we examine the behavior of Gamma with respect to Knuth’s correspondence between pairs of standard Young tableaux of the same shape with at most two rows and Dyck paths. Finally, we exploit the previous results to describe a bijection between the set of 321-avoiding centrosymmetric permutations of even length and the set of 321-avoiding involutions of the same length. All these tools are used to find some enumerative formulas about statistics over centrosymmetric permutations.
The talk is based on a joint work with Marilena Barnabei.
 Plus d'infos  


2016-01-22Sur une autre somme binomiale signée donnant les nombre des Baxter
10:45-11:45
076
Dans leur récent travail sur les sommes binomiales, Bostan, Lairez et Salvy (arxiv:1510.07487) présentent comme application de leurs algorithmes (Section 7.3) une identité de Le Borgne sur les nombres des Baxter. Je ne dispose pas d'interprétation combinatoire de cette identité que Lairez avait bien voulu me prouver. Par contre, je dispose d'une explication calculatoire de l'origine de cette identité. Elle vient d'une approche moins qu'élémentaire pour la résolution d'une équation fonctionnelle à deux variables catalytiques que m'avait présentée Mishna, Burril et Yen lors de mon séjour au PIMS/SFU à Vancouver en 2013/14. Cette équation était écrite pour compter les préfixes de diagrammes étendus représentant des partitions des entiers 1,2,...,n sans (future) 3-imbrication dont nous a parlé Courtiel l'an dernier. Mon approche n'avait pas été retenue, Mishna et Melczer notamment ayant prouvé par leurs propres moyens également calculatoires que ces préfixes de diagrammes étaient aussi comptés par les nombres des Baxter. Je présenterai les éléments de la preuve par mon approche qui me semblent dignes d'intérêt d'un point de vue méthodologique et quelques questions qu'ils suscitent.
 Plus d'infos  


2016-01-22Sur un modèle du graphe aléatoire inhomogène
09:30-10:30
076
Dans cet exposé, on considère un graphe aléatoire à n sommets où les arêtes sont présentes avec les probabilités proportionnelles aux produits des poids (qui sont des nombres positifs) sur les sommets. Le modèle généralise G(n, p) (le graphe d’Erdos-Renyi) en introduisant une inhomogénéité dans les degrés des sommets. On va donner une représentation du graphe à l’aide d’une forêt de Galton-Watson. En particulier, cette représentation nous permettra de trouver les limites d’échelle du graphe dans le régime critique lorsque n tend vers l’infini.
L’exposé est basé sur un travail en commun avec N. Broutin et T. Duquesne.
 Plus d'infos  


2016-01-15Conjugacy languages and conjugacy growth series in groups
10:45-11:45
076
To any group G generated by a finite set X one can associate several languages of words over X, such as the language of normal forms, or of geodesics, and then determine whether such a language is regular, context-free etc. One can also analyze the generating function of the language and determine whether it is rational, algebraic or transcendental. In the last decades several beautiful results have established connections between the algebraic and geometric properties of the group and the languages and generating functions mentioned above.
In this talk I will introduce a language which picks one representative word out of each conjugacy class, and show how one can use tools from various areas to determine the transcendence of the conjugacy growth series in free groups. All the necessary group theoretic concepts will be introduced.
 Plus d'infos  


2016-01-15Cordes terminales dans les diagrammes connexes de cordes
09:30-10:30
076
Peut-être souvent mésestimés, les diagrammes de cordes et leur énumération apparaissent dans de nombreux domaines mathématiques : physique quantique, théorie des nœuds, échantillonnage de graphes, analyse de structures informatiques, et même bio-informatique...
Les travaux de cet exposé, en cours de rédaction et coréalisés avec Karen Yeats (SFU, Vancouver), se placent de le cadre de la physique quantique. En effet, les solutions à certaines équations de Dyson-Schwinger (nous n'en parlerons que très peu, soyez rassurés) peuvent être définies grâce aux diagrammes de cordes connexes munies d'un paramètre particulier : les cordes dites terminales.
Nous étudierons donc quelques statistiques sur ces cordes terminales : leur nombre en moyenne, la position de la première corde terminale, etc. Nous constaterons notamment l'apparition d'une loi limite de probabilité qui, à ma connaissance, n'est pas répertoriée dans la littérature. Nous montrerons également en quoi les techniques classiques de combinatoire analytique ne peuvent s'appliquer et donnerons quelques idées sur la démarche à emprunter dans ce cas-là.
 Plus d'infos  


2016-01-08Degré des graphes réguliers à arêtes colorées
10:45-11:45
076
On introduira pour les graphes réguliers à arêtes colorées les notions de jaquettes et de degré de Gurau. Ce degré gouverne le comportement des fonctionnelles génératrices de ces graphes dans une certaine limite qui intéresse les physiciens théoriciens cherchant à quantifier la gravité. On identifiera et on énumèrera les graphes de degré maximal à ordre donné, dits « graphes méloniques ». Leur limite de Gromov Hausdorff coïncide avec l'arbre aléatoire d'Aldous, ainsi que l'ont prouvé Gurau et Ryan en s'appuyant sur les travaux d'Albenque et Marckert.
 Plus d'infos  


2015-12-18Arbres et/ou : une approche par limite locale
10:45-11:45
076
Un arbre et/ou est un arbre dont les nœuds internes sont étiquetés soit par le connecteur logique ET, soit par le connecteur logique OU, et dont les feuilles sont étiquetées par des littéraux choisis parmi k variables booléennes {x_1, ..., x_k} et leurs négations. Un tel arbre calcule une fonction booléenne à k variables, i.e. une fonction de {0,1}^k dans {0,1}.
Je m'intéresse dans cet exposé à décrire la fonction booléenne aléatoire calculée par un arbre et/ou aléatoire, en fonction des propriétés de l'arbre aléatoire choisi. Les résultats que je présente, obtenus en collaboration avec N. Broutin (Inria-Rocquencourt), concernent les arbres et/ou obtenus en étiquetant aléatoirement des arbres aléatoires standards : arbre de Catalan, arbre de Galton-Watson, arbre binaire de recherche aléatoire, etc.
Notre résultat principal décrit le comportement de la distribution induite sur l'ensemble des fonctions booléennes en fonction de la limite locale de l'arbre aléatoire sous-jacent.
 Plus d'infos  


2015-11-27Bijections pour les tableaux alternatifs rhomboïdaux
10:45-11:45
076
(travail en commun avec Olya Mandelshtam)
Nous reprenons les tableaux alternatifs rhomboïdaux (ou triangulaires) introduits dans l'exposé précédent en interprétant combinatoirement les probabilités stationnaires du modèle PASEP avec deux types de particules (modèle à trois paramètres alpha, beta et q). Nous donnons une preuve bijective du fait que ces tableaux sont énumérés par les nombres de Lah (n+1)!/(k+1)! binomial(n,k) en construisant une bijection entre ces tableaux et les « assemblées » de permutations. Cette bijection permet de décrire sur les assemblées les paramètres alpha et beta du modèle physique. Avec une autre bijection décrivant un processus d'insertion, nous obtenons une preuve bijective de l'expression explicite de la fonction de partition pour q=1 donnée au premier exposé.
 Plus d'infos  


2015-11-20Tableaux alternatifs rhomboïdaux pour le PASEP à deux types de particules
10:45-11:45
076
(travail en commun avec Olya Mandelshtam)
Le modèle du PASEP (partially asymmetric exclusion process) est très connu dans la physique des systèmes dynamiques (et aussi au groupe combinatoire du LABRI). Pour le modèle avec trois paramètres il s'agit de particules se déplaçant sur une bande dans les deux sens, avec entrée des particules à gauche et sortie à droite selon certaines probabilités alpha, beta et q. Ici nous étudions une extension, également classique en physique, avec deux types de particules. Ce modèle est lié aux polynômes de Koorwinder-Macdonald. Nous introduisons la notion de tableaux alternatifs rhomboïdaux (ou triangulaires) permettant d'interpréter combinatoirement les probabilités stationnaires du modèle à trois paramètres. Ces tableaux sont énumérés par les nombres de Lah (n+1)!/(k+1)! (binomial n,k). Nous donnons une expression explicite de la fonction de partition pour q=1.
 Plus d'infos  


2015-10-23Du nouveau sur les mots de Dyck ?
10:45-11:45
076
Il sera question de deux involutions sur les mots de Dyck de longueur donnée, la première est une symétrie classique la seconde qui semble nouvelle a été introduite par Yvan Le Borgne et moi-même dans le calcul du rang des configurations du graphe complet. On peut montrer que le nombre de leurs points fixes est le même égal à un coefficient binomial central. Plus étonnant est que la composition de ces deux involutions est une permutation dont tous les cycles sont de longueurs impaires. Nous avons avec les Bolognais Marilena Barnabei, Flavio Bonetti et le jeune Nicolo Catronuovo réussi à démontrer ce résultat après plusieurs semaines de tentatives diverses. Une idée de la preuve vous sera proposée.
 Plus d'infos  


2015-10-23Algèbre de Hopf d'incidence des posets de partitions semi-pointées
09:30-10:30
076
Dans les années 1990, Schmitt a décrit un procédé qui permet d'associer à toute famille d'intervalles vérifiant certaines conditions une algèbre de Hopf, appelée algèbre de Hopf d'incidence. Une algèbre de Hopf d'incidence bien connue est celle associée aux posets de partitions, aussi connue sous le nom d'algèbre de Hopf de Faà Di Bruno.
Après avoir rappelé les définitions nécessaires et présenté l'algèbre de Faà di Bruno, nous introduirons une algèbre de Hopf généralisant celle de Faà di Bruno : l'algèbre de Hopf d'incidence des partitions semi-pointées.
 Plus d'infos  


2015-10-09Relaxation de configurations dans le modèle du tas de sable sur la grille Z^2
10:45-11:45
076
Ce GT présente le travail effectué depuis février pendant mon stage de master sous la direction d'Yvan Le Borgne. Ce travail porte sur la relaxation de certaines configurations dans le modèle du tas de sable sur la grille Z^2. Il aborde deux questions distinctes.
1. On se donne une configuration aléatoire définie indépendamment sur chaque sommet par 2 grains avec proba p et 3 grains avec proba 1-p. L'ajout d'un grain à l'origine entraine une relaxation de support rectangulaire. En supposant certaines symétries sur la configuration aléatoire, je montre que la probabilité sur le périmètre du rectangle peut se décrire par des statistiques sur des permutations avec quelques bijections à la clé.
2. Dans le cas des graphes finis, on peut, en distinguant un point, définir une structure de groupe dans le modèle du tas de sable sur un graphe. Dans le cas Z^2, l'étude motive le travail avec des configurations périodiques et le placement du puits à l'infini dans une direction. On a alors des constructions analogues au cas fini mais à ce jour aucune structure naturelle de sous-groupe ne se détache sur des configurations périodiques.
 Plus d'infos  


2015-09-18Polynôme de Tutte, une nouvelle preuve d'universalité
10:45-11:45
Amphithéâtre du LaBRI (050)
Après quelques notions introductives, je vais montrer une nouvelle façon de prouver l'universalité du polynôme de Tutte, façon qui ne nécessite pas les arguments habituels d'induction sur les arêtes du graphe.
Si le temps le permet, je vais aussi montrer comment cela se généralise pour les graphes à ruban (ou graphes plongés dans des surfaces) et les polynômes de Bollobas-Riordan et Penrose.
 Plus d'infos  


2015-07-07Fonctions discrètes harmoniques dans le quart de plan
09:30-10:30
178
Dans cet exposé nous nous intéressons aux fonctions discrètes harmoniques dans des cônes (en particulier dans le quart de plan). La série génératrice de ces fonctions harmoniques satisfait une équation fonctionnelle proche de celle obtenue dans le contexte de l'énumération de marches dans le quart de plan. Nous montrons le lien entre ces fonctions harmoniques et une famille à un paramètre d'applications conformes. Une des motivations à l'étude de ces fonctions est qu'elles permettent le conditionnement au sens de Doob de marches aléatoires.
 Plus d'infos  


2015-06-26Plus longue sous-suite croissante : point de vue probabiliste
10:45-11:45
076
Dans les années 1960, Hammersley a introduit un système de particules dans le but de démontrer (sans y arriver) que la longueur de la plus longue sous-suite croissante d'une permutation uniforme de n éléments est de l'ordre de 2*racine(n). Dans les années 90, plusieurs auteurs ont réussi à compléter l'approche d'Hammersley pour obtenir une preuve probabiliste de ce résultat, l'objectif de cet exposé est de présenter cette stratégie.
N. B. : il s'agit d'un exposé de type "Groupe de Travail", dans le sens où ce sont des résultats pas de moi, vieux, et considérés comme "bien connus", c'est-à-dire connus de très peu de gens.
 Plus d'infos  


2015-06-12On the enumeration of planar Eulerian orientations
10:45-11:45
076
Eulerian planar maps are planar maps with all vertices of even degree. The number of Eulerian planar maps with a fixed number of edges m is well known, and they are in bijection with many combinatorial families, such as balanced Eulerian trees or bi-cubic maps.
Planar Eulerian orientations are directed planar maps in which the in- and out-degrees of every vertex are equal.
We first count the number of planar Eulerian orientations for m <= 12 (m is the number of edges) thanks to an encoding based on bilateral Dyck words. The values found (2, 10, 66, 504, 4216, 37548...) do not match with any known series from the OEIS.
We then present a sequence of algebraic series giving lower and upper bounds of the growth rate of planar Eulerian orientations. We show in particular that the growth rate of planar Eulerian orientations is between 10.69^m and 12.94^m.
 Plus d'infos  


2015-06-05Fonctions symétriques sur les mots et théorème de Redfield-Pólya
10:45-11:45
076
Depuis une vingtaine d’années de multiples généralisations des fonctions symétriques, souvent reliées à la théorie des représentations de certaines algèbres, ont été étudiées. Ces structures admettent des bases indexées par des objets combinatoires (mots, partitions, compositions, partitions d’ensemble en listes, arbres ...) et sont décrites de façon combinatoire et algorithmique. Les applications de ces algèbres sont vastes puisqu’elles interviennent en mathématique, physique et chimie.
C'est dans ce cadre que nous présentons les applications pour l’énumération de certains objets. Nous donnons des versions non-commutatives du théorème d’énumération de Redfield-Pólya (qui a été publié par John Howard Redfield en 1927 puis indépendamment redécouverte en 1937 par George Pólya). Ce théorème peut s'énoncer dans l'algèbre des fonctions symétriques classiques et permet d'énumérer les orbites de l'action d'un groupe fini sur un ensemble fini. Nous l'étudions ici dans l'algèbre des fonctions symétriques sur les mots WSym introduite par Rosas et Sagan en 2004 et dans d'autres algèbres de Hopf combinatoires.
 Plus d'infos  


2015-05-29Séquences récurrentes, triangulations L^infini-Delaunay et un problème d'empilement
10:45-11:45
076
Nous présentons une borne optimale pour la récurrence des transformations de l'intervalle [0,1]. Notre preuve de ce résultat est géométrique est consiste à comprendre les empilements optimaux pour la "pseudo-métrique" dist(x,y) = |xy|. Comme dans le cas euclidien, une preuve possible est via les triangulations de Delaunay. Mais contrairement au cas euclidien, nous utiliserons des triangulations Delaunay pour la métrique L^infini.
Si le temps le permet, on jouera aussi avec des permutations.
 Plus d'infos  


2015-05-22Énumération exacte d’automates acycliques minimaux et bijection avec les fonctions de parking généralisées
10:45-11:45
076
Les fonctions de parking sont intéressantes pour de nombreuses raisons. Elles sont en bijection avec les séquences de Prüfer, les chemins de Dyck décorés, etc. et sont liées à l’inversion de Lagrange, aux polynômes harmoniques diagonaux, etc. En particulier, elles sont en bijection avec les forêts d’arbres enracinés, autrement dit avec les endo-fonctions acycliques.
En 2002, Jim Pitman et Richard P. Stanley ont introduit une généralisation des fonctions de parking. Nous verrons qu'une sous-famille de ces fonctions de parking généralisées est en bijection avec l’ensemble des fonctions de transition des automates finis déterministes acycliques. Nous expliciterons une bijection et nous montrerons que cette dernière transporte une information précieuse sur les langages droits des états de l'automate.
Nous utiliserons cette information pour extraire et énumérer les automates acycliques non-initiaux pour lesquels tous les langages droits des états sont distincts. Enfin par une technique usuelle de graphes, nous obtiendrons une formule exacte d’énumération des automates acycliques minimaux.
 Plus d'infos  


2015-04-17Chemins de Gessel dans le quadrant
10:45-11:45
076
L'énumération des chemins à pas prescrits confinés dans le quadrant, et leur classification selon la nature de la série génératrice associée (algébrique, différentiellement finie, non différentiellement finie) s'est révélée un beau sujet combinatoire au cours de la décennie écoulée.
La classification des modèles à petits pas est maintenant terminée : la série qui compte les chemins du quadrant est D-finie si et seulement si un certain groupe associée à ce modèle est fini.
Du côté des modèles D-finis, un problème subsistait encore : donner une preuve simple de l'algébricité des chemins de Gessel (à pas E, O, NE, SW), d'abord établie à grands coups de calcul formel, puis en utilisant une machinerie sophistiquée d'analyse complexe, qui sort du champ des séries algébriques puisqu'elle fait intervenir les fonctions P et zeta de Weiertrass. Je présenterai une preuve qui reste au niveau des séries formelles et ne brasse que des équations polynomiales.
 Plus d'infos  


2015-04-09Integrability, Solvability and Enumeration
14:00-15:00
076
There are a number of seminal two-dimensional lattice models that are integrable, but have only been partially solved, in the sense that only some properties are fully known (e.g. the two-dimensional Ising model, where the free-energy is known, but not the susceptibility). Alternatively, critical properties are known for some lattices but not others. For example, the critical point of the self-avoiding walk model is known rigorously for the honeycomb lattice, but not for other lattices. Similarly for the q-state Potts model and both bond and site percolation. The critical manifold of the former is known only for some lattices, likewise the percolation threshold is known only for some lattices.
A range of numerical procedures exist, based on exact enumeration, or other numerical work, such as calculating the eigenvalues of transfer matrices, which, when combined with various structural invariants seem to give exact results in those cases that are known to be exact, but can be used to give increasingly precise estimates in those cases which are not exactly known. Reasons for this partial success are not well understood. In this talk I will describe four such procedures, and demonstrate their performance, and speculate on their partial success.
 Plus d'infos  


2015-03-27Nouvelles bijections entre tableaux de Young, diagrammes d'arcs et marches dans le treillis de Young
10:45-11:45
076
Les objets étudiés en combinatoire énumérative montrent une grande diversité : marches, permutations, tableaux de Young, diagrammes d'arcs... La liste est longue. Bien que les apparences laissent croire à une absence de corrélation, l’œil avisé saura voir les liens qui unissent ces objets entre eux. Cet exposé présentera quelques uns de ces liens.
L'objectif principal est la preuve d'une conjecture de Sophie Burrill, qui stipule que le nombre de tableaux de Young dont la hauteur est majorée par 2k est égal au nombre d'appariements ouverts ne présentant pas de nesting d'ordre k+1. Cela sera l'occasion de présenter la très belle bijection de Chen, Deng, Du, Stanley, Yan entre partitions d'ensemble et marches vacillantes. Nous donnerons par la suite la description de quelques classes combinatoires en bijection avec les appariements ouverts. Nous prendrons alors notre plus grand shaker et secouerons tout cela afin d'obtenir la preuve d'une conjecture fraîchement servie (avec éventuellement quelques olives si le temps le permet).
 Plus d'infos  


2015-02-13Pavages : quantifier l'apériodicité d'un jeu de tuiles
10:45-11:45
076
Un jeu de tuiles de Wang est un ensemble fini de carrés unités dont on a colorié chaque côté. Un jeu de tuiles T pave le plan si celui-ci peut être recouvert par des translatés de copies d'éléments de T (selon Z^2), de sorte que les arêtes en contact de deux tuiles adjacentes soient de même couleur. Un jeu de tuiles est dit apériodique s'il pave le plan mais si aucun pavage obtenu n'est invariant par une translation. La plupart des jeux de tuiles apériodiques sont construits de façon autosimilaire (via une règle de substitution).
Le but de cet exposé est d'introduire des invariants permettant de quantifier le niveau d'apériodicité d'un jeu de tuiles de Wang. L'un des invariants est de nature topologique, l'autre est métrique. Ils reposent sur la manière dont le jeu de tuiles pave d'autres objets que le plan. Ces invariants nous permettent de démontrer que les jeux de tuiles de Kari et Culik ne sont pas gouvernés par une construction autosimilaire, car trop apériodiques.
 Plus d'infos  


2015-01-23Combinatoire des arbres Cambriens
09:30-10:30
076
Les arbres Cambriens fournissent une généralisation naturelle des arbres binaires de recherche, dans laquelle chaque sommet peut avoir un parent et deux enfants, ou deux parents et un enfant. Ce premier exposé présentera la combinatoire de ces arbres, et en particulier une correspondance entre les permutations signées et les arbres Cambriens à niveaux, similaire à la correspondance de Robinson-Schensted ou à la correspondance sylvestre. On abordera aussi la combinatoire des paires d'arbres Cambriens jumeaux, qui sont comptés par des nombres Baxter-Cambriens encore assez mystérieux.
Cet exposé est partiellement basé sur des travaux en commun avec Grégory Chatel (Univ. Marne la Vallée) et Carsten Lange (Univ. Munich).
 Plus d'infos  


2015-01-23Algèbres de Hopf Cambriennes
10:45-11:45
076
Ce deuxième exposé présentera des applications des arbres Cambriens à la construction d'algèbres de Hopf combinatoires. On présentera en particulier l'algèbre Cambrienne qui généralise l'algèbre de Loday-Ronco sur les arbres binaires, et on étudiera certaines de ses propriétés (formules combinatoires pour les produits et coproduits, bases multiplicatives, indécomposables, ...). Si le temps le permet, on abordera aussi des généralisations naturelles de cette algèbre, dont les bases sont indexées par les paires d'arbres Cambriens jumeaux et par les arbres Schröder Cambriens.
Cet exposé est basé sur un travail en commun avec Grégory Chatel (Univ. Marne la Vallée).
 Plus d'infos  


2014-12-19La méthodologie de l'ansatz cellulaire appliquée aux tableaux du PASEP 2/2
10:45-11:45
076
Je montrerai le lien entre les exposés récents au GT de Patxi Laborde Zubieta et d'Olya Mandelshtam et la théorie de l'ansatz cellulaire, théorie qui avait l'objet d'une petite école en 2011/12.
Je ferai un rappel pédagogique sur quelques traits essentiels de cette théorie : comment associer un tableau (appelé Q-tableau) à une algèbre quadratique Q d'un certain type, comment définir une notion d'algèbre réciproque. Les tableaux alternatifs et les tableaux boisés apparaissent comme les Q-tableaux associés à l'algèbre du PASEP (définie par la relation DE=ED+E+D) et à son algèbre réciproque. Rappelons que le PASEP (partially asymmetric exclusion process) est un modèle très célèbre en physique des systèmes dynamiques et les tableaux associés permettent d'interpréter les probabilités stationnaires du modèle.
La théorie générale de l'ansatz cellulaire donne une méthode pour construire des bijections entre ces tableaux et d'autres objets combinatoires à partir d'une représentation combinatoire de l'algèbre Q. Dans le cas de l'algèbre du PASEP, je rappellerai une telle bijection entre les tableaux alternatifs et les permutations. Cette bijection permet de retrouver bijectivement le résultat de Patxi sur le nombre de coins occupés dans les tableaux boisés de taille n.
Dans un deuxième exposé, je rappellerai une autre méthode permettant de construire des bijections faisant intervenir ces Q-tableaux, appelée « démultiplication » des équations définissant l'algèbre quadratique Q. Dans le cas de l'algèbre du PASEP, nous obtenons une (nouvelle) bijection entre les tableaux alternatifs et des paires de mots. Cette bijection mériterait d'être étudiée. Dans le cas des tableaux alternatifs de Catalan (associée au TASEP) cette bijection devient la bijection introduite dans l'exposé d'Olya entre ces tableaux de Catalan et certaines paires de chemins.
Enfin, si le temps le permet, je rappellerai que dans le cas de l'algèbre définie par la relation UD=DU+Id, certains Q-tableaux associés sont les (graphes de) permutations et une bijection associée à une représentation combinatoire est l'algorithme RSK (Robinson-Schensted-Knuth). De plus la méthode de démultiplication des équations conduit naturellement à la même correspondance RSK.
 Plus d'infos  


2014-12-12La méthodologie de l'ansatz cellulaire appliquée aux tableaux du PASEP 1/2
10:45-11:45
076
Je montrerai le lien entre les exposés récents au GT de Patxi Laborde Zubieta et d'Olya Mandelshtam et la théorie de l'ansatz cellulaire, théorie qui avait l'objet d'une petite école en 2011/12.
Je ferai un rappel pédagogique sur quelques traits essentiels de cette théorie : comment associer un tableau (appelé Q-tableau) à une algèbre quadratique Q d'un certain type, comment définir une notion d'algèbre réciproque. Les tableaux alternatifs et les tableaux boisés apparaissent comme les Q-tableaux associés à l'algèbre du PASEP (définie par la relation DE=ED+E+D) et à son algèbre réciproque. Rappelons que le PASEP (partially asymmetric exclusion process) est un modèle très célèbre en physique des systèmes dynamiques et les tableaux associés permettent d'interpréter les probabilités stationnaires du modèle.
La théorie générale de l'ansatz cellulaire donne une méthode pour construire des bijections entre ces tableaux et d'autres objets combinatoires à partir d'une représentation combinatoire de l'algèbre Q. Dans le cas de l'algèbre du PASEP, je rappellerai une telle bijection entre les tableaux alternatifs et les permutations. Cette bijection permet de retrouver bijectivement le résultat de Patxi sur le nombre de coins occupés dans les tableaux boisés de taille n.
Dans un deuxième exposé, je rappellerai une autre méthode permettant de construire des bijections faisant intervenir ces Q-tableaux, appelée « démultiplication » des équations définissant l'algèbre quadratique Q. Dans le cas de l'algèbre du PASEP, nous obtenons une (nouvelle) bijection entre les tableaux alternatifs et des paires de mots. Cette bijection mériterait d'être étudiée. Dans le cas des tableaux alternatifs de Catalan (associée au TASEP) cette bijection devient la bijection introduite dans l'exposé d'Olya entre ces tableaux de Catalan et certaines paires de chemins.
Enfin, si le temps le permet, je rappellerai que dans le cas de l'algèbre définie par la relation UD=DU+Id, certains Q-tableaux associés sont les (graphes de) permutations et une bijection associée à une représentation combinatoire est l'algorithme RSK (Robinson-Schensted-Knuth). De plus la méthode de démultiplication des équations conduit naturellement à la même correspondance RSK.
 Plus d'infos  


2014-12-05La fonction de Fabius
10:45-11:45
076
Considérons la variable aléatoire obtenue en sommant des variables aléatoires indépendantes uniformes sur [0,2^-n] (le support de cette variable est dans [0,1]). Sa distribution est partout C^infini mais nulle part analytique ! C'est pour cette raison qu'elle a été introduite par Fabius (en 1966).
J'expliquerai par une promenade dynamique via le mot de Thue-Morse comment construire cette fonction.
 Plus d'infos  


2014-11-28Jardinage d'automne : comment réussir une transplantation d'arbres dans vos polyominos dirigés convexes
10:45-11:45
076
En tant que combinatoriciens, nous avons tous quelques arbres qui poussent au fond du jardin. Nous avons aussi quelques polyominos qui prennent de la poussière sur nos étagères. Dans cet atelier, grâce à la transplantation, nous allons montrer comment donner une seconde vie à tous nos polyominos dirigés convexes pour mettre en valeur nos arbres préférés.
Nous utiliserons cette méthode pour obtenir facilement et instantanément les fonctions génératrices des polyominos dirigés convexes avec différentes combinaisons de statistiques : hauteur, largeur, longueur de la dernière ligne/colonne, nombre de coins. Nous énumérerons différentes familles de polyominos dirigés convexes : les polyominos symétriques, les polyominos parallélogrammes et le cas difficile des polyominos dirigés k-convexes.
Pour les travaux pratiques, n'oubliez surtout pas d'apporter avec vous tous vos outils de jardinages : fonctions génératrices, mots et expressions rationnelles.
Il s'agit d'un travail réalisé en commun avec Simone Rinaldi et Samanta Socci de l'université de Sienne en Italie.
 Plus d'infos  


2014-11-14Une extension de l'algorithme de von Neumann pour simuler combinatoirement des variables exponentielles
10:45-11:45
076
Dans une note datant du début des années 1950, John von Neumann a décrit un algorithme très simple, ne faisant intervenir que des comparaisons et des compteurs, pour simuler de manière exacte une variable aléatoire suivant la loi exponentielle ; algorithme qui a d'ailleurs été analysé en détail par Flajolet et Saheb dans les années 1980.
Von Neumann termine sa note par une indication intrigante, affirmant que la méthode peut facilement s'étendre à « toute distribution satisfaisant une équation différentielle du premier ordre ». À ma connaissance, cette extension n'a jamais été explicitée, ni même précisée en ce qui concerne les conditions d'applicabilité.
Je présenterai une interprétation possible de la remarque de von Neumann, et un algorithme de simulation qui ressemble effectivement à une généralisation raisonnable de son algorithme. En l'occurrence, il s'agit de faire porter l'équation différentielle non pas sur la densité, mais sur la probabilité complémentaire de la fonction de répartition (« fonction de survie »).
 Plus d'infos  


2014-11-07A Determinantal Formula for Catalan Tableaux and TASEP Probabilities
10:45-11:45
076
We present a determinantal formula for the steady state probability of each state of the TASEP (Totally Asymmetric Simple Exclusion Process) with open boundaries, a 1D particle model that has been studied extensively and displays rich combinatorial structure. These steady state probabilities are computed by the enumeration of Catalan tableaux, which are certain Young diagrams filled with alpha's and beta's that satisfy some conditions on the rows and columns. We construct a bijection from the Catalan tableaux to weighted lattice paths on a Young diagram, and from this we enumerate the paths with a determinantal formula, building upon a formula of Narayana that counts unweighted lattice paths on a Young diagram. Finally, we provide a formula for the enumeration of Catalan tableaux with a given number of rows, which corresponds to the steady state probability that in the TASEP on a lattice with n sites, precisely k of the sites are occupied by particles. This formula is an alpha and beta generalization of the Narayana numbers. We conclude with some extensions to a two-species PASEP, in which there are particles of type 1 and 2 hopping right with rate 1 and hopping left with rate q, with only type 2 particles being able to enter and exit. We describe certain Catalan-like tableaux for the q=0 case, and two-species alternative tableaux for the q=1 case.
 Plus d'infos  


2014-10-24Un nouveau codage pour les processus de coalescence. Applications aux cas additif et multiplicatif.
10:45-11:45
076
Travail commun avec Nicolas Broutin (INRIA, Rocquencourt).
Les processus de coalescence ont pour but de décrire l'évolution de la composition d'un mélange composé de particules (ou d'amas de particules), qui ont tendance à s'agglomérer selon un certain mécanisme aléatoire.
Certains modèles peuvent être codés au niveau des particules par des structures combinatoires aléatoires qui évoluent avec le temps.
Par exemple, le coalescent multiplicatif peut se représenter sous la forme de l'évolution de la taille des composantes connexes dans G(n,p) (= Graphe d'Erdös-Rényi) lorsque p évolue.
Dans ce travail, nous présentons un nouveau codage qui permet de représenter ces processus sous la forme d'agglomération d'intervalles de la ligne. Cela mène à de nouveaux résultats, en particulier, dans le cas du coalescent multiplicatif.
 Plus d'infos  


2014-10-17Dénombrement des coins occupés dans les tableaux boisés
10:45-11:45
076
Le bord des tableaux boisés joue un rôle important dans le lien qu'il y a entre ces objets et le modèle du PASEP. Notamment, les coins correspondent aux sites où un changement d'état est possible. Dans cet exposé, nous verrons que dans l'ensemble des tableaux boisés de taille n, qui est de cardinal n!, il y a n! coins occupés. J'exposerai deux preuves de ce résultat, la première utilise la structure récursive des tableaux boisés donnée par l'algorithme d'insertion, tandis que la deuxième dénombre une statistique sur les permutations équivalente à celle des coins occupés. Enfin, je vous présenterai une conjecture raffinant ce résultat : dans les classes non-ambiguës il y a autant de coins occupés que de tableaux boisés.
 Plus d'infos  


2014-10-10Une généralisation de la relation des quadrangulations sur les constellations et les hypercartes
10:45-11:45
178
Les constellations sont des cartes spéciales qui généralisent la notion de carte en terme de factorisation de permutations. Dans cet exposé, nous généralisons une relation énumérative de Jackson et Visentin (1990) entre les quadrangulations ordinaires et biparties. Nous présenterons une relation similaire entre les constellations et les hypercartes en passant par une factorisation de caractère. Avec cette relation, on retrouve le comportement asymptotique des hypercartes établi dans Chapuy (2009), avec une preuve simplifiée.
 Plus d'infos  


2014-09-26The role of residue and quotient table in the theory of k-Schur functions
10:45-11:45
076
Recently, residue and quotient tables were defined, and were used to describe strong covers in the lattice of k-bounded partitions. In the talk, we will show how residue and quotient tables can be used to describe many other results in the theory of k-bounded partitions and k-Schur functions, including k-conjugates, weak horizontal and vertical strips, and the k-Murnaghan-Nakayama rule. If time permits, evidence will be presented for the claim that one of the most important open questions in the theory of k-Schur functions, a general rule that would describe their product, can also be concisely stated in terms of residue tables.
 Plus d'infos  


2014-09-19Combinatoire algébrique et théories quantiques des champs
10:45-11:45
076
La combinatoire (algébrique, analytique, etc.) joue un rôle central dans le formalisme de théories quantiques des champs (TQC). Dans ce séminaire, j'introduirai d'abord quelques notions de TQC : les graphes de Feynman, leur fonction génératrice et finalement la renormalisation (c.-à-d. la manière dont on manipule en TQC des intégrales, dites de Feynman, divergentes).
J'introduirai ensuite la notion d'algèbre de Hopf et j'illustrerai cela avec l'exemple de l'algèbre de Connes-Kreimer de graphes de Feynman. Cette construction code d'une manière élégante la combinatoire de la renormalisation dans une structure d'algèbre de Hopf.
Si le temps le permet, j'indiquerai comment cela se généralise pour des TQC non-commutatives, où les graphes sont remplacés par des cartes combinatoires.
 Plus d'infos  


2014-09-12Arbres binaires et « quatre couleurs »
10:45-11:45
076
En 1986 nous avons présenté avec Serge Dulucq une communication au Colloque sur les Arbres en Algèbre et Programmation (CAAP) dans laquelle nous donnions une preuve de l'équivalence entre l'existence d'une 4-coloration pour toute carte planaire et l'égalité de deux sous-ensembles du produit cartésien de deux monoïdes libres. Une étape de notre preuve consistait en l'équivalence de ces propriétés avec une construction sur les arbres binaires.
Récemment (en 2012) B. Cooper, E. Rowland et D. Zeilberger (voir http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/4ct.html) publient un résultat semblable et en tirent des conséquences plus intéressantes que notre premier résultat.
Je me propose de présenter ces deux approches.
 Plus d'infos  


2014-07-04Une introduction à la théorie des jeux combinatoires (2/2)
10:45-11:45
076
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 !

Remarque du secrétaire, après discussion avec l'orateur : celui-ci fera les rappels nécessaires pour permettre à tous de suivre cette séance, qu'ils aient assisté ou non à la première.
 Plus d'infos  


2014-06-13Arbres binaires, permutations et ordres d'insertion
10:45-11:45
076
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.
 Plus d'infos  


2014-05-26Asymptotic Lattice Path Enumeration Using Diagonals
11:00-12:00
076
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.
 Plus d'infos  


2014-05-23On semi-conjugate rational functions
10:45-11:45
076
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.
 Plus d'infos  


2014-04-11Une introduction à la théorie des jeux combinatoires 1
10:45-11:45
076
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 !
 Plus d'infos  


2014-04-04Les tableaux boisés de Baxter 2/2
10:45-11:45
076
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.
 Plus d'infos  


2014-03-28Les tableaux boisés de Baxter 1/2
10:45-11:45
076
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.
 Plus d'infos  


2014-02-21Chemins de l'espace confinés dans un octant
10:45-11:45
076
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).
 Plus d'infos  


2014-02-07Automates cellulaires probabilistes à loi invariante markovienne
10:45-11:45
076
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.
 Plus d'infos  


2014-01-31Probabilité que n points soient en position convexe dans un disque
10:45-11:45
076
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.
 Plus d'infos  


2014-01-17Mesures Markov-uniformes sur la droite, le plan et les arbres (travail en cours avec Irène Marcovici)
10:45-11:45
076
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.
 Plus d'infos  


2014-01-10Un nouvel arbre de génération pour les permutations, préservant les points fixes
10:45-11:45
076
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.
 Plus d'infos  


2013-12-20Longueur des éléments pleinement commutatifs et algèbres de Temperley-Lieb généralisées
10:45-11:45
076
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.
 Plus d'infos  


2013-12-13Sur la L1-réalisabilité des triangulations
10:45-11:45
076
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.
 Plus d'infos  


2013-12-06Calcul du rang des configurations de certaines familles de graphes (Cliques, Roues)
10:45-11:45
076
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)
 Plus d'infos  


2013-11-29Quoi de neuf sur les arbres pondérés ?
10:45-11:45
076
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.
 Plus d'infos  


2013-11-22Canopée des arbres binaires et intervalles genevois de l'associaèdre (2/2)
10:45-11:45
076
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.
 Plus d'infos  


2013-11-15Canopée des arbres binaires et intervalles genevois de l'associaèdre (1/2)
10:45-11:45
076
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.
 Plus d'infos  


2013-11-08Coins Nord-Est dans les chemins du quart de plan
10:45-11:45
076
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)
 Plus d'infos  


2013-10-25Génération aléatoire uniforme dans les langages rationnels (suite)
10:45-11:45
076
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.
 Plus d'infos  


2013-10-18Permutations triables par deux piles en parallèle
10:45-11:45
076
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.
 Plus d'infos  


2013-10-04Génération aléatoire uniforme dans les langages rationnels
10:45-11:45
076
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.
 Plus d'infos  


2013-09-20Compression d'arbres
10:45-11:45
076
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.
 Plus d'infos  


2013-09-13Permutations polonaises
10:45-11:45
salle 3 du bâtiment A29
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).
 Plus d'infos  


2013-06-21An algebraic-combinatorial approach to the Kronecker problem via quantum group representations
10:45-11:45
076
In this talk, I will describe our on-going efforts towards an algebraic-combinatorial approach towards the Kronecker problem.
Consider the natural embedding of GLm(C) × GLn(C) into GLmn(C) via the Kronecker product. With respect to this embedding, a GLmn(C) irreducible representation Vλ(mn) splits into a direct sum of irreducible GLm(C) × GLn(C) representations:
Vλ(mn) = ⊕μ,ν χμ,νλ Vμ(m) ⊗ Vν(n)

The Kronecker problem is the problem of computing the multiplicity coefficents χμ,νλ.
We consider the quantized version of this problem and propose an approach to this problem via the theory of quantum groups and the crystal bases. I will talk about our initial results in this direction. The talk is based on joint work with Milind Sohoni and K. V. Subrahmanyam.
 Plus d'infos  


2013-06-21Une formule d'équerre multivariée pour les arbres croissants
09:30-10:30
076
Plusieurs formules sommatoires d'équerre pour les arbres binaires sont apparues récemment dans la littérature. Dans cet exposé nous présentons un analogue pour des arbres croissants de taille r, faisant intervenir O(r2) paramètres, alors que la plupart des formules dans la littérature ont un nombre fixe de paramètres. Le membre de droite de la formule s'écrit comme un produit de facteurs de degrés 2. La preuve de la formule est bijective et est basée sur une nouvelle opération de recollage de chaînes pour construire un arbre.
 Plus d'infos  


2013-06-14Le vecteur h torique, les nombres de Narayana, et des partitions non-croisées
10:45-11:45
076
Le vecteur h torique est un invariant énigmatique des polytopes et des ensembles ordonnés Eulériens, introduit par Stanley. Dans cet exposé nous explorons deux cas spéciaux où le calcul de cet invariant est relié aux partitions non-croisées et aux nombres de Narayana. Dans le cas des polytopes cubiques, nous verrons qu'un renforcement de la symétrie exprimée par les équations de Dehn-Somerville se démontre en utilisant l'involution de Simion et Ullman sur le treillis des partitions non-croisées. Dans le cas des polytopes simples, nous verrons que la réponse à une question de Kalai posée dans les années 80 peut être donnée en utilisant des variantes des nombres de Narayana.
Les résultats sur les polytopes cubiques sont obtenus en collaboration avec Sarah Birdsong.
 Plus d'infos  


2013-05-31Une définition unifiée de l'activité pour le polynôme de Tutte
10:45-11:45
076
On retrouve dans la littérature plusieurs caractérisations différentes du polynôme de Tutte d'un graphe. Tutte l'a notamment défini grâce à une notion d'activité basée sur un étiquetage ordonné des arêtes. Plus tard, Bernardi a donné une notion non équivalente de l'activité en plongeant le graphe dans une surface.
On verra que d'autres notions d'activité peuvent être ainsi imaginées et qu'elles se regroupent toutes en une seule et même définition. On en profitera pour comprendre macroscopiquement le lien entre les différentes caractérisations du polynôme de Tutte.
À noter que cet exposé commencera par un état de l'art sur le polynôme de Tutte, cela permettra de remettre à plat ses connaissances sur le sujet.
 Plus d'infos  


2013-05-24Une fraction continue géométrique
10:45-11:45
076
Les fractions continues permettent de donner des meilleures approximations rationnelles d'un nombre réel donné. Il est également possible d'interpréter cet algorithme comme des « changements de bases » dans un tore plat. Je présenterai un algorithme qui généralise cette construction et permet de faire des fractions continues sur des surfaces plates de genre supérieur (chaque étape de l'algorithme peut être vu comme un changement de triangulation). On verra également que cet algorithme décrit les trajectoires de particules dans certains billards.
C'est un travail en commun avec Corinna Ulcigrai.
 Plus d'infos  


2013-05-17Algorithmes probabilistes pour la fouille quantitative de très grandes masses de données
10:45-11:45
076
L'avalanche de données qui nous sont disponibles --- provenant d'Internet, des banques, du séquençage de génomes, des réseaux de capteurs, etc. --- rendent généralement illusoire l'idée qu'on peut les examiner de manière très précise. La fouille quantitative ne s'attache donc qu'à extraire des statistiques élémentaires de flux, mais en le faisant de manière très efficace et peu couteuse en ressources (temps de calcul et espace) : le nombre d'éléments distincts, les éléments rares, et fréquents, le profils de données, les indices de similarité.
Dans cet exposé, il sera brassé un large panorama d'algorithmes qui se servent de techniques probabilistes pour atteindre de très grandes performances, là où une algorithmique déterministe serait inadéquate.
 Plus d'infos  


2013-04-19Un pont entre les espèce de structures et la combinatoire analytique (2/2)
10:45-11:45
076
Le livre Analytic Combinatorics de Flajolet et Sedgewick propose un cadre agréable -- la Méthode Symbolique -- pour définir des classes d'objets combinatoires à partir de grammaires (systèmes combinatoires) semblables à celles de la théorie des langages. En se plaçant dans ce cadre, il est possible d'effectuer un certain nombre de traitements quasi-automatiques sur ces objets : manipulation de séries génératrices, génération aléatoire, analyse asymptotique, ... Cependant, lorsqu'il s'agit d'implanter de telles méthodes, il est nécessaire de se poser la question : comment savoir si un système combinatoire donné est « bien formé » ? Cette question nous a amené à considérer une autre approche permettant de décrire des objets combinatoires : la Théorie des Espèces de Structures. Bien qu'étudiées à des fins très différentes, ces deux approches présentent de nombreux points communs et permettent, lorsqu'elles sont associées, de fournir une base de travail solide pour l'automatisation d'un certain nombre de traitements combinatoires. Dans cet exposé, nous présenterons ces deux approches et nous décrirons les passerelles menant de l'une à l'autre, dans le but de caractériser les systèmes qui décrivent effectivement des structures combinatoires.
Cette présentation est basée sur un travail en commun avec B. Salvy et M. Soria.
 Plus d'infos  


2013-04-12Wilf-équivalences dérivées d'une bijection entre Av(231) et Av(132)
10:45-11:45
076
Dans le cadre de l'étude d'opérateurs de tri de permutations composés de piles et de miroirs, j'ai défini dans mon exposé du 29 mars une bijection (notée P) entre la classe des permutations évitant 231 et celle des permutations évitant 132. Nous verrons dans cet exposé d'autres résultats que l'on peut obtenir grâce à cette bijection P. Plus précisément, nous démontrerons que les classes Av(231,π) et Av(132,P(π)) sont Wilf-équivalentes (c'est-à-dire énumérées par la même séquence) pour de nombreux motifs π que nous caractériserons. Nous verrons aussi que ces classes Av(231,π) sont toutes Wilf-équivalentes entre elles, à k=|π| fixé.
Il s'agit d'un travail en commun avec Michael Albert.
À noter qu'il n'est pas nécessaire d'avoir assisté à l'exposé du 29 mars pour venir à cette séance du GT.
 Plus d'infos  


2013-04-05Éléments « totalement commutatifs » et chemins du plan
10:45-11:45
076
Un élément d'un groupe de Coxeter W est dit « totalement commutatif » si on peut passer d'une de ses décompositions réduites à toute autre en utilisant uniquement les relations de commutation. Ces éléments ont été étudiés en détail par Stembridge dans le cas où W est fini. Nous considérons ici W fini ou affine, et énumérons les éléments totalement commutatifs selon leur longueur de Coxeter.
Notre approche consiste à encoder ces éléments par des chemins du plan que nous décomposons récursivement pour obtenir les fonctions génératrices voulues. Pour le type A fini, cela redonne un théorème de Barcucci et al. ; pour A affine, cela simplifie et précise des résultats de Hanusa et Jones. Pour tous les autres groupes finis et affines, nos résultats sont nouveaux.
Travail en collaboration avec Riccardo Biagioli et Frédéric Jouhet (Lyon).
 Plus d'infos  


2013-03-29Tri de permutations par plusieurs piles et miroirs, et Wilf-équivalences associées
10:45-11:45
178
On étudie les opérateurs de tri de permutations obtenus en composant l'opérateur S de tri par une pile de Knuth et l'opérateur R de miroir, un certain nombre de fois. Pour tout opérateur A de cette forme, on donne une bijection entre l'ensemble des permutations triées par S.A et l'ensemble de celles triées par S.R.A, démontrant ainsi que ces ensembles ont la même séquence d'énumération, mais aussi que de nombreuses statistiques classiques sur les permutations ont la même distribution sur ces deux ensembles. La description de cette famille de bijections repose deux ingrédients principaux : une caractérisation des préimages d'une permutation par S donnée par Mireille Bousquet-Mélou, et une bijection apparemment nouvelle entre l'ensemble des permutations qui évitent le motif 231 et l'ensemble de celles qui évitent 132, qui préserve de nombreuses statistiques. On présente aussi d'autres propriétés de cette bijection, en particulier pour trouver des familles de classes de permutations équivalentes au sens de Wilf.
Il s'agit d'un travail en commun avec Michael Albert.
 Plus d'infos  


2013-03-08Un pont entre les espèce de structures et la combinatoire analytique (1/2)
10:45-11:45
076
Le livre Analytic Combinatorics de Flajolet et Sedgewick propose un cadre agréable -- la Méthode Symbolique -- pour définir des classes d'objets combinatoires à partir de grammaires (systèmes combinatoires) semblables à celles de la théorie des langages. En se plaçant dans ce cadre, il est possible d'effectuer un certain nombre de traitements quasi-automatiques sur ces objets : manipulation de séries génératrices, génération aléatoire, analyse asymptotique, ... Cependant, lorsqu'il s'agit d'implanter de telles méthodes, il est nécessaire de se poser la question : comment savoir si un système combinatoire donné est « bien formé » ? Cette question nous a amené à considérer une autre approche permettant de décrire des objets combinatoires : la Théorie des Espèces de Structures. Bien qu'étudiées à des fins très différentes, ces deux approches présentent de nombreux points communs et permettent, lorsqu'elles sont associées, de fournir une base de travail solide pour l'automatisation d'un certain nombre de traitements combinatoires. Dans cet exposé, nous présenterons ces deux approches et nous décrirons les passerelles menant de l'une à l'autre, dans le but de caractériser les systèmes qui décrivent effectivement des structures combinatoires.
Cette présentation est basée sur un travail en commun avec B. Salvy et M. Soria.
 Plus d'infos  


2013-03-01Évacuation et promotion
10:45-11:45
076
Dans les années soixante (non, il n'y a pas si longtemps:-) Schützenberger a créé de toutes pièces la théorie combinatoire du « jeu de taquin ». Au départ il s'agissait de mieux comprendre une construction de Schensted (devenue ensuite « algorithme RSK »), et ses relations avec les représentations du groupe symétrique. Vers 1970 Schützenberger a fait agir les algorithmes du jeu de taquin sur n'importe quel ensemble partiellement ordonné fini P, et a ainsi défini deux transformations fondamentales sur les extensions linéaires de P, qu'il a progressivement appelées « évacuation » et « promotion ». Schützenberger a énoncé et prouvé plusieurs théorèmes fascinants vérifiés par ces transformations (par exemple l'évacuation est involutive).
En 2009 Stanley a recensé ces résultats et en a publié une présentation simplifiée, qui intègre en particulier des travaux de Haiman et de Reutenauer publiés autour de 1990. L'évacuation et la promotion apparaissent ainsi comme de simples permutations circulaires, modifiées a minima pour être compatibles avec un ordre partiel donné. J'exposerai ce point de vue en utilisant un logiciel où les « glissements » (opérations caractéristiques du jeu de taquin) sont exécutés par une application personnelle Flash (la technologie infâme d'Adobe).
 Plus d'infos  


2013-02-22Coefficients de structure de l’algèbre de Hecke de la paire (S2n, Bn)
10:45-11:45
076
L’algèbre du groupe symétrique C[Sn] est l’algèbre des combinaisons linéaires des permutations de taille n. Une base du centre de l’algèbre C[Sn] est donnée par les Kλ, où Kλ est la somme des permutations de type cyclique λ. Les coefficients de structure αλμν décrivent le produit dans le centre de C[Sn] : Kλ Kμ = ∑ναλμν Kν .
En 1958, Farahat et Higman ont démontré la polynomialité en n des coefficients αλμν , lorsque λ, μ et ν sont des partitions fixées, complétées avec des parts égales à 1 pour obtenir des partitions de n. En 1999, Ivanov et Kerov ont donné une nouvelle démonstration en introduisant les permutations partielles. Dans cet exposé, on commencera par présenter le cas du centre de l’algèbre du groupe symétrique. Après, on considèrera l’algèbre de Hecke de la paire (S2n, Bn) qui est un analogue du centre de l’algèbre du groupe symétrique. On donnera à la fin un résultat de polynomialité des coefficients de structure de cette algèbre en suivant la méthode de Ivanov et Kerov.
 Plus d'infos  


2013-02-08Lattice paths from an order-theoretic perspective
10:45-11:45
076
We will present some results and open problems regarding lattice paths which arise from certain natural partial order structures they can be endowed with. Some of the topics we will discuss are: rank-unimodality, enumeration of chains, computation of the Euler characteristic of distributive lattices of paths, order-isomorphisms with other poset of relevant combinatorial interest, the pattern containment order for lattice paths.
 Plus d'infos  


2013-02-01A combinatorial approach to lattice path asymptotics
10:45-11:45
076
Several di fferent approaches to determine the exponential growth for lattice paths restricted to the quarter plane have recently appeared. This talk will survey this recent progress and o ffer a relatively simple strategy that is surprisingly general, gives tight bounds and sheds some insight on the fundamental diff erences between walks restricted to a region defi ned by one boundary, and those restricted by two boundaries.
 Plus d'infos  


2013-01-25Propriétés asymptotiques de quelques classes de graphes à mineurs exclus
10:45-11:45
076
Soit A une classe de graphes étiquetés, fermée pour l'extraction de mineurs. Soit G_n un graphe aléatoire de taille n pris uniformément dans A. Quand n est grand, quelle est la probabilité que G_n soit connexe ? Plus généralement, combien de composantes connexes a-t-il ? Grâce aux travaux de McDiarmid et de ses collaborateurs, ces questions sont désormais résolues lorsque tous les mineurs interdits sont connexes. C'est par exemple le cas des graphes planaires.
Nous étudions, via une énumération exacte, une collection de classes A définies par l'interdiction de mineurs dont certains ne sont pas 2-connexes, et montrons que leur propriétés asymptotiques peuvent être très différentes de celles obtenues dans le cas de mineurs 2-connexes. Ces propriétés dépendent de la nature des singularités dominantes de la série génératrice C(z) qui compte les graphes connexes de A. Nous classons nos exemples selon cette nature, ce qui constitue un premier pas (modeste) vers une classification complète des classes de graphes closes par extraction de mineurs.
(travail en commun avec Kerstin Weller, Oxford)
 Plus d'infos  


2013-01-11Chemins auto-évitants dans un demi-plan
10:45-11:45
076
Il y a deux ans, Duminil-Copin et Smirnov ont prouvé une (relativement) vieille conjecture de Nienhuis (1982), selon laquelle le nombre de chemins auto-évitants de longueur n sur le réseau hexagonal croît en gros comme mu^n, avec mu=sqrt(2+sqrt(2)).
J'avais présenté leur preuve à ce groupe de travail à l'automne 2010. Elle a réveillé chez beaucoup de gens l'espoir de prouver d'autres conjectures du domaine.
Dans cet exposé, je présenterai ainsi la preuve d'une conjecture plus jeune (1995) de Batchelor et Yung, qui traite des chemins auto-évitants confinés dans un demi-plan, en interaction avec la frontière de ce demi-plan.
(travail joint avec N. Beaton, J. de Gier, H. Duminil-Copin et A. Guttmann)
 Plus d'infos  


2012-12-14Arbres et cartes munis de forêt couvrante
10:45-11:45
076
Dans le monde fascinant de l'énumération de cartes, on dénombre deux grandes familles de bijection : la première transforme les cartes en mobiles, la seconde en arbres bourgeonnants. D'abord introduites par Schaeffer pour les quadrangulations et cartes tétravalentes, ces bijections ont été généralisées grâce à Bouttier, Di Francesco et Guitter.
Cet exposé sera l'occasion de mettre en avant les arbres de la seconde famille, à savoir les arbres bourgeonnants. Nous montrerons l'utilité de ces objets pour l'énumération de cartes munies de forêt couvrante, notre actuel sujet de recherche.
La première partie se voudra avant tout didactique, elle présentera les arbres bourgeonnants tels qu'ils ont été introduits par Bouttier, Di Francesco et Guitter. Par suite, nous enrichirons ces objets avec des forêts couvrantes afin de retomber sur notre problématique de départ. Une étude combinatoire permettra alors d'exhiber une propriété fort intéressante de positivité, qui n'est pas sans rappeler la positivité des coefficients du polynôme de Tutte.
À noter que cet exposé aura de beaux dessins.
Travail commun avec Mireille Bousquet-Mélou.
 Plus d'infos  


2012-12-07Résultats récents obtenus grâce aux tableaux boisés
10:45-11:45
178
Cet exposé se veut un survol des résultats combinatoires obtenus ces deux dernières années grâce aux tableaux boisés. Ces objets, qui peuvent être vus comme une nouvelle incarnation des tableaux de permutations (Postnikov) ou des tableaux alternatifs (Viennot), jouent un rôle crucial dans l'interprétation combinatoire d'un modèle de physique nommé PASEP. L'atout des tableaux boisés est une procédure récursive beaucoup plus simple que les constructions antérieures. Je donnerai dans cet exposé, des applications combinatoires de cette procédure.
 Plus d'infos  


2012-11-16Towards randomly generated mammals...
10:45-11:45
076
Genome arrangements, a major mechanism of evolution, shuffle genetic material along chromosomes. Thus, a now standard approach models groups of close genomes as signed permutations. The correct data structure to study permutations in this context is the common interval tree. We refine these trees according to a parameter, and the resulting sub-families turn out to be simple varieties of trees. Thus, they are particularly amenable to analytic enumerative techniques, and Boltzmann generation. This refinement also has implications in algorithm analysis for various ancestral genome reconstruction algorithms. Finally, we compare the trees that we generate with those that arise with the direct comparison of a selection of mammalian genomes.
Work in collaboration with Mathilde Bouvel, Cédric Chauve, Rosemary McCloskey, Cyril Nicaud and Carine Pivoteau.
 Plus d'infos  


2012-11-09Bouquets de cercles et langages de courbes
10:45-11:45
076
Nous décrirons ici l'ensemble des fonctions de complexité des langages shifts qui proviennent du codage d'ensembles de courbes, appelés laminations en théorie des surfaces. Ces langages sont obtenus en déformant continuement les courbes sur des chemins de graphes étiquetés, orientés et plongés (proches de la notion de carte). Cette étude se basera sur l'ensemble de ces graphes qui n'ont qu'un seul sommet, i.e. les bouquets de cercles, et qui s'avèrent être des formes normales dans ce contexte. Nous montrerons également comment construire des langages pour chacune des complexités possibles, dont certaines des laminations finies correspondantes ont des représentations graphiques spiralées, vaguement minoennes irlando-crétoises.
 Plus d'infos  


2012-10-19Une extension stochastique du modèle du tas de sable sur un graphe
10:45-11:45
076
Dans le modèle du tas de sable, lorsqu'un sommet devient instable, c'est-à-dire que le nombre de grains en ce sommet dépasse son degré, celui-ci s'éboule en envoyant un grain vers chacun de ses voisins.
Dans notre modèle, un sommet instable envoie un grain vers chaque voisin avec probabilité p>0 (indépendamment pour chaque voisin).
On donnera une caractérisation des états récurrents de ce nouveau modèle, en termes d'orientations du graphe.
De plus, on introduira un polynôme comptant ces états récurrents selon leur nombre (total) de grains de sable, et on verra que celui-ci satisfait une relation de récurrence qui ressemble à celle du polynôme de Tutte.
 Plus d'infos  


2012-10-12Décompositions de graphes en 1-facteurs
10:45-11:45
076
Un 1-facteur d'un graphe G est un sous-graphe couvrant dont tous les sommets ont degré 1, aussi nommé perfect matching. Une 1-factorisation de G est une partition de ses arêtes en 1-facteurs disjoints. Un groupe d'automorphisme d'une 1-factorisation de G est un groupe de permutations des sommets de G qui envoie 1-facteurs sur 1-facteurs.
Dans cet exposé, nous discuterons le problème suivant : étant donné un graphe G, existe-t-il une 1-factorisation de G qui soit préservée par un groupe dont l'action est strictement transitive sur les sommets du graphe ? Ce problème a été traité pour des graphes complets et des groupes cycliques/abéliens/dihédriques, et, plus récemment, étendu aux graphes complets multipartis.
Nous exposerons nos résultats dans ce domaine, obtenus en collaboration avec G. Mazzuoccolo (Modène, Italie).
 Plus d'infos  


2012-10-05Some permutation classes enumerated by the central binomial coefficients
10:45-11:45
076
A permutation class is a downset in the subpermutation ordering. Permutation classes arise naturally in a variety of fields, such as the study of Shubert varieties, Chebyshev polynomials, and ordering algoritms. A permutation class C may be defined the set of minimal elements not belonging to it, its basis B. In his Ph.D. thesis, Olivier Guibert introduced eleven different permutation classes, whose basis contains four permutations of length four, each one enumerated by the central binomial coefficients. It is well known that the binomial coefficients enumerate also the set of Dyck prefixes of a given length.
In the present talk, we define a bijection between the permutation class of basis B={3241,3214,4213,4231} and the set of Dyck prefixes. This bijection allows us to relate particular features of a Dyck prefix with the occurrences of some statistics in the corresponding permutation (ascents, left-to-right maxima, length of the greatest decreasing sequence, etc). Moreover, we try to find similar bijections for the other ten classes enumerated by the central binomial coefficients, in order to find generating function for the distribution of some permutation statistics over these classes.
 Plus d'infos  


2012-09-28Sur le calcul du rang dans les graphes et en particulier les cliques (2/2)
10:45-11:45
076
En 2007, Baker et Norine ont proposé un théorème de Riemann-Roch pour les graphes. Dans ce théorème, le rang est un paramètre entier se définissant, à l'aide d'une optimisation parmi des compositions, sur tous les étiquetages des sommets par des entiers relatifs. En 2010 et 2011, Robert Cori avait présenté ici une preuve de ce résultat contenant également un algorithme de calcul du rang. Nous la rappellerons dans le cadre du modèle du tas de sable et présenterons comme nouveauté une spécialisation de l'algorithme au cas des cliques. L'analyse des exécutions intéressantes de cette spécialisation gloutonne donne l'occasion de patauger dans la si rare combinatoire des nombres de Catalan, avec pour changer des bistatistiques possédant des distributions avec des symétries.
 Plus d'infos  


2012-09-21Sur le calcul du rang dans les graphes et en particulier les cliques (1/2)
10:45-11:45
076
En 2007, Baker et Norine ont proposé un théorème de Riemann-Roch pour les graphes. Dans ce théorème, le rang est un paramètre entier se définissant, à l'aide d'une optimisation parmi des compositions, sur tous les étiquetages des sommets par des entiers relatifs. En 2010 et 2011, Robert Cori avait présenté ici une preuve de ce résultat contenant également un algorithme de calcul du rang. Nous la rappellerons dans le cadre du modèle du tas de sable et présenterons comme nouveauté une spécialisation de l'algorithme au cas des cliques. L'analyse des exécutions intéressantes de cette spécialisation gloutonne donne l'occasion de patauger dans la si rare combinatoire des nombres de Catalan, avec pour changer des bistatistiques possédant des distributions avec des symétries.
 Plus d'infos  


2012-09-07New perspectives on the enumeration of permutation classes
10:45-11:45
076
A permutation class is a collection of permutations closed downwards in a natural ordering. Early research in this area tended to concentrate on the enumeration of specific classes. I will describe a sequence of ideas which lead to the most general known results about the enumerative properties (specifically, the rationality or algebraicity of generating functions) for a collection of such classes. One particular consequence is that all "small" classes have rational generating functions. I will also illustrate how these ideas can be a guide for the actual enumeration of some specific classes.
 Plus d'infos  


2012-06-22Spanning trees, lattice Green functions and Mahler measures
10:45-11:45
076
On regular lattices the number of spanning trees grows exponentially, characterised by a constant known as the spanning tree constant. This constant is known for two dimensional lattices, but not for three dimensional lattices (with one exception). By recasting the definition in terms of the logarithmic Mahler measure of a Laurent polynomial, we can make use of recently proved results for Mahler measures to find the spanning tree constant for the four regular three-dimensional lattices. Further, by generalizing the spanning tree constant to what we call a spanning tree generating function (STGF), we relate this to the lattice Green function (LGF), and comparing results between the LGF and the STGF gives possibly new hypergeometric function identities.
Joint work with Mathew Rogers (Illinois, USA).
 Plus d'infos  


2012-06-15Un cas d'énumération de permutations triées par trois piles et deux symétries
10:45-11:45
076
On considère un cas particulier de permutations triées par trois piles et deux symétries (complément puis complément/miroir). Leur énumération est obtenue grâce à une bijection avec certains chemins de Motzkin (dont les pas montants et horizontaux sont bicoloriés).
Travail en commun avec Mathilde Bouvel.
 Plus d'infos  


2012-06-08Énumération de permutations triées par deux piles et une symétrie
10:45-11:45
salle 3 du bâtiment A29
On étudie les permutations triées par des opérateurs de la forme S.α.S, où S est l'opérateur usuel de tri par une pile et α est une symétrie du carré. Ces permutations sont caractérisées par des motifs exclus (de type généralisé), et des conjectures sur leur énumération ont été proposées par A. Claesson, M. Dukes et E. Steingrimsson. Ces conjectures portent sur une énumération raffinée selon la distribution de statistiques classiques sur les permutations. Nous démontrons ces conjectures, en ajoutant quelques statistiques dans l'une d'elles. Les preuves sont principalement à base d'arbres de génération, et utilisent aussi une bijection récente de S. Giraudo entre les permutations de Baxter et les permutations de Baxter tordues.
Il s'agit d'un travail en collaboration avec Olivier Guibert.
 Plus d'infos  


2012-06-01Étude d'une suppression d'une case dans les tableaux boisés et dans les tableaux de Dyck
10:45-11:45
076
Dans cet exposé, nous allons étudier la suppression d'une case dans les tableaux boisés ainsi que dans les tableaux de Dyck. L'objectif de ce travail est de mettre à jour des opérations qui trient les permutations en retirant au plus un seul motif 2-31.
 Plus d'infos  


2012-05-04Fonctions quasisymétriques sur les diagrammes de Young
10:45-11:45
076
La théorie des représentations des groupes symétriques a été développée par Frobenius en 1900. Comme pour tout groupe fini, tout se ramène à regarder une série de nombres χμλ indexés par deux partitions λ et μ : les caractères irréductibles. Ce n'est que dans les années 1990 que Kerov et Olshanski ont l'idée de regarder, avec une bonne normalisation, ces nombres comme des fonctions de λ.
La première partie de l'exposé consiste à présenter l'approche de Kerov et Olshanski. Dans cette approche, les caractères sont vus comme des fonctions "symétriques" de λ. Dans une seconde partie, nous expliquerons qu'il est plus naturel de les voir comme des fonctions quasisymétriques, une extension des fonctions symétriques beaucoup étudiée ces dernières années.
Il n'est pas nécessaire (c'est d'ailleurs inutile) de connaître la théorie "classique" des représentations du groupe symétrique pour suivre l'exposé.
 Plus d'infos  


2012-04-20k-formes, nombres de Genocchi et tableaux boisés
09:30-10:30
076
Les k-formes sont des partitions qui ont été introduites récemment par Lam, Lapointe, Morse et Shimozono en lien avec la théorie des fonctions symétriques.
Dans cet exposé, issu d'un travail en collaboration avec Florent Hivert, on montre que la série génératrice des k-formes est une fraction rationnelle.
La démonstration de ce résultat fait intervenir une certaine classe de k-formes, dites irréductibles, dont on conjecture qu'elles sont comptées par les nombres de Genocchi.
On présente les pistes explorées jusqu'ici pour tenter de prouver cette conjecture.
On conclut sur les liens entre les k-formes irréductibles et des objets étudiés par Adrien Boussicault et Jean-Christophe Aval : les tableaux de Dyck et les tableaux boisés.
 Plus d'infos  


2012-04-20Une méthode générique d'énumération de différentes classes de polycubes dirigés
10:45-11:45
076
Après avoir posé les définitions et propriétés permettant une extension des propriétés classiques des polyominos aux polycubes, nous exposons une méthode générique d’énumération de certains polycubes dirigés tri-dimensionnels.
Celle-ci est basée sur la méthode de décomposition des polyominos colonne par colonne et son interprétation en termes d'équations fonctionnelles due à Bousquet-Mélou.
Nous la généralisons ensuite au cas non dirigé, puis en dimension quelconque.
Nous appliquons chacune de ces variantes à des sous-classes de polycubes et exprimons des fonctions les dénombrant selon le volume et la largeur ainsi que des propriétés les caractérisant.
 Plus d'infos  


2012-04-13Distributions de cycles et distances entre génomes
10:45-11:45
076
Un grand nombre de mesures ont été proposées dans le but de comparer les génomes au niveau des gènes, et sont généralement basées sur des distances d'éditions impliquant des opérations inspirées par des mutations constatées dans l'évolution. Le "breakpoint graph" et ses variantes sont omniprésents dans l'étude de ces distances, et consistent en des représentations graphiques des génomes à comparer permettant l'obtention d'un grand nombre de résultats (bornes, calcul exact en temps polynomial ou résultats de complexité). Je présenterai ici le calcul de la distribution des cycles de ce graphe dans le cadre des permutations (signées et non signées), comment cette distribution permet d'estimer celles d'un certain nombre de distances, ainsi qu'une méthode automatique permettant d'obtenir des minorations sur ces distances dans le cas non signé.
[Ce travail a été réalisé avec Simona Grusea]
 Plus d'infos  


2012-04-06Combinatorics of minor-closed classes of graphs
10:45-11:45
076
In the past few years there has been a growing interest in finding properties of minor-closed classes of graphs. Typical examples of such properties are the number of graphs on n vertices, the probability that a graph on n vertices taken uniformly at random is connected etc. One of the first classes to be analyzed was the class of planar graphs and in fact many results known in this context extend to minor-closed classes, where the forbidden minors are 2-connected. In this talk, I am going to survey some well known results and present some examples indicating what might happen if we drop the condition that the excluded minors are 2-connected using tools from analytic combinatoric as well as methods from graph theory.
 Plus d'infos  


2012-03-23Intervalles de m-Tamari étiquetés
10:45-11:45
salle 3 bâtiment A29
Lors de sa venue au Labri à l'automne 2010, François Bergeron a présenté -- entre autres -- deux conjectures sur l'énumération des intervalles de certains treillis, dits de m-Tamari. Une conjecture pour des intervalles non-étiquetés, avec des nombres qui ressemblent à des nombres de cartes et ont une série génératrice algébrique. Une conjecture pour des intervalles étiquetés, avec des nombres qui ressemblent plutôt à des nombres d'arbres de Cayley, voire de cartes de Cayley, si ce n'est que la notion reste à inventer.
La première formule a été prouvée avec Éric Fusy et Louis-François Préville-Ratelle, et présentée au GT l'an dernier. La seconde a été prouvée, et très largement raffinée, avec ce même Louis-François et Guillaume Chapuy. La preuve manipule des séries génératrices, et les bijections restent à inventer.
Ces questions sont -- conjecturalement -- reliées aux polynômes coinvariants diagonaux en trois jeux de variables.
 Plus d'infos  


2012-03-16Modèle du marcheur pour les réseaux d'interactions
10:45-11:45
076
Des observations empiriques de la fin des années 1990 ont montré que la plupart des réseaux d'interactions (Internet, le web, les réseaux de collaboration) partagent des propriétés structurelles non triviales que ne possèdent pas les graphes aléatoires engendrés par le modèle classique d'Erdös-Rényi. Le modèle du marcheur tente de modéliser plus fidèlement ces réseaux. Je présenterai dans cet exposé certaines des propriétés des graphes aléatoires qu'il engendre : nombre d'arête, ordre de la plus grande composante connexe, présence de hubs.
 Plus d'infos  


2012-02-24Ordonnancement, Combinatoire : un problème d'identité remarquable.
10:45-11:45
076
« J'ai plein de choses à faire, mais par où commencer ?» Qui n'a jamais été confronté à cette angoissante question ? Après une introduction tout en douceur à l'ordonnancement, nous verrons que des préoccupations de ce genre permettent de définir des problèmes algorithmiques intéressants. Plus surprenant, l’un de ces problèmes fait apparaître des polynômes multivariés présentant une symétrie étonnante...
Bien que cet exposé présente plus de problèmes ouverts que de résultats, nous conclurons par quelques éléments de réponse à la question initiale : « par où commencer ?».
(Travail réalisé en collaboration avec Olivier Beaumont, Lionel Eyraud-Dubois et Loris Marchal)
 Plus d'infos  


2012-02-17Arithmetic matroids and Tutte polynomial
10:45-11:45
076
I will discuss the notion of arithmetic matroid, whose main example is given by a finite list of elements in a finitely generated abelian group. Guided by the geometry of toric arrangements, I will present a combinatorial intepretation of the associated arithmetic Tutte polynomial, which generalizes Crapo's formula for the classical Tutte polynomial.
 Plus d'infos  


2012-02-10Arbres plans pondérés et une classe de polynômes extrémaux à coefficients rationnels
10:45-11:45
076
Les objets que nous étudierons dans cet exposé seront les hypercartes planes dont toutes les faces, à part la face extérieure, sont de degré 1. Les arbres pondérés sont juste des outils pratiques pour manier plus facilement les hypercartes en question. Deux questions seront explorées : pour un assortiment de degrés donné des sommets noirs et blancs, quand est-ce qu'une hypercarte correspondante existe ? Quand est-ce qu'elle est unique ? La motivation provient du problème suivant : soient deux polynômes P et Q à coefficients complexes, premiers entre eux, du même degré, et avec les multiplicités fixées de leurs racines. Alors, quelle est la borne inférieure pour le degré de la différence P - Q ? Cette borne est-elle toujours atteinte ? Peut-on l'atteindre par des polynômes à coefficients rationnels ? Toutes ces questions prennent leur origine dans la théorie des nombres.
Travail en commun avec Fedor Pakovich.
 Plus d'infos  


2012-01-27Graphical description of extremal polynomials
10:45-11:45
076
Problems of conditional minimization of the uniform norm of polynomials or rational functions arise in different branches of science and technology. The solutions for those problems are very specific functions as they satisfy the so called equiripple property. This means that the vast majority of critical values (but not all of them!) lie in the set of (say) just two elements. An algebro-geometric Chebyshev construction describes such polynomials. As well they admit a representation in terms of certain weighted graphs.
 Plus d'infos  


2012-01-20Animaux dirigés, systèmes quadratiques et systèmes de réécritures
10:45-11:45
076
Un animal dirigé A sur le réseau carré est une partie de N2 contenant l'origine 0, et telle que chaque point de A peut être atteint depuis 0 en restant à l'intérieur de A, uniquement par des pas (0,1) ou (1,0). Le cardinal de A s'appelle l'aire de A, et l'ensemble des sommets de N2 que l'on peut ajouter à A sans lui faire perdre sa qualité d'animal dirigé (AD), s'appelle le périmètre de A. On s'intéresse à la question du calcul de la série génératrice G(x, y) des AD sur réseau carré selon l'aire et le périmètre. Il s'agit d'une question centrale dans l'étude des AD, très directement liée au problème de la percolation dirigée, pour lequel le seuil critique, qui est sup { p : G( p, 1-p) = 1 }, est inconnu (alors qu'il existe de nombreuses méthodes pour calculer G(x,1)). Dans cet exposé, nous montrons l'équivalence entre le calcul de G et le calcul d'une solution à un système quadratique dont les inconnues sont des matrices (équations relativement proches de celles apparaissant pour le TASEP). Incapable de résoudre ce problème, nous montrons que des matrices infinies obtenues comme point fixe d'un système de type "système de réécriture", sont "solutions naturelles" de ce problème quadratique. Trouver un vecteur propre pour l'une d'elle devrait permettre de calculer G...
 Plus d'infos  


2012-01-13Un modèle simple d'arbres décorés pour les cartes unicellulaires
10:45-11:45
076
Dans cet exposé, nous nous intéressons aux cartes unicellulaires, c'est-à-dire aux graphes dessinés sur des surfaces de telle sorte que le complémentaire soit homéomorphe à un disque.
Nous montrons que l'on peut mettre ces objets en bijection avec une famille d'arbres décorés. Malheureusement, l'existence de cette bijection est obtenue récursivement et on n'obtient donc pas de construction explicite. Mais on peut faire en sorte que cette bijection préserve beaucoup de structure : le graphe sous-jacent à la carte (avec ses éventuelles boucles et arêtes multiples !) peut être décrit simplement à partir de l'arbre décoré. Cette propriété permet de démontrer combinatoirement de nombreuses formules fines d'énumération de cartes unicellulaires.
Travail en commun avec Guillaume Chapuy et Éric Fusy.
 Plus d'infos  


2012-01-06Complexité de la coloration probabiliste d'un anneau : une application de la transformée de Mellin
10:45-11:45
076
Dans cet exposé, on s'intéresse à la 3-coloration distribuée d'un anneau anonyme. Nous étudions la complexité en temps et la bit-complexité de ce problème en présentant un algorithme probabiliste permettant de le résoudre et en montrant une borne inférieure générale.
L'analyse de l'algorithme utilise la transformée de Mellin, ce qui permet de donner la valeur exacte du temps moyen et non seulement une borne supérieure. Nous en déduisons que l'algorithme présenté est optimal.
Travail en collaboration avec Y. Métivier, M. Robson et N. Saheb.
 Plus d'infos  


2011-12-09Une méthode algorithmique pour le calcul des séries génératrices des classes de permutations, et pour la génération aléatoire dans ces classes
10:45-11:45
076
L'objectif de l'exposé est de présenter un cheminement algorithmique qui, partant d'une classe de permutations C donnée par sa base (supposée finie), permet d'obtenir automatiquement des résultats énumératifs sur la classe C, et un générateur aléatoire de permutations de C.
Je commencerai par définir les classes de permutations, et expliquerai comment le point de vue de la décomposition par substitution peut être efficacement utilisé pour décrire les permutations de toute classe donnée dans le formalisme des structures combinatoires. Une fois dans ce cadre classique, il devient aisé d'obtenir des résultats d'énumération et des générateurs aléatoires. La difficulté principale est de passer « algorithmiquement » de la description d'une classe par sa base à un système d'équations la décrivant comme une structure combinatoire. Je montrerai les principales étapes de ce cheminement, et esquisserai une explication plus détaillée de certaines d'entre elles.
Il s'agit d'un travail en commun avec Frédérique Bassino, Adeline Pierrot, Carine Pivoteau et Dominique Rossin.
 Plus d'infos  


2011-12-02Permutations et partitions d'ensemble de genre 1
10:45-11:45
178
La notion d'hypercarte a permis de définir un genre pour les couples de permutations. On prend ici pour définition du genre d'une permutation α, celui de l'hypercarte (ζn,α) où ζn est la permutation circulaire (1,2,...,n). On sait depuis quelques années qu'avec cette définition les permutations de Sn de genre 0 correspondent aux partitions sans croisement de 1,2,...,n, introduites par G. Kreweras et étudiées extensivement par P. Edelman, R. Simion, R. Stanley et d'autres.
On s'intéresse ici aux permutations de genre 1, celles d'entre elles dont tous les cycles sont de la forme (a1, a2,...,ap), avec a1 < a2 < ... < ap, correspondent à des partitions ; mais il y en d'autres comme par exemple (1,4,3,2) ou (1,5,3)(2,6,4). On proposera des formules d'énumération pour ces permutations et ces partitions. On utilisera des bijections mais aussi des calculs sur les séries génératrices.
Ceci est un travail commun avec Gábor Hetyei.
 Plus d'infos  


2011-11-25Promising q,t-Narayana polynomials
10:45-11:45
075
Some q,t-Catalan polynomials are relatively famous polynomials symmetric in q and t that may be defined as an enumeration of Dyck paths of the same size according to two statistics.
These polynomials appear in various, sometimes more algebraic, contexts.
In a joint work with Mark Dukes, we were lead to the definition of a promising familly of q,t-Narayana polynomials that may defined as an enumeration of parallelogram polyonominoes with the same bounding box according to two statistics.
It remains to place these polynomials in the litterature on the subject, but we can present a relatively natural path via the sandpile model between those two families of polynomials apparently both symmetric in q and t.
 Plus d'infos  


2011-11-18Une déformation à un paramètre de l'algèbre de Farahat-Higman
10:45-11:45
076
On montre, en introduisant une base appropriée, qu'une famille à un paramètre d'algèbres de Hopf introduite par Foissy interpole entre l'algèbre de Faà di Bruno et l'algèbre de Farahat-Higman. Les constantes de structure dans cette base sont des déformations des constantes de structure de l'algèbre de Farahat-Higman dans la base des projections des classes de conjugaison. On obtient pour ces constantes de structure déformées un analogue des formules de Macdonald.
 Plus d'infos  


2011-11-04Sur le profil des arbres plongés
10:45-11:45
076
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.
 Plus d'infos  


2011-11-03Representation theory, symmetric functions and bipartite maps
16:15-17:15
076
We define what is a representation of a finite group and we make an introduction to the theory of such objects. We define also an algebra of symmetric functions and some combinatorial objects called bipartite maps. We show some results which establish a connection between three of them and we state some conjectures which try to generelize this phenomena.
 Plus d'infos  


2011-10-14Structure des cartes non orientables à une face
10:45-11:45
076
Cet exposé a deux objectifs : le premier est de vous convier dans le monde mystérieux des cartes non orientables ; le second, plus implicite, est de présenter l'orateur, nouveau doctorant, au reste de l'équipe.
Nous commencerons par introduire en douceur la notion de carte topologique (sur des surfaces générales) en tant que dessin d'un graphe sur une surface, et montrerons comment aboutir à une représentation plus simple d'un point de vue combinatoire.
Après cela, nous étudierons plus particulièrement ce qui était le sujet de mon mémoire de M2 : une approche bijective pour énumérer les cartes non orientables à une face.
Nous nous intéresserons principalement aux bijections (qui semblent assez visuelles) trouvées dans le cas où le genre vaut 1/2 (c'est-à-dire sur le plan projectif).
Puis selon le temps restant, nous exposerons ce qui a été tenté pour les genres supérieurs, notamment en introduisant la notion d'entrelacement.
 Plus d'infos  


2011-10-07Polyominos inscrits
10:45-11:45
076
Dans cet exposé, je discuterai de l’énumération de polyominos selon l’aire. L’approche proposée consiste à fixer le format d’un rectangle et à compter les polyominos inscrits dans ce rectangle. Un polyomino est inscrit dans un rectangle lorsqu’il touche chacun des quatre côtés du rectangle. Nous commencerons par construire la série génératrice des polyominos d’aire minimale en les caractérisant géométriquement puis nous considérons différentes extensions de cette construction.
 Plus d'infos  


2011-09-30Empilements de mots pour l'énumération des interactions supérieures dans les chemins de Dyck
10:45-11:45
076
Objets classiques de la combinatoire énumérative, la seule chose que l'on ne compte peut-être pas sur les chemins de Dyck ce sont les méthodes pour les compter. Une interaction supérieure dans un chemin de Dyck est formée de deux sommets à la même hauteur définissant un facteur contenant une unique vallée. L'énumération des chemins de Dyck selon leurs nombres de pas et d'interactions supérieures contredit (temporairement) une décomposition récursive de ses chemins. Dans un précédent exposé, j'avais présenté deux méthodes permettant d'obtenir la série génératrice associée qui est un ratio de deux séries hypergéométriques basiques dont les raisons contiennent un coefficient algébrique. Après quelques rappels, cet exposé présentera une troisième méthode, inspirée de la théorie des empilements de Viennot, dont les étapes permettront de revisiter quelques-unes des méthodes d'énumération des chemins de Dyck.
 Plus d'infos  


2011-09-16Combinatoire des polynômes zonaux
10:45-11:45
314 du bâtiment A22
Les fonctions de Schur (introduites par Jacobi) sont des fonctions symétriques avec des propriétés surprenantes, tant du point de vue de la combinatoire que de la théorie des représentations. Dans cet exposé, nous considèrerons une autre famille de fonctions symétriques, les polynômes zonaux qui peuvent être considérés comme des analogues des fonctions de Schur.
Le résultat principal est une formule combinatoire relativement simple pour les polynômes zonaux. Les objets combinatoires mis en jeu sont des triplets d'appariements, que l'on peut interpréter comme des graphes dessinés sur une surface (orientable ou non).
 Plus d'infos  


2011-07-01Les jeux du type Bernoulli et un nouveau type de formules en combinatoire énumérative
10:45-11:45
076
Nous introduisons un jeu de troncature à deux joueurs sur les paires de mots de même longueur, tel que le nombre des positions de longueur n où le deuxième joueur a une stratégie gagnante est (n+1)! fois la valeur absolue du nième nombre de Bernoulli de deuxième espèce. Une généralisation de ce jeu nous offre un modèle combinatoire pour les nombres de Bernoulli dégénérés introduits par Carlitz. Une application probabiliste réalise l'intégrale de n'importe quelle fonction sur un intervalle fini comme le gain attendu dans un jeu aléatoire infini.
Ce qui rend facile de compter les positions gagnantes dans nos exemples est le fait qu'à chaque tour la stratégie ne permet qu'un seul bon coup. Nous décrivons une classe de jeux avec cette propriété qui nous offre une nouvelle interprétation combinatoire de plusieurs formules. Dans une sous-classe des jeux de troncature sur les mots on peut décomposer les positions gagnantes en positions gagnantes élémentaires, d'une manière unique. Ainsi nous obtenons des nouvelles formules pour les nombres et polynômes de Bernoulli de deuxième espèce et nous retrouvons une variante de la décomposition des permutations indécomposables qui a été utilisée par King pour construire un code Gray pour les permutations indécomposables.
 Plus d'infos  


2011-06-24Le nombre d'intervalles dans les treillis de m-Tamari
10:45-11:45
076
On considère l'ensemble T_n^m des chemins du plan issus de (0,0), formés de pas nord et est, finissant en (mn,n), et restant au dessus de la droite d'équation x=my. François Bergeron a décrit sur ces chemins un ordre, qui généralise l'ordre de Tamari (obtenu pour m=1). On verra que cet ordre donne une structure de treillis, pour tout m.
François a conjecturé une belle formule --- qui ressemble à un nombre de cartes, soit un coefficient binomial divisé par deux termes linéaires en n --- pour le nombre d'intervalles dans le treillis T_n^m. C'est cette formule qu'on démontre. Elle était connue depuis quelques années pour m=1, d'abord prouvée récursivement par Chapoton, puis par Bernardi et Bonichon via une bijection avec des triangulations. Pour m général, une approche bijective reste à inventer, et nous procédons récursivement.
Selon François B., ces mêmes nombres donnent la dimension d'un certain espace de polynômes --- mais c'est là une tout autre histoire, à coup sûr bien plus difficile.

Travail en commun avec Éric Fusy (LIX) et Louis-François Préville Ratelle (LACIM).
 Plus d'infos  


2011-06-10Shifts, échanges d'intervalles et arbres
10:45-11:45
salle 76
On présentera ici des relations entre les shifts (i.e. les langages fermés invariants par décalage), et les échanges d'intervalles, eux-mêmes liés à des représentations arborescentes de la combinatoire des mots de ces mêmes shifts.
 Plus d'infos  


2011-05-27Arbres non ambigus servis avec leurs myriades d'arbres planaires
10:45-11:45
salle 76
Les arbres non ambigus sont des dessins particuliers d'arbres binaires sur le quadrillage. Ce sont des objets qui apparaissent naturellement dans les tableaux boisés.
Dans cet exposé, nous utilisons les bijections classiques entre arbres binaires et arbres planaires pour
- engendrer les arbres non ambigus d'un arbre binaire donné;
- compter les arbres non ambigus d'un arbre binaire donné;
- réaliser une bijecion simple entre polyominos parallélogrammes et arbre binaires.
Enfin, nous donnons une bijection entre les tableaux boisés et les arbres non ambigus escaliers.
 Plus d'infos  


2011-05-20introduction aux tableaux escaliers
10:45-11:45
salle 76
On présentera les tableaux escaliers (généralisation des tableaux de
permutation, et en bijection avec les permutations doublement signées), et
quelques pistes utilisées pour les comprendre, notamment la construction
de ces tableaux par récurrence, qui a donné lieu à une étude des lois des
paramètres des tableaux, ou la mise en bijection de sous-ensembles de ces
tableaux avec des permutations.
 Plus d'infos  


2011-05-13Tableaux boisés servis avec leur algorithme d'insertion
10:45-11:45
salle 76
Dans cet exposé nous présentons les tableaux boisés.
Les tableaux boisés sont des objets en bijection simple avec les tableaux de permutation et les tableaux alternatifs.
Nous introduisons ensuite un algorithme d'insertion élémentaire sur nos tableaux qui donne une preuve simple que les tableaux de taille n sont comptés par n!.
Nous expliquons comment, à partir de cet algorithme, il est possible de construire un patron de bijections entre les tableaux boisés et les permutations.
Nous utilisons ensuite ce patron pour faire apparaître
- des bijections directes entre tableaux boisés et permutations;
- de nombreuses statistiques;
- des formules d'énumération.
Enfin, nous montrons comment il est possible de modifier l'algorithme d'insertion pour étudier la combinatoire des :
- tableaux boisés symétriques ( type B )
- chemins de Dycks valués
- partitions gauches
 Plus d'infos  


2011-05-06Inclusion/Exclusion cyclique
10:45-11:45
salle 76
Certaines formules pour les caractères du groupe symétrique s'expriment à l'aide de briques de base simples : des séries génératrices de fonctions sur des ensembles ordonnés. Dans cet exposé, nous regarderons les relations linéaires entre ces séries génératrices. Celles-ci peuvent être décrites à l'aide d'une opération combinatoire locale simple que nous appelons inclusion/exclusion cyclique.
 Plus d'infos  


2011-04-29Algorithmes barycentriques pour le dessin de graphes dans le plan
10:45-11:45
salle 76
Nous proposons un survol de deux algorithmes de dessin
bien connus pour dessiner un graphe dans le plan: celui de Tutte
et celui de Schnyder. Tous deux utilisent un principe
barycentrique de placement des sommets, cependant de manière
tres différente. Si le temps le permet nous montrerons aussi
d'autres algorithmes plus récents du type de celui de Schnyder.
 Plus d'infos  


2011-04-15Hypergraphes sur des surfaces: dualité et largeur arborescente
10:45-11:45
salle 76
Le dual d'un graphe planaire G est obtenu en plaçant un sommet par face de G et en ajoutant pour toute arête e de G une arête qui relie les centres des faces incidente à e. Cette notion classique s'étend sans problème aux plongements cellulaires sur des surfaces quelconques. Elle se généralise aussi aux hyper cartes qui sont des plongements d'hypergraphes sur des surfaces orientables.

Par ailleurs, les travaux de Bruno Courcelle ont montré que la largeur arborescente peut servir de mesure de "complexité" des graphes. Comme il semblerait curieux que la "complexité" d'un plongement et cette de son dual soit très différente, on s'attend à ce que la largeur arborescente d'un plongement et celle de son dual soit proche.

Dans cet exposé, montrerai comment définir une dualité pour les hypergraphes plongés dans des surfaces quelconques et comment j'ai utilisé cette extension pour obtenir un lien entre la largeur arborescente d'un plongement et celle de son dual.
 Plus d'infos  


2011-04-08Méthodes combinatoires de reconstruction de réseaux phylogénétiques
10:45-11:45
salle 76
Les réseaux phylogénétiques généralisent le modèle de l'arbre pour
décrire l'évolution, en permettant à des arêtes entre les branches de
l'arbre d'exprimer des transferts de matériel génétique entre espèces
coexistantes. De nombreuses approches combinatoires ont été conçues
pour reconstruire ces réseaux à partir de données extraites de
plusieurs arbres de gènes contradictoires. Elles se divisent en
plusieurs catégories selon le type de données en entrées (triplets,
quadruplets, clades ou bipartitions) et les restrictions de structure
sur les réseaux reconstruits.
Je présenterai deux approches combinatoires de reconstruction de
réseaux phylogénétiques, à partir de clades ou de quadruplets, ainsi
que des propriétés de structure des réseaux qu'elles reconstruisent.
Je montrerai également des limites de de ces méthodes, et la façon de
les prendre en compte, en particulier par des pré-traitements
appropriés des données.
 Plus d'infos  


2011-04-01Battages de cartes, partitions aléatoires et théorème central limite pour les caractères du groupe symétrique infini.
10:45-11:45
salle 76
À tout caractère irréductible du groupe symétrique infini, on associe des mesures de probabilité P_n et Q_n sur l'ensemble Y_n des partitions de l'entier n et sur l'ensemble S_n des permutations de taille n. La mesure Q_n peut être décrite par un algorithme de battages de cartes ; la mesure P_n est l'image de Q_n par l'algorithme de Robinson-Schensted, et elle correspond également à la décomposition du caractère initial dans la base des caractères irréductibles de S_n. On s'intéressera aux propriétés asymptotiques des mesures P_n, et on présentera une loi des grands nombres due à Kerov et Vershik, ainsi qu'un théorème central limite. S'il reste du temps, on évoquera aussi le lien conjectural entre les mesures Q_n, les mouvements browniens conditionnés à rester dans une chambre de Weyl et les valeurs propres de matrices hermitiennes browniennes.
 Plus d'infos  


2011-03-25Sur le problème de moments pour les polynômes de Laurent
10:45-11:45
salle 76
L'exposé sera dédié à une étude approfondie du dessin
(de l'hypercarte) qui, sous forme de permutations, se présente comme
(sigma,alpha) où sigma = (2,5,7,6,10,9)(3,8,4) et alpha = (1,5)(2,8)(4,7).
 Plus d'infos  


2011-03-18Excursions discrètes de hauteur bornée
10:45-11:45
salle 76
Considérons les chemins de Dyck de hauteur bornée par k. La série comptant ces
chemins est de la forme F_{k-1}/F_k, où les F_k sont les polynômes de
Fibonacci. Nous verrons que ces polynômes se factorisent en deux termes, qui
suivent la même récurrence linéaire que les F_k. Nous donnerons une
explication combinatoire de ce fait.

Ces résultats persistent dans un cadre plus général, étudié par Banderier et
Flajolet (2001), puis par Bousquet-Mélou (2008), où les chemins peuvent suivre
des pas appartenant à un ensemble S fixé symétrique (par exemple -2,-1,+1,+2).
Nous donnerons encore une interprétation combinatoire des polynômes impliqués
et de leurs facteurs.
 Plus d'infos  


2011-03-04Reconnaissance et génération aléatoire de polyominos digitalement convexes
10:45-12:00
Un polyomino digitalement convexe est l'ensemble des cellules intérieures d'une region convexe du plan. S. Brlek, J.-O. Lachaud, X. Provençal et C. Reutenauer ont donné un algorithme linéaire pour la reconnaissance de ces polyominos, basé sur une caractérisation combinatoire de leur mots de contour. Je présenterai cette caractérisation et je montrerai comment on peut en déduire un générateur aléatoire uniforme de polyominos digitalement convexes, faisant intervenir des générateurs de Boltzmann.
 Plus d'infos  


2011-02-18Génération Boltzmannienne exacte avec oracles inexacts
10:45-11:45
076
Le modèle de Boltzmann est une technique séduisante pour la génération aléatoires d'objets combinatoires, mais il a potentiellement le défaut de reposer sur un "oracle" chargé d'évaluer diverses séries génératrices en un même point. Une question naturelle est celle de l'influence, sur la qualité du résultat, de la précision numérique de l'oracle. On apportera à cette question des réponses plus ou moins satisfaisantes et intrigantes.
 Plus d'infos  


2011-02-11Génération Boltzmannienne exacte avec oracles inexacts
07:00-07:00
salle 76
Le modèle de Boltzmann est une technique séduisante pour la génération aléatoires d'objets combinatoires, mais il a potentiellement le défaut de reposer sur un "oracle" chargé d'évaluer diverses séries génératrices en un même point. Une question naturelle est celle de l'influence, sur la qualité du résultat, de la précision numérique de l'oracle. On apportera à cette question des réponses plus ou moins satisfaisantes et intrigantes.
 Plus d'infos  


2011-02-04Triangulations de l'hypercube, nombres eulériens, et simulation exacte de variables aléatoires
10:45-11:45
076
On s'intéresse à la simulation exacte de la loi d'une somme de n variables aléatoires indépendantes, uniformes sur l'intervalle [0,1] (loi de Irvin-Hall). Plus précisément, peut-on obtenir une simulation exacte, sans opérations arithmétiques ?
La recherche d'une méthode "efficace" conduit, via les nombres eulériens et des résultats "bien connus depuis des siècles" sur le volume de "tranches" d'un hypercube, à un algorithme qui, en moyenne, utilise n log(n) + k bits aléatoires pour donner une précision de k bits sur la variable aléatoire simulée - ce qui bat asymptotiquement l'algorithme naïf à base d'additions en multiprécision.
 Plus d'infos  


2011-01-21Sur la génération aléatoire des chemins auto-évitants
10:45-11:45
076
Le point de départ de cet exposé est un algorithme proposé par D. Knuth en 1971 pour engendrer des chemins auto-évitants aléatoires traversant un carré de côté k du coin Sud-Ouest au coin Nord-Est. Aléatoires... mais pas uniformes. À partir des chemins aléatoires obtenus, on peut construire un estimateur du nombre de tels chemins. Knuth puis Diaconis se sont intéressés à la qualité de cet estimateur, plus précisément à sa variance, dont la détermination revient à compter (ouf !) ces chemins auto-évitants selon un certain poids.
On présentera quelques résultats autour de cette question, et bien sûr... d'autres questions.
 Plus d'infos  


2011-01-14Preuve du théorème Riemann-Roch pour les graphes
10:45-11:45
salle 4 du bâtiment A29
Suite de l'exposé du 17 décembre 2010 intitulé "Tas de sable sur un graphe et un théorème du style Riemann-Roch", après un rappel des notions nécessaires.
 Plus d'infos  


2011-01-07Approche algébrique et généralisation des formules d'équerre pour les arbres
10:45-11:45
076
Une extension linéaire d'un ensemble ordonné $P$ est un ordre total plus fin que $P$. Dans le cas où $P$ est une forêt, Knuth a donné une très jolie formule en terme d'équerres pour dénombrer ces extensions linéaires. Des $q$-analogues de cette formule (prenant en compte l'indice majeur) ont été établis par Stanley, puis par Björner et Wachs.
L'objectif de cet exposé est de donner des interprétations algébriques de ces formules, en trouvant une présentation d'une certaine algèbre. Cette approche nous amène à considérer une classe de posets plus larges, appelés arbres décorés, pour lesquels on obtient des formules du même type.
Travail en commun avec Victor Reiner (University of Minnesota).
 Plus d'infos  




Liste des événements répétitifs du groupe Combinatoire Énumérative et Algébrique




Retour
Retour à l'index