Les exposés du lundi matin ont lieu en salle de séminaire de Mathématiques, ceux du jeudi après-midi en salle de séminaire du département d'informatique.

Prochaines séances

Exposés passés

Lundi 10 décembre 2015, 14h00 Hacène Belbachir (Université de Bab Ezzouar, USTHB, Alger) Triangle de Pascal Hyperbolique

Lundi 7 décembre 2015, 10h30 Frédéric Meunier (CERMICS, École Nationale des Ponts et Chaussées) Le problème du partage du collier On se donne un collier ouvert formé de n perles. Chaque perle est d’un certain type parmi t types possibles. On suppose qu’il y a un nombre pair de perles de chaque type. Goldberg et West ont prouvé en 1984 qu’il était possible de couper le collier en t endroits et de partitionner les t+1 sous-colliers obtenus en deux groupes contenant chacun autant de perles de chaque type, et ce indépendamment du nombre total n de perles. Si le collier est à partager entre deux personnes, on a ainsi obtenu un partage équitable du collier.
Ce résultat a depuis été généralisé de plusieurs manières (par exemple, pour un partage équitable entre plus de deux personnes) et pose un certain nombre de questions ouvertes (par exemple, peut-on calculer rapidement un tel partage ?). L’objectif de cet exposé est de présenter un certain nombre de ces généralisations et de ces questions ouvertes.

Jeudi 3 décembre 2015, 14h00 Syham El Kamlichi (Université de Rabat, Maroc.) Automates et cryptographie Dans cet exposé, je parlerai de l'utilisation d'une certaine classe de transducteurs, dits inversibles, en cryptographie. Après avoir donné la définition de transducteur inversible, je décrirai le crypto-système basé sur ce type de transducteur.

Jeudi 15 octobre 2015, 13h30 Sebastián Barbieri (ENS Lyon) Subshifts in groups: From square-free words on graphs to aperiodic subshifts Subshifts are sets of colorings of a group that respect local constraints given by forbidden patterns. We present an overview of this theory along with some classical results and questions about the decidability of related problems. Finally, we show how a proof of Alon, Grytczuk, Haluszczak and Riordan which shows the existence of a graph coloring such that every path contains no squares (a natural extension of the square free-word presented by Thue) can be adapted to show the existence of a subshift which contains no periodic points in every finitely generated group.

Du 14 au 17 septembre Journées Structures Discrètes : Programme

Jeudi 23 avril 2015, 14h00 Dan Betea (UPMC Paris 6 & CNRS, LPMA) Limit shapes in the Schur process We explore large random volume-weighted pyramid partitions introduced by Kenyon, Szendroi and Young, as well as large Aztec diamonds with non-uniform measures from the perspective of Schur processes. For each measure we describe the limit shape, and some of its properties. We also discuss fluctuations around the edge. If time permits, we draw attention to some speculative connections between these models and the Gelfand-Tsetlin polygons of Petrov and the Kenyon-Okounkov theory.
This is based on joint work with Mirjana Vuletic, Cedric Boutillier and Guillaume Chapuy.

Lundi 30 mars 2015, 10h30 Samuel Petite (LAMFA, Université de Picardie Jules Verne) Sur les groupes d'automorphismes de sous-shifts de faible complexité Le but de cet exposé est de présenter un survol des résultats connus sur les automorphismes, ou automates cellulaires, préservant un sous-shift X. En particulier, on montrera pourquoi pour un sous-shift minimal de complexité infiniement sous affine, e.g. Sturmien ou issu d'une substitution, le groupe des automorphismes est engendré par le shift et un groupe fini de transformations. Pour une classe de sous-shifts avec une récurrence polynomiale, on montre que n'importe quel sous groupe finiment engendré est virtuellement nilpotent.
Il s'agit d'un travail en commun avec F. Durand, S. Donoso et A. Maass.

Jeudi 12 mars 2015, 14h00 Sylvain Guillemot (LIRMM, université de Montpellier) Recherche de motifs dans les permutations La notion de motif définit un ordre naturel sur les permutations, introduit par Knuth dans les années 60. Intuitivement, on se donne deux permutations sigma et pi et l'on demande si sigma peut-être obtenue à partir de pi en supprimant certaines entrées, et en renumérotant les autres de manière consécutive. Cette notion a donné lieu a de nombreux résultats combinatoires sur les ensembles de permutations définis par motifs exclus, tandis que l'aspect algorithmique du problème a été moins étudié.
On présentera dans cet exposé un nouvel algorithme pour la recherche d'un motif sigma dans une permutation pi, qui s'exécute en temps f(k) n avec k = |sigma|, n = |pi| et f(k) = 2^{O(k^2 log k)}. Il s'agit d'un résultat commun avec Daniel Marx [SODA 2014] qui élucide la complexité paramétrée du problème : les précédents algorithmes avaient une complexité en n^{O(k)} et se posait la question de savoir si le problème était 'fixed-parameter tractable', c'est-à-dire avec une complexité qui soit un polynôme en n de degré constant et indépendant de k.

Lundi 16 février 2015, 10h30 Benjamin Hellouin (Andrés Bello University, Santiago, Chili) Phénomène de randomisation dans les automates cellulaires On s'intéresse au comportement asymptotique typique des automates cellulaires quand la configuration initiale est tirée au hasard, ce qui revient à étudier leur action sur l'espace des mesures de probabilité. En particulier, on observe pour une certaine famille d'automates un phénomène dit de randomisation : les mesures initiales simples sont envoyées sur la mesure uniforme.
Ce problème s'inscrit dans notre étude plus générale des mesures limites d'automates cellulaires. Quand la dynamique considérée est surjective (ce qui inclut les dynamiques réversibles), l'automate cellulaire possède une rigidité qui se prête à une approche combinatoire ou de probabilité discrète ; malgré tout, très peu est connu concernant l'action sur l'espace des mesures.
Nous conjecturons, résultats expérimentaux à l'appui, que certaines propriétés dynamiques imposent la randomisation. Cependant, ce n'est que récemment que nous avons terminé la première preuve complète de l'apparition de ce phénomène dans un automate cellulaire possédant une structure algébrique particulière. Notre preuve, constituée essentiellement de probabilités dicrètes, utilise des structures auto-similaires dans l'évolution temporelle de l'automate.
Ces différents travaux sont issus de collaborations avec Alejandro Maass, Irène Marcovici, Mathieu Sablik, Ville Salo et Guillaume Theyssier.

Jeudi 12 février 2015, 14h00 Sandrine Dasse-Hartaut (LIAFA, Paris Diderot) Combinatoire des tableaux escalier Les tableaux escaliers sont des objets combinatoires jeunes liés au PASEP, modèle de statistique physique, dont ils permettent d'exprimer la probabilité stationnaire. Différentes approches peuvent être utilisées pour étudier les tableaux escalier. On présente ici une bijection entre un sous-ensemble de ces tableaux et les permutations, et les liens que l'on déduit de cette bijection entre des statistiques des permutations et certains paramètres des tableaux escalier.

Jeudi 29 janvier 2015, 14h00 Jean-Baptiste Priez (LRI,université d'Orsay) Énumération d'automates acycliques minimaux à partir de fonctions de parking généralisées Les fonctions de parking usuelles sont bien connues pour être en bijection avec les endofonctions acycliques. À partir de la généralisation de ces fonctions due à Pitman et Stanley, on caractérise une famille de fonctions de parking généralisées en bijection avec les fonctions de transitions sous-jacentes aux automates acycliques. On explicite une bijection entre ces objets et extrait une caractéristique pour l'énumération des automates acycliques minimaux.

Lundi 15 décembre 2014, 10h30 Irène Marcovici (Institut Élie Cartan de Lorraine) Combinatoire, percolation, et physique statistique : les automates cellulaires probabilistes en jeu Je présenterai un automate cellulaire probabiliste (ACP) dont la définition est extrêmement simple, et qui intervient à la fois dans un problème de combinatoire (énumération des animaux dirigés) et dans la résolution d'un jeu lié à la percolation. Il est également lié au modèle des sphères dures en physique statistique. Dans un travail en collaboration avec James Martin, nous prouvons l'ergodicité de cet ACP pour toute valeur du paramètre de définition, répondant ainsi à des questions dans ces différents domaines.