Motivated by the discovery of hard-to-find social networks in epidemiology, we consider the question of exploring the topology of random structures (such as a random graph G) by random walks. The usual random walk jumps from a vertex of G to a neighboring vertex, with providing information on the connected components of the graph G. The number of these connected components is the Betti number beta0 . To gather further information on the higher Betti numbers that describe the topology of the graph, we can consider the simplicial complex C associated to the graph G: a k-simplex (edge for k = 1, triangle for k = 2, tetrahedron for k = 3 etc.) belongs to C if all the lower (k − 1)-simplices that constitute it also belong to C. For example, a triangle belongs to C if its three edges are in the graph G. Several random walks have already been proposed recently to explore these structures. We introduce a new random walk, whose generator is related to a Laplacian of higher order of the graph and to the Betti number betak . A rescaling of the walk for k = 2 (cycle-valued random walk), and on regular triangulation of the torus, is also detailed. We embed the space of chains into spaces of currents to establish the limiting theorem.
Joint work with T. Bonis, L. Decreusefond and Z. Zhang.

Dans cette exposé, je présente une approche d’énumération asymptotique du type guess-and- check pour certaines récurrences, à travers de l’étude des arbres binaires compactés. Un arbre binaire compacté est un graphe acyclique dirigé qui encode un arbre binaire, où on garde une seule copie pour les sous-arbres identiques. Nous prouvons que le nombre des arbres binaires compactés de taille n est asymptotiquement Θ(n!4^n exp(3 a_1 n^(1/3) )n^(3/4) ), avec a_1 ∼ −2.338 la plus grande racine de la fonction d’Airy. Typiquement, cette expression asymptotique contient un exponentiel étiré, qui est rare et intéressant dans l’énumération asymptotique. Pour arriver à ce résultat, nous postulons d’abord une récurrence à deux paramètres pour ces nombres, puis nous devinons la forme de l’asymptotique et la démontrons toujours à travers de la récurrence. Je présenterai aussi quelques autres applications, et notre effort à généraliser cette méthode.
Travail commun avec Andrew Elvey Price et Michael Wallner.

Formal language membership is a classical problem with myriad applications. Intuitively, the goal is to succinctly describe the subset of strings that carry important information in order to be able to identify them efficiently. For instance, searching for all substrings that belong to a given regular language is a common task in web scraping. Furthermore, determining the well-formedness of a data file can be reduced to the Dyck language membership problem. Moreover, repetitions in biological sequences, such as palindromes and squares, often indicate sites of functional significance. The quick growth of data volume and the presence of noise in applications demand efficient and robust methods for membership testing, and this tutorial will provide a survey of such methods and open questions.