Starting from a presentation of the many recent applications of Galois theory of functional equations to enumerative combinatorics, we will introduce the Galois theory of (different kinds) of difference equations. We will focus on the point of view of the applications, hence with little emphasis on the technicalities of the domain, but I'm willing to do an hour of « exercises » (i.e. to go a little deeper into the proofs), if a part of the audience is interested.[-]

L'énumération des chemins du quadrant formés de petits pas (c'est-à-dire de pas aux 8 plus proches voisins) est maintenant bien comprise. En particulier, leur série génératrice est différentiellement finie (solution d'une ED linéaire à coefficients polynomiaux) si et seulement si un certain groupe de transformations rationnelles, associé à l'ensemble des pas autorisés (encore appelé modèle), est fini. Il n'est pas du tout évident d'étendre à des marches à pas plus grands les méthodes qui ont permis cette classification. Guy Fayolle et Kilian Raschel ont décrit les difficultés qu'il faut attendre si on essaie de généraliser l'approche par analyse complexe (laquelle est très puissante dans le cas de petits pas). Dans cet exposé, j'expliquerai comment étendre à des pas quelconques l'approche algébrique la plus simple, qui repose seulement sur des séries formelles. Elle ne s'applique qu'aux modèles à groupe fini, et encore, pas à tous : pour les chemins à petits pas, elle résout 19 des 23 modèles concernés, laissant de côté les 4 modèles algébriques. Mais elle est tout de même assez robuste : on verra par exemple que, pour des modèles à pas dans {-2,-1,0,1}$^2$ elle résout 231 des 240 modèles à groupe fini, mettant ainsi en lumière 9 modèles particulièrement intéressants.
Travail en commun avec Alin Bostan et Steve Melczer.[-]

Excursions are walks which start and end at prescribed locations. In this talk we consider the counting sequences of excursions, more precisely, the functional equations their generating functions satisfy. We focus on two sources of excursion problems: walks defined by their allowable steps, taken on integer lattices restricted to cones; and walks on Cayley graphs with a given set of generators. The latter is related to the cogrowth problems of groups. In both cases we are interested in relating the nature of the generating function (i.e. rational, algebraic, D-finite, etc.) and combinatorial properties of the models. We are also interested in the relation between the excursions, and less restricted families of walks.
Please note: A few corrections were made to the PDF file of this talk, the new version is available at the bottom of the page.[-]

Let $X_{n}$ be an ensemble of combinatorial structures of size $N$, equipped with a measure. Consider the algorithmic problem of exactly sampling from this measure. When this ensemble has a ‘combinatorial specification, the celebrated Boltzmann sampling algorithm allows to solve this problem with a complexity which is, typically, of order $N(3/2)$. Here, a factor $N$ is inherent to the problem, and implied by the Shannon bound on the average number of required random bits, while the extra factor $N$.[-]

Recently several papers appears on ArXiv, on various topics apparently unrelated such as: spin system observable (T. Helmuth, A. Shapira), Fibonacci polynomials (A. Garsia, G. Ganzberger), fully commutative elements in Coxeter groups (E. Bagno, R. Biagioli, F. Jouhet, Y. Roichman), reciprocity theorem for bounded Dyck paths (J. Cigler, C. Krattenthaler), uniform random spanning tree in graphs (L. Fredes, J.-F. Marckert). In each of these papers the theory of heaps of pieces plays a central role. We propose a walk relating these topics, starting from the well-known loop erased random walk model (LERW), going around the classical bijection between lattice paths and heaps of cycles, and a second less known bijection due to T. Helmuth between lattice paths and heaps of oriented loops, in relation with the Ising model in physics, totally non-backtracking paths and zeta function in graphs. Dyck paths, these two bijections involve heaps of dimers and heaps of segments. A duality between these two kinds of heaps appears in some of the above papers, in relation with orthogonal polynomials and fully commutative elements. If time allows we will finish this excursion with the correspondence between heaps of segments, staircase polygons and q-Bessel functions.[-]

There is the same number of $n \times n$ alternating sign matrices (ASMs) as there is of descending plane partitions (DPPs) with parts no greater than $n$, but finding an explicit bijection is, despite many efforts, an open problem for about $40$ years now. So far, four pairs of statistics that have the same joint distribution have been identified. We introduce extensions of ASMs and of DPPs along with $n+3$ pairs of statistics that have the same joint distribution. The ASM-DPP equinumerosity is obtained as an easy consequence by considering the $(-1)$enumerations of these extended objects with respect to one pair of the $n+3$ pairs of statistics. One important tool of our proof is a multivariate generalization of the operator formula for the number of monotone triangles with prescribed bottom row that generalizes Schur functions. Joint work with Florian Aigner.[-]