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

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.
-