MULTIYEAR PROGRAM
RESEARCH SCHOOL - ÉCOLE DE RECHERCHE
Scientific Committee
Comité scientifique
Mathilde Bouvel (CNRS, Université de Lorraine)
Luc Devroy (Mc Gill University)
Éric Fusy (CNRS, Université Gustave Eiffel)
Conrado Martinez (Polytechnic University of Catalonia)
Organizing Committee
Comité d’organisation
Wenjie Fang (Université Gustave Eiffel)
Vincent Jugé (CNRS, Université Gustave Eiffel)
Marc Noy (Universitat Politècnica de Catalunya)
Carine Pivoteau (Université Gustave Eiffel)
IMPORTANT WARNING: Scam / Phishing / SMiShing ! Note that ill-intentioned people may be trying to contact some of participants by email or phone to get money and personal details, by pretending to be part of the staff of our conference center (CIRM). CIRM and the organizers will NEVER contact you by phone on this issue and will NEVER ask you to pay for accommodation/ board / possible registration fee in advance. Any due payment will be taken onsite at CIRM during your stay.
The annual meeting Aléa is dedicated to the study of random discrete structures arising in various scientific domains, mainly in theoretical computer science, combinatorics and probability theory, but also in statistical physics, bioinformatics or in other branches of mathematics.
These structures are, for example, trees, words, permutations, lattice walks, more geometrical objects like planar maps, or other objects related to discrete dynamics like cellular automata. Aims and methods are diverse, ranging from enumeration, asymptotic properties and analytic combinatorics, probability, random generation…
The Aléa meeting is closely related to the community of the Working Group Aléa of the “Groupement de recherche CNRS” gdr-im, which was created in the 90’s under the impulse of Philippe Flajolet to promote interactions between combinatorics and probability around the analysis of algorithms. In the last ten years it has been the birth place to many fruitful interdisciplinary collaborations (e.g. on planar maps, walks in quarter plane, algebraic urns…) and it has grown into one of the most active interface between computer scientists and mathematicians in France. The program of the conference aims both at broadening the common knowledge of the participants via mini-courses and invited long talks, and at reflecting the variety and dynamism of the community via short talks that are selected through an open call.
Les journées Aléa sont consacrées à l’étude de l’aléa discret, i.e. l’étude des structures aléatoires discrètes telles qu’elles apparaissent dans diverses disciplines, principalement l’informatique théorique, la combinatoire et la théorie des probabilités, mais aussi la physique statistique, la bio-informatique ou d’autres branches des mathématiques.
Les objets d’études sont par exemple les arbres, les mots, les permutations, les chemins, ou des objets plus géométriques comme les cartes, ou encore liés à une dynamique discrète comme les automates cellulaires. Les objectifs et les méthodes utilisées sont divers : l’énumération, les propriétés asymptotiques et la combinatoire analytique, les propriétés probabilistes, la génération aléatoire…
Les journées Aléa sont étroitement liées à la communauté du groupe de travail Aléa du gdr-im, créé à l’initiative de Philippe Flajolet vers la fin des années 90 pour favoriser les interactions entre combinatoristes et probabilistes autour de l’analyse d’algorithmes. Au cours de ces dix dernières années, elles ont été le creuset de nombreuses et fécondes collaborations interdisciplinaires (e.g. autour des cartes planaires, des marches dans le quart-de plan, des urnes algébriques…) et elles sont devenues lieu d’expression de l’une des interfaces math/info les plus actives en France. Le programme répond au double objectif d’assurer une forme de formation continue de la communauté au travers de cours invités et d’exposés longs, et de refléter sa diversité et son dynamisme au travers d’exposés courts sélectionnés via appel à propositions.
MINI-COURSES
Durée: for a total 2.5 hours + exercise session of 1 hour, each
We showcase several algorithmic methods that can assist in solving combinatorial problems. Such algorithms include recurrence guessing, closure properties for D-finite functions, creative telescoping, or cylindrical algebraic decomposition, which are implemented in many today’s computer algebra systems. We demonstrate with numerous examples how these can be applied beneficially in the context of enumerative combinatorics.
LONG TALKS
On assigne à chaque sommet v d’un graphe G une étiquette aléatoire l(v) de k bits, et on veut qu’il existe un décodeur déterministe D(.,.) tel que pour toute paire de sommets u,v de G, D(l(u),l(v)) dit si oui ou non u et v sont adjacents dans G, de manière correcte avec probabilité au moins 2/3.
On souhaite que D dépende uniquement de la classe de graphe qu’on considère (et pas de chaque graphe G dans la classe) et le problème le plus basique est de comprendre les classes de graphes pour lesquelles on peut choisir des étiquettes de taille k constante. C’est équivalent au fait de comprendre les (familles de) problèmes dont la complexité de communication aléatoire est constante. J’expliquerai ce lien et les différences fondamentales avec la version complètement déterministe du problème, je donnerai quelques résultats positifs et finalement mentionnerai un certain nombre de questions ouvertes.
Travail en commun avec Nathan Harms et Andrey Kupavskii.
Many classical sequences of integers have well established q-analogs. The most fundamental ones are certainly the q-integers and the q-binomial coefficients which both appear in various areas of mathematics and physics. With Valentin Ovsienko we recently suggested a notion of q-rational numbers based on combinatorial properties and on continued fraction expansions. The definition of q-rationals naturally extends the one of q-integers and leads to a ratio of polynomials with positive integer coefficients. Several enumerative interpretations of the coefficients can be given. The construction of q-rationals naturally leads to definitions of q-irrationals and q-unimodular matrices. Developments in various directions have been suggested. In particular there are connections with the combinatorics of posets, cluster algebras, homological algebra, braid groups and knots invariants. In this talk I will give an overview of the subject, starting with the basic definitions and properties of the q-rationals and ending with recent results on the Burau representation of the braid group.
SPONSORS
Projet ANR GrR (Reconfiguration de graphes)
Projet ANR DIMERS
