M
- Mylène Maida (Université Lille 1) ,
Quelques résultats d’universalité pour des mots en des permutations aléatoires.
08/02/2024.
Choisissons uniformément au hasard une permutation de N objets et intéressons-nous à des observables comme la longueur de la plus longue sous-suite croissante, le nombre de descentes, le nombre de cycles d'une taille donnée etc. Le comportement asymptotique de ces observables quand N devient très grand est bien compris. En particulier, il est facile de montrer que la loi jointe des petits cycles est asymptotiquement poissonienne. Si on considère maintenant non plus une permutation mais un mot en plusieurs permutations uniformes indépendantes, on sait, par des travausxde Nica, Magee, Puder etc, que le comportement asymptotique des petits cycles dépend de la structure algébrique du mot considéré et comment il en dépend. Au delà du cas uniforme, il existe bien d'autres façons intéressantes et/ou naturelles de choisir une permutation au hasard (loi d'Ewens, de Mallows...). Dans cet exposé, je présenterai des travaux en commun avec Slim Kammoun (ENS Lyon) dans lesquels nous avons essayé de comprendre à quelles conditions (sur les lois des permutations et la structure du mot) les petits cycles du mot en les permutations gardent un comportement asymptotique similaire au cas uniforme.
- Cécile Mailler (The University of Bath),
La marche aléatoire du singe.
6/06/2019.
Dans ce modèle de marche aléatoire non Markovienne, le marcheur effectue une marche aléatoire simple sauf à des temps exceptionels où il se téléporte à un site qu’il a déjà exploré dans le passé ; il choisit ce site aléatoirement, avec probabilité proportionelle au nombre de temps passé à ce site dans le passé. Les durées des `runs’’ entre deux ``téléportations'’ sont tirées au hasard de façon i.i.d. indépendamment du reste du processus. Dans ce travail en collaboration avec Gerónimo Uribe Bravo (UNAM), nous montrons comment l’étude de ce modèle peut être réduite à celle d’un arbre aléatoire récursif pondéré. Cette approche nous permet de montrer, entre autres, un théorème limite pour la position du marcheur, et ce dans le cas plus général où le processus sous-jacent (i.e. l’évolution du marcheur entre deux téléportations) est n’importe quel processus de Markov vérifiant lui-même un théorème limite de type théorème de la limite central.
- Kirone Mallick (IPhT, Orsay),
Fluctuations du courant dans le modèle d’exclusion et Processus de croissance.
29/02/2012.
Transparents.
Le processus d'exclusion asymétrique (ASEP) fournit une représentation microscopique des phénomènes de transport unidimensionnel. Il possède des propriétés physiques et mathématiques remarquables, qui en font un paradigme de la mécanique statistique. Son étude a connu un grand essor après une contribution fondamentale de Derrida, Evans, Hakim et Pasquier (1993), qui utilisèrent des algèbres quadratiques pour représenter les poids des configurations microscopiques du système~: cette `technique matricielle' a ouvert la voie à une interprétation combinatoire de ces poids en termes d'arbres, de chemins ou de tableaux. Nous commencerons par un rappel général des propriétés d'ASEP et de sa pertinence pour la physique statistique hors d'équilibre. Ensuite, nous expliquerons comment la méthode algèbrique peut être étendue pour calculer la fonction de grande déviation du courant, une observable très importante du point de vue de la physique. Nos résultats impliquent des produits tensoriels d'algèbres quadratiques et sont une nouvelle fois de type combinatoire : ils sont exacts pour toutes les tailles du système. Dans la derniere partie de l'exposé, nous présenterons une généralisation bidimensionnelle du processus d'exclusion, qui permet de représenter la forme limite d'un cristal cubique en croissance.
- Olya Mandelshtam (University of Waterloo, Canada) ,
Symmetric functions and interacting particle processes.
2/02/2023.
Macdonald polynomials are a family of symmetric functions that are known to have remarkable connections to a well-studied particle model called the asymmetric simple exclusion process (ASEP). The modified Macdonald polynomials are obtained from the classical Macdonald polynomials using an operation called plethysm. It is natural to ask whether the modified Macdonald polynomials are related to some other particle system.
We answer this question in the affirmative with a certain multispecies totally asymmetric zero-range process (TAZRP). This link motivated a new tableaux formula for modified Macdonald polynomials. We present a Markov process on those tableaux that projects to the TAZRP and derive formulas for stationary probabilities and certain correlations, proving a remarkable symmetry property. We also discuss some specializations of the tableaux formulas coming from ASEP and TAZRP to obtain some classical results. This talk is based on joint work with Arvind Ayyer and James Martin.
- Jean-Francois Marckert (LABRI, Bordeaux),
Animaux dirigés, systèmes quadratiques et systèmes de réécritures.
2/06/2022.
Transparents.
Un animal dirigé $A$ sur le réseau carré est une partie de $\mathbb{N}^2$ contenant l'origine 0, et telle que chaque point de A peut-être atteint depuis 0 en restant à l'intérieur de $A$, uniquement par des pas $(0,1)$ ou $(1,0)$. Le cardinal de $A$ s'appelle l'aire de $A$, et l'ensemble des sommets de $\mathbb{N}^2$ que l'on peut ajouter à $A$ sans lui faire perdre sa qualité d'animal dirigé (AD), s'appelle le périmètre de $A$. On s'intéresse à la question du calcul de la série génératrice $G(x, y)$ des AD sur réseau carré selon l'aire et le périmètre. Il s'agit d'une question centrale dans l'étude des AD, très directement liée au problème de la percolation dirigée, pour lequel le seuil critique, qui est $\sup \{ p : G( p, 1-p) = 1 \}$, est inconnu (alors qu'il existe de nombreuses méthodes pour calculer $G(x,1)$). Dans cet exposé, nous montrons l'équivalence entre le calcul de $G$ et le calcul d'une solution à un système quadratique dont les inconnues sont des matrices (équations relativement proches de celles apparaissant pour le TASEP). Incapable de résoudre ce problème, nous montrons que des matrices infinies obtenues comme point fixe d'un système de type "système de réécriture", sont "solutions naturelles" de ce problème quadratique. Trouver un vecteur propre pour l'une d'elle, devrait permettre de calculer $G$...
- Irène Marcovici (Université de Lorraine, Nancy),
Ergodicité de certains automates cellulaires bruités.
01/06/2017.
Quand on perturbe un automate cellulaire par un bruit aléatoire (probabilité positive d'erreur, indépendamment pour différentes cellules), on s'attend généralement à ce que le système soit ergodique, c'est-à-dire à ce qu'il oublie progressivement la configuration initiale au cours de son évolution. Lorsque le bruit est suffisamment élevé, des méthodes classiques de couplage permettent de le montrer. Mais lorsque le bruit est faible, l'ergodicité est souvent difficile à prouver. Je présenterai différentes extensions de la méthode de couplage lorsque l'automate cellulaire a des propriétés spécifiques (nilpotence, permutivité...).
- Irène Marcovici (Institut Elie Cartan de Lorraine),
Corrélations discrètes d’ordre 2 de certaines suites automatiques.
1/10/2021.
Transparents.
Une suite k-automatique est une suite qui peut être calculée par un automate fini de la manière suivante : le n-ième terme de la suite est fonction de l'état atteint par l'automate après lecture de la représentation de l'entier n en base k. Ces suites peuvent également être obtenues à partir du point fixe d'une substitution de longueur k. Je montrerai qu'il existe des familles de suites automatiques, qui, malgré leur description très simple, ont les mêmes corrélations d'ordre 2 qu'une suite i.i.d. de symboles choisis uniformément au hasard. Plus précisément, pour tout entier r>0, et pour tout couple (i,j) de symboles, la proportion asymptotique d'entiers n pour lesquels (u_n,u_{n+r})=(i,j) est égale à 1/L^2, où L est le nombre de symboles. La preuve repose sur des ingrédients simples et se généralise à des suites multi-dimensionnelles.
Il s'agit d'un travail en collaboration avec Thomas Stoll et Pierre-Adrien Tahay.
- Jean-François Marckert (LaBRI)
Les feuilletages aléatoires : à la recherche d’un analogue à la carte Brownienne en dimension supérieure.
2/06/2022.
Transparents.
Il s'agit d'introduire un candidat pour jouer le rôle de la carte Brownienne en dimension supérieure. La construction proposée permet de construire une suite d'objets combinatoires, tel que le kème objet s'obtienne à l'aide du (k-1)ème, par identification d'un grand nombre de sommets. Ces repliages successifs, forment une sorte de feuilletage (au sens pâtissier): ils diminuent les distances, ajoutent de la complexité, et font sortir du monde de la 2D. L'exposé consistera à exposer les idées principales de ce travail, et à présenter des théorèmes limites. (Travail commun avec Luca Lionni)
- Stephen Melczer (University of Waterloo),
An Invitation to Analytic Combinatorics in Several Variables.
1/4/2021.
The field of analytic combinatorics in several variables (ACSV) examines the asymptotic behaviour of multidimensional sequences using analytic properties of their (multivariate) generating functions. In addition to the tools used in the more classical univariate setting, the methods of ACSV rely on advanced results from complex analysis in several variables, topology, and algebraic and differential geometry -- giving the field a reputation for powerful methods which can be difficult for new researchers to get a firm grasp on. This talk aims to "demystify" ACSV by surveying some of its main results, software implementations, and recent applications of the theory. In addition, we show how these multivariate techniques can solve previously open problems on the asymptotic behaviour of univariate sequences and provide a significant new approach to attacking the "connection problem" for the asymptotics of D-finite functions.
- Laurent Ménard (Université Paris Ouest),
Triangulations munies d’un modèle d’Ising : algébricité et convergence locale.
21/9/2017.
Transparents.
En 2003, Angel et Schramm ont montré que la loi uniforme sur les triangulations planaires convergeait au sens de la limite locale lorsque l’on faisait tendre leur taille vers l’infini. La loi limite, appelée UIPT (pour Uniform Infinite Planar Triangulation) a été depuis très étudiée et est maintenant un objet bien compris. Dans mon exposé, je montrerai un résultat analogue à celui d'Angel et Schramm mais pour des triangulations échantillonnées selon la loi correspondant à un modèle d’Ising et non à la loi uniforme.
La principale difficulté est d’étendre au modèle d’Ising les résultats combinatoires et énumératifs connus dans le cadre des triangulations « sans matière ». En partant des travaux de Bernardi et Bousquet-Mélou, nous allons voir que les séries génératrices de triangulations à bord simple munies de spins sont algébriques quelles que soient les conditions au bord. Une analyse de singularité donnera alors accès aux informations voulues.
La partie combinatoire de l'exposé parlera surtout de la méthode des invariants de Tutte (et un peu de maple si on a le temps!). Pour le côté probabiliste, on se basera sur une décomposition en tranches des triangulations "à la Krikun".
Il s’agit d’un travail commun avec Marie Albenque et Gilles Schaeffer.
- Marc Mézard (LPTMS, Paris Sud),
Une approche probabiliste au problème d’acquisition comprimée (compressed sensing).
24/05/2012.
Transparents.
L'acquisition comprimée est une évolution majeure de ces dernières années en ce qui concerne l'acquisition de signaux et le traitement de l'information. Le problème majeur posé par l'acquisition comprimée est celui de la reconstruction d'un signal parcimonieux à partir d'un nombre de mesures inférieur au nombre d'inconnues. En utilisant des concepts de physique statistique, nous avons récemment introduit une nouvelle procédure qui permet de réaliser cette reconstruction parfaitement dans une vaste gamme de taux de mesure. Cette procédure permet en fait d'atteindre la performance optimale, c'est à dire de n'utiliser qu'un nombre de mesures égal au nombre de composants non nulles du signal. Elle est basée sur une approche probabiliste de la reconstruction, un algorithme de passage de messages, et une structuration de la matrice de mesures, fondée sur des principes de la théorie de nucléation des cristaux en physique statistique. L'implémentation numérique de cette nouvelle approche montre une amélioration remarquable des performances, par rapport aux algorithmes habituels fondés sur une minimisation de norme $L_1$. Cet exposé est basé sur des travaux en collaboration avec Florent Krzakala, Francois Sausset, Yifan Sun, et Lenka Zdeborova, voir l'article : Phys. Rev. X 2, 021005 (2012) [18 pages], disponible en open access sur http://prx.aps.org/abstract/PRX/v2/i2/e021005
- Marni Mishna (Simon Fraser University),
D-finite by design.
06/12/2012.
D-finite functions satisfy linear differential equations with polynomial coefficients. As innocuous as that might sound, they have been a rich treasure trove for number theorists, computer algebraists, and combinatorialists. Despite deep investigations from several different angles, they still hold many mysteries. For example, Gilles Christol conjectured over 20 years ago that all D-finite globally bounded functions are diagonals of rational functions. This would imply that combinatorial classes with D-finite generating functions are very structured, but yet we have no firm grasp on the anatomy of such classes. This talk will examine the hypothesis using recent developments in lattice path enumeration, in particular the orbit sum variant of the kernel method, amongst other combinatorial evidence. We will also look at the flip side, and describe some techniques to prove that generating functions are not D-finite.
- Marni Mishna (Simon Fraser University),
The Kaleidoscopic Splendor of Lattice Walk Enumeration,.
03/12/2020.
This talk will examine the rich topic of lattice path enumeration. A very classic object of combinatorics, lattice walks withstand study from a variety of perspectives. Even the simple task of classifying the two dimensional walks restricted to the first quadrant has brought into play a surprising diversity of techniques from algebra to analysis to geometry. We will consider walks under a few different lenses. We will see how lattice walks arise in algebraic combinatorics and group theory, and the impact of classification. We will show that a geometric perspective can offer a visual intuition of the role of weighted steps in enumeration formulas. We will also consider some of the existing recent developments using elliptic curves to unravel where the future may lie.
- Sophie Morier-Genoud (IMJ, Paris 6),
Cônes tangents aux variétés de Schubert.
29/09/2016.
Les variétés de Schubert, objets classiques en théorie des représentations, ont une géométrie et combinatoire très riches. Ces variétés admettent très souvent des singularités au point origine (commun à toutes les variétés). Le cône tangent à une variété au point origine, i.e. l'ensemble des vecteurs tangents à l'origine, donne une caractéristique de la singularité. Cette caractéristique est plus précise que celle donnée par l'espace tangent. Cependant les cônes sont bien moins étudiés et compris que les espaces tangents. Dans cet exposé nous rappellerons les notions élémentaires liées aux variétés de drapeaux et aux variétés de Schubert, puis nous formulerons un critère combinatoire pour que deux variétés de Schubert admettent le même cône tangent.
Travail en commun avec D. Fuchs, A. Kirillov, V. Ovsienko.
N
- Philippe Nadeau (CNRS, Institut Camille Jordan),
Éléments pleinement commutatifs dans les groupes de Coxeter.
3/10/2013.
Transparents. Synthèse.
Dans un groupe de Coxeter, les éléments ont une représentation par certains ensembles de mots liés entre eux par des relations. Un élément $w$ est dit pleinement commutatif (PC) si, étant donné deux mots de longueur minimale représentant $w$, il existe toujours une série de commutations de lettres adjacentes pour passer de l'un à l'autre. Ces éléments sont importants car ils indicent une base des algèbres de Temperley-Lieb généralisées; ils interviennent également en connexion avec les représentations d'algèbres de Hecke.
Dans cet exposé, nous nous intéresserons à la combinatoire des éléments PC. Nous les caractériserons précisément pour chaque groupe de Coxeter fini ou affine. Dans ce dernier cas, la suite énumérant les éléments PC selon leur longueur s'avère être ultimement périodique; on donnera la taille de la pré-période et la période minimale de cette suite, et on expliquera comment calculer sa série génératrice. Dans le cas d'un groupe de Coxeter général, on montrera que cette série est toujours rationnelle, via l'utilisation d'automates finis.
Basé en partie sur des travaux communs avec Riccardo Biagioli et Frédéric Jouhet.
- Reza Naserasr (IRIF),
Signed projective cubes.
25/11/2021.
The $n$-dimensional projective cube, denoted $PC(n)$, is the graph obtained from $(n+1)$-dimensional hypercube by identifying antipodal pairs. They are mostly referred to as folded cubes, but we rather view them as the discrete cube in the projective spaces.
The goal of this talk is to introduce and show the importance of these graphs. We will see that they form bridges connecting several domains of mathematics. They capture some prominent optimization problems and they lead to introduction of several new concepts. We will see how the notion of the "winding number" from algebraic topology can be employed to study a special case of a homomorphism question among these (signed) graphs. Finally we will identify several questions of interest for potential future work.
- Markus Nebel (TU Kaiserslautern),
Java 7’s Dual Pivot Quicksort — Analysis and Engineering.
5/12/2013.
Transparents.
Recently, a new Quicksort variant due to Yaroslavskiy was chosen as standard sorting method for Oracle's Java 7 runtime library. The decision for the change was based on empirical studies showing that on average, the new algorithm is faster than the formerly used classic Quicksort. Surprisingly, the improvement was achieved by using a dual pivot approach, an idea that was considered not promising by several theoretical studies in the past. In this talk, we identify the reason for this unexpected success. Moreover, we present the first precise average case analysis of the new algorithm showing e. g. that a random permutation of length n is sorted using $1.9n \ln n - 2.46n + O(\ln n)$ key comparisons and $0.6n \ln n + 0.08n + O(\ln n)$ swaps. Our analysis reveales a highly asymmetric nature of the algorithm. This suggest that asymmetric pivot choices are preferable to symmetric ones. From a theoretical point of view, this should allow us to improve on the current implementation in Oracle's Java 7 runtime library. We present results derived by means of our tool MaLiJAn to confirm this for asymptotic combinatorial cost measures such as the total number of executed instructions (Java bytecodes). However, the observed running times show converse behavior. With the support of data provided by MaLiJAn we are able to identify the profiling capabilities of Oracle's just-in-time compiler to be responsible for this unexpected outcome.
Dans cet exposé je présenterai les automates en tant qu'objets combinatoires. On s'intéressera à des problèmes d'énumération et de génération aléatoire, en utilisant des techniques de combinatoire analytique et de combinatoire bijective. La motivation de ces travaux est de faire de l'analyse d'algorithmes en théorie des langages, mais je me concentrerai dans cet exposé sur la combinatoire qui est derrière ces objets. Il s'agit de différents travaux réalisés avec F. Bassino, J. David, D. Gouyou-Beauchamps, P.-C. Héam, A. Martino, E. Ventura, S. Schmitz et P. Weil.
- Cyril Nicaud (IGM),
Analyse de quelques choix algorithmiques effectués dans les implantations de Python, Java et Lua .
2/06/2022.
- Jonathan Novak (Department of Mathematics, Massachusetts Institute of Technology),
Lozenge tilings of sawtooth domains near a turning point.
5/06/2014.
Transparents.
Random tilings of planar regions by three types of tiles known as "lozenges" have been heavily investigated over the past decade, partly due to their intrinsic appeal and partly due to their status as an especially tractable class of random surface models. There are many connections between lozenge tilings and the representation theory of the classical groups, and consequently representation-theoretic techniques can sometimes be used to effectively answer natural probabilistic questions about tilings. I will discuss tilings of a particular class of regions called "sawtooth domains" for which the relation to representation theory is particularly clear, and focus on the behaviour of a uniformly random tiling of a large sawtooth domain near a "turning point." As recently observed by Gorin and Panova, understanding the asymptotic joint distribution of tiles of one type in this regime comes down to understanding the asymptotics of the Harish-Chandra-Itzykson-Zuber integral in a certain scaling limit. There is a robust combinatorial model for the HCIZ integral which allows to analyze the required asymptotics at a very fine level of detail, and in particular extract a certain limit law. If time permits, I will explain how the techniques discussed can be modified to deal with tilings exhibiting certain additional symmetries.
- Jean-Christophe Novelli (LIGM, Marne-la-Vallée),
Promenade autour de l’inversion de Lagrange.
1/12/2014.
Cet exposé présentera des travaux récents ayant tous des liens profonds avec l'inversion de Lagrange, notamment des calculs dans les opérades dendriformes, des résultats sur les probabilités libres et encore d'autres composantes de la combinatoire algébrique et bijective.
Travaux en commun avec Matthieu Josuat-Vergès, Frédéric Menous et Jean-Yves Thibon.
- Marc Noy (Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya),
Random planar graphs with given minimum degree.
5/06/2014.
We determine the asymptotic growth of planar graphs with a condition on the minimum degree, and properties of random graphs from these classes. In particular we show that the size of the largest tree attached to the 2-core of a random planar graph is of order $c \log(n)$ for an explicit constant $c$. These results provide new information on the structure of random planar graphs.
Joint work with Lander Ramos.
O
- Valentin Ovsienko (Laboratoire de Mathématiques de Reims),
Combinatorial and analytic properties of $q$-deformed real numbers.
04/02/2021.
I will explain a recent notion of $q$-deformed real numbers, and discuss its various combinatorial and analytic properties. A "$q$-deformed real" is a Laurent series in one variable, $q$, with integer coefficients. The subject is connected to different theories, such as knot invariants, continued fractions, and cluster algebras. I will formulate a challenging conjecture about the convergence of the series arising as $q$-deformed real numbers. (Here we understand $q$ as a complex variable.) The conjecture is proved in particular cases and concrete examples. In the most simple examples of $q$-Fibonacci and $q$-Pell numbers, the explicit formulas for the radius of convergence are very similar to certain formulas of Ramanujan.
The talk is based on a joint work with Ludivine Leclere, Sophie Morier-Genoud and Alexander Veselov.
