Non conventional Analytic methods for Combinatorics – MétAConC

We have developed new conceptual tools for the analysis of divergent series and in particular series solutions of non-linear differential equation.
We have finely compared the conventional approaches of poisson / depoissonization with the Rice method, also using the Laplace transform. Researchers in the field use one or the other of these methods without ever comparing them. It is a work that involves a quintet of transformations «Poisson-Mellin-Rice-Newton-Laplace«
We have extended the dynamic analysis method to multi-dimensional Euclidean algorithms (the Brown algorithm and the Knuth algorithm). Such an analysis, therefore involves dynamic systems themselves multi-dimensional, and leads to the precise comparison between these two algorithms. This extension is also useful in modeling and analyzing network reduction algorithms.

We have continued to «revisit« conventional search algorithms when the search words are being sent from a dynamic source and the unit cost is the symbol comparison

Concerning the analysis of structures:
Trees in combinatorics have two important subfamilies: Simple trees and simple increasing trees. We have highlighted a third class called diamond trees that comes naturally in the study of concurrent processes. We have begun a detailed study of the parameters of these trees, which have led to the emergence of unconventional behaviors.

Concerning combinatorial physics:
Work on topological recurrence has been carried out, showing that the latter can be applied to general models of tensors.
We have worked on the problem of determining the arctic curve in the six-vertex model with boundary conditions of the boundary of the domain. We have developed an alternative method by which we recover the analytic expression previously conjectured in the square domain.

Concerning the random generation:
A first striking result was the fine study of the uniform random generation of permutations. For several years, it was recognized that the procedure known as «Knuth shuffle« or Fisher-Yates algorithm was optimal for the uniform generation of random permutations. This algorithm has some weaknesses (it is intrinsically sequential and executes a large number of remote swaps in memory). We have studied very finely another random generator (an initial version of which was proposed by Rao and Sandelius in the 1960s) and showed that this algorithm performs better than Fisher-Yates (both from a point of Theoretical view only at the level of the benchmarks). This result is a perfect example of the interest of algorithm analysis to obtain more efficient algorithms.

We wish to extend our analysis of divergent series. Our ultimate goal is to provide a new set of tools for the fine asymptotic analysis of these objects. At the present time, we have studied the parameters in the Riccati divergent equations that can be found in combinatorics in many situations (permutation theory, lambda-calculus, graph theory, diagrams, combinatorial maps, etc.). .). Our first results exhibited new phenomena (unconventional distributions, ...).

List of publications:
International revues:
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

International Conferences:
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)

For many years, we have maintained an constant and fruitful cooperation between France and Taiwan in the field of Algorithm
Analysis and Analytic Combinatorics. This collaboration has culminated last year with an award from the French Academy of
Sciences jointly obtained by C. Banderier, O. Bodini and H.-K. Hwang. The project MétaConc seeks continue the achievements
rewarded by this award, and aims to strengthen and further ciment this partnership. Our project deeply concerns Analytic
Combinatorics. This discipline focuses on the development of complex analysis tools which allow for a fine asymptotic analysis of the
behavior of combinatorial sequences. Many major advances were made by the French school founded by Ph. Flajolet (transfer
theorems, Rice method, ...). We wish to refine these tools and extend them to even more usage cases (methods to treat
non-0-analytic functions, non-basic functional equations or nonlinear differential equations).


- Combinatorial Structures and symbolic method: Here we want to enrich the symbolic method of new operators (Polya operators from the Coxeter groups, inverse Polya operators, scheduling operator generalizing box operators. Grafting and mutations on objects. But also, specifications and infinite iterated substitution, continued fractions, continued radicals ... Study isomorphisms of structures. Transfer from algebraic to holonomic classes, Swap of representations... The complex structures mixing additive and multiplicative behavior.

- The asymptotic analysis: Method of Rice, poissonisation-depoissonisation-Mellin, analysis of non-analytical series in 0, analysis of nonlinear differential equation, Ricatti equations and Painlevé, special functions, psi-series and unconventional development (DL with descending factorial, DL with bootstrapping such as Lambert expansion. Perturbation analysis, study of the operators described in axis 1 ...

-Analysis Algo and structures (applications): The lambda-terms, concurrent processes, combinatorial physical (maps, paving ...), graphs and hypergraphs (cacti graphes, hypergraphes modeling data bases), random sampling under Boltzmann model.