Combinatoire et interactions

Coordinator : Valérie Berthé

LaBRI coordinator : Sébastien Labbé

Description : Orbites des systèmes dynamiques discrets en informatique.

Coordinator : Thomas Duquesne

LaBRI coordinator : Mireille Bousquet-Mélou

Description : Il s’agit d’un projet collaboratif (programme “Défi de tous les Savoirs” (DS10) 2014) qui concerne les mathématiques fondamentales, bien que la plupart des questions de recherche abordées dans ce projet soient fortement liées à l’informatique, à la génétique des populations, à la mécanique statistique et la physique théorique. L’ambition principale du projet Graal est de rapprocher les domaines des probabilités, de la combinatoire, des processus stochastiques et de la physique théorique pour étudier les liens existant entre les graphes, les arbres et les cartes aléatoires, et de créer de nouvelles perspectives sur ces objets importants

Coordinator : Jean-Christophe Aval

LaBRI coordinator : Jean-Christophe Aval

Description : The project is organised around three main themes of research.

1. The first one is the study of tree-like tableaux (TLT) which are a new avatar of permutation tableaux. The latter, defned by A. Postnikov, proved their pertinence in the study of the PASEP model in theoretical physics. TLTs, recently introduced by members of the PSYCO project, enjoy two major features: an insertion algorithm, which is simultaneously simple and adaptable, and which has already shown its strength in a combinatorial context, and a natural underlying tree structure whose algebraic consequences remains to be investigated.

2. The second theme is the study of algebras of functions defned on Young diagrams. This arose in the work of Kerov and Olshanski on characters of symmetric groups. In the past few years, this topic has become more combinatorial, with the interpretation of some quantities as cardinalities of families of graphs drawn on surfaces. Recently, M. Lassalle has given numerical evidence that Jack polynomials seem to ft well in this context. It is thus a very challenging problem to fnd combinatorial proofs of these conjectures. Indeed, this would bring a new combinatorial insight on Jack polynomials.

3. The third and last theme deals with the space of diagonal coinvariants. This domain of research, which has generated an important activity in the past two decades, has very recently known a new advance, with the discovery by F. Bergeron of universal formulas (ie. independent of the number of alphabets) to develop the Hilbert and Frobenius series of diagonal coinvariants. This discovery implies remarkable conjectures, which are interesting challenges both from a combinatorial and algebraic point of view.

Coordinator: Benjamin Lévêque (LIRMM)

LaBRI Coordinator: Nicolas Bonichon

Description: Embedded Graphs and their Oriented Structures

Graph theory was initially about embedded graphs. Indeed, the graphs considered in the Königsberg's Bridges Problem or in the 4-Color Problem are planar (i.e. embedded on the plane without intersection between the curves representing edges). Natural generalizations of planar graphs are graphs embedded on surfaces, like the sphere or the torus. The goal of this project is to study such graphs.

In the plane, many families of graphs have oriented structures, which are orientations and colorings of the edges of the graph satisfying a particular local property. For example: 2-connected bipartite planar graphs admit 2-orientations, 3-­connected planar graphs admit Schnyder woods, 4-­connected planar triangulations admit transversal structures. These structures are in bijection with several combinatorial objects like contact system of polygons, TD-Delaunay triangulations, or Dyck words. They also appear to have various computer science applications such as succinct encoding, graph drawing, graph spanners, etc.

This project aims at generalizing these oriented structures to higher genus surfaces and higher dimensional objects. Recent results have been obtained in this direction by members of the project, thus opening new axes of research. The first steps of the project consist in finding the natural generalization of the considered structures, proving their existence, and studying their properties. Then the goal is to find bijections and applications of these objects that extend the planar case.

Coordinator : Jean-François Delmas

LaBRI coordinator : Jean-François Marckert

Other partners : Université Paris 6, Orléans, Nancy

Description : ARBRES ALEATOIRES CONTINUS ET APPLICATIONS

Les arbres aléatoires continus font l'objet d'une recherche extrèmement active actuellement du fait de leurs nombreuses applications. Nous voulons étudier dans ce projet différents aspects de ces arbres aléatoires :

Processus à valeurs arbres continus et marches aléatoires sur des arbres aléatoires

Fragmentation

Graphes planaires

Percolation

Coordinator : Mireille Bousquet Mélou (LaBRI)

Other partners : LAMA, Univ. Versailles (coord. Brigitte Chauvin), LIX, Ecole Polytechnique (coord. Gilles Schaeffer), Projet RAP, INRIA Rocquencourt (coord. Philippe Robert), GREYC, Univ. Caen (coord. Brigitte Vallée)

Description : This federative programme, Random Discrete Structures and Algorithms, presents ambitious goals of fundamental research. The aim is to quantify the main properties of certain basic structures that occur recurrently in a variety of algorithms. The main chapters of our research programme deal with words, arithmetic structures, trees, graphs, as well as random generation. We plan to develop a consistent toolbox of methods that will allow us to determine very precisely the “profiles” of random objects: far beyond the study of average properties, we will provide complete distributions, quantify the risk of large deviations, and study the transient behaviour of the structures. This project is built on the combination of complementary view points, including combinatorial, probabilistic, analytic and dynamic approaches. Several of these approaches have a strong mathematical flavour, while our final goals deal with concrete algorithmic questions.

Coordinator : Xavier Viennot

LaBRI coordinator : Xavier Viennot

Other partners : Université Paris-Est (coord. Alain Lascoux)

Description : The project MARS is an interdisciplinary project, overlapping three main fields: computer science, mathematics and physics. The main goal is to attack the celebrated (in combinatorics and in quantum physics) Razumov-Stroganov conjecture about certain intergers appearing in the XXZ Heisenberg spins chains model. These intergers are related to the alternating sign matrices, introduced 25 years ago, for which tremendous efforts have been made by some of the top leaders in combinatorics, q-series or number partitions theory. We also plan to attack the longstanding problem of finding a bijection between these alternating sign matrices and the so-called totally symmetric self-complementary plane partitions. The project involves different domains: symmetric functions, Schubert polynomials, orthogonal polynomials, group of permutations, Markov chains, random discrete structures, computer experimentations, bijections, algorithmics and some background from data structures in computer science, combinatorial physics, etc...