Méthodes analytiques non conventionnelles en Combinatoire – MétAConC

Nous avons developpé de nouveaux outils conceptuels pour l'analyse des séries divergentes et en particulier des series solutions d'équation différentielle non-linéaire.
Nous avons comparé finement les approches classiques de la poissonnisation/depoissonnisation avec la méthode de Rice, en utilisant également la transformée de Laplace. Les chercheurs du domaine utilisent l'une ou l'autre de ces méthodes sans jamais les comparer. C'est un travail qui fait intervenir un quintet de transformations « Poisson-Mellin- Rice-Newton- Laplace » 

Nous avons étendu la méthode d'analyse dynamique à des algorithmes d'Euclide multi-dimensionnels (l'algorithme de Brun, et celui de Knuth). Une telle analyse fait donc intervenir des systèmes dynamiques eux-mêmes multi-dimensionnels, et mène à la comparaison précise entre ces deux algorithmes. Cette extension est aussi utile dans les modélisations et les analyses d'algorithmes de réduction de réseaux.

Nous avons continué à « revisiter » les algorithmes de recherche classiques quand les mots à rechercher sont émis par une source dynamique et le coût unitaire est la comparaison de symboles

Concernant l'analyse de structures :
Les arbres en combinatoire admettent deux sous-familles importantes : Les arbres simples et les arbres croissants simples. Nous avons mis en lumière une troisième classe appelé les arbres diamants qui rentre de manière naturelle dans l'étude des processus concurrents. Nous avons commencé une étude fine des paramètres de ces arbres qui a fait émerger des comportements non classiques.

Concernant la physique combinatoire :
Des travaux autour de la récurrence topologique ont été menés, montrant que cette dernière peut s'appliquer à des modèles généraux de tenseurs.
Nous avons travaillé sur le problème de la détermination de la courbe arctique dans le modèle à six sommets avec des conditions aux limites de la frontière du domaine. Nous avons développé une méthode alternative, par laquelle nous récupérons l'expression analytique précédemment conjecturée dans le domaine carré.

Concernant la génération aléatoire :
Un premier résultat marquant a été l'étude fine de la génération aléatoire uniforme de permutations. Depuis plusieurs années, il était admis que la procédure appelé « Knuth shuffle » ou encore algorithme de Fisher-Yates était optimale pour la génération uniforme de permutations aléatoires. Cet algorithme a néanmoins quelques faiblesses (il est intrinsèquement séquentiel et exécute un nombre important de swaps éloignés en mémoire). Nous avons étudié très finement un autre générateur aléatoire (dont une version initiale avait été proposé par Rao et Sandelius dans les années 60) et montré que cet algorithme a des performances supérieures à celles de Fisher-Yates (à la fois d'un point de vue théorique qu'au niveau des benchmarks). Ce résultat est un parfait exemple d’intérêt de l'analyse d'algorithme pour obtenir des algorithmes plus efficaces.

Nous souhaitons prolonger notre analyse des structures à séries génératrices divergentes. Notre objectif ultime est de fournir une palette d'outils nouveaux pour l'analyse asymptotique fine de ces objets. Actuellement, nous nous sommes attaqués à l'étude des paramètres dans les équations divergentes de type Riccati que l'on rencontre en combinatoire dans de nombreuses situations (théorie des permutations, lambda-calcul, théorie des graphes, diagrammes, cartes combinatoires,...). Nos premiers résultats ont exhibé de nouveaux phénomènes (distributions non classiques,...).

Liste des principales publications :
Revues internationales :
1. A. Bacher, O. Bodini, H.K. Hwang, T.H. Tsai : Transactions on Algorithms (TALG), Volume 13 Issue 2, February 2017
2. O. Bodini, A. Genitrini, F. Peschanski : A quantitative study of pure parallel processes. In Electronic Journal of Combinatorics (EJC), 23, No. 1, P1.11, 39 pages, 2016
3. O. Bodini, A. Genitrini, N. Rolin : Pointed versus Singular Boltzmann Samplers : a Comparative Analysis. To appear in PUMA, 2016
4. H.-H. Chern, M. Fuchs, H.-K. Hwang, and R. Neininger : Dependence and phase changes in random m-ary search trees
Random Structures and Algorithms, to appear 2016
5. M. Fuchs, H.-K. Hwang, Y. Itoh, From coin-tossing to rock-paper-scissors and beyond: A log-exp gap theorem for selecting a leader, Journal of Applied Probability, to appear, 2017

Conférences internationales :
1. O. Bodini, A. Genitrini, and N. Rolin : Extended boxed product and application to synchronized trees. In Proc. Gascom'16
2. O. Bodini, M. Dien, X. Fontaine, A. Genitrini, H.K. Hwang : Increasing Diamonds. LATIN 2016: 207-219
3. O. Bodini, M. Dien, A. Genitrini, F. Peschanski : Entropic Uniform Sampling of Linear Extensions in Series-Parallel Posets.. Accepted for CSR'17
4. O. Bodini, M. Dien, A. Genitrini and F. Peschanski. :The Ordered and Colored Products in Analytic Combinatorics: Application to the Quantitative Study of Synchronizations in Concurrent Processes. In proc. of the 14th Workshop on Analytic Algorithmics and Combinatorics, ANALCO, 2017, p.16-30
5. M. Fuchs, H.-K. Hwang, Dependence between external path-length and size in random tries, AofA’2016, The 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Krakow, Poland, July 4–8, 2016
6. M. Drmota, M. Fuchs, H.-K. Hwang and R. Neininger,
External profile of symmetric digital search trees, in 2017 Proceedings of the Seventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO)

Depuis de nombreuses années, nous maintenons une collaboration intense et fructueuse entre la France et Taïwan dans le domaine
de l'analyse d'algorithmes et la combinatoire analytique. Cette collaboration a été récompensée l'an dernier par un prix de
l'Académie des Sciences décerné conjointement à C. Banderier, O. Bodini et H.-K. Hwang. Le projet MétaConc vise à renforcer et
rendre pérenne ce partenariat. Notre projet s'articule autour de la combinatoire analytique. Cette discipline s’intéresse au
développement d'outils d'analyse complexe pour rendre compte finement du comportement asymptotique de suites combinatoires.
De nombreuses avancées majeures ont été faites par l'école française fondée par Ph. Flajolet (théorèmes de transfert, méthode de
Rice,...). Nous souhaitons étendre et perfectionner ces outils (méthodes pour traiter les séries non analytiques en 0, ou des
équations fonctionnelles non élémentaires ou encore des équations différentielles non-linéaires,...). De manière plus détaillée, notre recherche d'oriente autour de trois axes :

- Structures Combinatoires et méthode symbolique : dans cet axe nous désirons enrichir la méthode symbolique de nouveaux opérateurs (opérateurs de Polya issu des groupes de Coxeter, Opérateur inverse des opérateurs de Polya, Opérateurs d'ordonnancement du type opérateur boite généralisé, algèbre des opérateurs. Opérateurs de type greffes et mutations. Mais aussi, spécifications à substitution et itérée infinie, fractions continués, radicaux continués... Etude des isomorphismes de structures : passage des classes algébriques aux classes holonomes, changement de représentations... Les structures complexes mélangeant additivité et multiplicativité.

- L'analyse asymptotique : Méthode de Rice, poissonisation-dépoissonisation-Mellin, analyse des séries non analytiques en 0, analyse des equations différentielles non-linéaires, équations de Ricatti et Painlevé, fonctions spéciales, psi-series et développement non conventionnel (DL en factoriel descendant, DL de type fonction de Lambert avec bootstrapping, analyse perturbative, étude des opérateurs décrits dans l'axe 1...

-Analyse d'algo et de structures (les applications) : Les lambda-termes, les processus concurrents, la physique combinatoire ( cartes, pavage,...), les graphes et hypergraphes (graphes cacti, modèle d'hypergraphes pour les bases de données,...), la génération aléatoire mulparamétrée sous modèle de Boltzmann.