Project

Back to overview

Several aspects of the study of non-uniform random permutations

Applicant Bouvel Mathilde
Number 172536
Funding scheme Project funding (Div. I-III)
Research institution Institut für Mathematik Universität Zürich
Institution of higher education University of Zurich - ZH
Main discipline Mathematics
Start/End 01.09.2017 - 31.12.2019
Approved amount 140'967.00
Show all

Keywords (7)

permutations; random; non-uniform distributions; convergence; permutation patterns; analysis of algorithms; genome rearrangements

Lay Summary (French)

Lead
Les permutations sont des objets très étudiés en mathématiques discrètes. Elles peuvent aussi servir de modèle dans de nombreux problèmes issus d'autres sciences (ou de la vie quotidienne): en effet, une permutation représente tout simplement une manière d'ordonner un ensemble fini d'objets distincts. Ce projet étudie les permutations aléatoires. Alors que celles-ci sont très bien comprises dans le cas uniforme, on s'intéresse ici au contraire à des distributions biaisées, avec plusieurs points de vue différents.
Lay summary
Les distributions non-uniformes envisagées dans ce projet sont de plusieurs types. D'une part, on considère des distributions donnant une probabilité strictement positive seulement aux permutations qui évitent certaines sous-structures (appelées motifs), la masse totale étant distribuée uniformément sur l'ensemble de ces permutations contraintes. D'autre part, inspirés par les modèles de graphes aléatoires, on étudie des distributions faisant intervenir un biais exponentiel,  par une statistique. Enfin, en utilisant les arbres de décomposition des permutations, on introduit des distributions biaisées pouvant être utiles en biologie computationnelle.

Les problèmes étudiés sur ces permutations aléatoires biaisées sont aussi de nature variée, avec des aspects théoriques et d'autres plus appliqués. Sur le plan théorique, on s'intéresse principalement à la convergence vers des objets limites, d'une part dans la topologie des permutons récemment définie, et d'autre part dans une topologie locale que notre projet vise à définir et à étudier. Sur le plan des applications, l'objectif est d'analyser des algorithmes lorsque les données reçues en entrée suivent une distribution non-uniforme, semblable aux cas "typiques" d'utilisation de ces algorithmes. Nous pensons en particulier à des algorithmes de tri sous des distributions favorisant les permutations presque triées, et des algorithmes de réarrangements de génomes sur des permutations qui ressemblent à celles issues de la comparaison entre des génomes de différentes espèces.
Direct link to Lay Summary Last update: 04.04.2017

Responsible applicant and co-applicants

Employees

Name Institute

Project partner

Publications

Publication
Local convergence for permutations and local limits for uniform ρ -avoiding permutations with | ρ | = 3
Borga Jacopo (2019), Local convergence for permutations and local limits for uniform ρ -avoiding permutations with | ρ | = 3, in Probability Theory and Related Fields.
The Brownian limit of separable permutations
Bassino Frédérique, Bouvel Mathilde, Féray Valentin, Gerin Lucas, Pierrot Adeline (2018), The Brownian limit of separable permutations, in The Annals of Probability, 46(4), 2134-2189.
An algorithm computing combinatorial specifications of permutation classes
Bassino Frédérique, Bouvel Mathilde, Pierrot Adeline, Pivoteau Carine, Rossin Dominique (2017), An algorithm computing combinatorial specifications of permutation classes, in Discrete Applied Mathematics, 224, 16-44.
Square permutations are typically rectangular
BorgaJacopo, SlivkenErik, Square permutations are typically rectangular, in Annals of Applied Probability.
Universal limits of substitution-closed permutation classes
BassinoFrédérique, BouvelMathilde, FerayValentin, GerinLucas, MaazounMickaêl, PierrotAdeline, Universal limits of substitution-closed permutation classes, in Journal of the European Mathematical Society (JEMS).

Collaboration

Group / person Country
Types of collaboration
Collaboration with F. Bassino, V. Feray, L. Gerin, M. Maazoun and A. Pierrot France (Europe)
- in-depth/constructive exchanges on approaches, methods or results
- Publication
Collaboration with M. Albert (Uni. Otago) New Zealand (Oceania)
- in-depth/constructive exchanges on approaches, methods or results
Collaboration with C. Nocaud and C. Pivoteau France (Europe)
- in-depth/constructive exchanges on approaches, methods or results
- Publication
Collaboration with J. Borga, V. Feray, B. Stufler (Uni Zurich) Switzerland (Europe)
- in-depth/constructive exchanges on approaches, methods or results
- Publication

Scientific events

Active participation

Title Type of contribution Title of article or contribution Date Place Persons involved
Graduate seminar of probability. Individual talk Phase transition for almost square permutations 30.10.2019 ETH Zürich (Switzerland), Switzerland Borga Jacopo;
Journées MathSTIC 2019. Talk given at a conference Phase transition for almost square permutations 21.10.2019 Université Paris 13, Paris (France), France Borga Jacopo;
Random Trees and Graphs Summer School. Talk given at a conference Square permutations are typically rectangular 01.07.2019 CIRM, Marseille (France), France Borga Jacopo;
Conference Analysis of Algorithms (AofA) 2019. Talk given at a conference Local convergence for permutations: a Markov chain approach via generating trees 24.06.2019 CIRM, Marseille (France),, France Borga Jacopo;
Permutation Patterns 2019. Talk given at a conference Square permutations are typically rectangular 17.06.2019 UZH Zurich (Switzerland),, Switzerland Borga Jacopo;
Graduate seminar of probability. Individual talk Square permutations are typically rectangular 02.05.2019 ETH Zürich (Switzerland), Switzerland Borga Jacopo;
Zurich Graduate Colloquium. Individual talk What is… a permuton? 26.03.2019 ETH Zürich (Switzerland), Switzerland Borga Jacopo;
Winter Combinatorics Meeting Talk given at a conference Limit shapes of pattern-avoiding permutations 20.02.2019 The Open University, Milton Keynes, Great Britain and Northern Ireland Bouvel Mathilde;
Journées combinatoires de Bordeaux 2019 Talk given at a conference Limit shapes of pattern-avoiding permutations 11.02.2019 Bordeaux, France Bouvel Mathilde;
séminaire Individual talk Local convergence for permutations: a Markov chain approach via generating trees 07.12.2018 ENS Lyon (France)., France Borga Jacopo;
Graduate seminar of probability. Individual talk A Galton-Watson tree approach to local limits of substitution-closed permutation classes 11.10.2018 ETH Zürich (Switzerland), Switzerland Borga Jacopo;
Permutation Patterns 2018. Talk given at a conference Local convergence for permutations: the case of uniform 231-avoiding permutations 09.07.2018 Dartmouth College in Hanover (USA, New Hampshire), United States of America Borga Jacopo;
Groupe de travail des thésards du LPSM. Individual talk Local convergence for permutations: the case of uniform 321-avoiding permutations 27.06.2018 Laboratoire de Probabilités, Statistique et Modélisation de Paris (France), France Borga Jacopo;
Discrete mathematics seminar. Individual talk Local convergence for permutations: the case of uniform 321-avoiding permutations 19.03.2018 Universität Zürich (Switzerland), Switzerland Borga Jacopo;
Probability seminar. Individual talk Local convergence for permutations 20.02.2018 Università degli Studi di Padova (Italy), , Italy Borga Jacopo;


Self-organised

Title Date Place
17th international conference Permutation Patterns (2019) 17.06.2019 University of Zurich, Switzerland
Workshop preceeding Permutation Patterns 2019 13.06.2019 University of Zurich, Switzerland

Communication with the public

Communication Title Media Place Year
Talks/events/exhibitions Studiare matematica, quali prospettive?, Liceo scientifico Leonardo da Vinci, Treviso (Italy) International 2019
Media relations: print media, online media Why do we need basic research -- promotion campaign of the SNF SNF youtube chanel Italian-speaking Switzerland German-speaking Switzerland Western Switzerland Rhaeto-Romanic Switzerland 2019
Media relations: radio, television Several interviews related to the Marie Heim-Vögtlin prize SRF, SNF journal, UZH journal Western Switzerland German-speaking Switzerland 2017

Awards

Title Year
Marie Heim-Vögtlin prize 2017 2017

Associated projects

Number Title Start Funding scheme
151254 Permutation classes: from structure to combinatorial properties 01.06.2014 Marie Heim-Voegtlin grants

Abstract

This research project fits into the general area of discrete mathematics. It is interestedin studying permutations, which are one of the simplest and most studiedobjects in this area. Generally speaking, a permutation of size n (whose set is denotedS_n) is a bijection from [1..n] to itself, but it can be represented in severalways. The one most relevant to this project is the diagram (resp. normalized diagram)representation of a permutation: it represents a permutation sigma of S_n as the set of points in the Cartesian plane at coordinates (i, sigma(i)) (resp. (i/n; sigma(i)/n)), for i ranging from 1 to n.The focus of this project is to study random permutations, under non-uniformdistributions. Indeed, whereas a lot is know about random permutations underthe uniform distribution (and its generalization as Ewens distribution), the nonuniformity is seldom studied. Note however several papers in the last few years onthis subject, which demonstrates also the topicality of our project.We plan to develop our research on non-uniform permutations under four axes,which are mainly independent from one another, and which offer different views ofthe problem, including some applications.In Axis 1, we consider permutations that avoid some sub-permutations (calledpatterns), and we work with the uniform distribution on these restricted permutations.Sets of permutations defined by such avoidance constraints are called classes.The study of permutation classes in combinatorics is a very rich topic, and some papersabout probabilistic properties of the simplest classes have appeared in the pastfew years. Here, the focus of our work is the description of the limit shapes of thenormalized diagrams of permutations in classes. Those limit shapes are describedas permutons, and studying the properties of the obtained permutons is also partof Axis 1.In Axis 2, we consider distributions on S_n which are exponentially biased bystatistics. Namely, for a permutation statistics chi, the probability of a permutation sigma of S_n is the quotient theta^{chi(sigma)}/sum_{tau in S_n}theta^{chi(tau)}, for a parameter theta which may depend on n. In the case where chi iscontinuous w.r.t. the permuton topology, we are interested in describing the limitpermutons of these distributions. This is the case in particular for chi countingthe number of occurrences of a given pattern, which includes Mallows distribution(for the pattern 21). But we also want to consider other statistics chi which givea higher probability to almost sorted permutations. In this framework, we mostlywant to analyze (sorting) algorithms, thereby providing more theoretical insight onthe practical complexity of those algorithms. But here also, we may consider theproblem of computing the limit permuton.Axis 3 is the most innovative part of this project, in the sense that it lays thefoundations of a new notion of convergence for permutations. It would be theanalogue of the Benjamini-Schramm convergence (or weak local convergence) forgraphs. Here, we propose a definition of this weak local convergence of permutations,ask whether it has an interpretation in terms of neighborhoods (like in thegraph case), and want to study the limits in this sense of several models of randompermutations.Finally, Axis 4 is turned towards applications in bio-informatics, and more preciselygenome rearrangements. Our goal here is to define non-uniform distributionson permutations such that the permutations produced under these distributionsresemble those obtained comparing the order of the homologous genes of relatedspecies. This would allow to analyze algorithms computing evolution scenarios ina model closer to the biological data than the usual uniform distribution. An importantbut hard task is to be able to quantify how good our models are in theirability to represent the data accurately.
-