CIRM - HOME (EN)
CIRM - ACCUEIL (FR)
RESEARCH SCHOOL
ECOLE DE RECHERCHE

ALEA Days
Journées ALEA
12 – 16 March, 2018
Scientific Committee
Comité scientifique

Frédérique Bassino (Université Paris 13)
Mireille Bousquet-Mélou (CNRS, Université de Bordeaux)
​Brigitte Chauvin (Université de Versailles St-Quentin-en-Yvelines)
Philippe Duchon (Université de Bordeaux)
Bruno Salvy (INRIA-ENS Lyon)
Organizing Committee
Comité d’organisation

Ana Busic (INRIA Paris et ENS)
Antoine Genitrini (Sorbonne Université)
Jean Mairesse (CNRS, Sorbonne Université)
James Martin (University of Oxford)
« Aléa days » is the annual meeting of the research group Aléa. We are interested in random discrete structures arising in different scientific domains : theoretical computer science, discrete mathematics, probability theory, statistical physics, bioinformatics.
Les journées Aléa sont les rencontres annuelles du groupe Aléa qui s’intéresse aux structures aléatoires discrètes issues de diverses disciplines : l’informatique théorique, les mathématiques discrètes, la théorie des probabilités, la physique statistique, la bio-informatique.
Mini-Courses ​

Sophie Laplante (Université Paris Diderot) – Introduction à la complexité


L’objectif du cours est d’aborder les notions de base en complexité du calcul, On couvrira ce qu’est un modèle de calcul muni d’une notion de ressource afin de parler declasses de complexité. On définira les classes de complexité P, NP, les classes d’espace logarithmique et polynomiale, ainsi que la hiérarchie polynomiale, en illustrant les classes à l’aide de problèmes de décision classiques. Afin de comparer les problèmes entre eux, on introduira la notion de réduction, ce qui permettra de définir la notion de NP complétude. Si le temps le permet nous aborderons les classes de complexité probabilistes.

Jean-François Marckert (CNRS, Université Bordeaux 1) – Notions de convergence probabiliste; application aux structures combinatoires


Les théorèmes de convergence sont tellement importants en théorie des probabilités, que l’on a du mal à imaginer comment cette discipline  aurait pu se développer en leur absence…
Les théorèmes de convergence les plus simples décrivent la convergence de certaines quantités, comme la moyenne d’une somme de variables aléatoires i.i.d. (de même loi et indépendantes): il s’agit de la loi des grands nombres ou le théorème central limite; de même, il existe des résultats de convergence du maximum de variables aléatoires i.i.d. bien normalisées, ou du maximum d’une marche aléatoire.
D’autres résultats plus complexes mais intéressant notre communauté, concernent la convergence de structures combinatoires normalisées vers des structures aléatoires continues (par exemple, convergence de marches aléatoires vers le mouvement brownien, ou des cartes aléatoires, vers la carte brownienne).
Dans les lignes précédentes, j’ai utilisé le mot « convergence » pour désigner des notions forts différentes, qu’il aurait fallu ne pas confondre… Convergence presque sûre, en probabilité , en loi, pour telle ou telle topologie.
Dans un premier temps, ce cours a pour but d’essayer d’éclaircir, en utilisant des exemples, les liens et différences qui existent entre ces notions pour des variables à valeurs dans R; on parlera si le temps le permet également de convergence de moments. On fera une petite liste de théorèmes célèbres, utilisables tels quels.
Dans un deuxième temps, on s’intéressera à la convergence de structures combinatoires aléatoires normalisées: bien sûr, il s’agira d’abord de bien comprendre ce  que cela signifie. On essaiera d’expliquer quel schéma il faut suivre pour prouver de tels résultats de convergence.

(pdf)

Marc Noy (Technical University of Catalonia, BarceloNA) – Logic and random graphs


We say that a class of labelled graphs G satisfies the first order (FO) zero-one law if for every graph property P expressible in FO logic, the probability that P holds in G tends either to 0 or to 1 as the number of vertices goes to infinity.  The first such result was proved for the class of all labelled graphs in the 1960s. Later it has been shown for other classes of graphs, defined by a global condition such as being regular or acyclic.  We will show that zero-one laws and convergence laws (each property has a limiting probability, not necessarily 0 or 1) hold for many classes of graphs defined in terms of forbidden minors, in particular planar graphs and graphs on a fixed surface.

The main tool for proving zero-one and convergence laws are Ehrenfeucht-Fraïsse games. EF games are also used to prove inexpressibility results, like the fact that the property that  a graph is connected is not expressible in FO.  We will also discuss properties in monadic second order logic (MSO), an extension of FO in which quantification over sets of vertices is allowed. 

​(pdf)

Long Talks

Enrica Duchi (Université Paris Diderot) – Polyominos, permutations et permutominos convexes


Dans cet exposé on s’intéresse aux liens entre trois familles d’objets comptés par des formules closes
remarquablement similaires entre elles. Si le nombre de polyominos convexes est connu depuis les travaux de Delest et Viennot,  les formules closes des permutations et permutominoes convexes ont été découvertes plus récemment et sont moins connues mais tout aussi jolies.  Pour expliciter le lien entre ces différentes classes nous reverrons des méthodes d’énumération classiques et d’autres un peu moins.

​​(pdf)

​Michel Habib (Université Paris Diderot) – New Perspectives for Graph Searches on Structured Families of Graphs    


Graph searching, a mechanism to traverse a graph visiting one vertex at a time in a specific manner, is a powerful tool used to extract structure from various families of graphs.
In this talk, we focus on two graph searches: Lexicographic Breadth First Search (LBFS), and Lexicographic Depth First Search (LDFS).
Many classes of  graphs have a vertex ordering characterisation, and we review how graph searching is used to produce efficiently such vertex orderings.
These orderings expose structure that we exploit to develop efficient linear and near-linear time algorithms for some NP-hard problems (independent set, colouring, Hamiltonicity for instance) on some special classes of graphs such as cocomparability graphs.

 In particular, we will prove fixed point type theorems for LexBFS, and then focus on a LexDFS-based framework to lift algorithms from interval graphs to cocomparability graphs.
Then I will present the relationships between graph searches, graph geometric convexities and antimatroids.  These relationships are for to be completely understood and I will pose some hard conjectures and some interesting problems to consider.

To finish I will present some recent results about Robinsonian matrices by M. Laurent and M. Seminaroti and their relationships with graph searches. This yields a new area of research to investigate.

(pdf)   –  VIDEO – 

​Irène Marcovici (Université de Lorraine) – Automates cellulaires et perturbations aléatoires


Les automates cellulaires sont des systèmes dynamiques pour lesquels le temps et l’espace sont discrets. Ils permettent de modéliser l’évolution d’un ensemble de composantes interagissant entre elles de manière locale : au cours du temps, chacune actualise son état en fonction de ce qu’elle perçoit de son voisinage. 
La règle locale qui définit le système peut mener à une grande complexité de comportements macroscopiques, qui dépendent souvent fortement de l’état initial. Mais les automates cellulaires sont généralement peu robustes aux perturbations aléatoires : si des erreurs se produisent au cours de l’évolution, ils ont tendance à évoluer vers des configurations qui ne dépendent plus de la condition initiale, on parle alors d’ergodicité.
Nous nous intéresserons à la capacité de certains automates cellulaires de « réparer » des erreurs présentes seulement dans la configuration initiale, ou d’être robustes à des erreurs se produisant au cours de l’évolution.

(pdf)

​Jean-Sébastien Sereni (Université de Lorraine) – Aspects extrémaux de la théorie des graphes


Nous verrons plusieurs problèmes classiques de théorie extrémale des graphes, résolus ou ouverts, dans le but de donner un aperçu du type de questions et d’outils du domaine. Des applications de résultats extrémaux dans des contextes inattendus comme la géométrie discrète ou le parallélisme seront présentées. Si le temps imparti le permet, nous introduirons les limites de permutations appelées « permutons ».

​(pdf)

Charlotte Truchet (Université de Nantes) – Pourquoi la programmation par contraintes a-t-elle besoin d’analyse en moyenne ?


La programmation par contraintes s’attache à résoudre des problèmes fortement combinatoires, exprimés à l’aide de relations logiques (les contraintes), portant sur des variables dans des domaines fixés, souvent finis. Chaque type de contraintes est dotée d’un algorithme de propagation, qui élague autant que possible les domaines des variables sans perdre de solutions. Les solveurs appliquent ces propagateurs tant que c’est possible, puis effectuent des choix (affectation d’une valeur à une variable) et itèrent le processus. On sait aujourd’hui résoudre des familles de contraintes assez larges, incluant notamment des contraintes de cardinalité, qui portent sur le nombre de valeurs qu’un sous-ensemble des variables peuvent prendre toutes ensemble. On sait moins bien caractériser leur comportement en moyenne : dans quels cas les propagateurs sont-ils efficaces ? Peut-il arriver qu’ils n’élaguent rien ? Comment les appliquer un par un dans un ordre astucieux ? Etc. Dans cet exposé, je présenterai les principes généraux de la résolutions de contraintes, puis détaillerai un certain nombre de questions d’analyse en moyenne qui se posent naturellement sur le comportement des solveurs de contraintes. Enfin, je présenterai quelques résultats récents sur l’analyse en moyenne de phénomènes spécifiques. 

(pdf)

Short Talks

Ny Aina Andriambolamalala (Université Paris Diderot)   Election de leader en log log    (pdf)
CYril Banderier (CNRS, Université Paris 13)   Motifs et marches aléatoires    (pdf)
​Mireille Bousquet-Mélou (CNRS, Université de Bordeaux)   Walks with large steps in the quadrant    (pdf)    – VIDEO – 
Arnaud Cadas (ENS Paris)   Optimal Control of the N bipartite matching model​    (pdf)
Gwendal Collet (TU Wien)   Counting patterns in weighted multigraphs    (pdf)
Henri Derycke (Université de Bordeaux)   Automate pour les récurrentes à gauche du modèle du tas de sable sur les bandes    (pdf)
Matthieu Dien (Academia Sinica, Tapei) Degré de la racine et schéma critique
Sergey Dovgal (Université Paris 13)   Polynomial tuning of multiparametric  combinatorial samplers   (pdf)
Andrew Elvey Price (The University of Melbourne)  Exact Enumeration of Planar Eulerian Orientations   (pdf)
Wenjie Fang (TU Graz)   Graphes cubiques et triangulations sur une surface orientable    (pdf)
Pierre-Louis Giscard (University of York)   Un crible non-commutatif en biologie   (pdf)
Vincent Jugé (CNRS Université Paris-Est)   Uniform generation of infinite concurrent runs: the case of trace monoids   (pdf)
Mathias Lepoutre (École polytechnique)   A bijective proof of the enumeration of maps in higher genus   (pdf)
Baptiste Louf (Université Paris Diderot)   Cartes et hiérarchie KP : bijections pour le cas planaire   (pdf)
Mickaël Maazoun (ENS Lyon) – Limites d’échelle de permutations évitant des motifs   (pdf)
Philippe Marchal (CNRS, Université Paris 13)   Corners of Young tableaux and periodic urns   (pdf)
Pascal Moyal (Université de Technologie de Compiègne)   Topics on general stochastic matching models   (pdf)
Yann Ponty (CNRS École polytechnique)   Comptage et design multiple d’ARN   (pdf)   – VIDEO – 
Nicolas Pouyanne (Université de Versailles St Quentin)     Sur les mesures stationnaires des VLMC   (pdf)   – VIDEO –
Christelle Rovetta (LIX, INRIA, LRI)      Estimer les caractéristiques des structures secondaires d’ARN à partir d’un échantillonnage non redondant   (pdf)
Sébastien Samain (INRIA & ENS)    Exact Computation and Bounds for the Coupling Time in Queueing Systems   (pdf)
Michael Wallner (Université de Bordeaux)     A bijection of plane increasing trees with bounded relaxed binary trees   (pdf)

SPONSORS

Picture

ANR GRAAL