2018-2019


Lundi 10 décembre : Florent Hivert (Université Paris-Sud, LRI) https://www.lri.fr/~hivert/

Titre : Combinatoire algébrique en Coq/MathComp

Résumé : Dans cet exposé, je présenterai mon travail de formalisation sous le système Coq/MathComp d'un certain nombre de résultats de combinatoire algébrique, notamment la règle de Littlewood Richardson, les caractères des groupes symétriques et la formule des équerres. Cet exposé se veut introductif et ne suppose pas de familiarité avec les systèmes de preuves formelles. Après une introduction au système Coq/MathComp, j'essayerai de donner une idée de la démarche, de l'intérêt et des difficultés d'un tel travail de formalisation.
Le résultat du travail est accessible sur https://github.com/hivert/Coq-Combi. Il a bénéficié de contributions de Thibaut Benjamin, Jean Christophe Filliâtre, Christine Paulin et Olivier Stietel.


Lundi 3 décembre : Alina Mayorova (Laboratoire d'informatique de l'École polytechnique (LIX))

Titre : Type B extensions of Cauchy identity and Schur-positivity related to Chow’s quasisymmetric functions.

Résumé : The Cauchy identity is a fundamental formula in algebraic combinatorics that captures all the nice properties of the RSK correspondence. In particular, expanding both sides of the identity with Gessel's quasisymmetric functions allows to recover the descent preserving property, an essential tool to prove the Schur positivity of sets of permutations. We introduce a new type B extension of Schur-positivity based on Chow's quasisymmetric functions and domino functions, i.e. generating functions for domino tableaux. Further, we suggest a q-analogue of the modified domino functions to extend a type B Cauchy identity by Lam and link it with Chow's quasisymmetric functions. We apply this result to a new framework of type B q-Schur positivity and to prove new equidistribution results for some sets of domino tableaux.


Lundi 26 novembre : Cédric Chauve (département de Mathématiques, Université Simon Fraser, Burnaby, Colombie-Britannique, Canada) https://www.sfu.ca/math/department/faculty/chauve--cedric.html

Titre : On the Median and Small Parsimony problems in some genome rearrangement Models.

Résumé : The main goal of genome rearrangement problems is to compute evolutionary scenarios that can explain the order of genes observed in extant genomes. This naturally leads to questions about the order of genes in ancestral genomes, often of extinct species. If a species phylogeny is given, this problem is known as the Small Parsimony Problem, and in its simplest form, where a single ancestral genome is considered, the Median Problem. In this talk, I will first review several algorithmic results on the Median and Small Parsimony Problems, from initial intractability results to surprising tractability results, and then present some more recent results on the same problems in the context where duplicated genes are considered.


Lundi 19 novembre : Ilya Galanov (LIPN, Université Paris 13)

Titre : On self-assembly of aperiodic tilings

Résumé : Aperiodic tilings serve as a mathematical model for quasicrystals - crystals that do not have any translational symmetry, Penrose tilings are the most famous example. The objective is to grow such a tiling by adding tiles one by one using only the local information. The motivation is to mimic the growth of a real world quasicrystals. In this paper we propose a local growth algorithm for a particular class of aperiodic tilings, namely the cut and project tilings in four-dimensional space which admit local rules. Simulations strongly support the evidence that this algorithm grows aperiodic tilings, up to an unavoidable but neglectable proportion of missing tiles.


Lundi 12 novembre : Mathieu Sablik (Université Paul Sabatier de Toulouse) https://www.math.univ-toulouse.fr/~msablik/

Titre : Mesures limites pour des automates cellulaires ou des automates cellulaires probabilistes

Résumé : Les automates cellulaires modélisent des phénomènes à interactions locales où chaque cellule est actualisée en parallèle. Ce modèle déterministe peut être bruité en perturbant l’actualisation de chaque cellule. Leur étude empirique est basée sur l’observation d’un diagramme espace temps initié par une configuration tirée au hasard. Il est donc naturel de s’intéresser aux valeurs d’adhérence de la suite des itérés d’une mesure par un automate cellulaire ou un automate cellulaire bruité, cela correspond aux comportements asymptotiques typiques observés. Dans cet exposé on s’intéressera à leur étude suivant deux approches :

  • pour certaines classes d’automates cellulaire déterministe ou bruité, il est possible de déterminer les mesures limites associées ;
  • on se donne une mesure et on cherche à déterminer si elle est accessible comme mesure limite par un automate cellulaire déterministe ou bruité.

Lundi 5 novembre : Alexandre Zvonkine

Titre : Construction de cartes régulières à partir de leurs petits quotients

Résumé : Toute carte, et toute hypercarte, peut être représentée comme un triplet de permutations ($\sigma$,$\alpha$,$\phi$) qui agissent sur l'ensemble B de brins d'arêtes. Les cycles de $\sigma$ sont des sommets, les cycles de $\alpha$ sont des arêtes, les cycles de $\phi$ sont des faces. À toute carte on peut associer deux groupes : le groupe de monodromie G = <$\sigma$,$\alpha$,$\phi$> et le groupe d'automorphismes H. Une carte est dite régulière si ces deux groupes sont isomorphes. Dans ce cas-là l'ensemble de brins B peut être identifié avec le groupe, et le groupe agit sur lui-même par multiplications. Ainsi, une construction d'une carte régulière, même assez grande, peut être effectuée en fabricant d'abord un groupe ayant des propriétés voulues, et un tel groupe peut être fabriqué en tant que groupe de monodromie d'une autre carte qui est, elle, souvent petite. Comme un exemple principal, nous allons considérer les cartes de Hurwitz. En 1893, Hurwitz a démontré que la taille du groupe d'automorphismes d'une carte de genre g > 1 est bornée par 84(g-1). Les cartes qui atteignent cette borne sont extrêmement rares : il y a à peu près vingt mille cartes régulières de genre entre 2 et 101, dont seulement sept atteignent la borne de Hurwitz.


Lundi 22 octobre : Samuel Simon (Department of Mathematics, Simon Fraser University, Canada)

Titre : Asymptotics of Weighted Highly Symmetric Walks.

Résumé : A walk on the square lattice is a sequence of steps from a given step set, and the length of the walk is the size of the sequence. The enumeration and asymptotics of walks confined to a region has been of interest, and much progress has been made within the past few decades. We consider a particular weighted family of walks confined to the positive cone in d dimensions.
We introduce standard techniques used in manipulation functional equations to extract the desired terms from generating functions. Then we combine results from analytics combinatorics and complex analysis along with the explicit structure of our step sets to extract the asymptotics growth.


Lundi 15 octobre : Xavier Caruso

Titre : Nombre moyen de racines d'un polynôme p-adique aléatoire

Résumé : À l'instar des réels, le corps des nombres p-adiques s'obtient par complétion à partir des nombres rationnels et est muni d'une mesure naturelle (qui peut être considérée comme un analogue de la mesure gaussienne) qui permet de donner un sens à un nombre p-adique aléatoire et, par suite, à des structures p-adiques aléatoires plus complexes telles que les polynômes. L'étude des polynômes aléatoires p-adiques peut ainsi être menée de même que l'on étudie habituellement les polynômes aléatoires réels.
Dans cet exposé, je m'intéresserai au nombre moyen de racines des polynômes p-adiques aléatoires dans le corps des nombres p-adiques, Qp, ainsi que dans ses extensions algébriques. Je montrerai en particulier qu'un polynôme p-adique aléatoire a, en moyenne, une seule racine dans Qp et, a contrario a pratiquement toutes ses racines dans l'extension maximale non ramifiée de Qp. Un parallèle avec la situation sur les corps finis sera également proposé.
N.-B. : L'exposé est destiné à un public pour lequel on ne suppose aucune familiarité particulière avec les nombres p-adiques. Il contiendra en particulier de très nombreux (r)appels basiques sur Qp, et sur ses extensions algébriques.


Lundi 1er octobre : Thomas Krajewski (CPT Marseille & LIPN) http://www.cpt.univ-mrs.fr/ cf. 11/12/2015.

Titre : Algebraic structures related to loop equations

Résumé : Random matrix theory investigates probability laws defined on matrices and proved to be useful in various areas of physics and mathematics. In particular, the expansion of the corresponding matrix integrals around a Gaussian one leads to a sum over maps, so that the former can be considered as a generating function for maps. Changing variables in the matrix integrals provides constraints on the generating function, known as loop equations, which reduce to the Tutte equations for map enumeration. Loop equations are also at the origin of the topological recursion that allows to construct explicitly the generating function at fixed genus in terms of lower genera. Recently, a purely algebraic formulation of topological recursion has been presented by Kontsevitch and Soibelman (see https://arxiv.org/abs/1701.09137), which is versatile enough to encompass various other situations, like random tensors and semi-classical expansions in quantum theory.
In this talk, I will briefly review the relation between matrix integrals and map enumeration and then show how the associated loop equations can be formulated in the wider framework proposed by Kontsevitch and Soibelman.


Lundi 24 septembre : Xavier Viennot

Titre : Empilements de Laguerre pour le PASEP

Résumé : Le PASEP (partially asymmetric exclusion process) est un modèle très connu en physique des systèmes dynamiques ayant une combinatoire sous-jacente très riche et particulièrement étudiée par l'équipe bordelaise. Josuat-Vergès a donné une belle interprétation combinatoire de la fonction de partition du modèle à 3 paramètres en termes de permutations, en utilisant une combinaison de 4 bijections. Nous en donnons une autre preuve en introduisant un nouvel objet dans le jardin combinatoire du PASEP : les empilements de Laguerre, c'est-à-dire certains empilements de segments pointés, en bijection avec les permutations. Nous montrons le lien avec les tableaux de Dyck, les « histoires de Laguerre » et la structure de données « dictionnaire » en informatique.


Lundi 17 septembre à 9h30 : Théo Karaboghossian

Titre : Invariant polynomial et théorème d’inversion sur le monoïde de Hopf des hypergaphes et ses sous monoïdes.

Résumé : La notion de monoïde de Hopf a été introduite par Aguiar et Mahajan et formalise de façon algébrique les notions de fusion et séparation d’objet combinatoires (concaténation de mots, restriction de graphes etc). Aguiar et Ardila ont montré que ce formalisme donne un cadre idéal pour définir des invariants polynomiaux. Dans cet exposé je présente la notion de monoïde de Hopf et m’appuie sur les travaux d’Aguiar et Ardila pour définir un nouvel invariant polynomial d’hypergraphe. Je montre ensuite que cet invariant est sujet à un théorème d’inversion similaire à celui de Stanley sur le polynôme chromatique d’un graphe. Finalement je montre que l’on retrouve des résultats similaires déjà connus en tant que conséquences de ce théorème.

~~~~~

Lundi 17 septembre à 10h45 : Samuele Giraudo (Univ. Marne-la-Vallée) http://igm.univ-mlv.fr/~giraudo/

Titre : Réécriture dans les arbres et dénombrement

Résumé : Nous expliquons comment obtenir un système d'équations pour décrire la série caractéristique d'une famille d'arbres évitant un ensemble donné de motifs. La théorie algébrique qui permet de formaliser ce procédé est celle des opérades. Les opérades permettent, via leurs présentations par générateurs et relations, d'obtenir des systèmes de réécriture sur les arbres, qui, lorsque certaines propriétés de confluence sont vérifiées, offrent des pistes pour le dénombrement. Cette approche algébrique de l'énumération est présentée sur de nombreux exemples.



Français English

Groupe

Événements

GT

* Années précédentes

Ressources

edit SideBar