Homepage of Samuel Alexandre Vidal
Combinatorial Algorithms

An Optimal Algorithm to Generate Pointed Trivalent Diagrams and Pointed Triangular Maps
Published in Theoretical Computer Science Volume 411, Issues 31–33, 28 June 2010, Pages 2945–2967.
[View online] [PDF] [A062980] [A129114] [A129115]

Abstract : A trivalent diagram is a connected graph with cyclic orientations and degree conditions on its vertices. It is the combinatorial description of an unembedded trivalent ribbon graph. We shall describe and analyze an algorithm giving an exhaustive list of trivalent diagrams of a given size. The list being non-redundant in that no two diagrams of the list are isomorphic. The algorithm will be shown to have optimal performances in that the time necessary to generate a diagram will be shown to be bounded in the amortized sense. What is striking is that the bound is uniform on the size of the diagrams being generated. One objective of the paper is to provide a reusable theoretical framework for algorithms generating exhaustive lists of complex combinatorial structures with attention paid to the case of unlabeled structures and to those generators having the CAT property.

Combinatorics and Group Theory

Counting Rooted and Unrooted Triangular Maps
In collaboration with M. Petitot.
Published in Journal of Nonlinear Systems and Applications. Volume 1, Number 1-2, Pages 51-57, 2010.

[PDF]

Abstract : In this paper, we describe a new way to count isomorphism classes of rooted triangular maps and unrooted triangular maps. We point out an explicit connection with the asymptotic expansion of the Airy function. The analysis presented here is used in a recent paper “Vidal (2007)” to present an algorithm that generates in optimal amortized time an exhaustive list of triangular maps of a given size.

Sur la Classification et le Denombrement des Sous-groupes du Groupe Modulaire et de leurs Classes de Conjugaison
[View online] [PDF] [arXiv] [A121350]

Abstract : In this paper we give a classification of subgroups of $\mathrm{PSL}_2(\mathbb{Z})$ and their conjugacy classes using combinatorial invarients : trivalent diagrams pointed or not. We also give explicite formulae counting isomorphism classes of those structures and several variations of them. Until now the counting of not pointed trivalent diagrams was an open problem. The methods extends to count rooted triangular maps. In the end of the paper we give an efficient algorithm to count those structures. It lays on an unexpected factoring of the cycle index series of those combinatorial species.

Trivalent Diagrams, Modular Group and Triangular Maps
[View online] [PDF] [A121350] [A005133] [A062980] [A129114]

Abstract : The aim of the paper is to give a preliminary overview of some of the results of the thesis prepared by the author. We propose a bijective classification of the subgroups of the modular group by pointed trivalent diagrams. Conjugacy classes of those subgroups are in one to one correspondence with unpointed trivalent diagrams. We also give in the form of generating series, the number of those trivalent diagrams both pointed or not, as well as generating series for both rooted and unrooted versions of triangular maps up to isomorphism. That later results was a difficult open problem for almost 150 years.

Stochastic Modeling

Models of Stochastic Gene Expression and Weyl Algebra
Published in Lecture notes in computer science. Algebraic and Numeric Biology: 4th International Conference, Anb 2010.
[PDF]

Abstract : This paper presents a symbolic algorithm for computing the ODE systems which describe the evolution of the moments associated to a chemical reaction system, considered from a stochastic point of view. The algorithm, which is formulated in the Weyl algebra, seems more efficient than the corresponding method, based on partial derivatives. In particular, an efficient method for handling conservation laws is presented. The output of the algorithm can be used for a further investigation of the system behaviour, by numerical methods. Relevant examples are carried out.

Differential Number Theory

Formes Différentielles et Corps de Nombres (Differential Forms and Number Fields)
Under the direction of Paul Gérardin [View online] [PDF]

Abstract : In that work, we describe an algebraic generalization of some basic differential geometry situation and its application to number fields. The objective among others was to extend a short note by A. Weil and while doing so we strive to clarify the striking analogy there is between function fields and number fields using examples borrowed from both geometry and arithmetics.