Journée-séminaire de combinatoire

Liste de diffusion                  Exposés (très) passés          Exposés passés (récents)          Contacts

Depuis sa création en mai 2010, l'équipe CALIN (Combinatoire, algorithmique et interactions) a fait du mardi une journée-séminaire, se composant d'exposés généralistes ou de groupes de travail, reprenant ainsi la tradition des séminaires CIP (Combinatoire, Informatique, Physique) et de l'ancienne équipe "Optimisation combinatoire et algorithmique distribuée".

PlanCampus

Les séminaires de l'équipe ont lieu tous les mardis (10h30->12h15, 14h00->15h00, suivi de notre salon de thé combinatoire 15h45->17h00) en salle B107 au LIPN (voici un plan).

Seminars usually take place each Tuesday in room B107 at the LIPN (here is a map).

Si vous souhaitez venir donner un exposé chez nous, ce serait avec grand plaisir : contacter Gérard Duchamp pour le créneau de 10h30 ou Cyril Banderier et Thierry Monteil pour le créneau de 14h00.

Liste des exposés (et des évènements scientifiques) à venir :

[Voir le site des actualités du LIPN pour les annonces des autres séminaires du LIPN, ou le site de nos collègues de probabilités au LAGA. Voir aussi le séminaire de combinatoire "Philippe Flajolet".]

12 septembre 2017 B107 14h00 Christophe Vignat Euler Polynomials and Identities for Non-Commutative Operators

Liste des exposés passés [2002-2017] :

[Si vous souhaitez accèder directement aux plus anciens exposés passés, cliquez ici !]
27/06/2017 Vincent Delecroix Compter les méandres [abstract.html
Un méandre est une configuration d'intersections de deux courbes sur la sphère. Leur comptage résiste depuis longtemps à l'assaut des physiciens théoriciens, des informaticiens et des mathématiciens. Nous savons depuis longtemps qu'il existe un exposant de croissance exponentielle (pour des raisons de sous-additivité) mais pas beaucoup plus... Dans cet exposé, je présenterai comment obtenir des asymptotiques de comptage de méandres lorsqu'on contraint la combinatoire. Dans les cas que nous considérons, l'asymptotique est polynomiale et non plus exponentielle. Ces résultats nouveaux obtenus par des méthodes de théorie ergodique n'éclairent pas, à priori, le problème du comptage non contraint. (travail en commun avec E. Goujard, A. Zorich et P. Zograf)
] [arXiv] [arXiv]
13/06/2017 Samuele Giraudo Grammaires à bourgeons [Slides.pdf] [abstract.html
Les opérades colorées permettent de généraliser la notion de grammaire non contextuelle de façon à décrire des familles d'objets combinatoires variées (dont les arbres, englobant de ce fait les grammaires d'arbres régulières). Nous allons introduire ces grammaires, appelées grammaires à bourgeons, et expliquer comment il est possible de considérer des séries formelles sur les opérades colorées. Ce dernier point offre des outils pour le dénombrement. Dans ce contexte, nous introduisons plusieurs produits sur l'espace de ces séries : un produit pré-Lie, un produit de composition associatif et deux analogues de l'étoile de Kleene.
] [arXiv]
13/06/2017 Samuele Giraudo Opérades des cliques décorées [Slides.pdf] [abstract.html
Nous proposons une construction fonctorielle de la catégorie des magmas unitaires vers celle des opérades non symétriques. Cette construction munit l'espace des configurations de diagonales décorées dans les polygones d'une structure d'opérade. On obtient ainsi diverses nouvelles opérades sur des sous-familles particulières de tels polygones : configurations sans croisement, configurations non imbriquées, configurations de Motzkin, etc. Nous montrons aussi comment cette construction permet de donner des définitions alternatives d'opérades déjà connues comme l'opérade des simples et doubles multi-tiles (provenant de la théorie des langages) et l'opérade de gravité.
] [arXiv]
06/06/2017 Akhilesh Parol Multizeta values and Apéry-like sums [Slides.pdf]
06/06/2017 Hoang Ngoc Minh Le domaine des polylogarithmes (The domain of Li)
30/05/2017 Pierre Lairez Calcul des périodes : applications aux sommes binomiales et au volume d'ensembles semi-algébriques [abstract.html
L'étude des intégrales de fonctions algébriques est très fructueuse en géométrie algébrique, comme l'illustre, par exemple, les travaux d'Euler sur les intégrales elliptiques. Les applications aux calculs effectifs sont moins connues. J'en présenterai quelques unes. Plus précisément, je vais m'intéresser aux « périodes », c'est le résultat de l'intégration sur un cycle d'une fractions rationnelle en plusieurs variables. Je montrerai comment les calculer, sous la forme d'équations différentielles, et j'expliquerai deux applications à des problèmes bien différents : la démonstrations automatiques d'identités entre sommes binomiales et le calcul du volume de certains ensembles semi-algébriques (i.e., définis par un ensemble d'inégalités polynomiales).
]
30/05/2017 Hoang Ngoc Minh Autour des associateurs (séance de calcul) [abstract.html
This talk concerns the resolution of $KZ_3$ and our recent results on combinatorial aspects of zeta functions, $\{\zeta(s_1,\ldots,s_r)\}_{s_1,\ldots,s_r\in\C^r}$. In particular, we describe the action of the differential Galois group of $KZ_3$ on the asymptotic expansions of its solutions leading to a group of associators which contains the associator $\Phi_{KZ}$. Non trivial expressions of an associator with rational coefficients is also explicitly provided, based on the algebraic structures and the singularity analysis of the polylogarithms, $\{\Li_{s_1,\ldots,s_r}\}_{s_1,\ldots,s_r\in\C^r}$, and the harmonic sums, $\{\H_{s_1,\ldots,s_r}\}_{s_1,\ldots,s_r\in\C^r}$.
]
23/05/2017 Thierry Monteil Magouilles diverses pour les machines à signaux [abstract.html
Les machines à signaux sont un modèle de calcul déterministe dont espace et temps sont continus.

Si les accumulations d'événements sont interdites, ce modèle est connu pour être équivalent au modèle de BlumShubSmale linéaire. Nous construirons dans ce cadre un oracle universel optimal (en nombre de vitesses et de paramètres irrationnels). Nous verrons comment jouer au billard permet semi-décider l'algébricité d'un nombre réel alors que c'est impossible dans le modèle BSS-linéaire. Nous verrons comment modifier légèrement le modèle pour obtenir un modèle équivalent au modèle BSS standard.

Lorsque l'on permet aux accumulations d'événements de produire un signal, nous verrons, en jouant sur l'alternance discret/continu, comment construire des machines dont le pouvoir dépasse largement les modèles de calcul usuels, en particulier, nous construirons

  • une "courbe de Peano" c'est a dire une surjection de [0,1] dans [0,1]^2.
  • un "oracle universel continu", c'est à dire un machine à un paramètre M(p) telle que toute suite N->[0,1] est generèe un certain M(p).
  • une "fonction analytique universelle", c'est à dire une machine avec 2 parametres t,x telle que pour toute fonction analytique f de rayon de convergence >1, il existe t tel que f(x)=M(t,x) pour tout x dans [-1,1], en particulier, on peut calculer les fonctions exp(x), sin(), en déplaçant un curseur.
  • aussi, on peut prendre en compte la géométrie du modèle dans la formulation même de ce que peut "calculer" (ou "dessiner") une machine, pas seulement un booléen, un entier ou un réel comme dans le cas discret. Étant donnée une machine M, si certains types de collisions sont coloriés en rouge, l'ensemble de leurs accumulations au temps 1 est un compact. Il se trouve que cette restriction est la seule : il existe une machine à un parametre M(p) telle que pour tout compact K inclus dans [0,1], il existe p dans [0,1] tel que l'ensemble des accumulations rouges de M(p) au temps 1 est K.

L'exposé sera informel et sa compréhension ne nécessitera pas de prérequis.

]
23/05/2017 Hoang Ngoc Minh Autour des associateurs [abstract.html
This talk concerns the resolution of $KZ_3$ and our recent results on combinatorial aspects of zeta functions, $\{\zeta(s_1,\ldots,s_r)\}_{s_1,\ldots,s_r\in\C^r}$. In particular, we describe the action of the differential Galois group of $KZ_3$ on the asymptotic expansions of its solutions leading to a group of associators which contains the associator $\Phi_{KZ}$. Non trivial expressions of an associator with rational coefficients is also explicitly provided, based on the algebraic structures and the singularity analysis of the polylogarithms, $\{\Li_{s_1,\ldots,s_r}\}_{s_1,\ldots,s_r\in\C^r}$, and the harmonic sums, $\{\H_{s_1,\ldots,s_r}\}_{s_1,\ldots,s_r\in\C^r}$.
]
16/05/2017 Yann Chevaleyre Thé combinatoire accompagné d'un petit problème de combinatoire géométrique issu de l'apprentissage
16/05/2017 Yann Ponty Génération aléatoire de marches 2D positives [abstract.html
Les marches aléatoires 2D, composés d'un ensemble fini de pas élémentaires et restreintes au quadrant positif, forment des classes combinatoires dotées de structures typiquement complexes, et admettant une grande variété de comportements asymptotiques. En collaboration avec Jérémie Lumbroso (Princeton, USA) et Marni Mishna (SFU, Canada), nous nous intéressons à la génération aléatoire uniforme de marches d'une taille n donnée, à partir de l'ensemble des pas élémentaires. Notre principal résultat consiste en un algorithme de rejet, qui remplace le quart de plan par un demi-plan bien choisi. On se ramène alors à la génération aléatoire de marches 1D composées de pas généralement irrationnels, et pour lesquels une génération uniforme est possible en temps polynomial à partir d'une famille de grammaires non-contextuelles. Un résultat de Garbit et Raschel démontre ensuite l'existence d'un demi-plan tel que l'espérance du nombre de tirages dans le demi-plan est polynomiale, mais une analyse plus fine de la complexité de cette approche soulève des questions en combinatoire (analytique) des marches 1D/2D et des spécifications algébriques. Cette présentation consiste en une version étendue d'un exposé présenté à GASCOM 2016.
]
09/05/2017 Tom Denat Random graphs and average-case analysis of NP-complete problems [Slides.pdf] [arXiv]
02/05/2017 Alice Héliou Mots minimaux absents
02/05/2017 Hoang Ngoc Minh The algebra of Kleene stars of the plane and polylogarithms [arXiv]
25/04/2017 Nicolas Behr The rule algebra framework - a diagram-algebraic approach to stochastic rewriting  [abstract.html
I will give an overview and report on the latest results of the so-called rule algebraic approach to stochastic rewriting systems [1,2]. Besides a general (high-level) introduction to the mathematical concepts, the focus of the talk will be on the practical implications in terms of efficiently analyzing rewriting systems. In particular, I will compare the traditional approaches to analyzing chemical reaction systems (aka discrete graph rewriting systems) to analytically tractable cases of stochastic graph rewriting systems, such as the preferential attachment model. Amongst the novel results, the combinatorial conversion and disassociator dynamics theorems introduced in detail in the morning session will be mentioned, as well as perspectives in terms of restricted rewriting systems.
[1] N. Behr, V. Danos and I. Garnier, Stochastic mechanics of graph rewriting, In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 46-55. ACM, 2016.
[2] N. Behr, V. Danos, I. Garnier and T. Heindel, The algebras of graph rewriting, arXiv preprint arXiv:1612.06240 (2016).
] [arXiv]
25/04/2017 Nicolas Behr Combinatorial conversion and disassociator dynamics for stochastic rewriting systems [abstract.pdf]
18/04/2017 Thomas Dreyfus Holonomie et non-holonomie des marches dans le quart de plan [abstract.html
L'étude des marches dans le quart de plan a fait ces dernières années l'objet de nombreuses avancées, aussi bien par des méthodes de combinatoire, de théorie des probabilités, de théorie du potentiel, de calcul formel... Il reste de nombreux problèmes ouverts, comme notamment mieux comprendre pourquoi certaines marches sont dénombrées par des séries génératrices algébriques, d'autres par des séries D-finies (holonomes), tandis que d'autres (a priori très "proches") aboutissent à des séries non différentiellement algébriques. Nous montrerons comment la théorie de Galois (et notamment ses variantes pour des équations aux différences), ainsi que des éléments d'analyse complexe (paramétrisation de courbes par fonctions elliptiques) nous a permis d'avancer sur ces questions. [travail joint avec Michael Singer, Julien Roques, Charlotte Hardouin]
] [arXiv]
18/04/2017 Gérard Duchamp Noncommutative evolution equations : twosided multipliers, initial conditions and asymptotics.
11/04/2017 Nicolas Gachadoit Utilisation avancée de Maple : calcul parallèle et interfaçage avec des bibliothèques externes [abstract.html
Maple possède plusieurs milliers de fonctions, mais certains calculs spécifiques peuvent nécessiter l'utilisation de bibliothèques externes. Par ailleurs, les ordinateurs n'évoluent plus tellement dans le sens d'une augmentation de la fréquence des processeurs mais dans le sens d'une augmentation du nombre de cœurs de calcul. Cette présentation détaillera les fonctionnalités de Maple permettant de réaliser des calculs parallèles et de s'interfacer avec du code écrit dans d'autres langages.
]
04/04/2017 Mireille Régnier Accurate prediction of the statistics of repetitions in random sequences [abstract.html
Repetitive patterns in genomic sequences have a great biological significance and also algorithmic implications. Analytic combinatorics allow to derive formula for the expected length of repetitions in a random sequence. Asymptotic results, that generalize previous works on a binary alphabet, are easily computable. Simulations on random sequences show their accuracy. As an application, the sample case of Archaea genomes illustrates how biological sequences may differ from random sequences.
]
28/03/2017 Sergey Dovgal Phase Transition Threshold for Random Graphs and 2-SAT using Degree Constraints [abstract.html
We show that by restricting the degrees of the vertices of a graph to an arbitrary set Δ, the threshold α(Δ) of the phase transition for a random graph with n vertices and m = α(Δ).n edges can be either accelerated (e.g., α(Δ) approx 0.38 for Δ = {0,1,4,5}) or postponed (e.g., α(Δ) approx 0.95 for Δ={1,2,50}) compared to a classical Erdős–Rényi random graph where α(N)=1/2. We investigate different graph statistics inside the critical window of transition (planarity, diameter, longest path...). We apply our results to a 2-SAT model with restricted literal degrees: the number of clauses that each literal is incident to belongs to the set Δ. We prove a lower bound for the probability that a formula with n variables and m=2.α(Δ) n clauses is satisfiable. This probability is close to 1 for the subcritical regime m=2.α.n.(1-μ.n-1/3), μ to ∞ and improves/generalizes the lower bound of Bollobás, Borgs, Chayes, Kim, and Wilson. This shows how the phase transition threshold for 2-SAT moves if we change the degrees of the literals. Joint work with Vlady Ravelomanana.
] [arXiv]
21/03/2017 Journées ALEA
14/03/2017 Xavier Goaoc Géométrie combinatoire : densité d'hypergraphes et méthode probabiliste [abstract.html
Un hypergraphe à n sommets dont aucune projection sur k sommet n'est complète a au plus O(n^{k-1}) arêtes. Ce résultat, découvert simultanément par Sauer, Vapnick-Chervonenkis et Perles-Shelah au début des années 1970, est fondamental en apprentissage. En géométrie combinatoire et algorithmique, il permet souvent de contrôler la complexité (globale) d'une structure par sa "densité" locale. J'introduirai à ce mécanisme avant de présenter quelques extensions récentes, obtenues conjointement avec Boris Bukh (https://arxiv.org/abs/1701.06632), qui permettent un controle plus fin de la complexité. L'exposé ne supposera aucune connaissance préalable et un des ingrédients sera une construction probabiliste.
] [arXiv]
07/03/2017 CALIN réunion d'équipe pour le rapport scientifique
07/03/2017 Christophe Tollu TBA
21/02/2017 Nicolas Macé Conductivité des quasicristaux et pavages apériodiques [Slides.pdf] [arXiv]
21/02/2017 Christian Lavault Fonctions de type Mittag-Leffler et calcul fractionnaire
07/02/2017 Éric Fusy Bijections for planar maps with boundaries [Slides.pdf]
07/02/2017 Gérard H. E. Duchamp Polylogarithms and fields of germs
31/01/2017 Veronica Guerrini The neighbours of Baxter numbers [Slides.pdf] [abstract.html
Baxter numbers are a well known number sequence enumerating Baxter permutations and several other combinatorial objects. In this talk, we define a new class of objects called Slicings of parallelogram polyominoes counted by Baxter numbers that enables us to find a continuum from Catalan structures to Baxter structures. This continuum is established by means of a new succession rule (i.e. generating tree) associated with Schröder numbers, that interpolates between the known succession rules for Baxter and Catalan numbers. Then, similarly we consider a generalization for the Baxter succession rule that forms a link between Baxter numbers and Factorial numbers. Such succession rule defines semi-Baxter numbers, which result to count plane permutations, whose enumeration was set as an open problem by Bousquet-Mélou and Butler, and inversion sequences avoiding (210,100), as conjectured by Martinez and Savage.
]
25/01/2017 Journées combinatoires de Bordeaux (25-27 janvier)
24/01/2017 Gérard Duchamp Polylogarithms and solutions of KZ3 + programme février-mars
17/01/2017 Workshop on Large Random Structures in Two Dimensions (IHP 16-20 janvier)
17/01/2017 Gérard Duchamp Non-commutative differential equations, topology and algebra III (interactive).
10/01/2017 Youssef Abdelaziz Combinatorial physics, hypergeometric functions and differential equations [arXiv]
10/01/2017 Philippe Duchon Permutations aléatoires et cycles courts (via des arbres de génération) [abstract.html
Tirer une permutation aléatoire uniforme de taille n n'est pas bien difficile, et on sait assez bien à quoi c'est censé ressembler. Qu'en est-il si on souhaite imposer des restrictions sur le type cyclique? Il n'est pas bien difficile non plus de tirer une permutation aléatoire ayant un nombre prédéterminé de points fixes - il suffit de savoir tirer un dérangement, et à grande taille, près de 37% des permutations sont des dérangements. On a donc facilement un algorithme qui va nécessiter en moyenne O(n) tirages d'entiers aléatoires d'ordre O(n). Dans ce travail en commun avec Romaric Duvignau (EJC, 2016), nous montrons comment cela peut être fait avec n+O(1) tirages en moyenne, par un rejet anticipé. Cela est possible grâce à la construction d'un arbre de génération pour les permutations, qui a la particularité de "fixer" très rapidement, et aussi vite qu'il est possible, le nombre de points fixes. Comme conséquences faciles, on a alors des algorithmes tout aussi efficaces pour tirer des permutations aléatoires avec un nombre prescrit de points fixes. Le passage de "points fixes" à "cycles d'une longueur k donnée" est possible, mais sensiblement moins élégant.
]
10/01/2017 Gérard Duchamp Non-commutative differential equations, topology and algebra II (characters).
03/01/2017 Gérard Duchamp Séries doubles et structures de données
03/01/2017 Hoang Ngoc Minh Séance d'ouverture 2017 : Polylogarithms and harmonic sums with complex multi-indices.
20/12/2016 Gérard Duchamp Non-commutative differential equations, topology and algebra
13/12/2016 Journée MathSTIC Modèles de dimères : Vincent Beffara, Benoît Laslier, Cédric Boutillier, Béatrice de Tilière
09/12/2016 Quoc Hoan Ngo Double regularization of polyzetas at negative multi-indices and rational extensions (soutenance de thèse) [abstract.html
In this PhD thesis are studied the polylogarithms and the harmonic sums at non-positive (i.e., weakly negative) multi-indices. General results about these objects in relation with Hopf algebras are pr ovided. The technics exploited here are based on the combinatorics of noncommmutative generating series relative to the Hopf phi-huffle algebra. Our work will also propose a global process to renormalize divergent polyzetas. Finally, we will apply these ideas to non-linear dynamical systems with singular inputs.

The jury will be composed of: Gérard Duchamp, Hoang Ngoc Minh (directeurs), Sylvie Paycha, Dominique Manchon (rapporteurs), Karol Penson, Vincent Rivasseau, Loic Foissy, Christophe Tollu.

]
09/12/2016 Van Chiên Bui Développement asymptotique des sommes harmoniques (soutenance de thèse) [abstract.html
En abordant les nombres spéciaux comme les sommes harmoniques ou les polyzêtas sous leur aspect combinatoire, nous introduisons d'abord la définition d'un produit entre mots, dit produit de quasi-mélange q-déformé, une généralisation des produits de mélange et de quasi-mélange, ce qui nous permet de construire des structures complètes d'algèbre de Hopf en dualité. En même temps, nous construisons des bases en dualité, contenant des bases de transcendance associées aux mots de Lyndon, et des formules explicites sur lesquelles les sommes harmoniques, les polyzêtas ou les polylogarithmes sont indexés et représentés par la factorisation de la série génératrice noncommutative diagonale. De cette façon, en identifiant les coordonnées locales, nous trouvons des relations polynomiales homogènes, en poids, entre les polyzêtas indexés par ces bases. Enfin, nous déterminons les développements asymptotiques des sommes harmoniques, indexées aussi par ces bases, grâce à leur série génératrice et à la formule d'Euler Maclaurin. Pour accompagner cette étude théorique, nous proposons des algorithmes et un package en Maple afin de calculer des bases, la structure des polyzêtas et des développements asymptotiques des sommes harmoniques.

Le jury sera composé de Gérard Duchamp, Hoang Ngoc Minh, (co-directeurs), Jacky Cressson, Loïc Foissy, (rapporteurs), Sylvie Paycha, Joris van der Hoeven, Daniel Barsky, Christophe Tollu (examinateurs).

]
06/12/2016 Tatiana Starikovskaya Streaming and communication complexity of Hamming distance [Slides.pdf] [abstract.html
We will discuss the complexity of one of the most basic problems in pattern matching, that of approximating the Hamming distance. Given a pattern P of length n the task is to output an approximation of the Hamming distance (that is, the number of mismatches) between P and every n-length substring of a longer text. We provide the first efficient one-way randomised communication protocols as well as a new, fast and space efficient streaming algorithm for this problem.
]
06/12/2016 Van Chiên Bui Développement asymptotique des sommes harmoniques (3ème partie)
06/12/2016 Quoc Hoan Ngo Double régularisation des polyzêtas en les multi-indices négatifs et extensions rationnelles (3ème partie)
02/12/2016 Alexandra Ugolnikova Pavages aléatoires (soutenance de thèse) [abstract.html
B0;136;0cDans cette thèse nous étudions deux types de pavages : des pavages par une paire de carrés et des pavages sur le réseau tri-hexagonal (Kagome). Nous considérons différents problèmes combinatoires et probabilistes. Nous commençons par le cas des carrés 1 × 1 et 2 × 2 sur des bandes infinies de hauteur k et obtenons des résultats sur la proportion moyenne des carrés 1 × 1 pour les cas planaire et cylindrique pour k ≤ 10. Nous considérons également des questions d’échantillonnage et comptage approximatif. Pour obtenir un échantillon aléatoire nous définissons des chaînes de Markov pour les pavages par des carrés et sur le réseau Kagome. Nous montrons des bornes polynomiales pour le temps de mélange pour les pavages par des carrés 1 × 1 et s × s des régions n × log n et les pavages Kagome des régions en forme de losange. Nous considérons aussi des chaines de Markov avec des poids λ sur les tuiles. Nous montrons le mélange rapide avec des conditions spécifiques sur λ pour les pavages par des carrés 1 × 1 et s × s et pavages Kagome. Nous présentons des simulations qui suggèrent plusieurs conjectures, notamment l’existence des région gel´ees pour les pavages aléatoires par des carrés et sur le réseau Kagome des régions avec des bords non plats.

Le jury se composera de Thomas Fernique (directeur), Béatrice de Tilière, Éric Rémila (rapporteurs), et de Frédérique Bassino, Olivier Bodini, Ana Bušić, Pavel Kalouguine.

]
29/11/2016 Olivier Bodini Une analyse asymptotique des polyominos digitalement convexes. [abstract.html
Dans cet exposé, nous montrerons comment des techniques élémentaires (transformées de Mellin) en combinatoire analytique permettent d'obtenir des résultats assez surprenants sur les polyominos. En particulier, si l'on savait correctement énumérer les polyominos digitalement convexes, nous saurions si l'hypothèse de Riemann est vraie !
]
29/11/2016 Van Chiên Bui Développement asymptotique des sommes harmoniques (2ème partie)
29/11/2016 Quoc Hoan Ngo Double régularisation des polyzêtas en les multi-indices négatifs et extensions rationnelles (2ème partie)
22/11/2016 Quoc Hoan Ngo Double régularisation des polyzêtas en les multi-indices négatifs et extensions rationnelles.
22/11/2016 Réunion d'équipe
22/11/2016 Van Chiên Bui Développement asymptotique des sommes harmoniques
17/11/2016 Journée MathSTIC Croissance-fragmentation : Benjamin Dadoun (Zurich), Marie Doumic (INRIA), Igor Kortchemski (X), Quan Shi (P13)
15/11/2016 Quoc Hoan Ngo An interface between physics and number theory [abstract.pdf]
15/11/2016 Samuel Petite Restrictions sur le groupe d'automates cellulaires préservant un sous-shift fixé [abstract.html
Un sous shift est un ensemble fermé de suites sur un alphabet fini, invariant par décalage (le shift). L'ensemble des automates cellulaires préservant ce sous shift est en général un groupe dénombrable compliqué. Nous présenterons dans cet exposé un survol des différentes restrictions sur ces groupes pour les sous-shift d'entropie nulle.
]
15/11/2016 Suzy Maddah On Generalized Hypergeometric Solutions of Linear Differential Systems of First Order [abstract.html
In this talk, we consider linear differential systems of first order (equivalently linear differential equations of arbitrary order), and we question whether they can be solved in terms of generalized hypergeometric functions. This question is motivated by the many properties of the latter which arise in physics and combinatorics. It has been tackled in the literature for second-order differential equations, namely Bessel's, Whittaker's, Kummer's, and Gauss's. We propose a new algorithm which surpasses the restrictions on the dimension of the system, and equivalently on the order of the equation. This is a joint work with Frédéric Chyzak.
]
08/11/2016 30 ans du LIPN
25/10/2016 Vincent Pilaud Réalisations géométriques des complexes d'accordéons [abstract.html
Soient 2n points en position convexe alternativement colorés rouges et bleus, et soit D une dissection de l'enveloppe convexe des points rouges. Une diagonale entre deux points bleus est un D-accordéon si les arêtes de D qu'elle croise forment un accordéon. Le complexe d'accordéons de D est le complexe simplicial formé des ensembles de D-accordéons qui ne se croisent pas. Par exemple, le complexe d'accordéons d'une triangulation est un associaèdre, et celui d'une quadrangulation a été étudié par Baryshnikov et Chapoton. Ces complexes ont été introduits récemment par Garver et McConville dans un langage dual. Dans cet exposé, nous donnerons des réalisations géométriques de ces complexes simpliciaux, basées sur de fortes analogies avec les algèbres amassées de type fini. Lorsque D est une triangulation ayant des triangles internes, nous obtenons en particulier de nouvelles réalisations de l'associaèdre. Cet exposé est basé sur des travaux en commun avec Christophe Hohlweg (UQAM, Montréal), Thibault Manneville (LIX, École Polytechnique) et Salvatore Stella (Univ. la Sapienza, Rome).
]
25/10/2016 Christophe Tollu Sur les catégories additives et abéliennes II
18/10/2016 Johan Nilsson Counting square tilings [abstract.html
We consider tilings of a rectangle with squares tiles of size 1x1 and 2x2. We present a method to calculate the number of such tilings via matrix multiplication, where we optimize the number of multiplication needed and reduce the space required for the matrix multiplication by dynamically generate the matrices involved.
]
18/10/2016 Van Chiên Bui Développement asymptotique des sommes harmoniques
11/10/2016 Gérard Duchamp Non-commutative differential equations and (some) geometrical hints [abstract.html
On prendra appui sur les intégrales itérées des systèmes fuschsiens pour proposer une théorie des équations différentielles non-commutatives. Plusieurs surprises et cadeaux nous attendent dans cette exploration.
]
11/10/2016 Christophe Tollu Sur les catégories additives et abéliennes
06/10/2016 Nicolas Rolin De l'usage des opérateurs en combinatoire : construction, analyse et génération aléatoire (soutenance de thèse) [abstract.html
On étudie en combinatoire les objets munis d'une taille (la taille dans le cadre informatique peut se traduire par exemple par la mémoire occupée par l'objet). On appelle classe combinatoire un ensemble d'objets qui pour toute taille possède un nombre fini d'éléments. On peut par exemple considérer les textes régis par une certaine grammaire, dans ce cas la taille est le nombre de caractères, ou des arbres avec comme taille le nombre de nœuds. Une méthode naturelle pour décrire les classes, la méthode symbolique, consiste à décomposer les objets en sous-objets plus élémentaires à l'aide d'opérateurs (tels que l'union disjointe, le produit cartésien,...). On peut ensuite traduire ces décompositions sur des séries formelles. Le premier volet de résultats présentés dans cette thèse traite de la méthode symbolique et de son utilisation. On y présente des résultats asymptotiques sur des modèles d'arbres croissants issus de la théorie de la concurrence, puis une discussion sur comment décomposer certains opérateurs en réplications élémentaires. Le deuxième volet de résultats s'intéresse au sujet de la génération aléatoire uniforme d'objets dans une classe donnée. On montre tout d'abord comment générer des structures croissantes en adaptant les méthodes de génération récursive classiques aux opérateurs de produit croissant. On présente ensuite des résultats sur la génération de Boltzmann, avec une comparaison quantitative de deux méthodes, puis une extension permettant de conserver les propriétés d'uniformité de la génération en utilisant des approximations.
]
04/10/2016 Marc Mezzarobba Évaluation multi-précision rigoureuse de fonctions D-finies en Sage [Slides.pdf] [abstract.html
Je présenterai une implémentation en développement d'algorithmes d'évaluation numérique de fonctions D-finies (c.-à-d. solutions d'équations différentielles linéaires à coefficients polynomiaux), pour le logiciel de calcul formel libre SageMath. Ce nouveau package a vocation à remplacer NumGfun, un package un peu similaire pour Maple que j'ai présenté au séminaire CALIN il y a quelques années. Si le temps le permet, je dirai aussi quelques mots des algorithmes originaux utilisés. La fonctionnalité centrale de ce code est le « prolongement analytique numérique » d'une fonction D-finie, qui fournit une approximation de la matrice envoyant un jeu de conditions initiales en un point donné du plan complexe sur les conditions « initiales » qui définissent la même fonction au voisinage d'un autre point. Le prolongement analytique numérique permet de calculer des valeurs ou encore des approximations polynomiales de fonctions D-finies n'importe où sur leur surface de Riemann, des matrices de monodromie d'opérateurs différentiels, etc. Le code traite complètement le cas limite important de conditions initiales généralisées données en un point singulier régulier de l'opérateur. Il peut donc être utilisé pour calculer des matrices de connexion entre singularités régulières, ce qui est utile notamment en combinatoire analytique. Par ailleurs, il s'agit d'une implémentation rigoureuse, au sens où elle renvoie des intervalles qui (sauf bug !) contiennent à coup sûr le résultat mathématique exact.
]
04/10/2016 Gérard H. E. Duchamp TBA
27/09/2016 Quan Shi Random recursive trees and growth-fragmentations [abstract.html
Growth-fragmentation processes describe the evolution of particles that grow and divide as time proceeds. Previous studies on growth-fragmentations have mostly focused on the self-similar case. In this talk we introduce a new class of growth-fragmentations, called Ornstein- Uhlenbeck type growth-fragmentations. Loosely speaking, the size of each fragment evolves according to the exponential of a Lévy driven Ornstein-Uhlenbeck type process. This model is partly motivated by the work of Bertoin and Baur (EJP. 2015) which shows that such processes arise naturally in dynamical percolation on an infinite random recursive tree.
]
27/09/2016 Hoang Ngoc Minh Trans-series and a nice story.
20/09/2016 Joseph Ben Geloun Counting observables of colored tensor models [abstract.html
Colored tensor models generate Feynman graphs representing discrete geometries. They form as an interesting approach of quantum gravity where discrete geometries represent quanta of spacetime. The coloring in tensor models improves a lot the topology type of these discrete structures and this helps a lot in their understanding. In my presentation, I will review (in a pedestrian way) their construction and then list basic properties of their observables. Recalling that an observable simply means in this context a convolution or contraction of tensors, observables of colored tensor models map to bi-partite colored graphs. A first question that one can address is can we enumerate these observables? I will explain how such an enumeration is possible and how it has lead us to an intriguing bijection with the counting of branched covers of the 2-sphere.
]
20/09/2016 Eric Hoffbeck Shuffle d'arbres [abstract.html
Les shuffles (battages) jouent un rôle important dans la compréhension du produit d'ensembles simpliciaux, qui intervient à de nombreux endroits en topologie algébrique. Récemment, une généralisation des ensembles simpliciaux a été introduite : les ensembles dendroidaux (on remplace les {0,1,...,p} (avec leur ordre total) par des arbres (avec leur ordre partiel)). La catégorie des ensembles dendroidaux est également munie d'un produit, où interviennent des shuffles d'arbres. Dans cet exposé, après une brève motivation topologique, j'introduirai cette notion de shuffles d'arbres, en donnant plusieurs définitions équivalentes et de nombreux exemples. Je présenterai ensuite quelques propriétés algébriques et combinatoires de ces shuffles. Mon exposé est basé sur un travail en commun avec Ieke Moerdijk.
]
06/09/2016 Julien Courtiel Génération des alignements d'arbres [abstract.html
L'alignement d'arbres est la généralisation naturelle de la notion classique d'alignement de séquences. Elle est utilisée dans de nombreux domaines, y compris pour la comparaison de structures secondaires d'ARN (ce qui nous intéressera aujourd'hui). Nous allons donc comprendre comment explorer l'espace des alignements d'arbres et comment déduire des algorithmes efficaces pour comparer les ARN. Cet exposé introduit ainsi les notions d'alignement de séquences et d'arbres et décrit le problème d'ambiguïté qui point quand nous voulons générer de manière correcte les alignements d'arbres. Pour résoudre ce problème d'ambiguïté dans le contexte des alignements d'arbres, nous donnons un schéma de décomposition sous la forme de grammaire sans contexte. Cela conduit à de nombreux résultats : propriétés statistiques sur les larges structures d'ARN, algorithmes efficaces d'échantillonnage... Ces travaux, en collaboration avec Cédric Chauve et Yann Ponty, illustrent le fait que la combinatoire peut être un puissant couteau suisse pour traiter des problèmes algorithmiques qui apparaissent dans de nombreux champs appliqués.
]
06/09/2016 Collectif Réunion d'organisation + exposé
26/07/2016 Quoc Hoan Ngo Polylogarithms at non-positive (i.e. negative) multi-indices II [abstract.pdf]
12/07/2016 Nihar Prakash Gargava Some properties of the image of the star of the plane [abstract.pdf]
28/06/2016 Quoc Hoan Ngo Polylogarithms at non-positive (i.e. negative) multi-indices [abstract.pdf]
21/06/2016 Van Chiên Bui Asymptotic expansion of harmonic sums thanks to the Euler-Maclaurin formula and to generating series [abstract.html
On the one hand, asymptotic expansions of harmonic sums are constructed by following the Euler-Maclaurin formula. On the other hand, due to relations among polylogarithms, polyzetas, harmonic sums and their generating series, which are the Lie exponentials in the shuffle and quasi shuffle algebras, we will show structure of polylogarithms and polyzetas. From this, asymptotic expansions of harmonic sums will also establish by following generating series.
]
16/06/2016 Journée MathSTIC Rencontre "Combinatoire, Opérades et Probabilités" à Paris 13
14/06/2016 Hoang Ngoc Minh Double regularization of polyzetas at negative multi-indices and polylogarithmic trans-series
07/06/2016 Christophe Tollu Algèbres de Hall (construction catégorique) II
31/05/2016 Élie de Panafieu Counting connected graphs with large excess [abstract.html
We enumerate the connected graphs that contain a linear number of edges with respect to the number of vertices. So far, only first term of the asymptotics and a bound on the error were known (Bender Canfield McKay 1995, Pittel Wormald 2005, van der Hofstad Spencer 2006). We present a proof based on analytic combinatorics, i.e. generating function manipulations, and derive the complete asymptotic expansion.
] [arXiv]
31/05/2016 Hoang Ngoc Minh Transséries polylogarithmiques II
30/05/2016 Summer School Transversal Aspects of tilings (30 mai-24 juin)
25/05/2016 José Aliste-Prieto Reconstruction of trees and chromatic polynomial [abstract.html
The U-polynomial of a graph was introduced by Noble and Welsh as a generalization of some invariants coming from Knot theory. It also generalizes the chromatic symmetric function of Stanley. In this talk, we will consider the problem of whether there exist non-isomorphic trees with the same U-polynomial (or,equivalently, with the same chromatic symmetric function). We will survey what is know about the U-polynomial and this problem. In particular, we will show how to recover some classic invariants from the U-polynomial and we exhibit several subclasses of trees for which a solution of this problem is known. FInally, we construct some non-isomorphic trees with "almost" the same U-polynomial, based on solutions of an old problem in Number theory due to Prouhet-Tarry-Escott.
] [arXiv]
24/05/2016 Peter Nejjar KPZ growth models and Tracy-Widom distributions [.pdf] [.pdf]
24/05/2016 Christophe Tollu Algèbres de Hall (construction catégorique)
17/05/2016 Bernhard Gittenberger Analytic combinatorics of lambda-terms
17/05/2016 Hoang Ngoc Minh Transséries polylogarithmiques
10/05/2016 Gwendal Collet Limit laws of vertex degree distribution in planar maps [abstract.html
We consider the family of rooted planar maps where the vertex degrees belong to a (possibly infinite) set of positive integers. Using a classical bijection with mobiles and some refined analytic tools to deal with the systems of equations that arise, we first recover the universal asymptotic behaviour of planar maps. Furthermore we establish that the expected number of vertices of a given degree satisfies a multi-dimensional central limit theorem. We also discuss some possible extension to maps of higher genus.
]
10/05/2016 Gérard H. E. Duchamp Abélianisation et majorations de Lappo-Danilevski IV : Propriétés de croisssance [Slides.pdf] [abstract.html
In this talk, we start from two sources [i) The poly- and hyper-logarithms ii) the classic Dyson series] in order to develop the theory of noncommutative differential equations, giving a touch of Lie-theoretic insights to understand the interplay between orbits and coordinates which are - following Gelfand's paradigm - special functions. The talk(s) will be illustrated with concrete examples and explicit computations.
]
03/05/2016 Collectif Séance de programme et discussion sur les travaux en cours
03/05/2016 Gérard H. E. Duchamp Abélianisation et majorations de Lappo-Danilevski III : ED bilatères et avec second membre
26/04/2016 Gérard H. E. Duchamp Abélianisation et majorations de Lappo-Danilevski II : ED non-commutatives
19/04/2016 Henri Mühle On Noncrossing Partitions for the Alternating Groups [abstract.html
The lattice of noncrossing set partitions of an n-set can be seen as a subgraph of the Cayley graph of the symmetric group S generated by all transpositions. We mimic this construction for the alternating group A2n+1 generated by all 3-cycles. The resulting poset provides a rich new source of combinatorics coming from the alternating groups, which in some sense parallels the combinatorics behind the noncrossing set partitions. We present some enumerative and bijective results, and suggest an extension of this construction to all finite Coxeter groups. This is joint work with Philippe Nadeau.
]
12/04/2016 Alfredo Hubard Métriques extrémales et plongements de graphes [abstract.html
Dans cet exposé je présenterai des résultats dans l' intersection de la géométrie Riemannienne et la topologie algorithmique. Plus précisément, je discuterai des manières effectives de planariser une surface triangulée, des problèmes de nombre de croisements, et de la "meilleure" métrique Riemannienne pour une surface. Si le temps le permet, je parlerai également des défis en haute dimension et des connections avec les nombres de faces des complexes simpliciaux.
]
12/04/2016 Valentin Suder Antiderivative functions over F_2^n [Slides.pdf] [abstract.html
We use a linear algebra point of view to describe the derivatives and higher order derivatives over F_2^n. On one hand, this new approach ennobles us to prove several properties of these functions, as well as the functions that have these derivatives. On the other hand, we provide a method to construct all of the higher order derivatives in given directions. We also demonstrate some properties of the higher order derivatives and their decomposition as a sum of functions with 0-linear structure. Moreover, we introduce a criterion and an algorithm to realize discrete antidifferentiation of vectorial Boolean functions. This leads us to define a new equivalence of functions, that we call differential equivalence, which links functions that share the same derivatives in directions given by some subspace.
]
12/04/2016 Gérard H. E. Duchamp Abélianisation et majorations de Lappo-Danilevski I : Intégrales itérées
05/04/2016 Sylvain Carrozza O(N) random tensor models [Slides.pdf] [abstract.html
I will introduce a class of three indices tensor models, endowed with O(N)⊗3 invariance (N being the size of the tensor). They generate weights for general 3-colored graphs, which are not necessarily bipartite. Relying on combinatorial properties of colored graphs, I will first prove the existence of a 1/N expansion for any such model. I will then focus on a model with two parameters, and illustrate how standard methods from analytic combinatorics allow to compute physical quantities such as critical exponents.
]
30/03/2016 Grégory Miermont Random maps with a boundary: a user's manual
30/03/2016 Benedikt Stufler Limits of random tree-like combinatorial structures
30/03/2016 Vincent Tassion A new proof of the sharpness of the phase transition for Bernoulli percolation on Z^d
30/03/2016 Philippe Marchal Rectangular Young tableaux
30/03/2016 Journées MathSTIC, Amphi Euler:
29/03/2016 Svetlana Puzynina Infinite self-shuffling words [abstract.html
An infinite word x on an alphabet A is self-shuffling, if x admits factorizations: $x=\prod_{i=1}^\infty U_iV_i=\prod_{i=1}^\infty U_i=\prod_{i=1}^\infty V_i$ with $U_i,V_i \in \A^*$. In other words, there exists a shuffle of x with itself which reproduces x. W­­e prove that many important and well studied words are self-shuffling: This includes the Thue-Morse word and all Sturmian words except Lyndons. We further establish a number of necessary conditions for a word to be self-shuffling, and show that certain other important words (including the paper-folding word and infinite Lyndon words) are not self-shuffling. This new notion has some unexpected applications: As a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic. Finally, we provide a positive answer to a recent question by T. Harju whether square-free self-shuffling words exist and discuss self-shuffling in a shift orbit closure.
]
29/03/2016 Olivier Bouillot Une généralisation des nombres et polynômes de Bernoulli en dimensions supérieures [Slides.pdf] [abstract.html
Les multizêtas sont des nombres généralisant la fonction zêta de Riemann au cas de la dimension supérieure. Ces nombres sont (en particulier) définis sur des n-uplets d'entiers strictement positifs, mais grâce à des prolongements analytiques, il est possible de les prolonger tous les n-uplets d'entiers. Cela correspondant alors une généralisation des nombres puis des polynômes de Bernoulli. Bien qu'il n'y ait pas unicité d'une telle généralisation, nous introduirons un exemple explicite et satisfaisant où nombres de propriétés importantes des polynômes de Bernoulli se transmettent au cas multiple. Au passage, cela permet de répondre à une question sur la renormalisation des multizêtas aux entiers négatifs.
]
29/03/2016 CALIN réunion d'équipe sur les candidatures MdC
29/03/2016 Alexander Meduna Regulated Grammars and Automata [Slides.pdf] [abstract.html
This talk explains the gist underlying regulated grammars and automata as well as the main purpose of their investigation. This investigation is classified into four major topics--the study of their power, properties, reduction, and mutual convertibility. The talk illustrates this inevstigation by a case study in terms of one-sided random-context grammars. Most importantly, it points out that propagating versions of one-sided random-context grammars characterize the family of context-sensitive languages, and with erasing rules, they characterize the family of recursively enumerable languages; as a result, they are stronger than ordinary random context grammars. Open problem areas are formulated.
]
22/03/2016 Colloque en l'honneur de Marcel-Paul Schützenberger (21-25 mars, Bordeaux)
22/03/2016 Axel Bacher Lattice paths in 3D
22/03/2016 Martin Delacourt Calculer dans un automate cellulaire unidirectionnel réversible : vers l'indécidabilité de la périodicité? [abstract.html
On s'intéresse au parallèle entre 2 problèmes sur des modèles distincts d'automates. D'une part, les automates de Mealy (transducteurs lettre à lettre complets) qui produisent des semi-groupes engendrés par les transformations sur les mots infinis associées aux états. En 2013, Gillibert a montré que le problème de la finitude de ces semi-groupes était indécidable. En revanche la question est ouverte dans le cas où l'automate de Mealy produit un groupe. D'autre part, les automates cellulaires unidirectionnels pour lesquels la question de la décidabilité de la périodicité est ouverte. On peut montrer l'équivalence de ces problèmes. On fera un pas dans cette étude en montrant qu'il est possible de simuler du calcul Turing dans un automate cellulaire unidirectionnel réversible, rendant ainsi des problèmes de prédiction indécidables ainsi que la question de la périodicité partant d'une configuration finie.
]
15/03/2016 Mathias Pétréolle Partitions d'entiers et groupes de Coxeter [Slides.pdf] [abstract.html
En 2009, Han a redécouvert et généralisé une identité due à Nekrasov et Okounkov, qui fait un lien entre d'un coté, les puissances de la fonction êta de Dedekind, et de l'autre les partages d'entiers et leurs longueurs d'équerres. Pour cela, il utilise la formule de Macdonald pour le système affine de racines de type A. Je montrerai comment, à l'aide de bijections, il est possible de démontrer des identités de Nekrasov-Okounkov pour d'autres types de systèmes de racines (type affine C et D notamment), et je présenterai les nouvelles formules des équerres qui en découlent. Dans une seconde partie, je présenterai la notion d'éléments cycliquement pleinement commutatifs dans les groupes de Coxeter, qui ont été introduits pour étudier une version cyclique d'un théorème de Matsumoto. Je montrerai ensuit comment, en utilisant la théorie des automates finis, on peut démontrer que la série génératrice de ces éléments est une fraction rationnelle, quelque soit le groupe de Coxeter considéré.
]
15/03/2016 Bérénice Delcroix-Oger Algèbre de Hopf d'incidence des posets de partitions semi-pointées [Slides.pdf] [abstract.html
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. [En fonction du temps qui me restera, j'évoquerai mes récents résultats en collaboration avec J.-C. Aval, Adrien Boussicault, P. Laborde-Zubieta et F. Hivert sur les arbres non ambigus. ]
]
08/03/2016 Journées ALEA (7-11 mars 2016)
08/03/2016 Gérard H. E. Duchamp Non-commutative diffferential equations and (some) infinite dimensional Lie groups
01/03/2016 Grégory Châtel Algèbre de Hopf cambrienne [abstract.html
En 1998, Loday et Ronco décrivent une algèbre de Hopf combinatoire dont la base est indicée par des arbres binaires. Cette algèbre possède de nombreux liens avec divers résultats antérieurs. Son produit est en particulier lié aux intervalles du treillis de Tamari, structure d'ordre partiel dont les éléments sont des arbres binaires. En 2006, Reading définit la notion de treillis cambrien d'un groupes de Coxeter. Le treillis Cambrien généralise l'ordre de Tamari en utilisant des structures arborescentes qui généralisent les arbres binaires : les arbres cambriens. Une question naturelle se pose alors : est-il possible de généraliser l'algèbre de Hopf de Loday-Ronco aux arbres cambriens ? Dans cette présentation, j'expliquerai les résultats que nous avons obtenus avec Vincent Pilaud sur les arbres cambriens en type A.
]
23/02/2016 ALEA in Europe (22-26 février, München)
17/02/2016 STACS'2016 (17-20 février)
16/02/2016 Benjamin Hellouin Uniformisation de l'aléa en dynamique symbolique [abstract.html
Une transformation T : X -> X d'un espace X est dite randomisante si son itération tend à uniformiser la distribution des configurations de l'espace X. Plus précisément, quand une mesure de probabilité initiale non uniforme est fixée sur X (la distribution initiale), l'itération de la transformation T 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.
Ce travail est issu d'une collaboration avec Ville Salo et Guillaume Theyssier (ex-CMM, Universidad de Chile).
]
16/02/2016 Christophe Tollu Algèbres de (Ringel-)Hall II [abstract.html
Dans l’espoir de comprendre certains travaux récents de Berenstein et Rudel (« Quantum cluster characters of Hall algebras », arXiv:1308.2992 et « The Feigin tetrahedron », arXiv:1401.4338v2), en particulier la construction d’un homomorphisme, appelé « quantum shuffle character », entre le dual de l’algèbre de Ringel-Hall et l’algèbre de mélange quantique, j’étudierai l’algèbre de Ringel-Hall, en insistant sur sa structure d’algèbre de Hopf auto-duale.
]
12/02/2016 Damien Pous Hacking nondeterminism with induction and coinduction [abstract.html
Finite automata are used in a wide range of verification problems. We introduce "bisimulation up to congruence" as a technique for proving language equivalence of non-deterministic finite automata. Exploiting this technique, we devise an optimisation of the classical algorithm by Hopcroft and Karp which, as we show, is exploiting a weaker "bisimulation up to equivalence" technique. The resulting algorithm can be exponentially faster than the recently introduced "antichain algorithms".
]
09/02/2016 Nicolas Basset Mesure des langages temporisés et applications à la combinatoire des permutations [abstract.html
Dans un premier temps j'exposerai de manière générales la théorie de la volumétrie des langages temporisés développés durant (et depuis) ma thèse. Avec mes collègues nous avons trouvé des applications à cette théorie dans divers domaines de recherche tels que la théorie de l’information, la vérification, la combinatoire énumérative. Dans un second temps, je décrirai plus précisément comment étant donné un automate temporisé, on peut exprimer et calculer son entropie et sa fonction génératrice des volume s à l'aide de la théorie spectrale d'un opérateur fonctionnel associé à cet automate temporisé. Nous fonctionnons par analogie avec le cas discret, au lieu d'appliquer la théorie de Perron-Frobenius à la matrice d'adjacence d'un automate fini, nous appliquons la théorie des opérateurs positifs agissant sur les espaces de Banach à l'opérateur fonctionnel de notre automate temporisé. Dans un troisième temps je décrirai les applications au dénombrement et à la génération aléatoire de permutations dans les classes régulières (c'est à dire chaque permutation de la classe a un mot de montées et de descentes appartennant à un langage régulier donné). Nous nous intéresserons particulièrement à la génération aléatoire par générateur de Boltzmann et par processus stochastique d'entropie maximal.
]
02/02/2016 Anne Bouillard Une formule de Möbius pour les groupe de traces [abstract.html
Les groupes de traces sont une généralisation des monoïdes de traces (encore appelés monoïdes partiellement commutatifs libres). Un résultat de 1969 de Carier et Foata montre l'existence d'une formule d'inversion de Möbius pour la série génératrice du monoïde de traces. Nous généralisons ce résultat aux groupes de traces, ce qui nous permettra également d'étudier la hauteur moyennes des traces.
]
02/02/2016 Gérard H. E. Duchamp Exponentielles dans l'algèbre de shuffle et transcendence
27/01/2016 Journées combinatoires de Bordeaux (27-29 janvier)
26/01/2016 Inhomogeneous Random Systems et Journées de physique statistique @ ENS (26-29 janvier)
21/01/2016 Camille Coti Exploiting Redundant Computation in Communication-Avoiding Algorithms for Algorithm-Based Fault Tolerance
21/01/2016 Bilel Sdiri Contrast enhancement method for stereo endoscopic images based on binocular just noticeable difference model
21/01/2016 Caio Filippo Corro Méthode lagrangienne pour les arborescences couvrantes avec application en traitement automatique des langues
21/01/2016 Lionel Pournin L'opération de flip dans les triangulations : du stockage de données à la topologie des surfaces
21/01/2016 Bénédicte Haas The CRT is the scaling limit of large random dissections
21/01/2016 Journée MathSTIC
19/01/2016 Journées du GDR-IM (18-20 janvier)
13/01/2016 Julien Courtiel Cordes terminales dans les diagrammes connexes de cordes [abstract.html
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 noeux, é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à.
]
12/01/2016 Gérard H. E. Duchamp Exponentielles dans l'algèbre de shuffle et transcendence
05/01/2016 CALIN Réunion d'équipe
05/01/2016 Gabriel Renault Jeux dead-ending en version misère [abstract.html
Les jeux combinatoires sont des jeux finis sans hasard à deux joueurs et à information complète. En convention normale, un joueur perd lorsqu'il ne peut plus jouer, alors que ce joueur gagnerait en convention misère. La théorie des jeux combinatoires développée par Berlekamp, Conway et Guy pour les jeux en convention normale a donné peu de résultats pour les jeux en convention misère, ce qui explique que nous étudiions ici un sous-ensemble de jeux, appelés dead-ending, dans lesquels un joueur qui ne peut pas jouer à un certain point ne pourra plus jamais jouer dans ce jeu, quelle que soit la séquence de coups jouée par son adversaire. Les jeux combinatoires peuvent être représentés par des arbres dans lesquels les fils d'un nœud représentent les positions que les joueurs peuvent atteindre depuis la position que le nœud représente. Nous étudions la somme des jeux dead-ending et utilisons ses propriétés pour réduire ses arbres, leur donnant une forme canonique et garantissant que l'inverse d'un jeu inversible est naturel.
]
05/01/2016 Collectif Bonne année + opérateurs intégraux dans le plan doublement fendu
15/12/2015 Andrea Sportiello Sur la forme limite de l'identité dans le tas de sable abélien [abstract.html
Le modèle du Tas de Sable Abélien décrit d'une façon élémentaire des processus de diffusion dans des réseaux. Des configurations de sable instables se stabilisent en des configurations stables, suite à une dynamique de avalanches. Malgré sa simplicité, ce modèle présente des phenoménes surprenents. On peut ansi considérer des configurations instables très simples à décrire, sur des réseaux réguliers, et observer le résultat à la fin de l'avalanche : on verra apparaitre des formes fractales complexes. Une de ces configurations est l'identité récurrente, Id. Quand le graphe est une portion carrée, de taille L, du réseau carré. On a donc une suite Id(L) de configurations, qui, mises à l'échelle, semblent converger vers une forme limite fractale, qui fascine les chercheurs depuis longtemps. On vient d'obtenir une description complète de cette forme. Ce résultat fait apparaitre plusieurs surprises: tous les points de contact entre les morceaux qui forment le fractal ont des coordonnées (x,y) qui appartiennent au meme corps cubique. Par exemple, le bien connu "carré bleu" qu'on trouve au milieu de la configuration est à une distance du bord de 0.58315637..., c'est à dire, la seule racine réelle de l'équation 2x^3+3x^2+x-2=0.
]
15/12/2015 Philippe Biane Gog, Magog et Schützenberger [abstract.html
Les triangles Gog et Magog sont formés d'entiers positifs satisfaisant certaines inégalités. Ils apparaissent dans de nombreuses questions d'algèbre, de combinatoire, de théorie des représentations ou de physique statistique. Je parlerai d'une approche récente, reposant sur l'involution de Schützenberger, du problème de construire des bijections explicites entre ces objets.
]
15/12/2015 Bénédicte Haas Le CRT est la limite d'échelle de grandes dissections aléatoires [abstract.html
Une dissection du polygone régulier à n côtés est la graphe formé par le polygone et certaines de ses diagonales, avec la règle que deux diagonales ne peuvent se croiser qu'aux sommets du polygone. On s'intéresse ici au comportement asymptotiquement d'une dissection uniformément distribuée dans l'ensemble des dissections du polygone à n côtés. Nous verrons que multipliée par n^(-1/2) cette dissection uniforme converge vers un multiple du CRT brownien. Ce résultat se généralise à des mesures attribuant des poids de Boltzmann aux degrés des faces des dissections, lorsque ces poids décroissent suffisamment vite. Il s'agit d'un travail en collaboration avec Nicolas Curien et Igor Kortchemski.
]
15/12/2015 Bodo Lass Polynômes symétriques et inégalités [abstract.html
Un théorème fondamental pour la théorie des égalités affirme que les polynômes symétriques élémentaires engendrent la sous-algèbre des polynômes symétriques, et sont algébriquement indépendants. Nous explorons l'utilité de ce résultat pour la théorie des inégalités.
]
15/12/2015 Tanguy Rivoal Approximants de Padé et polyzêtas [abstract.html
Peu de résultats sont connus sur la nature diophantienne des valeurs de la fonction zêta et de leurs généralisations, les polyzêtas. Une méthode générale pour parvenir à montrer l'irrationalité de tel ou tel nombre consiste à construire des approximations polynomiales, dites de Padé, de séries entières, puis à spécialiser pour obtenir des approximations numériques de ces nombres. Je présenterai diverses constructions d'approximants de Padé dans le contexte des polyzêtas. Certaines proviennent de travaux en commun avec Stéphane Fischler.
]
15/12/2015 Christian Krattenthaler Un théorème de factorisation pour le nombre des pavages en losanges d'un hexagone avec des trous triangulaires [abstract.html
Je présenterai un curieux théorème de factorisation pour le nombre des pavages en losanges d'un hexagone avec symétrie verticale et horizontale dont plusieurs trous triangulaires ont été enlevés le long de l'axe de symétrie horizontale. Je relierai ce théorème avec des autres théorèmes de factorisation, et je discuterai quelques conséquences et questions ouvertes. Ce travail a été effectué en commun avec Mihai Ciucu.

"A factorisation theorem for the number of rhombus tilings of a hexagon with trianglar holes"

I shall present a curious factorisation theorem for the number of rhombus tilings of a hexagon with vertical and horizontal symmetry axis, with triangular holes along the latter axis. I shall set this theorem in relation with other factorisation theorems, and discuss some consequences and open questions. This is joint work with Mihai Ciucu.

]
15/12/2015 Journée en l'honneur de Christian Krattenthaler
14/12/2015 Remise du doctorat honoris causa à Christian Krattenthaler
08/12/2015 Luca Lionni Colored triangulations of arbitrary dimensions are stuffed Walsh maps [abstract.html
Regular D-edge-colored graphs encode D-dimensional colored triangulations of pseudo-manifolds. We study such families of edge-colored graphs built from a finite but arbitrary set of building blocks, which extend the notion of p-angulations to arbitrary dimensions. I will introduce a bijection between any such family and some colored combinatorial maps which we call stuffed Walsh maps. Those maps generalize Walsh's representation of hypermaps as bipartite maps, by replacing the vertices which correspond to hyperedges with non-properly-edge-colored maps.

We are interested in the number of bi-chromatic cycles of the initial edge-colored graphs because because they encode the curvature of the corresponding triangulated pseudo-manifold. I will therefore present new tools that use the bijection in order to study the graphs which maximize the number of bi-chromatic cycles at fixed number of vertices and provide examples where the corresponding stuffed Walsh maps can be completely characterized.

] [arXiv]
08/12/2015 Christophe Tollu Algèbres de (Ringel-)Hall. Suivi de : Échelles de comparaison  [abstract.html
Titre : Algèbres de (Ringel-)Hall Suivi de : Échelles de comparaison et développements singuliers Résumé : Dans l’espoir de comprendre certains travaux récents de Berenstein et Rudel (« Quantum cluster characters of Hall algebras », arXiv:1308.2992 et « The Feigin tetrahedron », arXiv:1401.4338v2), en particulier la construction d’un homomorphisme, appelé « quantum shuffle character », entre le dual de l’algèbre de Ringel-Hall et l’algèbre de mélange quantique, j’étudierai l’algèbre de Ringel-Hall, en insistant sur sa structure d’algèbre de Hopf auto-duale. En deuxième partie est prévu un rapppel de ce que sont les échelles suivant des bases de filtres générales (voisinages, pointés, fendus, bases de filtre de Fréchet, complémentaires de points isolés etc...). On appliquera ces notions aux développements singuliers de P. Flajolet et A. Odlyzko. Une discussion générale sur les travaux en cours s'ensuivra.
]
03/12/2015 Séminaire Flajolet Timothy Budd, Jehanne Dousse, Yann Bugeaud
03/12/2015 Yinon Spinka Long-range order in random 3-colorings of Z^d [abstract.html
Consider a random coloring of a bounded domain in Zd with the probability of each coloring F proportional to exp(-β*N(F)), where β>0 is a parameter (representing the inverse temperature) and N(F) is the number of nea rest neighboring pairs colored by the same color. This is the anti-ferromagnetic 3-state Potts model of statistical physics, used to describe magnetic interactions in a spin system. The Kotecký conjecture is that in such a model, for d≥3 and high enough β, a sampled coloring will typically exhibit long-range order, placing the same color at most of either the even or odd vertices of the domain. We give the first rigorous proof of this fact for large d. This extends previous works of Peled and of Galvin, Kahn, Randall and Sorkin, who treated the case β=infinity. No background in statistical physics will be assumed and all terms will be explained thoroughly. Joint work with Ohad Feldheim.
]
02/12/2015 Mark Ward An overview of an analytic approach for branching processes (Colloquium : Les mercredis du LIPN) [abstract.html
One approach to solving some questions in probability theory--especially questions about asymptotic properties of algorithms and data structures--is to take an analytic approach, i.e., to utilize complex-valued methods of attack. These methods are especially useful with several types of branching processes, leader election algorithms, pattern matching in trees, data compression, etc. This talk will focus on some of the highlights of this approach. I endeavor to keep it at a level that is accessible for graduate students.
]
02/12/2015 Yinon Spinka Random 3-colorings of Z^d [abstract.html
Lattice spin systems are used in statistical physics to model various magnetic materials. I will first introduce some well-known models in this field and give a short review of known results, with an emphasis on the phenomenon of long-range order. I will then discuss a result on the existence of long-range order for random 3-coloring of Z^d in high-dimensions (joint work with Ohad Feldheim). Finally, I will also discuss a result of long-range order for the loop O(n) model on the hexagonal lattice (joint work with Hugo Duminil-Copin, Ron Peled and Wojciech Samotij). No background in statistical physics will be assumed and all terms will be explained thoroughly.
]
01/12/2015 Yinon Spinka Long-range order in lattice spin systems [abstract.html
Lattice spin systems are used in statistical physics to model various magnetic materials. I will first introduce some well-known models in this field and give a short review of known results, with an emphasis on the phenomenon of long-range order. I will then discuss a result on the existence of long-range order for random 3-coloring of Z^d in high-dimensions (joint work with Ohad Feldheim). Finally, I will also discuss a result of long-range order for the loop O(n) model on the hexagonal lattice (joint work with Hugo Duminil-Copin, Ron Peled and Wojciech Samotij). No background in statistical physics will be assumed and all terms will be explained thoroughly.
]
24/11/2015 semaine de physique combinatoire @IHP (60 ans d'Alan Sokal et de Vincent Rivasseau)
18/11/2015 Hsien-Kuei Hwang Coin Tossing in algorithmics (Colloquium : Les mercredis du LIPN) [abstract.html
Coin-tossing is one of the simplest ways of resolving a conflict, deciding between two alternatives, and generating random phenomena. It has been widely adopted in many daily-life situations and scientific disciplines. In this talk, I will present a few research themes connected to the use of coin-tossing in algorithmics, taken from my research: these include random permutations, data structures, evolutionary algorithms and leader selection. The main focus will be on the stochastic behaviors and the methods of analysis.
]
17/11/2015 Frédéric Chyzak A computer-algebra-based formal proof of the irrationality of zeta(3) [Slides.pdf] [abstract.html
We report on the formal verification of an irrationality proof of the evaluation at 3 of the Riemann zeta function. This verification uses the Coq proof assistant in conjunction with algorithmic calculations in Maple. This irrationality result was first proved by Apéry in 1978, and our formalization follows the proof path of his original presentation. The crux of it is to establish that some sequences satisfy a common recurrence. We formally prove this by an a posteriori verification of calculations performed by a Maple session. This bases on computer-algebra algorithms implementing Zeilberger's approach of creative telescoping. This experience illustrates the limits of the belief that creative telescoping can discover recurrences for holonomic sequences that are easily checked a posteriori. We discuss this observation and describe the protocol we devised in order to produce complete formal proofs of the recurrences. Beside establishing the recurrences, our proof combines the formalization of arithmetical ingredients and of some asymptotic analysis.
Joint work with Assia Mahboubi, Thomas Sibut-Pinote, and Enrico Tassi.
]
10/11/2015 Yining Hu The Flajolet-Soria formula, Furstenberg and Christol's theorems [abstract.html
Part 1: We show that the Flajolet-Soria coeffcient extraction formula for algebraic series can be deduced from a theorem of Furstenberg, with which we can prove that the formula is valid for all fields and not only for the complex field.
Part 2: We present a method of finding infinite products involving blocking counting functions in any base. This is a generalization of the work of Allouche and Shallit, where the result applies to base 2.
]
03/11/2015 Thomas Wong Enumeration Problems in Directed Walk Models [abstract.html
Self-avoiding walks appear ubiquitously in the study of linear polymers as it naturally captures their volume exclusion property. However, self-avoiding walks are very difficult to analyse with few rigourous results available. In 2008, Alvarez et al. determined numerical results for the forces induced by a self-avoiding walk in an interactive slit. These results resembled the exact results for a directed model in the same setting by Brak et al. in 2005, suggesting the physical consistency of directed walks as polymer models. Via the kernel method, we extend the directed walk model to a series of models involving two directed walks as a way to find exact enumerative results for studying the behaviour of ring polymers near an interactive wall, or walls. In the final model we considered, we are unable to find exact solutions via the kernel method. Instead, we use transfer matrices to obtain numerical results that are qualitatively similar to those presented by Alvarez et al.
]
27/10/2015 Thomas Fernique Degré algébrique des pavages [abstract.html
On s'intéresse aux pavages par carrés et losanges qui discrétisent des plans de l'espace à quatre dimensions. Plus précisément, on veut savoir lesquels peuvent être caractérisés par leurs motifs locaux. Il se trouve qu'ils correspondent à des plans définis par des entiers quadratiques (et pas plus). La généralisation aux pavages par plus de losanges reste ouverte.
]
27/10/2015 Quoc Hoan Ngo The Combinatorics of Harmonic Sums and Polylogarithms at negative integer multi-indices [abstract.pdf]
20/10/2015 Philippe Marchal Forme limite de tableaux de Young rectangulaires [abstract.html
En 2004, Pittel et Romik ont montré l'existence d'une forme limite pour les tableaux de Young rectangulaires. Je montrerai comment la méthode probabiliste des "densités", que je développe depuis quelques travaux déjà, permet de retrouver cette forme limite et donne aussi les fluctuations sur le bord : on trouve une gaussienne dans les coins et Tracy-Widom ailleurs sur le bord.
]
13/10/2015 Olivier Bodini Analyse asymptotique et génération aléatoire des structures en diamant [abstract.html
Nous allons d'écrire et étudier une classe importante de DAG, appelé structure en diamant. Cette étude repose sur une analyse asymptotique d'équations différentielles non linéaires. Nous expliquerons aussi comment développer des générateurs aléatoires efficaces pour ces structures. Travail en commun avec Hsien-Kuei Hwang, Antoine Genetrini et Xavier Fontaine.
]
13/10/2015 Gérard H. E. Duchamp Théorème de Wei-Norman (II)
09/10/2015 Stéphane Dartois Tenseurs aléatoires (soutenance de thèse) [abstract.html
During this defense I present pieces of the work I achieved on random tensor models (tensor models for short). I will define colored triangulations and then review their combinatorics. After this is done I show how one can write integral representation of their generating series. These representations are called tensor models. Using this representation I will describe the combinatorial 1/N expansion for two different kinds of models generating specific classes of colored and non-colored combinatorial maps. I will then concentrate on a specific model, that is the simpler non trivial tensor model and explore some of its properties. In particula r I review the properties of its double scaling limit, then using its Hubbard-Stratanovitch representation, I show how one can use matrix models techniques to recover results obtained using combinatorial techniques. I will finally present several results that point towards integrable structures in the framework of random tensor models.
]
06/10/2015 Pascal Vanier Calculabilité et pavages [Slides.pdf] [abstract.html
Les pavages, ou sous-shifts de type fini sont des ensembles de coloriages du plan vérifiant des contraintes locales en nombre fini. Nous nous intéresserons en particulier au problèmes d'isomorphisme entre sous-shifts, connu sous le nom de conjugaison et plus particulièrement aux invariants de conjugaison, qui sont des "objets" permettant de caractériser certains aspects des sous-shifts. Nous donnerons en particulier des caractérisations calculatoires de ces derniers qui permettront de voir les liens intimes qui lient pavages et classes de complexité/calculabilité.
]
06/10/2015 Hoang Ngoc Minh Théorème de Wei-Norman (I)
29/09/2015 pôle MathSTIC réunion axe 3 (Physique mathématique, physique statistique, combinatoire)
29/09/2015 Van Chiên Bui Harmonic sums computed at transcendence bases
23/09/2015 Sergio Caracciolo A fresh view on the matching problem [abstract.html
I will review some new results in the stochastic euclidean bipartite matching problem. First I will look at the simple one dimensional version, for which many exact results can be achieved. Afterwards, by discarding the discrete nature of the problem, as usual in a critical system, I will show how it is possible to resort to a continuous version for which an analytical expression for the minimum cost and correlation functions can be computed.
]
22/09/2015 pôle MathSTIC réunion (12h30-14h30) axe 1 (Optimisation et apprentissage appliqués aux contenus numériques)
22/09/2015 Journées du GT Combinatoire Algébrique du GDR IM
15/09/2015 AG du LIPN
15/09/2015 Gérard H. E. Duchamp About the "new" Bourbaki (2012)
08/09/2015 Michael Wallner Why and when does the half-normal distribution appear in combinatorics? [abstract.html
We present an extension of a theorem by Michael Drmota and Michèle Soria [1997] that can be used to identify the limiting distribution for a class of combinatorial schemata. This is achieved by determining analytical and algebraic properties of the associated bivariate generating function. We give sufficient conditions implying a half-normal limiting distribution, extending the known conditions leading to either a Rayleigh, a Gaussian or a convolution of the last two distributions. Finally, we present some applications to lattice path and tree enumeration, images and preimages in random mappings.
]
07/07/2015 Joshua Socolar Nonlinear dynamics and complex systems
30/06/2015 Gérard H. E. Duchamp Autour de la question : Local coordinates on (infinite dimensional) Lie groups, factorization of Riemann zeta functions
24/06/2015 Kilian Raschel Walks in the quarter plane with arbitrary big jumps
24/06/2015 Marni Mishna Uniform random generation of walks in the quarter-plane
24/06/2015 buffet combinatorico-probabiliste
24/06/2015 Grégory Schehr Statistics of the real roots of real random polynomials
24/06/2015 Anne-Laure Basdevant Dénombrement de plus longues sous-suites croissantes
24/06/2015 Accueil de la Journée MathStic "Combinatoire et probabilités"
23/06/2015 Hoang Ngoc Minh Adjunction and combinatorics of duality
16/06/2015 Aladin Virmaux Représentations de tours de monoïdes et algèbres de Hopf [abstract.html
Les monoïdes J-triviaux forment une importante famille de monoïdes dont l'étude des représentations est particulièrement combinatoire. De plus, certains exemples (la paire NCSF/Qsym est catégorifiée par les monoïdes 0-Hecke, l'algèbre de Weyl par NilHecke, etc) laissent suggérer que ce sont des candidats naturels pour catégorifier certaines algèbres de Hopf. Dans cet exposé, nous considérerons des tours de monoïdes J-triviaux et étudierons des formules générales d'induction et de restriction. Nous verrons en détail le cas des tours de semi-treillis duquel on tire des "semi-catégorifications" de certaines algèbres de Hopf (FQSym, PBT, NCSF).
]
09/06/2015 Van Chiên Bui Two q-deformations of multiple polylogarihms
02/06/2015 Katarzyna Górska Explicit forms and combinatorial content of Levy stable distributions [abstract.pdf]
02/06/2015 Quoc Hoan Ngo Multiple- polylogarithms at non-positive integers and Rota-Baxter operators  [abstract.pdf]
26/05/2015 Louis Dumont Efficient Algebraic Diagonals and Walks [Slides.pdf] [abstract.html
The diagonal of a multivariate power series F is the univariate power series Diag F generated by the diagonal terms of F. Diagonals form an important class of power series; they occur frequently in number theory, theoretical physics and enumerative combinatorics. We study algorithmic questions related to diagonals in the case where F is the Taylor expansion of a bivariate rational function. It is classical that in this case Diag F is an algebraic function. We propose an algorithm that computes an annihilating polynomial for Diag F. Generically, it is its minimal polynomial and is obtained in time quasi-linear in its size. We show that this minimal polynomial has an exponential size with respect to the degree of the input rational function. Throughout the talk, we use a common problem of counting certain lattice walks to illustrate the capacities and limits of our tools.
]
26/05/2015 Katarzyna Górska Photoluminescence decay of silicon nanocrystals and Lévy stable distributions [abstract.pdf]
21/05/2015 Dmytro Volin Quantum spectral curve and multiple zeta values (2/2) [Slides.pdf] [abstract.html
The AdS/CFT (anti-de Sitter/conformal field theory) quantum spectral curve is a tool for computing the conformal spectrum of a four-dimensional gauge theory, N=4 SYM, in the planar limit. This tool proved to be very efficient: we were able to get the explicit 10-loop perturbative results. The answer is expressed in terms of multiple zeta values. I will explain what the quantum spectral curve is and how the multiple zeta values emerge from it.
]
21/05/2015 Dmytro Volin Quantum spectral curve and multiple zeta values (1/2) [Slides.pdf] [abstract.html
The AdS/CFT (anti-de Sitter/conformal field theory) quantum spectral curve is a tool for computing the conformal spectrum of a four-dimensional gauge theory, N=4 SYM, in the planar limit. This tool proved to be very efficient: we were able to get the explicit 10-loop perturbative results. The answer is expressed in terms of multiple zeta values. I will explain what the quantum spectral curve is and how the multiple zeta values emerge from it.
] [arXiv]
20/05/2015 Journées LAGA surfaces plates (J.C. Yoccoz, A. Zorich, G. Forni)
12/05/2015 Jean-Baptiste Priez Énumération d'automates minimaux et fonctions de parking [Slides.pdf] [abstract.html
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.
] [arXiv]
12/05/2015 Mikhael Berlinkov Various aspects of automaton synchronization [Slides.pdf] [abstract.pdf]
07/05/2015 Alexandra Ugolnikova Soutenance à mi parcours : Tilings
07/05/2015 Quentin de Mourgues Soutenance à mi-parcours : A left/right dynamic on permutations [abstract.html
Soit s une permutation dans Sigma_n. Soit i(s)=s(1), j(s)=s^{-1}(1), Soit C_k le cycle 1>2>...>(k-1)>1 (k,k+1,..,n points fixes). On definit L et R comme suit: L(s) = C_{j(s)}.s et R(s) = s.C_{i(s)}^{-1} Il est facile de voir que L et R sont inversibles, la dynamique L/R partitionne donc Sigma_n en classes d'équivalence qui sont des graphes orientés uniformes (une arête entrant/sortant par "couleur" L et R) fortement connexes. Dans cet exposé, on étudiera ces classes : leur nombre, leur taille, leur structure, etc.
]
05/05/2015 Samuel Lelièvre Comptage et énumération de surfaces plates, formes quasimodulaires [Slides.pdf]
21/04/2015 Thierry Bousch La tour de Hanoï, revue par Dudeney [Slides.pdf] [abstract.html
Dans la version classique de "la Tour de Hanoï", c'est-à-dire avec trois aiguilles, on sait bien qu'on peut transférer N disques d'une aiguille vers une autre en 2^N-1 mouvements, et que ce nombre est minimal. Ajoutons une quatrième aiguille: quel est alors le nombre minimum de mouvements nécessaires pour transférer N disques d'une aiguille vers une autre? Etrangement, ce problème posé il y a plus d'un siècle par le puzzliste anglais Henry Ernest Dudeney n'a été résolu que tout récemment. Et pour d'autres variantes de la Tour de Hanoï, avec davantage d'aiguilles ou des restrictions sur les mouvements, le problème est largement ouvert. voir aussi l'article sur le site du CNRS
]
14/04/2015 Thibault Manneville Diamètre et hamiltonicité des associaèdres de graphe [Slides.pdf]
14/04/2015 Gérard H. E. Duchamp Motzkin paths and phi-shuffle
07/04/2015 Loïc Foissy Structure algébrique des opérateurs de Fliess [Slides.pdf] [arXiv] [arXiv]
07/04/2015 Quoc Hoan Ngo Soutenance de thèse à mi-parcours
07/04/2015 Van Chiên Bui Soutenance de thèse à mi-parcours
31/03/2015 Erik Aas Multi-type TASEP on a ring [abstract.html
I will give an introduction to, and describe recent research on the multi-type TASEP on a ring. This is a Markov process on permutations given by randomly sorting (cyclically) adjacent letters in the permutation at hand. The model is motivated both by physical and combinatorial considerations. The stationary distribution has a nice description in terms of the multi-line queues discovered by Ferrari and Martin.
] [arXiv]
31/03/2015 Gérard H. E. Duchamp Intégrales itérées et (indépendance linéaire des) fonctions coordonnées
24/03/2015 Gwendal Collet Automates d'arbres [Slides.pdf]
17/03/2015 Journées ALEA ALEA, au CIRM (16-20 mars)
17/03/2015 Gérard H. E. Duchamp Phi-shuffle and various combinatorial Hopf algebras II : Hunting the antipode of infiltration products (discussion)
17/03/2015 Gérard H. E. Duchamp Phi-shuffle and various combinatorial Hopf algebras I : Infiltration and evaluation of Motzkin Paths (discussion)
11/03/2015 André Katz Une histoire personnelle des pavages et quasi-cristaux [abstract.pdf] [.pdf]
11/03/2015 Cédric Boutillier Le modèle d'Ising XOR : une interprétation par les dimères bipartis [Slides.pdf]
11/03/2015 Béatrice de Tilière Le laplacien massique Z-invariant sur les graphes isoradiaux [Slides.pdf]
10/03/2015 Sébastien Labbé Une généralisation des mots de Christoffel en dimension d. [Slides.pdf] [abstract.html
In this work, we extend the definition of Christoffel words to directed subgraphs of the hypercubic lattice in arbitrary dimension that we call Christoffel graphs. Christoffel graphs when d=2 correspond to well-known Christoffel words. We show that Christoffel graphs have similar properties to those of Christoffel words: symmetry of their central part and conjugation with their reversal. Our main result extends Pirillo's theorem (characterization of Christoffel words which asserts that a word amb is a Christoffel word if and only if it is conjugate to bma) in arbitrary dimension. In the generalization, the map amb\mapsto bma is seen as a flip operation on graphs embedded in Z^d and the conjugation is a translation. We show that a fully periodic subgraph of the hypercubic lattice is a translate of its flip if and only if it is a Christoffel graph. This is joint work with Christophe Reutenauer. Preprint is available at http://arxiv.org/abs/1404.4021.
] [arXiv]
03/03/2015 Olivier Bouillot Généralisation des nombres et polynômes de Bernoulli aux cas multiples [Slides.pdf] [abstract.html
Les nombres et polynômes de Bernoulli sont des objets classiques qui apparaissent respectivement lors du prolongement analytique des fonctions zêta de Riemann et de Hurwitz aux entiers négatifs. En lien avec la généralisation multiple de ces fonctions, les multizêtas et multizêtas de Hurwitz, nous allons généraliser les nombres et polynômes de Bernoulli au cas multiple. Bien qu'il n'y a pas unicité d'une telle généralisation, nous introduirons un exemple explicite et satisfaisant où nombres de propriétés importantes des polynômes de Bernoulli se transmettent au cas multiple. Au passage, cela permet de répondre à une question sur la renormalisation des multizêtas aux entiers négatifs.
]
03/03/2015 Quoc Hoan Ngo Sommes harmoniques et polylogarithmes en les multiindices negatifs II [abstract.pdf]
03/03/2015 Gérard H. E. Duchamp Asymptotic scales, asymptotic expansions and characters
25/02/2015 Michael Drmota Quasi-random properties of subsequences of sequences generated by finite automata [abstract.html
Automatic sequences T(n) are the output sequence of a finite automaton, where the input is the q-adic digital representation of n. The most prominent example is the Thue-Morse sequence t(n) (that is also the fixed point of the substitution 0 -> 01, 1 -> 10). Automatic sequences have been studied in many diff erent contexts from combinatorics to algebra, number theory, harmonic analysis, geometry and dynamical systems. For example, they have a linear subword complexity and they are almost periodic. Since the subword complexity is linear the entropy of the related dynamical system is zero. This also means that they do not behave like a random sequence. However, the situation changes drastically when one uses proper subsequences of automatic sequences, for example the subsequence along primes or squares. It is conjectured that the resulting sequences are normal sequences so that they behave like random sequences (=quasi random sequences). Recently this property was proved (together with C. Mauduit and J. Rivat) for the Thue-Morse sequence along the subsequence of squares - and it turns out that this propery extends to several other automatic sequences and also to subsequences of the form [n^c], where 1 < c < 4/3. Thus such subsequences of automatic sequences give rise to a completely new class of pseudo random sequences that can be computed very efficiently.
]
24/02/2015 Michael Drmota Profile of random trees [Slides.pdf] [abstract.html
The purpose of this talk is to give a survey on the behaviour of the profile of three different kind of random trees, namely Galton-Watson trees, search trees and digital trees.
]
17/02/2015 Élie de Panafieu Problèmes de satisfaction de contraintes et graphes inhomogènes
17/02/2015 Quoc Hoan Ngo Sommes harmoniques et polylogarithmes en les multiindices negatifs [abstract.pdf]
10/02/2015 Gaëtan Borot Énumérer les cartes farcies de toute topologie (avec un soupçon de combinatoire analytique) [abstract.html
Les cartes sont des surfaces discrètes construites en recollant le long de leurs bords des polygônes - l'exemple le plus simple étant les triangulations. En tant que surfaces orientables, leur topologie est caractérisée par le nombre de bords n, et le nombre d'anses g. Si l'on se donne un poids de Boltzmann t_k pour chaque k-gone, l'énumération des cartes à un bord et de genre 0 est un problème très bien étudié. Ici, je considèrerai le problème plus général d'énumérer les cartes farcies: ce sont les surfaces obtenues en a) piochant dans une boîte à outils pouvant contenir des surfaces à bords polygonaux et de topologie quelconque ; b) en recollant ces morceaux élémentaires le long de leurs bords ; c) pondérant l'énumération par des poids de Boltzmann dépendant du genre et de la longueur des bords de chaque morceau élémentaire. J'expliquerai notamment qu'il existe une récurrence universelle sur la caractéristique d'Euler totale 2 - 2g - n, qui réduit le problème d'énumération en toute topologie à celui des disques (n = 1, g = 0) et des cylindres (n = 2,g = 0).
]
10/02/2015 Gérard H. E. Duchamp Polyzetas, characters and the Euler-Mascheroni constant
03/02/2015 Adrian Tanasa Graph polynomials and relations with physics [abstract.html
In the first part of the talk I will introduce the Tutte polynomial of graphs and explicitly show its relation with polynomials appearing in the so-called parametric representation of integrands canonically associated to graphs in quantum field theory. In the second part of the talk I will show a new proof of the celebrated property of universality of the Tutte polynomial of graphs (or matroids), proof which does not require the usual edge induction arguments. Finally, I will present how this proof generalizes for the universality property of the Bollobas-Riordan polynomial of ribbon graphs (or embedded graphs).
]
27/01/2015 Nada Mimouni Soutenance de thèse (AOC-RCLN)
27/01/2015 Gérard H. E. Duchamp Evolution equations in combinatorics and physics
20/01/2015 Francesco Caltagirone On convergence of Approximate Message Passing [Slides.pdf] [abstract.html
Approximate message passing is an iterative algorithm for compressed sensing and related applications. A solid theory about the performance and convergence of the algorithm exists for measurement matrices having iid entries of zero mean. However, it was observed by several authors that for more general matrices the algorithm often encounters convergence problems. In this paper we identify the reason of the non-convergence for measurement matrices with iid entries and non-zero mean in the context of Bayes optimal inference. Finally we demonstrate numerically that when the iterative update is changed from parallel to sequential the convergence is restored.
]
13/01/2015 Johan Nilsson Generalized paper-folding sequences [Slides.pdf] [abstract.pdf]
13/01/2015 Gérard H. E. Duchamp Séries de Hilbert et noyaux
06/01/2015 ANALCO 2015 / SODA 2015 (San Diego)
06/01/2015 Hoang Ngoc Minh Combinatorics of the Dyson series
16/12/2014 Hsien-Kuei Hwang Dependence and phase change in random m-ary search trees
16/12/2014 Hoang Ngoc Minh
09/12/2014 Adrian Tanasa Asymptotic expansion for random tensor models [abstract.html
Three-dimensional random tensor models are a natural generalization of the celebrated matrix models. The associated tensor graphs, or 3D maps, can be classified with respect to a particular integer or half-integer, the degree of the respective graph. 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.
] [arXiv]
09/12/2014 Christophe Tollu Idempotents de Lie et idempotents primitifs (séance interactive)
02/12/2014 Lionel Pournin Le diamètre asymptotique des associaèdres généralisés [abstract.html
Les associaèdres généralisés ont été introduits par Sergey Fomin et Andrei Zelevinsky dans le cadre de la théorie des algèbres amassées, et réalisés géométriquement par Chapoton, Fomin et Zelevinsky. Ils sont associés à n'importe quel groupe de Coxeter fini. Parmi eux figurent trois familles infinies de polytopes : les associaèdres de type A (associaèdres usuels), de type B ou C (cycloèdres), et de type D. Le diamètre asymptotique des associaèdres de types A, B (ou C), et D est maintenant connu et cet exposé passera en revue les cas des types B (ou C), et D. Les preuves ne seront pas données entièrement, mais seulement esquissées. Quelques questions associées seront finalement discutées.
]
02/12/2014 Christophe Tollu
25/11/2014 Yeong-Nan Yeh Tutte polynomial, G-parking function and sandpile [abstract.pdf]
25/11/2014 Christian Lavault Nombres généralisés de Stirling, Bessel, Touchard et Bell dans l'algèbre de Weyl méromorphe (2ème partie)
18/11/2014 Phan Dương Hiệu Cryptographie : Black-box Trace and Revoke Codes [abstract.pdf]
18/11/2014 Christian Lavault Nombres généralisés de Stirling, Bessel, Touchard et Bell dans l'algèbre de Weyl méromorphe
04/11/2014 Silvia Goodenough On the Heisenberg--Weyl algebra and related sets of Riordan subgroups
28/10/2014 Hoang Ngoc Minh (Pure) transcendence bases in phi-deformed shuffle bialgebras. Application to identify local coordinates in the group of associators. [abstract.html
Effective construction of pairs of bases in duality in the general co-commutative deformations of the shuffle co-product allow to identify the local coordinates in the group of associators leading to the ideal of homogeneous polynomial relations among polyzetas.
]
28/10/2014 Quoc Hoan Ngo
21/10/2014 Mathilde Bouvel A general theory of Wilf-equivalence for Catalan structures [abstract.html
It is a commonly observed phenomenon in enumerative combinatorics that several combinatorial classes share the same enumeration. For any two classes which seem to have the same enumeration sequence, a natural problem is to prove that it is indeed the case, ideally with a bijective proof that allows to map the structure of one class to that of the other. Such coincidences of enumeration are called Wilf-equivalences in the context of pattern-avoiding permutation classes (the definition of pattern-avoidance will be given during the talk). Wilf-equivalence has been a popular topic in the research on pattern-avoiding permutations, from its beginnings in the seventies until now. It is fair to say that most of the works done so far are specific to given pairs of equi-numerous classes, thus forming a sort of "case-by-case catalogue" of the known Wilf-equivalences. In this talk, we explore a different approach: we are interested in describing all Wilf-equivalences between permutations classes defined by the avoidance of two patterns: 231 and an additional pattern p (w.l.o.g., we can assume that p itself avoids 231). We will explain that this is one way of phrasing a seemingly more general (but actually equivalent) question: that of describing all Wilf-equivalences between classes of Catalan objects subject to one further avoidance restriction. Such classes are denoted Av(A), A being a Catalan object. Our results, to be presented in the talk, are the following. First, we define an equivalence relation ~ among Catalan objects. Our main result is that it refines Wilf-equivalence: if A ~ B, then Av(A) and Av(B) have the same enumeration. The proof is subdivided in several cases, and it is bijective in all cases but one. We further conjecture that the converse statement holds, i.e., that this relation ~ coincides with Wilf-equivalence. Then, we show how to enumerate the number of equivalence classes for ~, hereby providing an upper bound on the number of Wilf-equivalence classes. It is also interesting to study a special ~-equivalence class, which can be understood at a very fine level of details. Our results on this ~-class (called the "main" one) unify and generalize several results of the literature on Wilf-equivalence. Finally, we explain how our bijective cases in the proof of the main theorem can often be refined to provide comparison results between the enumerations of classes Av(A) and Av(B) when A and B are not equivalent for ~. A consequence is that the "main" ~-class corresponds to the largest possible enumeration sequence. This is a joint work with Michael Albert (University of Otago), and a preprint is available at arXiv:1407.8261.
] [arXiv]
21/10/2014 Valentin Féray Inclusion/exclusion cyclique [abstract.html
Dans cet exposé (au tableau), je regarderai la série génératrice multivariée des fonctions croissantes sur un ensemble ordonné donné. Le but est de décrire combinatoirement (à l'aide des diagrammes de Hasse des ensembles ordonnés) les relations entre les séries formelles obtenues. Je vais d'abord présenter le travail fondamental de Stanley sur les P-partitions qui répond, en quelque sorte, à cette question. Je donnerai ensuite une seconde réponse, à l'aide de l'opération d'inclusion-exclusion cyclique que j'ai récemment introduite.
]
14/10/2014 Gérard H. E. Duchamp Transcendence et algorithme de remplacement
14/10/2014 Van Chiên Bui Struture of polyzetas and algorithms on the bases
07/10/2014 Thierry Monteil Le langage asymptotique des courbes lisses [abstract.html
Le tracé d'une courbe sur une grille produit une suite de pixels consécutifs qui peut être représentée par un mot sur l'alphabet {droite, haut, gauche, bas}. Ce codage établit un dictionnaire entre objets géométriques (ou différentiels) et propriétés combinatoires sur les mots. Par exemple, le codage des segments de droites correspond aux mots dits 1-équilibrés, qui sont les facteurs finis des mots sturmiens. Une méthode classique pour analyser une courbe lisse discrétisée consiste à décomposer son codage en mots 1-équilibrés maximaux, qui servent alors de tangentes discrètes. Sans ajout d'hypothèses, les estimateurs de tangentes ou de courbure associés ne convergent pas nécéssairement lorsque la maille de la grille tend vers zéro. Une raison possible est la suivante : certains mots non 1-équilibrés peuvent apparaître dans le codage de courbes lisses pour des mailles arbitrairement fines. Let but de cet exposé est de décrire ce langage et voir ce qu'on peut lui faire dire.
]
07/10/2014 Séance d'organisation
30/09/2014 Joseph Ben Geloun Polynomials invariants on stranded graphs [Slides.pdf] [abstract.html
Tutte polynomial is a 2-variable polynomial defined on a graph which satisfies a contraction/deletion recurrence relation. This polynomial generalizes into the so-called Bollobas-Riordan (4-variable) polynomial for ribbon graphs which also satisfies a similar recurrence rule. In the recent Physics literature, there exists a growing interest for a new category of graphs called rank d stranded graphs. Such graphs encompass simple and ribbon graph structures and represent simplicial complexes in any dimension d. I will introduce a genuine 7-variable polynomial on these graph structures when restricted in rank 3 and when provided with a specific coloring. The polynomial satisfies a new contraction/cut rule. The procedure can be certainly extended in any rank.
] [arXiv]
30/09/2014 Lauren Williams Introduction to cluster algebras (à l'IHP)
23/09/2014 Nguyên Hoàng Nghĩa soutenance de thèse
02/07/2014 Nicolas Basset Génération aléatoire via les langages temporisés [Slides.pdf] [abstract.html
A chaque langage régulier, on associe la classe (appelée régulière) de permutations ayant un motif d'ascentes/descentes (a/d) dans ce langage régulier de {a,d}*. Par exemple, on peut définir ainsi les permutations alternantes, les permutations n’ayant pas deux descentes consécutives, les permutations ayant un nombre pair de descentes... J’expliquerai un algorithme qui étant donné un automate renvoie une formule close pour la série génératrice exponentielle de la classe régulière de permutations associée. J’expliquerai ensuite un algorithme qui permet de générer des permutations aléatoirement et de façon uniforme les permutations de même longueur de la classe régulière de permutations considérée. Les deux algorithmes sont basés sur une correspondance entre comptage de permutations et volumes de langages temporisés qui s’explique en terme de polytopes d’ordre et polytopes de chaîne de Stanley. Les deux algorithmes évoqués ci-dessus sont ainsi obtenus à partir d’algorithmes de calcul de fonction génératrice des volumes et de génération aléatoire de mots temporisé associés à un automate temporisé.
]
02/07/2014 Julien David Machines de Łukasiewicz [Slides.pdf] [abstract.html
Dans cette présentation, on s'intéressera à deux sujets a priori distincts. Le premier concerne la génération aléatoire d'arbres planaires dans lequel on maîtrise le nombre d'occurrences d'un motif d'arbre. Le but est, partant d'un motif donné, de produire automatiquement une grammaire d'arbre dans laquelle les occurrences du motif sont marqués. Cette grammaire permet directement d'obtenir un générateur aléatoire en utilisant la méthode récursive, mais permet également d'obtenir une série génératrice bivariée. Le second est une présentation d'une famille de grammaires d'arbres et des automates qui y sont associés, appelés machines de Lukasiewicz. Cette famille fut utilisé pour résoudre le premier problème. Il s'agit d'une généralisation des grammaires d'arbre régulières. Si ces grammaires et les machines associés ont des propriétés de clôtures décevantes, on a pu décrire un algorithme de minimisation pour les machines déterministes.
]
02/07/2014 Marie-Pierre Béal Systèmes sofiques-Dyck et fonctions zêtas [Slides.pdf] [abstract.html
Les systèmes dynamiques symboliques sont des suites bi-infinies de symboles dont les facteurs finis évitent un ensemble de mots finis donné. Nous présentons les systèmes appelés sofiques-Dyck. Ces systèmes sont une généralisation des systèmes Markov-Dyck introduits par Krieger et Matsumoto. Nous montrons que ces systèmes de séquences sont exactement les systèmes dont le langage des facteurs finis est un langage de mots imbriqués (nested words). Nous calculons la fonction zêta, qui compte les séquences périodiques du système, pour un système sofic-Dyck. (Travaux avec Michel Blockelet et Catalin Dima)
]
02/07/2014 CALIN Quelques résultats de "combinatoire-théorie des langages" récents ou anciens ou futurs !
02/07/2014 Gérard Duchamp Marcel-Paul Schützenberger et les monoïdes [abstract.html
Marcel-Paul Schützenberger était un fan du monoïde plaxique et aussi des monoïdes de commutation : souvenirs et réminiscences.
]
02/07/2014 journée "combinatoire et théorie des langages" à Paris 13 (et clôture de cette année de séminaires CALIN !)
01/07/2014 ANR Magnum journée ANR Magnum à Marne (9h30 Chaim Goodmann-Strauss, 11h Julien Clément, 12h discussions, 12h30 buffet, 14h30 soutenance de Sven de Félice, 16h30 pot et discussions sur Magnum) [abstract.html
Le 1er juillet aura lieu à Marne une journée de l'ANR MAGNUM, avec des exposés le matin et la soutenance de thèse de Sven De Félice l'après-midi. Voilà le programme de la journée : 9h30 Accueil, 10h Chaim Goodman-Strauss (Univ. Arkansas), 11h Julien Clément (GREYC), 12h Discussions, 12h30 Buffet, 14h30 Soutenance de thèse de Sven De Félice, 16h30 Pot de thèse et discussions sur Magnum. Cela a lieu dans la salle de séminaire 4B08R, au 4eme étage du batiment Copernic. Pour venir, descendre à la station Noisy-Champs du RER A (direction Marne-la-vallee ou Torcy) et suivre le plan : http://www.u-pem.fr/universite/presentation/plans-dacces/plan-du-campus/
]
27/06/2014 Ladji Kané Soutenance de thèse
24/06/2014 Lucas Gérin Exposants d'échelle pour un modèle (très simplifié) de percolation de premier passage
24/06/2014 Marie Théret Retour sur le théorème de forme en percolation de premier passage
24/06/2014 Jean-Christophe Mourrat Temps de survie du processus de contact sur les graphes aléatoires réguliers
24/06/2014 Olivier Garet Processus de contact en milieu aléatoire
24/06/2014 Ellen Saada Un théorème de forme asymptotique pour un modèle de propagation d'épidémie >2
24/06/2014 Journée Math-STIC (LIPN-LAGA)
17/06/2014 Conférence AofA'2014 @Jussieu, du 16 au 20 juin
10/06/2014 pôt départ à la retraite de Silvia Goodenough
10/06/2014 Christophe Tollu Grassmanniennes, positivité et positroïdes (deuxième partie, d'après A. Postnikov) [abstract.html
Les positroïdes sont des matroïdes qui sont liés à l'étude de la partie positive des variétés grassmanniennes. Ils sont depuis quelques années l'objet de nombreuses études, en combinatoire, en géométrie et même en physique. L'exposé retracera le chemin qui, des variétés grassmanniennes, a mené à leur définition. On commencera par de nombreux rappels et on s'appuiera surtout sur les travaux d'A. Postnikov.
]
03/06/2014 Christophe Tollu Grassmanniennes, positivité et positroïdes (d'après A. Postnikov) [abstract.html
Les positroïdes sont des matroïdes qui sont liés à l'étude de la partie positive des variétés grassmanniennes. Ils sont depuis quelques années l'objet de nombreuses études, en combinatoire, en géométrie et même en physique. L'exposé retracera le chemin qui, des variétés grassmanniennes, a mené à leur définition. On commencera par de nombreux rappels et on s'appuiera surtout sur les travaux d'A. Postnikov.
]
27/05/2014 Éric Fusy La fonction à deux points et à trois points pour les quadrangulations et cartes [Slides.pdf] [abstract.html
Pour une famille F de cartes planaires on appelle "fonction à k points" la série génératrice de comptage des cartes de F avec k points marqués dont les distances deux à deux sont prescrites. On sait depuis les résultats de Bouttier, Di Francesco et Guitter (s'appuyant sur une bijection de Schaeffer) que la fonction à 2 points des quadrangulations admet une expression explicite, et des réultats plus récents de Bouttier et Guitter (s'appuyant sur une bijection de Miermont) ont établi une expression explicite pour la fonction à trois points des quadrangulations. Nous passerons en revue ces résultats et montrerons comment on peut exploiter une bijection récente due à Ambjorn et Budd pour établir des expressions explicites pour les fonctions à deux points et à trois points des cartes générales. Travaux en commun avec Jérémie Bouttier et Emmanuel Guitter
]
27/05/2014 Gérard H. E. Duchamp Prolongement des fonctions holomorphes et des sommes harmoniques (séance interactive)
20/05/2014 Raoul Santachiara Conformal field theory approach: combinatorial aspects and applications in critical geometry [abstract.html
A two-dimensional system enjoys conformal symmetry when the invariance under rescaling and rotations is enhanced to invariance under any conformal (i.e. analytic and invertible) mapping. The conformal field theory (CFT) approach aims to find the solutions of the infinite set of equations imposed by conformal invariance. This approach has been successfully employed in diverse areas of physics and mathematics for almost thirty years. We will survey the basics ideas behind the CFT approach. We will adress some recent results concerning the representation of Virasoro algebras and its relations with Benjamin-Ono and Calogero-Moser integrable models. We finally show new results on conformally invariant random fractals.
]
20/05/2014 Christophe Tollu Grassmanniennes, positivité et positroïdes (d'après A. Postnikov) [abstract.html
Les positroïdes sont des matroïdes qui sont liés à l'étude de la partie positive des variétés grassmanniennes. Ils sont depuis quelques années l'objet de nombreuses études, en combinatoire, en géométrie et même en physique. L'exposé retracera le chemin qui, des variétés grassmanniennes, a mené à leur définition. On commencera par de nombreux rappels et on s'appuiera surtout sur les travaux d'A. Postnikov.
]
13/05/2014 Sihem Mesnager Objets combinatoires en cryptographie et en théorie des codes [Slides.pdf] [abstract.html
Les fonctions courbes ont été introduites par Rothaus et étudiées pour la première fois par Dillon dans sa thèse. Les fonctions courbes sont les fonctions booléennes qui sont à distance de Hamming maximale des fonctions affines. Depuis leur introduction, elles sont devenues l'un des objets les plus important en cryptographie symétrique. Une des raisons motivant leur étude est qu'il est recommandé que la fonction booléenne utilisée pour concevoir un système de chiffrement symétrique soit une fonction courbe pour pouvoir résister de manière optimale aux attaques par corrélation rapides. En plus de cette importance cryptographique, les fonctions courbes ont la propriété fascinante que leurs supports sont des objets combinatoires intéressants. Leurs supports forment des ensembles à différence, appelés ensembles à différence de Hadamard. Parmi les familles de fonctions courbes, il en est une qui pourrait avoir une importance grandissante dans les années à venir : les fonctions hyper-courbes (introduites par Youssef et Gong en 2001). Les fonctions hyper-courbes sont des fonctions courbes qui ont la propriété d'être aussi à distance maximale des permutations polynomiales. Très récemment, il a été mis en lumière que ces fonctions étaient en relation étroite avec des objets géométriques intéressants: les hyperovales. Dans cet exposé, nous présenterons un résumé des résultats les plus importants et de nos apports à l'étude des fonctions booléennes courbes en illustrant les liens possibles entre les fonctions courbes et des objets combinatoires et géométriques cités précédemment. Nous présenterons aussi le lien entre les fonctions courbes et la théorie des codes et plus particulièrement entre certaines fonctions vectorielles courbes et les codes minimaux (dont les propriétés combinatoires peuvent être exploitées par les systèmes de partage de secret).
]
13/05/2014 Van Chiên Bui Studying construction of polyzetas
06/05/2014 Lionel Pournin Sur les diamètres de certains graphes de flips [abstract.html
Considérons une surface orientable S de genre g avec k>0 bords. Plaçons un ensemble E de n points sur S de manière que chaque bord contienne au moins un de ces points. Le graphe des flips de E est le graphe G dont les sommets sont les triangulations de E et dont les arêtes joignent deux triangulations qui peuvent être transformées l'une en l'autre par un flip (cette opération consiste à échanger les diagonales d'un quadrilatère). Le graphe G est connexe. Si on considère les triangulations de E à homéomorphisme près, les sommets de E étant marqués, le diamètre de ce graphe est borné. Lorsque S est un disque dont le bord contient tous les points de E, G est le graphe de l'associaèdre de dimension n-3. Il a été montré récemment que le diamètre de ce graphe est 2n-10 dès que n est supérieur à 12. La preuve de ce résultat sera esquissée. Plusieurs autres résultats sur le diamètre de G seront ensuite donnés et discutés dans le cas où S n'est pas un disque.
]
06/05/2014 Quoc Hoan Ngo A scheme of noncommutative combinatorial number theory and physics [abstract.pdf]
29/04/2014 exposés ANR Magnum à P6: O. Bodini & A. Sportiello
15/04/2014 Ha Duong Phan Some algebraic structures on chip firing game [abstract.html
The chip firing game is a discrete dynamical model on graphs which was first defined by D. Dhar (1990) and by A. Björner, L. Lovász and W. Shor (1991). The model has various applications in many fields of science such as physics, computer science, social science and mathematics. Recently, this model is used as a tool to study many properties of graphs and it was proved to be related to subjects of graph theory, such as Laplacian matrix, Tutte polynomial, spanning tree or graphic matroid, etc. In this talk, I will present some algebraic structure raised on this model.
]
15/04/2014 Ladji Kane Factorisations tangentes à l'identité
08/04/2014 Gleb Koshevoy A Hopf algebra structure on positroids
08/04/2014 Réunion des CS pour audition MdC et Prof
01/04/2014 Srecko Brlek Sur la structure palindromique des mots [Slides.pdf] [abstract.html
En combinatoire des mots finis ou infinis, la nature des motifs qui apparaissent dans un mot donné sont une des nombreuses manières de déterminer sa complexité. Les calculs de diverses statistiques permettent de mettre en évidence certaines relations qu'il vérifie.
]
01/04/2014 Alice Jacquot Soutenance de thèse
25/03/2014 Irène Marcovici Autour des automates cellulaires probabilistes [abstract.html
Un automate cellulaire probabiliste (ACP) est une chaîne de Markov sur un espace symbolique. Le temps est discret, les cellules évoluent de manière synchrone, et le nouvel état de chaque cellule est choisi de manière aléatoire, indépendamment des autres cellules, selon une distribution déterminée par les états d'un nombre fini de cellules situées dans le voisinage. Je présenterai les résultats obtenus au cours de ma thèse sur deux "problèmes inverses" : le premier consiste à étudier les ACP ayant des mesures invariantes de forme produit de Bernoulli ; le second est le problème de la classification de la densité, qui consiste à trouver un AC(P) dont l'évolution permette de distinguer une configuration initiale sur l'alphabet binaire tirée selon une mesure de Bernoulli de paramètre inférieur ou supérieur à 1/2, et que nous avons résolu sur les grilles de dimension supérieure ou égale à 2 et sur les arbres.
]
25/03/2014 Wojciech Mlotkowski Noncommutative probability III : Free infinite divisibility
18/03/2014 Journées ALEA (17-21 mars)
18/03/2014 Ladji Kane Combinatoire des q-déformations de la base de Poincaré-Birkhoff-Witt-Lyndon (2/2) [abstract.html
Soit S_w^{(q)} une base construit avec la même relation de réccurence et avec la même condition iniatiale que la base S_w. Soit P_w^{(q)} la base duale de la base S_w^{(q)}. Nous allons montrer qu'une q-déformation de la base de Poincaré-Birkhoff-Witt-Lyndon P_w^{(q)} est aussi multiplicative. Cette deuxième séance sera consacrée à l'examen fin des stastistiques sur le groupe symétrique induite par la q-shuffle et au conditions suffisantes de multiplicativité des bases.
]
18/03/2014 Wojciech Mlotkowski Noncommutative probability II : Free additive and multiplicative convolutions [Slides.pdf]
11/03/2014 Matthieu Deneufchâtel Convolution de Dirichlet et énumération de pyramides et espaliers [Slides.pdf] [abstract.html
Nous étudions l’énumération de deux familles de polycubes, les pyramides et les espaliers, en lien avec une version multi-indexée de la convolution de Dirichlet.
]
11/03/2014 Wojciech Mlotkowski Noncommutative probability I : Noncrossing partitions and free cumulants [Slides.pdf]
04/03/2014 Moon Duchin Rationality of growth in the Heisenberg groups [abstract.html
I'll discuss the history of work on the question of how and whether rationality of growth depends on generators. That is, for a finitely generated group, one can study the growth function (the number of words spellable in up to n letters) and its growth series, the associated generating function. This growth series is itself a rational function when there is a recursive relationship among the values of the growth function. It is known that all virtually abelian groups and all hyperbolic groups have rational growth in any generators, by work of Benson and Cannon respectively. Work of Shapiro and of Stoll sheds some light on the situation in nilpotent groups, but shows it to be more complicated-- even for the second Heisenberg group H_5, some generators give rational growth but others do not. I'll describe work in progress with Shapiro giving geometric arguments to establish rationality in all generators for the classical Heisenberg group H_3.
]
04/03/2014 Wojciech Mlotkowski Free product of representations
04/03/2014 Ladji Kane Combinatoire des q-déformations de la base de Poincaré-Birkhoff-Witt-Lyndon (1/2) [abstract.html
Soit S_w^{(q)} une base construite avec la même relation de réccurence et avec la même condition iniatiale que la base S_w, mais en utilisant une déformation du shuffle. Soit P_w^{(q)} la base duale de la base S_w^{(q)}. Nous allons proposer une démonstration du fait que cette q-déformation de la base de Poincaré-Birkhoff-Witt-Lyndon P_w^{(q)} est aussi multiplicative.
]
25/02/2014 Quentin de Mourgues A left/right dynamic on permutations [abstract.html
Soit s une permutation dans Sigma_n. Soit i(s)=s(1), j(s)=s^{-1}(1), Soit C_k le cycle 1>2>...>(k-1)>1 (k,k+1,..,n points fixes). On definit L et R comme suit: L(s) = C_{j(s)}.s et R(s) = s.C_{i(s)}^{-1} Il est facile de voir que L et R sont inversibles, la dynamique L/R partitionne donc Sigma_n en classes d'équivalence qui sont des graphes orientés uniformes (une arête entrant/sortant par "couleur" L et R) fortement connexes. Dans cet exposé, on étudiera ces classes : leur nombre, leur taille, leur structure, etc.
]
25/02/2014 Gleb Koshevoy Cluster fans [abstract.html
One of the main motivation of S.Fomin and A.Zelevinsky for introducing cluster algebras was the desire to provide a combinatorial framework to understand the structure of ''dual canonical bases'' in coordinate rings of various algebraic varieties related to semisimple groups. For a finite cluster algebra, they show that the cluster complex can be implemented as a simplical fan in the vector space span by the simple roots of the corresponding Lie algebra. We show that the cluster complex for cluster algebra of the base affine space for GL(n) can be implemented as a simplicial fan in the space span by interval one-column semistandard Young tableaux filled in the alphabet {1,...,n}. For n>6, such a fan contains infinitely many cones and its support covers semistandard Young tableaux corresponding to real elements of the dual canonical basis. For types ADE, cluster complexes of the corresponding finite cluster algebras are subfans of our cluster complex with appropriate n's.
]
18/02/2014 Christophe Tollu Algèbres PSH d'après A. Zelevinsky II [abstract.html
Les algèbres PSH sont des algèbres de Hopf (sur les rationnels ou les réels) autoduales qui ont une base pour laquelle les constantes de structures sont positives. Le premier exposé sera consacré à quelques résultats de structure, et le deuxième à l'usage que Zelevinsky a fait de ces algèbres en théorie des représentations.
]
12/02/2014 Journées Combinatoires de Bordeaux (12-14 février 2014)
12/02/2014 Journées Holonomes (12-14 février 2014)
11/02/2014 Michele Pagani Petit voyage autour des sémantiques quantitatives de la logique linéaire [abstract.html
Une sémantique dénotationelle interprète les types de données (comme Bool ou Int) par des espaces mathématiques (posets, treillis, structures algébriques) et les programmes par des fonctions sur ces espaces. L'intérêt d'une telle interprétation étant de donner une description du comportement opérationnel des programmes qui fait abstraction du langage dans lequel les programmes sont écrits. Les sémantiques quantitatives sont en particulier les sémantiques dénotationelles issues de la logique linéaire, où les types de données sont interprétés par des espaces vectoriels (ou, plus généralement, des modules), les programmes qui utilisent exactement une fois leurs données d'entrée deviennent des fonctions linéaires (au sens algébrique), alors que les programmes qui utilisent leurs ressources un nombre indéterminé de fois (comme les programmes récursifs ou les programmes utilisant l'instruction while, par exemple) sont interprétés par des fonctions analytiques, approximables par des polynômes, qui représentent des calculs partiels. Ces sémantiques sont particulièrement naturels pour décrire des programmes non-déterministes, voire probabilistes ou quantiques, l'addition exprimant une sorte de superposition des états élémentaires et les scalaires associant une estimation quantitative à une telle superposition. Dans cet exposé, je chercherai à donner une intuition de l'interprétation des programmes via quelques exemples de sémantiques quantitatives et à donner un aperçu des résultats récemment obtenus, en particulier dans le cadre des langages fonctionnels probabilistes.
]
11/02/2014 Christophe Tollu Algèbres PSH d'après A. Zelevinsky I [abstract.html
Les algèbres PSH sont des algèbres de Hopf (sur les rationnels ou les réels) autoduales qui ont une base pour laquelle les constantes de structures sont positives. Le premier exposé sera consacré à quelques résultats de structure, et le deuxième à l'usage que Zelevinsky a fait de ces algèbres en théorie des représentations.
]
04/02/2014 Gérard H. E. Duchamp A lemma about angular independence (Discussion)
28/01/2014 Adeline Pierrot Combinatoire et algorithmique dans les classes de permutations [abstract.html
Cet exposé donnera un aperçu du domaine de recherche accessible et dynamique des permutations à motifs exclus, tout en illustrant dans ce cadre les interactions fructueuses existantes entre combinatoire et algorithmique. Un outil clé présenté sera la décomposition par substitution des permutations, qui est un exemple de décomposition récursive d'objets discrets utile tant sur le plan combinatoire qu'algorithmique, et qui fait partie du même cadre général que la décomposition modulaire des graphes. Une telle décomposition permet de mettre en évidence la structure des objets étudiés, et de l'exploiter afin d'obtenir des résultats de nature énumérative, des algorithmes de génération aléatoire, ou des algorithmes de décision.
]
28/01/2014 Hoang Ngoc Minh Un petit retour sur le prolongement analytique des polylogarithmes [abstract.html
La repr\'esentation int\'egrale des polylogarithmes, pour $|z|<1$, $$\Li_{s_1,\ldots,s_r}(z)= \sum_{n_1>\ldots>n_r}\frac{z^{n_1}}{n_1^{s_1}\ldots n_r^{s_r}}, $$ permet de le prolonger analytiquement sur $\C^r$. Aux entiers n\'egatifs, ils sont devenus des fonctions rationnelles en $z$ $$ \Li_{-s_1,\ldots,-s_r}(z)=\sum_{n_1>\ldots>n_r} n_1^{s_1}\ldots n_r^{s_r} z^{n_1}\in\C[z,1/z,1/(1-z)] $$ dont le d\'eveloppement de Laurent, en $z=1$, conduisent aux poly-Bernoulli.
]
21/01/2014 Valentin Bonzom Gaussian expectations in random tensor theory from meanders and stabilized-interval-free permutations [abstract.html
Je m'intéresse à l'espérance de polynômes en des variables aléatoires tensorielles distribuées selon une gaussienne. Je présenterai brièvement une famille de polynômes dont les espérances comptent des nombres de systèmes de méandres, puis je discuterai en détail cette famille de méandres. Un méandre étant vu comme un collage de deux systèmes d'arches, il s'agit ici de méandres étiquetés par une permutation qui détermine un système d'arches à partir de l'autre. Je montrerai que le nombre de méandres étiquetés par une permutation donnée se décomposent naturellement en méandres irréductibles, étiquetés par des permutations qui ne stabilisent aucun sous-interval (Stabilized-Interval-Free permutations).
]
21/01/2014 Gleb Koshevoy Cluster algebras and subtraction-free computing [abstract.html
Using cluster transformations we design subtraction-free algorithms for computing Schur functions and their skew, double and supersymemtric analogues, for generating spanning trees and arborescences polynomials. The latter provides an exponential complexity gap between circuits admitting arithmetic operations +, x, / versus +, x. In addition, we establish an exponential complexity gap between circuits admitting +, -, x, / versus +, x, /. Together with V. Strassen's result on "Vermeidung von Divisionen" this closes a long-standing problem on comparative complexity power between all possible subsets of operations +, -, x, /. (a joint work with S. Fomin and D. Grigoriev)
]
21/01/2014 Olivier Bouillot Sur la notion de polynômes de Bernoulli multiple [abstract.pdf]
14/01/2014 Olivier Mallet Convolution de Dirichlet et énumération de pyramides [abstract.html
Dans cet exposé, on introduit deux familles de polycubes : les pyramides et les espaliers. On calcule les séries génératrices ordinaire et de Dirichlet de ces objets à l'aide d'une version multi-indexée de la convolution de Dirichlet. On s'intéresse ensuite à une généralisation des pyramides et des espaliers en dimension d quelconque et on montre que le nombre de pyramides de volume fixé en dimension d+1 est un polynôme en d. On explique enfin comment appliquer les techniques mises en œuvre ici à d'autres familles de polycubes.
]
14/01/2014 Ladji Kane Combinatoire des q-déformations de la base de Poincaré-Birkhoff-Witt-Lyndon [abstract.html
Soit Sw(q) une base construite avec la même relation de récurrence et avec la même condition initiale que la base Sw. Soit Pw(q) la base duale de la base Sw(q). Nous allons montrer que cette q-déformation de la base de Poincaré-Birkhoff-Witt-Lyndon Pw(q) est aussi multiplicative.
]
07/01/2014 Pierre-Étienne Meunier Pavages auto-assemblants avec et sans coopération [abstract.html
Les pavages auto-assemblants sont un modèle de formation de structures moléculaires, dans lequel on peut simuler des machines de Turing. Il s'agit essentiellement d'une modification des tuiles de Wang, où l'on rajoute un mécanisme de formation des pavages. Je présenterai dans cet exposé deux résultats de séparation entre deux variantes de ce modèle : le modèle coopératif, où certaines tuiles ne peuvent s'assembler avec le reste du pavage que si plusieurs de leurs côtés correspondent, et le modèle non-coopératif, où toutes les tuiles peuvent s'assembler si au moins un de leurs côtés correspond.
]
17/12/2013 Christophe Tollu Algèbre de Hopf de Zelevinsky
10/12/2013 Nicolas Curien Sur la structure conforme des cartes planaires aléatoires [abstract.html
Une triangulation est un graphe (planaire, fini connexe) dessiné proprement dans la sphère de dimension 2 dont toutes les faces sont des triangles. On considère une triangulation aléatoire T_n choisie uniformément dans l'ensemble de toutes les triangulations à n faces. La structure métrique de T_n munie de la distance de graphe a été étudiée en profondeur récemment. En particulier, Le Gall (voir aussi Miermont) a prouvé que T_n renormalisée par n^{-1/4} converge vers une surface aléatoire fractale appelée la carte brownienne. Dans cet exposé nous nous intéresserons à un autre aspect des triangulations aléatoires. En effet, $T_n$ peut naturellement être munie d'une structure de surface de Riemann et l'on peut ainsi étudier sa "structure conforme" qui est censée être très liée au champs libre gaussien en dimension 2. Je présenterai un chemin pour l'étude de cette structure conforme fondé sur l'exploration markovienne des cartes planaires à l'aide d'un processus SLE_6.
]
10/12/2013 Guillaume Chapuy Diamant aztèque, pyramides, et pavages pentus de Z^2 [abstract.html
Je parlerai de modèles de pavages par dominos de certaines régions du plan que nous appelons les «pavages pentus». Ces modèles contiennent plusieurs classes de pavages pour lesquelles des propriétés remarquables (énumératives et probabilistes) avaient été obtenues, notamment le «diamant aztèque» et les «partitions pyramides». Nous élucidons leur structure combinatoire en les mettant en correspondance avec des suites de partitions entrelacées, faisant ainsi le lien avec les «processus de Schur» introduits par Okounkov et Reshetikhin. La méthode permet non seulement une compréhension unifiée des formules d'énumération, et leur généralisation à une famille infinie de modèles, mais également le calcul de fonctions de corrélation entre particules, ouvrant potentiellement la voie à l'étude unifiée des formes limites (théorèmes de type «cercle arctique»). Notre point de vue conduit par ailleurs à des algorithmes plaisants de génération aléatoire. L'exposé contiendra de nombreuses illustrations et peut-être même une applet java. Aucun pré-requis n'est nécessaire. (Travail commun avec Jérémie Bouttier et Sylvie Corteel)
]
10/12/2013 Christian Houdré Comportements asymptotiques dans quelques problèmes de sous-suites communes et/ou croissantes [abstract.html
Cet exposé présentera un panorama partiel et quelques résultats récents sur le comportement asymptotique (moyenne, variance, lois limites) dans certains problèmes de plus longue sous-suite croissante et/ou commune.
]
10/12/2013 Olivier Hénard Autour des arbres de coalescence [abstract.html
Les arbres de coalescence utilisés en phylogénétique sont naturellement construits depuis les feuilles. Nous posons la question d'une description de ces arbres depuis la racine. Parmi les arbres de coalescence, les Beta coalescents constituent une classe d'étude favorite, et des liens récents avec certaines classes d'arbres combinatoires (arbres récursifs et arbres binaires) ont récemment permis d'en améliorer la compréhension. Nous commencerons par rappeler ces constructions alternatives, dues respectivement à Goldschmidt et Martin, et Abraham et Delmas. Nous présenterons ensuite notre propre contribution, basée sur la représentation dite "lookdown".
]
10/12/2013 Journée Math-STIC/BQR Marmots :
04/12/2013 Uno Takeaki A New Approach to String Pattern Mining with Approximate Match [abstract.html
Frequent string mining is the problem of finding frequently appearing strings in a given string database or large text. It has many applications to string data analysis on strings such as texts, word sequences, and genome sequences. The problem becomes difficult if the string patterns are allowed to match approximately, i.e., a fixed number of errors leads to an explosion in the number of small solutions, and a fixed ratio of errors violates the monotonicity that disables hill climbing algorithms, and thus makes searching difficult. There would be also a difficulty on the modeling of the problem; simple mathematical definitions would result explosion of the solutions. To solve this difficulty, we go back to the motivations to find frequent strings, and propose a new method for generating string patterns that appear in the input string many times. In the method, we first compute the similarity between the strings in the database, and enumerate clusters generated by similarity. We then compute representative strings for each cluster, and the representatives are our frequent strings. Further, by taking majority votes, we extend the obtained representatives to obtain long frequent strings. The computational experiments we performed show the efficiency of both our model and algorithm; we were able to find many string patterns appearing many times in the data, and that were long but not particularly numerous. The computation time of our method is practically short, such as 20 minutes even for a genomic sequence of 100 millions of letters.
]
03/12/2013 Uno Takeaki Efficient Algorithms for Dualizing Large-Scale Hypergraphs [abstract.html
A hypergraph F is a set family defined on vertex set V. The dual of F is the set of minimal subsets H of V such that J \cap H \ne \emptyset for any J in F The computation of the dual is equivalent to many problems, such as minimal hitting set enumeration of a subset family, minimal set cover enumeration, and the enumeration of hypergraph transversals. In this paper, we introduce a new set system induced by the minimality condition of the hitting sets, that enables us to use efficient pruning methods. We further propose an efficient algorithm for checking the minimality, that enables us to construct time efficient and polynomial space dualization algorithms. The computational experiments show that our algorithms are quite fast even for large-scale input for which existing algorithms do not terminate in practical time.
]
03/12/2013 Ladji Kane Combinatoire du q-shuffle
03/12/2013 Quoc Hoan Ngo Lyndon words, polylogarithm functions and the Riemann zeta functions
19/11/2013 Emily Redelmeier Cartography on unoriented surfaces, with applications to real and quaternionic random matrices [Slides.pdf] [abstract.html
I will discuss the cartographic machinery (encoding of maps on surfaces by permutations) on unoriented surfaces. I will discuss how these appear in calculations with real and quaternionic random matrices, and their connections with other combinatorial objects associated with these objects, such as the hyperoctahedral group and matricial cumulants. I will present some results in asymptotic second-order freeness which may be approached using these objects.
]
19/11/2013 Gérard H. E. Duchamp Infiltration I
14/11/2013 James Ryan Melons are branched polymers [Slides.pdf] [abstract.html
Melonic graphs constitute the family of graphs arising at leading order in the 1/N expansion of tensor models. They were shown to lead to a continuum phase, reminiscent of branched polymers. We show here that they are in fact precisely branched polymers, that is, they possess Hausdorff dimension 2 and spectral dimension 4/3.
]
14/11/2013 Matti Raasakka Next-to-leading order in the large N expansion of the multi-orientable tensor model [Slides.pdf] [abstract.html
After providing some background and motivation for random tensor models and their large N expansion, I will discuss recent results on the next-to-leading order of the large N expansion for the multi-orientable tensor model. I will describe the class of Feynman tensor graphs contributing to this order in the expansion, and the characteristic properties of the next-to-leading order series for this model. These results represent the first step towards the larger goal of defining an appropriate double-scaling limit for the multi-orientable tensor model.
]
14/11/2013 Gilles Schaeffer Regular colored graphs of positive degree [Slides.pdf] [abstract.html
Regular colored graphs are dual representations of pure colored D-dimensional complexes. These graphs can be classified with respect to an integer, their degree, much like maps are characterized by the genus. We analyse the structure of regular colored graphs of fixed positive degree and perform their exact and asymptotic enumeration. In particular we show that the generating function of the family of graphs of fixed degree is an algebraic series with a positive radius of convergence, independant of the degree. We describe the singular behavior of this series near its dominant singularity, and use the results to establish the double scaling limit of colored tensor models.
]
14/11/2013 Vincent Vargas Critical and dual Gaussian multiplicative chaos [Slides.pdf] [abstract.html
The theory of Gaussian multiplicative chaos enables to make sense of random measures defined formally by the exponential of a Gaussian Free Field (and more generally any logarithmically correlated field in all dimensions). These random measures are conjectured to be the scaling limit of random planar maps coupled to a CFT and conformally mapped to the sphere or the upper half plane. The construction of the measures involve a parameter gamma related to the central charge c of the CFT. The classical construction does not settle the question of constructing the measure for c=1 or equivalently gamma=2 as it yields a vanishing measure. In this talk, I will explain the appropriate construction and some properties of Gaussian multiplicative chaos at criticality, i.e. for gamma=2. If time permits, I will also explain the construction of the dual measure (gamma larger than 2) and how to make sense of the KPZ equation in this context.
]
14/11/2013 Omid Amini Coloriage des graphes sur les surfaces [abstract.html
Je commencerai par introduire le concept de S-coloriage de graphe : étant donné un sous-ensemble S(v) de voisins de v pour tout sommet v d'un graphe G, c'est un coloriage propre des sommets de G tel que, en outre, les sommets qui appartiennent ensemble à un même S(v) pour un sommet v reçoivent des couleurs différentes. Ceci généralise à la fois le concept de coloriage du carré de graphe et le coloriage cyclique des graphes plongés.
Je présenterai un résultat structurel fort pour les graphes plongés dans une surface fixe, qui permet par exemple de démontrer que la taille maximum d'une clique dans le carré d'un tel graphe de degré maximum D est au plus 3D / 2 plus une constante.
En utilisant ce résultat de structure, le S-coloriage d'un graphe plongé peut se réduire au coloriage d'arêtes d'un multigraphe. Je donnerai ensuite un aperçu général du travail de Jeff Kahn sur arête-coloriage d'un multigraphe H, basé sur l'utilisation des distributions hardcores sur les couplages, définies par des points à l’intérieur du polytope des couplages de H.
En combinant ces résultats, on peut établir un résultat général sur le S-coloriage des graphes plongés, impliquant notamment les versions asymptotiques des conjectures de Wegner et de Borodin sur le coloriage du carré et le coloriage cyclique des graphes planaires. Mon exposé est basé sur un travail en commun avec L. Esperet et J. van den Heuvel.
]
14/11/2013 Journée "cartes combinatoires" (PEPS "Cartes 3D" et BQR P13 "Combinatoire algébrique") :
12/11/2013 Jérémie Bouttier Distances in random planar maps and discrete integrability [Slides.pdf] [abstract.html
Metric properties of random maps (graphs embedded in surfaces) have been subject to a lot of recent interest. In this talk, I will review a combinatorial approach to these questions, which exploits bijections between maps and some labeled trees. Thanks to an unexpected phenomenon of ``discrete integrability'', it is possible to enumerate exactly maps with two or three points at prescribed distances, and more. I will then discuss probabilistic applications to the study of the Brownian map (obtained as the scaling limit of random planar maps) and of uniform infinite planar maps (obtained as local limits). If time allows, I will also explain the combinatorial origin of discrete integrability, related to the continued fraction expansion of the so-called resolvent of the one-matrix model. Based on joint works with E. Guitter and P. Di Francesco.
]
12/11/2013 Hoang Ngoc Minh Mathematical renormalization in quantum electrodynamics via noncommutative generating series [Slides.pdf] [abstract.html
We are focusing on the approach by noncommutative formal power series in order to study combinatorial aspects of the renormalization of solutions of nonlinear differential equations with three regular singularities involved in QED (quantum electrodynamics).
]
05/11/2013 Vincent Pilaud Associaèdres d'arbres signés [abstract.html
Un associaèdre est un polytope dont les sommets correspondent aux triangulations d'un polygone convexe et dont les arêtes correspondent aux flips entre ces triangulations. J.-L. Loday en a donné une réalisation particulièrement élégante qui a été généralisée ensuite dans deux directions : d'un côté par C. Hohlweg et C. Lange pour obtenir de multiples réalisations de l'associaèdre paramétrées par une séquence de signes, et de l'autre par A. Postnikov pour obtenir une réalisation des associaèdres de graphes de M. Carr et S. Devadoss. Le but de cet exposé est de présenter une généralisation commune de ces constructions aux associaèdres d'arbres signés. Nous présenterons aussi les riches propriétés combinatoires et géométriques des polytopes qui en résultent. L'exposé sera illustré par le cas de l'associaèdre classique, dont l'interprétation en termes d'épine dorsale (arXiv:1307.4391, travail en commun avec C. Lange) est le fil directeur de ce travail.
]
05/11/2013 Collectif Discussion informelle sur Schur et les fonctions symétriques
29/10/2013 Bernhard Gittenberger Random Boolean functions generated by random Boolean expressions [Slides.pdf] [abstract.html
We will investigate the probability distribution on the set of Boolean functions in n variables if a Boolean function is generated by a large Boolean expression drawn uniformly at random from all expressions of the same size. We show that a precise quantitative relation between the probability of a function and its complexity which is defined as the minimal size of an expression representing the function.
]
22/10/2013 ALEA in Europe School
22/10/2013 Séance à la mémoire d'Alain Lascoux [abstract.html
Une bien triste nouvelle, ce 19 octobre, Alain Lascoux nous a quitté. Formé comme un spécialiste de géométrie algébrique, puis collaborateur de Marcel-Paul Schützenberger, il avait consacré toute sa vie de chercheur à mettre au jour et à exploiter algorithmiquement les aspects combinatoires de certaines questions d'algèbre, de théorie des représentations et de géométrie. Plusieurs membres de l'équipe l'ont longuement côtoyé, à Jussieu, à Marne-la-Vallée ou pendant les réunions semestrielles du Séminaire Lotharingien de Combinatoire ; nous ne pouvons que dire que samedi dernier, la combinatoire algébrique a perdu un de ses maîtres, et avec lui un peu de ses couleurs et de son mordant. Nous dédions notre traditionnelle séance du séminaire de l'équipe CALIN (dont Alain fut l'un des parrains scientifiques) à sa mémoire.
]
15/10/2013 Jeremy Lovejoy Le rang d'une suite unimodale et fonctions theta partielles [abstract.html
Il existe des égalités inattendues autour du rang d'une suite unimodale, telle que U(1,5,5n+3) = U(2,5,5n+3), où U(t,m,n) est le nombre de suites unimodales de poids n avec rang congru à t modulo m. De telles égalités rappellent celles pour le rang d'une partition qui ont été observées par F. Dyson et qui sont liées aux formes modulaires et mock modulaires. Dans le cas des suites unimodales, il n'y a pas cette structure modulaire ; la démonstration dépend d'une identité de fonctions thêta partielles due à Ramanujan. Ceci est un travail en commun avec B. Kim (Séoul).
]
15/10/2013 Nguyên Hoàng Nghĩa Structure constants and freeness
08/10/2013 Olivier Carton Normalité et automates [Slides.pdf] [abstract.html
We strengthen the theorem that establishes that deterministic finite transducers can not compress normal infinite words. We prove that, indeed, non-deterministic finite transducers, even augmented with a fixed number of counters, can not compress normal infinite words. However, there are push-down non-deterministic transducers that can compress normal infinite words. We also obtain new results on the preservation of normality with automata selectors. Complementing Agafonov's theorem for prefix selectors, we show that suffix selectors also preserve normality. However, there are simple two-sided selectors that do not preserve normality.
]
08/10/2013 Collectif Réunion de programme et lissage du phi-shuffle (2ème partie) [arXiv]
01/10/2013 Nicolas Thiéry Étude de chaînes de Markov à l'aide de représentations de monoïdes [abstract.html
Étude de chaînes de Markov à l'aide de représentations de monoïdes

La théorie des représentations des groupes finis est un sujet classique. Dans le cadre plus général des monoïdes finis, la théorie est plus récente et a priori plus complexe. Cependant il existe des classes de monoïdes où, comme pour les groupes, la théorie se simplifie et fait surgir de la combinatoire, ce qui ouvre la porte à des applications.

Dans cet exposé, nous présenterons brièvement les éléments de la théorie en mentionnant quelques développements algorithmiques récents [1], et décriront une application typique à l'étude d'une chaîne de Markov sur des tas de sable à écoulement orienté [2]. La démarche exploratoire sera illustrée par quelques calculs typiques avec le logiciel Sage.

Refs:
- [1] Cartan invariant matrices for finite monoids
http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewArticle/dmAR0178
- [2] arXiv:1305.1697: Directed nonabelian sandpile models on trees
Ayyer, Schilling, Steinberg, T.

] [arXiv]
01/10/2013 Collectif Réunion de programme et lissage du phi-shuffle [arXiv]
24/09/2013 Matti Raasakka Connes-Kreimer combinatorial Hopf algebra for the Ben Geloun-Rivasseau tensor field model [abstract.html
The Ben Geloun-Rivasseau quantum field theoretical model is the first tensor model shown to be perturbatively renormalizable. We define here an appropriate Hopf algebra describing the combinatorics of this new tensorial renormalization. The structure we propose is significantly different from the previously defined Connes-Kreimer combinatorial Hopf algebras due to the involved combinatorial and topological properties of the tensorial Feynman graphs. In particular, the 2- and 4-point function insertions must be defined to be non-trivial only if the superficial divergence degree of the associated Feynman integral is conserved.
]
24/09/2013 Bérénice Oger Action of the symmetric groups on the homology of the hypertree posets [abstract.html
The set of hypertrees on n vertices can be endowed with a poset structure. This poset has been used by McCammond and Meier to study the group of motions of the trivial link, which is an analogue of the braid group. They also proved that this poset is Cohen-Macaulay and computed the dimension of its only homology group. After a short introduction on this topological context, we explain how we used the theory of species to compute the action of the symmetric group on this homology group. We then link it with the PreLie operad.
]
24/09/2013 Emily Burgunder Kontsevich graph complexes [abstract.html
Kontsevich proved that the Lie homology of symplectic Hamiltonians can be encoded as the homology of a Hopf bialgebra of graph complex attached to the commutative world. In this talk we will see some generalisation of this theorem : commutative world being replaced by operad, symplectic by a classical group, and we can consider Lie homology or its lifting to Leibniz homology.
]
24/09/2013 Samuele Giraudo From PROs to combinatorial Hopf algebras [abstract.html
There is a well-known natural functorial construction which, from a set-operad, produces a Hopf algebra. We extend this construction to the category of PROs with some extra properties. By this generalization, we retrieve, among other, the Hopf algebra of noncommutative symmetric functions in various bases and the noncommutative Faà di Bruno Hopf algebra. We also obtain new ones, as some Hopf algebras involving forests, heaps of pieces, and some kinds of combinational circuits. All these Hopf algebras are similar in a sense to the Connes-Kremier Hopf algebra. In this talk, we shall recall some background about PROs, then present the construction associating a Hopf algebra with a PRO, and finally, review some examples of applications.
]
24/09/2013 Journées Math-STIC Trees and graphs (from algebraic combinatorics to topology and random tensor models):
17/09/2013 Thé combinatoire et réunion d'équipe
17/09/2013 Thierry Monteil Pavages : quantifier l'aperiodicité d'un jeu de tuiles [abstract.html
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.
]
17/09/2013 Stéphane Fischler Valeurs de G-functions [abstract.html
Une sous-classe importante des fonctions holonomes est la classe des G-fonctions (définie par Siegel), qui jouent notamment un rôle important en théorie des nombres, en physique et en combinatoire. Une grande question, qui demeure en partie ouverte, est de comprendre de façon fine la structure de l'ensemble des valeurs prises par ces fonctions en des points algébriques. Ces valeurs englobent de célèbres constantes mathématiques, comme pi, les polyzêtas, des valeurs de fonctions hypergéométriques... Nous montrerons le résultat suivant : toute valeur en un point algébrique d'une G-fonction peut s'écrire f(1), où f est une G-fonction à coefficients rationnels dont le rayon de convergence peut de surcroît être choisi arbitrairement grand. On démontre aussi d'autres propriétés de ces valeurs de G-fonctions ; par exemple les constantes de connexion obtenues en prolongeant des G-fonctions sont de tels nombres. Il s'agit d'un travail en commun avec Tanguy Rivoal, dédié à la mémoire de Philippe Flajolet.
]
17/09/2013 Gérard H. E. Duchamp Une famille de contrexemples liée à l'infiltration des automates [abstract.html
It is now sure that one can show a version of the CQMM theorem which holds even in presence of heavy torsion. However the arrow constructed from the enveloping algebra of the primitive elements may not be into. There is a strange connection between the counter-example given on Mathoverflow and the q-infiltration product discovered by Luque et al.
]
03/09/2013 Ioannis Michos The support problem and shuffle algebra in positive characteristic
30/07/2013 Hans Porst Universal constructions for Hopf algebras [abstract.html
Starting from a slightly more abstract definition of Hopf algebras as usual, we present a method towards solutions of universal constructions for Hopf algebras (as, e.g., existence of free and cofree ones). On doing so we propose the use of results of category theory, not just of categorical language.
The talk, however, will be non-technical in this respect. Only elementary knowledge of categorical language will be expected.
]
23/07/2013 Gérard H. E. Duchamp Vers un modèle unifié des déformations et perturbations ?
23/07/2013 Collectif Point sur les articles en cours
23/07/2013 Hoang Ngoc Minh Sur la conjecture de Kashiwara-Vergne
10/07/2013 Alice Jacquot Soutenance à mi-parcours
10/07/2013 Ladji Kane Soutenance à mi-parcours
10/07/2013 Nguyên Hoàng Nghĩa Soutenance à mi-parcours
02/07/2013 Permutation Patterns 2013 (1-5 juillet 2013)
25/06/2013 FPSAC 2013 (24-28 juin 2013)
25/06/2013 Ladji Kane Coefficients de normalisation de la q-base S
18/06/2013 Lenka Zdeborová Where the really hard problems really are? [Slides.pdf]
18/06/2013 Gérard H. E. Duchamp qij-shuffle
18/06/2013 Hoang Ngoc Minh Monoides pondérés et critère de Friedrichs
13/06/2013 Journée ANR Magnum [abstract.html
10h30 Aline Parreau (LIFL) Une preuve combinatoire du lemme local de Lovasz
11h45 Julien David (LIPN) & Yann Ponty (LIX) présentation de RDos (Random Discrete Objects Suite): un ensemble d'outils pour la génération aléatoire d'objets combinatoires
12h30 Buffet en salle A201
14h Mathieu Raffinot (LIAFA) Nouvelles avancées dans la recherche de motifs uniques ou consécutifs dans des permutations travail en commun avec D.l Belazzougui (Univ. of Helsinki), A. Pierrot (LIAFA) et S. Vialette (LIGM)
15h15 Axel Bacher (LIPN) Génération aléatoire d'arbres en taille exacte et linéaire en temps et en espace
16h15 Discussion : bilan et perspectives après 30 mois
]
11/06/2013 Grégory Schehr Extreme statistics of non-intersecting Brownian motions [Slides.pdf] [abstract.html
Non-intersecting Brownian motions (BMs) have been the subject of numerous studies both in mathematics and in physics. In addition to their deep connection with random matrix theory, It was shown that they are at the heart of many fundamental models of statistical physics, like stochastic growth models or directed paths in random media. In this talk I will review some  recent results which we have obtained for the extreme statistics, like the maximal height, of such non-intersecting BMs.   
Les marcheurs Browniens conditionnés à ne pas se croiser ont suscité beaucoup d'intérêt ces dernières années, tant en mathématique (pour leurs aspects probabilistes et combinatoires) qu'en physique (comme des modèles de polymères ou de transition de mouillage ou de fusion). Dans cet exposé je présenterai un calcul exact de la distribution de la hauteur maximale d'une collection de N ponts Browniens (appelés 'watermelons without wall') et de N excursions Browniennes (appelées 'watermelons with a wall') conditionnés à ne pas se croiser. Je montrerai que dans la limite asymptotique où N tend vers l'infini cette distribution converge vers la distribution de Tracy-Widom qui décrit les fluctuations de la plus grande valeur propre de matrices aléatoires de l'ensemble gaussien orthogonal (GOE pour 'Gaussian Orthogonal Ensemble'). Je discuterai enfin une application de ces résultats asymptotiques à des modèles de croissance stochastique.
]
11/06/2013 Ladji Kane Preuve complète de la formule des coefficients λi
04/06/2013 Andrew Rechnitzer Combinatorics of the hard-squares model [Slides.pdf]
04/06/2013 Ladji Kane q shuffles de déformation et de perturbation
28/05/2013 AofA (27-31 mai 2013)
23/05/2013 Journée Math-STIC/BQR Marmots Yueyun Hu (LAGA), Axel Bacher (LIPN), Vladas Sidoravicius (Sao Paulo), Hugo Duminil-Copin (Genève), Guy Fayolle (INRIA)
21/05/2013 Jehanne Dousse Une généralisation du théorème de Roth pour les progressions arithmétiques [abstract.html
Le théorème de Roth établit que pour tout a>0, il exite un entier N tel que tout sous-ensemble de {1,...,N} de cardinal au moins aN contient une progression arithmétique de longueur 3 (un ensemble de la forme {x,x+r,x+2r} avec x et r des entiers non nuls). Plusieurs autres théorèmes importants de combinatoire additive concernent les progressions arithmétiques, comme le théorème de Szemeredi ou celui de Green-Tao. Après une introduction à la combinatoire additive, nous présenterons une généralisation du théorème de Roth aux "d-configurations" (ensembles de la forme {x_i+x_j+a|1<=i<=j<=d}, avec x_1,...,x_d et a des entiers) et nous étudierons son application aux sous-ensembles sans somme.
] [arXiv]
14/05/2013 Thomas Krajewski Combinatorial Hopf algebraic description of the multiscale renormalization in quantum field theory [arXiv]
14/05/2013 Petru Valicov Quelques résultats sur les codes identifiants [abstract.html
Un code identifiant d'un graphe est un sous-ensemble C de sommets qui est à la fois dominant (tout sommet du graphe a un voisin dans C ou appartient à C) et séparant (tous les sommets ont un voisinage distinct à l'intérieur de C). Dans cet exposé, nous faisons un tour d'horizon de quelques résultats sur cette notion. Nous proposons une caractérisation des graphes qui ont le code minimum de taille n-1, n étant l'ordre du graphe. Également nous nous intéressons à ce paramètre dans la classe des graphes adjoints. Si le temps le permet, nous parlerons de la complexité du problème dans différentes sous-classes des graphes parfaits.
]
14/05/2013 Gérard H. E. Duchamp Quasi-déterminants
02/05/2013 Tiago Dinis de Fonseca Le modèle à 6 vertex généralisé et les polynômes de Macdonald [Slides.pdf] [abstract.html
Les polynômes symétriques jouent, depuis toujours, un rôle assez important en physique. Par exemple, il est connu que la « fonction génératrice » du modèle à 6 vertex (remarquablement, ce modèle est en bijection avec les matrices à signes alternants) est un polynôme de Schur. Plus récemment, on a découvert, que la « fonction génératrice » d'une généralisation de ce modèle est aussi un polynôme symétrique, plus précisément, un polynôme de Macdonald.
]
02/05/2013 Aristide Baratin Méthodes combinatoires pour la gravité quantique [abstract.html
Certaines approches à la gravité quantique reposent sur une construction combinatoire de l'intégrale fonctionnelle.
Une question centrale dans ce contexte est de savoir comment incorporer, ou éventuellement retrouver dans un régime approprié, les symétries de la théorie classique (invariance par difféomorphismes).
Je présenterai certains aspects mathématiques de ce problème, que j'examinerai sous deux angles complémentaires :
  • le point de vue des invariants dits de "state sum", où les difféomorphismes de la variété sont remplacés par certaines opérations combinatoires sur des triangulations (mouvements de Pachner).
  • le point de vue des modèles de matrices, où l'invariance par difféomorphismes est le résultat de la sommation sur une certaine classe de graphes associés à des triangulations.
]
23/04/2013 Gérard H. E. Duchamp Combinatoire des idempotents de Lie ou CQMM sans base [abstract.html
Le théorème (classique) de Cartier-Quillen-Milnor-Moore (CQMM) dit que, en caractéristique zéro, une bigèbre est l'algèbre enveloppante de ses éléments primitifs si et seulement si elle est filtrée positivement.
Dans le but de poursuivre l'étude de l'arithmétique de certaines fonctions spéciales, il est nécessaire d'étendre ce résultat aux situations où les éléments primitifs n'ont plus nécessairement de base.
Nous donnons une preuve nouvelle du théorème de CQMM classique utilisant la combinatoire des idempotents eulériens et les fonctions symétriques noncommutatives ainsi que des applications combinatoires récentes du CQMM.
]
18/04/2013 Journée inaugurale du pôle MathSTIC de Paris 13 [abstract.html
Journée inaugurale du pôle MATHSTIC :

3 laboratoires de l'Institut Galilée (Le LAGA, le LIPN, et le L2TI) s'associent pour proposer une journée inaugurale du POLE MATHSTIC, le 18 avril de 9h30 à 17h30 en Amphi A.

9h30 Accueil
9h45 Présentation du pôle (C. Fouqueré) Mots de C. Desfrançois VPCS et F. Dibos Directrice de l'institut Galilée
10h Présentation de l'axe 2 (L. Halpern) Architectures émergentes et passage à l'échelle d'applications parallèles (C. Coti) Déploiement de réseaux sans fil (N. Achir ) Méthodes de décomposition de domaine espace-temps (C. Japhet) Calculs performants pour la simulation d'écoulements à fronts raides (F. Benkhaldoun)
12h Buffet (salle M100 de l'IUT)
13h15 Présentation de l'axe 3 (A. Sportiello) Mots circulaires (B. Rittaud) Physique combinatoire : algèbres de Hopf - combinatoires en théories quantiques de champs (A. Tanasa) Combinatoire et aléas (P. Marchal)
15h15 pause café
15h30 Présentation de l'axe 1 (R. Wolfler-Calvo) Les algorithmes de flots à la rescousse (L. Létocart) Compression d'images avec contrôle de qualité : au delà ( B. Matei) Améliorer la mobilité grâce aux Systèmes de Transport Intelligents (K. Boussetta)
17h30 fin

]
16/04/2013 Jean Fromentin Sur l'arbre des semigroupes numériques [Slides.pdf] [abstract.html
Un semi-groupe numérique est une partie de N stable par addition et de complément fini. D'apparence simple, ces objets conduisent à de nombreux problèmes : problème de Frobenius (ou de rendu de monnaie), conjecture de Wilf, ... Les semi-groupes numériques peuvent être regroupés par genre, le genre d'un semi-groupe numérique étant le cardinal de son complémentaire dans N. Une question naturelle est alors de déterminer le nombre de semi-groupes numériques de genre donné. Les valeurs de n_g ont été calculés par Maria Bras Amoros pour g<=52. Sur sa page web, Manuel Delgado donne la valeur de n_55. Dans cet exposé, après une introduction aux semi-groupes numériques, nous présenteront différentes optimisation algorithmiques permettant d'améliorer les résultats de Maria Bras Amoros et Manuel Delgado.
]
16/04/2013 Matthieu Deneufchâtel Intégrales Itérées
16/04/2013 Christophe Tollu Dynamique des tableaux de Young infinis d'après Romik et Sniady
09/04/2013 Sylvie Corteel Pyramides et diamants [Slides.pdf] [abstract.html
On cherche à énumérer des pavages par dominos d'une région obtenus par flip à partir d'un pavage minimal unique. Pour cela, on utilise les diagrammes maya, les "vertex operators" et les fonctions de Schur supersymétriques. On obtient des formules type "équerre" ; dont des cas particuliers compte les pavages du diamant aztèque ou les partitions pyramides de Ben Young. [Travail en commun avec Jérémie Bouttier et Guillaume Chapuy)]
]
02/04/2013 Valentin Bonzom A set of triangulations of manifolds in arbitrary dimensions from multi-graphs with colored edges [abstract.html
I will talk about families of triangulations of manifolds in arbitrary dimensions which can be represented by multi-graphs with colored edges. I will focus on an important family of such triangulations, called melonic triangulations, which controls the behavior of integrals over random tensors (a promising approach to quantum gravity). These integrals can be solved by an exact counting of the melonic triangulations. If time permits, I will describe the relation to loop models on random planar maps, and also an interesting family of colored triangulations related to meanders.
]
02/04/2013 Valentin Bonzom Invariants of cellular complexes from twisted cohomology and the Reidemeister torsion [abstract.html
Cellular complexes are often used in physics as discretizations of spacetime. An interesting class of amplitudes associated to those complexes are topological invariants. I will present a simple model which relates an integral over some Lie group elements associated to the edges of the complex to the so called combinatorial, or Reidemeister torsion of the complex.
]
26/03/2013 Matteo Silimbani Combinatoire des arbres non ambigus [abstract.html
Au cours de cet exposé, je définirai des nouveaux objets combinatoires, les arbres non-ambigus. Ces objets peuvent être vus comme des arbres dessinés sur une grille sous certaines contraintes et ils sont liés à plusieurs objets combinatoires, comme les polyominos parallélogrammes et les tableaux boisés définis par Aval, Boussicault et Nadeau. L'on verra comment l'énumération des arbres non-ambigus satisfaisant des contraintes supplémentaires permet de donner des preuves combinatoires élégantes d'identités dues à Carlitz, et à Ehrenborg et Steingrìmsson. Je montrerai aussi une formule des équerres pour le comptage des arbres non-ambigus dont l'arbre sous-jacent est fixé. Enfin, je utiliserai les arbres non-ambigus pour décrire une bijection très naturelle entre polyominos parallélogrammes et arbres binaires.
]
26/03/2013 70ème Séminaire Lotharingien de Combinatoire
19/03/2013 Journées ALEA
19/03/2013 Gérard H. E. Duchamp Fonctions symétriques noncommutatives, algèbre des descentes et action sur les bigèbres sans graduation ni liberté
12/03/2013 Juanjo Rué Perna Bipartite subfamilies of planar graphs [Slides.pdf] [abstract.html
I will survey the techniques used to get asymptotic results for subfamilies of planar graphs, as well as how to relate this methodology with the context of map enumeration. In the second part of the talk, I will explain the ideas behind some on-going projects related to the enumeration of bipartite subfamilies of graphs.
]
12/03/2013 Andrea Sportiello Algebraic/combinatorial proofs of Cayley-type identities for derivatives of determinants and pfaffians
05/03/2013 Axel de Goursac Combinatorial aspects of the Jacobi conjecture [Slides.pdf] [abstract.html
We expose the reformulation of the Jacobian conjecture in terms of the combinatorics of Feynman diagrams of a certain Quantum Field Theory. We will also discuss considerations about Dixmier conjecture and Noncommutative Quantum Field Theory.
]
05/03/2013 Axel de Goursac Weyl quantization of the Heisenberg supergroup and application to combinatorial quantum field theory [Slides.pdf] [abstract.html
By using Kirillov's orbits method and Weyl-type quantization on the Heisenberg supergroup, we construct a non-formal deformation quantization of superspaces. We are led by the theory to introduce new notions such as Hilbert superspaces and C*-superalgebras. Then, a noncommutative superspace coming from this deformation yields an interpretation of the renormalizable quantum field theory with harmonic term on the Moyal space.
]
26/02/2013 Patrice Ossona de Mendez Un petit survol des grands algorithmes de la théorie des graphes, illustrés via le logiciel libre PIGALE [Slides.pdf]
26/02/2013 Christophe Tollu Algèbres localement semi-simples et graphes gradués : quelques résultats de base [abstract.html
Une algèbre A est localement semi-simple si c'est la limite inductive d'une chaîne d'algèbres semi-simples de dimension finie An. On associe à A un graphe gradué (appelé diagramme de Bratteli), qui se construit facilement à partir de la décomposition de chaque An en somme directe d'algèbres (pleine) de matrices. Les diagrammes de Bratteli jouent un rôle de premier plan dans la théorie algébrico-combinatoire des algèbres localement semi-simples. Je présenterai quelques résultats fondamentaux de cette théorie.
]
19/02/2013 Christian Krattenthaler Énumeration exacte et asymptotique de pastèques avec barrière [abstract.html
Le modèle des promeneurs vicieux (sic!) a été introduit par Michael Fisher en mécanique statistique en 1984. De nombreuses variantes ont été étudiées depuis, en particulier celle que je condidère dans mon exposé : lorsque qu'il y a une interaction entre ces promeneurs et un mur. Ce modèle a été originellement proposé par Owczarek, Essam et Brak, qui ont établi quelques résultats partiels. Je montrerai comment complètement déterminer le comportement asymptotique de la fonction de partition correspondante (et celle d'un autre paramètre pertinent). Nous rencontrerons comme de bien entendu (attendu!) mes chers amis : déterminants, une bijection de tableau et des séries hypergéometriques.
]
19/02/2013 Olivier Bouillot Les multitangentes, vues à travers les multizêtas de Hurwitz [abstract.html
En lien avec les multizetas qui généralisent la fonction zeta de Riemann en plusieurs dimension, il existe deux autres familles apparentées et naturelles : les multizetas de Hurwitz et les multitangentes. Alors que les multizetas sont des nombres, les multizetas de Hurwitz et les multitangentes sont des fonctions méromorphes sur C.
Nous présenterons une vue d'ensemble des liens important unissant ces objets, des résultats connues et de ce que l'on peut espérer obtenir à terme.
Nous présenterons notamment les derniers résultats d'un travail en cours sur les multizetas de Hurwitz, à savoir leur indépendance linéaire sur le corps des fractions rationnelles.
]
12/02/2013 Julien Clément Some patterns in Pierre Nicodème's works [Slides.pdf]
12/02/2013 Bruno Salvy Newton iteration in computer algebra and combinatorics [Slides.pdf]
12/02/2013 Alin Bostan Computer algebra for the enumeration of lattice walks [Slides.pdf]
12/02/2013 Pierre Nicodème Journée en l'honneur du départ à la retraite de Pierre Nicodème : accueil
05/02/2013 Shalom Eliahou La conjecture de Hadamard [Slides.pdf]
05/02/2013 Axel Bacher Inversion de Lagrange multivariée
29/01/2013 Thierry Combot Initiation à la théorie de Galois différentielle et applications aux fonctions holonomes [Slides.pdf] [abstract.html
Nous présenterons la théorie de Galois différentielle appliquée aux équations différentielles à coefficients polynomiaux puis aux équations aux différences. On montrera ensuite comment calculer ces groupes de Galois, et quels sont les algorithmes disponibles. On présentera alors les méthodes disponibles pour résoudre ces équations en introduisant les fonctions liouviliennes. Enfin nous appliquerons ces méthodes pour l'analyse du comportement asymptotique des solutions : le groupe de Galois donne en particulier des relations algébriques a priori sur les constantes apparaissant dans ces développements asymptotiques, et permettent dans le cas liouvillien de les expliciter.
]
29/01/2013 Gérard H. E. Duchamp Combinatorial deformations I : Coloured algebras (tensor products and Lie theory)
22/01/2013 Gérard H. E. Duchamp Combinatorial aspects of quantum physics [abstract.html
This small account aims at presenting a project which deals with combinatorial aspects of Quantum Mechanics (or Physics).
This project brings together specialists in Mathematics, Informatics and Physics.
The general subjects are: Hopf algebras, representation theory, deformations, discrete operators and evolution equations.
Since the accomplishment of Connes and Kreimer, the Hopf algebras entered Physics as an efficient tool to solve or to render compact computation problems of composition and decomposition. As many of these Hopf algebras are defined by diagrams (the language of R. Feynman), the problem of implementing them in order to compute at a high order induces many fundamental questions (polynomial realizations, data structures, finite orbits, etc.). These are indeed the problems of (multiple) indexation which appear in ``special sums'' like MZV, EZS, Jack polynomials, MacDonald polynomials or in geometric problems like the combinatorial presentation of Schubert cycles, combinatorics of flag manifolds, or the computation and measure of entangled states.
Quantum Mechanics rests almost entirely on commutation relations (of Heisenberg-Weyl type or deformed) and on evolution equations which give new insights respectively for orthogonal polynomials and for exact solutions of Fokker-Planck or non-commutative evolution equations ($KZ_n$).
The strength of the project relies not only on its scientific unity but also on a well coordinated team scattered among several communities. The qualities and complementarity of the different centers will be commented throughout this small talk.
]
22/01/2013 Adrian Tanasa Grassmanian variables, Grassmann-Berezin integrals and things we can do with [abstract.html
In this talk I will introduce Grassmann variables and the basic rules of Grassmann-Berezin calculus. I will then show how we can use these tools to express Pfaffians and determinants and to derive various non-trivial identities in combinatorics and combinatorial physics (deletion/contraction relation for graph polynomial, Desnanot-Jacobi identities etc.).
]
22/01/2013 Journées du GDR-IM (21-22 janvier)
15/01/2013 Philippe Marchal Génération aléatoire de permutations alternées [abstract.html
Désiré André (dans son article de 1879) a montré que le développement en série de tan(x) et sec(x) est lié à une jolie suite combinatoire, les nombres Eulériens, qui comptent le nombre de permutations alternées. J'introduis un nouvel algorithme, basé sur des idées de théorie des probabilités, qui permet d'engendrer une telle permutation de longueur n en temps n log n. Je montrerai que l'idée peut aussi s'étendre à d'autres classes de permutations contraintes.
]
15/01/2013 Nguyên Hoàng Nghĩa The Tutte polynomial for matroids, a renormalization group-like approach [abstract.html
Using a quantum field theory renormalization group-like differential equation, we give a new proof of the recipe theorem for the Tutte polynomial for matroids. The solution of such an equation is in fact given by some appropriate characters of the Hopf algebra of isomorphic classes of matroids, characters which are then related to the Tutte polynomial for matroids.
]
08/01/2013 Hoang Ngoc Minh Polyzêtas colorés
18/12/2012 Christophe Tollu Théorie des modèles : une application
04/12/2012 Stephen Melczer A Classification of Restricted Lattice Walks with Small Steps [Slides.pdf] [abstract.html
The enumeration of lattice walks in restricted regions is an elegant problem which has been the subject of much attention. In this talk we survey recent results on lattice walks in the quarter plane, regarding the analytic properties of their generating functions. Specifically, we discuss the classification of walks whose generating functions satisfy linear differential equations, and why this property is desirable.
]
04/12/2012 Laurent Poinsot Classes combinatoires : un point de vue catégorique [Slides.pdf]
27/11/2012 Stéphane Dartois Développements asymptotiques pour les modèles tensoriels
20/11/2012 Thomas Fernique Pavages de Penrose revisités [abstract.html
Dans les années 70, Ammann et Penrose ont indépendamment découvert deux losanges légèrement déformés qui permettent de paver le plan (c'est-à-dire de le couvrir en entier sans que les losanges ne se superposent), mais seulement de façon non-périodique. De Bruijn a par la suite montré que ces pavages pouvaient être vus comme des discrétisations d'un plan totalement irrationnel de l'espace euclidien à cinq dimensions. Nous montrerons comment, dans cet espace, les déformations de ces losanges se traduisent en contraintes géométriques simples qui permettent de retrouver le résultat de De Bruijn par une méthode différente, plus générique. Pour illustrer cette généricité, nous présenterons une variante des losanges de Ammann et Penrose dont les pavages peuvent être vus comme des discrétisations d'une famille à deux paramètres de plans de l'espace euclidien à cinq dimensions. Il s'agit d'un travail en commun avec Nicolas Bédaride (LATP, Marseille).
]
20/11/2012 Hoang Ngoc Minh Déformations et perturbations du produit de mélange
13/11/2012 Nick Beaton Self-avoiding walks and polygon models [abstract.html
Self-avoiding bridges on the hexagonal lattice In their recent paper proving the connective constant mu of self-avoiding walks (SAWs) on the hexagonal (honeycomb) lattice, Duminil-Copin and Smirnov consider the generating function of self-avoiding bridges which span a strip of width T, and conjecture that this generating function vanishes at 1/mu in the large T limit. This generating function was again considered by Bousquet-Mélou, de Gier, Duminil-Copin, Guttmann and myself when we studied the adsorption of SAWs onto an impenetrable surface, and we proved the conjecture of Duminil-Copin and Smirnov. I will discuss this conjecture and its proof, as well as what happens after rotating the lattice by pi/4. Reference arXiv: pdf1, pdf2
]
13/11/2012 Matthieu Deneufchâtel et Gérard H. E. Duchamp Sur une famille de bigèbres combinatoires [Slides.pdf]
12/11/2012 Adrian Tanasa Soutenance d'HDR : "Combinatoire en théories quantiques des champs et modèles de tenseurs aléatoires"
06/11/2012 Carine Pivoteau Un pont entre les espèce de structures et la combinatoire analytique II [abstract.html
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és à 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.
]
06/11/2012 Carine Pivoteau Un pont entre les espèce de structures et la combinatoire analytique I [abstract.html
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és à 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.
]
23/10/2012 Juanjo Rué Perna On the probability of planarity of a random graph near the critical point [Slides.pdf] [abstract.html
Consider the uniform random graph G(n,M) with n vertices and M edges. Erdős and Rényi (1960) conjectured that when n goes to infinity, then the limit of "Pr(G(n,n/2) is planar" exists and is a constant strictly between 0 and 1. Łuczak, Pittel and Wierman (1994) proved this conjecture and Janson, Łuczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this talk we show how to determine the exact probability of a random graph beingplanar near the critical point M=n/2. More exactly, for each λ, we find an exact analytic expression for p(λ) = \lim_{n \to \infty} \Pr{G(n,n/2 (1+λ n^{-1/3})) is planar}. In particular, we obtain p(0) \approx 0.99780. If time permits we will show extensions of these techniques and further research. This is a joint work with Marc Noy (UPC-Barcelona) and Vlady Ravelomanana (LIAFA-Paris)
]
23/10/2012 Gérard H. E. Duchamp Sweedler's duals and Schützenberger's calculus [abstract.html
The theoretical setting of his talk is based essentially on the paper - with the same title [pdf]- published in a workshop about Combinatorial Physics [1]. This setting was used to prove, with Christophe Reutenauer, a conjecture by Alain Connes [2]. We give new insights and applications of this concept.
[1] G.H.E. Duchamp and C. Tollu, Sweedler’s duals and Schützenberger’s calculus, In K. Ebrahimi-Fard, M. Marcolli and W. van Suijlekom (eds), Combinatorics and Physics, p. 67–78, Amer. Math. Soc. (Contemporary Mathematics, vol. 539), 2011.
[2] G. Duchamp, C. Reutenauer, Un critère de rationalité provenant de la géométrie non-commutative (à la mémoire de Schützenberger), Inventiones Mathematicae, 128, 613-622, (1997).
]
16/10/2012 Hsien-Kuei Hwang Maxima of multivariate samples: theory, algorithms and applications
16/10/2012 Hoang Ngoc Minh Séries de rang de Lie fini
09/10/2012 Anna Frid Comptage des mots de rotation [Slides.pdf] [abstract.html
Nous donnons une formule précise pour le nombre total des mots de rotation engendrés par deux intervalles. Le résultat utilise les travaux de Berstel et Pocchiola sur les mots sturmiens. Il continue aussi un résultat par Cassaigne et Frid (2007) sur le comptage des mots de rotation dont l'intervalle est fixé. [Travail commun avec D. Jamet]
]
09/10/2012 Gérard H. E. Duchamp Groupe de Hausdorff et coordonnées locales [abstract.html
In classical Lie groups, the product of one-parameter groups wrt any basis of the tangent Lie algebra provides an open mapping which gives at once a system of local coordinates. We discuss the transposition of this process to the Hausdorff (profinite) Lie group with several combinatorial alphabets.
]
02/10/2012 Gérard H. E. Duchamp Quelques remarques sur les caractères et la renormalisation (travaux en cours)
02/10/2012 Christophe Tollu Sur les corps de fonctions et leurs extensions
27/09/2012 Matthieu Deneufchâtel Soutenance de thèse : Iterated integrals in combinatorial physics [Slides.pdf]
25/09/2012 collectif Inauguration du salon de thé combinatoire [abstract.html
Ce "salon de thé combinatoire" avec petits gâteaux et grandes questions se veut un groupe de travail libre autour de la combinatoire. Ce salon est ouvert à tous, chacun pouvant exposer de manière décontractée ses travaux en cours, ses problèmes ouverts, ses lectures scientifiques... Nous souhaitons un lieu de partage convivial et actif. Un lieu où l'on peut lancer des idées, poser des questions naïves ou profondes sans crainte. En d'autres termes, un lieu où faire de la recherche !
]
25/09/2012 Bernhard Gittenberger Infinite-Dimensional Functional Equations and Gaussian Limiting Distributions [abstract.html
What Philippe Flajolet popularized as the "Drmota-Lalley-Woods theorem" gives a kind generalisation of the Perron-Frobenius theory (rational world) to polynomial system of equations (algebraic world). It establishes a universal behaviour (square singularity, Gaussian limit law). This talk will deal with systems of functional equations in finitely or infinitely many random variables arising in combinatorial enumeration problems. We prove sufficient conditions under which the combinatorial random variables encoded in the generating function of the system tend to a finite or infinite dimensional limiting distribution. The proofs use a pinch of complex analysis and functional analysis. [Joint work with Michael Drmota and Johannes Morgenbesser]
]
25/09/2012 Vonjy Rasendrahasina Soutenance de thèse : MAX-2-XORSAT
18/09/2012 Michael Drmota Extremal parameters in critical and subcritical graph classes [Slides.pdf] [abstract.html
In recent years there has been increasing interest in the asymptotic analysis of (several classes of) planar maps and planar graphs. This was initiated by bijective methods (e.g. the Shaeffer bijection), generating function methods (e.g. Gimenez and Noy's result on the asymptotics of number of planar graphs) and the search for probabilistic limiting objects (e.g. the Brownian map by Le Gall). In particular in the discussion of several planar graph classes (like series-parallel graphs or labelled planar graphs) a dichotomy between a "critical" and "subcritical" behaviour between 2-connected and connected graphs was observed. Informally a graph class is subcritical when all 2-connected components are small (i.e., at most of log n - size) and one observes a "treelike structure". Conversely a graph class is critical when the largest 2-connected component is comparable to the size of the whole graph. The purpose of this talk is to discuss the asymptotic behaviour of several (extremal) parameters of subcritical and critical graph classes, in particular the diameter and the maximum degree. For subcritical graph classes the diameter is (usually) of oder n^(1/2) whereas we can expect the order n^(1/4) in the critial case. On the other hand the maximum degree is (usually) of order log n in both cases. However, critical graph classes are notoriously more difficult to handle than subcritical ones. This talk is mainly based on joint work with Omer Gimenez, Marc Noy, Konstantinos Panagiotou, and Angelika Steger.
]
18/09/2012 Matthieu Deneufchâtel et Gérard H. E. Duchamp Un théorème différentiel [Slides.pdf] [abstract.html
Dans cet exposé, nous présentons un théorème relatif à un critère d'indépendance linéaire des coefficients d'une solution d'une équation différentielle non commutative. Ce théorème a pour conséquence l'indépendance linéaire des polylogarithmes et de leur généralisation, les hyperlogarithmes, sur des corps de fonctions. Dans la suite nous regardons à travers le miroir pour avoir des renseignements sur les dérivations.
]
03/09/2012 Matthieu Deneufchâtel Iterated integrals in combinatorial physics
03/09/2012 Nguyên Hoàng Nghĩa On the selection/quotient principle
07/08/2012 Collectif CQMM and rewriting (part 2) [abstract.html
Nous devons comprendre les aspects du théorème de CQMM préparatoires à l'implémentation. Cela passe par une phase d'analyse/conception des différentes réécritures qui lui sont liées.
]
07/08/2012 Collectif CQMM and rewriting (part 1) [abstract.html
Nous devons comprendre les aspects du théorème de CQMM préparatoires à l'implémentation. Cela passe par une phase d'analyse/conception des différentes réécritures qui lui sont liées.
]
31/07/2012 FPSAC 2012 (30 juillet-3 août)
31/07/2012 Gérard H. E. Duchamp Quelques lois exotiques (et utiles) pour le ξ-stuffle (II) [abstract.html
Les constantes de structure (ou coefficients de linéarisation) de certaines algèbres (comme les fonctions rationnelles nulles à l'infini) ont une riche combinatoire que nous nous proposons d'illustrer et de discuter sur quelques exemples.
]
31/07/2012 Matthieu Deneufchâtel Combinatoire des bases en dualité pour différents stuffles
24/07/2012 Gérard H. E. Duchamp Quelques lois exotiques (et utiles) pour le ξ-stuffle [abstract.html
Les constantes de structure (ou coefficients de linéarisation) de certaines algèbres (comme les fonctions rationnelles nulles à l'infini) ont une riche combinatoire que nous nous proposons d'illustrer et de discuter sur quelques exemples.
]
17/07/2012 Hoang Ngoc Minh Polyzetas irréductibles et bases de Gröbner [abstract.html
Le passage des polyzêtas de Riemann aux polyzêtas de Hurwitz colorés nécessite une déformation du stuffle au duflle puis au truffle. Dans cet exposé, nous suivons la trace de la déformation de l'algèbre de Hopf en précisant des calculs (et des algorithmes) de base concernant le logarithme, l'exponentielle, la détermination des éléments primitifs et de l'antipode.
]
17/07/2012 Hoang Ngoc Minh Shuffles, duffles, truffles [abstract.html
Le passage des polyzêtas de Riemann aux polyzêtas de Hurwitz colorés nécessite une déformation du stuffle au duflle puis au truffle. Dans cet exposé, nous suivons la trace de la déformation de l'algèbre de Hopf en précisant des calculs (et des algorithmes) de base concernant le logarithme, l'exponentielle, la détermination des éléments primitifs et de l'antipode.
]
10/07/2012 Olivier Bouillot Les multitangentes, vues à travers les multizêtas de Hurwitz (part 2) [abstract.html
Les multizêtas sont les nombres définis par des sommes itérées sur les entiers strictement positifs, généralisant les valeurs de la fonction ζ de Riemann aux entiers supérieurs à 2. Ceux ci possèdent de nombreuses dénominations dans la littérature : polyzêtas, nombres d'Euler-Zagier, valeurs zêta multiples, sommes harmoniques multiples.... L'étude algébrique et arithmétique de ces nombres pourrait apparaître comme étant du folklore mathématique. Cependant, il n'en est rien : cette étude se trouve justifiée par l'apparition de ces nombres, depuis 30 ans, dans des domaines très variés et très actifs des mathématiques : théorie des nombres, groupes quantiques, diagrammes de Feynman, théorie de la résurgence, ...
Une généralisation fonctionnelle naturelle de ces nombres nous amène à considérer les ``multitangentes'' : il s'agit de fonctions méromorphes définies de manière analogue aux multizêtas, mais par des sommes itérées sur tous les entiers. Le but de l'exposé sera d'introduire les premières propriétés de ces fonctions, de montrer les liens profond entre multitangentes et multizêtas et de faire un état des lieux de ce que l'on sait faire et souhaite faire.
L'après midi sera consacré, en fonction des souhaits des auditeurs, à différents détails techniques, calculatoires ou combinatoires exposés le matin, à faire le point sur l'état d'avancement de certaines conjectures ou encore de généralisation elliptiques.
]
10/07/2012 Olivier Bouillot Les multitangentes, vues à travers les multizêtas de Hurwitz (part 1) [abstract.html
Les multizêtas sont les nombres définis par des sommes itérées sur les entiers strictement positifs, généralisant les valeurs de la fonction ζ de Riemann aux entiers supérieurs à 2. Ceux ci possèdent de nombreuses dénominations dans la littérature : polyzêtas, nombres d'Euler-Zagier, valeurs zêta multiples, sommes harmoniques multiples.... L'étude algébrique et arithmétique de ces nombres pourrait apparaître comme étant du folklore mathématique. Cependant, il n'en est rien : cette étude se trouve justifiée par l'apparition de ces nombres, depuis 30 ans, dans des domaines très variés et très actifs des mathématiques : théorie des nombres, groupes quantiques, diagrammes de Feynman, théorie de la résurgence, ...
Une généralisation fonctionnelle naturelle de ces nombres nous amène à considérer les ``multitangentes'' : il s'agit de fonctions méromorphes définies de manière analogue aux multizêtas, mais par des sommes itérées sur tous les entiers. Le but de l'exposé sera d'introduire les premières propriétés de ces fonctions, de montrer les liens profond entre multitangentes et multizêtas et de faire un état des lieux de ce que l'on sait faire et souhaite faire.
L'après midi sera consacré, en fonction des souhaits des auditeurs, à différents détails techniques, calculatoires ou combinatoires exposés le matin, à faire le point sur l'état d'avancement de certaines conjectures ou encore de généralisation elliptiques.
]
03/07/2012 Gérard H. E. Duchamp The contrivances of shuffle products and their siblings
26/06/2012 Mario Valencia Pabon Lokshtanov-Nederlof's exact pseudo-polynomial time algorithm for the knapsack problem in polynomial space
26/06/2012 Gérard H. E. Duchamp An interface between physics and number theory
25/06/2012 Omar Ait Mous Soutenance de thèse
19/06/2012 AofA 2012 (17-22 juin)
05/06/2012 Daniel Barsky Éléments d'ordre une puissance de p dans le groupe symétrique, exponentielle de Dwork et analyse p-adique d'après Conrad, Ishihara, Ochiai, Takegahara, Yoshida [abstract.html
Les auteurs suscités ont montré que le nombre de solutions, bn,p de gp=1 dans le groupe Sn possède d'intéressante propriétés p-adique. Je montre que ce résultat équivaut à une propriété (inattendue ?) de prolongement analytique p-adique de la fonction Gamma p-adique. Ce résultat se généralise.
]
05/06/2012 Pierre-André Picon Produits-quotients de factorielles, fonction partie entière et lien avec le théorème de Tchebycheff et l'hypothèse de Riemann
29/05/2012 Hypergeometric series and algebra, geometry, number theory and physics (29 mai-1 juin, IHP)
22/05/2012 Christophe Tollu Catégories, Automates et Représentations I
22/05/2012 Henning Bruhn-Fujimoto Matroïdes infinis [abstract.html
Un matroïde est une structure sur un ensemble fini qui généralise au même temps l'indépendance dans un espace vectoriel et le comportement des arbres couvrant d'un graphe. Parmi les points clés d'un matroïde sont la dualité et l'existence des bases et des circuits. En 1966, Rado a demandé comment la définition des matroïdes se laisse étendre sur des ensembles infinis en gardant ces propriétés clées. Dans l'exposé je donnerai une réponse à la question de Rado. Travail en collaboration avec R. Diestel, M. Kriesell. R. Pendavingh et P. Wollan.
]
22/05/2012 Gérard H. E. Duchamp Combinatoire des états cohérents I : états classiques et généralisés
22/05/2012 CANT 2012 School on Combinatorics, Automata and Number Theory (21-25 mai), CIRM
15/05/2012 Roberto Bondesan Percolation and lattice algebras in localization problems [abstract.html
I will discuss geometrical problems arising from the study of localization using disordered network models. I will focus mostly on relations to the percolation problem and the role of lattice algebras.

survey de John Cardy sur le sujet

]
15/05/2012 Bernhard Gittenberger Some shape characteristics of Pólya trees [abstract.html
We discuss the asymptotic behaviour of some typical shape characteristics like profile and height as well as a refinement like the degree profile of Pólya trees (unlabeled, nonplane rooted trees). We prove a local limit theorem for the height and a functional limit theorem for the profiles.
]
01/05/2012 fête du séminaire
24/04/2012 Gérard H. E. Duchamp Composition de fonctions représentatives : shuffles, produits de Cauchy et de Hadamard
24/04/2012 Olivier Roussel Shuffle de langages et génération aléatoire
24/04/2012 Margherita Disertori Matrices aléatoires gaussiennes unitaires et méthodes de point col
24/04/2012 Stéphane Dartois Various combinatorial aspects of tensor models
17/04/2012 Christophe Tollu Initiation à la dualité entre groupes et catégories de représentations II [abstract.html
La théorie de la dualité de Tannaka est l'étude des interactions entre un groupe et la catégorie de ses représentations. Les premiers théorèmes de Krein et Tannaka se concentraient sur la question de la reconstruction d'un groupe compact à partir de ses représentations. On présentera quelques constructions catégoriques qui jouent un rôle important dans la présentation moderne de cette théorie "classique".
]
17/04/2012 Gérard H. E. Duchamp Mécanique quantique, clôtures rationnelles et fonctions représentatives
10/04/2012 Christophe Tollu Exercices et compléments
10/04/2012 Éric Balandraud Méthode polynomiale et combinatoire additive dans Fp [abstract.html
Apres avoir expose les principes de la methode polynomiale, aussi appelee Combinatorial Nullstellensatz. Nous detaillerons ses applications en combinatoire additive. Cette methode donne de nouvelles preuves de resultats classiques, comme le theoreme de Cauchy-Davenport ou de Erdos-Ginzburg-Ziv, et de nombreux resultats recents. Certaines de ces applications font appel de maniere surprenante a des determinants binomiaux issus des travaux de Gessel et Viennot.
]
10/04/2012 Xavier Goaoc Un point de vue combinatoire sur le théorème de Helly [abstract.html
Le théorème de Helly énonce que si une famille finie de convexe de R^d est d'intersection vide alors elle contient une sous-famille d'au plus d+1 membres dont l'intersection est déjà vide. J'illustrerai comment ce résultat classique et certaines de ses généralisations récentes s'expriment naturellement en termes de combinatoire topologique. Aucune connaissance préalable en géométrie ou topologie ne sera supposée. Travail commun avec Éric Colin de Verdière (CNRS-ENS) et Grégory Ginot (UPMC-ENS).
]
10/04/2012 Christophe Tollu Initiation à la dualité entre groupes et catégories de représentations [abstract.html
La théorie de la dualité de Tannaka est l'étude des interactions entre un groupe et la catégorie de ses représentations. Les premiers théorèmes de Krein et Tannaka se concentraient sur la question de la reconstruction d'un groupe compact à partir de ses représentations. On présentera quelques constructions catégoriques qui jouent un rôle important dans la présentation moderne de cette théorie "classique".
]
03/04/2012 Manuel Bodirsky Sur une conjecture d'énumération
03/04/2012 Manuel Bodirsky Théorie de Ramsey et un lien récent avec la topologie dynamique [Slides.pdf]
03/04/2012 Gérard H. E. Duchamp Combinatoire des catégories de modules I : Suites de Jordan-Hölder et q-caractéristiques de Frobenius [abstract.html
On explique la partie "catégories de modules" avec de possibles prolongements.
]
27/03/2012 Séminaire SLC (25-28 mars)
27/03/2012 Alice Jacquot Algorithme de Rémy et générateur de Boltzmann pour spécifications holonomes [abstract.html
Je présenterai des travaux en cours avec Olivier Bodini et Axel Bacher sur la génération aléatoire d'arbres décrit par une spécification holonome. Cette approche nous permet de généraliser l'algorithme de Rémy.

Référence : article de Jean-Luc Rémy

]
20/03/2012 Gérard H. E. Duchamp Fonctors U, L and T in combinatorics [abstract.html
Many combinatorial Hopf algebras are positively graded in finite dimensions. This has a consequence on Hilbert series of (and in) these. For example, in FQSym, the Hilbert series of the cocommutative part could be computed and it was conjectured with some evidence that the primitive part was a free lie algebra. We give some hints on an ongoing work.
]
20/03/2012 Mark Ward A solved problem in analysis. An unsolved problem in analysis.
20/03/2012 Tanguy Rivoal Quelques propriétés analytiques des applications miroir
20/03/2012 Christophe Tollu Combinatoire des représentations polynomiales des groupes généraux linéaires
13/03/2012 Loïck Lhote Complexité moyenne de la recherche de motifs fréquents et de traverses minimales d'hypergraphes [Slides.pdf] [abstract.html
La fouille de données est le domaine qui vise à extraire automatiquement de l'information dans de grandes masses de données. Une manière de faire est d'extraire des motifs qui vont contenir cette information et qui servent ensuite à créer des règles d'association. Il existe un grand nombre de motifs (motifs fréquents, fermés, libres, émergents, satisfaisant des mesures d'intérêts, bordure négative, etc.) et une large famille d'algorithmes dédiés pour les extraire. Dans le pire des cas, le nombre de motifs est souvent exponentiel et c'est souvent la seule information dont on dispose sur la complexité des problèmes et des algorithmes. Pourtant en pratique, les algorithmes sont efficaces lorsqu'ils sont utilisés avec des paramètres raisonnables. L'analyse en moyenne qui, contrairement à celle dans le pire des cas, tient compte de toutes les entrées possibles peut expliquer ce genre de phénomène. L'exposé présentera des analyses en moyenne concernant les motifs fréquents et les traverses minimales d'hypergraphes. Le calcul des traverses minimales est fondamental en fouille de données puisqu'il existe par exemple une bijection avec les motifs de la bordure négative. Une question algorithmique encore ouverte est de savoir si le calcul des traverses minimales est output-polynomial (polynomial en la taille de l'entrée plus celle de la sortie) dans le pire des cas. Un éclairage en moyenne sera apporté à cette question.
]
13/03/2012 Arnaud Mary Génération des dominants minimaux d'un graphe [Slides.pdf] [abstract.html
La théorie des bases de données et la théorie des treillis présentent de nombreux liens que je rappellerai dans cette présentation. Je présenterai ensuite le problème de génération des transversaux minimaux d'un hypergraphe et j'expliquerai en quoi celui-ci est fortement lié à la théorie des treillis. Un hypergraphe H est une collection d'ensembles E (appelés hyperarête) sur un ensemble de sommet V. Un transversal de H est un ensemble de sommets qui intersecte toutes les hyperarêtes de H. Le problème de génération associé au transversaux, consiste à "lister" tous les transversaux minimaux d'un hypergraphe, c'est-à-dire ceux qui ne contiennent aucun autre transversal. Je parlerai enfin d'un cas particulier du problème de génération des transversaux minimaux qui est la génération des dominants minimaux d'un graphe.
]
13/03/2012 Christophe Tollu Combinatoire fine des représentations des groupes symétriques et linéaires
06/03/2012 Journées ALEA (4-9 mars)
06/03/2012 Gérard H. E. Duchamp Les mécanismes de perturbation du shuffle (théorèmes de structure) [abstract.html
Lorsque la structure tensorielle n'est pas déformée, on a tout un univers de déformations du shuffle par addition d'un terme de type Hofmann. Lorsque le coproduit associé à ce terme est dualisable, on obtient des bigèbres. On examine ici les théorèmes fondamentaux qui gouvernent les structures de ces bigèbres (travail en cours). Si le temps le permet, la séance sera suivie d'un entrainement au calcul tensoriel.
]
06/03/2012 Gérard H. E. Duchamp Quantum and Hopf I : FQSym and a question of C. Reutenauer [abstract.html
We tell the story of FQSym and its link to Combinatorial Physics through FQSymq and MQSym.
]
28/02/2012 Viviane Pons Les bases de l'anneau des polynômes en Sage [abstract.html
L'anneau des polynômes en n variables est souvent vu de façon récursive comme l'anneau des polynômes en 1 variable à coefficients dans les polynômes à n-1 variables. Nous montrons une approche différente qui étudie l'anneau comme une somme linéaire de vecteurs d'entiers de taille n : les exposants des monômes. A partir d'opérations simples sur les vecteurs, on obtient des actions sur les polynômes. Nous définissons des opérations de différences divisées à partir desquelles nous obtenons des bases linéaires de l'anneau des polynômes. Ces bases apparaissent dans le contexte de la géométrie algébrique et peuvent être vues comme des généralisations de certaines bases des polynômes symétriques. Tout l'exposé sera illustré de calculs effectués à partir du logiciel Sage.
]
28/02/2012 Pavel Salimov Open problems on maximal pattern complexity of infinite words [abstract.html
A pattern T={t_0 < t_1 <...} is a containing 0 finite subset of N. A pattern complexity p_x(T) of an infinite word x: N->{0,1} on pattern T is a number of different words of the form x_{t_0}x_{t_1}... Maximal pattern complexity of x is the function p_x(n) = sup_{|T|=n} p_x(T) of n that takes a maximal value of all pattern complexities of x over patterns of cardinality n. In the talk, I'll describe some properies of this function, compare it to the other well-studied measures of complexity, give an example of calculating it and outline some open problems related to it.
]
28/02/2012 Gérard H. E. Duchamp Matrices tassées et convolution [abstract.html
On rappelle la construction des algèbres de Hopf MQSym et LDiag, puis on étudie le groupe de Lie du voisinage de l'unité pour la convolution dans ces algèbres. Une démonstration explicite du théorème de Cartier-Quillen-Milnor-Moore à l'aide de ce groupe de Lie est possible en général, elle est donnée et on tente de dégager les premiers éléments de combinatoire qui en découlent pour ces algèbres de Hopf.
]
27/02/2012 Rencontre « Combinatorics of Mathematical Renormalization »
21/02/2012 Algorithms and Permutations (20-21 février)
21/02/2012 Gérard H. E. Duchamp Ordered infinite products in analysis and combinatorial applications III [abstract.html
We continue our exploration of the combinatorics of groups.
Function spaces are used in order to dualize the product : typically the algebraic dual of the group algebra k[G] is the full function space kG. In many cases, given a function φ∈ kG, there exists no nice formula for φ(fg).
But, if we restrict φ to some subspaces, the expression of φ(fg) can be nicely split. Examples will be taken in : Faà di Bruno formula, Free group, Noncommutative Symmetric function. If time permits, we will treat some points of the theory of deformation and some combinatorial aspects of quantum groups.
]
14/02/2012 Alain Plagne Quelques exos de théorie additive des nombres
14/02/2012 Alain Plagne Une introduction aux aspects combinatoires de la théorie additive des nombres
14/02/2012 Hoang Ngoc Minh
14/02/2012 Gérard H. E. Duchamp Ordered infinite products in analysis and combinatorial applications II [abstract.html
We pursue our exploration of infinite products by examples of complete monoidal factorizations and applications to "Lie" groups which are classic in combinatorics (Riordan, Haussdorff). We construct the Faà di Bruno Hopf algebra through a very simple specialization of the exponential formula. This talk is meant to be a partial contribution to F4M sessions.
]
07/02/2012 Mathieu Feuillet Comportement transitoire des processus d'Ehrenfest et d'Engset [abstract.html
Nous considérons deux processus stochastiques classiques : les urnes d'Ehrenfest, introduites en 1907 pour la théorie cinétique des gaz pour décrire les échanges de chaleur entre deux corps et le modèle d'Engset introduit en 1918 et qui est, avec le modèle d'Erlang, un des tous premiers modèles stochastiques de réseaux de communication. Nous proposons d'étudier le comportement asymptotique de la distribution des temps d'atteinte de ces deux processus lorsque le nombre de particules ou d'utilisateurs croît vers l'infini. En particulier, nous obtenons des résultats sur les temps d'atteinte de frontière. Cette étude repose sur des techniques de martingales et notamment sur une famille de martingales positives qui est l'équivalent pour le processus d'Ehrenfest des martingales exponentielles utilisées pour l'étude des marches aléatoires et du mouvement brownien.
]
07/02/2012 Basile Morcrette Urnes de Pólya : le miracle de la résolution par combinatoire analytique [Slides.pdf] [abstract.html
Les modèles d'urnes de Pólya sont des objets très simples mais pour lesquels de nombreuses questions restent ouvertes. Depuis 2005, une approche utilisant la combinatoire analytique s'est développée (Flajolet-Gabarro-Pekari, puis Flajolet-Dumas-Puyhaubert). Nous verrons, à travers des exemples concrets, comment la combinatoire analytique permet d'appréhender ces modèles. Les exemples proposés proviendront des fonctions booléennes, des k-arbres, ainsi que des modèles de croissance de population.
]
07/02/2012 Gérard H. E. Duchamp Ordered infinite products in analysis and combinatorial applications (The end of mathematical theories?) [abstract.html
We explore the notions of summability and multipliability as they are developed classically in analysis. We give examples in combinatorics where infinite products are supplied and, using the concept of generalized sequence, we give a rigorous framework for these products. Also a contribution to F4M via the exponential formula.
]
31/01/2012 Harald Andrés Helfgott Lattice dimers : asymptotics [abstract.html
Soit R une région finie dans le plan carrelé, il y a un nombre fini de manières de la recouvrir avec des dominos. Choisissons un recouvrement au hasard de manière uniforme. Quelle est la probabilité de trouver une configuration donnée dans un endroit donné ? Dans le contexte de problèmes de recouvrement, les deux régions plates finies les plus étudiées sont probablement le rectangle (depuis Kasteleyn (1961)) et le diamant aztèque (Elkies, Kuperberg, Larsen et Propp (1992)). Ces deux cas illustrent deux extrêmes de comportement asymptotique. Les probabilités des configurations locales dans un rectangle ont été déterminées par Kenyon (1997). Nous verrons comme déterminer de manière exacte les probabilités des configurations locales dans un diamant aztèque, avec une esquisse des asymptotiques. Les résultats (et leurs preuves!) sont nettement différents de ceux du cas rectangulaire.
]
31/01/2012 Harald Andrés Helfgott Lattice dimers : enumeration [abstract.html
Soit R une région finie dans le plan carrelé, il y a un nombre fini de manières de la recouvrir avec des dominos. Choisissons un recouvrement au hasard de manière uniforme. Quelle est la probabilité de trouver une configuration donnée dans un endroit donné ? Dans le contexte de problèmes de recouvrement, les deux régions plates finies les plus étudiées sont probablement le rectangle (depuis Kasteleyn (1961)) et le diamant aztèque (Elkies, Kuperberg, Larsen et Propp (1992)). Ces deux cas illustrent deux extrêmes de comportement asymptotique. Les probabilités des configurations locales dans un rectangle ont été déterminées par Kenyon (1997). Nous verrons comme déterminer de manière exacte les probabilités des configurations locales dans un diamant aztèque, avec une esquisse des asymptotiques. Les résultats (et leurs preuves!) sont nettement différents de ceux du cas rectangulaire.
]
31/01/2012 Olivier Bodini F4M (1) : Constructeurs de Flajolet
25/01/2012 Journées du GDR-IM (25-26 janvier)
24/01/2012 Michel Rigo Combinatoire des jeux, des mots et numération [Slides.pdf] [abstract.html
Dans la première partie de l'exposé, nous présenterons quelques concepts classiques de la théorie des jeux combinatoires : définition d'un jeu, quelques exemples comme le jeu de Nim, Wythoff ou Chomp!, graphe et noyau d'un jeu, position perdante/gagnante, nim-somme, fonction de Sprague-Grundy et somme de jeux, etc.

Ensuite, nous montrerons à travers le "célèbre" jeu de Wythoff, variante du jeu de Nim, des liens existant avec la combinatoire des mots. En effet, il est assez facile de vérifier que le mot de Fibonacci abaababaab..., unique point fixe du morphisme f(a)=ab et f(b)=a, code exactement les positions perdantes du jeu de Wythoff. En outre, des liens entre les mots substitutifs engendrés par morphisme itéré et les systèmes de numération sont bien connus (la voie a été ouverte par Cobham dans son papier de 1972 sur les suites k-automatiques). Ainsi, on peut aussi caractériser les positions perdantes du jeux de Wythoff à l'aide de la numération de Zeckendorf construite sur la suite de Fibonacci 1,2,3,5,8,... Cette caractérisation repose sur des propriétés syntaxiques (testables par automate fini) des représentations dans ce système.

Partant de ces constatations, nous présenterons, dans la dernière partie de l'exposé, quelques travaux récents montrant les interactions "fructueuses" existant entre jeux combinatoires, mots infinis engendrés par morphisme et systèmes de numération associés. Nous évoquerons les questions suivantes : étant donné un mot infini comme le mot de Tribonacci point fixe du morphisme f(a)=ab, f(b)=ac, f(c)=a, peut-on définir un jeu dont les positions perdantes sont codées par ce mot ? Existe-t-il des variantes du jeu de Wythoff (on change l'ensemble des coups admissibles à jouer) possédant le même ensemble de positions perdantes ? Toute suite de Beatty homogène donne-t-elle naissance à un jeu combinatoire invariant pour lequel l'ensemble des coups disponibles ne dépend pas de la position de jeu ?

Quelques références :

A. Fraenkel, Heap Games, Numeration Systems and Sequences, Annals of Combin.. 2 (1998), 197–210.
A. Fraenkel, How to beat your Wythoff games’ opponent on three fronts, Amer. Math. Monthly 89 (1982), 353–361.
voir aussi les pages de Aviezri Fraenkel http://www.wisdom.weizmann.ac.il/~fraenkel/
E. Duchêne, M. Rigo, A morphic approach to combinatorial games : the Tribonacci case, Theor. Inform. Appl. 42 (2008), 375-393.
E. Duchêne, M. Rigo, Invariant games, Theoret. Comp. Sci. 411 (2010), 3169-3180, http://orbi.ulg.ac.be/handle/2268/35496
E. Duchêne, A. Fraenkel, R. Nowakowski, M. Rigo, Extensions and restrictions of wythoff's game preserving wythoff's sequence as set of P positions, to appear in J. Combinat. Theory Ser. A 117 (2010), 545-567, http://orbi..ulg.ac.be/handle/2268/17591

http://www.discmath.ulg.ac.be/publi.html

pour une référence "grand public" sur les jeux combinatoires, voir par exemple les notes :
Thomas S. Ferguson, UCLA, http://www.math.ucla.edu/~tom/Game_Theory/Contents.html

Enfin, pour un survol sur les numérations (avec quelques remarques sur les jeux combinatoires), cf.

M. Rigo, Numeration Systems: a Link between Number Theory and Formal Language Theory, Proceedings of Developments in Language Theory, London, Ontario, Canada (2010), Lect. Notes in Comput. Sci. 6224, 33-53 Springer-Verlag (2010), http://orbi.ulg.ac.be/handle/2268/35488

]
24/01/2012 Gérard H. E. Duchamp Physique combinatoire : chemins, diagrammes de Ferrers et matrices de transfert [abstract.html
On part d'un opérateur montant M et d'un opérateur descendant D et on étudie le problème physique du "paquet de transfert" (l'ensemble des histoires qui mènent d'un niveau n au niveau n+k). La série génératrice de toutes ces histoires est un langage sur l'alphabet {M,D} qui se spécialise en des fractions continues doubles. D'autre part, l'histoire des réécritures d'une chaîne en M et D se retrouve dans les statistiques de placements de tours (rook numbers) sur des diagrammes de Ferrers qui donne très simplement les constantes de structures de HW. Ceci conduit aux HW-graphes et à leurs couplages qui à leur tour peuvent être déduits de la trace des calculs sur un centre infiniment engendré. Voir:
  • Combinatorial Models of Creation-Annihilation Pawel Blasiak, Philippe Flajolet ([Arxiv])
  • Combinatorial Algebra for second-quantized Quantum Theory P. Blasiak, G. H. E. Duchamp, A. I. Solomon, A. Horzela, K. A. Penson ([Arxiv])
]
17/01/2012 Gérard H. E. Duchamp Exercices, exemples et preuves
17/01/2012 Axel Bacher Chemins et animaux : applications de la théorie des empilements de pièces [abstract.html
Le but de cet exposé est d'établir des résultats énumératifs sur certaines classes de chemins et d'animaux. Ces résultats sont obtenus en appliquant la théorie des empilements de pièces développée par Viennot. Nous étudions les excursions discrètes (ou chemins de Dyck généralisés) de hauteur bornée ; nous obtenons des résultats énumératifs qui interprètent combinatoirement et étendent des résultats de Banderier, Flajolet et Bousquet-Mélou. Nous décrivons et énumérons plusieurs classes de chemins auto-évitants, dits chemins faiblement dirigés. Ces chemins sont plus nombreux que les chemins prudents qui forment la classe naturelle la plus grande jusqu'alors. Nous calculons le périmètre de site moyen des animaux dirigés, prouvant des conjectures de Conway et Le Borgne. Enfin, nous obtenons des résultats nouveaux sur l'énumération des animaux de Klarner et les animaux multi-dirigés de Bousquet-Mélou et Rechnitzer.
]
17/01/2012 Gérard H. E. Duchamp Foncteurs, constructeurs, grammaires, espèces et opérades : que proposer ? (atelier)
10/01/2012 Hanane Tafat Bouzid Sur la diversité des lois limites d'expressions régulières
10/01/2012 Lucas Gérin Distances en percolation et TASEP [abstract.html
La percolation de paramètre p, c'est ce qui reste dans Z² quand on efface chaque arête indépendamment avec probabilité 1-p. Quand p est proche de un, il y a une composante connexe infinie. Le TASEP, ce sont des voitures qui avancent de façon aléatoire sur une seule voie, sans se doubler et sans se rentrer dedans. A priori, ça n'a rien à voir.
Le but de cet exposé est de montrer que des estimées sur le TASEP permettent d'obtenir des estimées sur certaines distances dans la composante infinie de percolation, quand p est très proche de un. (Travail avec A.-L.Basdevant et N.Enriquez).
]
10/01/2012 Charles Delorme Graphes distance-réguliers et partitions équitables [Slides.pdf] [abstract.html
On sait que les graphes distance-réguliers ou distance-birégulier se caractérisent par le fait que les distances à n'importe quel sommet réalisent de partitions équitables. Pas de panique: les termes mystérieux seront illustrés par des exemples. Qu'arrive-t-il si on prend les distances à d'autres sous-ensembles de sommets?
]
10/01/2012 Gérard H. E. Duchamp Espaces fonctionnels et analyse harmonique pour la combinatoire
03/01/2012 Gérard H. E. Duchamp Fils rouges et programme de l'année
03/01/2012 Nicolas Broutin Recherches partiellement spécifiées dans les arbres multidimensionnels [Slides.pdf] [abstract.html
Nous considérons la recherche d'éléments dans des structures de données multidimensionnelles (quad trees, k-d trees), en particulier lorsque certaines coordonnées ne sont pas spécifiées (partial match query). Nous supposons que les données consistent en un ensemble de points uniformes dans le carré unité. Pour ce modèle, dans une structure contenant n points, Flajolet et Puech ont montré que le nombre de noeuds C_n(U) à visiter pour répondre à une requête demandant l'ensemble des données dont la première coordonnée est x=U est tel que E[C_n]\sim κ nβ, où κ et β sont des constantes explicites. Nous développons une approche basée sur l'analyse des coûts C_n(s) pour des requêtes à x=s fixé. Nous donnons en particulier des estimations précises de la variance et de la distribution limite de C_n(s) lorsque n\to\infty. Nos résultats permettent de décrire un processus limite pour C_n(s) lorsque s varie dans (0,1).

Travail en collaboration avec Ralph Neininger et Henning Sulzbach.

]
03/01/2012 Brigitte Chauvin Chaînes de Markov à mémoire variable et tries des suffixes [Slides.pdf] [abstract.html
Dans un premier temps, on expliquera comment on produit des mots, au sens d'une source dynamique probabiliste, avec une source ``VLMC'' (Variable Length Markov Chain). Puis, pour une famille de sources VLMC associées à un ``peigne infini'', on construira le trie des suffixes correspondant. On trouvera l'asymptotique de sa hauteur et de son niveau de saturation, qui ne sont pas toujours logarithmiques. On fera le lien entre ce comportement asymptotique et les propriétés de mélange de la source.
]
20/12/2011 Hanane Tafat Bouzid Sur la diversité des motifs dans les lois limites d'expressions régulières
20/12/2011 Christophe Tollu Partitions virtuelles, z-mesures et groupe symétrique infini (d'après divers auteurs)
20/12/2011 Andrea Sportiello A (completely new & simpler!) proof of Razumov-Strogonov
14/12/2011 Conférence Philippe Flajolet and Analytic Combinatorics (14-16 décembre)
13/12/2011 Donatella Merlini A survey on Riordan arrays [Slides.pdf] [abstract.html
Historically, there exist two versions of the Riordan array concept. The older one (better known as recursive matrix and introduced by Barnabei, Brini and Nicoletti) consists of bi-infinite matrices, deals with formal Laurent series and has been mainly used to study algebraic properties of such matrices. The more recent version consists of infinite, lower triangular arrays, deals with formal power series and has been used to study combinatorial problems. The name Riordan arrays has been coined in 1991 by Shapiro, Getu, Woan and Woodson with the aim of defining a class of infinite lower triangular arrays with properties analogous to those of the Pascal triangle. This concept has been successively studied by Sprugnoli in the context of the computation of combinatorial sums. Some other important aspects of the theory have been studied later by Merlini, Sprugnoli and Verri and the literature about Riordan arrays is vast and still growing. After describing the classical properties about this concept, in this talk we present some recent results concerning Riordan arrays related to binary words avoiding a pattern p and show that every Riordan array induces two characteristic combinatorial identities in three parameters n, k, m in Z which are valid in the bi-infinite realm of recursive matrices.
]
13/12/2011 Mireille Bousquet-Mélou Sur le profil des arbres plongés [abstract.html
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.

]
13/12/2011 Christophe Tollu Groupe unitaire infini et ses caractères
06/12/2011 Luciano Norberto Grippo Forbidden subgraph characterizations of some classes of intersection graphs [Slides.pdf] [abstract.html
Given a finite family of non-empty sets F. The intersection graph of F is obtained by representing each set by a vertex, two vertices being adjacent if and only if their corresponding sets intersect. In this talk we will focus on two important intersection graph classes, namely circular-arc graphs (intersection graphs of arc on a circle) and circle graphs (intersection graphs of chords on a circle). We will present some partial characterizations by forbidden induced subgraphs for these classes. Let F be a family of graphs. A graph $G$ is said to be a probe--F graph if its vertex set can be partitioned into two sets: a set P of probe vertices and a stable set N of non-probe vertices in such a way that edges, whose endpoints belongs to N, can be added to G so that the resulting graph belongs to F. We will present some forbidden induced subgraphs characterizations for probe interval graphs and probe unit interval graphs on superclasses of cographs. Finally, we will present a complete forbidden induced subgraphs characterization of probe block graphs. This talk is based on a mix of joint works with F. Bonomo, G. Durán and M. Safe.
]
06/12/2011 Christian Lavault & Hoang Ngoc Minh & Gérard H. E. Duchamp Quelques propriétés du shuffle
29/11/2011 Christian Lavault & Hoang Ngoc Minh & Cyril Banderier & Hanane Tafat Exercice sur l'identité shuffle de Minh-Petitot
29/11/2011 Daniel Posner Efficient solutions for the λ-coloring problem on classes of graphs [Slides.pdf] [abstract.html
A λ-coloring of a graph is a function that assigns frequencies (represented by natural numbers) to its vertices in such way that if two vertices are adjacent, then their frequencies differ by at least two, and if two vertices share a common neighbor, then their frequencies must be different. Motivated by mobile wireless networks, the λ-coloring problem aims to use the minimum frequency spectrum without interferences, i.e., respecting the distances restrictions. It is known that the decision version of this problem is NP-complete even for simple classes of graphs such as bipartite graphs, split graphs, and planar graphs. In this seminar we talk about recent results in $lambda$-coloring, including efficient solution when it is restricted to the classes of split permutation graphs and (q, q-4)-graphs, q fixed. Joint work with Marcia R. Cerioli.
]
29/11/2011 Christophe Tollu Permutations aléatoires (infinies), partitions aléatoires (infinies) et motivations via la théorie des représentations
22/11/2011 Journée Renormalisabilité en gravité quantique : aspects combinatoires, algébriques et analytiques à l'IHP
15/11/2011 Ladji Kane Shuffles et stuffles
15/11/2011 Robert Cori Quelques problèmes combinatoires inspirés par le modèle physique du tas de sable [abstract.html
Cet exposé se veut introductif et élémentaire. Je présenterai la version combinatoire du modèle physique du tas de sable comme un jeu consistant à déplacer des jetons sur les sommets d'un graphe connexe. J'introduirai et je donnerai les propriétés des configurations récurrentes de jetons, puis les bijections entre ces configurations et les arbres recouvrants du graphe. Une incursion dans les polynômes de Tutte est ensuite prévue, puis une investigation sur les algorithmes de tirage aléatoire d'arbres recouvrants. Après avoir rappelé ce panorama de travaux remontant aux années 1990-2000, quelques résultats dans des directions nouvelles seront évoqués.

Quelques articles introductifs :

Deepak Dhar (1999)
Studying Self-Organized Criticality with Exactly Solved Models
arxiv.org/abs/cond-mat/9909009

Dominique Rossin et Robert Cori
On the sandpile group of dual graphs
European Journal of Combinatorics 21 (2000) 447-459

Chip-Firing and Rotor-Routing on Directed Graphs
Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuyal Peres, James Propp and David B. Wilson
In and Out of Equilibrium 2
Progress in Probability, 2008, Volume 60, 331-364.

]
15/11/2011 Gérard H. E. Duchamp & Hoang Ngoc Minh Déformations et perturbations, des nouvelles des polyzêtas
09/11/2011 Flavia Bonomo On the b-coloring problem [abstract.html
A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G is the maximum number t such that G admits a b-coloring with t colors.Several problems related to b-coloring of graphs have been introduced in the literature. Recently, the theory of b-colorings of graphs has been applied in to some clustering problems in data mining processes. In this talk, we will summarize the last algorithmic and theoretical results obtained on b-coloring and the related notions of b-perfection, b-continuity and b-monotonicity within some graph classes. This is a mix of joint works with C. Betancur, G. Duran, I. Koch, F. Maffray, J. Marenco and M. Valencia-Pabon.
]
08/11/2011 Dominique Manchon Deux algèbres de Hopf définies à partir de découpages de graphes
08/11/2011 Patrick Dehornoy Sur la distance de rotation entre deux arbres binaires [Slides.pdf] [abstract.html
Le problème est de construire des arbres binaires éloignés vis-à-vis de la distance de rotation, ce qui équivaut à construire des expressions parenthésées éloignées vis-à-vis de l'associativité, ou encore des triangulations de polygone éloignées vis-a-vis de l'échange de diagonales. On présentera la magnifique solution de Sleator-Tarjan-Thurston basée sur la géométrie hyperbolique, qui est optimale mais valable seulement pour une taille assez grande (non effective), ainsi qu'une méthode combinatoire basée sur une notion de séparatrice dans les associaèdres, qui est (pour le moment) non optimale, mais valable pour toute taille.
]
08/11/2011 Laurent Poinsot Soutenance d'HDR : Contributions à l'algèbre, à l'analyse et à la combinatoire des endomorphismes sur les espaces de séries [Slides.pdf] [abstract.html
Le dual topologique de l'espace des séries en un nombre quelconque, éventuellement infini, de variables non commutatives avec un corps topologique séparé de coefficients, pour la topologie produit, n'est autre que l'espace des polynômes. Il en résulte de façon immédiate que les endomorphismes continus sur les séries sont exactement les matrices infinies mais finies en ligne. Les matrices triangulaires infinies, puisque formant une algèbre de Fréchet, disposent quant à elles d'un calcul intégral et différentiel, que nous développons dans un cadre assez général, et qui permet d'établir une correspondance exponentielle-logarithme de type Lie. Nous déployons ces outils sur l'algèbre de Weyl (à deux générateurs) réalisée fidèlement comme une algèbre d'opérateurs agissant continûment sur l'espace des séries formelles (en une variable). Puis nous démontrons que chaque endomorphisme d'un espace vectoriel de dimension infinie dénombrable peut s'obtenir explicitement sous la forme de la somme d'une famille sommable en des opérateurs plus élémentaires, les opérateur d'échelle (généralisation de l'algèbre de Weyl), précisant de la sorte le théorème de densité de Jacobson. Par dualité (topologique) un résultat similaire concernant les opérateurs continus sur un espace de combinaisons linéaires infinies tombent presque gratuitement. Par ailleurs nous développons la notion d'algèbre (réduite) large d'un monoïde à zéro (obtenue par complétion de l'algèbre réduite) qui nous permet de calculer de nouvelles formules d'inversion de Möbius ainsi que des séries de Hilbert.

- Le jury : Jacques Alev, Claude Carlet , Frédéric Chapoton, Patrick Dehornoy, Gérard Duchamp, Loïc Foissy, Dominique Manchon, Frédéric Patras, Laurent Rigal et Jean-Yves Thibon.

]
25/10/2011 collectif séance d'exo (Cédric Boutillier + Jesper Lykke Jacobsen) [Slides.pdf]
25/10/2011 Jesper Lykke Jacobsen A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings [abstract.html
voir article ArXiV http://fr.arxiv.org/abs/1003.4847
]
25/10/2011 Cédric Boutillier Formalisme d'opérateurs vertex pour l'étude des grandes partitions planes [abstract.html
On introduira le formalisme utilisé par Okounkov et Reshetikhin pour étudier les partitions planes aléatoires, basé sur une représentation de gl(∞). Après avoir expliqué comment calculer avec ce formalisme les statistiques locales pour ces objets, on présentera le phénomène de forme limite déterministe lorsque la taille de ces objets tend vers l'infini. On discutera en particulier l'influence de la forme du « mur du fond » sur lequel s'appuie la partition plane sur ces propriétés statistiques. Travail en collaboration avec S. Mkrtchyan, N. Reshetikhin et P. Tingley.

Références :

pour le formalisme :
A. Okounkov and N. Reshetikhin, Correlation function of Schur process with application to local geometry of a random 3-dimensional Young diagram math.CO/0107056, J. Amer. Math. Soc. 16 (2003), no. 3, 581–603.

notre article :
arxiv.org/pdf/0912.3968

]
18/10/2011 collectif Séance d'exo (Christiane Frougny)
18/10/2011 Christiane Frougny Sur l'addition en parallèle [abstract.html
Il est bien connu que l'addition dans un système de numération standard a une complexité linéaire, ce qui est trop lent pour faire un processeur arithmétique efficace. En 1961, Avizienis a donné un algorithme parallèle d'addition en base 10 avec les chiffres {-6, -5, ..., 5, 6} où la retenue ne se propage pas. On obtient ainsi une complexité (en parallèle) constante. Dans le langage de la dynamique symbolique, une telle addition est une fonction locale (sliding block code). Cette technique est utilisée pour accélérer les algorithmes de multiplication et de division.

Dans ce travail nous nous intéressons à des systèmes de numération où la base est un nombre algébrique beta, |beta|>1. Quand tous les conjugués algébriques de beta ont un module différent de 1, on peut trouver un alphabet symétrique de chiffres signés entiers sur lequel faire l'addition en parallèle. Cet algorithme est une généralisation de celui d'Avizienis.

L'algorithme d'addition est simple, mais l'alphabet obtenu est en général plus grand que nécessaire. Nous donnons des bornes inférieures sur la cardinalité minimale d'un alphabet permettant de faire l'addition en parallèle. Nous présentons ensuite une série de cas où la borne est atteinte.

Travail en collaboration avec Edita Pelantová et Milena Svobodová (CTU, Prague)

]
18/10/2011 Matthieu Deneufchâtel Factorisation de Schützenberger, structures libres combinatoires et bases duales [Slides.pdf] [abstract.html
Cet exposé a pour but de présenter la factorisation de Schützenberger dans un cadre général. Nous présentons un théorème général qui permet de l'écrire dans le cas d'une algèbre de Lie quelconque et rappelons les outils nécessaires à sa formulation dans le cadre des structures partiellement commutatives. Nous terminerons en donnant quelques idées concernant des travaux en cours relatifs à l'aller-retour entre bases de PBW et de Radford.
]
11/10/2011 collectif séance d'exo (Valérie Berthé)
11/10/2011 Valérie Berthé Substitutions et transcendance [Slides.pdf] [abstract.html
Les substitutions (c'est-à-dire les morphismes de monoïde libre) engendrent des mots infinis qui peuvent être vus comme des développements soit de réels, soit de séries formelles de Laurent dans des corps algébriques. Dans le cas de substitutions de longueur constante (suites automatiques), les séries ainsi produites sont algébriques. Dans le cas des réels, on obtient en général des nombres transcendants. Après une première partie de survol autour de ces divers types de comportements algébriques, nous nous intéresserons aux développements dits S-adiques, où il ne s'agit plus d'itérer la même substitution, mais de composer un nombre fini de substitutions.
]
11/10/2011 Miguel Mendez Combinatorial differential equations and shift-plethysm [Slides.pdf] [abstract.html
The combinatorial solution to an autonomous differential equation y´=φ(y) was shown to be the family of increasing φ-enriched trees (Leroux-Viennot). We introduce a generalization of this kind of differential equations that uses the operation of shift-plethysm instead of usual substitution. Its solution is again a family of φ-enriched trees with labels that give information related to the length of each branch.
]
04/10/2011 Thomas Fernique Quasicristaux : structure et croissance [abstract.html
Les quasicristaux sont des matériaux ordonnés, à l'instar des cristaux habituels, mais sans être périodiques contrairement à ces derniers. Découverts en 1982 et "officialisés" après 10 ans de controverses, ils ont contribué à relancer l'étude des pavages non périodiques, qui en sont un modèle répandu. Dans cet exposé, on s'intéresse à deux problèmes théoriques principaux de ce modèle : d'une part la caractérisation de pavages non périodiques par des contraintes locales (structure des quasicristaux), d'autre part la recherche et l'étude d'un méchanisme de formation de ces pavages qui soit physiquement plausible (croissance des quasicristaux). On donnera quelques résultats marquants ainsi que quelques pistes à explorer.
]
04/10/2011 Jean-Paul Allouche Séries de Dirichlet automatiques (ou comment une constante de Flajolet-Martin ne fut pas evaluée) [abstract.pdf]
04/10/2011 pot de rentrée du séminaire (12h-14h)
04/10/2011 Brigitte Vallée De l'importance de la discipline des sources [Slides.pdf] [abstract.html
En algorithmique, on manipule très souvent des mots, notamment dans l'algorithmique du texte ; plus souvent encore, on manipule ce qu'on appelle communément des clés, notamment dans les algorithmes de tri ou de recherche, ou dans les bases de données. Dans une perspective plus réaliste, il faut vraiment considérer une clé comme une suite finie de symboles, c'est-à-dire comme un mot. On remplace alors le coût unitaire d'une comparaison entre deux clés par le coût de la comparaison entre deux mots, égal au nombre de symboles comparés. L'algorithmique générale devient alors de l'algorithmique du texte, et le processus qui produit les mots, appelé source, acquiert alors une grande importance.
Notre programme, décrit dans l'exposé, est donc le suivant :
1. Donner un sens à ce qu'on appelle une "source générale", opérer une classification des sources, en exhibant des sous-classes intéressantes, reliées notamment à des systèmes dynamiques.
2. Définir une série génératrice (de type Dirichlet) reliée canoniquement à la source et relier la classification des sources à la classification (analytique) de leurs séries de Dirichlet.
3. Exhiber une propriété importante de la source, appelée la "discipline", et, dans le cas des sources dynamiques, donner des conditions suffisantes qui entraînent la discipline.
]
27/09/2011 Luc Lapointe Jack superpolynomials, clustering properties and the super-Virasoro algebra III
27/09/2011 Luc Lapointe Jack superpolynomials, clustering properties and the super-Virasoro algebra II
27/09/2011 Luc Lapointe Jack superpolynomials, clustering properties and the super-Virasoro algebra I [abstract.html
The Jack superpolynomials are symmetric polynomials, involving commuting and anticommuting variables, that are orthogonal eigenfunctions of a certain integrable model known as the supersymmetric Calogero-Moser-Sutherland model.
We will discuss how the usual properties of the Jack polynomials can be extended to the Jack superpolynomial case. We will mainly focus on the fact that classes of Jack superpolynomials at special values of the coupling constant admit clusters of size at most k, that is, they vanish when k+1 variables are equal but not (conjecturally) when only k are identified (a sort of generalization of the Pauli exclusion principle).
We will also describe the connection between the super-Virasoro algebra and the vanishing of the Jack superpolynomials.
]
20/09/2011 Séminaire SLC (18-21 septembre)
08/09/2011 Exposés-présentation générale des 5 équipes du LIPN
19/07/2011 Apostol Vourdas Harmonic Analysis on some direct and inverse limits
19/07/2011 Christophe Tollu Autour du "Ring Theorem", (d'après Okunkov, Kerov, Vershik)
12/07/2011 Gérard H. E. Duchamp Théorie des automates et renormalisation puis discussion
12/07/2011 Pierre Simonnet Clôtures rationnelles et algorithme de Berry-Sethi
12/07/2011 Christophe Tollu Extrémalité et caractères
05/07/2011 Ahmed Djebbar Histoire(s) des mathématiques arabes [.ppt]
05/07/2011 Guy Louchard The Saddle point method in combinatorics asymptotic analysis: successes and failures (A personal view) [Slides.pdf]
05/07/2011 Étienne Grandjean Complexité, logique et algorithmes [Slides.pdf]
05/07/2011 Sidi Mohamed Sedjelmaci L'algorithme d'Euclide en parallèle [Slides.pdf]
05/07/2011 Wojciech Szpankowski Shannon legacy and beyond [abstract.html
Information is the distinguishing mark of our era, permeating every facet of our lives. An ability to understand and harness information has the potential for significant advances. Our current understanding of information dates back to Claude Shannon's revolutionary work in 1948, resulting in a general mathematical theory of reliable communication that formalized the modern digital communication and storage principles, paved the way for the Internet, DVDs and iPods of today. While Shannon's information theory has had profound impact, its application beyond storage and communication poses foundational challenges. The National Science Foundation has just established a Science & Technology Center on the Science of Information to meet the new challenges posed by the rapid advances in networking, biology and knowledge extraction. Its missions is to develop rigorous principles guiding the extraction, manipulation, and exchange of information, integrating elements of space, time, structure, semantics and context. In this talk, after reviewing main results of Shannon, we then attempt to identify some features of information encompassing structural, spatio-temporal, and semantic facets of information. If time allows, we present one new result on a fundamental lower bound for structural compression and describe a novel algorithm achieving this lower bound for graphical structures.
]
05/07/2011 Journée en l'honneur de l'éméritat de Christian Lavault. Accueil et café
28/06/2011 Matthieu Deneufchâtel Autour des "objets de Lie" [Slides.pdf] [abstract.html
Dans cet exposé, je rappelle les définitions de différents objets apparentés par leur nom et que l'on peut ranger dans la classe des "objets de Lie". J'illustrerai aussi les liens qui les unissent et présente différents théorèmes importants, en particulier dans le mouvement actuel. Nous parlerons donc, entre autres, d'algèbre de Lie, de groupe de Lie, des théorèmes de Cartier-Quillen-Milnor-Moore et de Poincaré-Birkhoff-Witt.
]
28/06/2011 Gérard H. E. Duchamp Lie algebra Prim(H), CQMM theorem and combinatorial applications
21/06/2011 Ljuben Mutafchiev N-ary subtrees of Galton-Watson trees [abstract.pdf]
21/06/2011 Adrian Tanasa Hochschild cohomology and combinatorial Dyson-Schwinger equations in quantum field theory [Slides.pdf] [abstract.html
I will introduce in this talk the combinatorial Connes-Kreimer Hopf algebra of Feynman graphs, celebrated structure known to encode the combinatorics of renormalization in quantum field theory (QFT). Hochschild cocyles (associated to some particular graphs) will then be defined; this allows to write down the combinatorial Dyson-Schwinger equations (recursive equations in power series written in terms of these Hochschild cocyles). It is worth emphasizing that the Dyson-Schwinger equations can play a crucial role in non-perturbative QFTs. Several explicit examples will be given to illustrate these various notions. Based on: http://arxiv.org/abs/0907.2182
]
21/06/2011 Mathieu Lewin Renormalisation de charge pour un modèle non linéaire issu de l'électrodynamique quantique [abstract.html
La renormalisation est l'un des outils fondamentaux de la théorie quantique des champs. En particulier, en électrodynamique quantique, on doit renormaliser la charge et la masse de l'électron.
Dans cet exposé je présenterai un modèle non linéaire simplifié, basé sur l'opérateur de Dirac et prenant en compte la polarisation du vide, pour lequel il est possible de réaliser complètement la renormalisation de charge. Il s'agit d'un résumé de travaux en collaboration avec Gravejat (Paris- Dauphine), Hainzl (Tuebingen, Allemagne), Séré (Paris-Dauphine) et Solovej (Copenhague).
]
61/10/ 201 conférences FPSAC et AofA
07/06/2011 Alan Sokal Higher roots and Hadamard-product formulae [Slides.pdf] [abstract.pdf]
07/06/2011 Alan Sokal The leading root of the partial theta-function [Slides.pdf] [abstract.pdf]
31/05/2011 Thomas Krajewski Une preuve combinatoire de la formule des équerres de Postnikov [abstract.pdf]
31/05/2011 Ljuben Mutafchiev On certain statistics of random weighted partitions of large integers [abstract.pdf]
31/05/2011 Thomas Krajewski Polynômes de graphes et théorie quantique des champs [abstract.pdf]
24/05/2011 Alan Sokal Applications of the explicit implicit function formula and the exponential formula [Slides.pdf] [abstract.pdf]
24/05/2011 Gwendal Collet Cartes avec un nombre fixé de trous [Slides.pdf]
24/05/2011 Alan Sokal Some wonderful conjectures (but almost no theorems) at the boundary between analysis, combinatorics and probability [Slides.pdf] [abstract.pdf]
17/05/2011 Hayat Cheballah Autour de la conjecture de Zeilberger [Slides.pdf] [abstract.html
On s'interesse ici a construire une bijection entre deux familles d'objets combinatoires : les ASMs et les TSSCPPs ou, selon Zeilberger, entre les triangles Gog et les triangles Magog. Jusqu'à présent, seule une bijection entre les trapèzes à une ligne était connue, et l'étape suivante, celle des trapèzes à deux lignes, semblait inaccessible. Nous proposons de résoudre ce problème grâce à l'utilisation d'un outil fondamental en combinatoire, l'involution de Schutzenberger. Cette construction laisse entrevoir la possibilité d'une solution complète du problème, en traitant les trapèzes à nombre arbitraire de lignes.
]
17/05/2011 Valentina Boeva Bioinformatics challenges in next-generation-sequencing era [abstract.html
"Next Generation Sequencing" represents a class of relatively new technologies (first results published in 2007) which enable sequencing millions of short nucleotide sequences (reads) in several days. I will briefly discuss several biological applications of "Next Generation Sequencing", such as ChIP-Seq, transcriptome sequencing, small-RNA sequencing, whole genome sequencing. I will summarize the main challenges of the primary steps data analysis: assembly or alignment of reads, normalization of read counts. If I have time I will also talk about "Next-Next Generation Sequencing" (first results published in 2010).
Références :
] [.ppt]
17/05/2011 Muriel Livernet Operades, algebres pre-Lie et algebres de Hopf [abstract.html
On montrera que l'algebre de Hopf de Connes et Kreimer, apparait de maniere naturelle comme construction d'algebre de Hopf provenant soit de l'operade preLie soit de l'operade NAP, que je definirais. Je donnerai d'autres exemples d'algebres de Hopf qui peuvent etre obtenus a partir de la theorie des operades.
]
10/05/2011 Gérard H. E. Duchamp Discussion et exos
10/05/2011 Maxime Crochemore Local repetitions in strings [Slides.pdf] [abstract.html
The analysis of repetition in strings constitutes a fundamental area of combinatorics on words due to important applications to text algorithms, data compression, music analysis, and biological sequences analysis, to quote a few. The talk surveys algorithmic methods used to locate repetitive segments in strings. It discusses the notion of runs that encompasses various types of periodicities considered by different authors. The analysis of related algorithms raises interesting combinatorial questions and conjectures.
]
10/05/2011 CALIN buffet et violons pour un an de CALIN !
10/05/2011 Gérard H. E. Duchamp et Adrian Tanasa Physique Combinatoire : les trois étages de la fusée
03/05/2011 Vincent Pilaud Le polytope des briques [Slides.pdf] [abstract.html
L'objet central de cet exposé est le graphe des flips sur les arrangements de pseudodroites avec points de contact couvrant un support donné. Il généralise les graphes de flips sur trois objets géométriques intéressants : les triangulations d'un polygone convexe, les pseudotriangulations d'un ensemble de points du plan en position générale, et les multitriangulations d'un polygone convexe. On s'intéresse en particulier à la polytopalité de ces graphes de flips. Par example, le graphe des flips sur les triangulations est le graphe de l'associahédre et le graphe des flips sur les pseudotriangulations est le graphe du polytope des pseudotriangulations. Pour les +multitriangulations, la question reste ouverte. Dans cet exposé, je rappellerai dans un premier temps les principales propriétés combinatoires de ces objets, en soulignant le lien avec les complexes des sous-mots du groupe symétrique définis par Knutson et Miller. Dans un deuxième temps, je présenterai la construction du "polytope des briques" d'un support. Son graphe est un sous-graphe du graphe des flips sur les arrangements de pseudodroites ayant ce support. Cette construction contient en particulier toutes les réalisations de l'associaèdre d'Hohlweg et Lange, qui apparaissent comme polytopes de briques de certains supports bien choisis. Travail en commun avec Francisco Santos (Université de Cantabrie).
]
26/04/2011 François Delbot Comparaison et évaluation en moyenne d'algorithmes d'approximation pour le problème du vertex cover [abstract.html
Dans la littérature, on considère souvent qu'un algorithme d'approximation polynomial est plus performant qu'un autre lorsqu'il possède un meilleur rapport d'approximation en pire cas. Cependant, il faut être conscient que cette mesure, désormais "classique", ne prend pas en compte la réalité de toutes les exécutions possibles d'un algorithme (elle ne considère que les exécutions menant à la plus mauvaise solution). Dans mes travaux, je me suis focalisé sur le problème du vertex cover et j'ai tenté de mieux "capturer" le comportement des ces algorithmes d’approximation en montrant que les performances moyennes d’un algorithme peuvent être décorélées des performances en pire cas, en évaluant les performances moyennes d’un algorithme et en comparant les performances de différents algorithmes (analytiquement et expérimentalement). J'ai également proposé un algorithme de liste et j'ai prouvé analytiquement qu'il retourne toujours une meilleure solution que celle construite par un autre algorithme de liste récent [ORL 2006] quand ils traitent la même liste de sommets (dans certains graphes particuliers, la différence de taille peut être arbitrairement grande). On constate dans ces études que les algorithmes 2-approchés étudiés sont ceux qui obtiennent les plus mauvaises performances en moyenne et que ceux qui ont les meilleurs comportements moyens ont de mauvais rapports d'approximation.
]
26/04/2011 Collectif Discussions
19/04/2011 Gérard H. E. Duchamp Discussion sur les techniques graphiques utilisées en Physique et programme (tentative)
19/04/2011 Wojciech Szpankowski Discrete divide and conquer recurrences [Slides.pdf] [abstract.html
Divide-and-conquer recurrences are one of the most studied equations in computer science. Yet, discrete versions of these recurrences still present some challenges. The discrete nature of this recurrence (represented by quantization) introduces certain oscillations not captured by the traditional Master Theorem of divide and conquer recurrence, for example due to Akra and Bazzi who primary studied the continuous version of the recurrence. We show how powerful techniques such as Dirichlet series, Mellin-Perron formula, and (extended) Tauberian theorems of Wiener-Ikehara can be used to provide a complete and precise solution to this basic computer science recurrence. We illustrate applicability of our results on several examples including a popular and fast arithmetic coding algorithm due to Boncelet for which we estimate its average redundancy and prove the Central Limit Theorem for the phrase length. This allows us to compare the redundancy of Boncelet's algorithm to the (asymptotically) optimal Tunstall scheme. Join work with M. Drmota (TU Wien)
]
12/04/2011 Razvan Gurau Discussion
12/04/2011 Juan Vera Phase Transition for the mixing time of Glauber Dynamics on Regular Trees at Reconstruction: Colorings and Independent Sets [Slides.pdf] [abstract.html
Glauber dynamics is a simple Markov chain used to sample (complex) spin distributions, such as colorings and independent sets, on graphs. We show that the mixing time of the Glauber dynamics for random k-colorings (and for the hard core model with boundary conditions) of the complete tree undergoes a phase transition around the reconstruction threshold. The central element of our result is a general technique that transforms a reconstruction algorithm into a set with poor conductance.
]
12/04/2011 Razvan Gurau The 1/N expansion in colored tensor models [Slides.pdf] [abstract.html
The 1/N expansion in colored tensor models
Abstract: Matrix models are one of the most versatile tools in theoretical physics with applications ranging from the theory of strong interaction, to string theory, critical phenomena and two dimensional quantum gravity.
The versatility of matrix models is largely due to their topological 1/N expansion dominated by graphs with spherical topology. In higher dimensions matrix models generalize to tensor models. The ordinary tensor models are plagued by singularities and do not admit a meaningful 1/N expansion.
In this talk I will show that by adding an extra ingredient (a coloring of the fields) the tensor models become manageable and admit a 1/N expansion dominated by graphs with spherical topology in arbitrary dimension.
]
05/04/2011 Aristide Baratin Aspects of group field theories [abstract.html
"Aspects of group field theories"
Group field theories (GFT) provide a higher dimensional generalization of matrix models. Just as the Feynman graphs of matrix models are ribbon graphs dual to Riemann surfaces, the graphs of a D-dimensional GFT are D-stranded graphs dual to triangulated (pseudo)-manifolds. They provide a new and promising framework for the study of quantum gravity, including a sum over all topologies. I will describe several new aspects of these theories, including a dual formulation as non-commutative field theories, which provide important insights on their geometrical meaning.
]
05/04/2011 Cyril Nicaud Mots de Lyndon aléatoires [abstract.html
Dans cet exposé je présenterai diverses propriétés combinatoires et algorithmiques des mots de Lyndon aléatoires. Je parlerai principalement de factorisation standard (travail avec F. Bassino et J. Clément) et de décomposition en mots de Lyndon. On verra des techniques analytiques et des techniques probabilistes pour aborder ce genre de questions. Le résultat principal est que l'on peut décomposer en mots de Lyndon en temps moyen sous-linéaire. On utilise pour cela une bonne compréhension de ce qu'est un mot aléatoire "typique" et des techniques d'algorithmique du texte.
]
05/04/2011 Aristide Baratin Combinatorial state sum invariants from categories [Slides.pdf] [abstract.html
"Combinatorial state sum invariants from categories"
'State sum models' are discrete functional path integrals. Using the combinatorics of the Pachner moves of the triangulation to convert a topological problem into an algebraic one, these models can be used to define manifold invariants and topological quantum field theories. Just as 3d state sum models, including quantum gravity, can be built using categories of group representations, 2-categories of 2-group representations may provide interesting state sum models for 4d quantum topology, if not quantum gravity. I will describe the construction of the first non-trivial example of a such models, based on the representations of a categorical version of the Euclidean group. I will show that this model shows up naturally in a combinatorial (state sum) reformulation of Feynman integrals for ordinary quantum field theories on 4d Euclidean spacetime.
]
01/04/2011 Hichem Kenniche Réseaux de capteurs sans fil de grande taille : quelques contributions à la modélisation et à l'algorithmique [abstract.html
Date: Wed, 16 Mar 2011 10:29:36
From: Hichem.Kenniche
j'ai le plaisir de vous inviter à la soutenance de ma thèse intitulée « Réseaux de capteurs sans fil de grande taille: quelques contributions à la modélisation et à l'algorithmique » ainsi qu'au pot qui suivra. La soutenance aura lieu le vendredi 1 avril à 11h00 dans la salle B311. Le jury sera constitué de :
M. Jean Frédéric Myoupo, professeur, Université de Picardie Jules Verne, Président.
M. Yves Métivier, professeur, Université Bordeaux 1, Rapporteur.
M. Vincent Villain, professeur, Université de Picardie Jules Verne, Rapporteur.
Mme. Frédérique Bassino, professeur, Université Paris 13, Examinatrice.
M. Gérard Duchamp, professeur, Université Paris 13, Examinateur.
M. Christian Lavault , professeur, Université Paris 13, Directeur de thèse.
M. Vlady Ravelomanana, professeur, Université Paris 7, Co-encadrant.

-------------------------------------------------------------------
Résumé de la thèse :
Cette thèse est consacrée d'abord aux problèmes de modélisation des réseaux de capteurs sans fil, à savoir, comment trouver un modèle de communication réaliste. Un réseau de communication se modélise par un graphe. Le cadre de réseaux de capteurs sans fil ne va pas déroger à la règle et les capteurs, les noeuds de communication, seront modélisés par les sommets du graphe tandis que les arêtes représenteront les liens physiques de communication entre ces éléments communicants. La notion de graphe est importante car un grand nombre de paramètres employés en théorie des graphes permettent de quantifier des propriétés physique, topologiques ou des performances des réseaux modélisés. Toutefois, dans l'avenir les applications impliqueront un très grand nombre de capteurs à déployer sur de grande zones souvent inaccessibles, ce qui conduirait à un déploiement aléatoire rendant les modèles de graphes classiques obsolètes. Nous montrons que la stratégie aléatoire est la seule façon de déployer les réseaux de capteurs et par conséquent la modélisation par les graphes aléatoires géométriques et les graphe de Poisson est la plus appropriée. Nous développons ensuite nos travaux concernant la k-couverture, définie comme tout point physique de la zone de déploiement doit être couvert par au moins k noeuds actifs. Une notion très importante car nécessaire au bon fonctionnement du réseau car impliquant le connexion. Pour étudier les réseaux de capteurs aléatoires et pour pouvoir mettre à profit leurs densités afin de concevoir des protocoles qui permettent de maintenir un haut degré de couverture tout en prolongeant la durée de vie du réseau, nous étudions les limites fondamentales de la durée vie d'un réseau de capteurs que tout algorithme peut atteindre. Pour un ensemble de n points suivants un processus ponctuels de Poissons d'intensité dans une région de taille S avec chaque point couvrant un disque unité, nous donnerons des résultats concernant les valeurs requise pour garantir la k-couverture pour toute valeur de k. Nous terminons enfin par l'étude en moyenne d'algorithmes pour la recherche de stable maximal dans les graphes aléatoires. Nous examinons d'abord la performance du plus simple des algorithmes séquentiel sur deux types de graphes aléatoires. Dans le premier cas, nous considérons des graphes de Poisson, on établira que l'algorithme glouton trouve un ensemble indépendant maximal dont la loi limite est asymptotiquement normale. Dans le second cas, nous étudions le même algorithme sur les graphes d'Erdös-Rényi et montrerons que la distribution limite n'existe pas. Enfin, nous présenterons et analyserons un algorithme distribué probabiliste optimal (en temps et en bits).
]
29/03/2011 Axel de Goursac Combinatoire algébrique et C* algèbres [abstract.html
Algebraic structures and C*-algebras
In this talk, we will introduce the basics of the theory of C*-algebras, which correspond to noncommutative topological spaces in the noncommutative geometry picture. Then, we will see the Hochschild cohomology as a generalization of the de Rham complex of differential forms, and some applications to physics.
]
29/03/2011 Axel de Goursac Aspect combinatoire de la renormalisation en théorie des champs [Slides.pdf] [abstract.html
Combinatorial aspects of renormalization in quantum field theory
In this talk, we will present the main ingredients of the BPHZ renormalization of quantum field theory. Then, we will see the situation of quantum field theory on noncommutative spaces.
]
22/03/2011 Flavia Stan A symbolic summation approach to Feynman integral calculus [Slides.pdf] [abstract.html
We discuss two methods based on Wilf-Zeilberger summation for the computation of Feynman parameter integrals. For the first method, the integrals are rewritten as multisums over hypergeometric terms to fit the input class of WZ-summation. These summation problems are highly nested sums with non-standard boundary conditions. They satisfy inhomogeneous recurrences containing sums of lower nested depth on the right-hand sides. These last recurrences can be solved recursively by Carsten Schneider's Sigma package. Another approach to evaluate Feynman integrals is by representing them as nested Mellin-Barnes integrals. We show how WZ-methods determine recurrences for contour integrals of this type, thus eliminating the need to find sum representations. This algorithmic technique is also applied to prove typical entries from the Gradshteyn-Ryzhik table of integrals using the Mellin transform method.
]
22/03/2011 Laura Giambruno Étude de la complexité en états moyenne des opérations rationnelles sur les langages finis [Slides.pdf] [abstract.html
La complexité en états d'un langage rationnel est le nombre d'états de son automate minimal. Dans cet exposé nous considèrerons une distribution, où les langages finis sont donnés comme une liste de mots, et nous étudierons la complexité en moyenne des opérations rationnelles: union, concaténation et étoile. L'étude en moyenne est particulièrement intéressante quand le pire de cas est exponentiel, ce qui est le cas ici pour l'étoile et pour la concaténation. Nous prouverons notamment qu'en moyenne la complexité est de ces deux opérations est linéaire. Nous finirons l'exposé en présentant une extension de ces résultats à d’autres classes de langages. Il s'agit de travaux effectués en collaboration avec F. Bassino et C. Nicaud.
]
22/03/2011 Julien David Génération exhaustive de multiensembles de sous-mots fréquents [Slides.pdf] [abstract.html
On étudie le problème suivant: partant d'un mot w et d'un entier q, on souhaite engendrer toutes les façons possibles de partitionner w en ensemble de sous-mots fréquents. Un sous-mot est fréquent s'il possède au moins q occurrences dans la partition. Chaque mot étant associé à un nombre d'occurrences, on s'intéresse à des multiensembles de mots plutôt qu'à des ensembles de mots. Par exemple, partant du mot w=cabcba et d'un entier q=2, le multiensemble {(cb,2),(a,2)} est une solution. On présentera un algorithme qui engendre l'ensemble des solutions sans redondance et on montrera que, sauf si P=NP, la complexité de ce problème est exponentiel dans la taille de la sortie. On donnera un exemple d'une des applications possibles pour cet algorithme.
]
15/03/2011 Marc Mezzarobba Évaluation numérique de fonctions spéciales et combinatoire analytique avec NumGfun [Slides.pdf] [abstract.html
L'objet de cet exposé est de présenter NumGfun, un module Maple consacré à la manipulation « analytique » des solutions d'équations différentielles linéaires à coefficients polynomiaux (fonctions dites D-finies ou holonomes). Les principales fonctionnalités de NumGfun concernent l'évaluation numérique des fonctions D-finies, et le calcul de bornes qui permettent de contrôler leur comportement. Je ferai une démonstration de l'utilisation de NumGfun, et je montrerai comment, à travers le calcul certifié de constantes de connection, il peut être utilisé pour étudier le comportement asymptotique de suites données par des séries génératrices D-finies.
] [.mw]
15/03/2011 Laurent Boyer Comportements typiques dans les automates cellulaires [Slides.pdf] [abstract.html
Les automates cellulaires constituent une classe d'objets permettant de décrire, à l'aide d'une unique règle locale finie, l'évolution, potentiellement complexe, d'un système infini. L'objectif de l'exposé est d'introduire un cadre formel permettant de quantifier des propriétés parmi l'ensemble des automates cellulaires. On commencera par une présentation de tous les objets considérés. On verra ensuite notre formalisme proprement dit et ses liens avec la complexité de Kolmogorov. On évoquera enfin quelques résultats significatifs en s'intéressant d'une part aux techniques qui interviennent dans nos preuves et d'autre part aux conséquences de ces résultats sur notre compréhension des automates cellulaires.
]
08/03/2011 Journées ALEA / Séminaire SLC
01/03/2011 Jean-Christophe Novelli Réalisations des algèbres de Hopf combinatoires [abstract.html
On illustre l'utilité du concept de réalisation et de spécialisation d'alphabet d'une algèbre (sur des alphabets commutatifs ou non, simplement ou doublement indexés) par une (longue) série d'exemples. Les premiers se rapportent aux compositions, aux arbres binaires et aux permutations et on termine, si le temps le permet, en présentant l'exemple le plus récent, celui de l'algèbre de Connes-Kreimer.
]
01/03/2011 Samuele Giraudo Structures algébriques et combinatoires sur les permutations de Baxter [Slides.pdf] [abstract.html
Nous construisons une sous-algèbre de Hopf de l'algèbre de Hopf des fonctions quasi-symétriques libres dont les bases sont indexées par les objets de la famille combinatoire de Baxter (i.e. permutations de Baxter, couples d'arbres binaires jumeaux, etc.). Cette construction repose sur la définition du monoïde de Baxter, analogue du monoïde plaxique et du monoïde sylvestre, et d'un algorithme d'insertion analogue à l'algorithme de Robinson-Schensted. Les propriétés algébriques de cette algèbre de Hopf sont étudiées..
]
01/03/2011 Pierre-Loïc Méliot Partitions aléatoires choisies suivant les poids des traces de Markov des algèbres d'Hecke [Slides.pdf] [abstract.html
Étant donnée une trace définie sur l'algèbre d'Hecke du groupe symétrique Sn, la décomposition de t sur la base des caractères irréductibles fournit une mesure de probabilité sur l'ensemble Pn des partitions de taille n. Lorsque t est la trace régulière de Hq(Sn), ou plus généralement une trace de Markov, la mesure correspondante vérifie une loi des grands nombres et un théorème central limite pour la taille des lignes et des colonnes des partitions. Via l'algorithme RSK et la théorie des fonctions quasisymétriques, ces résultats peuvent être interprétés en termes de longueur des plus longs sous-mots croissants et décroissants de modèles de permutations aléatoires.
]
28/02/2011 Pierre Martinetti Séminaire LCR - Von Neumann algebras in physics by examples [abstract.html
We will illustrate the importance of von Neumann algebras in physics, emphasizing in particular their role in the algebraic formulation of quantum field theory.
We will illustrate by various examples how some characteristic properties of von Neumann algebra have a direct translation into properties of spacetime.
]
22/02/2011 Gérard H. E. Duchamp De Lyndon à Lothaire.
22/02/2011 Philippe Marchal Marches aléatoires : records, lemme cyclique et convergence presque sûre [Slides.pdf] [abstract.html
Marches aléatoires : records, lemme cyclique et convergence presque sûre. (Philippe Marchal, LAGA, Paris 13)
Dans un premier temps, nous montrerons comment montrer la convergence presque sûre des chemins de Dyck vers le Brownien. Dans un deuxième temps, nous parlerons des plus hauts points successifs (classiquement appelés "records") d'une marche aléatoire à valeurs dans R. Il existe des relations de dualité bien connues entre les records successifs ascendants et les records successifs descendants, dont la preuve se ramène essentiellement au lemme cyclique. Nous établissons de nouvelles relations liant, pour une même trajectoire, le nombre de records ascendants et le nombre de records ascendants pour la marche rétrograde.
]
22/02/2011 Hoang Ngoc Minh Algebraic combinatorial aspects of nonlinear differential systems [Slides.pdf]
15/02/2011 Cyril Banderier Séance d'exercices autour des mots de Lyndon et de l'inversion de Moebius
15/02/2011 Alexandre Benoit Expansions de Fourier et de Chebyshev de fonctions D-finies [Slides.pdf] [abstract.html
Chebyshev polynomials, Hermite polynomials, Bessel functions and other families of special functions each form a basis of some Hilbert space. A Generalized Fourier Series is a series expansion in one of these bases, for instance a Chebyshev series. When such a series solves a linear differential equation, its coefficients satisfy a linear recurrence equation. We interpret this equation as the numerator of a fraction of linear recurrence operators. This interpretation lets us give a general algorithm for computing this recurrence, and a simple view of existing algorithms for several specific function families. Joint work with Bruno Salvy.
]
15/02/2011 Gérard H. E. Duchamp Combinatoire de certaines bases duales [abstract.html
On donne les notions de factorisation complète du monoïde libre et fait le lien avec les bases de Radford et leurs duales.
Si le temps le permet, on donnera le "principe d'identification locale" sur les mots de Lyndon.
Les preuves seront données et discutées complètement et les outils de preuve seront posés, détaillés et discutés interactivement en vue de la communication à différentes communautés.
]
08/02/2011 Pierre Martinetti The thermal time hypothesis: geometrical action of the modular group in conformal field theory with boundary [Slides.pdf] [abstract.html
The thermal time hypothesis: geometrical action of the modular group in conformal field theory with boundary.
After recalling the basis of the thermal time hypothesis of Connes and Rovelli (namely the idea that the physical flow of time is a state dependent notion, that can be retrieved from the modular group associated to the von Neumann algebra of local observables of the physical system under consideration), we present an explicit computation of the action of the modular group associated to double-cone regions of bi-dimensional Minkowski spacetime for a conformal field theory with boundary.
Starting from the covariance of the theory under the Möbius group, we show how to work out an ad-hoc state whose modular group has a pure geometrical action. We compute the Unruh temperature associated to one specific orbit. We then investigate the action of the modular group of the vacuum state, showing that it mixes the previous geometrical action with a nonlocal term. The latest mixes the components of the field in two light-like directions. From a mathematical point of view, it provides one of the first examples of an explicit computation of (the action of) the unitary cocycle intertwinning the modular group of different states on the same algebra.
]
08/02/2011 Pierre Martinetti An algebraic Birkhoff decomposition for non perturbative renormalization [Slides.pdf] [abstract.html
An algebraic Birkhoff decomposition for non perturbative renormalization.
We show how the formalism of Connes-Kreimer, initially developed for perturbative renormalization, can be partially adapted to Wilson's continuous renormalization. The combinatorics of renormalization is no longer described by the Hopf algebra of Feynman diagrams, but rather by the Hopf algebra of rooted trees with two decorations. The latest correspond to the two distinct scales at which one fixes the initial conditions of the equations of the renormalization group. In this framework, we show that the equivalent of the projection on the holomorphic part of the Birkhoff decomposition (in perturbative renormalization) is now a projection on one decoration.
]
08/02/2011 Pierre Martinetti Distances in Noncommutative Geometry [Slides.pdf] [abstract.html
Distances in Noncommutative Geometry.
We shall give an overview of the metric aspect of Noncommutative Geometry, underlining the link between the distance formula in Connes' theory of spectral triple and other distances in mathematics, in particular:
- the horizontal distance in sub-riemannian geometry,
- the Wasserstein distance in the theory of optimal transport.
We will also propose several physical interpretation of this distance, regarding the Higgs field in the standard modelof elementary particles, or the distance in some model of quantum spacetimes.
]
01/02/2011 Gérard H. E. Duchamp Combinatoire des dérivations extérieures (fin)
01/02/2011 Benoît Rittaud Mots circulaires, nombres F-adiques et la suite 1, 5, 16, 45, 121, 320, ... [abstract.html
Un mot circulaire est un mot fini dans lequel on suppose que la première lettre suit la dernière. On le dit admissible s'il ne contient que des 0 et des 1 sans jamais voir deux 1 de suite. Les mots circulaires admissibles renferment des structures explicites de groupes abéliens finis liés à la suite 1, 5, 16, 45, 121, 320,... par ailleurs connue pour ses propriétés combinatoires. Une application des mots circulaires admissibles est l'étude des nombres "F-adiques", qui sont un équivalent des p-adiques pour le système de numération déduit de la propriété de Fibonacci. Plus d'infos : Sloane EIS
]
01/02/2011 Gérard H. E. Duchamp Combinatoire des dérivations extérieures (début)
26/01/2011 Journées Combinatoire de Bordeaux (du mercredi 26 janvier au vendredi 28).
25/01/2011 collectif Table ronde sur les méthodes orbitales en combinatoire
18/01/2011 Gérard H. E. Duchamp Algèbres de substitutions (suite)
18/01/2011 Matthieu Deneufchâtel About different kinds of substitutions [Slides.pdf]
18/01/2011 Gérard H. E. Duchamp Algèbres de substitutions : introduction
11/01/2011 Hoang Ngoc Minh Calculs dans les groupes de Galois différentiels III
11/01/2011 Guoniu Han Formules des équerres pour diverses familles d'arbres et de partitions [Slides.pdf] [abstract.html
La formule des équerres (”hook formula”) apparaît dans le contexte des tableaux de Young et joue un rôle essentiel en combinatoire algébrique, théorie des représentations et théorie des partitions. Une nouvelle méthode, appelée technique de développement en longueur des équerres (et qui présente quelques challenges algorithmiques), permet de découvrir toute une famille de formules des équerres, pour plein de structures combinatoires, suggérant qu'un phénomène mathématique profond ne nous est pas encore pleinement révélé. Un cas particulier de ces formules a été obtenu par Nekrasov et Okounkov dans un contexte tout à fait différent. Dans le cas des arbres planaires on obtient une formule qui unifie plusieurs résultats classiques, y compris la formule de Postnikov. D’autres travaux récents liés à ce sujet par Stanley, Ono, Bessenrodt, Carde, Loubert, Potechin, Sanborn, Okada et Panova seront présentés, ainsi que des liens avec de célèbres conjectures de Ramanujan-Lehmer sur certaines formes modulaires en théorie des nombres...
]
11/01/2011 Christian Lavault q-analogues
04/01/2011 Hoang Ngoc Minh Calculs dans les groupes de Galois différentiels II
04/01/2011 Matthieu Josuat-Vergès Une "version finie" du produit triple de Jacobi, via chemins et fractions continues [Slides.pdf] [abstract.html
Le produit triple de Jacobi est une identité reliant un produit infini à une somme infini, un cas particulier célèbre étant le théorème pentagonal d'Euler. Nous montrons ici une version finie consistant à dire que les sommes tronquées comptent certains chemins (ou que leur série génératrice s'écrit comme une fraction continue). Ceci est relié à des problèmes d'énumération, via certaines formules dites de Touchard-Riordan.
]
04/01/2011 Gérard H. E. Duchamp Calculs dans les groupes de Galois différentiels I
14/12/2010 Ladji Kané Faà di bruno, orbite finie et fonctions rationnelles sur un groupe
14/12/2010 Hoang Ngoc Minh Dérivées successive de la série des Polylogs et Formule de Faà di Bruno
14/12/2010 Laurent Poinsot Faà di Bruno, orbite finie et fonctions rationnelles sur un groupe [Slides.pdf]
07/12/2010 Gérard H. E. Duchamp Équations différentielles non commutatives
07/12/2010 Mario Valencia Pabon Partitions de produits de graphes complets en ensembles dominants indépendants [Slides.pdf] [abstract.pdf]
07/12/2010 Gérard H. E. Duchamp Triangularité et théorème(s) de Radford
30/11/2010 Laurent Poinsot Séance interactive sur les polyzêtas II
30/11/2010 Jean-Éric Pin Une extension aux mots du théorème de Mahler [Slides.pdf]
30/11/2010 Hoang Ngoc Minh Séance interactive sur les polyzêtas I
23/11/2010 Adrian Tanasa Discussion à la suite de "Renormalizability in (non)commutative quantum field theory" [Slides.pdf] [abstract.html
I will introduce in this talk the main ingredients required to obtain a renormalizable model in quantum field theory.
After presenting the main ideas for commutative models, I will generalize this for noncommutative quantum field theory, where usual graphs are replaced by topologically richer ribbon graphs.
]
23/11/2010 Adrian Tanasa Renormalizability in (non)commutative quantum field theory [abstract.html
I will introduce in this talk the main ingredients required to obtain a renormalizable model in quantum field theory.
After presenting the main ideas for commutative models, I will generalize this for noncommutative quantum field theory, where usual graphs are replaced by topologically richer ribbon graphs.
]
23/11/2010 Hoang Ngoc Minh Sur la renormalisation de polyzêtas divergents
16/11/2010 Christophe Tollu Processus déterminantaux II
16/11/2010 Nikolaos Fountoulakis 3-connected cores in random 2-connected graphs [Slides.pdf]
16/11/2010 Christophe Tollu Processus déterminantaux I
09/11/2010 Ladji Kane Indexation de Lyndon des polynômes irréductibles sur un corps à q éléments
09/11/2010 Rafik Aguech Fragmentations aléatoires [Slides.pdf]
09/11/2010 Gérard H. E. Duchamp K< x > en tant qu'algèbre enveloppante, caractéristique nulle et positive
02/11/2010 Laurent Poinsot Adjonction d'unité, aspect catégorique [Slides.pdf] [abstract.html
Titre : Adjonction d'unité, aspect catégorique.
Laurent Poinsot
Résumé :
L'adjonction d'une unité à un semi-groupe pour constituer un monoïde, ou à un anneau pour en faire un anneau unitaire, dérive d'une construction générale, que je me propose d'exposer, dans le cadre des catégories monoïdales.
En effet, pour une catégorie monoïdale C donnée avec coproduits finis et telle que le tenseur se distribue sur le coproduit, cela résulte de l'existence d'un adjoint à gauche pour le foncteur d'oubli de la catégorie des monoïdes internes à C dans celle de ses semi-groupes internes.
]
02/11/2010 Olivier Bodini Génération aléatoire via la méthode de Boltzmann
02/11/2010 Gérard H. E. Duchamp Autour de la relation d'Heisenberg AB-BA=I
26/10/2010 Gérard H. E. Duchamp Dual de Sweedler et forme sandwich
26/10/2010 Roland Bacher Exponentielles de séries génératrices exponentielles [article.pdf]
26/10/2010 Matthieu Deneufchâtel Exemples et calculs sur les duals de Sweedler [Slides.pdf]
19/10/2010 François Bergeron Discussion
19/10/2010 François Bergeron Combinatoire de Catalan et des fonctions de stationnement [Slides.pdf] [abstract.html
Titre:
Combinatoire de Catalan et des fonctions de stationnement
Au cours des dernières années, des questions soulevées en théorie des invariants de groupes, concernant les propriétés des espaces coinvariants diagonaux, ont mené à une étude fine de la combinatoire des fonctions de stationnement (parking functions) et de paramètres sur celles-ci. Nous allons présenter certains de ces développements, ainsi que des extensions qui font intervenir l'ordre de Tamari et ses extensions aux cas des chemins de Dyck généralisés.
L'emphase sera donc mise sur les problèmes combinatoires soulevés par cette étude.
]
19/10/2010 François Bergeron SLk pavages de ZxZ [Slides.pdf]
05/10/2010 Brigitte Vallée Discussion
05/10/2010 Brigitte Vallée Analyse des algorithmes euclidiens et opérateurs de Ruelle [Slides.pdf]
05/10/2010 Brigitte Vallée Systèmes dynamiques, opérateurs de transfert et analyse fonctionnelle [Slides.pdf]
28/09/2010 Julien David (soutenance de thèse à Marne-la-Vallée)
28/09/2010 Gérard H. E. Duchamp Polynômes orthogonaux comprimés et états cohérents
21/09/2010 Andrea Sportiello Limit shapes in random tiling models: a geometric approach [Slides.pdf]
21/09/2010 Laurent Poinsot Sur le plongement du complété d'un espace normé dans son complété pour une autre norme [Slides.pdf] [abstract.html
Titre:
Sur le plongement du complété d'un espace normé dans son complété pour une autre norme.
Soit E un espace vectoriel muni de deux normes p et q comparables, i.e., quel que soit x, p(x) est inférieur ou égal à q(x). En dépit du fait que dans cette configuration toute suite de Cauchy pour q est une suite de Cauchy pour p, on ne peut rien dire en général des relations entre les complétés de E pour p et pour q.
Dans cet exposé, une condition nécessaire et suffisante pour laquelle le complété pour q se plonge continûment (et densément) dans le complété pour p est présentée.
]
21/09/2010 Gérard H. E. Duchamp Un opérateur transcendant dans le noyau de la transformation Gelfand décrit par un modèle particulaire
06/09/2010 Mark Wilson Higher order asymptotics from multivariate generating functions [Slides.pdf]
20/07/2010 Hoang Ngoc Minh Analytic and combinatoric aspects of Hurwitz polyzêtas [article.pdf avec Jean-Yves Enjalbert]
20/07/2010 Pawel Hitczenko Restricted Compositions with same number of parts
20/07/2010 Clôture de l'année académique par un repas "CALIN" de fin d'année
20/07/2010 Hanane Tafat, Cyril Banderier Grammaires algébriques et asymptotique [Slides.pdf] [abstract.html
Titre : Grammaires algébriques et asymptotique.
Résumé :
Nous verrons dans un premier temps comment étudier un "motif" dans un langage rationnel (=une grammaire linéaire) via la série génératrice associée à un automate. Nous donnerons une application au modèle de Schelling.
Nous verrons dans un deuxième temps les aspects asymptotiques des grammaires algébriques : Universalité du phénomène "1/ sqrt(Pi) n^3/2", pour finir sur les recherches en cours : que peut-il être dit au-delà du théorème de Drmota-Lalley-Woods.
Comme, au delà de la théorie, se cache un certain nombre de problèmes techniques, nous montrerons sur des exemples comment on peut utiliser les packages Maple algolib/combstruct/gfun de Salvy/Flajolet et al. pour faire effectivement les calculs asymptotiques, générer des structures, etc.
]
08/07/2010 Journée de présentation des sujets de recherche des nouveaux stagiaires et doctorants de l'équipe CALIN : Gora Adj, Sven De Félice, Sandrine Dasse-Hartaut, Omar Ait Mous, Matthieu Deneufchâtel, Hanane Tafat Bouzid.
06/07/2010 Gérard H. E. Duchamp Espaces rationnels de fonctions sur un groupe : application à l'algèbre de Hopf de Faà di Bruno
29/06/2010 Christophe Tollu Fonctions harmoniques et bord de Martin, le cas discret (exposé 2/2)
29/06/2010 Christophe Tollu Fonctions harmoniques et bord de Martin, le cas discret (exposé 1/2)
22/06/2010 Gérard H. E. Duchamp Bidual de Sweedler et rationalité
22/06/2010 Silvia Goodenough Formule de Faà di Bruno et continuité partielle
15/06/2010 Hoang Ngoc Minh TBA
15/06/2010 Andrea Sportiello Approximations de π et modèle à six sommets
01/06/2010 Laurent Poinsot Dualité et séries formelles [abstract.html
Titre : Dualité et séries formelles.
Résumé :
L'objectif de cet exposé est de montrer que, quelle que soit la topologie (séparée) de corps sur K, le dual (topologique, pour la topologie produit) de l'espace K^X des applications définies sur un ensemble X et à valeurs dans le corps K est isomorphe au sous-espace K^(X) des fonctions à support fini.
En particulier, ce résultat s'applique lorsque X est le monoïde commutatif libre sur une lettre x, où, dans ce cas, K^X n'est autre que l'ensemble des séries formelles K[[x]], et K^(X) celui des polynômes K[x].
Une conséquence de ce fait est que l'espace des endomorphismes continus (sous les hypothèses précédentes quant au choix des topologies) de K^X est isomorphe à l'espace des " matrices " dont les " lignes " sont à support fini.
]
01/06/2010 Gérard H. E. Duchamp Dualité algébrique et continue en Informatique
25/05/2010 Silvia Goodenough Déformations d'algèbres de Hopf
25/05/2010 Alfredo Viola Linear Probing Hashing
18/05/2010 Hayat Cheballah Construction partielle de la bijection Gog-Magog
18/05/2010 Jean Cardinal Sorting under partial information (without the ellipsoid algorithm)
18/05/2010 Hoang Ngoc Minh Une preuve par indiscernabilité
11/05/2010 Xavier Viennot (LaBRI) Combinatoire bijective et "interactions"...
11/05/2010 Alain Lascoux (IGM) Quelques bijoux de combinatoire algébrique
11/05/2010 Andrea Sportiello (Université de Milan, Italie) Preuve de la conjecture de Razumov-Stroganov
11/05/2010 Philippe di Francesco (CEA) Physique et combinatoire
11/05/2010 Christian Krattenthaler (Université de Vienne, Autriche) Calcul avancé de déterminants et calcul de π
11/05/2010 Conrado Martinez (Université Polytechnique de Catalogne, Espagne) Searching with dices : A survey on randomized data structures
11/05/2010 Philippe Flajolet (INRIA / Académie des Sciences) Analyse d'algorithmes et combinatoire analytique
11/05/2010 "Journée CALIN" Inauguration de la nouvelle équipe de combinatoire
04/05/2010 Matthieu Deneufchâtel Le shuffle et ses q-déformations
04/05/2010 Gérard H. E. Duchamp q-déformations du shuffle et Physique
27/04/2010 Andrzej Horzela The φ4 model in QFT : nonlinearity, Feynman graphs and renormalization
13/04/2010 Gérard H. E. Duchamp Exercices sur les fonctions D-finies
13/04/2010 Xavier Provençal Combinatoire des mots et convexité discrète
13/04/2010 Cyril Banderier Exercices sur les fonctions D-finies
06/04/2010 Kirone Mallick Solutions exactes pour le processus d'exclusion asymétrique [Slides.pdf]
06/04/2010 Damien Régnault Automates cellulaires stochastiques et modélisation de la formation des quasi-cristaux
06/04/2010 Kirone Mallick Discussion sur les structures algébriques des q-analogues et de la supersymétrie
30/03/2010 Dominique Manchon Renormalisation des valeurs zêta multiples aux entiers négatifs [abstract.html
Renormalization of multiple zeta values for negative integers. Using Connes and Kreimer renormalization, we will show how to extend multpiple zeta functions to every complex argument so that the "quasi-abattage" relations are preserved. The values obtained for negative integers are rational. We will discuss a multi-dimensional analogue. Common work with Sylvie Paycha.
]
30/03/2010 Jean Fromentin Algorithmique des tresses : la forme normale tournante [abstract.html
Une tresse, est un objet géométrique composé de brins qui se croisent.. En mettant bout à bout deux tresses ayant le même nombre de brins, on obtient une nouvelle tresse. Munis de cette opération, l’ensemble des tresses à n brins forme un groupe. Une présentation, par générateurs et relations de ce groupe, est donnée en 1942 par Artin. Une tresse peut alors être vue comme une classe d’équivalence de mots de tresse. Une forme normale est alors un moyen (souvent algorithmique) de sélection pour une tresse d’une mot de tresse distingué la représentant. L’exposé sera divisé en deux parties. La première sera consacrée à une introduction aux groupes de tresses : point de vue intuitif, structure de groupe, présentation d’Artin, problème du mot, etc. Dans la seconde, je présenterai l’objet central de mes travaux, qui est une nouvelle forme normale des tresses, dite forme normale tournante, et j’expliquerai (un peu) en quoi cette nouvelle forme est intéressante, notamment en liaison avec l’ordre de Dehornoy des tresses. Ensuite, je me concentrerai sur les aspects plus informatiques de cette approche, à savoir la construction d’automates explicites reconnaissant les formes tournantes. Seuls les idées seront présentées dans cet exposé, les détails techniques seront volontairement omis.
]
30/03/2010 Dominique Manchon TBA
23/03/2010 Adrian Tanasa Algèbres de Hopf combinatoires dans les théories quantiques des champs
23/03/2010 Andrea Sportiello A combinatorial proof of the Razumov-Stroganov conjecture
23/03/2010 Gérard H. E. Duchamp Physique Combinatoire : Peut-on se passer de l'analyse fonctionnelle ?
23/03/2010 Andrzej Horzela TBA
16/03/2010 Pawel Blasiak Graph Model of the Heisenberg-Weyl algebra [abstract.html
The Heisenberg-Weyl algebra, underlying most physical realizations of Quantum Theory, is considered from a combinatorial point of view. We construct a concrete model of the algebra in terms of graphs which endowed with intuitive concepts of composition and decomposition provide a rich bi-algebra structure.
It will be shown how this encompass the Heisenberg-Weyl algebra, thereby providing a straightforward interpretation of the latter as a shadow of natural constructions on graphs. We will also discuss some combinatorial methods suitable for this graphical calculus.
]
16/03/2010 Pawel Blasiak TBA
09/03/2010 Angela Mestre On the Feynman graph expansion of 1-particle irreducible n-point functions in quantum field theory [Slides.pdf]
09/03/2010 Gérard H. E. Duchamp Sur les structures algébriques de la physique (discussion)
02/03/2010 Cyril Banderier Survey sur "combinatoire et holonomie"
16/02/2010 Ali Akhavi Analyse symbolique des algorithmes de recherche de séquence génératrice optimale dans une structure présentée [abstract.html
Pour étudier un algorithme de tri classique sur /n/ nombres réels distincts, il suffit d’étudier l’algorithme sur les antécédents de /(1,2,...,n)/, i.e. sur les /n!/ énumérations des éléments de l’ensemble /{1,...,n}/. L’exécution de l’algorithme sur l’ensemble de ces /n!/énumérations permet de constater toutes les exécutions possibles de l’algorithme. Lorsque les algorithmes sont décrits à la manière des systèmes dynamiques symboliques, chaque exécution est une suite de transformations élémentaires. Afin de caractériser parmi tous les mots sur l’alphabet des transformations élémentaires, ceux qui correspondent à des traces d’exécutions, il suffit donc pour les tris classiques de considérer les traces d’exécutions sur un ensemble générique : l’ensemble des / / énumérations des éléments de l’ensemble /{1,...,n}/. Nous fournissons un cadre permettant d’exhiber de tels ensembles génériques d’entrées // pour les algorithmes de recherche de séquence génératrice optimale dans une structure présentée (les tris en sont des exemples particuliers mais cela englobe aussi les algorithmes d’Euclide de Gauss et bien d’autres). Une structure présentée est une structure munie d’un squelette pour sa présentation (ou encore son codage) : un entier pour le cardinal d’une séquence génératrice et un ensemble de mots correspondants aux relateurs. Nous nous intéressons à de tels objets munis d’un préordre, lorsqu’ils possèdent beaucoup (éventuellement une infinité) de séquences génératrices. Nous considérons les algorithmes qui partant d’une séquence génératrice quelconque retournent une séquence génératrice satisfaisant certaines propriétés vis-à-vis du préordre.
]
16/02/2010 Christian Lavault q-series et leurs applications combinatoires et physiques
16/02/2010 Aloïs Panholzer Some applications of the method of moments in the analysis of algorithms [Slides.pdf]
09/02/2010 Aloïs Panholzer Exact and asymptotic enumeration results for combinatorial objects [Slides.pdf]
09/02/2010 Christian Lavault q-analogues et notations de Dirac
09/02/2010 Gérard H. E. Duchamp Exponentielles, équations d'évolution et fonctions symétriques (commutatives et non-commutatives)
02/02/2010 Matthieu Deneufchâtel Asymptotique de certaines intégrales de Selberg: le cas unitaire et la transformée binomiale
02/02/2010 Gérard H. E. Duchamp Fin de l'atelier du 05 janvier
26/01/2010 François Delbot Comparaison et évaluation en moyenne de processus d'optimisation pour le problème du vertex cover [abstract.html
La théorie de la complexité distingue les problèmes que l’on sait résoudre en un temps polynomial en la taille des données (que l’on peut qualifier de raisonnable), des problèmes NP-complets, qui nécessitent (en l’état actuel des connaissances) un temps de résolution exponentiel en la taille des données (que l’on peut qualifier de déraisonnable). C’est pour cette raison que la communauté scientifique s’est tournée vers les algorithmes (polynomiaux) d’approximation dont la mesure de qualité se fait le plus souvent grâce au rapport d’approximation en pire cas (pour un problème de minimisation de taille, un algorithme a un rapport d’approximation de k si la taille de toute solution pouvant être retournée par l’algorithme est inférieure ou égale à k fois la taille de la solution optimale). Dans la littérature, on en vient à considérer qu’un algorithme est plus performant qu’un autre lorsqu’il possède un plus petit rapport d’approximation en pire cas. Cependant, il faut être conscient que cette mesure, désormais "classique", ne prend pas en compte la réalité de toutes les exécutions possibles d’un algorithme (elle ne considère que les exécutions menant à la plus mauvaise solution). Dans les travaux que je vais vous présenter, nous avons tenté de mieux "capturer" le comportement des algorithmes d’approximation en allant plus loin que le simple rapport d’approximation en pire cas (en nous focalisant sur le problème du Vertex Cover) : En montrant que les performances moyennes d’un algorithme peuvent être décorélées des performances en pire cas. Par exemple, nous avons montré que dans la classe des graphes spécialement conçus pour le piéger en pire cas, l’algorithme glouton "Maximum Degree Greedy" retourne, en moyenne, des solutions dont la taille tend vers l’optimum lorsque n tend vers l’infini. En évaluant les performances moyennes d’un algorithme. Nous avons prouvé que l’algorithme online présenté par Demange et Paschos en 2005 (dont le rapport d’approximation en pire cas est égal au degré maximum du graphe) est au plus 2-approché en moyenne dans n’importe quel graphe. Ce résultat, combiné à d’autres, montre que cet algorithme est "en pratique" meilleur que la plupart des algorithmes 2-approchés connus, malgré un mauvais rapport d’approximation en pire cas . En comparant les performances de différents algorithmes (analytiquement et expérimentalement). Nous avons proposé un algorithme de liste et nous avons prouvé analytiquement qu’il retourne toujours une meilleure solution que celle construite par un autre algorithme de liste récent [ORL 2006] quand ils traitent la même liste de sommets (dans certains graphes particuliers, la différence de taille peut être arbitrairement grande). Nous avons également comparé analytiquement (en utilisant des outils comme les séries génératrices) les performances moyennes de six algorithmes sur les chemins. Nous les avons ensuite expérimentées sur un grand nombre de graphes de diverses familles bien choisies. On constate dans ces études que les algorithmes 2-approchés étudiés sont ceux qui obtiennent les plus mauvaises performances en moyenne et que ceux qui ont les meilleurs comportements moyens ont de mauvais rapports d’approximation (fonction du degré max. du graphe). Tous ces résultats montrent que le rapport d’approximation en pire cas n’est pas toujours suffisant pour caractériser l’intégralité de la qualité d’un algorithme et que d’autres analyses (en moyenne notamment) doivent être effectuées pour en faire le tour.
]
26/01/2010 Christophe Tollu Réalisation de certaines algèbres d'opérateurs à l'aide de la combinatoire des mots
19/01/2010 Christian Lavault Emergence et applications des q-analogues
19/01/2010 Andrea Sportiello Clifford representation of an algebra related to spanning forests [Slides.pdf]
12/01/2010 Christian Brouder De l'algèbre de Hopf des polynômes à celle de la renormalisation (exposé 1/2)
12/01/2010 Antoine Genitrini Expressions booléennes aléatoires : probabilités, complexité et comparaison quantitative de logique propositionnelle [Slides.pdf] [abstract.html
Écrivez une formule booléenne de manière aléatoire, construite avec des ensembles fixés de connecteurs et de littéraux. Quelle est la fonction booléenne « typique » qu’elle représente ? Quelle est la probabilité que la formule calcule la fonction Vrai ? Un littéral ? Ou une autre fonction donnée ? D’autres questions de nature un peu différente peuvent se poser : quelle est la complexité de la fonction booléenne représentée par cette formule aléatoire (i.e. la taille de la plus petite formule la représentant) ? Quelle est la complexité moyenne d’une fonction booléenne définie sur k variables ? Ces questions mettent en avant le problème suivant : comment définir une distribution de probabilité sur les fonctions booléennes ? Les premiers articles se posant ce genre de questions ont mis en avant deux modèles de formules booléennes aléatoires, basées sur les connecteurs binaires Et/Ou, et qui engendrent une distribution (non uniforme) sur les fonctions booléennes. Ces articles n’ont répondu que très partiellement aux premières questions que j’ai évoquées. On adapte aisément ces distributions au cas de formules construites à l’aide de l’unique connecteur Implication, un des connecteurs de base d’un point de vue logique. Ce modèle de base suscite de l’intérêt car certaines formules représentant des tautologies (formule calculant toujours Vrai) en logique classique ne sont pas des tautologies en logique intuitionniste. Dans un premier temps, j’exposerai les résultats concernant l’ensemble des fonctions booléennes construites sur l’Implication, puis j’aborderai en détail les tautologies. Dans un troisième temps, j’enrichirai le modèle de formules en utilisant plusieurs connecteurs logiques aléatoires. Enfin, je conclurai l’exposé en abordant différentes perspectives relatives à ces problèmes et sur lesquelles je travaille actuellement.
]
12/01/2010 Christian Brouder De l'algèbre de Hopf des polynômes à celle de la renormalisation (exposé 2/2)
05/01/2010 Gérard H. E. Duchamp Quelques groupes de Lie de dimension infinie utiles en Combinatoire
05/01/2010 Gérard H. E. Duchamp Atelier: Exercice 5.37 de Stanley, Enumerative Combinatorics
22/12/2009 Rafik Aguech
22/12/2009 Kamel Mazhouda Critère de positivité de Li et l'hypothèse de Riemann [Slides.pdf]
22/12/2009 Cyril Banderier Mellin et sommes harmoniques
15/12/2009 Laurent Poinsot Formule d'inversion de Möbius et monoïde à zéro
15/12/2009 Yann Ponty Repliement de l'ARN : Une approche combinatoire [abstract.html
Historiquement, l’ADN et les protéines, aux deux extremités du dogme central de la biologie moléculaire, ont monopolisé l’attention des chercheurs en biologie, délaissant dans un premier temps l’ARN, confinée dans un rôle d’intermédiaire. Cependant, des études menées au cours de la dernière décennie sur les mécanismes de fonctionnement de ce polymère ont révélé une diversité de modes d’actions et un potentiel thérapeutique tels que deux prix Nobels ont été décernés à C. Mello/A. Z. Fire (Médecine 2006) et V. Ramakrishnan/T. A. Steitz/A. E. Yonath (Chimie 2009). À l’échelle nanométrique des interactions moléculaires, il est possible d’analyser la fonction des molécules à travers leur géométrie, ou conformation. Dans le cas de l’ARN, la conformation fonctionnelle d’un ARN résulte de phénomènes d’appariement entre des bases complémentaires, qui provoquent un repliement global de l’ARN. Par ailleurs, des contraintes stériques permettent bien souvent de limiter l’ensemble des conformations possible à des structures simples, les structures secondaires, dans lesquels les appariements considérés sont sans croisement. On assimile alors cet ensemble à un ensemble canonique "de Boltzmann", un des objets de base de la physique statistique, ce qui permet de définir une distribution de probabilité, dite de Boltzmann, sur l’ensemble des structures secondaires réalisables. L’ensemble des conformations d’un ARN est aussi assimilable à un objet combinatoire simple, analogue d’un arbre ou encore d’une séquence bien parenthésée, et pouvant être étudié grâce à l’arsenal de la combinatoire analytique. Après une introduction présentant les problématiques et challenge actuels de la bioinformatique de l’ARN, nous présenterons deux contributions à l’algorithmique des structures d’ARN, reposant sur une vision combinatoire de l’ensemble des conformations. La première consiste en une analyse et une amélioration d’un algorithme d’échantillonnage statistique pour la structure d’ARN. En se basant sur une analogie avec la génération aléatoire par la méthode dite récursive, nous pratiquons une analyse de la complexité moyenne de l’algorithme, et proposons une amélioration algorithmique basée sur un parcours "Boustrophedon" proposé par Flajolet/Zimmermann/Van Cutsem 1994. La deuxième application consiste en l’analyse d’une représentation hierarchique pour l’ensemble de Boltzmann, les RNA Shapes introduites par Giegerich/Voß/Rehmsmeier 2004.. Cette hierarchie de représentations compactes pour la structure d’ARN permet la mise en oeuvre d’approches modulaires pour l’analyse des repliements. Cependant, ces approches exigent parfois une énumération exhaustives des Shapes compatibles avec un ARN, provoquant ainsi une explosion combinatoire qu’il convient de quantifier. Pour cette raison, nous avons modélisé et énuméré celles-ci, obtenant des croissances asymptotiques en $\Theta(A^n/n^{3/2})$ pour ces représentations, avec A=1.8... (resp. A=1.3) pour la représentation la moins (resp. la plus) compacte, à comparer avec A=2.3 pour le nombre de structures secondaires de taille similaire.. Au passage, nous montrons (encore une...) bijection entre le niveau de représentation le plus compact et les mots de Motzkin. Les travaux sur les RNA-Shapes ont été menés en collaboration avec A. Lorenz et P. Clote (Boston College).
]
08/12/2009 Roland Berger Algèbres de Koszul et combinatoire des mots
08/12/2009 Mathilde Bouvel Motifs et classes de permutations : le point de vue des arbres de décomposition [abstract.html
Dans cet exposé, on étudie les classes de permutations, qui sont des ensembles de permutations fermés par le bas pour la relation d’ordre de motif. Je présenterai d’une part des résultats de nature algorithmique sur la recherche de motif dans les permutations, et d’autre part des résultats plutôt combinatoires sur la structure des classes de permutations. Un point commun à ces résultats est qu’ils ont été obtenus en utilisant les arbres de décomposition des permutations. Je présenterai ces objets, et illustrerai par des exemples comment ils peuvent être utilisés en combinatoire comme en algorithmique.
]
08/12/2009 Roland Berger Combinatoire des mots et algèbres de Koszul
01/12/2009 Gérard H. E. Duchamp Shuffle, stuffle et commultiplications
24/11/2009 Christophe Tollu Matrices de Wigner : Traces, moments, convergence faible et combinatoire (exposé 1/2)
24/11/2009 Christophe Tollu Matrices de Wigner : Traces, moments, convergence faible et combinatoire (exposé 2/2)
17/11/2009 Christophe Tollu Transformée de Gelfand et transformée de Fourier
17/11/2009 Matthieu Deneufchâtel Algorithme de calcul rapide d'intégrales de type Selberg
10/11/2009 Laurent Poinsot Monoïde partiel libre (exposé 2/2)
10/11/2009 Vonjy Rasendrahasina MAX-2-XORSAT [abstract.html
Nous présentons une approche analytique du problème d’optimisation MAX-2-XORSAT basée sur la combinatoire analytique et énumérative. Dans cet exposé, nous étudions les séries génératrices liées aux configurations optimales de MAX-2-XORSAT. En combinant ces outils avec ceux d’analyse complexe, nous quantifions alors le nombre maximum de clauses satisfaisables des instances aléatoires de MAX-2-XORSAT.
]
03/11/2009 Gérard H. E. Duchamp Théorème de Carter et déformation de Hoffman
03/11/2009 Julien David Analyse de la complexité moyenne de l'algorithme de Moore [abstract.html
Dans un premier temps, on présentera une méthode de génération aléatoire d’automates déterministes accessibles complets et un outil, REGAL, utilisant cette méthode. Les générateurs implantés dans REGAL permettent d’engendrer des automates de plusieurs milliers d’états et ce faisant, d’établir des conjectures crédibles sur les propriétés en moyenne des automates, ainsi que sur les algorithmes qui s’y appliquent. Dans une deuxième partie, on présentera un résultat théorique sur la complexité moyenne de l’algorithme de Moore: si la complexité dans le pire cas de l’algorithme est connu pour être en $\mathcal{O}(n^2)$, on montrera que pour un alphabet fini arbitraire et la distribution uniforme sur l’ensemble des automates déterministes accessibles complets n états, la complexité moyenne est $\mathcal{O}(n\log n)$.
]
03/11/2009 Silvia Goodenough Algèbres d'incidence (d'après W.Schmitt)
27/10/2009 Hayat Cheballah Mesure de Plancherel sur le graphe de Young Fibonacci
27/10/2009 Gérard H. E. Duchamp Traces, caractères et transformation de Gelfand (Exemples)
20/10/2009 Christophe Tollu Partitions aléatoires et processus ponctuels (d'après divers auteurs) (exposé 1/2)
20/10/2009 Christophe Tollu Partitions aléatoires et processus ponctuels (d'après divers auteurs) (exposé 2/2)
13/10/2009 Laurent Poinsot Monoïde partiel libre (exposé 1/2)
13/10/2009 Gérard H. E. Duchamp Combinatoire de la formule de Kilmoyer
06/10/2009 Gérard H. E. Duchamp Combinatoire des extensions centrales de Heisenberg-Weyl
06/10/2009 Gérard H. E. Duchamp Combinatoire des opérateurs diagonaux et applications
29/09/2009 Laurent Poinsot Monoïdes partiels et monoïdes à zéro
29/09/2009 Guilhem Semerjian Physique statistique et SAT aléatoire [Slides.pdf] [abstract.html
Dans les années 90 des simulations numériques ont révélées des propriétés intéressantes dans les ensembles aléatoires d’instances de problèmes de satisfaction de contraintes (satisfiabilité, coloriage de graphes notamment). Quand un paramètre définissant l’ensemble aléatoire (le nombre de clauses par variables) augmente la probabilité de trouver une formule satisfiable chute abruptement de 1 à 0 dans la limite des grandes tailles de formule. Ce phénomène de seuil a été l’objet d’actives recherches en informatique et en probabilités. Par ailleurs des outils (non-rigoureux) de physique statistique ont pu être appliqués à ces problèmes. Un certain nombre de résultats ont émergé de ces études, par exemple des conjectures quantitatives sur la valeur du seuil de satisfiabilité, et une image plus précise de la structure de l’ensemble des solutions des formules satisfiables. D’autres résultats de physique statistique ont un aspect plus algorithmique, que ce soit l’analyse d’algorithmes déjà existants ou la suggestion de nouvelles stratégies pour résoudre ces formules aléatoires. Dans ce séminaire j’essaierai de présenter, sans rentrer dans les détails techniques, le cadre général de ces études et certains de ces résultats.
]
29/09/2009 Gérard H. E. Duchamp groupe de travail
22/09/2009 Matthieu Deneufchâtel Symmetric Functions and integrable many body systems [Slides.pdf]
22/09/2009 Hoang Ngoc Minh L'action du groupe de Galois différentiel des polylogarithmes sur leur développement asymptotique (exposé 2/2)
22/09/2009 Gérard H. E. Duchamp L'opérateur de déplacement en optique quantique (propriétés et combinatoire )
15/09/2009 Gérard H. E. Duchamp États cohérents quantiques et problème des moments
15/09/2009 Hoang Ngoc Minh L'action du groupe de Galois différentiel des polylogarithmes sur leur développement asymptotique (exposé 1/2)
08/09/2009 Christophe Tollu z-mesures et correspondance RSK
08/09/2009 Hayat Cheballah Introduction à Sage, Sage-Combinat
07/07/2009
07/07/2009 Hayat Cheballah Processus limite sur le bord du treillis de Young (d'après Borodin et Olshanski)
30/06/2009 groupe de travail
30/06/2009 groupe de travail
23/06/2009 Mario Valencia Pabon Homomorphismes dans les graphes : applications et problèmes
23/06/2009 Laurent Rigal Sur quelques aspects combinatoires des algèbres quantiques
16/06/2009 Sidi Mohamed Sedjelmaci Méthode du cercle et coprimalité
16/06/2009 Olivier Gérard Suites coalescentes, mots radio-actifs et autres généralisations de la factorielle
02/06/2009 Christophe Tollu Processus stochastiques sur les graphes de branchements
02/06/2009 Gérard H. E. Duchamp Structures partiellement commutatives III : fonction de Mobius, factorisations critiques et formules de Witt
26/05/2009 Christophe Tollu TBA
26/05/2009 Gérard H. E. Duchamp Structures partiellement commutatives II : réécritures, fonction de Moebius, formules de Witt et classes circulaires
19/05/2009 Gérard H. E. Duchamp Structures partiellement commutatives I : élimination de Lazard
12/05/2009 Silvia Goodenough Opérateurs de symétrisation
12/05/2009 Gérard H. E. Duchamp Un programme de Physique Combinatoire
05/05/2009 Gérard H. E. Duchamp Algèbre de Hopf de réarrangements (d'après W.Schmitt)
05/05/2009 Christophe Tollu TBA
28/04/2009 Laurent Poinsot Monoides partiels et algèbres booléennes
21/04/2009 Christophe Tollu Produits infinis et combinatoire analytique
07/04/2009 Gérard H. E. Duchamp Noncommutative q-on algebra
07/04/2009 Gérard H. E. Duchamp Identities in the braid algebra and a conjecture of Don Zagier
31/03/2009 Christophe Tollu z-mesures sur les partitions et théorie des représentations (d'après Kerov, Okounkov, Olshanski et d'autres)
31/03/2009 Andrzej Horzela Quantization and Combinatorics III : Other quantization schemes
24/03/2009 Gérard H. E. Duchamp NCSF, théorie des langages et superalgèbres
24/03/2009 Andrzej Horzela Quantization and Combinatorics II : Operator quantization
17/03/2009 Hayat Cheballah Construction algébrique du bord du treillis de Young
17/03/2009 Andrzej Horzela Quantization and Combinatorics I : Formalisms of classical mechanics
10/03/2009 Gérard H. E. Duchamp Superalgèbres de Lie
10/03/2009 Adrien Boussicault La décomposition en éléments simples et les posets
03/03/2009 Alin Bostan The full counting function of Gessel walks is algebraic [abstract.html
The aim of the talk is to show how a difficult combinatorial problem has been recently solved using an experimental-mathematics approach combined with (rather involved) computer algebra techniques. More precisely, let $f(n,i,j)$ denote the number of lattice walks in the quarter plane which start at the origin, end at the point $(i,j)$, and consist of $n$ unit steps going either west, south-west, east, or north-east. In the early nineties, Ira Gessel conjectured that the sequence of excursions $f(n,0,0)$ is holonomic. We will present the computer-driven discovery and proof of the following generalization, obtained in August 2008 together with Manuel Kauers: the full generating series $F(t,x,y) = \displaystyle{\sum_{i,j,n \geq 0} f(n,i,j) x^i y^j t^n}$ is an algebraic function.
]
03/03/2009 Carine Pivoteau Génération aléatoire de structures combinatoires: la méthode de Boltzmann effective
03/03/2009 Gérard H. E. Duchamp Lemme de Levi et diagrammes étiquetés
17/02/2009 Laurent Poinsot Puissances des opérateurs de substitution avec préfonction
17/02/2009 Hayat Cheballah TBA
17/02/2009 Christophe Tollu Déformations de mesures de Plancherel d'après Matsumoto
10/02/2009 groupe de travail
03/02/2009 Hoang Ngoc Minh A propos de certaines constantes de l'analyse combinatoire
20/01/2009 Silvia Goodenough Convolution dans l'algèbre libre et coefficients de la formule CBH
20/01/2009 Christophe Tollu Analyse harmonique sur un treillis : exemple(s)
13/01/2009 Laurent Poinsot Développement d'endomorphismes sur les suites en série infinie
13/01/2009 Gérard H. E. Duchamp Convolution I
06/01/2009
06/01/2009 Hoang Ngoc Minh Aspects combinatoires algébriques de l'analyse asymptotique des systèmes dynamiques non linéaires avec entrées singulières
16/12/2008 Silvia Goodenough Un travail sur les coefficients des formules de BCH et Dynkin
16/12/2008 Zaid Odibat Fractional Calculus: Definitions, Numerical Methods and Applications in Control Systems and Multi-scale Processes
09/12/2008 Hayat Cheballah Espaces de chemins et fonctions sur les graphes de branchements
09/12/2008 Flavia Bonomo On variations of the graph coloring problem [abstract.html
A coloring of a graph is an assignment of natural numbers to its vertices in such a way that adjacent vertices receive different colors. This well-known problem is a basic model for frequency assignment and resource allocation problems. In order to take into account particular constraints arising in practical settings, more elaborate models of vertex coloring have been defined in the literature. One of such generalized models is the list-coloring problem, which considers a prespecified set of available colors for each vertex. The list-coloring problem is NP-complete even for split graphs, interval graphs, and bipartite graphs. We consider some particular cases of the list-coloring problem: μ-coloring, where each vertex has its own upper bound for the color to be assigned, and (γ,μ)-coloring, where each vertex has its own lower and upper bounds for the color to be assigned. The μ-coloring problem arises in the context of classroom allocation to courses, where each course must be assigned a classroom which is large enough so it fits the students taking the course. We will present some polynomial time algorithms to solve these problems on classes where list-coloring is NP-complete.
]
02/12/2008 Gérard H. E. Duchamp Calculs explicites et deux problèmes ouverts dans DIAG et LDIAG
25/11/2008 Hayat Cheballah TBA
18/11/2008 Frédéric Meunier Atelier de peinture et découpage de collier [abstract.html
Le problème de l’atelier de peinture est un problème simple à formuler et à comprendre, mais extrêmement riche. Par certains aspects, il relève de l’optimisation combinatoire, par d’autres, de la topologie algébrique, par d’autres encore, il est un point d’entrée dans les classes de complexité exotique comme PPA ou PPAD.
]
18/11/2008 Laurent Poinsot Équations différentielles dans les algèbres de Fréchet
04/11/2008 Silvia Goodenough Dérivations et formule CBH
21/10/2008 Laurent Poinsot Séries entières et algèbres de Fréchet
14/10/2008 Christophe Tollu Problèmes de bord et d'asymptotique dans le treillis des compositions
07/10/2008 Hayat Cheballah Treillis des compositions
30/09/2008 Christophe Tollu Problèmes de bord et d'asymptotique pour le treillis des compositions
16/09/2008 Gérard H. E. Duchamp Calculs d'orbites monoïdales et linéaires
09/09/2008 Gérard H. E. Duchamp Calculs de chemins dans les graphes marqués
24/06/2008 Gérard H. E. Duchamp Supersymétrie, cocycles et bicaractères
09/05/2008 Pawel Hitczenko Comment utiliser les martingales
29/04/2008 Gérard H. E. Duchamp Évolution des hamiltoniens à plusieurs modes et polyzetas
16/04/2008 Gérard H. E. Duchamp Groupes de substitutions : le cas inhomogène
15/04/2008 Matthieu Josuat-Vergès Permutations, orientations acycliques, et motifs évités [abstract.html
Nous allons mettre en correspondance trois sortes d’objets : des permutations (ensemble d’excédences fixés), des orientations acycliques de graphes, et enfin des diagrammes de Young remplis de 0 et de 1 en évitant certains motifs. Les tableaux de permutations font le lien entre la première et la troisième classe d’objets, ici le motif évité est une paire de matrices d’ordre 2. En prenant une autre paire de matrices d’ordres 2, on fait élémentairement le lien entre la deuxième et la troisième classe. Reste à voir que les motifs évités sont équivalents, au sens où ils s’énumèrent de la même façon, ce qui peut se faire par récurrence mais aussi par des bijections. Selon le temps restant, nous montrerons que cette correspondance s’étend à une classe de polyominos bien plus générale que celle des diagrammes de Young.
]
09/04/2008 Pawel Blasiak Graphs for quantum theory: Combinatorial constructions
01/04/2008 Frédérique Bassino Génération aléatoire d'automates déterministes [Slides.pdf] [abstract.html
Cet exposé portera sur la génération aléatoire d’automates finis. Les automates peuvent être vus comme des graphes orientés dont les arêtes sont étiquetées sur un alphabet fini et dont deux sous-ensembles de sommets sont distingués (l’ensemble respectivement des états initiaux et des états finals). On présentera une bijection entre l’ensemble des automates déterministes et accessibles à n états sur un alphabet fini et des diagrammes particuliers qui peuvent eux-mêmes être représentés comme les partitions d’un ensemble en n sous ensembles non-vides. Ces constructions combinatoires permettent d’estimer asymptotiquement le nombre d’automates à n états. Cette approche combinatoire a conduit à la conception d’un générateur aléatoire efficace, pour la distribution uniforme sur les automates déterministes à n états : la complexité moyenne en temps du générateur de Boltzmann associé est en O(n3/2). On montrera quelques exemples de résultats expérimentaux obtenus avec la librairie C++ REGAL dans laquelle il est implanté. [ Travail en collaboration avec Julien David et Cyril Nicaud (IGM). ]
]
25/03/2008 Karol Penson TBA
18/03/2008 Hayat Cheballah Espaces de Fock
11/03/2008 Christophe Tollu Autour de la formule d'Accardi-Bozejko
26/02/2008 Julien Fayolle Analyse de la compression par anti-dictionnaire [Slides.pdf] [abstract.html
La compression sans perte d’un texte par anti-dictionnaire (DCA) est une technique de compression efficace introduite par Crochemore et alii à la fin des années quatre-vingt dix. Son principe repose sur la construction de l’anti-dictionnaire du texte : un dictionnaire formé de certains mots n’apparaissant pas dans le texte (mots appelés mots minimaux interdits). Après une introduction à cet algorithme, je montre que sous un modèle sans mémoire de génération des textes, le nombre moyen de mots dans l’anti-dictionnaire sur l’ensemble des textes de taille n se comporte asymptotiquement en $\frac{Kn}{h}+o(n)$, où la constante $K$ est determinée explicitement et $h$ est l’entropie du modèle probabiliste. Les outils que j’utilise proviennent de la combinatoire analytique et des probabilités.
]
19/02/2008 Pierre Nicodème Counting occurrence of words in random texts [Slides.pdf] [abstract.html
We consider random texts generated by a Bernoulli source. We want to count simultaneously the number of occurrences of words within a finite set of words in a random text of size n. The use of generating functions permits to construct a multivariate function counting the occurrences in texts of all size from 0 to infinity. From there several techniques give access to texts of size n. We compute the multivariate generating function
  1. by the very elegant analytic inclusion-exclusion method that resorts to combinatorics.
  2. by constructing the Aho-Corasick automaton recognizing the words, and translating later to generating functions. We compare the complexity of these two methods.
[Joint work with F. Bassino, J. Clément and J. Fayolle].
]
19/02/2008 Hayat Cheballah Groupes algébriques de substitutions approchées et groupe de Riordan
12/02/2008 Jean-Gabriel Luque q-discriminants, hyperdéterminants et polynômes de Macdonald
05/02/2008 Pawel Hitczenko Probabilistic take on permutation tableaux [Slides.pdf] [abstract.html
Permutation tableaux are relatively new combinatorial objects that are in bijections with permutations. They have ben introduced in the context of algebraic combinatorics and subsequently found applications in combinatorial aspects of some particle models (like PASEP). Permutation tableaux have been studied mostly by bijective methods. In this talk, I will describe a direct, elementary approach based on probabilistic interpretation of a basic construction. This talk is partially based on results obtained jointly with Sylvie Corteel.
]
05/02/2008 Laurent Poinsot Fonctions parfaitement non linéaires et partition approchée de l'unité
15/01/2008 Jean Mairesse Tetris, traces, tresses [abstract.html
Le modèle de Tetris sera le fil rouge de l’exposé. Il constitue un paradigme pour différents modèles de Systèmes à Événements Discrets, qui peuvent se voir comme des spécialisations, variations ou extensions de Tetris. Tetris constitue également le point de rencontre de deux classes de modèles mathématiquement intéressantes : les systèmes itérés d’applications topicales (max-plus dans le cas de Tetris) et les marches aléatoires sur les groupes ou monoïdes discrets (traces dans le cas de Tetris). Par ailleurs, le modèle de Tetris est intéressant en lui-même et sera étudié en tant que tel. On s’intéresse aux aspects énumératifs (combien d’empilements différents ?), à l’optimisation (à quoi ressemblent les empilements les plus denses ?) et à l’évaluation de performances (à quelle vitesse se constituent les empilements aléatoires ?).
]
14/01/2008 Allan I. Solomon Introduction to entanglement
08/01/2008 Gérard H. E. Duchamp Quelques exercices inédits sur les algèbres de Hopf
11/12/2007 Hsien-Kuei Hwang Uniform asymptotics of Poisson approximation to binomial distribution and its generalizations [abstract.html
New uniform asymptotic approximations with error bounds are derived for a generalized total variation distance of Poisson approximation to the Poisson-binomial distribution (covering binomial distribution as special case). The method of proof is also applicable to other Poisson approximation problems, and therefore to a lot of data structures and algorithms.
]
04/12/2007 Cyrille Bertelle, Rawan Ghnemat, Gérard H. E. Duchamp Combinatoire et modélisation : ségrégation de Schelling et dérangements généralisés
27/11/2007 Gérard H. E. Duchamp Sur le théorème de réciprocité de Frobenius
13/11/2007 Christophe Tollu TBA
06/11/2007 Gérard H. E. Duchamp Semigroupes partiels, perturbations de coproduits et applications : Infiltration, Physique et Hoffmann
30/10/2007 groupe de travail
23/10/2007 Laurent Poinsot Fonctions parfaitement non-linéaires
16/10/2007 groupe de travail
09/10/2007 Christophe Tollu Polytopes et coefficients de Littlewood-Richardson
02/10/2007 Gérard H. E. Duchamp Limites projectives et applications en physique
19/06/2007 Christophe Tollu Une approche non commutative du théorème central-limite de Vershik-Kerov II
12/06/2007 groupe de travail
05/06/2007 Christophe Tollu Une approche non commutative du théorème central-limite de Vershik-Kerov I
29/05/2007 Frédéric Chyzak Sommation et intégration symboliques des fonctions spéciales et suites combinatoires
29/05/2007 Gérard H. E. Duchamp Sommabilité, finitude et rationalité en Informatique et en Physique
29/05/2007 Éric Laugerotte Manipulation d'expressions non commutatives
22/05/2007 groupe de travail
24/04/2007 Gérard H. E. Duchamp Notion de sommabilité : applications en informatique et en physique
03/04/2007 Gérard H. E. Duchamp États cohérents non conventionnels, résolutions de l'unité et applications
27/03/2007 Gérard H. E. Duchamp États cohérents et problème de moments de Stieltjes
13/03/2007 Frédéric Toumazet Le programme SCHUR : fonctions symétriques, groupes et algèbres de Lie, et applications à la physique
06/03/2007 Gérard H. E. Duchamp Un groupe de Lie-Fréchet qui intervient en Combinatoire et en Physique
20/02/2007 Christophe Tollu Processus markoviens sur les partitions (d'après Borodin et Olshanski) II
06/02/2007 Christophe Tollu Processus markoviens sur les partitions (d'après Borodin et Olshanski) I
16/01/2007 Annick Valibouze Groupes de Galois et idéaux de Galois
19/12/2006 Kurusch Ebrahimi-Fard Relations de Rota-Baxter et bigèbres généralisées
12/12/2006 Christophe Tollu TBA
05/12/2006 groupe de travail
28/11/2006 Gérard H. E. Duchamp Espaces de Fock non commutatifs II : conjecture de Zagier, factorisation dans l'espace des tresses et interpolations de Hopf
21/11/2006 Adrien Boussicault Identités liées aux fonctions de Greene
31/10/2006 Kurusch Ebrahimi-Fard On Connes-Kreimer's Birkhoff decomposition in perturbative Quantum Field Theory
24/10/2006 Christophe Tollu Représentations remarquables du groupe symétrique infini I
17/10/2006 Jean-Gabriel Luque Polynômes de période et crochet de Ihara
03/10/2006 Gérard H. E. Duchamp Espaces de Fock non commutatifs et déformations d'algèbres de Hopf
26/09/2006 Muriel Livernet Algèbres de Hopf tordues II
19/09/2006 Muriel Livernet Algèbres de Hopf tordues I
28/02/2006 Luaï Jaff Combinatoire des tableaux (oscillants)
21/02/2006 Christophe Tollu Graphe de Young et caractères du groupe symétrique infini
07/02/2006 groupe de travail
31/01/2006 Gérard H. E. Duchamp Spécialisations du dual de Sweedler
24/01/2006 Muriel Livernet L'opérade associative et l'ordre de Bruhat faible du groupe symétrique (en collaboration avec M. Aguiar)
17/01/2006 Gérard H. E. Duchamp Matrices biinfinies et applications
10/01/2006 Christophe Tollu Combinatoire des algèbres LS (diagrammes de Bratteli)
03/01/2006 groupe de travail
13/12/2005 groupe de travail
06/12/2005 Sébastien Orange TBA
29/11/2005 Bodo Lass Démonstration de la conjecture de Dumont
22/11/2005 groupe de travail
15/11/2005 groupe de travail
08/11/2005 Ephrem Razafimanantsoa Représentations symétriques des polynômes en plusieurs variables
25/10/2005 Gérard H. E. Duchamp Algèbre des graphes de Feynman : liens avec FQSym et isomorphismes de Foissy
18/10/2005 groupe de travail
11/10/2005 Gérard H. E. Duchamp Algèbre des graphes de Feynman : déformation de coproduits
22/01/2003 Séance de rentrée
31/05/2005 Marcelo Aguiar TBA
24/05/2005 Tyrell McAllister TBA
17/05/2005 Gérard H. E. Duchamp Algèbres de Hecke V. Modules indécomposables
26/04/2005 groupe de travail
19/04/2005 groupe de travail
12/04/2005 Gérard H. E. Duchamp Algèbres de Hecke IV. Calculs explicites dans l'algèbre de Hecke, Hamiltoniens quantiques et théorie de Galois
29/03/2005 Gérard H. E. Duchamp Algèbres de Hecke III : Triangle de Cartan-Brauer de Hn(0)
22/03/2005 Christophe Tollu Algèbres de Hecke II : Couples de Gelfand de groupes linéaires p-adiques
15/03/2005 Gérard H. E. Duchamp Algèbres de Hecke I : Caractéristique d'Euler-Poincaré et représentations polynomiales des algèbres de Iwahori-Hecke
08/03/2005 Frédéric Toumazet Combinatoire de l'acide chlorhydrique
22/01/2005 groupe de travail
15/02/2005 Bruno Vallette Séries de Hilbert-Poincaré et dualité de Koszul
08/02/2005 Gérard H. E. Duchamp Fonctions quasi-symétriques libres
01/02/2005 Frédéric Toumazet Modèle des ruches pour les nombres de Kostka : aspects algorithmiques (avec J. Nzeutchap)
25/01/2005 Gérard H. E. Duchamp Algèbre de Hopf des diagrammes et applications
18/01/2005 Jean-Louis Loday Opérades et bigèbres généralisées
11/01/2005 Christophe Tollu Forme-limite des diagrammes de Young et fonctions sur ces diagrammes
22/01/2003 groupe de travail
07/12/2004 Todor Popov
30/11/2004 Christophe Tollu Caractères asymptotiques des groupes symétriques (2e partie)
23/11/2004 Christophe Tollu Caractères asymptotiques des groupes symétriques (1e partie)
16/11/2004 Loïc Foissy Algèbre de Hopf de Connes-Kreimer non commutative
09/11/2004 Muriel Livernet Introduction aux opérades
02/11/2004 Jean-Gabriel Luque Calcul de l'intégrale de Selberg par des méthodes hyperdéterminantales
26/10/2004 Gérard H. E. Duchamp Algèbres de Hopf de fonctions (fin)
26/10/2004 Muriel Livernet Théorèmes de Milnor-Moore non commutatifs (d'après Londay-Ronco)
19/10/2004 Vlady Ravelomanana Composante(s) géante(s) dans les graphes et physique statistique
12/10/2004 Muriel Livernet Théorèmes de Milnor-Moore non commutatifs (d'après Loday et Ronco)
28/09/2004 Gérard H. E. Duchamp Algèbres de Hopf de fonctions (début)
05/05/2004 Michèle Vergne Formules de résidus pour le calcul de fonctions de partitions (dont l'énumération de points entiers dans des polytopes) et de sommes d'Euler-Maclaurin
28/04/2004
24/03/2004
05/02/2004 Ronald C. King Atelier
28/01/2004 Charles Cochet Calcul effectif de la fonction de partition vectorielle ; application aux flots dans les réseaux et en théorie des représentations
14/01/2004 Atelier "combinatoire des algèbres de Lie"
17/12/2003 Dualité de Schur-Weyl (groupe symétrique / groupe général linéaire) et extensions d'après Halverson et Ram
22/10/2003 atelier combinatoire des groupes et algèbres de Lie
27/05/2003 Leonid Vainerman Groupes quantiques et fonctions spéciales
27/05/2003 Vlady Ravelomanana Algorithmique distribuée et graphes aléatoires géométriques
27/05/2003 Rémi Monasson Transitions de phase en informatique : de l'approche physique à une analyse rigoureuse
27/05/2003 Karol Penson Extending Dobinski relations: from boson normal ordering to Feynman diagrams
27/05/2003 Cyril Banderier Combinatoire (analytique), informatique (théorique) et physique (statistique)
27/05/2003 Xavier Viennot Empilements de pièces et combinatoire des monoïdes de traces en physique
26/05/2003 Florent Hivert & Nicolas Thiéry Algèbres (de Hopf) combinatoires; implantation (+ démo)
26/05/2003 Grzegorz Pestka Dirac equation and its algebraic approximation
26/05/2003 Abdelmalek Abdesselam Combinatoire du logarithme et renormalisation en physique
26/05/2003 Ronald C. King The square of the Vandermonde determinant and its q-deformation
26/05/2003 Frédéric Toumazet Polynomialité des coefficients de Littlewood-Richardson
26/05/2003 Xavier Viennot La suite magique 1, 2, 7, 42, 429, ... en combinatoire et en physique
26/05/2003 Journées du LIPN (26-27 mai 2003) :
14/05/2003
30/04/2003 Emmanuel Briand Polynômes multisymétriques
30/04/2003 Cyril Banderier Combinatoire formelle et calcul analytique
26/03/2003 Daniel Barsky Matrices de Seidel
05/03/2003 Gérard H. E. Duchamp Combinatoire des dérivations et des opérateurs caténatifs
26/02/2003 groupe de travail
12/02/2003 Nicolas Thiéry Mupad Combinat : une plate-forme libre de développement collaboratif pour la combinatoire algébrique
05/02/2003 Alain Lascoux Yang-Baxter, glace carrée et variétés de drapeaux
22/01/2003 groupe de travail
08/01/2003 Gérard H. E. Duchamp Combinatoire et facteurs de commutation
08/01/2003 Christophe Tollu Réalisabilité des algèbres de Weyl déformées
18/12/2002 Jean-Yves Thibon Un monoïde plaxique pour les arbres binaires
04/12/2002 Karol Penson Dobinski formula revisited
20/11/2002 Gérard H. E. Duchamp Combinatoire et facteurs de commutation
20/11/2002 Christophe Tollu Réalisabilité des algèbres de Weyl déformées
06/11/2002 Jean-Gabriel Luque Pfaffiens et Hafniens dans l'algèbre de shuffle
06/11/2002 Frédéric Toumazet Caractères non compacts et physique

Liste de diffusion

Pour être automatiquement tenu informé des séances du séminaire, il vous suffit de cliquer sur le bouton ci-contre.
[Vous pouvez alors à loisir vous désabonner, configurer vos mails de rappels (e.g. 1 semaine, la veille, 10 minutes avant l'exposé...).] sem


Dernière modification : vendredi 16 juin 2017 Valid HTML 4.01! Valid CSS! Organisateurs : Cyril.Banderier & Gerard.Duchamp at lipn.univ-paris13.fr