2024

Heure:	14:00 - 15:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Quelques progrès récents sur les fonctions G et les fonctions E
Description:	Javier Fresán Les fonctions G et les fonctions E sont des séries entières à coefficients algébriques qui sont solution d'une équation différentielle et satisfont à des conditions de croissance de nature arithmétique. Elles correspondent aux fonctions holonomes/D-finies qui apparaissent dans de nombreux problèmes en combinatoire, probabilité, physique. Elles ont été introduites dans le mémoire de Siegel sur les applications de l'approximation diophantienne en 1929, dans le but de généraliser les résultats de transcendence pour les valeurs de la fonction exponentielle en des arguments algébriques. Je survolerai de façon accessible quelques progrès récents, voire très récents, et moins récents sur les fonctions G et les fonctions E, en mettant l'accent sur deux questions : quelle est la structure de leurs équations différentielles ? quelle place occupent les fonctions hypergéométriques parmi elles ?

Heure:	15:00 - 15:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	The magic number pi: computation and proof of irrationality
Description:	Michael Drmota talk for the students, EUR Math&CS

Heure:	11:00 - 12:00
Lieu:	Salle C308, Institut Galilée, Université de Villetaneuse
Résumé:	A Knowledge Compilation Take on Binary Boolean Optimization
Description:	Florent Capelli The Binary Boolean Optimization (BPO) problem aims at finding the maximal value that a rational polynomial P(x) can take when x is supposed to be a vector with 0 and 1 values. This non-linear optimization problem has recently received renewed attention. Current techniques for solving it either involve to solve a linear relaxation of the problem or use dedicated algorithm exploiting some structure in the way monomials are interacting with one another, allowing one to skip large parts of the search space compared to the brute force approach. In this talk, we present and explore the consequences of an interesting connection between BPO instances and another well studied problem on Boolean functions: the Algebraic Model Counting (AMC) problem. Given a Boolean function f on variables X and a weight on each of its variable, the AMC problem aims at finding the sum of the weights of every satisfying assignments of f. This problem can encode a lot of different tasks by simply changing the underlying algebraic structure where the sum and products are made. This way, we show how one can reformulate BPO instances as an AMC problem on an algebraic structure known as the (max,+)-semiring. The consequences of this connection are manyfold. In particular, we are able to recover every known results on the tractablability of BPO problem from this connection and the existing literature on the complexity of AMC. More importantly, this connection allows us to discover new tractable classes for BPO and is flexible enough so that we can find tractable instances of the slight variations of BPO such as BPO with cardinality constraints or pseudo-Boolean BPO, two problems for which few tractability results where known. More importantly, this approach yields practical results: by running a modified version of d4, a tool originally made for knowledge compilation, so that it performs AMC on the (max,+)-semiring instead, we show that our approach is competitive with the existing ones on hard instances. This talk will cover a gentle presentation of the BPO problem and its connection with AMC. We will then give a quick overview on existing techniques for solving AMC that are based on Knowledge Compilation and how this approach is fruitful for solving extensions of the BPO problem. We will conclude by a presentation of the way d4 works and of our practical results.

Heure:	09:30 - 17:30
Lieu:	Amphithéâtre Euler, Institut Galilée
Résumé:	Journées MathStic Probabilités-Combinatoire 1
Description:	Mireille Bousquet-Mélou, Mingkun Liu, Armand Riera, Meltem Ünel, Baptiste Louf Ces journées s'inscrivent dans le cadre de l'axe 3 (Physique mathématique, Physique Statistique, Combinatoire) de la fédération de recherche Math-STIC de l'Université Sorbonne Paris Nord, qui associe les laboratoires de mathématiques (LAGA), d'informatique (LIPN) et de traitement et transmission de l'information (L2TI). Les exposés auront lieu dans l'amphi Euler de l'Institut Galilée. Des repas (buffets) seront proposés le midi. L'inscription est gratuite mais obligatoire (avant le 20 septembre) pour faciliter l'organisation. Jeudi 3/10 Mireille Bousquet-Mélou : Combinatorics of 3-coloured quadrangulations This talk deals with the enumeration of (planar) maps equipped with a proper 3-colouring of their vertices. The case of triangulations is well-understood, with an algebraic generating function and bijective solutions. The case of general planar maps is still algebraic, but the combinatorial explanations for that are missing. We will focus on quadrangulations, for which algebraicity is lost. We will see that this problem admits several interesting reformulations (in terms of orientations, of height functions...), which suggest to record in the enumeration other statistics, beyond the edge number. We will present solutions for some bivariate problems, obtained in collaboration with Andrew Elvey Price (Tours). Mingkun Liu : Length spectra of random metric maps: a Teichmüller theory approach In this talk, I will first discuss short closed geodesics on a random hyperbolic surface of large genus, and we will see that the lengths of these geodesics are distributed in exactly the same way as those of the short cycles in a big random map (following the work of Mirzakhani­­-Petri and Janson-Louf). Next, I will present a joint work with Simon Barazer and Alessandro Giacchetto, where we study random maps of large genus with a Teichmüller theory approach. Armand Riera : TBA Meltem Ünel : TBA Baptiste Louf : Counting with random walks We are interested in an enumerative problem, namely counting geometric objects called combinatorial maps, which can be parametrized by two numbers: their size, and a topological parameter called the genus. We are interested in an asymptotic estimation of the number of these objects when both the size and the genus go to infinity. While enumeration in one parameter is a very well studied topic with many powerful tools available, this problem is a case of bivariate enumeration, is a rather new topic with very few results known at the moment. Our method consists in studying a recurrence formula for these maps and modeling it by a random walk, forgetting completely about the combinatorics of the model. This is a work in progress with Andrew Elvey-Price, Wenjie Fang and Michael Wallner.

Heure:	09:00 - 16:00
Lieu:	Amphithéâtre Euler, Institut Galilée
Résumé:	Journées MathStic Probabilités-Combinatoire 2
Description:	Michael Drmota, Alice Contat, Andrew Elvey Price, Enrica Duchi, Quentin Berger Ces journées s'inscrivent dans le cadre de l'axe 3 (Physique mathématique, Physique Statistique, Combinatoire) de la fédération de recherche Math-STIC de l'Université Sorbonne Paris Nord, qui associe les laboratoires de mathématiques (LAGA), d'informatique (LIPN) et de traitement et transmission de l'information (L2TI). Les exposés auront lieu dans l'amphi Euler de l'Institut Galilée. Des repas (buffets) seront proposés le midi. L'inscription est gratuite mais obligatoire (avant le 20 septembre) pour faciliter l'organisation. Vendredi 4/10 Michael Drmota : The method of moments revisited with applications to planar maps The classical method of moments is used to prove limiting distributions by showing that properly centralized and/or scaled moments of a random variable converge to the corresponding moments of the limit. However, it is not always easy to obtain precise asymptotics for centralized moments - for example for proving a central limit theorem - due to "heavy cancellations". The main goal of this talk is to show some applications to random planar maps of a method of moments by Gao and Wormald that proves a central limit theorem without centralized moments. This is joint work with Eva-Maria Hainzl and Nick Wormald. Alice Contat : Parking on Cayley trees & Frozen Erdös-Rényi Consider a uniform rooted Cayley tree T_n with n vertices and let m cars arrive sequentially, independently, and uniformly on its vertices. Each car tries to park on its arrival node, and if the spot is already occupied, it drives towards the root of the tree and parks as soon as possible. Using combinatorial enumeration, Lackner & Panholzer established a phase transition for this process when m is approximately n/2 . We couple this model with a variation of the classical Erdös-Rényi random graph process. This enables us to describe completely the phase transition for the size of the components of parked cars using a modification of the standard multiplicative coalescent which we named the frozen multiplicative coalescent. The talk is based on joint work with Nicolas Curien. Andrew Elvey Price : Classification of D-finite walks in the quarter plane via elliptic functions Given a set of small steps, we consider the three variable generating function counting walks in the quarter plane using these steps. Since the seminal paper by Bousquet-Mélou and Mishna, the problem of characterising the generating function into the hierarchy Algebraic < D-finite < D-algebraic has received a lot of attention. For unweighted walks this characterisation is complete, however the existing proof of D-finiteness does not generalise to unweighted walks. In this talk I will describe our new proof that the generating function is D-finite in each variable if and only if the group of the walk is finite. This result applies to any weighted model is based on the elliptic function method. This is joint work with Thomas Dreyfus and Kilian Raschel. Enrica Duchi : TBA Quentin Berger : FK-percolation and Recursions on Galton-Watson Trees Some statistical mechanics models on trees may sometimes reduce to the study of some "simple" tree recursion; this is for instance the case for the FK-percolation model. It turns out that when the recursion is concave, we can compare this tree recursion to the one verified by (possibly non-linear) resistive networks. I will present a recent work with Irene Ayuso Ventura (Créteil), in which we obtain precise estimates on the asymptotic behaviour of non-linear conductances of Galton-Watson tree, also deriving some information on the FK-percolation model on random trees.