Résumé: This talk continues the previous presentation concerning
pattern statistics in rational models.
The main goal is to present a notion of symbol periodicity for irreducible
matrices of polynomials that extends the standard notion of periodicity
of non-negative matrices (used in Perron-Frobenius Theorem). This notion
plays a central role in the analysis of (local) limit distributions of
pattern statistics in primitive rational models.
Résumé: This talk is devoted to the study of limit
distributions of certain pattern statitics defined in so-called rational
stochastic models. The main goal is to present a local limit theorem
of Gaussian type for each statistics under suitable primitivity hypothesis
and discuss possible extensions to algebraic models.
Two main tools will be presented:
Résumé: Dans sa thèse, Olivier Guibert considère, entre autres, les mots composés de 3 lettres '1', '2', et '3', tels que tout préfixe possède plus de '1' que de '2' et plus des '2' que de '3'. Il établit un certain nombre de bijections entre des familles d'objets combinatoires variés et des mots de piles dont certains motifs sont exclus. Par ailleurs, il conjecture qu'en excluant certains motifs ( - 2 Y 2 - 3 3 ou - 1 Y 3 - 2 1), ces mots sont comptés de la même manière que les triangulations du plan. Dans le but de coder efficacement les triangulations, nous donnerons des bijections entre les triangulations et les mots de piles qui excluent les motifs - 2 Y 2 - 3 1 ou - 1 Y 3 - 2 1.
Résumé: This talk is devoted to the analysis of limit
distributions of pattern statistics in certain rational stochastic
models.
The main problem in pattern statistics consists of estimating the
frequency of pattern occurrences in a word of given length generated
at random.
The stochastic models we consider are called rational and are defined
by finite automata with positive weights. These models extend the
classical Markovian and Bernoullian models and are rather general
since they allow us to reduce the set of patterns to a simple symbol
of the alphabet. In the previous litterature, the rational models have
been studied mainly in the primitive case, i.e. when the automaton
defining the model consists of one aperiodic strongly connected
component, or in the bicomponent case.
Here we consider rational models having an arbitrary number of
connected components. We establish the limit distributions of the
pattern statistics (as the length of the random word grows) in the
most significant cases; such distributions are characterized by a
family of unimodal density functions defined by polynomials over
adjacent intervals.
Résumé: I will define the Ising model, and then present a method to construct non-isomorphic graphs with the same partition function.
Résumé: Je me propose de refaire l'exposé que j'ai fait à Lucelle au 54ème Séminaire Lotharingien de Combinatoire célébrant un certain anniversaire. Cet exposé était une "promenade dans le jardin des bijections" et le fil conducteur était certaines bijections de contractions et d'expansions de chemins de Dyck ou de Motzkin, ainsi que leur analogue dans le monde des dominos et des empilements de dominos.
Je commencerai par une partie historique sur les nombres de Catalan, vers la fin du 18ème siècle et les années 1830, avec Euler, Segner, Arbogast, Lamé, Liouville, Binet, Rodrigues et finalement... Catalan. Je rappellerai la bijection directe obtenue avec Gouyou-Beauchamps montrant que le nombre d'animaux dirigés à source compacte est 3n. L'introduction du modèle des empilements de dominos et leurs bijections de base a beaucoup simplifié les premières bijections relatives aux animaux dirigés. Le but est de "comprendre", c'est-à-dire "démonter", cette bijection originelle pour 3n.
Cette compréhension passe par la théorie des polynômes orthogonaux, des fractions continues de Jacobi et Stieljes, des formules de contractions "1+1" des fractions continues et leur explication en termes de chemins ou d'empilements de dominos. Le sujet passe alors par la combinatoire des nombres de Strahler. Je présenterai une nouvelle bijection, obtenue lors de mon séjour à l'Institut Mittag-Leffler lors d'une stimulante collaboration avec Don Knuth, et démontrant des formules sur les convergents de fractions continues relatives à des contractions non-standards de type "1+3". Le sujet est lié à l'algorithme quotient-différence en analyse numérique, d'anciens travaux (avec Myriam Desainte-Catherine) sur certains déterminants de Hankel de nombres de Catalan, et de récents développements sur d'autres déterminants de Hankel en combinatoire.
Résumé: Les polynômes B-quasisymétriques ont été récemment étudiés par Baumann-Hohlweg. On s'intéresse ici à l'idéal engendré par ces polynômes, et au quotient associé, dont on prouve qu'il est de dimension égale au nombre d'arbres ternaires.
Résumé: Le triangle de Catalan B(n,k)
1 1 1 1 2 2 1 3 5 5 1 4 9 14 14
est engendré par la récurrence B(n,k) = somme des B(n-1,l) pour l inférieur ou égal à k. On vérifie aisément que les sommes horizontales de ce triangle donnent les nombres de Catalan. Que se passe-t-il si l'on considère la même construction en dimension 3 ?
Résumé: We prove a product formula for the weighted enumeration of self-complementary plane partitions contained in a given box where adding one half of an orbit of cubes and removing the other half of the orbit changes the sign of the weight.
We use nonintersecting lattice path families to expres this enumeration as a Pfaffian which is difficult to evaluate directly, but can be expressed in terms of the known ordinary enumeration of self-complementary plane partitions.
Résumé: On donne de nouvelles énumérations, via le polynôme de Tutte, des suites de degrés d'un graphe orienté, prenant en compte les parties acycliques et totalement cycliques. Les classes d'orientations ayant même suite de degrés peuvent alors être interprétées comme configurations d'un cycle-cocycle firing game, qui étent le système dynamique edge firing game par dualité. Ce système présente des similitudes énumératives intrigantes avec le modèle du tas de sable.
Résumé: During the years a lot of different bijections and involutions between Young tableaux of different types had been found and investigates. Due to an almost magical property of the Young tableaux there are a lot of different relationships involving the involutions. I will present the results of a project to find and explain these relationships in a consistent manner.
Résumé: Nous appliquons la méthode ECO sur les chemins culminants pour trouver une série génératrice en fonction de la hauteur h et de la longueur n. Cette méthode permet d'obtenir une équation de récurrence selon la hauteur finale ainsi que la génération exhaustive de tels chemins.
Résumé: In 2001 Razumov and Stroganov conjectured a relation between the eigenvector of a Hamiltonian associated with the O(1) loop model and the number of fully packed loop configurations with a specified matching on the external edges. This spawned an interest in enumerating these configurations. I follow an idea of de Gier and make such an enumeration for a particular type of matchings on half-turn symmetric FPL configurations.
Résumé: Dans un premier temps, je rafraichirai les mémoires en résumant un exposé que j'avais fait dans le passé. Il s'agit de deux articles de physiciens (Ambjorn, Loll, Di Francesco, Guitter, Kristjansen) introduisant les triangulations Lorentziennes, objets combinatoires modélisant la gravitation quantique Lorentzienne en dimension 2. Avec certaines conditions sur les bords, deux modèles sont résolus de manière exacte. Les nombres de Catalan et les empilements de pièces y jouent un rôle crucial.
Le problème général revient à l'énumération des empilements connexes, introduits par Bousquet-Mélou et Rechnitzer dans leur article sur les animaux multidirigés. Je reviendrai également sur quelques formules et preuves combinatoires de cet article.
La gravitation quantique introduit un paramètre "courbure" sur ces triangulations. Je donnerai une solution du modèle général avec tous les paramètres, complétant un exposé précédent de Will James. La solution fait intervenir des empilements de segments et des polynômes orthogonaux.
Résumé: Je vous présenterai un exposé intitulé Chess tableaux and chess problems que Timothy Chow (travail de T. Chow, H. Eriksson et C.K. Fan, en préparation) a lui-même présenté au séminaire de Combinatoire du MIT.
Résumé: On présentera de façon unifiée des résultats (anciens) sur la hauteur et le profil des arbres binaires, et des résultats (nouveaux) sur la "vraie largeur" (ou empattement ?) et le profil vertical de ces mêmes arbres.
Ces résultats sont basés sur l'obtention de séries génératrices bizarrement algébriques, suivie de l'étude du comportement asymptotique de leurs coefficients.
Résumé: Nous nous sommes intéressés à la génération aléatoire des mots d'un langage apparaissant dans l'étude d'algorithmes utilisés en bioinformatique. Il s'agit de chemins dans le demi plan composés de pas (1,+a) et (1,-b), positifs, et terminant en une ordonnée maximale. Tentant diverses approches, nous avons prouvé que ces langages sont non algébriques, trouvé des relations entre ces langages et les mots de Dyck généralisés de hauteur bornée, et construit un algorithme de génération en O(n) après un précalcul en O(a^2*n^3). Nous manquons cependant de données combinatoires sur les mots de Dyck pour en déduire une forme close de série.
Résumé: On s'intéresse au problème de l'énumération des cartes planaires boisées (c'est-à-dire munies d'un arbre couvrant). Il existe une bijection (due a R.C. Mullin, 1965) entre les cartes planaires boisées et certains couples d'arbres enracinés. Cette bijection permet d'établir le résultat de comptage suivant:
Le nombre de cartes planaires boisées à n arêtes est
2/((n+2)(2n+1)) Binomial(2n+1,n-1)^2
Le comptage des cartes boisées est un cas particulier du comptage des cartes selon leur polynôme dichromatique (aussi appelé polynôme de Tutte).
Je commencerai par rappeler les notions de carte planaire et de polynôme dichromatique. J'expliquerai aussi la bijection mentionnée ci-dessus.
Je présenterai ensuite une démonstration analytique du résultat de comptage par une nouvelle méthode. Cette technique de résolution est inspirée d'un article de W.T. Tutte portant sur le comptage des triangulations coloriées. La présentation de cette autre méthode est motivée par l'espoir de faire émerger une "méthode des invariants de Tutte". Cette présentation se veut donc une introduction aux ingrédients d'une nouvelle méthode de résolution d'équations. Méthode qui pourrait (?) permettre le comptage des cartes planaires coloriées.
Résumé: The objects of study here are two-dimensional lattice walks, with a fixed set of step directions, restricted to the first quadrant. These walks are well studied, both in a general context of probabilistic models, and specifically as particular case studies for fixed direction sets, notably the so-called Kreweras' walks defined by the direction set {NE, W, S}.
The goal here is to examine two series associated to these walks: a simple length generating function, and a complete generating function which encodes a walk's endpoints, and to determine combinatorial criteria which decide when these series are algebraic, D-finite or none of the above. (with our attention drawn to the generating functions which appear to be non-D-finite) We shall present (what we expect to be... +/- some details) a complete classification of all nearest neighbour walks where the set of directions is of cardinality three, and discuss how this leads to a natural conjecture for the classification of nearest walks with any direction set.
(Work in progress with M. Bousquet-Mélou)
Résumé: Let Sn be the set of all permutations on {1,...,n}, and In := { π in Sn: π2 = Id}. Many permutation statistics stat: Sn --> N have the property that Σπ in Sn x1+stat(π) = An(x), where An(x) is the n-th Eulerian polynomial.
In this talk we look at some properties of these polynomials when this sum is restricted to the class of involutions, i.e. Σπ in In x1+stat(π).
Résumé:
This work introduces a labelled directed graph which encodes a network in which processes communicate by asynchronous message passing with a symmetric port numbering. The basic events (send, receive, transmission and internal) are encoded by local computations on arcs. From this directed graph, combinatorial characterizations of graphs and of families of graphs in which the naming problem and the election problem admit solutions are given. The main tool is covering. We establish a bridge between the characterizations obtained for two kinds of models: the model studied by Yamashita and Kameda and the models studied by Mazurkiewicz, Boldi and Vigna, Chalopin et al.