Journée-séminaire de combinatoire

Steinitz's lemma is about a finite set $V$ of at most unit vectors in $R^d$ whose sum equals zero. It states that the elements of $V$ can be ordered so that all partial sums along this ordering have norm at most 2d. I'm going to explain and prove a matrix version of this lemma. Moreover, I plan to give a bouquet of open questions from various areas of discrete and convex geometry.

A cross-cap drawing of a graph G is a drawing on the sphere with g distinct points, called cross-caps, such that the drawing is an embedding except at the cross-caps, where edges cross properly. I will first outline a connection between cross-cap drawings and an algorithm coming from computational biology to compute the signed reversal distance between two permutations. Then I will explain how this connection can be leveraged to answer two computational problems on graphs embedded on surfaces. This is joint work with Alfredo Hubard and Arnaud de Mesmay.

Some of my favorite problems that require no prerequisites. For instance, given an infinite collection of slabs in 3-space with divergent total width, can we translate each of them so that altogether they cover the unit ball?

À chaque sous-groupe H du groupe libre, on peut associer un unique graphe, dit graphe de Stallings de H, qui a des propriétés remarquables : il est fini si H est finiment engendré, calculable en temps presque linéaire à partir d'un ensemble de générateurs de H, et il permet de résoudre élégamment et efficacement un grand nombre de problèmes algorithmiques : calcul du rang et d'une base de H, calcul de l'index de H, calcul de l'intersection de deux sous-groupes, résolution du problème de l'appartenance uniforme… Des choses plus exotiques aussi, comme le calcul de la clôture pro-p de H ou de sa clôture algébrique. Comme ce graphe fini est assez contraint, on peut utiliser la combinatoire pour énumérer les graphes de Stallings et donc les sous-groupes, les générer aléatoirement, et aborder des questions asymptotiques : quelle est l'espérance du rang d'un sous-groupe du groupe libre, quelle est la probabilité qu'il soit d'indice fini, etc… On peut aussi évaluer la complexité en moyenne du problème de l'appartenance uniforme. La notion de graphe de Stallings peut être étendue aux sous-groupes quasi-convexes des groupes hyperboliques, et à des classes un peu plus larges. On y conserve la calculabilité. On peut par exemple étendre au groupe modulaire certains résultats algorithmiques et asymptotiques sur le groupe libre. Ma présentation sera appuyée sur la littérature classique (à commencer par Stallings 1983) et sur mes travaux, menés pour l'essentiel avec Frédérique Bassino et Cyril Nicaud.

En mode groupe de travail, nous verrons via quelle méthode Sharir et Welzl (en 2009) ont obtenu une borne sup pour le nombres de triangulations de $n$ points. Voir aussi la discussion sur cstheory stackexchange.

Machine learning theoretical models very often assume a dataset obtained from a Gaussian distribution, or from a Gaussian mixture. The possible limitations of such a Gaussian assumption have been recently object of investigation, and theoretically characterization, leading to a number of "Gaussian universality" results. In this talk I will present an analytical treatment of the performance in high dimensions of simple architectures on heavy-tailed distributed datasets, showing that even simple generalized linear models exhibit a striking dependence on non-Gaussian features in both classification and regression tasks.

Organisatrices : Thi Mai Trang Nguyen (L2TI), Thanh Mai Pham Ngoc (LAGA) et Céline Rouveirol (LIPN)

Programme :
13h30 - Bienvenue - Session 1
13h30 - 14h00 : Predicting Lagrangian Multipliers for Mixed Integer Linear Programs (Francesco Demelas, Joseph Le Roux, Mathieu Lacroix, Axel Parmentier, LIPN et Ecole des Ponts)
14h00 - 14h30 : A Deep Learning Approach for Predicting Radio Channels across Frequency in Mobile Networks (Pegah Alizadeh - Ericsson France)
14h30 - 15h00 : Adaptive Estimation on Nonparametric Geometric Graphs (Thanh Mai Pham Ngoc - LAGA)
15h00 - 15h30 : Temporal Data Aggregation in Wireless Sensor Networks for Indoor Air Quality monitoring (Janeth Aguilar, Liticia Djennabi, Salvador Ruiz Correa, Gladys Diaz et Khaled Boussetta - L2TI et IPICYT, Mexico)
15h30 - 15h45 : Pause café
15h45 - Session 2
15h45 - 16h15 : Choix des Participants Basé sur le Score pour l'Apprentissage Fédéré dans le Contexte de la Détection d'Intrusion Réseau (Diogo Menezes Ferrazani Mattos - Université Fédérale de Fluminense, Brésil)
16h15 - 16h45 : Inference of Social Networks Explored by Random Walks (Viet Chi Tran, LAMA, Université Gustave Eiffel)
16h45 - 17h15 : Optimisation des Blocs de Ressources dans un Réseau 5G en Utilisant une IA Hybride (Ouamri Mouhamed Amine - L2TI)
17h15 - 17h45 : Leveraging Complex Network Analysis for Explainable Network Intrusion Detection (Rushed Kanawati - LIPN)
17h45 - Fin de la journée

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 ?

The Laguerre polynomials are a family of orthogonal polynomials which have been well-studied in combinatorics. The coefficients of these polynomials enumerate a certain family of graphs which have been called Laguerre digraphs or Laguerre configurations. The polynomial sequence has a well-known Stieltjes moment representation, i.e., these polynomials can be expressed as the sequence of moments of a certain measure supported on the positive real-axis. It is known that a sequence is a Stieltjes moment sequence if and only if its Hankel matrix is totally positive. A natural question is to ask if the Hankel matrix is also coefficientwise totally positive. We will address this question in this talk. We will begin by stating the main theorem which will not require any prerequisites. We then motivate this result; we first state the equivalence between Stieltjes moment sequences and the total positivity of Hankel matrices, then we mention how this theory has been extended coefficientwise. We introduce the production-matrix method which is a powerful tool to prove total positivity. Finally, we sketch a proof of our main theorem.

This talk will be on popular matchings in the one-sided preferences model. Popular matchings need not always exist in this model and there is a simple combinatorial algorithm to decide if one exists. We will see an LP-duality inspired algorithm for the more general problem of deciding if a popular assignment (i.e., a popular maximum-matching) exists or not. This algorithm can be generalized to solve the popular common base problem in the intersection of two matroids where one matroid is the partition matroid, this implies the popular arborescence problem (relevant in liquid democracy) can be solved efficiently.

In this talk we will consider algorithms for finding optimal popular matchings. While it is easy to find max-size popular matchings, it is NP-hard to find a min-cost popular matching. This motivates us to relax popularity to a weaker notion called "quasi-popularity". Describing the popular and quasi-popular matching polytopes is hard, but there is an easy-to-describe integral polytope sandwiched between these two hard ones (see the illustration). So we can efficiently find a quasi-popular matching of cost at most that of a min-cost popular matching.

The problem of computing a stable matching in a bipartite graph is an old and well-studied problem. Gale and Shapley showed in 1962 that such a matching always exists and can be efficiently computed. This is a classical result in algorithms with many applications in economics and computer science. Stability is a strong and rather restrictive notion. This series of talks will be on a relaxation of stability called "popularity". In the first talk we will see simple and efficient algorithms for some popular matching problems. No background in algorithms or matching theory will be assumed.

The arc complex is a pure flag simplicial complex associated to a finite-type topological surface with marked points. It was discovered by Harvey and used by geometers like Harer, Penner, Bowditch, Epstein to study geometric properties of hyperbolic surfaces, their Teichmüller spaces and their mapping class groups. The arc complex is also a subcomplex of the cluster complex of a cluster algebra, defined by Fomin-Zelevinksy. For most of the surfaces, the arc complex is locally non-compact. In this talk, I will discuss about the simplicial topology of the arc complex in the finite cases. In particular, I will focus on the shellability (analogous to simply-connectedness) and collapsibility (analogous to contractibility) of these finite complexes and prove that they are closed combinatorial balls.

Nous discuterons de la limite de faible intensité des tessellations de Poisson--Voronoï sur les espaces hyperboliques, alias tessellations idéales de Poisson--Voronoï (IPVT de l'anglais). En particulier, nous verrons comment une simple description poissonnienne de la cellule qui contient l'origine de l'espace hyperbolique (cellule zéro) permet d'étudier des propriétés fines des tuiles de l'IPVT. L'exposé présentera des impressions en 3D de réalisations de la cellule zéro de l'IPVT de l'espace hyperbolique tridimensionnel dans le modèle de la boule de Poincaré. Travail en collaboration avec Nicolas Curien, Nathanaël Enriquez, Russell Lyons et Meltem Ünel. Pour en savoir plus sur les bijoux : https://matteodachille.github.io/ipvt

We introduce nondeterministic walks, a new variant of one-dimensional discrete walks. The main difference to classical walks is that its nondeterministic steps consist of sets of steps from a predefined set such that all possible extensions are explored in parallel. We discuss in detail the nondeterministic Dyck step set $\{ \{-1\}, \{1\}, \{-1,1\}\}$ and Motzkin step set $\{\{-1\}, \{0\}, \{1\}, \{-1,0\}, \{-1,1\}, \{0,1\}, \{-1,0,1\}\}$, and show that several nondeterministic classes of lattice paths, such as nondeterministic bridges, excursions, and meanders are algebraic. The key concept is the generalization of the ending point of a walk to its reachable points, i.e., a set of ending points. We extend our results to general step sets: We show that nondeterministic bridges and several subclasses of nondeterministic meanders are always algebraic. We conjecture the same is true for nondeterministic excursions, and we present python and Maple packages to support our conjecture. This research is motivated by the study of networks involving encapsulation and decapsulation of protocols. Our results are obtained using generating functions, analytic combinatorics, and additive combinatorics. Joint work with Élie de Panafieu.

Puisque la réductibilité d'une matrice M se traduit à la fois en termes de conjugaison avec une matrice contenant un bloc nul et en termes de positivité de ses puissances, il a paru intéressant d'étudier la présence et la persistance de termes nuls (les zéros) dans les différentes puissances de M.

On apprendra que les zéros d'une matrice non-négatives se diversifient en trois catégories, que la présence de zéros "permanents" est équivalente à la réductivité et possède une traduction "visuelle" simple, on en déduira une caractérisation originale des matrices réductibles, un algorithme élémentaire de réduction dans le cas non-négatif.

Un arbre couvrant d'un graphe connexe fini G est un sous-graphe connexe de G qui contient chaque sommet et ne contient aucun cycle. Un résultat bien connu d'Aldous énonce que la limite d'échelle de l'arbre couvrant uniforme du graphe complet est l'arbre brownien. En fait cet énoncé est plus général : l'arbre brownien est la limite d'échelle des arbres couvrants uniformes pour un grand ensemble de graphes en grande dimension. Dans cet exposé, nous allons essayer d'expliquer ce phénomène universel, à l'aide des algorithmes d'échantillonnage. Si le temps nous permet, nous allons également discuter des limites d’échelle des arbres couvrants aléatoires non-uniformes. Travaux en collaboration avec Asaf Nachmias et Matan Shalev.

A combinatorial substitution is a map over tilings which allows to define sets of tilings with a strong hierarchical structure. We show that such sets of tilings are sofic, that is, can be enforced by finitely many local constraints. This extends some similar previous results (Mozes’90, GoodmanStrauss’98) in a shorter presentation.

Le cas le plus simple et peut-être le plus naturel des limites locales des arbres est Uniform Infinite Planar Tree: on commence par la suite des mesures de probabilité uniforme \nu_N dont le support est l’ensemble des arbres planes enracinés de taille $N$ et on étudie la limite faible $\nu$ de cette suite, dont le support est l'ensemble des arbres plans enracinés de taille infinie. Une modification naturelle dans la recherche des limites différentes est de pondérer les arbres: est-ce que la nouvelle suite des mesures $\rho_N$, par rapport à laquelle la valeur d’un arbre de taille N est proportionnelle à son poids, admet une limite faible? Dans cet exposé, on considère des arbres plans enracinés dont la distribution est uniforme pour une hauteur $h$ et une taille $N$ fixées et dont la dépendance à la hauteur est de forme exponentielle, $\exp(-\mu h)$, pour $\mu$ réel. En définissant le poids total de ces arbres de taille $N$ fixe comme $Z^{\mu} _N$, on détermine son comportement asymptotique pour $N$ grand, pour $\mu$ réel quelconque. Finalement, on identifie la limite locale des mesures de probabilité correspondantes et on trouve une transition à $\mu=0$ d'une phase à une seule épine à une phase à plusieurs épines (backbone). En conséquence, il y a une transition dans le taux de croissance du volume des boules autour de la racine en fonction du rayon, passant d'une croissance linéaire pour $\mu < 0$ à la croissance quadratique familière pour $\mu=0$ et à une croissance cubique pour $\mu > 0$.

In a joint work with Valentin Féray, we prove, under mild conditions on fixed points and two cycles, the asymptotic normality of vincular pattern counts for a permutation chosen uniformly at random in a conjugacy class.Additionally, we prove that the limiting variance is always non-degenerate for classical pattern counts. The proof uses weighted dependency graphs.

Combinatorial depth measures are a way to generalize the concept of medians to higher dimensions, formalizing our intuition that some query points lie „deeper“ within a set of data points than others. Several such measures have been introduced in the last century, such as Tukey depth or Simplicial depth. Many fundamental problems in discrete geometry, such as the centerpoint theorem or Tverberg’s theorem, can be phrased naturally in terms of depth measures. In my talk, I consider families of combinatorial depth measures defined by natural sets of axioms and show that they cannot differ too much.

Considérons un arbre enraciné dont les sommets seront interprétés comme des places de parking, chaque place pouvant accueillir au maximum une voiture. Sur chaque sommet de l’arbre, on ajoute une étiquette entière et positive représentant le nombre de voitures arrivant sur ce sommet. Chaque voiture essaie de se garer sur son sommet d'arrivée et, si la place est occupée, elle descend en direction de la racine de l'arbre jusqu'à ce qu'elle trouve un sommet vide où se garer. S'il n'y a pas de sommet libre sur le chemin vers la racine, la voiture sort de l'arbre, contribuant ainsi au flux de voitures à la racine. Ce modèle présent une transition de phase intéressante que nous allons analyser en détail. Après un aperçu du cas où l'arbre sous-jacent est un arbre critique de Bienaymé-Galton-Watson, nous nous concentrerons sur le cas de l'arbre binaire infini, où la transition de phase qui s'avère être "discontinue". Si le temps le permet, je montrerai que notre technique s’applique également aux arbres surcritiques avec loi géométrique, grâce aux résultats d’énumération de Linxiao Chen. L'exposé est basé sur un travail joint avec David Aldous, Nicolas Curien et Olivier Hénard, et avec Linxiao Chen.

We introduce a new poset structure on Dyck paths where the covering relation is a particular case of the relation inducing the Tamari lattice. We prove that the transitive closure of this relation endows Dyck paths with a lattice structure. We provide a trivariate generating function counting the number of Dyck paths with respect to the semilength, the numbers of outgoing and incoming edges in the Hasse diagram. We deduce the numbers of coverings, meet and join irreducible elements. We give a generating function for the number of intervals, and we compare this number with the number of intervals in the Tamari lattice. Finally, we present a sequent calculus capturing this new Lattice.

La série génératrice des cartes orientables pondérées (et sa généralisation aux constellations) peut s’exprimer simplement à l’aide des fonctions de Schur. La série des cartes non-orientées (c’est-à-dire orientable ou non) admet une expression similaire où les fonctions de Schur sont remplacées par les polynomes zonaux. Dans ces deux cas, il existe une grande diversité d’outil permettant d’étudier ces objets: théorie des représentations, décomposition combinatoires, lien avec la théorie des matrices aléatoires, propriétés d’intégrabilité, etc. Les polynômes de Jack sont une déformation à un paramètre $b$ (dite b-déformation) qui interpole ces deux cas. Seulement, la déformation rend plus délicate l’étude de la série génératrice associé, source de deux conjectures proposées par Goulden et Jackson en 96. Dans cet exposé, je rappellerai les propriétés des constellations b-déformées introduites récemment par Chapuy et Dolega et soulignerait certaines des difficultés induite par la b-déformation pour étudier ces objets. Je présenterai des résultats récents en collaboration avec V. Bonzom nous permettant d’extraire un ensemble d’EDP pour certains modèle de constellations. Je parlerai également de travaux en cours permettant de donner une interprétation géométrique du poids en b des constellations.

Dans cet exposé, je présenterai une notion d’arbre de décomposition d’un ensemble de points dans le plan (plus précisément de son chirotope, la fonction qui encode l'orientation de tout triplet de point de l'ensemble). Cette décomposition, qui s'appuie sur le concept d'ensembles de points s'évitant mutuellement ("mutually avoiding sets"), s'inspire de la décomposition modulaire des graphes. J'expliquerai pourquoi cette décomposition est canonique, et comment elle peut être utilisée pour calculer le nombre de triangulations d'un chirotope à l'aide de sa décomposition. Il s'agit d'un travail commun avec Mathilde Bouvel, Valentin Féray et Xavier Goaoc. In this talk, I'll introduce a notion of decomposition tree of a planar point set (more precisely, of its chirotope, that is the function encoding the orientation of any triplet of points in the set). This decomposition relies on the concept of mutually avoiding point sets, and is inspired by the modular decomposition of graphs. I'll explain why this decomposition is canonical, and how it can be used to compute the number of triangulations of a chirotope using its decomposition. This is a joint project with Mathilde Bouvel, Valentin Féray and Xavier Goaoc.

Associé à un groupe de Weyl, il y a deux ensembles d’objets combinatoires, comptés par les nombres de Catalan généralisés, qui s’appellent les partitions non-croisées et les partitions non-imbriquées. Ces objets ont des liens très intéressants avec la théorie des représentations d’algèbres : pour ne citer qu’un résultat, par exemple, les partitions non-croisées sont en bijection avec les sous-catégories "wide" de la catégorie des modules sur des algèbres héréditaires de type finie. La question d’une relation exacte entre ces deux objets n’admet que des réponses partielles. Récemment, nous avons mis en lumière des liens supplémentaires, renforçant certains liens déjà connus, dans le cas du groupe symétrique : pour tout élément de Coxeter standard, nous construisons une bijection équivariante entre les partitions non-croisées sous l’action du complément de Kreweras et les partitions non imbriquées sous une action cyclique particulière, que nous appelons le complément de Kroweras. Cette bijection équivariante, construites à partir de règles locales, est l’unique bijection qui est à la fois équivariante et qui préserve le support. Dans cet exposé, je vais tenter de faire le tour de tous les ingrédients nécessaires, en exposant des aspects davantage tirés vers la théorie des représentations, afin d’aboutir à la construction de cette bijection. Ces travaux sont en collaboration avec Gabriel Frieden, Alessandro Iraci, Florian Schreier-Aigner, Hugh Thomas et Nathan Williams.

La richesse de l'étude combinatoire des polytopes repose grandement sur le paradoxe entre leur extrême banalité dans toutes sphères des mathématiques et la grande difficulté à établir des théorème combinatoires généraux sur ceux-ci. En prenant une sous-famille des polytopes, les zonotopes, dont la structure est beaucoup plus algébrique, nous avons démontré un certain nombre de résultats énumératifs asymptotiques. Tout d'abord sur le nombre de types combinatoires de polytopes équiprojectifs, ce qui ouvre de nouvelles perspectives sur une question ouverte posée par Shephard en 1968 d'une construction explicite de tous ces polytopes. Ensuite, dans le domaine des polytopes entiers, c'est à dire les polytopes dont les sommets sont de coordonnées entières (dans R^d), nous avons calculé l'équivalent asymptotique du nombre de zonotopes entiers dans un hypercube. Ce résultat nous permet d'améliorer les résultats de Barany Bureau et Lund en donnant le deuxième ordre de la convergence d'un zonotope entier dans un cône dont les deux extrémités sont fixées. Tout cela nous permet enfin d'établir un théorème limite fonctionnel pour les polygones entiers uniformément aléatoires dans un carré, où apparaît un pont Brownien avec une dérive étonnante, car c'est une courbe cubique.

Jury :
Frédérique Bassino, USPN - Examinatrice
Olivier Bodini, USPN - Examinateur
Luca Castelli Aleardi, Ecole polytechnique - Examinateur
Nathanaël Enriquez, Université Paris Saclay Examinateur
Xavier Goaoc, Univ. de Lorraine - Rapporteur
Philippe Marchal, CNRS, USPN - Directeur
Jean-François Marckert, CNRS Université de Bordeaux - Rapporteur
Lionel Pournin, USPN - Directeur

Un pavage du plan est composé d'ensembles fermés appelés tuiles, qui couvrent le plan euclidien sans trou ni chevauchement. Ma thèse porte sur des pavages quasipériodiques : bien qu'ils ne soient pas périodiques, on y trouve partout les mêmes motifs finis et leurs propriétés peuvent être assez fortes. Les plus connus sont les pavages de Penrose, qui combinent un grand nombre de propriétés. On peut en effet les définir par des règles locales, des substitutions, par coupe et projection, ou comme système dynamique symbolique. De manière générale, les pavages quasipériodiques se définissent par une seule de ces méthodes, et on se demande quels liens il peut y avoir entre différentes façons de les définir ou représenter. La structure combinatoire d'un pavage peut être étudiée via le graphe d'adjacence des tuiles (ou graphe dual). Dans un tel graphe, on s'intéresse aux sous-arbres induits ayant le plus grand nombre possible de feuilles à nombre n de sommets fixé. La suite de ces maxima est appelée ``fonction feuille''. Dans ma thèse, je détermine la formule de la fonction feuille des pavages de Penrose, en utilisant les substitutions et règles locales pour exhiber une famille de sous-arbres induits ``pleinement feuillus'' arbitrairement grands. Ensuite, comme les barres d'Ammann des pavages de Penrose joué un rôle dans l'étude du problème ci-dessus, on tente de mieux les comprendre via la notion de sous-périodes, qui découlent d'un schéma de coupe et projection. On définit grâce à celles-ci une méthode permettant de trouver des barres d'Ammann pour de nombreux pavages, en construisant des jeux de tuiles décorées, qui sont apériodiques. Les pavages en questions peuvent alors être obtenus en assemblant les tuiles façon puzzle plutôt que par coupe et projection. Enfin, en utilisant les règles locales, on construit aussi un jeu de tuiles de Wang associé aux pavages golden octagonal. La démarche suivie permet en outre d'établir un lien explicite entre schéma de coupe et projection et partition de Markov offrant une représentation symbolique de ces pavages. Le caractère substitutif des pavages golden octagonal est montré.

Jury :
Alexandre BLONDIN MASSÉ, Université du Québec à Montréal - Directeur de thèse
Olivier BODINI, Université Sorbonne Paris Nord - Examinateur
Émilie CHARLIER, Université de Liège - Rapportrice
Thomas FERNIQUE, Université Sorbonne Paris Nord - Directeur de thèse
Samuel PETITE, Université de Picardie - Rapporteur
Christophe REUTENAUER, Université du Québec à Montréal - Examinateur
Laurent VUILLON, Université de Savoie - Examinateur

Comment empiler un nombre infini d’oranges pour maximiser la proportion de l’espace couvert ? Kepler a conjecturé que l’empilement des "balles de canon" est optimal. 400 ans se sont écoulés avant que cette conjecture soit démontrée par Hales et Ferguson dont la preuve comporte 6 papiers et des dizaines de milliers de lignes de code informatique. Comment arranger un nombre infini de pièces de monnaie de 3 rayons différents sur une table infinie pour maximiser la proportion de la surface couverte ? Un arrangement de disques est dit triangulé si chacun de ses "trous" est borné par trois disques mutuellement tangents. Connelly a conjecturé que si de tels arrangements existent, l’un d’eux maximise la proportion de la surface couverte; cela est vrai pour les arrangement unaires et binaires. Dans cette thèse, nous étudions diverses techniques utilisées dans la preuve de la conjecture de Kepler ainsi que dans d’autres résultats importants de le domaine des arrangements de disques et de sphères, tels que la redistribution de la densité locale basée sur la recherche par l’ordinateur et l’arithmétique d’intervalles. Cela nous permet de prouver l’assertion de la conjecture de Connelly pour 31 triplets de rayons de disques triangulés et de la réfuter pour 45 autres triplets. En outre, nous obtenons des bornes précises sur la densité locale des cellules simpliciales dans les empilements à 2 sphères en 3D.
Jury :
Sandor Fekete, Univ. de Braunschweig - Rapporteur
Thomas Fernique, USPN - Directeur
Xavier Goaoc, Univ. de Lorraine - Examinateur
Nabil Mustafa, USPN - Examinateur
Michael Rao, ENS de Lyon - Rapporteur
Nathalie Revol, ENS de Lyon - Examinatrice
Guillaume Theyssier, Univ. d'Aix-Marseille - Examinateur

La présentation sera en anglais et sera suivie d'un pot en salle café (A201) auquel vous êtes également invités.

Pour plus de détails, https://lipn.univ-paris13.fr/~pchelina/PhD_defense.html

We study the enumeration of closed walks of given length and algebraic area on the honeycomb lattice. Using an irreducible operator realization of honeycomb lattice moves, we map the problem to a Hofstadter-like Hamiltonian and show that the generating function of closed walks maps to the grand partition function of a system of particles with exclusion statistics of order g=2 and an appropriate spectrum, along the lines of a connection previously established by two of the authors. Reinterpreting the results in terms of the standard Hofstadter spectrum calls for a mixture of g=1 (fermion) and g=2 exclusion whose physical meaning and properties require further elucidation. In this context we also obtain some unexpected Fibonacci sequences within the weights of the combinatorial factors appearing in the counting of walks. (Joint work with Stéphane Ouvry and Alexios P. Polychronakos)

Depuis plus de 70 ans maintenant, le problème du dénombrement des polygones auto-évitants sur les réseaux réguliers du plan résiste aux efforts des mathématiciens. Pour poser ce problème, considérons un graphe planaire infini dont tous les nœuds sont identiques, comme le réseau carré. On fixe un noeud sur ce graphe et on considère toutes les trajectoires sur le graphe partant de ce nœud et revenant à celui-ci en dernière étape et ne repassant jamais deux fois par le même nœud: on obtient un polygone auto-évitant (SAP en anglais), la question étant de compter asymptotiquement les SAP de grande longueur. Les SAP apparaissent naturellement dans de nombreux processus aléatoires que nous présenterons brièvement. De fait, dénombrer les SAP a été quasiment exclusivement tenté à l'aide d'argument probabilistes, culminants dans la loi de Schramm-Loewner (SLE_k) pour laquelle on conjecture que SLE_8/3 reproduit la loi uniforme sur les SAP. Parallèlement à ces développements, une route purement déterministe dans l'études des SAP a lentement émergé, ceux-ci satisfaisant une extension semi-commutative de la théorie des nombres sur les monoids de Cartier-Foata. Dans cette extension, dénombrer les SAP revient à étendre le théorème des nombres premiers. Nous présenterons cette voie déterministe et en particulier comment des cribles de la théorie des nombres permettent de s'approcher du but, offrant au passage la première méthode générique pour évaluer les valeurs concrètement prises par la loi de probabilité SLE_2 sur les SAP et de nouvelles indications sur les chemins presque totalement auto-évitants.

La journée de rentrée du LIPN aura lieu mardi 10 octobre de 9h30 à 17h.
Elle sera l'occasion d'écouter les nouveaux membres du laboratoire, d'annoncer les actualités et les grandes échéances de l’année et de participer à une pièce de théatre forum sur l'inclusion dans la recherche.
9h30-11h45 Exposés des nouveaux recrutés : Silvia di Gregorio (AOC) Florent Koechlin (CALIN), Morgan Rogers (LoVe), Thomas Papastergiou (A3) (salle B107)
12h-12h30 Courte Assemblée Générale du LIPN (salle B107)
12h30-14h Buffet déjeunatoire (salle A201)
14h-16h Pièce de théatre sur l'inclusion par la Compagnie Entrées de Jeu (salle F003-004)
16h15 Pot de cloture (salle café A201)

It is known that the largest possible volume for the intersection of a d-dimensional unit hypercube with a hyperplane H through its center is the square root of 2. This happens when H is orthogonal to a diagonal of a square face of the hypercube. This question can be generalized by considering the hyperplanes H at a fixed distance t to the center of the hypercube. Vitali Milman asked which among these hyperplanes have an intersection of maximal volume with the hypercube and conjectured that this happens when H is orthogonal to a diagonal or a sub-diagonal of the hypercube, depending on the value of t. Several recent results on this question are presented in this talk. In particular, when t is large enough (and smaller than the circumradius of the hypercube), the maximal volume is achieved exactly when the hyperplane is orthogonal to a diagonal of the hypercube. For smaller values of t, local extremality results will be presented at the diagonals and sub-diagonals of the hypercube.

In an effort to provide breadth instead of going deep into a single topic, the talk will cover two sets of geometric problems that are unrelated and suitable for a general audience interested in discrete mathematics and algorithms. In the first part I will explain variants of the barrier resilience problem, where the aim is to go from a source point to a target point in the plane visiting as few monitored regions as possible. The problem appears in sensor networks and in robotics, and its solution is related to vertex-disjoint paths/cycles in graphs. In the second part I will talk about crossing numbers of graphs and what we know about the crossing number of planar graphs with an additional edge.

We propose a new method for obtaining the coefficients of complete asymptotic expansions in a systematic manner, which is suitable for various families of graphs in dense regime. The core idea is to introduce a new type of (bivariate) generating series for the expansion coefficients, which we call a coefficient generating function. We show that the coefficient generating functions possess certain general properties that make it possible to express the asymptotics in a short closed form and give a combinatorial meaning to their coefficients. Applications of our method include asymptotics of connected graphs, irreducible tournaments, strongly connected digraphs, satisfiable 2-SAT formulae and contradictory strongly connected implication digraphs. Moreover, using marking variables, we obtain asymptotics of the above families with a fixed number of connected, irreducible, strongly connected and contradictory components, respectively. This is joint work with Sergey Dovgal.

A multivariate generating function (MGF) is an analytic function in d variables ($d>1$) which encodes a d-dimensional array of numbers as its Taylor coefficients. In recent years we see the emergence of a theory of analytic combinatorics in several variables which enables us to compute the asymptotic expansions of an array of numbers from its MGF. I will illustrate this theory with some examples from graph enumeration problems, and explain the new challenges it brings up compared to analytic combinatorics in one variable.

Dans le modèle des partitions aléatoires considérées avec la mesure de Plancherel Poissonisée, la distribution de probabilité de la premiere partie d'une partition s'écrit en termes de déterminants de Toeplitz et elle se comporte, dans une certaine limite, précisément comme la distribution de Tracy-Widom pour GUE (Baik-Deift-Johansson). Le premier objectif de cet exposé est donc de comprendre ces résultats et le deuxième est d'explorer leur généralisations pour d'autres modèles de partitions aléatoires, avant et après limite.

Multitudinous probabilistic and combinatorial objects are associated with generating functions satisfying a composition scheme $F(z)=G(H(z))$. The analysis becomes challenging when this scheme is critical (i.e., $G$ and $H$ are simultaneously singular). Motivated by many examples (random mappings, planar maps, directed lattice paths), we consider a natural extension of this scheme, namely $F(z,u)=G(u H(z))M(z)$. We also consider a variant of this scheme, which allows us to analyse the number of $H$-components of a given size in $F$. We prove that these two models lead to a rich world of limit laws, where~we identify the key rôle played by a new universal law: the three-parameter Mittag-Leffler distribution, which is essentially the product of a beta and a Mittag-Leffler distribution. We also prove (double) phase transitions, additionally involving Boltzmann and mixed Poisson distributions, bringing a unified explanation of the associated thresholds. In all cases we obtain moment convergence and local limit theorems. We end with extensions of the critical composition scheme to a cycle scheme and to the multivariate case, leading to product distributions. Applications are presented for random walks, trees (supertrees of trees, increasingly labelled trees, preferential attachment trees), triangular Pólya urns, and the Chinese restaurant process.
(Based on a joint work with Markus Kuba and Michael Wallner, to appear in Annals of Applied Probability)

Travail en collaboration avec Étienne Bellin, Arthur Blanc-Renaudie, Emmanuel Kammerer.

Dans le but d'étudier la mosaïque de Voronoi de processus ponctuels aléatoires vides de points dans de grandes régions, nous nous intéressons à la mosaïque de Voronoi dans le plan tout entier, d'un processus ponctuel de Poisson d'intensité uniforme sur le demi plan et d'intensité nulle dans son complémentaire. Dans le demi plan ne contenant pas de points, elle donne lieu à des cellules arbitrairement allongées dont nous decrirons la limite en loi après renormalisation convenable. Travail en collaboration avec Pierre Calka et Yann Demichel.

Le théorème d’isomorphisme de Dynkin ainsi que ses dérivées, sont des identités en loi reliant, pour la plupart, les temps locaux d’un processus de Markov à des processus permanentaux. Malgré leurs utilisations variées, elles demeurent des identités en loi sans interpretation trajectorielle simple. Nous proposerons une nouvelle lecture de l’identité surnommée « second théorème de Ray-Knight généralisé » et du théorème d’isomorphisme de Sznitman.

We use the interior of the arc complex to parametrise all those deformations of an ideal polygon, with vertices decorated with horoballs, that uniformly lengthen every edge and diagonal. This is done by using strip deformations, following the work of Danciger-Guéritaud-Kassel in Margulis spacetimes via the arc complex. As a consequence we get that the interior of the arc complex is an open PL-manifold of dimension one less than that of the deformation space of the polygon.

A set of shapes is called aperiodic if the shapes admit tilings of the plane, but none that have translational symmetry. A longstanding open problem asks whether a set consisting of a single shape could be aperiodic; such a shape is known as an aperiodic monotile or sometimes an "einstein". The recently discovered "hat" monotile settles this problem in two dimensions. In this talk I provide necessary background on aperiodicity and related topics in tiling theory, review the history of the search for for an aperiodic monotile, and then discuss the hat and its mathematical properties.

The rightmost particle in a branching Brownian motion at time $t$ is, with high probability, around position $2t - 3/2 \ln t$. The probability that it lies around position $c t$ with $c>2$ is exponentially small with time, with a rate which is known since Chauvin Rouault (1989). We investigate the details of these large deviations, using as a starting point an intriguing relation between the quantity we consider and the median position of the rightmost particle.

The asymmetric simple exclusion process is a paradigm of stochastic interacting particles, that was invented to describe low-dimensional transport with constraints. Thanks to its rich mathematical and combinatorial properties, exact solutions have been obtained for this system and have lead us to a better understanding of non-equilibrium statistical mechanics. The aim of this talk is to review some results about this model, describe the methods involved and present some recent developments.

We'll begin with a short survey on orthogonal polynomials and then we'll consider the following model. If a sequence indexed by nonnegative integers satisfies a linear recurrence without constant terms, one can extend the indices of the sequence to negative integers using the recurrence. Recently, Cigler and Krattenthaler showed that the negative version of the number of bounded Dyck paths is the number of bounded alternating sequences. In this talk we present two methods to compute the negative versions of sequences related to moments of orthogonal polynomials. We give a combinatorial model for the negative version of the number of bounded Motzkin paths. We also prove two conjectures of Cigler and Krattenthaler on reciprocity between determinants. Joint work with Donghyun Kim, Jang Soo Kim, Minho Song, U-Keun Song.

Combinatorial Physics is now a well-established interdisciplinary domain where combinatorics and physics interact in both directions. In this talk I will present how a particular problem in theoretical physics (namely the implementation of the so-called double scaling limit mechanism for various random tensor models) is successfully tackled using purely combinatorial methods.

Pour cette soutenance, j'introduirai les cartes combinatoires et les triangulations dites colorées en dimensions supérieures à 2. En dimensions 3 et plus, j'expliquerai les difficultés à classifier et énumérer les triangulations de variétés, y compris de la sphère. Les triangulations colorées offrent un cadre qui permet de représenter les triangulations comme des graphes aux arêtes colorées. Cela a permis de nombreuses avancées, et je donnerai notamment un théorème qui caractérise les collages de 3-boules maximisant le nombre d'arêtes. Initialement guidé par la perspective de construire d'autres modèles pour l'énumération de variétés en dimension 3, je me suis intéressé aux équations satisfaites par les séries génératrices de cartes. Je parlerai ici de la hiérarchie KP, connue notamment pour être à l'origine de magnifiques récurrences sur le nombre de cartes en fonction de la taille et du genre, et de sa généralisation aux cartes non-orientées. La soutenance sera présentée devant le jury composé de Bruno Benedetti (U. Florida, examinateur) Olivier Bodini (LIPN, président) Marthe Bonamy (LaBRI, examinatrice) Mireille Bousquet-Mélou (LaBRI, rapportrice) Éric Colin de Verdière (LIGM, examinateur) Nabil Mustafa (LIPN, examinateur) Gilles Schaeffer (LIX, rapporteur)

After a brief overview of recent advances in 2d quantum gravity related to JT gravity (Jackiw–Teitelboim gravity), we will suggest a different approach that relies on self-overlapping curves. We will then see how the algorithmic and combinatorial properties of those curves can be analysed numerically.

After a brief overview of recent advances in 2d quantum gravity related to JT gravity, we will suggest a different approach that relies on self-overlapping curves.
We will then present some algorithmic and combinatorial properties of those curves.

The advent of tensor models (TM) in physics (quantum gravity theory) has produced eminent results that put them at the center of discussions in the early 90s. TM generalize matrix models producing the famous random maps whose continuum limit is known as the Brownian sphere. They therefore define useful tools for understanding discrete and random geometries in dimension greater than or equal to 3 as well as their continuum limits. My research, during the last past years, focused on their extension in a field theoretic setting. We discover several crucial features of these field theories, both at the mathematical and physical level, and for all results, combinatorics plays a pivotal role. Combinatorics indeed illustrates the fertile link between mathematical physics, algebra and computer science that this thesis reports.

Plan of the presentation:
Intro
1 Graphs and stranded graphs
2 Tensor Field Theories: Renormalization Group analysis
3 Polynomial invariants for weakly colored graphs
4 Enumeration, topological and algebraic structures on tensor graphs
5 A lattice interpretation of the Kronecker coefficient
Conclusion

Jury
Frédérique Bassino (Université Sorbonne Paris Nord)
Olivier Bodini (Université Sorbonne Paris Nord)
Robert De Mello Koch (University of Witwatersrand), rapporteur.
Harald Grosse (Universität Wien), rapporteur.
Maxim Kontsevich (Institut des Hautes Etudes Scientifiques)
Manfred Salmhofer (Universität Heidelberg)
Gilles Schaeffer (Ecole Polytechnique), rapporteur.
Raimar Wulkenhaar (Westfälischen Wilhelms-Universität), rapporteur.

One can always transform a triangulation of a convex polygon into another by performing a sequence of edge flips, which amounts to follow a path in the graph G of the associahedron. The least number of flips required to do so is then a distance in that graph whose estimation is instrumental in a variety of contexts, as for instance in computational biology, in computer science, or in algebraic topology. On the other hand, it is known that paths in G correspond to a certain kind of 3-dimensional triangulation. This talk is about the recent proof that these 3-dimensional triangulations are flag when the corresponding path is a geodesic. This result, that provides a new powerful tool to study the geometry of G, can be thought of as a 3-dimensional analogue of a well-known strong convexity property of G. Several consequences on the computation of distances in G and on strong convexity in related graphs will be discussed. This talk is based on joint work with Zili Wang (Dartmouth College).

Beta-expansions are generalisations of the usual decimal or binary expansions to real bases. Instead of taking powers of a single base, we use powers of two bases where the exponents depend on the choice of the (binary) digit sequence. We study the question when such expansions are unique and give a characterisation of the pairs of bases that admit non-trivial unique expansions or even uncountably many unique expansions. This is directly related to the question when a binary shift defined by two lexicographic inequalities is non-trivial or uncountable, and the characterisation is in terms of S-adic words, where S consists of the Sturmian substitutions and the Thue-Morse substitution. This is joint work with Vilmos Komornik and Yuru Zou.

Betweenness centrality has been a long subject of study in network science since it was introduced by Freeman in 1977. This centrality measure asses the importance of nodes in a graph, it has been used for example in social, biological and research collaboration networks. Moreover, betweenness centrality has been used in graph partitioning and community detection in the well-known Girvan-Newan algorithm. A simple approach to compute betweenness centrality for all the nodes of a static graph is to use Floyd-Warshall algorithm that runs in $O(n^3)$. Brandes in 2001 published an algorithm that runs in $O(nm + n^2 \ln n )$ on weighted graphs, it is still considered one of the best theoretical results on the question. Betweenness centrality has also been extended to temporal graphs. Temporal graphs have edges that bear labels according to the time of the interactions between the nodes. Betweenness centrality has been extended to the temporal graph settings, and the notion of paths has been extended to temporal paths. Recent results by Buss et al. and Rymar et al. extended Brandes algorithm to the temporal setting with a general algorithm running in $O(n^2mT^2)$, where $T$ is the number of time units. Their results rise 2 questions, one is about the nature of temporal paths and the other considering the extension of Brandes algorithm to the temporal setting. In the seminar we will discuss these issues and address them. We will see that we are able to deploy Brandes algorithm to its full extent and improve the running time of these recent results to $O(nmT + n^2T \ln(nT))$. We will also discuss how Brandes algorithm can also be generalized to stream graphs which are dynamic graphs with continuous time and dynamicity on the nodes

I will explain how the exploration of graphs using Prim's algorithm, or invasion percolation, yields intuitive approaches to some scaling limits the classical multiplicative coalescent processes related to random graphs. This work is based on joint work with J.-F. Marckert.

Many processes involving growing trees/graphs are adding a small amount of nodes/edges at each step. Such models often exhibit statistics (like the degree distribution) which are not compatible with the ones observed e.g. in social networks. Is there a natural mathematical model which possess this fast growing rate feature? To this aim, we consider a new family of trees (introduced by Mahmoud): the exponential recursive trees. At each step, one adds (with probability $p$) a new child to each node of the tree. In this talk, we establish typical properties concerning the evolution at time $n$ of such a tree: its size, its number of leaves at depth $d$, its internal path length, its number of protected nodes. Using martingale theory, we give results on average or in $L^1$ and some of the corresponding limit distributions (characterized by their moments). We end with some open problems.

In this thesis we study rooted maps (graphs embedded on surfaces), the linear lambda-calculus, and their combinatorial interactions. Building upon recent bijective connections between these two domains, we make use of a combination of techniques drawn from map theory, logic, and combinatorics to study the structural properties of large random trivalent maps (both planar and of arbitrary genus) and linear lambda-terms, as well as that of various families of objects related to these. Some of the properties studied on maps of arbitrary genus and their corresponding families of lambda-terms include:
- The number of loops and bridges in trivalent maps and of identity and closed subterms in closed linear lambda-terms.
- The number of unary vertices in (1,3)-valent maps and of free variables in open linear lambda-terms.
- The number of binary vertices in (2,3)-valent maps and of unused abstractions in closed affine lambda-terms.
- The number of occurences of various patterns in trivalent maps and in closed linear lambda-terms.

Using the last, we obtain a lower bound on the average number of steps required to normalise a closed linear lambda-term.

As for planar maps, we study various parameters analogous to the above. We also present a novel interpretation of a recurrence by Goulden and Jackson for trivalent planar maps, based on the study of the planar lambda calculus.

*Composition of the jury*

Marie Albenque, École Polytechnique (Examiner)
Olivier Bodini, Université Sorbonne Paris Nord (Advisor)
Katarzyna Grygiel, Jagiellonian University (Invited)
Hsien-Kuei Hwang, Academia Sinica (Reviewer)
Damiano Mazza, CNRS and Université Sorbonne Paris Nord (Examiner)
Paul-André Melliés, CNRS and Université Paris-Cité (Examiner)
Marni Mishna, Simon Fraser University (Examiner)
Gilles Schaeffer, CNRS and École Polytechnique (Reviewer)
Noam Zeilberger, École Polytechnique (Advisor)

We examine and clarify in detail the contributions of Yoshisuke Matsunaga (1694?–1744) to the computation of Bell numbers in the eighteenth century (in the Edo period), providing modern perspectives to some unknown materials that are by far the earliest in the history of Bell numbers. Later clarification and developments by Yoriyuki Arima (1714–1783), and several new results such as the asymptotic distributions (notably the corresponding local limit theorems) of a few closely related sequences are also given. Joint work with Xiaoling Dou and Chong-Yi Li.

Directed Acyclic Graphs (DAGs) are directed graphs in which there is no path from a vertex to itself. DAGs are an omnipresent data structure in computer science and the problem of counting the DAGs of given number of vertices has been solved in the 70's by Robinson. For keeping the density of such graphs under control, one needs to take its number of edges into account too. But the adaptation of Robinson's enumeration to achieve this leads to counting formulas based on the inclusion-exclusion principle, inducing a high computational cost for the uniform random sampling based on this formula. I will present two contributions. First the enumeration of a new class of DAGs, enriched with an independent ordering of the children of each vertex, according to their numbers of vertices and edges. A constructive recursive counting formula is obtained (i.e. without using the inclusion-exclusion principle) thanks to a new decomposition scheme. Then I will show the applicability of the method by proposing a constructive enumeration of Robinson's labelled DAGs, by vertices and edges, based on the same approach. The consequence of having such a formula is that efficient uniform random samplers can be derived for both models.

In this talk, we generalize the classical Lazard’s elimination on the free Lie algebra L_k(X) to a more general scheme, namely quotients of Lazard’s eliminations. This implies (for Lie algebras defined by generators and relations) situations when the alphabet of generators can be partitioned in a way compatible with the relations. In this case, our scheme provides semidirect decompositions of these Lie algebras. As particular cases we consider the Partially Commutative Lie algebras and Drinfeld-Kohno Lie algebras for which our result provides decompositions of the Lie algebras (of these two series) into direct sums of free Lie algebras. As a result, we indicate how to construct combinatorial bases (of these Lie algebras) and their dual bases. Incidentally, we recover answers to Pr. Schützenberger’s questions about the Partially Commutative Free Lie algebra.

De nombreuses structures combinatoires admettent, au sens large, une notion d’irréductibilité : les graphes peuvent être connexes, les permutations indécomposables, les polynômes irréductibles, etc. Dans cette thèse, nous nous intéressons à la probabilité qu'un tel objet pris au hasard soit irréductible, lorsque sa taille tend vers l'infini. On obtient des développements asymptotiques complets pour ces probabilités ; l'irréductibilité est comprise à travers les constructions combinatoires SET, SEQ et CYC dans le contexte de la méthode symbolique. Nous appliquons notre approche aux graphes connexes, aux tournois irréductibles, aux permutations indécomposables et aux couplages parfaits. En outre, nous établissons des asymptotiques pour plusieurs modèles de surfaces connexes comprenant les surfaces à petits carreaux, les cartes combinatoires et certains objets de dimension supérieure tels que les constellations et les modèles de tenseurs colorés. Nous montrons que les coefficients apparaissant dans ces asymptotiques sont entiers et qu'ils peuvent être interprétés comme des suites de comptage d'autres classes combinatoires « secondaires ». Par exemple, les graphes connexes conduisent aux tournois irréductibles, les surfaces à petits carreaux aux permutations indécomposables, les cartes combinatoires aux couplages parfaits indécomposables. De plus, nous obtenons certaines probabilités asymptotiques qu'un objet combinatoire aléatoire ait un nombre donné de composantes irréductibles. Passant de la méthode symbolique à la théorie des espèces, nous traitons également le modèle G(n,p) de Erdös–Rényi. Nous établissons également la probabilité qu'un graphe orienté aléatoire soit fortement connexe en utilisant une décomposition plus complexe qui implique des graphes acycliques orientés.

Ammann bars are formed by segments (decorations) on the tiles of a tiling such that forming straight lines with them while tiling forces non-periodicity. Only a few cases are known, starting with Robert Ammann's observations on Penrose tiles, but there is no general explanation or construction. We propose a general method for cut and project tilings based on the notion of subperiods and we illustrate it with an aperiodic set of 36 decorated prototiles related to what we called Cyrenaic tilings.

Jacobi's bound is a sharp bound on the order of quasi-regular solutions of a differential system, always conjectural in the general case. It is expressed as the tropical determinant of the order matrix of the system. This result appears in posthumous manuscripts of Jacobi, which seem to come from a large abandoned project, Phoronomia. These texts reduce complexity problems related to the computation of normal forms to combinatorial problems, solved by original methods that make Jacobi a precursor of graph theory and shortest path problems.
Knowing the matrix $(a_{i,j})$ which expresses the productivity of worker $i$ assigned to task $j$, the tropical determinant $\sum_{\sigma\in S_{n}}\sum_{i=1}^{n}a_{i,\sigma(i)}$ is the maximum total productivity. Since the polynomial time method given by Jacobi was forgotten, it took ten years to discover an equivalent solution: the Hungarian method of Kuhn (1955), which uses earlier results of Kőnig and Egerváry. We will show the connection between Jacobi's algorithm, based on the notion of canon, and Kuhn's method, based on minimal covers. Hopcroft and Karp's algorithm for the marriage problem will also be described in the context of canons.
It will be shown how shortest path problems related to the canon computation allow to bound the orders of derivation needed to go from one normal form to another, as well as generalizations to underdetermined systems. This allows to easily characterize a subclass of flat systems, systems whose control is particularly easy. Among these is a simplified model of an aircraft.

La conjecture de Kepler stipule que la façon d'empiler les oranges qui minimise l'espace entre les oranges est bien celle utilisée sur les marchés. On se propose ici de mentionner quelques jalons importants vers la preuve de cette conjecture, et de décrire les principales idées de la preuve finalement apportée par Hales & Ferguson en 1998. Si le temps le permet, on parlera de quelques problèmes voisins toujours ouvertes (plusieurs disques ou sphères notamment).

Let $P$ be a set of $2n$ points in convex position, such that n points are colored red and n points are colored blue. A non-crossing alternating path on $P$ of length $L$ is a sequence $p_1, ..., p_L$ of $L$ points from $P$ so that (i) all points are pairwise distinct; (ii) any two consecutive points $p_i, p_{i+1}$ have different colors; and (iii) any two segments $p_i p_{i+1}$ and $p_j p_{j+1}$ have disjoint relative interiors, for $i \neq j$. We show that there is an absolute constant $\epsilon > 0$, independent of $n$ and of the coloring, such that $P$ always admits a non-crossing alternating path of length at least $(1 + \epsilon)n$. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least $(1 + \epsilon)n$ points of $P$. This is a properly colored matching whose segments are pairwise disjoint and intersected by a common line. For both versions, this is the first improvement of the easily obtained lower bound of $n$ by an additive term linear in $n$. The best known published upper bounds are asymptotically of order $4n/3 + o(n)$. Based on joint work with Pavel Valtr.

Maps come with different shapes, such as trees or triangulations with many more edges. Many classes of maps have been enumerated (2-connected maps, trees, quadrangulations...), notably by Tutte, and a phenomenon of universality has been demonstrated: for the majority of them, the number of elements of size $n$ in the class has an asymptotic of the form $\kappa\, \rho^{-n} \, n^{-5/2}$, for a certain $\kappa$ and a certain $\rho$. Nevertheless, there are classes of ``degenerate'' maps whose behaviour is similar to that of trees, and whose number of elements of size $n$ has an asymptotic of the form $\kappa\, \rho^{-n} \, n^{-3/2}$, as for example outerplanar maps. This dichotomy of behaviour is not only observed for enumeration, but also for metrics. Indeed, in the ``tree'' case, the distance between two random vertices is in $\sqrt{n}$, against $n^{1/4}$ for uniform planar maps of size $n$. This work focuses on what happens between these two very different regimes. We highlight a model depending on a parameter $u \in \mathbb{R}^*_+$ which exhibits the expected behaviours, and a transition between the two: depending on the position of $u$ with respect to $u_C$, the behaviour is that of one or the other universality class. More precisely, we observe a ``subcritical'' regime where the scale limit of the maps is the Brownian map, a ``supercritical'' regime where it is the Brownian tree and finally a critical regime where it is the $3/2$ stable tree.

In this talk, using the algebraic combinatorics on noncommutative formal power series with holomorphic coefficients and a Picard-Vessiot theory of noncommutative differential equations, we give a recursive construction of solutions of the Knizhnik-Zamolodchikov equations satisfying asymptotic conditions.

On s’intéresse à l’arbre couvrant de poids minimum d’un graphe complet dont les arêtes sont pondérées par des uniformes indépendantes. On sait que cet objet a une limite d’échelle en tant qu’espace métrique. Je montrerai en quoi des représentations discrètes exactes basées sur l’utilisation conjointe des algorithmes de Prim et de Kruskal permettent d’ouvrir la voie vers une construction explicite de la limite. Travail en collaboration avec J.-F. Marckert.

In 2015, Haglund Remmel and Wilson proposed two conjectural combinatorial interpretations of a certain symmetric function involving a certain Delta operator, which acts diagonally on the MacDonald polynomials. These formulas generalise the shuffle conjecture (Haglund, Haimal, Loehr, Remmel, Ulyanov 2002), now theorem (Carlsson, Mellit 2018). In this talk, we will first discuss some of the motivation and history of these famous problems. Then, we will talk about our new symmetric function operator Theta and their role in the proof of one of the Delta conjectures and the formulation of a possible unified Delta conjecture. (Based on joint works with Michele D'Adderio, Alessandro Iraci, Yvan Le Borgne, Marino Romero)

Pour un entier $b\ge 2$ fixé, on s'intéresse à la variation de la fonction somme-des-chiffres (en base $b$), notée $s$. Plus précisément, pour un entier $r\in\mathbb{N}$, on considère la fonction, définie sur $\mathbb{N}$, $\Delta^{(r)}(n):=s(n+r)-s(n)$ et aux propriétés asymptotiques de celle-ci. Ces propriétés sont bien définies sur le groupe des entiers $b$-adiques. On se proposera de construire un espace de probabilités à partir de ce groupe et du système dynamique de l'odomètre. Ce sera l'occasion d'y introduire la notion de Tours de Rokhlin. Sur cet espace de probabilités, on considérera $\Delta^{(r)}$ en tant que variable aléatoire. On énoncera alors quelques propriétés vérifiées par $\Delta^{(r)}$. En particulier, on donnera un énoncé de type TCL avec vitesse de convergence généralisant un résultat de Emme et Hubert. (Article en commun avec Thierry de la Rue et Elise Janvresse)

Titre : Déterminant : combinatoire, complexité et variantes.
Intention : L'accent sera mis sur les caractérisations combinatoires du déterminant et leur utilisation pour obtenir de bonnes bornes de complexité ; tout le matériel sera réutilisé dans les séances suivantes.

Un sommet du réseau ${\mathbb Z}^d$ est dit visible depuis l'origine si le segment de droite joignant l'origine à ce sommet intersecte le réseau en exactement deux points (l'origine et le sommet lui-même).
Cette notion a un contenu arithmétique : $(x_1,\dots,x_d)$ est visible depuis l'origine si et seulement si ${\rm PGCD}(x_1,\dots,x_d) = 1$.
Colorions les sommets visibles depuis l'origine en blanc et les autres en noir. À quoi ressemble ce coloriage vu depuis un point choisi « uniformément au hasard dans ${\mathbb Z}^d$ »? Nous verrons qu'il est possible de donner un sens rigoureux à cette question et d'y apporter une réponse satisfaisante.
Le coloriage aléatoire émergeant de cette étude peut être étudié du point de vue de la percolation. Nous verrons que, pour tout $d \geq 2$, presque sûrement, le nombre de composantes connexes blanches infinies vaut $1$ tandis que le nombre de composantes connexes noires infinies vaut $0$.
On présentera une démonstration de ce résultat obtenue en collaboration avec Samuel Le Fourn et Mike Liu.

le 15 février, nous aurons la visite d'Ali Charara, directeur de l'Institut des Sciences de l'Information et de leurs interaction (INS2I) du CNRS. Ce sera l'occasion de lui présenter le LIPN et un échantillon des recherches qui y sont menées (cf programme ci-dessous) Cette visite se clôturera par un déjeuner auquel tous les membres du LIPN sont conviés.

Les exposés se dérouleront en amphi B et le déjeuner en salle M100.

8h30-9h : Accueil - café
9h : Ouverture par Christophe Fouqueré, président de l'Université
9h05 : Introdution par Ali Charara, directeur de l’INS2I
9h10-9h25 : Présentation du laboratoire par Frédérique Bassino, directrice du LIPN
9h25-11h30 : Présentation des 5 équipes (25 minutes par équipe)

• LoVe Damiano Mazza "Complexités"
  Laure Petrucci "algorithmes et outils de model-checking"
• RCLN Nathalie Pernelle "Découverte d’expressions référentielles dans les graphes de connaissance"
  Nadi Tomeh "Traitement automatique de l’arabe et ses dialectes"
• A3 Aomar Osmani "Méta-apprentissage"
  Basarab Matei "Apprentissage à partir de Données et d' Apprenants : vers de nouveaux formalismes"
• AOC Roberto Wolfler Calvo "Maximisation de l'influence"
  Roland Grappe "Box-Totally Dual Integral Polyhedra"
• CALIN Lionel Pournin "Triangulations, flips et convexité forte
  Thomas Fernique "Des Empilements de Disques aux Nanoparticules"

• Posters
  Mustapha Lebbah (A3) "La start-up HephIA"
  Jaime Arias "La plateforme CosyVerif"
  Jorge Garcia Flores "La plateforme CheneTAL"

  
  11h45-12h30 : Echanges entre la direction de l’INS2I et les membres du LIPN
  12h30-14h00 : Déjeuner (en salle M100)

We give a summary of recent progress on the algebraic area enumeration of closedpaths on planar lattices. Several connections are made with quantum mechanics andstatistical mechanics. Explicit combinatorial formulae are proposed which rely onsums labelled by the multicompositions of the length of the paths.

An approximation algorithm for a Constraint Satisfaction Problem is called robust if it outputs an assignment satisfying a $(1 - f(\epsilon))$-fraction of the constraints on any $(1-\epsilon)$-satisfiable instance, where the loss function $f$ is such that $f(\epsilon) \rightarrow 0$ as $\epsilon \rightarrow 0$. Moreover, the runtime of the algorithm should not depend in any way on $\epsilon$. We present such an algorithm for the Unique Games Problem on complete graphs with $q$ labels. Specifically, the loss function is $f(\epsilon) = (\epsilon + c_\epsilon \epsilon^2)$, where $c_\epsilon$ is a constant depending on $\epsilon$ such that $\lim_{\epsilon \rightarrow 0} c_\epsilon = 16$. The runtime of our algorithm is $O(qn^3)$ (with no dependence on $\epsilon$) and can run in time $O(qn^2)$ using a randomized implementation with a slightly larger constant $c_\epsilon$. Our algorithm is combinatorial and uses voting to find an assignment. We prove NP-hardness (using a randomized reduction) for Unique Games on complete graphs even in the case where the constraints form a cyclic permutation, which is also known as Min-Linear-Equations-mod-q on complete graphs. This is joint work with Antoine Meot, Moritz Muehlenthaler and Arnaud de Mesmay.

Rowmotion is a group action on partially ordered sets which has received much attention of late in the dynamical algebraic combinatorics community. In particular, various statistics on posets turn out to be homomesic with respect to row motion, that is, the statistic has the same average over any orbit. A fence is a poset obtained from a sequence of chains by identifying maximal and minimal elements in an alternating fashion. These posets are important in the theory of cluster algebras and $q$-analogues.
We investigate rowmotion on antichains and ideals of fences. In particular, we show that orbits of antichains can be visualized using tilings. This permits us to prove various homomesy results for the number of elements of an antichain or ideal in an orbit. Rowmotion on fences also exhibits a new phenomenon, which we call homometry, where the value of a statistic is constant on orbits of the same size.
Along the way, we prove a homomesy result for all self-dual posets and show that any two Coxeter elements in certain toggle groups behave similarly with respect to homomesies which are linear combinations of ideal indicator functions. We end with some conjectures and avenues for future research. This is joint work with Sergi Elizalde, Matthew Plante, and Tom Roby. No background in dynamical algebraic combinatorics will be assumed.

In this talk, we present a solution of KZ(3) in K3^Id and then asymptotic solutions of KZ(4). We also review some important problems of iterated integrals and Chen series over a simply connected manifold. This paves the way for finding all solutions of KZ(n), for n>2. PS: Voici un lien expliquant certains aspects des équations KZ : https://en.wikipedia.org/wiki/Knizhnik-Zamolodchikov_equations

A point from the grid ${\mathbb Z}^d$ is called primitive when its coordinates are relatively prime. In this talk we will examine the question of how many primitive points one can pick, whose first non-zero coordinate is positive, under the constraint that the largest coordinate of their sum is at most a fixed number $k$. We will solve the question exactly for all $k$ and $d$. A number of connections with number theory, geometric combinatorics, and the theory of linear programming will be made explicit along the way.

The average-case analysis of algorithm is often an object of controversy. Some would say that it is not a relevant information of the algorithm’s "true" efficiency as it is often based on the uniform distribution over the inputs, which is not a good modelization of real-world contexts. Others would reply that the same can be said about worst-case analysis and that, in this regard, average case analysis is a non negligible additional information when one has to choose between two algorithms to solve a problem. In this presentation, we adopt the following point of view: the average case analysis of an algorithm is relevant to predict the algorithm behavior in a real-world context if and only if there exists a property (either on the distribution or the object), determining for the algorithm efficiency, whose average value is approximately the same given the random distribution under which the algorithm is studied and in the real-world context. In this study, the "determining property" we consider is the Shannon entropy of probability distributions. We exhibit several random generators of "probability distributions with fixed entropy" and perform an experimental and theoretical analysis of string matching algorithms. We obtain a continuous function, which takes a Shannon entropy as an input and returns the average complexity of the naive string matching algorithm. Joint work with Olivier Bodini and Izabell Iskandar.

An elimination tree for a connected graph $G$ is a rooted tree on the vertices of $G$ obtained by choosing a root x and recursing on the connected components of G−x to produce the subtrees of x. Elimination trees appear in many guises in computer science and discrete mathematics, and they encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent Hartung-Hoang-Mütze-Williams combinatorial generation framework to elimination trees, and prove that all elimination trees for a chordal graph $G$ can be generated by tree rotations using a simple greedy algorithm. This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs. Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations. As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations. This is a joint work with Arturo Merino (TU Berlin) and Torsten Mütze (U. Warwick), to be presented at SODA'22.

Catalytic equations appear in several combinatorial applications, most notably in the numeration of lattice path and in the enumeration of planar maps. The main purpose of this paper is to show that the asymptotic estimate for the coefficients of the solutions of (so-called) positive catalytic equations has a universal asymptotic behavior. In particular, this provides a rationale why the number of maps of size n in various planar map classes grows asymptotically like $c.n^{−5/2}\gamma^n$, for suitable positive constants $c$ and $\gamma$. Essentially we have to distinguish between linear catalytic equations (where the subexponential growth is $n^{−3/2}$) and non-linear catalytic equations (where we have $n^{−5/2}$ as in planar maps). Furthermore we provide a quite general central limit theorem for parameters that can be encoded by catalytic functional equations, even when they are not positive. Joint work with Marc Noy and Guan-Ru Yu.

The study of maps (graphs embedded into surfaces) is a rich subject at the crossroads of mathematics, computer science and theoretical physics. In this talk I will review the slice decomposition of planar maps : it started as a reformulation of some (by now) classical bijections between planar maps and trees, but then evolved into a general framework applicable to many families of maps and to their scaling limits. For simplicity I will restrict to the easiest setting of bipartite maps with controlled face degrees. I will explain how slice decomposition allows to enumerate pointed rooted maps, then "cylinders" and "pairs of pants" (planar maps with two and three boundaries, respectively). The talk is based on joint works with Emmanuel Guitter and Grégory Miermont.

We will first introduce translation surfaces, which are Riemann surfaces built from gluing polygons in the plane via translations. The torus is the most basic example of a translation surface. The closed geodesics we count are called saddle connections, and are found by following geodesics which start and end at a marked point. In the case of the torus, the saddle connections correspond to pairs of integers (a,b) which are coprime to each other. We will present probabilistic results counting saddle connections with length conditions, as well as counting pairs of saddle connections with various pairing conditions. We will finish with highlighting the open questions and difficulties of counting triples of closed geodesics.

We consider simply generated random plane trees with $n$ vertices and $k_n$ leaves, sampled from a sequence of weights. Motivated by questions on random planar maps, we will focus on the asymptotic behaviour of the largest degree. Precisely we will give conditions on both the number of leaves and the weight sequence that ensure the convergence in distribution of the associated Łukasiewicz path (or depth-first walk) to the Brownian excursion. This should also provide a first step towards the convergence of the height or contour function of the trees. The proof scheme is to reduce step by step to simpler and simpler objects and we will discuss excursion and bridge paths, non decreasing paths conditioned by their tip, and finally estimates of the form of the local limit theorem which may be of independent interest. Based on a joint work with Igor Kortchemski.

The study of random combinatorial structures and their limits is a growing field at the interface of combinatorics, probability theory, and mathematical physics. Planar graphs are a prominent example of such structures, yet important problems concerning their asymptotic shape remain open. This talk highlights open conjectures and reviews recent results, in particular the discovery of a Uniform Infinite Planar Graph (UIPG) as their quenched local limit.

It is well known that a line can intersect at most $2n-1$ cells of the $n \times n$ chessboard. What happens in higher dimensions: how many cells of the $d$-dimensional $[0,n]^d$ box can a hyperplane intersect? We determine this number asymptotically. We also prove the integer analogue of the following fact. If $K,L$ are convex bodies in $R^d$ and $K \subset L$, then the surface area $K$ is smaller than that of $L$. Joint work with Peter Frankl.

Semi-direct products can be seen as solutions of universal problems (see Andreas Thom's answer in MO96078 [1]) by means of ``structures acting on structures''. On the other hand Lazard's elimination theorems (Lie groups, Lie algebras and monoids) can be thought as byproducts of ``alphabets acting on codes''.
In this talk, we will illustrate (and prove some lemmas) about the tight link between these two concepts.

[1] MO96078: Are semidirect products categorical-colimits ?
https://mathoverflow.net/questions/96078

Considérons $n$ copies d'un tenseur complexe $T$ (de rang quelconque) et $n$ copies de son complexe conjugué ${\bar T}$, et procédons à la contraction des tenseurs avec une métrique triviale (symbole de Kronecker) en ne permettant que des contractions entre les $T$ et les ${\bar T}$. On obtient ainsi un invariant unitaire que l'on appelle invariant tensoriel. Les invariants tensoriels sont ainsi faits de contractions de tenseurs et sont au cœur de théories des champs (en physique) dont ils représentent les observables. Une question naturelle est: de combien de façon non équivalentes peut-on contracter ces $2n$ tenseurs complexes ? Une réponse à cette question a été fournie dans [AIHPD (2014) 1, 77-138], comme étant un dénombrement d'orbites d'actions de groupes symétriques. Je présenterai l'analyse asymptotique à grand $n$ d'une telle énumération pour des invariants tensoriels complexes de rang 3. La série asymptotique fait apparaître les nombres de Stirling de seconde espèce. La généralisation à tout rang est conjecturée.

Lattice walks taking steps from a fixed step set, and staying within some region of the lattice (most prominently, a quarter plane) have occupied combinatorialists for the past few decades and produced a huge range of rich results, drawing on algebra, probability theory, differential equations, and computational methods. I will discuss a new twist on this idea -- walks on the edges of the square lattice which obey two-step rules. These allow (or forbid) steps in a given direction to be followed by steps in another direction. We classify these rules according to a number of criteria, and show how these properties affect their generating functions, asymptotic enumerations and limiting shapes, on the full lattice as well as the upper half plane. The situation in the quarter plane is still very unclear, but I'll discuss some preliminary computational results.

Bonjour à toutes et tous, J'ai le plaisir de vous inviter à ma soutenance de thèse intitulée "Plans discrets substitutifs" qui se déroulera le 7 juillet à 14h en hybride.

La soutenance sera publique et se déroulera dans la salle de séminaire du LIPN à Villetaneuse, mais le nombre de participants est limité par la situation sanitaire et si vous souhaitez venir physiquement merci de me contacter par retour de mail. Vous pourrez aussi assister à ma soutenance à distance sur https://bbb.lipn.univ-paris13.fr/b/lut-uwi-axf-cq1 . En cas de problème avec le serveur bbb nous basculerons sur https://rdv2.rendez-vous.renater.fr/soutenance-these-lutfalla-8zchf (nous n'utiliserons ce lien de visio que en cas de problème avec le serveur principal).

Je soutiendrai mes travaux devant le jury composé de :
ARNOUX Pierre, Université Aix-Marseille (rapporteur)
BODINI Olivier, Université Paris XIII (examinateur)
FERNIQUE Thomas, Université Paris XIII (directeur de thèse)
KARI Jarkko, Université de Turku (examinateur)
MASÁKOVÁ Zuzana, Université Technique Tchèque (examinatrice)
POURNIN Lionel, Université Paris XIII (examinateur)
THUSWALDNER Jörg, Université de Leoben (rapporteur)

*Résumé:* Un pavage est un recouvrement du plan par des tuiles qui ne se chevauchent pas. Nous nous intéressons principalement aux pavages dont les tuiles sont des losanges unitaires et qui sont exacts c’est à dire que si on prend deux tuiles dans le pavages soit elles ne se touchent pas, soit elles on un unique sommet en commun, soit elles ont une arête entière en commun. Les substitutions sont des applications qui à chaque tuile associent un ensemble de tuiles appelé motif (dont la forme est habituellement la même que celle de la tuile initiale mais en plus grand), une substitution peut être étendue aux pavages en l’appliquant à chaque tuile séparément et en recollant les motifs obtenus. Les substitution permettent de construire des pavages avec une forte structure hiérarchique. Les plans discrets sont des pavages exacts par losanges unitaires avec un nombre fini de directions d’arêtes n que l’on peut relever dans R^n et qui lorsqu’on les relève approximent un plan. On dit aussi pavages planaires pour plans discrets. Notons que les plans discrets sont une version relâchée des pavages coupe-et-projections. Dans cette thèse nous étudions principalement les pavages substitutifs par losange relevés dans R^n . Nous prouvons que les pavages Sub Rosa ne sont pas des plans discrets, les pavages Sub Rosa sont des pavages substitutifs par losange avec symétrie rotationnelle d’ordre n qui ont été définis par Jarkko Kari et Markus Rissanen et qui étaient de bons candidats pour être des plans discrets. Nous définissons une nouvelle famille de pavages que l’on appelle les pavages Planar Rosa qui sont des plans discrets substitutifs avec symétrie rotationnelle d’ordre n. Nous étudions aussi la méthode de la multigrille qui permet de construire des pavages coupe-et-projection. On utilise cette méthode pour donner une construction explicite pour des pavages coupe-et-projection par losanges avec symétrie rotationnelle globale d’ordre n

*Abstract:* A tiling is a covering of the plane by tiles which do not overlap. We are mostly interested in edge-to-edge rhombus tilings, this means that the tiles are unit rhombuses and any two tiles either do not intersect at all, intersect on a single common vertex or along a full common edge. Substitutions are applications that to each tile associate a patch of tiles (which usually has the same shape as the original tile but bigger), a substitution can be extended to tilings by applying it to each tile and gluing the obtained patches together. Substitutions are a way to grow and define tilings with a strong hierarchical structure. Discrete planes are edge-to-edge rhombus tilings with finitely many finitely many edge directions be lifted in R n and which approximate a plane in R^n , such a tiling is also called planar. Note that discrete planes are a relaxed version of cut-and-project tilings. In this thesis we mostly study edge-to-edge substitution rhombus tilings lifted in R^n . We prove that the Sub Rosa tilings are not discrete planes, the Sub Rosa tilings are edge-to-edge substitution rhombus tilings with n-fold rotational symmetry that were defined by Jarkko Kari and Markus Rissanen and which were good candidates for being discrete planes. We define a new family of tilings which we call the Planar Rosa tilings which are subsitution discrete planes with n-fold rotational symmetry. We also study the multigrid method which is a construction for cut-and-project tiling and we give an explicit construction for cut-and-project rhombus tilings with global n-fold rotational symmetry.

The maximum expected length of increasing subsequence chosen by a real-time player from a random iid sequence is $\sqrt{2n}$, as was found by Samuels and Steele in 1981. In this talk we survey refinements and generalisations of this benchmark, also in connection with some bin-packing models.We further present recent results on fluctuations of the length and shape of the sequence selected by the optimal or a near-optimal policy.

Nous introduisons une classe de problèmes appelés recherche de représentant. Étant donné un groupe G qui opère sur un ensemble X, l'entrée d'un problème sera un élément x de X et la sortie un représentant x* de l'orbite de l'orbite de x sous l'action de G. Nous spécifions un rapport bien particulier entre X et G, qui permet, en utilisant le formalisme introduit par Gurevich pour modéliser les algorithmes, de dire que tout algorithme réversible (dans le sens où toute donnée accessible au début d'une exécution est accessible jusqu'à la fin) résout en fait un tel problème. Nous montrons que les traces d'exécution d'un tel algorithme est un diagramme (i.e., graphes orientés et arc-colorés) couvrant du diagramme de Cayley du groupe des automorphismes d'une algèbre naturellement associée à l'algorithme. Notre approche permet de relier borne inférieure de complexité et diamètre d'un graphe de Cayley du groupe d'automorphisme, lorsque ce groupe est fini. Quand il est infini, mais à croissance polynomiale, notre approche fournit, sous une condition raisonnable, une borne inférieure exponentielle, pour la complexité algébrique (i.e. on compte le nombre d'opérations élémentaires). Si le temps le permet, nous parlerons également de la caractérisation du langage des traces d'exécution d'un algorithme.

Knots give rise (via complex Chern-Simons theory) to matrices of q-series, (formal power series with integer coefficients) with remarkable combinatorial, arithmetic and analytic properties, which define, in particular, holomorphic functions in the complex plane minus a ray. These are examples of 'holomorphic quantum modular forms'. We will explain the main ideas with examples of the two simplest hyperbolic knots. Joint work with Rinat Kashaev, Don Zagier, Jie Gu and Marcos Marino (in various collaborations).

En 2016, avec Veronica Guerrini, Simone Rinaldi et Gilles Schaeffer, (https://doi.org/10.1088/1751-8121/50/2/024002 et https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2017/43%20Duchi%20Guerrini%20Rinaldi%20Schaeffer.pdf), nous avons introduit un modèle de surfaces branchantes que nous avons appelées poissons combattants. Ces poissons ont de belles propriétés énumératives encore largement mystérieuses : ils partagent la formule des cartes planaires non séparables enracinées, mais une conjecture résiste, qui lie 4 paramètres de ces poissons à des paramètres des arbres ternaires gauches qui codent ces cartes. En considérant le codage des poissons par leur arbre squelette, nous sommes récemment arrivé naturellement à une variante de ce modèle, qui se trouve avoir la même formule que les cartes planaires enracinées...

We discuss the characterization of $(f_0, f_1)$-pairs of $d$-polytopes for $d=3, 4, 5$. We completely characterize the $(f_0, f_1)$-pairs of $6$-dimension polytopes and find a characterization of $7$-dimension polytopes having excess degree greater than 11. We finally conjecture bounds fulfilled by $d$-polytopes with excess greater than $3d-10$.

En ces temps difficiles, nous avons tous besoin de nous réconforter autour de jolies bijections pleines de couleurs. Cet exposé parle d'un travail coréalisé avec Andrew Elvey-Price (Tours) et Irène Marcovici (Nancy). Nous avons répondu ensemble à une question ouverte de Mortimer et Prellberg, sollicitant une bijection entre une famille de marches dans un domaine triangulaire borné (pensez à un grand triangle équilatéral subdivisé en plusieurs petits triangles équilatéraux) et les fameux chemins de Motzkin, mais avec une hauteur bornée. Les techniques que nous utilisons pour les preuves sont élémentaires et semblent robustes. En plus de résoudre la conjecture de Mortimer et Prellberg, notre approche nous a permis de trouver une nouvelle bijection inattendue entre des marches tridimensionnelles contraintes dans une pyramide et certaines marches bidimensionnelles sur une grille carrée.

Building upon the rule-algebraic stochastic mechanics framework, I will present a new approach to computing multi-variate generating function expressions in combinatorics. This approach is applicable for combinatorial structures which can be described as some initial configuration together with a generator (ideally uniform) whose repeated applications render the structures of increasing sizes. Unlike in species theory, computations in this approach are based upon the notion of rewriting rules, their sequential compositions and the so-called rule algebras (which encode information on the combinatorics of sequences of rewriting steps). I will introduce a computational strategy for determining multi-variate generating functions describing joint distributions of pattern counts in a species, namely via a form of ODE system obtained from the computation of certain commutators (of rules in the generator with rules implementing pattern counts). Some concrete results for the species of planar rooted binary trees will be presented for illustration. I will put a particular emphasis on an interesting open problem which concerns the existence of the aforementioned type of combinatorial evolution equations as seen in the planar rooted binary trees example. Reference: Nicolas Behr (2021). “On Stochastic Rewriting and Combinatorics via Rule-Algebraic Methods”. Invited Paper in Patrick Bahr (ed.): Proceedings 11th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2020), Online, 5th July 2020, Electronic Proceedings in Theoretical Computer Science 334, pp. 11–28. http://eptcs.web.cse.unsw.edu.au/paper.cgi?TERMGRAPH2020.2

I will start from reviewing Groebner bases and their connection to polynomial system solving. The problem of solving a polynomial system of equations over a finite field has relevant applications to cryptography and coding theory. For many of these applications, being able to estimate the complexity of computing a Groebner basis is crucial. With these applications in mind, I will review linear-algebra based algorithms, which are currently the most efficient algorithms available to compute Groebner bases. I will define and compare several invariants, that were introduced with the goal of providing an estimate on the complexity of computing a Groebner basis, including the solving degree, the degree of regularity, and the last fall degree. Concrete examples will complement the theoretical discussion.

The associative symmetric operad $As$ is the linear span of all permutations endowed with an operation allowing us to insert a permutation into another one. This structure is rich both under a combinatorial and an algebraic point of view. In this context, Aguiar and Livernet have constructed alternative bases of $As$ relating it with the combinatorics of the weak order on permutations. In this talk, I will present a family of analogous operads, defined on some families of words of integers. These operads are substructures of a master structure called interstice operad. We obtain in this way operads on objects in correspondence with permutations, increasing trees, Fuss-Catalan objects, or walks in rectangles. One of the peculiarities of some of these operads is that, despite to their relative simplicity, some are infinitely generated and have nonquadratic and nonhomogeneous nontrivial relations. Joint work with Camille Combe.

Le problème du postier chinois est un problème classique de l'optimisation combinatoire. Dans cet exposé, je me concentrerai sur le problème du postier chinois dans les triangulations planaires. Je montrerai une borne optimale sur la longueur du plus court parcours de postier, et je discuterai des liens à la chimie théorique.

On présentera le produit eñe, ses propriétés algébriques et analytiques, et son extension à des fonctions à singularités isolées. Ceci conduit naturellement à la découverte des formules intégrales de la monodromie pour les produits eñe exponentiels et les produit de Hadamard.
[Séminaire organisé par le GDR EFI]

Given a sequence S of n real numbers, there always exists a monotonic subsequence of S of size sqrt(n). In this talk I will present three applications of this beautiful fact : conflict-free coloring (cellular networks), contact-maps (biology) and independent sets (graphs).

Une suite k-automatique est une suite qui peut être calculée par un automate fini de la manière suivante : le n-ième terme de la suite est fonction de l'état atteint par l'automate après lecture de la représentation de l'entier $n$ en base $k$. Ces suites peuvent également être obtenues à partir du point fixe d'une substitution de longueur $k$. Je montrerai qu'il existe des familles de suites automatiques qui, malgré leur description très simple, ont les mêmes corrélations d'ordre 2 qu'une suite i.i.d. de symboles choisis uniformément au hasard. Plus précisément, pour tout entier $r>0$, et pour tout couple $(i,j)$ de symboles, la proportion asymptotique d'entiers $n$ pour lesquels $(u_n,u_{n+r})=(i,j)$ est égale à $1/L^2$, où $L$ est le nombre de symboles. La preuve repose sur des ingrédients simples et se généralise à des suites multi-dimensionnelles.
Il s'agit d'un travail en collaboration avec Thomas Stoll et Pierre-Adrien Tahay.

Les quadtrees ("point quadtrees") sont un analogue multidimensionnel des arbres binaires de recherche, où un ensemble de points dans un espace de dimension d>1 sont représentés de manière hiérarchique par un arbre qui permet la recherche et l'insertion d'un nouveau point en un temps contrôlé par la hauteur de l'arbre. L'analyse probabiliste des quadtrees, réalisée dans les années 90 notamment par des méthodes analytiques, suppose généralement que les points sont pris aléatoirement (et uniformément) dans un domaine rectangulaire. Or, à la différence des arbres binaires de recherche, il ne suffit pas de randomiser l'ordre d'insertion pour assurer que ce modèle est pertinent: la loi de l'arbre obtenu par insertion dans un ordre aléatoire de ces points dépend significativement du nuage de points considéré. Nous montrons que, si l'on analyse la longueur de cheminement des arbres comme représentative du coût de construction du quadtree, on peut identifier exactement les pires nuages de points. C'est vrai en un sens probabiliste assez fort: la loi du cheminement total pour le pire cas domine, pour l'ordre stochastique, la loi du cheminement pour tout autre nuage de points. En particulier, aucun nuage de points n'a une longueur de cheminement moyenne plus grande que le 2n log(n) des arbres binaires de recherche. (Travail en commun avec Sophie Juppet)

Séminaire organisé par le LIGM.

Nous revoyons ensemble les étapes essentielles établissant l'équation faisant le pont entre les structures algébriques des polyzêtas convergent, via leur séries génératrices non commutatives mises sous forme factorisée MRS.

We present some bialgebras and their monoid of characters. We entend the well-known theorem (when the scalars form a field) about linear independence of characters to the case of some rings. Examples of algebraic independence of subfamilies and identites derived from their groups (or monoids) of characters are provided. In this framework, we give a way to factorise characters (the MRS factorisation) as a resolution of unity as well as combinatorial counterparts of this resolution in terms of bases in duality.
Joint work with Darij Grinberg (Drexel University, Philadelphia, US / currently Germany) and Hoang Ngoc Minh (LIPN, Paris XIII University)

Nous revoyons ensemble les étapes essentielles établissant l'équation faisant le pont entre les structures algébriques des polyzêtas convergent, via leur séries génératrices non commutatives mises sous forme factorisée MRS.

We present some bialgebras and their monoid of characters. We entend the well-known theorem (when the scalars form a field) about linear independence of characters to the case of some rings. Examples of algebraic independence of subfamilies and identites derived from their groups (or monoids) of characters are provided. In this framework, we give a way to factorise characters (the MRS factorisation) as a resolution of unity as well as combinatorial counterparts of this resolution in terms of bases in duality.
Joint work with Darij Grinberg (Drexel University, Philadelphia, US / currently Germany) and Hoang Ngoc Minh (LIPN, Paris XIII University)

Nous revoyons ensemble les étapes essentielles établissant l'équation faisant le pont entre les structures algébriques des polyzêtas convergent, via leur séries génératrices non commutatives mises sous forme factorisée MRS.

We briefly review a number of random networks in recent areas of interest of the speaker, and discuss the issues that arise. We present the Apollonian network as a case study. We study the distribution of the degrees of vertices as they age in the evolutionary process. Asymptotically, the (suitably-scaled) degree of a node with a fixed label has a Mittag-Leffler-like limit distribution. The degrees of nodes of later ages have different asymptotic distributions, influenced by the time of their appearance. The very late arrivals have a degenerate distribution. The result is obtained via triangular Pólya urns. Also, via the Bagchi-Pal urn, we show that the number of terminal nodes asymptotically follows a Gaussian law. We prove that the total weight of the network asymptotically follows a Gaussian law, obtained via martingale methods. Similar results carry over to the sister structure of the k-trees.

[NB: For this talk, we have the pleasure to join the "Applied Mathematics Webinar", Jeddah - Riadh - Dammam - Tunis]

The class of completely monotone functions and Bernstein functions is important in the context of infinitely divisible probability measures of $(0,\infty)$. We shall provide for them several new characterizations via two approaches: the first one is driven algebraically via elementary preserving mappings and the second one is developed in terms of the behavior of their restriction on $N$. As a consequence, we give a complete answer to the following question: "Can we affirm that a function $f$ is completely monotone (resp. a Bernstein function) if we know that the sequence $(f (k))_k$ is completely monotone (resp. alternating)?". This approach constitutes a kind of converse to Hausdorff’s moment characterization theorem in the context of completely monotone sequences. With closely related tools, we solve an open problem raised by Harkness and Shantaram (1969) who obtained, under sufficient conditions, a limit theorem in law for sequences of nonnegative random variables build with the iterated stationary excess operator. We show that the conditions of Harkness and Shantaram are actually necessary; continuous time convergence is equivalent to discrete time convergence; and the only possible limits in distribution are mixture of exponential with log-normal distributions.

[NB: For this talk, we have the pleasure to join the "Applied Mathematics Webinar", Jeddah - Riadh - Dammam - Tunis]

Nous revoyons ensemble les étapes essentielles établissant l'équation faisant le pont entre les structures algébriques des polyzêtas convergent, via leur séries génératrices non commutatives mises sous forme factorisée MRS.

L'action de sous-groupes sur un produit de groupes symétriques permet d'énumérer différentes familles de graphes. En particulier, les graphes à ruban bi-partis à $n$ arêtes (et au plus $2n$ sommets) sont les orbites de l'action adjointe $( g s_1 g ^{-1} , g s_2 g ^{-1})$ dans $S_n \times S_n$, où $g, s_1$ et $s_2$ sont des éléments de $S_n$. Ces graphes forment une base d'une algèbre $K(n)$, qui est aussi un espace de Hilbert pour un certain produit sesquilinéaire. On y définit une famille finie d'opérateurs $T_i$, qui commutent entre eux (système intégrable) et qui sont hermitiens. Nous sommes donc en présence d'un modèle de mécanique quantique. Dans une base de représentation de Fourier, étiquetée par les diagrammes de Young, les $T_i$ admettent des valeurs propres qui ne sont rien d'autre que les caractères (normalisés) de cette représentation. On montre que les multiplicités des valeurs propres de ces opérateurs sont les coefficients de Kronecker, bien connus en théorie des représentations. Nous démontrons qu'il existe un algorithme (HNF) de construction de cette multiplicité qui s'interprète comme la dimension d'un sous-treillis du treillis des graphes à ruban : $\mathbb{Z}^{{\rm Rib}(n)}$, où ${\rm Rib}(n)$ est le nombre de graphes à ruban bi-partis à n arêtes. Ceci offre ainsi une réponse à la question de Murnaghan (Amer. J. Math, 1938) sur l'interprétation combinatoire du coefficient de Kronecker. Je finirai par une application au problème de décision de l'annulation du coefficient de Kronecker.

TBA

La théorie des produits infinis classiques s'inscrit naturellement dans celle des anneaux topologiques. Nous verrons en effet plusieurs exemples de convergences utilisés en combinatoire. Puis quelques produits classiques seront passés en revue

• Weierstrass
• Newton-Girard
• Produits unipotents
• Factorisation MRS

Public will choose!

La théorie des produits infinis classiques s'inscrit naturellement dans celle des anneaux topologiques. Nous verrons en effet plusieurs exemples de convergences utilisés en combinatoire. Puis quelques produits classiques seront passés en revue

• Weierstrass
• Newton-Girard
• Produits unipotents
• Factorisation MRS

There are a number of combinatorial structures that admit a notion of irreducibility in some sense, including connected graphs and surfaces, irreducible tournaments and indecomposable permutations. We are interested in the asymptotic behaviour of probability that a random labelled object is irreducible, as its size tends to infinity. It turns out that, under some conditions, it is possible to obtain this asymptotics with the help of the symbolic method. Namely, it is so when the considered combinatorial class can be described as a set or a sequence of the corresponding irreducible class, and when its counting sequence grows sufficiently fast. Moreover, the coefficients involved in the asymptotic expansion are often integers. We explain their combinatorial meaning. This is an ongoing joint work with Thierry Monteil.

Structural properties of large random λ-terms may be gleaned by studying the asymptotic distributions of various parameters of interest, such as the number of free variables, abstractions and applications, and so on. Such properties have been studied for general λ-terms under various considerations such as different notions of size and various structural restrictions. Linear λ-terms, that is, terms where each variable occurs exactly once, form an interesting subsystem of λ-calculus with various combinatorial connections to much-studied classes of objects such as trivalent maps. The purpose of this work is to help shed some light on what the “typical” terms of certain fragments of the linear λ calculus look like. The fragments we deal with in this work may be roughly partitioned into two major categories, the algebraic and the differentially-algebraic one, according to the nature of the specifications they admit.

En partant des travaux de O.Bodini sur les polyominos convexes, nous avons écrit la construction combinatoire des zonotopes, et ainsi pu, avec les outils de combinatoire analytique, obtenir le nombre asymptotique de zonotope dans un carré de côté n, puis dans un cube de côté n, ainsi que d'autres propriétés asymptotique tels le nombre de côté moyen, la forme limite. Cette méthode est généralisable à toute dimension, mais devient très fastidieuse en montant en dimension.

Quels sont les empilements à trois disques les plus denses ? Un empilement est dit triangulé si chacun de ses trous est borné par trois disques tangents. Ces empilements semblent les meilleurs candidats pour maximiser la densité. Il existe 164 paires $(r,s)$ tq $1>r>s$ permettant un empilement triangulé par des disques de rayons $1$, $r$ et $s$. On est en train de développer une méthode pour prouver que dans tous ces 164 cas la densité est maximisée par un empilement triangulé.

Une façon d'apréhender un système dynamique $T:X\to X$ est de partitionner $X$ en un nombre fini de parties $P_i$ et d'associer à chaque point $x\in X$ un mot infini qui décrit la suite des atomes de la partitions rencontrés le long de l'orbite de $x$ par $T$. Ce codage symbolique permet, lorsque la partition est convenable, de décrire les propriétés dynamiques de $T$ (mesures invariantes, entropie, mélange, ...) en termes combinatoires (fréquences, complexité, ...). La complexité du codage symbolique est la fonction qui associe à tout entier $n$, le nombre de mots de longueur $n$ qui appraissent dans les mots infinis obtenus. Cette notion raffine la notion d'entropie. Étant donnée une translation $T$ du tore $\mathbb{T}^d$, nous pouvons essayer de la coder de sorte à avoir une complexité la plus faible possible. Nous verrons comment construire des partitions (dont le bord est nécéssairement fractal) qui permettent d'obtenir une complexité linéaire. Ce travail a été fait dans le cadre du groupe de travail Pytheas Fogg.

Hexagonal close-packings are the most efficient way to pack unit disks in R^2. But what do we mean by the definite article "the" in the previous sentence? Are hexagonal close-packings the only optimal packings? If we measure optimality by density, the answer is, No. In fact, there are far too many density-optimal packings to classify in any meaningful way. This suggests that density is too coarse a notion to capture everything that we mean (or should mean!) by "efficient". To study efficiency, we study deficiency, and seek ways to quantify defects in a regular packing. An obstacle here is that common kinds of defects inhabit disparate scales (e.g., point defects are infinitesimal compared to line defects, which in turn are infinitesimal compared to the bulk). This suggests we turn to extensions of the real numbers that include infinitesimal elements (or rather, as turns out to be more helpful, infinite elements). We use a regularization trick to make sense of these ideas (starting in one dimension). This enables us to sharpen our notion of optimal packing so that the optimal disk-packings are provably the hexagonal close-packings and no others. A side-benefit is a natural but apparently new finitely additive, non-Archimedean measure in Euclidean n-space; it agrees with n-dimensional volume when applied to finite regions, but some infinite regions are "more infinite" than others. For slides related to an earlier version of this talk, see http://jamespropp.org/brown18a.pdf

Le but de cet exposé est de motiver, de construire, et d'étudier un modèle permettant d'analyser l'impact de la démographie et de l'extinction sur la composition génétique d'une population. On considèrera une population d'individus diploïdes (c'est-à-dire qui possèdent deux versions de chaque gène) caractérisés par leur génome à un locus multi-allélique (le vocabulaire biologique sera réintroduit en début d'exposé). Cette population sera modélisée par un processus de diffusion stochastique obtenu comme limite d'échelle d'un processus de naissance et mort non-linéaire, et qui peut être vu comme un processus de Wright-Fisher avec taille de population variable. Ce processus limite permet d'étudier simultanément la composition génétique et la taille de la population et notamment d'étudier la composition génétique de la population lors de l'extinction, dont le comportement sera relié à l'intégrabilité des trajectoires de l'inverse de la taille de population. Certains comportements du modèle seront aussi comparés à ceux d'un modèle de Wright-Fisher classique.

We consider the Robinson-Schensted-Knuth algorithm applied to a random input and investigate the shape of the bumping route (in the vicinity of the y-axis) when a specified number is inserted into a large Plancherel-distributed tableau. We show that after a projective change of the coordinate system the bumping route converges in distribution to the Poisson process. (Joint work of Łukasz Maślanka, Mikołaj Marciniak, Piotr Śniady).
Handout for those who do not know RSK algorithm: http://psniady.impan.pl/data/uploads/suprising-2020/handout.pdf

Pour étudier le système de Keller-Segel dans sa forme parabolique, on propose un système de particules stochastique avec une interaction inhabituelle : chaque particule interagit avec le passé de toutes les autres par l’intermédiaire d'un noyau espace-temps fortement singulier. On montrera l'existence et la propagation de chaos pour ce système dans le cas unidimensionnel. On discutera les résultats numériques dans le cas bi-dimensionnel et pourquoi les techniques de preuves développées en d=1 ne s’appliquent pas ici. Nous énoncerons aussi un résultat d’existence et unicité pour l’EDS non-linéaire au sens de McKean sous des conditions explicites sur les paramètres du modèle dans le cas bi-dimensionnel.

Say, you have a fixed set of tiles and want to count how many ways you can tile a rectangle of a fixed height, or a square. What kind of sequences can be obtained? This seeming innocent question is related to a number of beautiful problems in enumerative and asymptotic combinatorics. I will give a broad overview of the subject and discuss the types of integer sequences that arise along the way. I will also mention a few curious conjectures.

Il est bien connu que les traces de deux marches aléatoires simples indépendantes sur ${\mathbb Z}^d$ ont p.s. un nombre fini de points d’intersection si, et seulement si, $d > 4$. Dans cet exposé nous nous intéresserons à la queue de distribution de ce nombre de points d’intersection en dimension 5 et plus. Je donnerai des éléments de preuve d’un résultat récent qui donne un principe de grandes déviations, et qui clôt - dans le cas discret - une question de van den Berg, Bolthausen et den Hollander datant de 2004.

West's stack-sorting map is a specific function that sends permutations to permutations. I will discuss a certain Decomposition Lemma that has led to several advances in the understanding of this function, including a polynomial-time algorithm for counting 3-stack-sortable permutations. We can generalize the Decomposition Lemma by considering special sets of binary plane trees called troupes. I will also mention recent progress concerning the average number of iterations of the stack-sorting map needed to sort a permutation.

We investigate the connection between properties of formal languages and properties of their generating series, with a focus on the class of holonomic power series. It is a classical result that regular languages have rational generating series and that the generating series of unambiguous context-free languages are algebraic. This connection between automata theory and analytic combinatorics has been successfully exploited. For instance, Flajolet used it in the eighties to prove the inherent ambiguity of some context-free languages using criteria from complex analysis. Settling a conjecture of Castiglione and Massazza, we establish an interesting link between unambiguous Parikh automata and holonomic power series, which also yields characterizations of inherent ambiguity and algorithmic byproducts for these automata models. This is a joint work with Alin Bostan, Arnaud Carayol and Cyril Nicaud.

In the first part of the talk, I will discuss some applications of graph theory to the study of fullerene molecules. In the second part, I will discuss how quadrangulations are related to Kneser graphs, and how they helped disprove two widely-believed conjectures in commutative algebra.

Random sampling techniques have proven invaluable in constructing succinct approximations of large data sets, in particular those with geometric attributes in Euclidean spaces. The study of such approximations involve several aspects: a better understanding of the discrete and combinatorial structure of data in high dimensions, efficient algorithms for constructing succinct approximations, the role and limits of random sampling, and applications of such approximations in algorithms and combinatorics.

I will discuss a fairly new method for solving certain systems of functional equations arising in combinatorics. I will start by describing the work of Bernardi, Bousquet-Mélou and Raschel on enumerating walks with small steps in the quarter plane, then I will describe how I have applied this method more generally, in particular to counting certain walks by winding angle. In each case the solutions involve Jacobi theta functions.

How many patterns (subsequences up to order isomorphism) of size k can a permutation with size n contain? What are the optimal permutations? The goal of this work is to answer this question experimentally, for n up to 17, by exhaustively searching all permutations on GPUs. I will detail the algorithms used, then do a quick introduction to GPU programming and explain a few salient points of their implementation. Work in common with Michael Engen (University of Florida).

Euler's reflection identity between inverse Gamma functions (with center zero) suggest that there are symmetrisation procedures that amount to the lacunarization of the exponents in exponentials. We start from, precisely, the lacunarization of the exponent in the Eulerian identity $$ \dfrac1{\Gamma(1+z)} =\exp\biggl(\gamma z-\sum_{n\ge2}\zeta(n)(-z)^n/n\biggr) $$ and obtain, of course, a family of new entire function (with real coefficients).
What is surprising, is that these "new" entire functions are the images of algebraically independent characters of the stuffle algebra. Algebraic independence of the characters is obtained via general theorems like Radford's lemma on characters, "Kleene stars of the plane" phenomena and the Lie-theoretic setting of the BTT (basic triangle theorem).

The seminar is thought as interactive and a walk along a route through (Hopf) algebra(s), complex analysis, functional analysis and combinatorics on words.

This thesis gathers several works on the lattice polytopes of IR^d. In particular, it focuses on the combinatorics of the family of the d-dimensional lattice polytopes contained in the [0,k]^d hypercube, denoted (d,k)-polytopes. Due to their elusive combinatorics, a direct approach using the symbolic method is out of reach. Hence, we propose an original approach based on the description of a graph whose vertex set is the set of (d,k)-polytopes. In this graph, there is an edge between two polytopes if we can transform each of them into the other by an elementary move. These elementary moves are local operations performed on the polytopes. Proceeding this way, we prove that the graph we defined is connected and we obtain a uniform random sampler based on a Markov Chain for the (d,k)-polytopes of arbitrary dimension. We obtain also obtain two exhaustive enumeration algorithms. The first part of this thesis focuses on the description of the above mentionned elementary moves and the study of the graphs based upon them. The second part presents the random sampling and the exhaustive enumeration algorithms. Jury members: Anna Ben-Hamou, Olivier Bodini, Éric Colin de Verdière, Jean-François Marckert, Vincent Pilaud, Mario Valencia-Pabon.

La théorie des espaces de pavages a été profondément façonnée par le résultat historique de Berger : un jeu de tuiles fini peut ne paver le plan que de manière apériodique. Ces points apériodiques sont au coeur de nombreuses directions de recherche du domaine, en mathématiques comme en informatique. Dans cette exposé, nous répondons aux questions suivantes en dimension 2 : 1. Quelle est la complexité calculatoire de déterminer si un jeu de tuiles (espace de type fini) possède un point apériodique ? 2. Comment se comportent les espaces de pavages ne possédant aucun point apériodique ? Nous montrons qu'un espace de pavage 2D sans point apériodique a une structures très forte : il est "équivalent" (presque conjugué) à un espace de pavage 1D, et ce résultat s'applique aux espaces de type fini ou non. Nous en déduisons que le problème de posséder un point apériodique est co-récursivement-énumérable-complet, et que la plupart des propriétés et méthodes propres au cas 1D s'appliquent aux espaces 2D sans point apériodiques. La situation en dimension supérieure semble beaucoup moins claire. Cet exposé est issu d'une collaboration avec Anael Grandjean et Benjamin Hellouin de Menibus.

Plan

1. Introduction : un problème universel
   1. Exemples de structures libres comme solutions de problèmes universels
   2. L'algèbre $\frak{h} = K \langle X\rangle$ sur l'alphabet $X = \{0,1\}$, et ses deux sous-algèbres $\frak{h}^1$ et $\frak{h}^2$
2. Structure d'algèbres de shuffle et de stuffle, intégrales itérées des polylogs
3. Algèbres harmoniques, algèbre des séries formelles sur $X$ : $K\langle \! \langle X\rangle \! \rangle$ et algèbre des séries rationnelles.

We will discuss ribbon graphs and their topological polynomial invariant that generalizes the famous Tutte polynomial and that is called the Bollobas-Riordan (BR) polynomial. After giving the definition of ribbon graphs and discussing their correspondence with signed rotation systems, we will inspect the main topological properties of ribbon graphs seen as surfaces with boundaries. We will then introduce the BR topological polynomial invariant that satisfies a contraction-deletion recursion relation in a similar way of the Tutte polynomial. If the time allows it, we may give a glimpse of the proof of the universality theorem for the BR polynomial.

After having recalled and proved the set of "marvelous identities" evoked last week through an Umbral coding of "the plane", we construct, after Minh's work, a regularized character of the stuffle algebra which transports, point-by-point the Hausdorff group of the stuffle algebra. We provide as well the $q$-analogue and set some open questions.

In this expository talk we present a constructive approach to generate exact solutions of the one-dimensional Stieltjes moment problem, with moments expressible via factorials and/or gamma functions. We will mainly concentrate on continuous solutions. The main ingredient of this method is a systematic use of the inverse Mellin transform and of a generalization of hypergeometric function called the Meijer G function, fully implemented in computer algebra systems. The essential property inherent in these tools is the Mellin (i.e. multiplicative) convolution. It allows one to produce exact solutions for a large family of various moment sets, especially those being combinatorial sequences. We enumerate various, older and more recent, criteria for positivity as well as for the uniqueness of so obtained solutions. Our method permits one to bypass (in many cases) an involved question of verifications of these criteria. Amongst concrete examples reviewed here we mention the explicit construction of the so called Stieltjes classes of non-unique solutions via polynomial killers, the problem of non-unique Lévy stable distributions and the construction of moment filters. Finally, a possible application of this methodology to purely discrete distributions will be briefly exposed.

In this talk, we consider the normal ordering of operators of the type $$ \Omega=\sum_{\alpha+\beta=r}c_{\alpha,\beta}(a^+)^\alpha a(a^+)^\beta,\ \ \alpha,\beta,r\textrm{ integers} $$ where $a$ (resp. $a^{+}$) is a boson annihilation (resp. creation) operator; these satisfy $[a,a^{+}]\equiv a a^{+}-a^{+}a=1$, and for the purposes of this presentation may be thought of as $a\equiv d/dx$ and $a^{+}\equiv x$. We discuss the integration of the one-parameter groups $e^{\lambda\Omega}$ and their combinatorial by-products. In particular we show how these groups can be realized as groups of substitutions with prefactor functions. To end with, we provide a recent application of the concept one-parameter groups to arithmetics.

Pour disposer des pièces d'un euro sur une table sans superposition de façon à laisser le moins de surface libre, la meilleure façon est de les centrer sur une grille triangulaire. La première preuve est due à Toth (1943), on en présentera une preuve élémentaire. Peut-on faire plus dense si on a des pièces de un et deux euros ? Et si on peut jouer librement sur la taille des pièces ? On présentera quelques résultats et preuves, qui font intervenir des triangulations style Delaunay, de l'arithmétique d'intervalle et font travailler l'ordinateur. La morale est : à la fin, les pavages gagnent.

The question of extension of (partially defined) operators is ubiquitous in mathematics, physics and computer science. Here, after having dealt with it in general, we explicit concrete computations illustrating cases of unconditional and conditional convergences. This talk provides a collection of techniques coming from Mathematics, Computer Science and Arithmetics.

1. We to recall some of the facts about conc-characters ("Stars of the Plane") and the enlargement of indexations from polynomials to series (especially those who allow a "calculus" i.e. rational ones), from elements to shuffle and stuffle subalgebras.
2. Nuclearity of Hardy spaces
3. Examples of unconditional convergence, partition of indices for the transform of $\frac{log(1+x_0)}{x_0}x_1$ and handling of the "magic identity".

References

1. In SLC 74 :
   Van Chien Bui, Gérard H.E. Duchamp, Quoc Huan Ngô, Vincel Hoang Ngoc Minh and Christophe Tollu, (Pure) Transcendence Bases in φ-Deformed Shuffle Bialgebras (22 pp.), SLC 74
2. G. H. E. Duchamp and C. Tollu, Sweedler's duals and Schützenberger's calculus , In K. Ebrahimi-Fard, M. Marcolli and W. van Suijlekom (eds), Combinatorics and Physics, p. 67 - 78, Amer. Math. Soc. (Contemporary Mathematics, vol.~539), 2011.
3. https://mathoverflow.net/questions/310354/independence-of-characters-with-respect-to-polynomials
4. G.H.E. Duchamp, Ngo Quoc Hoan, Hoang Ngoc Minh, Kleene stars of the plane, polylogarithms and symmetries, TCS, 800, 2019, 52-72,
   DOI: 10.1016/j.tcs.2019.10.016

Le problème de l'assignation aléatoire euclidienne peut être considérée comme l'étude des propriétés statistiques de l'état fondamental d'un système dont les configurations sont constituées des matchings d’un graphe bipartite et dont les sommets sont extraits d'une certaine mesure de probabilité supporté sur $\mathbb{R}^d$. Ce problème est maintenant un problème classique dont les liens avec d'autres problèmes importants dans différentes disciplines sont bien connus depuis quelque temps. Après avoir discuté de certains de ces liens, je vais présenter une approche simple pour l'étude de l'asymptotique du coût moyen de la solution optimale en dimension d=1 (travail avec Andrea Sportiello). Par cette méthode, je montrerai comment régions où la densité de probabilité associée aux sommets du graphe bipartite est faible peuvent donner lieu à des corrections anomales à cette asymptotique (aussi logarithmiques), et comment, dans un autre cas, ces contributions peuvent être comparées à des contributions véritablement collectives par le biais de lignes critiques.

The question of extension of (partially defined) operators is ubiquitous in mathematics, physics and computer science. We will deal with it in general and questions of renormalisation and regularisation of polyzetas, in particular

• Algebraic independence of certain conc-characters ("Stars of the Plane").
• Enlargement of indexations from polynomials to series (especially those who allow a "calculus" i.e. rational ones).
• Downsampling Wrench's formula.

References

1. In SLC 74 :
   Van Chien Bui, Gérard H.E. Duchamp, Quoc Huan Ngô, Vincel Hoang Ngoc Minh and Christophe Tollu, (Pure) Transcendence Bases in φ-Deformed Shuffle Bialgebras (22 pp.), SLC 74
2. G. H. E. Duchamp and C. Tollu, Sweedler's duals and Schützenberger's calculus , In K. Ebrahimi-Fard, M. Marcolli and W. van Suijlekom (eds), Combinatorics and Physics, p. 67 - 78, Amer. Math. Soc. (Contemporary Mathematics, vol.~539), 2011.
3. https://mathoverflow.net/questions/310354/independence-of-characters-with-respect-to-polynomials
4. G.H.E. Duchamp, Ngo Quoc Hoan, Hoang Ngoc Minh, Kleene stars of the plane, polylogarithms and symmetries, TCS, 800, 2019, 52-72,
   DOI: 10.1016/j.tcs.2019.10.016

Using a probabilistic approach proposed by Vershik, one can study various classes of integer partitions. By endowing those classes with the Boltzmann distribution and applying local limit theorems, one may derive asymptotic enumeration formulas (such as the Hardy–Ramanujan formula), or the shape of partitions of large integers (e.g. the curve derived by Temperley in 1952). After reminding some notions of combinatorics and the definition of the Boltzmann distribution over a combinatorial structure, we will explain a procedure that can be used in order to derive the kind of results we mentioned and we will discuss applications to some classes of partitions.

The question of extension of (partially defined) operators is ubiquitous in mathematics, physics and computer science. We will deal with it in general and questions of renormalisation and regularisation of polyzetas, in particular

• Algebraic independence of certain conc-characters ("Stars of the Plane").
• Enlargement of indexations from polynomials to series (especially those who allow a "calculus" i.e. rational ones).
• Downsampling Wrench's formula.

References

1. In SLC 74 :
   Van Chien Bui, Gérard H.E. Duchamp, Quoc Huan Ngô, Vincel Hoang Ngoc Minh and Christophe Tollu, (Pure) Transcendence Bases in φ-Deformed Shuffle Bialgebras (22 pp.), SLC 74
2. G. H. E. Duchamp and C. Tollu, Sweedler's duals and Schützenberger's calculus , In K. Ebrahimi-Fard, M. Marcolli and W. van Suijlekom (eds), Combinatorics and Physics, p. 67 - 78, Amer. Math. Soc. (Contemporary Mathematics, vol.~539), 2011.
3. https://mathoverflow.net/questions/310354/independence-of-characters-with-respect-to-polynomials
4. G.H.E. Duchamp, Ngo Quoc Hoan, Hoang Ngoc Minh, Kleene stars of the plane, polylogarithms and symmetries, TCS, 800, 2019, 52-72,
   DOI: 10.1016/j.tcs.2019.10.016

Permutations, words, tableaux, and other such families of objects often play a role in diverse subfields of mathematics, physics and computer science. When the structure of the object under investigation is known there are well-established tools, such as symbolic and analytic combinatorics, that derive an enumeration, asymptotics, and the ability to randomly generate instances of the objects. However, the initial step from a definition of the object to a structural description is often ad-hoc, human-staring-at-a-blackboard type of work. We thus tried to automatize this work via an implementation "Combinatorial Exploration" in Python and applied it to several combinatorial objects, such as permutations, set partitions and words. In this talk we will focus on permutations and show how we have found structural descriptions of so-called 'permutation classes'. (See the project webpage: https://permutatriangle.github.io/papers/2019-02-27-combex.html)

A classical problem over trace monoids is the recognition of rational trace languages. This problem can be solved in a time proportional to the number of prefixes of the input trace. In this talk I will present some results on the number of prefixes of a trace of length n in the worst case and in the average case under suitable probabilistic assumptions. I will also discuss other results concerning the variance, the moments and the limit distribution of the corresponding random variables.

In this talk, I will report on several experiments around large scale enumerations in enumerative and algebraic combinatorics. I'll describe a methodology used to achieve large speedups in several enumeration problems. Indeed, in many combinatorial structures (permutations, partitions, monomials, young tableaux), the data can be encoded as a small sequence of small integers that can often efficiently be handled by a creative use of processor vector instructions. Through the challenging example of numerical monoids, I will then report on how Cilkplus allows for a extremely fast parallelization of the enumeration. Indeed, we have been able to enumerate sets with more that 10^15 elements on a single multicore machine. En collaboration avec Jean Fromentin.

Après avoir présenté des généralités concernant les jeux stochastiques simples (qui sont des chaînes de Markov où deux adversaires peuvent contrôler certains sommets), nous feront en particulier l'état en ce qui concerne les algorithmes de résolution de ces jeux, en regardant en particulier les algorithmes d'itération de stratégies. Enfin, nous présenterons un algorithme stochastique, qui améliore l'état de l'art, ayant une complexité paramétrée par le nombre de nœuds aléatoires du graphe.

In this talk, we consider the probability space of random digraphs defined as follow. We generate a random undirected graph by taking the classical Erdős–Rényi model $\mathbb G(n,p)$. Thereafter, each edge is given a direction, where each of the two directions has probability $\frac{1}{2}$ and all choices are made independently. The result is a simple digraph on $n$ vertices. We will study the the probability that a random digraph is acyclic when $p=O(1/n)$, i.e. it does not contain a directed cycle when the number of edges is linear in the number of vertices. This is a joint work with Dimbinaina Ralaivaosaona and Stephan Wagner.

Green and Tao famously proved that the set of primes contains arbitrarily long arithmetic progressions. We will explain the heavy machinery behind the Green-Tao theorem and explains why polynomial configurations are much harder than linear ones and what can still be done for them. We will also discuss other extensions of the Green-Tao theorem.

We are constructing the first steps of a noncommutative Picard-Vessiot theory and we illustrate this theory in the study of independences of a new family of Gamma functions.

I am going to discuss weak convergence in the Skorokhod space of Galton-Watson processes with immigration (GWI), properly normalized, under the assumption that the tail of the immigration distribution has a logarithmic decay. It will be explained that the limits are extremal shot noise processes. Interestingly, both the behavior in mean and the survival probability (especially in the subcritical case) of the underlying Galton-Watson processes without immigration affect the asymptotics in question. The sequence of the conditional expectations of GWI given the immigration forms a very particular instance of a (divergent) perpetuity. In view of this I shall also present functional limit theorems in the Skorokhod space for general divergent perpetuities and suprema of perturbed random walks which are closely related objects.

In this talk we will discuss recent results concerning large deviations of one-dimensional nearest neighbour random walk in site-random environment. Our main contribution is an extension of large deviation results to precise (rather than logarithmic) asymptotic. We will explain how this result is related to large deviations of branching process in random environment and stochastic recurrence equations.

Considérons un processus de Poisson ponctuel dans le plan. À l'instant initial, un segment issu de chaque point de ce processus croît à une vitesse aléatoire dans une direction aléatoire. La croissance de ce segment s'arrête dès qu'il en touche un autre. La réunion des segments percole-t-elle ? Quel est le lien avec le titre de l'exposé ? Travail en collaboration avec David Coupier et David Dereudre.

In the paper Arctic curves of the six-vertex model on generic domains: the Tangent Method [J. Stat. Phys. 164 (2016), arXiv:1605.01388], of Filippo Colomo and myself, we pose the basis for a method aimed at the determination of the ``arctic curve'' of large random combinatorial structures, i.e. the boundary between regions with zero and non-zero local entropy, in the scaling limit. In this paper many things are claimed, and few are proven. In particular, it is not made clear that variants of it can be made fully rigorous in certain circumstances. In this seminar we present the simplest such instance: we rederive the arctic circle phenomenon for ``domino tilings of the aztec diamond'', first discovered by Jockusch, Propp and Shor [arXiv:math/9801068, but in fact from 1995].

We will discuss the emerging substructures in graphs with degree constraints, digraphs, acyclic digraphs, and 2-CNF below the point of their respective phase transitions. While long time ago, probabilistic method allowed to establish the location of the transition points, with some very rough properties, more and more refined results gradually become available. With analytic combinatorics as a main tool, we will see what exactly is happening when the structure approaches its boiling point. Based on joint works with Élie de Panafieu and Vlady Ravelomanana.

We consider the model of first passage percolation on Zd in dimension d≥2 : we associate with the edges of the graph a family of i.i.d. non negative random variables. We interpret the random variable associated with an edge as its capacity, i.e., the maximal amount of water or information that can cross the edge per second. This leads to a natural definition of maximal flow through a bounded domain of the graph from a collection of sources to a collection of sinks. This maximal flow is equal to the minimal capacity of a cutset, i.e., a set of edges such that if we remove it from the graph we disconnect completely the sources from the sinks. In this talk, we will focus on one of the properties of this minimal cutset : it's cardinality. This is a joint work with Barbara Dembin (LPSM, Université de Paris).

We consider the random directed graph G(n,p) with vertex set {1,2,...,n} in which each of the n(n-1) possible directed edges is present independently with probability p. We are interested in the strongly connected components of this directed graph. A phase transition for the emergence of a giant strongly connected component is known to occur at p = 1/n, with critical window p= 1/n + λ n^-4/3 for λ ∈ R. We show that, within this critical window, the strongly connected components of G(n,p), rescaled by n^-1/3, converge in distribution to a sequence (C₁,C₂,...) of finite strongly connected directed multigraphs with edge lengths which are either 3-regular or loops. The convergence occurs the sense of an L¹ sequence metric for which two directed multigraphs are close if there are compatible isomorphisms between their vertex and edge sets which roughly preserve the edge-lengths. Our proofs rely on a depth-first exploration of the graph which enables us to relate the strongly connected components to a particular spanning forest of the undirected Erdős-Rényi random graph G(n,p), whose scaling limit is well understood. We show that the limiting sequence (C₁,C₂,...) contains only finitely many components which are not loops.

We study random minimal factorizations of the n-cycle into transpositions, which are factorizations of the full cycle (1,...,n) as a product of n-1 transpositions. It is known since Denes (1959) that they are counted by the sequence nn-2 and bijections with Cayley trees and parking functions have been found. Moreover, these factorizations are naturally encoded (in two different ways) by sequences of non-crossing set of chords of the unit disk. We establish limit theorems for these sets of chords. The limiting objects are constructed from Levy’s excursion processes and interpolate between the circle and Aldous’ Brownian triangulation. One key step of the proof is to connect our model with conditioned bitype Galton-Watson trees with offspring distribution varying with $n$, and to find the limit of the contour function of those trees. If time allows, we will also describe the limit of the trajectory of a fixed element in this factorization (in some sense, this is a local limit result in space). This is a joint work with Igor Kortchemski.

A record in a permutation is an entry which is either bigger or smaller than the entries either before or after it (there are four types of records). Entries which are not records are called internal points. We explore scaling limits (called permuton limits) of uniform permutations in the classes Sq(n,k) of almost square permutations of size n+k with exactly k internal points. We first investigate the case when k=0, this is the class of square permutations, i.e. permutations where every point is a record. The starting point for our result is a sampling procedure for asymptotically uniform square permutations. Building on that, we characterize the global behavior by showing that square permutations have a permuton limit which can be described by a random rectangle. We also explore the fluctuations of this random rectangle, which we can describe through coupled Brownian motions. We then characterize the permuton limit of almost square permutations with k internal points, both when k is fixed and when k tends to infinity along a negligible sequence with respect to the size of the permutation. Here the limit is again a random rectangle but of a different nature: we will show during the seminar that a phase transition on the shape of the limiting rectangles arises for different values of k. Joint work with E.Slivken and E. Duchi.

Étant donné un nuage de points poissonien, Hammersley étudia dans les années 70 le nombre maximal de points du nuage par lequel un chemin croissant peut passer. Ceci permettait alors d'obtenir la longueur asymptotique de la plus longue sous-suite croissante dans une grande permutation aléatoire. Dans cet exposé, nous généraliserons le problème d'Hammersley en rajoutant des contraintes sur le chemin et nous exposerons des couplages qui permettent de se ramener au problème originel. Travail en collaboration avec Lucas Gerin.

We consider prunings of two families of continuum random trees: the Lévy trees and the inhomogeneous continuum random trees. The so-called cut trees encode the genealogies of the fragmentations that come with the pruning. The reconstruction problem asks how much information about the initial tree is retained in its cut tree and how to recover it from the cut tree. We propose a new approach to the reconstruction problem, which has been treated previously for the Brownian CRT and for the stable trees. Our approach does not rely upon self-similarity and can apply to both Lévy trees and inhomogeneous continuum random trees. Joint work with Nicolas Broutin and Hui He.

Random graphs with finite excess appear naturally in at least two different settings: random graphs in the critical window (aka critical percolation on regular and other classes of graphs), and unicellular maps of fixed genus. In the first situation, the scaling limit of such random graphs was obtained by Addario-Berry, Broutin and Goldschmidt based on a depth-first exploration of the graph and on the coding of the resulting forest by random walks. This idea originated in Aldous' work on the critical random graph, using instead a breadth-first search approach that seem less adapted to taking graph scaling limits. We show hat this can be done nevertheless, resulting in some new identities for quantities like the radius and the two-point function of the scaling limit. We also obtain a similar ``breadth-first'' construction of the scaling limit of unicellular maps of fixed genus. This is based on joint work with Sanchayan Sen.

Permutation patterns is a burgeoning area of combinatorics. While many versions of the question ‘how many patterns can a permutation contain?’ have been asked over the years, each has been viewed in isolation. We present a unified viewpoint for these questions, as well as some answers.

Pour une famille d'objets combinatoires $C$ (donnée souvent sous forme d'un oracle), le problème de génération consiste à lister tous les objets de $C$ sans duplicats. Cela peut être lister tous les graphes series-parallèles de taille $n$ donnée, ou encore, lister tous les ensembles satisfaisant une certaine propriété (par exemple les stables d'un graphe donné). On souhaite mesurer la complexité en temps de tels algorithmes de génération exhaustive, mais puisque les objets à lister sont souvent en quantité exponentielle par rapport à la taille de l'oracle, on est intéressé par des algorithmes de temps polynomial en les tailles cumulatives des entrées et sorties (complexité dite "output-sensitive"). L'exposé portera sur les différentes problématiques associées à ces questions et considérera deux familles de problèmes : sous-graphes maximaux satisfaisant une propriété et les transversaux minimaux.

Étant donné un nombre premier p, on trouve en particulier des congruences modulo des puissances de p pour les nombres de Stirling et les nombres harmoniques généralisés en utilisant des techniques p-adiques. On généralise aussi indépendamment du mathématicien Z-H Sun (des nombres premiers) un résultat de Glaisher datant de 1900 sur le théorème de Wilson modulo p^2 au rang p^3.

Étant donné un nombre premier p, on trouve en particulier des congruences modulo des puissances de p pour les nombres de Stirling et les nombres harmoniques généralisés en utilisant des techniques p-adiques. On généralise aussi indépendamment du mathématicien Z-H Sun (des nombres premiers) un résultat de Glaisher datant de 1900 sur le théorème de Wilson modulo p^2 au rang p^3.

Dear Colleagues, I cordially invite you to my PhD defence which will take place in Université Paris 13 18/09/2019, 14:00 next Wednesday, room B107. Title: Interdisciplinary image of Analytic Combinatorics Abstract: This thesis is devoted to the development of tools and the use of methods from Analytic Combinatorics, including exact and asymptotic enumeration, statistical properties of random objects, and random generation. Certain focus is put on the multidisciplinarity of the domain, which is emphasised by using examples from computational logic, statistical mechanics, biology, mathematical statistics, networks and queueing theory. Rapporteurs: M Éric Fusy M Valeriy Liskovets M Konstantinos Panagiotou Jury: Mme Mireille Bousquet-Mélou M Éric Fusy M Andrea Sportiello Mme Brigitte Vallée Directeurs de thèse: M Olivier Bodini M Vlady Ravelomanana The defence will take place in the room B107, at 14:00, and will be followed by a traditional pot de soutenance, to which everyone is kindly invited. If you intend to come, please write me an email so that we can add submit your name to the security list. Kind regards, Sergey Dovgal

Les suites de nombres classiques ont souvent des q-analogues intéressants. Les plus connus sont certainement les q-nombres entiers et les q-coefficients binomiaux qui apparaissent tous deux dans différents domaines de mathématique et physique. En revanche, la notion de q-nombre rationnel n'existe pas vraiment. On propose une définition basée sur des propriétés combinatoires des rationnels et des fractions continues. La définition des q-rationnels étend naturellement celle des q-entiers et aboutit à un quotient de polynômes à coefficients entiers positifs. On donne une interprétation énumérative des coefficients de ces polynômes en termes de graphes et de représentations de carquois. On remarque aussi des liens avec les polynômes de Jones, les algèbres amassées, et une possible extension vers une notion de q-nombre réel. Il s'agit d’un travail en commun avec V.Ovsienko.

Je présenterai les fruits de mon travail de thèse qui s'intitule "Complexité de la recherche de motifs dans un texte aléatoire". Le jury sera composé de Frédérique Bassino (directrice de thèse), Julien Clément, Thierry Lecroq (rapporteur), Cyril Nicaud (rapporteur), Mireille Régnier, Andrea Sportiello. Vous êtes également conviés au pot qui suivra en salle A201. Cordialement, Tsinjo Rakotoarimalala

Les deux polynômes de Symanzik sont des invariants de graphes utilisés en théorie quantique des champs pour calculer des intégrales de Feynman. Le premier polynôme de Symanzik est le dual du polynôme de Kirchhoff pondéré, qui compte le nombre pondéré d'arbres couvrants d'un graphe. En 2009, Duval, Klivans et Martin ont généralisé la notion d'arbres et le théorème de Kirchhoff en dimensions supérieures (sur les complexes simpliciaux). Nous pouvons de même généraliser les polynômes de Symanzik. Les deux polynômes partagent de nombreuses propriétés remarquables, notamment une formule de délétion-contraction et une forme déterminantale. Toutefois, nous verrons que la propriété de stabilité par subdivision, propre aux polynômes de Symanzik, rend ces polynômes peut-être plus intéressants que leurs duaux.

La notion de frise d'entiers a été introduite dans les années 1970 par Conway et Coxeter. Une telle frise correspond à un nombre fini de bandes horizontales superposées d'entiers positifs (>0), bornées au-dessus et en dessous par des bandes de 1, avec une condition locale liant ces entiers. Plus explicitement on demande que ad-bc=1, pour toute configuration locale de a, b, c, et d en forme de « diamant » (a et d se suivent sur une même ligne, avec b et c respectivement juste au-dessus et en dessous). Conway et Coxeter ont souligné que cela force un phénomène de répétition cyclique horizontale; de là le terme de frise. Un autre aspect fascinant est qu'il n'y a qu'un nombre fini de telles frises ayant un nombre fixé de lignes, et qu'elles sont énumérées par les nombres de Catalan. Après un survol de cette notion et de sujets reliés, nous allons en considérer diverses généralisations. En particulier, on établira des liens avec la formule de condensation de Dogdson (l'auteur d'Alice au pays des merveilles) pour un calcul récursif de déterminants.

D-finite functions is a well known class of functions. They are defined via a linear differential equation with polynomial coefficients and we can find many examples in elementary functions (exp(x), sin(x)), combinatorial generating functions (all P-recursive sequence have a D-finite generating function) and many other special functions. In this talk we will see a natural extension to this class: the DD-finite (and, more generically, Dn-finite) functions. These functions are defined using a linear differential equation with D-finite coefficients. We will described the structural properties known for this larger class of functions.

La notion d'espèces de structures combinatoires, introduite il y a presque 40 ans, fournit un contexte conceptuel naturel pour décrire la nature de « structures combinatoires » sur un ensemble. Non seulement des opérations fondamentales entre espèces de structures permettent d'élaborer naturellement, et de spécifier de nouvelles espèces en termes d'espèce connues; mais cette approche donne directement les identités combinatoires correspondantes. On obtient ainsi une approche systématique à la résolution de problèmes classiques d'énumération, autant dans leur version étiquetée que non-étiquetée (alias : théorie de Pólya). Nous allons donner une présentation accessible à cette théorie, avec plusieurs illustrations. Si le temps le permet, nous allons survoler différents domaines d'applications récents au-delà des aspects plus habituels de combinatoire énumérative (physique théorique, chimie, etc.).

While the enumeration of linear extensions of a given poset is a well-studied question, its cyclic counterpart (enumerating extensions to total cyclic orders of a given partial cyclic order) has been subject to very little investigation. In this talk I will introduce some classes of partial cyclic orders for which this enumeration problem is tractable. Some cases require the use of a multidimensional version of the classical boustrophedon construction (a.k.a. Seidel-Entringer-Arnold triangle). The integers arising from these enumerative questions also appear as the normalized volumes of certain polytopes. This is partly joint work with Arvind Ayyer (Indian Institute of Science) and Matthieu Josuat-Verges (Laboratoire d’Informatique Gaspard Monge / CNRS).

Cet exposé concerne la génération aléatoire de familles classiques de chemins (Dyck, Motzkin et Schröder et leurs préfixes). Le point de départ est l'algorithme florentin (Barcucci, Pinzani et Sprugnoli 1994+), qui utilise une méthode de rejet anticipé pour engendrer les préfixes. Je montrerai comment on peut raffiner cet algorithme en utilisant une fonction de « rattrapage » qui permet de fortement réduire, voire d'éliminer, la probabilité de rejet. Les algorithmes obtenus sont asymptotiquement optimaux en termes d'entropie utilisée et significativement plus rapides que les algorithmes florentins.

Trace monoids are basic mathematical models of concurrent systems. The probabilistic framework on trace monoids can be found in Abbes and Mairesse (2015) including the uniqueness of uniform measure and random generation. To adopt more practical dynamic systems, it is essential to take account of ”state”. Conventionally, we model the ”concurrency” by the traces in a trace monoid and model the ”state” by the words in an automaton. Combining these two features, we consider the traces in an automaton, which is equivalent to the executions in a safe Petri net. Our goal is to prove the uniqueness of the uniform measure for partial actions on a trace monoid in order to generate uniformly the infinite executions of a 1-safe Petri net. In this talk, I will present some properties and the difficulties that we encounter now.

Dans cet exposé, on s'intéresse aux liens entre trois familles d'objets comptés par des formules closes remarquablement similaires entre elles. Si le nombre de polyominos convexes est connu depuis les travaux de Delest et Viennot, les formules closes des permutations carrées et permutominoes convexes ont été découvertes plus récemment et sont moins connues mais tout aussi jolies. Pour expliciter le lien entre ces différentes classes, nous reverrons différentes méthodes d'énumération.

Imagine a plane tree together with a configuration of particles (cars) at each vertex. Each car tries to park on its node, and if the latter is occupied, it moves downward towards the root trying to find an empty slot. This model has been studied recently by Bruner and Panholzer as well as Goldschmidt and Przykicki where is it shown that parking of all cars obeys a phase transition ruled by the density of cars. We study the annealed critical model of random plane tree together with a parking configuration of cars. Surprisingly this object is connected to stable looptre e of parameter 3/2 and to processes encountered in the theory of random planar maps! The talk is based on ongoing work with Olivier Hénard.

There are two natural well-studied measures on integer partitions: Plancherel and uniform. In the scaling limit, their first parts behave differently and on a different scale: Plancherel shows random matrix-type Tracy-Widom statistics (the Baik-Deift-Johansson theorem), while uniform shows Gumbel, a maximum of independent Gaussians (the Erdős-Lehner theorem). In this talk, based on joint work with Jérémie Bouttier, we present the 'finite temperature/cylindric' extension of the Plancherel measure, coming from counting standard Young tableaux of skew shape and interpolating between Plancherel and uniform. The edge scaling limit yields the finite temperature Tracy-Widom distribution of Johansson, observed in random matrix models and interpolating between Tracy-Widom and Gumbel statistics. A time-extension of the result yields the finite temperature/periodic extended Airy process of Le Doussal-Majumdar-Schehr.

Research on Kronecker coefficients and plethysms gained significant momentum when the topics were connected to geometric complexity theory, an approach towards computational complexity lower bounds via algebraic geometry and representation theory. Both types of coefficients appear independently in R. Stanley's list of "Positivity problems and conjectures in algebraic combinatorics". This talk is about a result that was obtained with geometric complexity theory as motivation, namely an inequality between rectangular Kronecker coefficients and plethysm coefficients. The proof interestingly uses insights from algebraic complexity theory. As far as we are aware, algebraic complexity theory has never been used before to prove an inequality between representation theoretic multiplicities. This is joint work with Greta Panova (Rectangular Kronecker coefficients and plethysms in geometric complexity theory, Adv Math 2017).

A marked point process is a series of events generated along the time which is accompanied with some additional information. Examples of the marked point processes include trades in foreign exchange markets, earthquake activities, and times at which a neuron fires an action potential. Calculating a distance between two time windows of a given marked point process is the first step to analyze it from the viewpoint of nonlinear dynamics.
In this talk, I would like to introduce a new faster algorithm for the distance computation, and show its validity through preliminary numerical experiments. I also discuss the median computation problem. This talk is based on my recent joint work with Prof. Yoshito Hirata (Univ. of Tokyo, Japan).

Dans un graphe d'Erdős-Rényi à $N$ sommets et probabilité de connexion $c/N$, on démontrera que les arbres couvrants de la composante géante construits par des algorithmes d'exploration basés sur la recherche en profondeur convergent vers une limite déterministe explicite. Cela exhibe entre autres des chemins simples, éventuellement induits, du graphe de longueur linéaire en $N$. Si le temps le permet j'évoquerai ensuite le cas des graphes construits par modèle de configuration. Ces résultats sont issus de collaborations avec Gabriel Faraud, Nathanaël Enriquez et Nathan Noiry.

Les nanoparticules sont des objets chimiques dont les trois dimensions sont inférieures à 100 nm. L'exposé présentera dans un premier temps les intérêts que suscitent les nanoparticules en tant que telles et les stratégies pour limiter/contrôler leur croissance à l'échelle nanométrique. La deuxième partie abordera le fait de les assembler, la chimie "supraparticulaire" ou leur auto-assemblage dans l'espace et sur surface.

Cécile Dartyge et András Sárközy ont introduit une notion de « chiffres » dans les corps finis. Nous mesurons de manière quantitative le caractère pseudo-aléatoire de ces chiffres en lien avec les opérations de multiplication et d'addition au travers de l'étude de suites remarquables. Nos résultats peuvent être réinterprétés à l'aide la notion de trace qui est fondamentale dans les corps finis.

In the 1970s, William Tutte developed a clever algebraic approach, based on certain “invariants”, to solve a functional equation that arises in the enumeration of properly colored triangulations. The Laplace transform of the stationary distribution of semimartingale reflected Brownian motion (SRBM) in wedges satisfies similar equations. To be applicable, the method requires the existence of two functions called invariant and decoupling function, respectively. While all models have invariants, we prove that the existence of a decoupling function is equivalent to a simple geometric condition on the angles. For the models that have in addition a decoupling function, we obtain integral-free expressions of the Laplace transform in terms of the invariants. As a consequence, we obtain new derivations of the Laplace transform in several well-known cases, as the skew symmetric SRBM, orthogonal reflections, or the Dieker-Moriarty result characterizing sum-of-exponential densities. Cet exposé est issu d’un travail en cours en collaboration avec Mireille Bousquet-Mélou, Charlotte Hardouin, Andrew Elvey Price et Kilian Raschel

We set the foundation for a series of works aimed at proving strong relations between uniform random planar maps and Liouville quantum gravity (LQG). Our method relies on a bijective encoding of site-percolated planar triangulations by certain 2D lattice paths. Our bijection parallels in the discrete setting the mating-of-trees framework of LQG and Schramm-Loewner evolutions (SLE) introduced by Duplantier, Miller, and Sheffield. Combining these two correspondences allows us to relate uniform site-percolated triangulations to $\sqrt{8/3}$-LQG and SLE${}_6$. In particular, we establish the convergence of several functionals of the percolation model to continuous random objects defined in terms of $\sqrt{8/3}$-LQG and SLE${}_6$. For instance, we show that the exploration tree of the percolation converges to a branching SLE${}_6$, and that the collection of percolation cycles converges to the conformal loop ensemble CLE${}_6$. We also prove convergence of counting measure on the pivotal points of the percolation. Our results play an essential role in several other works, including a program for showing convergence of the conformal structure of uniform triangulations and works which study the behavior of random walk on the uniform infinite planar triangulation. (Joint work with Olivier Bernardi and Xin Sun.)

Dans le modèle de graphe aléatoire d'Erdős–Rényi $G(n,p)$, l'émergence de la composante géante se situe à la fenêtre $p=n^{-1}+O(n^{-4/3})$. Lorsque $p$ varie de $(1-\epsilon)n^{-1}$ (sous-critique) à $n^{-1}$, puis à $(1+\epsilon)n^{-1}$, la plus grande composante varie de $O(\epsilon^{-2}\log(n\epsilon^3))$ à $\Theta(n^{2/3})$, puis $(1+o(1)) 2 \epsilon n$. Nous considérons une généralisation de $G(n,p)$ sur les hypergraphes k-uniformes, avec une notion de connexité d'ordre supérieur. Plus précisément, pour $1 \leq j < k$, considérons les ensembles de j sommets, appelés les j-ensembles. Deux j-ensembles sont j-connexes s'il existe entre eux un chemin d'hyperarêtes dont l'intersection de deux hyperarêtes consécutives contient au moins $j$ sommets. Une composante j-connexe est une famille maximale de j-ensembles qui sont j-connexes l'un à l'autre. Sous cette notion de j-connexité, nous avons déterminé, dans un régime sous-critique, la taille précise des $m$ plus grandes composantes j-connexes, et aussi leur structure. C'est un travail joint avec Oliver Cooley, Nicola Del Giudice et Mihyun Kang.

A pattern in a permutation is a subsequence with a specific relative order. What can we say about a typical large random permutation that avoids a particular pattern? We use a variety of approaches. For certain classes we give a geometric description that relates these classes to other types of well-studied random objects like random walks or random trees. Using the right geometric description we can find the the distribution of certain statistics like the number and location of fixed points. Earlier work dealt with permutations that avoid a pattern of length 3 using a variety of bijections. More recently, using connections with random walks in cones, we show certain scaling limits for permutations avoiding longer monotone patterns are given by traceless Dyson Brownian motion. This is joint work with Christopher Hoffman and Douglas Rizzolo.

En 1950, Foulkes a formulé une conjecture simple sur le pléthysme de fonction symétriques qui n’est toujours pas résolue aujourd’hui. De fait, elle avait déjà été énoncée (sous une autre forme) par Hadamard en 1897. Assez récemment, elle a été généralisée d’une façon qui soulève plusieurs jolis problèmes de combinatoire énumérative, que nous allons décrire. Puis, après avoir mis en place les concepts nécessaires et discuté des avancées sur la question, nous allons présenter de nouvelles conjectures encore plus générales (incluant des $q$-analogues), et montrer quelques résultats associés.

Nous présenterons une approche pour faire de la génération aléatoire de polytopes entiers en utilisant les chaînes de Markov. Les objets à engendrer sont les polytopes entiers contenus dans l'hypercube ${[0,k]}^d$, notés $(d,k)$-polytopes. On s’intéresse à la distribution uniforme sur nos objets. La construction du générateur aléatoire se fait de la manière suivante : modéliser une chaîne de Markov dont les états seront les $(d,k)$-polytopes, lancer des marches sur la chaîne jusqu'à ce qu'on soit assez proche d'une distribution stationnaire. Notre principal résultat est que cette distribution stationnaire est unique et uniforme. Je présenterai également des résultats sur le temps de mélange de notre chaîne.

A hypergraph is Sperner if no hyperedge contains another one. A Sperner hypergraph is equilizable (resp., threshold) if the characteristic vectors of its hyperedges are the (minimal) binary solutions to a linear equation (resp., inequality) with positive coefficients. These combinatorial notions have many applications and are motivated by the theory of Boolean functions and integer programming. We introduce the class of 1-Sperner hypergraphs, defined by the property that for every two hyperedges the smallest of their two set differences is of size one. We characterize this class of Sperner hypergraphs by a decomposition theorem and derive several consequences from it, including bounds on the size of 1-Sperner hypergraphs, a proof that every 1-Sperner hypergraph is both threshold and equilizable, and an efficient algorithm for genera ting the minimal transversals within this class of hypergraphs. Several applications of 1-Sperner hypergraphs and their structure to graphs will also be discussed, including new characterizations of threshold graphs and new classes of graphs of bounded clique-width. The talk is based on joint works with Endre Boros and Vladimir Gurvich.

Étant donné un groupe de permutation infini G, on définit la fonction qui à tout entier naturel n associe le nombre d'orbites de sous-ensembles de cardinal n, pour l'action induite de G sur les sous-ensembles d'éléments. Cameron a conjecturé que cette fonction de comptage (le profil de G) est un quasi-polynôme dans le cas où sa croissance est polynomiale. Une autre conjecture, plus forte, a été émise plus tard par un de ses étudiants, Macpherson. Elle concerne une certaine structure d'algèbre graduée sur les orbites de sous-ensembles, créée par Cameron, et suppose que si le profil de G est polynomial, alors son algèbre des orbites est de type fini. L'exposé présentera ces deux conjectures et leur contexte, ainsi que les idées de la preuve de la conjecture de Macpherson, fruit d'un travail commun avec Nicolas Thiéry (avec les conseils précieux de Peter Cameron lui-même).

Introduced by Gosper in 1978, the Continued Logarithm Algorithm computes the gcd of two integers efficiently, performing only shifts and subtractions. Shallit has studied its worst-case complexity in 2016, showing it to be linear. Here, we perform the average-case analysis of the algorithm: we study its main parameters (number of iterations, total number of shifts) and obtain precise asymptotics for their mean values, with explicit constants. Our analysis involves the dynamical system underlying the algorithm, which produces continued fraction expansions whose quotients are powers of 2. Even though studied by Chan in 2005, this system from an Ergodic Theory perspective, the presence of powers of 2 in the quotients gives a dyadic flavour which cannot be analysed only with Chan's results. Thus we introduce a dyadic component and deal with a two-component dynamical system. With this new mixed system at hand, we provide a complete average-case analysis of the algorithm.

To every factor w of an infinite word x in a finite alphabet, we can associate a bipartite graph, called the extension graph of w, in which one puts edges between left and right copies of letters a, b such that awb is a factor of x. The word x is said to be dendric if for all factor w of x, the extension graph of w is a tree. Dendric words are therefore defined in terms of combinatorial properties of their language. Dendric subshifts are symbolic systems defined using dendric words. We will talk about some dynamical properties of dendric subshifts.

On introduit le modèle d'arbres suivant. On se donne une suite arbitraire de nombres réels positifs $(a_n)_{n\geq 1}$. On définit $T_1$ comme l'arbre à un seul sommet d'étiquette $1$. Si $T_n$ est déjà construit, $T_{n+1}$ est obtenu en rajoutant un sommet étiqueté $n+1$ à l'arbre $T_n$. Le nouveau sommet est un enfant du sommet $k\geq n$ avec une probabilité proportionnelle à $a_k+deg(k)$, où $deg(k)$ est le degré du sommet dans l'arbre $T_n$. On s'intéressera à l'évolution de la suite des degrés des sommets de l'arbre. Sous certaines conditions sur la suite des réels $(a_n)_{n\geq 1}$, la suite des degrés adéquatement renormalisés converge p.s. (dans $l^p$ pour p assez grand) vers une suite aléatoire, qui peut être décrite comme les accroissements successifs d'une chaîne de Markov. Pour certaines suites $(a_n)$, la loi de la chaîne de Markov est même explicite. La preuve utilise des résultats classiques sur les urnes de Pólya, que je rappellerai.

La théorie géométrique de la complexité (GCT) est un programme de recherche lancé par K. Mulmuley et M. Sohoni aux alentours de 2000 pour attaquer la variante algébrique, due à L. Valiant, de la conjecture centrale de la théorie de la complexité, l'hypothèse de Cook $P \neq NP$. Ce programme substitue aux hypothèses de Cook et de Valiant une conjecture de nature géométrique, à laquelle les formidables outils de la géométrie algébrique et de la théorie des représentations peuvent être appliqués. Dans l'esprit de ses promoteurs, la GCT avait aussi pour but de permettre de démontrer l'existence de minorants de complexité ("lower bounds" en franglais) par la production effective de témoins. Dans ce mini-tutoriel sur la GCT, je présenterai le programme initial de Mulmuley-Sohoni, quelques-uns des développements récents et des obstacles qui sont apparus dans sa réalisation. Aucune compétence particulière en géométrie ou en théorie des représentations n'est requise des participants.

La théorie géométrique de la complexité (GCT) est un programme de recherche lancé par K. Mulmuley et M. Sohoni aux alentours de 2000 pour attaquer la variante algébrique, due à L. Valiant, de la conjecture centrale de la théorie de la complexité, l'hypothèse de Cook $P \neq NP$. Ce programme substitue aux hypothèses de Cook et de Valiant une conjecture de nature géométrique, à laquelle les formidables outils de la géométrie algébrique et de la théorie des représentations peuvent être appliqués. Dans l'esprit de ses promoteurs, la GCT avait aussi pour but de permettre de démontrer l'existence de minorants de complexité ("lower bounds" en franglais) par la production effective de témoins. Dans ce mini-tutoriel sur la GCT, je présenterai le programme initial de Mulmuley-Sohoni, quelques-uns des développements récents et des obstacles qui sont apparus dans sa réalisation. Aucune compétence particulière en géométrie ou en théorie des représentations n'est requise des participants.

La théorie géométrique de la complexité (GCT) est un programme de recherche lancé par K. Mulmuley et M. Sohoni aux alentours de 2000 pour attaquer la variante algébrique, due à L. Valiant, de la conjecture centrale de la théorie de la complexité, l'hypothèse de Cook $P \neq NP$. Ce programme substitue aux hypothèses de Cook et de Valiant une conjecture de nature géométrique, à laquelle les formidables outils de la géométrie algébrique et de la théorie des représentations peuvent être appliqués. Dans l'esprit de ses promoteurs, la GCT avait aussi pour but de permettre de démontrer l'existence de minorants de complexité ("lower bounds" en franglais) par la production effective de témoins. Dans ce mini-tutoriel sur la GCT, je présenterai le programme initial de Mulmuley-Sohoni, quelques-uns des développements récents et des obstacles qui sont apparus dans sa réalisation. Aucune compétence particulière en géométrie ou en théorie des représentations n'est requise des participants.

La théorie géométrique de la complexité (GCT) est un programme de recherche lancé par K. Mulmuley et M. Sohoni aux alentours de 2000 pour attaquer la variante algébrique, due à L. Valiant, de la conjecture centrale de la théorie de la complexité, l'hypothèse de Cook $P \neq NP$. Ce programme substitue aux hypothèses de Cook et de Valiant une conjecture de nature géométrique, à laquelle les formidables outils de la géométrie algébrique et de la théorie des représentations peuvent être appliqués. Dans l'esprit de ses promoteurs, la GCT avait aussi pour but de permettre de démontrer l'existence de minorants de complexité ("lower bounds" en franglais) par la production effective de témoins. Dans ce mini-tutoriel sur la GCT, je présenterai le programme initial de Mulmuley-Sohoni, quelques-uns des développements récents et des obstacles qui sont apparus dans sa réalisation. Aucune compétence particulière en géométrie ou en théorie des représentations n'est requise des participants.

Nous calculons l'entropie au bord pour la percolation d’arêtes sur le réseau carré, dans la présence d’un poids statistique pour les boucles qui touchent le bord. Ainsi, nous obtenons des expressions exactes pour le ruban et le cylindre de taille L. Pour le cylindre, nous présentons une analyse asymptotique rigoureuse qui permet le calcul des corrections de taille finie à un ordre arbitraire. Pour le ruban, nous donnons des expressions exactes qui ont été vérifiées par des calculs numériques de haute précision. Nos résultats rigoureux viennent en appui à un argument basé sur la théorie conforme des champs, en particulier en ce qui concerne les corrections logarithmiques universelles pour le cas du ruban, dues aux effets géométriques des coins.

Après un rappel sur les circuits arithmétiques et le problème de Valiant (VP vs VNP), je présenterai quelques résultats récents sur la "complexité déterminantale" du permanent, puis montrerai comment la version purement algébrique du problème VP vs VNP se prête à une reformulation en termes de géométrie des orbites du déterminant et du permanent (pour l'action d'un groupe algébrique sur les polynômes homogènes). Plusieurs ingrédients de base du programme de théorie géométrique de la complexité de Mulmuley et Sohoni seront présentés au cours de l'exposé bien que celui-ci ne soit pas "A crash course on Geometric Complexity Theory

Reporting on recent work with G.H.E. Duchamp and K.A. Penson (arXiv:1712.06575), I plan to present a formulation of chemical reaction systems in the so-called stochastic mechanics formalism. This approach allows to uncover some deep relationships between the combinatorial techniques of boson normal-ordering and the dynamics of chemical reaction networks: each semi-linear reaction type induces an evolution within a space of probability distributions that can be computed explicitly via our techniques. For the interesting remaining types of reactions, some results involving systems of Sobolev-Jacobi orthogonal polynomials will be presented.

In this work, a new branch-and-price-and-cut algorithm is proposed to solve the one-dimensional bin packing problem (1D-BPP). The 1D-BPP is one of the most fundamental problems in combinatorial optimization and has been extensively studied for decades. Recently, Delorme et al. (2016) proposed 500 new test instances for the 1D-BPP; the best exact algorithm proposed in the literature can optimally solve 167 of these new instances, with a time limit of one hour imposed to each execution of the algorithm. The exact algorithm proposed in this paper is based on the classical set-partitioning model for the 1D-BPP and the subset-row inequalities proposed by Jepsen et al. (2008). We describe an ad-hoc label-setting algorithm to solve the pricing problem, dominance and fathoming rules to speedup its computation and a new primal heuristic. The exact algorithm can easily handle some practical constraints, like the incompatibility between the items, and therefore we also apply it to solve the 1D-BPP with conflicts (1D-BPPC). The proposed method is tested on a large family of 1D-BPP and 1D-BPPC classes of instances. For the 1D-BPP, the proposed method can optimally solve 237 instances of the new set of difficult instances; the largest instance involves 1003 items and bins of capacity 80,000. For the 1D-BPPC, the experiments show that the method is highly competitive with state-of-the-art methods, and successfully closed several open 1D-BPPC instances.

Soit \(a_n\) une suite de nombres entiers et considérons le produit \(\prod_{n=1}^{N} a_n\). Combien ce produit a-t-il de facteurs premiers ? Quel est le plus grand ? Nous présenterons différents résultats concernant des suites célèbres : les nombres de Fermat, de Fibonacci, \(n!+1\)...

En dimension d≥3, on prend n simplexes, et on recolle leurs facettes de manière arbitraire. On obtient ainsi un espace topologique qui est a priori une pseudo-variété, mais pas toujours une variété. De combien de manière peut-on le faire, asymptotiquement, pour obtenir une variété? On donne des réponses (très) partielles à cette question sous la forme de bornes inférieures et supérieures superexponentielles. En particulier on détermine le comportement surexponentiel en dimension 3, dans le cas des triangulations coloriées issues des modèles de tenseur. Au passage on croise des questions rigolotes et nouvelles d'énumération de graphes que nous laissons partiellement ouvertes. Travail en commun avec Guillem Perarnau.

Dans cet exposé, nous commencerons par rappeler la notion de temps de mélange d'une chaîne de Markov et introduirons le phénomène de cutoff, qui décrit une convergence très abrupte à l'équilibre. Établir le cutoff pour une chaîne donnée requiert souvent une analyse extrêmement fine, et il existe assez peu de résultats généraux permettant par exemple d'exhiber des grandes classes de graphes sur lesquels la marche aléatoire présente le cutoff. On peut alors se demander ce qu'il se passe sur un graphe « typique ». Nous considérerons le cas des graphes aléatoires à suite prescrite de degrés, et montrerons qu'avec forte probabilité, sur de tels graphes, la marche aléatoire simple et la marche aléatoire dite « sans rebroussement » présentent le cutoff. En interprétant les temps de mélange comme des entropies limites sur un arbre de Galton-Watson qui constitue une approximation locale du graphe, nous montrerons de plus que la marche aléatoire sans rebroussement mélange plus vite que la marche simple. Ces résultats sont issus de collaborations avec Justin Salez (Paris Diderot), Eyal Lubetzky (NYU) et Yuval Peres (Microsoft Research).

Ce travail (en collaboration avec C. Donati-Martin et V. Beffara) est une extension d'un article de G. Chapuy (2007), obtenue en remplaçant le groupe des permutations d'ordre n muni de la probabilité uniforme par le groupe unitaire (resp. orthogonal) d'ordre n. On définit ainsi une suite indexée par n de processus à deux paramètres qui converge en loi vers un drap brownien. Les preuves mettent en jeu la combinatoire associée au calcul de Weingarten.

Pólya urns are urns where at each unit of time a ball is drawn uniformly at random and is replaced by some other balls according to its colour. We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time mod p. Our key tool are generating functions, which encode all possible urn compositions after a certain number of steps. The evolution of the urn is then translated into a system of differential equations and we prove that the moment generating functions are D-finite. From these we derive asymptotic forms of the moments. When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions. Furthermore, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions.

Dans cet exposé, on parlera de la notion de hom-idempotence dans l'ensemble de graphes : un graphe $G$ est dit hom-idempotent s'il existe un homomorphisme entre le graphe produit cartésien $G*G$ et $G$ lui-même. Cette notion est fortement liée à une classe particulière de graphes de Cayley qu'on appelle les graphes de Cayley normaux. On montrera que les graphes de Kneser $K(n,k)$ ne sont pas hom-idempotents. On montrera aussi que les graphes s-stables de Kneser $K(n,k)_s$ ne sont pas hom-idempotents si $s=2$ mais, pour $n=sk+1$, $K(n,k)_s$ est hom-idempotent. Finalement, on appliquera la notion de hom-idempotence à la $k$-tuple coloration de graphes : une $k$-tuple coloration de graphes consiste en affecter à chaque sommet un $k$-ensemble de couleurs de sorte que sommets adjacents reçoivent $k$-ensembles disjoints. On montrera que la différence entre le nombre chromatique du graphe produit cartésien de graphes de Kneser $K(n,k)*K(n,k)$ et le nombre chromatique d'une 2-tuple coloration du même graphe $K(n,k)*K(n,k)$ n'est pas bornée.

In biology a phylogenetic tree is a classical tool to represent the evolutionary relationship among species. Our main frustration against the classical combinatorial models is related to the chrono- logical aspect that seems not considered by the models. E. g. the Schröder trees do not take into account the time evolution. We develop in this paper a model for phylogenetic trees satisfying in priority two constraints: (1) to take into account the chronological evolution and (2) to be efficient to simulate. Our model is based on some increasingly labeling of Schröder trees.

I will explain theory convexity for lattices, free Abelian groups without torsion. I will show that a famous class of polytopes, polymatroids of combinatorial optimization, is related to one of classes of discrete convexity. Several instances of discretely convex functions related to combinatorics of Young tableaux will be demonstrated.

On considère la famille des polynômes \(P_m(X)\in {\mathbb Q}[X]\) donnée par $$\prod_{m\ge 1} (1-q^m)^{-z}=\sum_{m\ge 0} P_m(z) q^m.$$ Ces polynômes ont des connexions profondes avec la théorie des nombres (pour les partitions d'entiers) et avec la fonction \(\tau\) de Ramanujan. Ils sont apparus pour la première fois dans le travail de Newman de 1955, et ont été utilisé par Serre dans son travail de 1985 sur la lacunarité des puissances de la fonction \(\eta\) de Dedeking. Ils peuvent être donnés aussi par \(P_0(X)=1\) et $$P_m(X)=\frac{X}{m}\left(\sum_{k=1}^m \sigma(k) P_{m-k}(X)\right)\qquad {\text{ pour}}\qquad m\ge 1.$$ Il est facile de voir que \(P_m(X)\) n'a aucune racine positive. De plus, par la formule pentagonale d'Euler, on déduit que \(X+1\mid P_m(X)\) pour un nombre infini de \(m\). On se pose la question de savoir si \(P_m(X)\) peut avoir comme zéro d'autres racines de l'unité différentes de \(-1\). On montre que cela n'est jamais le cas, c'est-à-dire que si \(\zeta\) est une racine d'unité d'ordre \(N\ge 3\) et \(m\ge 1\), alors \(P_m(\zeta)\ne 0\). La preuve utilise des resultats classiques sur les corps finis, et un petit peu de théorie analytique des nombres.

En 1996, Propp et Wilson ont proposé un algorithme permettant l'échantillonnage sans biais de la distribution stationnaire d'une chaîne de Markov ergodique. Ce dernier appelé aussi algorithme de simulation parfaite, requiert la simulation en parallèle de tous les états possibles de la chaîne. Un des challenges lorsque l'on veut faire de l'échantillonnage par simulation parfaite réside généralement à mettre en place des stratégies permettant de ne pas avoir à simuler toutes les trajectoires. Un réseau fermé de files d'attente est un réseau dans lequel les clients ne peuvent ni entrer ni quitter le réseau. La dynamique de tels réseaux est couramment représentée par une chaîne de Markov ergodique. La difficulté pour qui voudrait appliquer l'algorithme de Propp et Wilson à de tels réseaux, réside dans la taille de l'espace des états qui est exponentielle en le nombre de files à laquelle s'ajoute une contrainte globale à savoir le nombre constant de clients.

Les structures dans lesquelles l'ordre des opérateurs est important se codent facilement par des mots. Il en est ainsi des intégrales itérées. Nous montrerons qu'alors, considérer la serie génératrice (non-commutative) permet de se ramener à une équation différentielle (non-commutative) très simple pour laquelle on peut développer un "calculus" élémentaire et très puissant.

Cluster algebras, invented by Sergey Fomin and Andrei Zelevinsky around 2000, are commutative algebras whose generators and relations are constructed in a recursive manner. Due to cluster recursion we obtain Laurent polynomials in the initial variables, so-called Laurent phenomenon of cluster algebras. The coordinate ring of base affine space C[N_-\SL_n] plays an important role in representation theory and is endowed with a cluster algebra structure. We show that under specialization of minors to Schur functions, Laurent polynomials of this cluster algebra turn into 'homogeneous' sums of Schur function. A positivity conjecture says that these sums have positive coefficients. This conjecture is true for finite cluster subalgebras.

Consider the following particle system. We are given a uniform random rooted tree on vertices labelled by {1,2,...,n}, with edges directed towards the root. Each node of the tree has space for a single particle (we think of them as cars). A number m of cars arrives one by one, and car i wishes to park at node S_i, where S₁, S₂,... , S_m are i.i.d. uniform random variables on {1,2,...,n}. If a car arrives at a space which is already occupied, it follows the unique path oriented towards the root until the first time it encounters an empty space, in which case it parks there; otherwise, it leaves the tree. Let A_n,m denote the event that all m cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Set m = [α n]. Then if α ≤ 1/2, P(A_{n,[α n]}) → sqrt(1-2α)/(1-α), whereas if α > 1/2 we have P(A_{n,[α n]}) → 0. (In fact, they proved more precise asymptotics in n for α ≥ 1/2.) In this talk, I will give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Time permitting, I will also discuss some generalisations.

We introduce a family of polytopes, called primitive zonotopes, which can be seen as a generalization of the permutahedron of type B_d. We discuss connections to the largest diameter of lattice polytopes and to the computational complexity of multicriteria matroid optimization. Complexity results and open questions are also presented. In particular, we answer a question raised in 1986 by Colbourn, Kocay, and Stinson by showing that deciding whether a given sequence is the degree sequence of a 3-hypergraph is computationally prohibitive. Based on joint works with Asaf Levin (Technion), George Manoussakis (Paris Sud), Shmuel Onn (Technion).

I am going to talk about very popular combinatorial connection between ordinary and exponential generating functions which is called cycle index function. I am going to define the combinatorial species according to the book "Theory of Species" by Bergeron, Labelle, Leroux, and present their beautiful proof of the cycle index composition theorem. The proof relies on the theory of symmetric functions in infinitely many variables. This proof is a beautiful example of Grothendieck's concept: in order to prove something particular, one should make a more general statement and prove it.

On montre que le calcul du PGCD de 𝑚 integers de 𝑂(𝑛) bits peut se faire en parallèle en temps 𝑂(𝑛 / log 𝑛) avec 𝑂(𝑚𝑛^1+𝜖 ) processors, pour tout 2 ≤ 𝑚 ≤ 𝑛^3/2 / log 𝑛, c'est-à-dire que le temps de calcul en parallèle ne dépend pas dépend du nombre d'entiers m considéré dans cet intervalle.

I am going to talk about very popular combinatorial connection between ordinary and exponential generating functions which is called cycle index function. I am going to define the combinatorial species according to the book "Theory of Species" by Bergeron, Labelle, Leroux, and present their beautiful proof of the cycle index composition theorem. The proof relies on the theory of symmetric functions in infinitely many variables. This proof is a beautiful example of Grothendieck's concept: in order to prove something particular, one should make a more general statement and prove it.

À l'instar du mouvement brownien qui apparaît comme limite d'échelle universelle de toute marche aléatoire raisonable, les disques browniens sont des espace métrique aléatoires qui apparaissent comme limite d'échelle universelle de modèles raisonables de cartes aléatoire du disque. Ces objets généralisent la carte brownienne de Miermont et Le Gall obtenue en considérent des cartes aléatoire de la sphère. Nous présenterons les disques browniens et en donneront quelques propriétés remarquables. Ce travail est en commun avec Grégory Miermont.

I am going to talk about very popular combinatorial connection between ordinary and exponential generating functions which is called cycle index function. I am going to define the combinatorial species according to the book "Theory of Species" by Bergeron, Labelle, Leroux, and present their beautiful proof of the cycle index composition theorem. The proof relies on the theory of symmetric functions in infinitely many variables. This proof is a beautiful example of Grothendieck's concept: in order to prove something particular, one should make a more general statement and prove it.

Les cartes combinatoires, étant un modèle riche, portent plusieurs aspects : algébrique, géométrique, bijective, ... Dans cet exposé, je présente un ensemble de résultats et de connexions dans le domaine de l'énumération des cartes, obtenus à travers des aspects différents. Nous verrons comment utiliser les outils algébrique, comme caractères du groupe symétrique et équations fonctionnelles, à énumérer les cartes. Nous verrons aussi comment étudier les autres objets dans la combinatoire, ici les intervalles du treillis de Tamari, à travers de l'aspect bijectif des cartes.

Polynomial systems arise in many areas of engineering sciences and computer science. Most of the time, the end-user expects some information about the real solution set of the system under study. Algorithmic problems encompass which appear frequently is to decide the existence of real solutions, compute sample points in each connected component of the set under study, compute a description of this set on some affine space or answer connectivity queries. All these problems are NP-hard and, actually the best known complexities to solve them are exponential in the number of variables. Moreover, because of the non-linearity of the considered systems, reliable issues are important. In this talk, I will give an overview of computer algebra algorithms for solving these problems with a focus on those which conciliate practical efficiency with asymptotically optimal complexity.

Considérons une triangulation de la sphère choisie aléatoirement, de manière uniforme, parmi toutes les triangulations ayant un nombre fixé de faces (deux triangulations sont identifiées si on passe de l'une à l'autre par un homéomorphisme direct de la sphère). On munit l'ensemble des sommets de cette triangulation de la distance de graphe usuelle. Nous montrons que, quand le nombre de faces tend vers l'infini, l'espace métrique ainsi obtenu, convenablement changé d'échelle, converge en loi, au sens de la distance de Gromov-Hausdorff, vers un espace métrique compact aléatoire appelé la carte brownienne. Ce résultat, qui répond à un problème posé par Schramm, reste vrai pour des classes beaucoup plus générales de graphes plongés dans la sphère. La carte brownienne apparaît ainsi comme un modèle universel de surface aléatoire, homéomorphe à la sphère mais de dimension de Hausdorff égale à 4.

We introduce an algorithm for the uniform generation of infinite runs in concurrent systems under a partial order probabilistic semantics. Using trace monoids as concurrency models, we will first focus on the notion of a uniform distribution on infinite traces in general and on the simulation of such a distribution. Then, we will introduce our algorithm, which aims at simulating a uniform distribution in a distributed context. This algorithm outputs on-the-fly approximations of a theoretical infinite run, the latter being distributed according to the exact uniform probability measure. The average size of the approximation grows linearly with the time of execution of the algorithm, and the execution of the algorithm only involves distributed computations, provided that some - costly - precomputations have been done. This presentation is based on a joint work with Samy Abbes.

Nous nous intéressons à différents modèles d'arbres aléatoires et aux marches aléatoires sur les sommets de tels arbres. Dans le cas où la marche aléatoire est transiente, la marche part presque sûrement vers l'infini en empruntant un rayon aléatoire. La loi de ce rayon est appelée la mesure harmonique sur le bord de l'arbre. Un phénomène de chute de dimension se produit : cette mesure harmonique est presque sûrement concentrée sur une partie petite (au sens de la dimension de Hausdorff) du bord de l'arbre. Autrement dit, les trajectoires de la marche aléatoires sont presque sûrement comprises dans un sous-arbre beaucoup plus fin que l'arbre original. Cette théorie a été initiée par Russel Lyons, Robin Pemantle et Yuval Peres dans les années 1990. Plus récemment, Nicolas Curien, Jean-François Le Gall, puis Shen Lin ont étudié ce phénomène sur un autre modèle d'arbres aléatoires. Nous rappellerons leurs résultats et discuteront des généralisations sur lesquelles nous avons travaillé.

Dans un travail en commun avec Pascal Hubert, nous étudions les lois limites de certains produits de matrices et en donnons une application arithmétique: On note s_2 la fonction somme des chiffres en base 2 et on considère, pour tous paramètres entiers a et d, la densité asymptotique mu_a(d) des ensembles d'entiers n tels que s_2(n+a)-s_2(n)=d. Pour tout a, mu_a est une mesure de probabilité sur Z. On démontre que pour toute mesure invariante ergodique sur {0,1}^N, et pour toute suite d'entiers (a_n) dont les décompositions en binaire décrivent les préfixes d'un point générique de cette mesure, mu_{a_n} vérifie un théorème de type limite centrée. Ce résultat est obtenu en calculant les moments de mu_{a_n} qui sont donnés par des produits de matrices aléatoires.

The hard-core gas model is a natural combinatorial problem that has played an important role in the design of new approximate counting algorithms and for understanding computational connections to statistical physics phase transitions. For a graph G = (V, E) and a fugacity t > 0, the hard-core model is defined on the set of independent sets of G where each independent set I has weight w(I) = |I|^t . The equilibrium state of the system is described by the Gibbs distribution in which each independent set I has probability ~ w(I). A long-standing open problem to establish the critical fugacity t* for the hard-core gas model on the 2-dimensional integer lattice Z^2. In particular, t* is the conjectured critical point for the phase transition between uniqueness of infinite-volume Gibbs measures on Z^2 when t < t* and non-uniqueness when t > t*. Empirical results identified the critical point t* ~ 3.79. The best known bounds show 2.538 < t* < 5.3646. In this talk the techniques to obtain these bounds will be discussed. Special emphasis will be given to the lower bound, which is based on connections between the decay of correlations on the lattice and on its self-avoiding walk tree.

The study of random algebraic objects sheds a different light on these objects, which complements the algebraic and the algorithmic points of view. When it comes to finitely generated subgroups of free groups, we have a remarkable graphical representation called the Stallings graph: the Stallings graph of a subgroup H is a finite labeled graph uniquely associated with H, efficiently computed from a set of generators of H (say, given as reduced words), and from which one can efficiently compute many invariants of H. I will discuss enumerating and randomly generating finitely generated subgroups of free groups, for the distribution given by Stallings graphs: for each positive integer n, one considers the finite number of subgroups whose Stallings graph has n vertices, and one considers the uniform distribution on that set. This requires understanding the combinatorial structure of Stallings graphs, which are interesting objects per se. I will also exhibit natural properties of subgroups which are `generic' for this distribution. This is joint work with F. Bassino (LIPN) and C. Nicaud (LIGM)

The computation of GCDs or inverse modulars is a basic operation in Arithmetic or Cryptography. The analysis and the optimisation of algorithms that compute GCDs is a speciality in Caen. In this talk, we will introduce two multiple Gcd algorithms that are natural extensions of the usual Euclid algorithm, and coincide with it for two entries. The plain (or naive) algorithm was proposed by Knuth and performs successive calls to the classical Euclid Algorithm. The Brun algorithm performs Euclidean divisions, between the largest entry and the second largest entry, and then re-orderings. This is the discrete version of a multidimensional continued fraction algorithm due to Brun. We will present the average--case analyses of the plain and the Brun algorithms. Both analyses are very similar and we will prove that the mean number of Euclidean divisions is linear with respect to the input size. However, we show that the role of the dimension is different according to the algorithm. The method relies on dynamical analysis, and is based on the study of the underlying dynamical systems.

La soutenance aura lieu le mardi 5 décembre à 12h45, en salle B017 du LIPN (Paris 13) devant le jury composé de:
Mme Fréderique Bassino,Professeur, Univ. Paris 13, directrice
M. Andrea Sportiello,Chargé de Recherche CNRS, Univ. Paris 13 co-directeur
M. Erwan Lanneau, Professeur, Univ. Grenoble AlpesRapporteur
M. Giovanni Forni, Professeur, Univ. Maryland, College Park MD, U.S.A. Rapporteur
M. Vincent Delecroix, Chargé de Recherche CNRS, Univ. de Bordeaux
M. Pascal Hubert, Professeur, Univ. d'Aix-Marseille
M. Carlos Matheus, Chargé de Recherche CNRS, Univ. Paris 13
M. Anton Zorich, Professeur, Univ. Paris Diderot

Une approche combinatoire pour les dynamiques de type Rauzy

Les dynamiques de type Rauzy sont des actions de groupes (ou de monoïde) sur une collections d'objets combinatoires. L'exemple le plus connu concerne une action sur les permutations, associée au transformations d'échanges d'intervalles (IET) pour l'application de poincaré sur les surfaces de translations orientables. Les classes d'équivalences sur les objets induites par l'action de groupe sont reliées aux composantes connexes de l'espace de module des differentiels abéliennes avec un ensemble de singularités donné, et ont été classifiées par Kontsevich et Zorich, et par Boissy, en utilisant des éléments de théorie de géométrie algébrique, de topologie, de systèmes dynamiques et de combinatoires.
Dans la première partie de cette thèse, nous donnons une preuve purement combinatoire de ces deux théorèmes de classification. Notre preuve peut être interprétée géométriquement et sa structure générale est proche de celle Kontsevich-Zorich, même si les techniques de preuves sont differentes. Néanmoins, toutes les dynamiques de type Rauzy n'ont pas forcément une correspondance géométrique, et certaines parties de la preuve ne se généralise pas bien. Dans la seconde partie, nous developpons une nouvelle méthode, que nous appelons la méthode d'étiquetage. Cette seconde méthode n'est pas complètement indépendente de la précédente mais elle introduit un nouvel ingrédient crucial: le fait de considérer une sorte de 'monodromie' pour la dynamique.
Cette seconde approche s'étend à plusieurs dynamiques de type Rauzy. Nous obtenons d'abord en appliquant la méthode d'étiquetage une preuve simple et éclairante du théorème de classification d'une dynamique de type Rauzy que nous appelons la dynamique d'involution (et dont la complexité est équivalente au problème d'isomorphisme de graphe). Ensuite nous réappliquons la méthode d'étiquetage pour déduire une seconde preuve de la classification pour la dynamiques de Rauzy. Enfin nous présentons un certain nombre de dynamiques pour lesquelles la méthode d'étiquetage peut être utilisée.

La fonction s_b(n) est égale à la somme des chiffres qui composent la représentation de l'entier n en base b. De nombreuses séries associées à cette séquence ont été calculées, par exemple dans J.P. Allouche, J. Shallit, Sums of digits and the Hurwitz Zeta function, Analytic Number Theory pp. 19-30, LNM 1434. On présentera de nouvelles séries génératrices associées à la suite s_b(n), ainsi que certains produits infinis. L'obtention de ces résultats utilise des outils rencontrés dans le domaine du calcul symbolique et de la théorie des probabilités. Ce travail a été realisé en collaboration avec T. Wakhare.

We prove an explicit formula for the polynomial part of a restricted partition function, also known as the first Sylvester wave. This is achieved by way of some identities for higher-order Bernoulli polynomials, one of which is analogous to Raabe's well-known multiplication formula for the ordinary Bernoulli polynomials. As a consequence of our main result we obtain an asymptotic expression of the first Sylvester wave as the coefficients of the restricted partition grow arbitrarily large. (Joint work with Christophe Vignat).

Quand on cherche à caractériser les formes convexes pouvant paver le plan (en s’autorisant les rotations et miroirs), seul le cas des pentagones restait ouvert. De 1918 à 2015, 15 différents types de pentagones pouvant paver le plan ont été découverts. Je présente une recherche exhaustive de tous les pentagones convexes pavant le plan, qui permet de clore cette question. La preuve se sépare en deux parties: la première montre, en utilisant la compacité, qu'on peut se limiter à un ensemble de 371 familles, et la seconde est une recherche exhaustive informatisée, pour chacune des 371 familles, qui ne trouve aucun nouveau type de pentagones que les 15 types connus.

Les invariants unitaires, ou contractions de tenseurs covariants et contravariants, sont en bijection avec les graphes bi-partites colorés. Ces objets trouvent leur intérêt dans l'étude des cartes combinatoires en dimension supérieure à deux. Je présenterai une autre connexion que peut avoir le comptage de ces invariants avec la théorie de la représentation des groupes symétriques. En particulier, je démontre que le nombre d'invariants de tenseurs de rang 3 est une somme de carrés de coefficients de Kronecker. Ceci établit probablement un lien avec la théorie de la complexité. D'autre part, en passant par l'algèbre du groupe symétrique, ces invariants peuvent être munis d'une structure algébrique. Nous discutons les conséquences de l'existence d'une telle algèbre.

In this talk, I will show tools and sketch proofs about Noncommutative Evolution Equations (in particular, preparing Hoang Ngoc Minh's talk about associators). Starting from the very simple setting of Noncommutative Formal Power Series with variable coefficients, we can explore in a compact and effective (in the sense of computability) way the Hausdorff group of Lie exponentials in particular the one linked to Hyperlogarithms (and then Polylogarithms) and show some multiplicative renormalisations (as those of Drinfeld). Some parts of this work are connected with Dyson series and take place within the project "Evolution Equations in Combinatorics and Physics".

On s'intéresse à deux problèmes d'énumération bijective, qui présentent une structure très similaire. Le premier, énoncé par Bousquet-Mélou et Mishna en 2010, a été réduit par Elizalde en 2014 à trouver une bijection entre les chemins sous-diagonaux de longueur paire utilisant des pas N,S,E,O finissant sur l'axe, et les excursions dans le quart de plan utilisant les mêmes pas. Le deuxième, énoncé en 2015 par Burrill et al., consiste à montrer bijectivement que les diagrammes de partition ouverts sans 3-croisement étendu sont énumérés par les nombres de Baxter. Il se ramène au problème précédent en utilisant cette fois les pas N,S,E,O,NO,NS,EO,ES. La similarité de ces deux problèmes nous amène à emprunter une démarche commune qui consiste à retirer les arcs ouverts de la représentation par diagrammes définie par Chen et al. en 2005, pour se ramener à des excursions sous-diagonales marquées. Au cours de la résolution de ces problèmes, on utilisera les forêts de Schnyder pour démontrer la symétrie de certaines statistiques, une méthode dont on verra qu'elle est en fait plus générale et permet dans plusieurs cas d'obtenir des symétries intéressantes.

Aperiodic tilings serve as a mathematical model for quasicrystals, such crystals that do not have any translational symmetry. Question about how quasicrystals grow still remains open. In this talk I will present the algorithm for growing defect free Penrose tilings using local rules based on paper “Growth rules for quasicrystals” by Joshua Socolar. And state necessary conditions for deterministic growth of cut-and-project aperiodic tilings using “defective seeds".

Dans cet exposé, je me propose de résumer les travaux que j'ai effectués pendant ma thèse sur les groupes d'automate. Tout d'abord, j'expliquerai comment les automates de Mealy (une classe spéciale de transducteurs) peuvent engendrer des (semi-)groupes et pourquoi ces (semi-)groupes ont été intensément étudiés depuis les années 80. Je parlerai ensuite brièvement de trois de mes travaux, en commençant par la génération aléatoire de groupes finis, puis en parlant de la dynamique de l'action du groupe et enfin en étudiant le lien entre certaines propriétés structurelles de l'automate et les caractéristiques du groupe qu'il engendre. Dans tous ces exemples, j'espère réussir à souligner comment l'utilisation conjointe d'outils venant d'informatique théorique, de combinatoire et de théorie des groupes permet une meilleure compréhension du sujet et l'obtention de nouveaux résultats. Je terminerai en posant deux problèmes combinatoires qui pourraient intéresser les membres de l'assistance.

Après avoir introduit ce que sont les quasicristaux, j'expliquai deux façons d'en construire : avec une description substitutive, et par coupé-projection. Le but de cet exposé sera de faire un lien entre ces deux constructions en se restreignant au cas d'un quasicristal de dimension 1 pour simplifier l'exposé. Plus précisément, étant donné une substitution associée à un nombre de Pisot, j'expliquai comment décider si le pavage autosimilaire correspondant peut aussi être décrit par un coupé-projeté régulier.

Les triangulations colorées sont des espaces discrets formés par collage de briques élémentaires qui sont elles-mêmes formées de simplexes en dimension d. Ces briques élémentaires sont par exemple des polygones en dimension 2 et incluent les octaèdres en dimension 3. Les triangulations colorées visent ainsi le développement d'une nouvelle théorie qui intègrerait les cartes combinatoires, spécifiques à la dimension 2, dans un cadre théorique en dimension arbitraire. Je présenterai ces objets en expliquant qu'ils peuvent être représentés par des graphes aux arêtes colorées. Cela les rend particulièrement propices à l'analyse combinatoire, dans le but de les classifier combinatoirement à la manière du genre en dimension 2 et de les énumérer. Je définirai une notion généralisant la planarité en dimension supérieure et je présenterai un système d'équations portant sur les fonctions génératrices de triangulations colorées, qui généralise les équations de Tutte/Schwinger-Dyson des cartes. Selon le temps restant et les gouts de l'auditoire, je pourrai présenter des résultats soit en dimension 3 lorsque les briques élémentaires sont homéomorphes à des boules, soit en dimension 4 où il existe des régimes dans les classes d'universalité des arbres, des cartes planaires et des arbres de cartes mélangeant les deux.

In queuing theory, it is usual to have some models with a "reset" of the queue. In terms of lattice paths or random walks, it is like having the possibility of jumping from any altitude to zero. These objects have the interesting feature that they do not have the same intuitive probabilistic behaviour as classical Dyck paths (the typical properties of which are strongly related to Brownian motion theory). In this talk we will quantify some relations between these two types of paths. Starting from an a priori not expected continued fraction (for which we give a bijective proof, and an analytic proof), we prove several formulae for related combinatorial structures conjectured in the On-line Encyclopedia of Integer Sequences. We also derive limit laws for parameters like the number of returns to zero or the size of an average catastrophe. We end with some considerations on uniform random generation. [Joint work with Cyril Banderier]

Nous nous intéressons aux structures mathématiques sous-jacentes des programmes concurrents et parallèles. L'idée est de modéliser des programmes concurrents à l'aide d'abres étiquettés croissants. Nous pouvons ensuite réaliser une étude combinatoire sur ces structures, en déduire certaines propriétés et faire une génération aléatoire uniforme de programmes concurrents qui peut servir dans le cadre du model-checking.

Nous nous intéresserons d'abord au comportement asymptotique du nombre de variables libres des lambda-termes linéaires uniformément générés. Nous discuterons ensuite de la génération aléatoire de lambda-termes linéaires clos via l'utilisation d'un GPU.

Le diamètre des polyèdres est une borne théorique sur la complexité de l'algorithme du simplexe. Pour cette raison, il est habituellement estimé en fonction de la dimension d du polyèdre et du nombre n de ses facettes. Dans le cas des polytopes en nombres entiers contenus dans l'hypercube [0,k]^d, un autre jeu de paramètres qui a du sens est la taille k de l'hypercube cube et sa dimension d. Cet exposé présente des résultats récents sur le plus grand diamètre δ(d,k) de tels polytopes. Plusieurs de ces résultats seront présentés et discutés. Ces résultats seront mis en perspective avec la conjecture de Hirsch (maintenant infirmée) et avec des travaux de Thiele, Balog et Bàràny et Acketa et Žunic sur les polygones en nombres entiers contenus dans le carré [0,k]².

In our overview talk, we present a quantitative analysis of lambda calculus and combinatory logic under various combinator bases, focusing on the asymptotic properties of both computational models, such as normalisation or typeability. We discuss utilised analytic methods, their limitations and current challenges. Finally, we discuss effective random sampling techniques, in particular Boltzmann models, and their application in automated software verification tools.

Un méandre est une configuration d'intersections de deux courbes sur la sphère. Leur comptage résiste depuis longtemps à l'assaut des physiciens théoriciens, des informaticiens et des mathématiciens. Nous savons depuis longtemps qu'il existe un exposant de croissance exponentielle (pour des raisons de sous-additivité) mais pas beaucoup plus... Dans cet exposé, je présenterai comment obtenir des asymptotiques de comptage de méandres lorsqu'on contraint la combinatoire. Dans les cas que nous considérons, l'asymptotique est polynomiale et non plus exponentielle. Ces résultats nouveaux obtenus par des méthodes de théorie ergodique n'éclairent pas, à priori, le problème du comptage non contraint. (travail en commun avec E. Goujard, A. Zorich et P. Zograf)

Les opérades colorées permettent de généraliser la notion de grammaire non contextuelle de façon à décrire des familles d'objets combinatoires variées (dont les arbres, englobant de ce fait les grammaires d'arbres régulières). Nous allons introduire ces grammaires, appelées grammaires à bourgeons, et expliquer comment il est possible de considérer des séries formelles sur les opérades colorées. Ce dernier point offre des outils pour le dénombrement. Dans ce contexte, nous introduisons plusieurs produits sur l'espace de ces séries : un produit pré-Lie, un produit de composition associatif et deux analogues de l'étoile de Kleene.

Nous proposons une construction fonctorielle de la catégorie des magmas unitaires vers celle des opérades non symétriques. Cette construction munit l'espace des configurations de diagonales décorées dans les polygones d'une structure d'opérade. On obtient ainsi diverses nouvelles opérades sur des sous-familles particulières de tels polygones : configurations sans croisement, configurations non imbriquées, configurations de Motzkin, etc. Nous montrons aussi comment cette construction permet de donner des définitions alternatives d'opérades déjà connues comme l'opérade des simples et doubles multi-tiles (provenant de la théorie des langages) et l'opérade de gravité.

The polylogarithm map Li can be extended partly to some series. In this talk, we examine the algebra generated by the image of Li of a particular family of series that we call "Star of the plane". We discuss the basis of the algebra as a module and the characters of this algebra. We also prove the linear independence of the usual polylogarithms over this algebra.

L'étude des intégrales de fonctions algébriques est très fructueuse en géométrie algébrique, comme l'illustre, par exemple, les travaux d'Euler sur les intégrales elliptiques. Les applications aux calculs effectifs sont moins connues. J'en présenterai quelques unes. Plus précisément, je vais m'intéresser aux « périodes », c'est le résultat de l'intégration sur un cycle d'une fractions rationnelle en plusieurs variables. Je montrerai comment les calculer, sous la forme d'équations différentielles, et j'expliquerai deux applications à des problèmes bien différents : la démonstrations automatiques d'identités entre sommes binomiales et le calcul du volume de certains ensembles semi-algébriques (i.e., définis par un ensemble d'inégalités polynomiales).

This talk concerns the resolution of $KZ_3$ and our recent results on combinatorial aspects of zeta functions, $\{\zeta(s_1,\ldots,s_r)\}_{s_1,\ldots,s_r\in{\mathbb C}^r}$. In particular, we describe the action of the differential Galois group of $KZ_3$ on the asymptotic expansions of its solutions leading to a group of associators which contains the associator $\Phi_{KZ}$. Non trivial expressions of an associator with rational coefficients is also explicitly provided, based on the algebraic structures and the singularity analysis of the polylogarithms, $\{{\rm Li}_{s_1,\ldots,s_r}\}_{s_1,\ldots,s_r\in{\mathbb C}^r}$, and the harmonic sums, $\{H_{s_1,\ldots,s_r}\}_{s_1,\ldots,s_r\in{\mathbb C}^r}$.

Les machines à signaux sont un modèle de calcul déterministe dont espace et temps sont continus.

Si les accumulations d'événements sont interdites, ce modèle est connu pour être équivalent au modèle de BlumShubSmale linéaire. Nous construirons dans ce cadre un oracle universel optimal (en nombre de vitesses et de paramètres irrationnels). Nous verrons comment jouer au billard permet semi-décider l'algébricité d'un nombre réel alors que c'est impossible dans le modèle BSS-linéaire. Nous verrons comment modifier légèrement le modèle pour obtenir un modèle équivalent au modèle BSS standard.

Lorsque l'on permet aux accumulations d'événements de produire un signal, nous verrons, en jouant sur l'alternance discret/continu, comment construire des machines dont le pouvoir dépasse largement les modèles de calcul usuels, en particulier, nous construirons

• une "courbe de Peano" c'est a dire une surjection de [0,1] dans [0,1]^2.
• un "oracle universel continu", c'est à dire un machine à un paramètre M(p) telle que toute suite N->[0,1] est generèe un certain M(p).
• une "fonction analytique universelle", c'est à dire une machine avec 2 parametres t,x telle que pour toute fonction analytique f de rayon de convergence >1, il existe t tel que f(x)=M(t,x) pour tout x dans [-1,1], en particulier, on peut calculer les fonctions exp(x), sin(), en déplaçant un curseur.
• aussi, on peut prendre en compte la géométrie du modèle dans la formulation même de ce que peut "calculer" (ou "dessiner") une machine, pas seulement un booléen, un entier ou un réel comme dans le cas discret. Étant donnée une machine M, si certains types de collisions sont coloriés en rouge, l'ensemble de leurs accumulations au temps 1 est un compact. Il se trouve que cette restriction est la seule : il existe une machine à un parametre M(p) telle que pour tout compact K inclus dans [0,1], il existe p dans [0,1] tel que l'ensemble des accumulations rouges de M(p) au temps 1 est K.

L'exposé sera informel et sa compréhension ne nécessitera pas de prérequis.

This talk concerns the resolution of $KZ_3$ and our recent results on combinatorial aspects of zeta functions, $\{\zeta(s_1,\ldots,s_r)\}_{s_1,\ldots,s_r\in{\mathbb C}^r}$. In particular, we describe the action of the differential Galois group of $KZ_3$ on the asymptotic expansions of its solutions leading to a group of associators which contains the associator $\Phi_{KZ}$. Non trivial expressions of an associator with rational coefficients is also explicitly provided, based on the algebraic structures and the singularity analysis of the polylogarithms, $\{{\rm Li}_{s_1,\ldots,s_r}\}_{s_1,\ldots,s_r\in{\mathbb C}^r}$, and the harmonic sums, $\{H_{s_1,\ldots,s_r}\}_{s_1,\ldots,s_r\in{\mathbb C}^r}$.

Les marches aléatoires 2D, composés d'un ensemble fini de pas élémentaires et restreintes au quadrant positif, forment des classes combinatoires dotées de structures typiquement complexes, et admettant une grande variété de comportements asymptotiques. En collaboration avec Jérémie Lumbroso (Princeton, USA) et Marni Mishna (SFU, Canada), nous nous intéressons à la génération aléatoire uniforme de marches d'une taille n donnée, à partir de l'ensemble des pas élémentaires. Notre principal résultat consiste en un algorithme de rejet, qui remplace le quart de plan par un demi-plan bien choisi. On se ramène alors à la génération aléatoire de marches 1D composées de pas généralement irrationnels, et pour lesquels une génération uniforme est possible en temps polynomial à partir d'une famille de grammaires non-contextuelles. Un résultat de Garbit et Raschel démontre ensuite l'existence d'un demi-plan tel que l'espérance du nombre de tirages dans le demi-plan est polynomiale, mais une analyse plus fine de la complexité de cette approche soulève des questions en combinatoire (analytique) des marches 1D/2D et des spécifications algébriques. Cette présentation consiste en une version étendue d'un exposé présenté à GASCOM 2016.

I will give an overview and report on the latest results of the so-called rule algebraic approach to stochastic rewriting systems [1,2]. Besides a general (high-level) introduction to the mathematical concepts, the focus of the talk will be on the practical implications in terms of efficiently analyzing rewriting systems. In particular, I will compare the traditional approaches to analyzing chemical reaction systems (aka discrete graph rewriting systems) to analytically tractable cases of stochastic graph rewriting systems, such as the preferential attachment model. Amongst the novel results, the combinatorial conversion and disassociator dynamics theorems introduced in detail in the morning session will be mentioned, as well as perspectives in terms of restricted rewriting systems.
[1] N. Behr, V. Danos and I. Garnier, Stochastic mechanics of graph rewriting, In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 46-55. ACM, 2016.
[2] N. Behr, V. Danos, I. Garnier and T. Heindel, The algebras of graph rewriting, arXiv preprint arXiv:1612.06240 (2016).

L'étude des marches dans le quart de plan a fait ces dernières années l'objet de nombreuses avancées, aussi bien par des méthodes de combinatoire, de théorie des probabilités, de théorie du potentiel, de calcul formel... Il reste de nombreux problèmes ouverts, comme notamment mieux comprendre pourquoi certaines marches sont dénombrées par des séries génératrices algébriques, d'autres par des séries D-finies (holonomes), tandis que d'autres (a priori très "proches") aboutissent à des séries non différentiellement algébriques. Nous montrerons comment la théorie de Galois (et notamment ses variantes pour des équations aux différences), ainsi que des éléments d'analyse complexe (paramétrisation de courbes par fonctions elliptiques) nous a permis d'avancer sur ces questions. [travail joint avec Michael Singer, Julien Roques, Charlotte Hardouin]

Maple possède plusieurs milliers de fonctions, mais certains calculs spécifiques peuvent nécessiter l'utilisation de bibliothèques externes. Par ailleurs, les ordinateurs n'évoluent plus tellement dans le sens d'une augmentation de la fréquence des processeurs mais dans le sens d'une augmentation du nombre de cœurs de calcul. Cette présentation détaillera les fonctionnalités de Maple permettant de réaliser des calculs parallèles et de s'interfacer avec du code écrit dans d'autres langages.

Repetitive patterns in genomic sequences have a great biological significance and also algorithmic implications. Analytic combinatorics allow to derive formula for the expected length of repetitions in a random sequence. Asymptotic results, that generalize previous works on a binary alphabet, are easily computable. Simulations on random sequences show their accuracy. As an application, the sample case of Archaea genomes illustrates how biological sequences may differ from random sequences.

We show that by restricting the degrees of the vertices of a graph to an arbitrary set Δ, the threshold α(Δ) of the phase transition for a random graph with n vertices and m = α(Δ).n edges can be either accelerated (e.g., α(Δ) approx 0.38 for Δ = {0,1,4,5}) or postponed (e.g., α(Δ) approx 0.95 for Δ={1,2,50}) compared to a classical Erdős–Rényi random graph where α(N)=1/2. We investigate different graph statistics inside the critical window of transition (planarity, diameter, longest path...). We apply our results to a 2-SAT model with restricted literal degrees: the number of clauses that each literal is incident to belongs to the set Δ. We prove a lower bound for the probability that a formula with n variables and m=2.α(Δ) n clauses is satisfiable. This probability is close to 1 for the subcritical regime m=2.α.n.(1-μ.n^-1/3), μ to ∞ and improves/generalizes the lower bound of Bollobás, Borgs, Chayes, Kim, and Wilson. This shows how the phase transition threshold for 2-SAT moves if we change the degrees of the literals. Joint work with Vlady Ravelomanana.

Un hypergraphe à n sommets dont aucune projection sur k sommet n'est complète a au plus O(n^{k-1}) arêtes. Ce résultat, découvert simultanément par Sauer, Vapnick-Chervonenkis et Perles-Shelah au début des années 1970, est fondamental en apprentissage. En géométrie combinatoire et algorithmique, il permet souvent de contrôler la complexité (globale) d'une structure par sa "densité" locale. J'introduirai à ce mécanisme avant de présenter quelques extensions récentes, obtenues conjointement avec Boris Bukh (https://arxiv.org/abs/1701.06632), qui permettent un controle plus fin de la complexité. L'exposé ne supposera aucune connaissance préalable et un des ingrédients sera une construction probabiliste.

Baxter numbers are a well known number sequence enumerating Baxter permutations and several other combinatorial objects. In this talk, we define a new class of objects called Slicings of parallelogram polyominoes counted by Baxter numbers that enables us to find a continuum from Catalan structures to Baxter structures. This continuum is established by means of a new succession rule (i.e. generating tree) associated with Schröder numbers, that interpolates between the known succession rules for Baxter and Catalan numbers. Then, similarly we consider a generalization for the Baxter succession rule that forms a link between Baxter numbers and Factorial numbers. Such succession rule defines semi-Baxter numbers, which result to count plane permutations, whose enumeration was set as an open problem by Bousquet-Mélou and Butler, and inversion sequences avoiding (210,100), as conjectured by Martinez and Savage.

Tirer une permutation aléatoire uniforme de taille n n'est pas bien difficile, et on sait assez bien à quoi c'est censé ressembler. Qu'en est-il si on souhaite imposer des restrictions sur le type cyclique? Il n'est pas bien difficile non plus de tirer une permutation aléatoire ayant un nombre prédéterminé de points fixes - il suffit de savoir tirer un dérangement, et à grande taille, près de 37% des permutations sont des dérangements. On a donc facilement un algorithme qui va nécessiter en moyenne O(n) tirages d'entiers aléatoires d'ordre O(n). Dans ce travail en commun avec Romaric Duvignau (EJC, 2016), nous montrons comment cela peut être fait avec n+O(1) tirages en moyenne, par un rejet anticipé. Cela est possible grâce à la construction d'un arbre de génération pour les permutations, qui a la particularité de "fixer" très rapidement, et aussi vite qu'il est possible, le nombre de points fixes. Comme conséquences faciles, on a alors des algorithmes tout aussi efficaces pour tirer des permutations aléatoires avec un nombre prescrit de points fixes. Le passage de "points fixes" à "cycles d'une longueur k donnée" est possible, mais sensiblement moins élégant.

In this PhD thesis are studied the polylogarithms and the harmonic sums at non-positive (i.e., weakly negative) multi-indices. General results about these objects in relation with Hopf algebras are pr ovided. The technics exploited here are based on the combinatorics of noncommmutative generating series relative to the Hopf phi-huffle algebra. Our work will also propose a global process to renormalize divergent polyzetas. Finally, we will apply these ideas to non-linear dynamical systems with singular inputs.

The jury will be composed of: Gérard Duchamp, Hoang Ngoc Minh (directeurs), Sylvie Paycha, Dominique Manchon (rapporteurs), Karol Penson, Vincent Rivasseau, Loic Foissy, Christophe Tollu.

En abordant les nombres spéciaux comme les sommes harmoniques ou les polyzêtas sous leur aspect combinatoire, nous introduisons d'abord la définition d'un produit entre mots, dit produit de quasi-mélange q-déformé, une généralisation des produits de mélange et de quasi-mélange, ce qui nous permet de construire des structures complètes d'algèbre de Hopf en dualité. En même temps, nous construisons des bases en dualité, contenant des bases de transcendance associées aux mots de Lyndon, et des formules explicites sur lesquelles les sommes harmoniques, les polyzêtas ou les polylogarithmes sont indexés et représentés par la factorisation de la série génératrice noncommutative diagonale. De cette façon, en identifiant les coordonnées locales, nous trouvons des relations polynomiales homogènes, en poids, entre les polyzêtas indexés par ces bases. Enfin, nous déterminons les développements asymptotiques des sommes harmoniques, indexées aussi par ces bases, grâce à leur série génératrice et à la formule d'Euler Maclaurin. Pour accompagner cette étude théorique, nous proposons des algorithmes et un package en Maple afin de calculer des bases, la structure des polyzêtas et des développements asymptotiques des sommes harmoniques.

Le jury sera composé de Gérard Duchamp, Hoang Ngoc Minh, (co-directeurs), Jacky Cressson, Loïc Foissy, (rapporteurs), Sylvie Paycha, Joris van der Hoeven, Daniel Barsky, Christophe Tollu (examinateurs).

We will discuss the complexity of one of the most basic problems in pattern matching, that of approximating the Hamming distance. Given a pattern P of length n the task is to output an approximation of the Hamming distance (that is, the number of mismatches) between P and every n-length substring of a longer text. We provide the first efficient one-way randomised communication protocols as well as a new, fast and space efficient streaming algorithm for this problem.

B0;136;0cDans cette thèse nous étudions deux types de pavages : des pavages par une paire de carrés et des pavages sur le réseau tri-hexagonal (Kagome). Nous considérons différents problèmes combinatoires et probabilistes. Nous commençons par le cas des carrés 1 × 1 et 2 × 2 sur des bandes infinies de hauteur k et obtenons des résultats sur la proportion moyenne des carrés 1 × 1 pour les cas planaire et cylindrique pour k ≤ 10. Nous considérons également des questions d’échantillonnage et comptage approximatif. Pour obtenir un échantillon aléatoire nous définissons des chaînes de Markov pour les pavages par des carrés et sur le réseau Kagome. Nous montrons des bornes polynomiales pour le temps de mélange pour les pavages par des carrés 1 × 1 et s × s des régions n × log n et les pavages Kagome des régions en forme de losange. Nous considérons aussi des chaines de Markov avec des poids λ sur les tuiles. Nous montrons le mélange rapide avec des conditions spécifiques sur λ pour les pavages par des carrés 1 × 1 et s × s et pavages Kagome. Nous présentons des simulations qui suggèrent plusieurs conjectures, notamment l’existence des région gel´ees pour les pavages aléatoires par des carrés et sur le réseau Kagome des régions avec des bords non plats.

Le jury se composera de Thomas Fernique (directeur), Béatrice de Tilière, Éric Rémila (rapporteurs), et de Frédérique Bassino, Olivier Bodini, Ana Bušić, Pavel Kalouguine.

Dans cet exposé, nous montrerons comment des techniques élémentaires (transformées de Mellin) en combinatoire analytique permettent d'obtenir des résultats assez surprenants sur les polyominos. En particulier, si l'on savait correctement énumérer les polyominos digitalement convexes, nous saurions si l'hypothèse de Riemann est vraie !

Un sous shift est un ensemble fermé de suites sur un alphabet fini, invariant par décalage (le shift). L'ensemble des automates cellulaires préservant ce sous shift est en général un groupe dénombrable compliqué. Nous présenterons dans cet exposé un survol des différentes restrictions sur ces groupes pour les sous-shift d'entropie nulle.

In this talk, we consider linear differential systems of first order (equivalently linear differential equations of arbitrary order), and we question whether they can be solved in terms of generalized hypergeometric functions. This question is motivated by the many properties of the latter which arise in physics and combinatorics. It has been tackled in the literature for second-order differential equations, namely Bessel's, Whittaker's, Kummer's, and Gauss's. We propose a new algorithm which surpasses the restrictions on the dimension of the system, and equivalently on the order of the equation. This is joint work with Frédéric Chyzak.

Soient 2n points en position convexe alternativement colorés rouges et bleus, et soit D une dissection de l'enveloppe convexe des points rouges. Une diagonale entre deux points bleus est un D-accordéon si les arêtes de D qu'elle croise forment un accordéon. Le complexe d'accordéons de D est le complexe simplicial formé des ensembles de D-accordéons qui ne se croisent pas. Par exemple, le complexe d'accordéons d'une triangulation est un associaèdre, et celui d'une quadrangulation a été étudié par Baryshnikov et Chapoton. Ces complexes ont été introduits récemment par Garver et McConville dans un langage dual. Dans cet exposé, nous donnerons des réalisations géométriques de ces complexes simpliciaux, basées sur de fortes analogies avec les algèbres amassées de type fini. Lorsque D est une triangulation ayant des triangles internes, nous obtenons en particulier de nouvelles réalisations de l'associaèdre. Cet exposé est basé sur des travaux en commun avec Christophe Hohlweg (UQAM, Montréal), Thibault Manneville (LIX, École Polytechnique) et Salvatore Stella (Univ. la Sapienza, Rome).

We consider tilings of a rectangle with squares tiles of size 1x1 and 2x2. We present a method to calculate the number of such tilings via matrix multiplication, where we optimize the number of multiplication needed and reduce the space required for the matrix multiplication by dynamically generate the matrices involved.

On prendra appui sur les intégrales itérées des systèmes fuschsiens pour proposer une théorie des équations différentielles non-commutatives. Plusieurs surprises et cadeaux nous attendent dans cette exploration.

On étudie en combinatoire les objets munis d'une taille (la taille dans le cadre informatique peut se traduire par exemple par la mémoire occupée par l'objet). On appelle classe combinatoire un ensemble d'objets qui pour toute taille possède un nombre fini d'éléments. On peut par exemple considérer les textes régis par une certaine grammaire, dans ce cas la taille est le nombre de caractères, ou des arbres avec comme taille le nombre de nœuds. Une méthode naturelle pour décrire les classes, la méthode symbolique, consiste à décomposer les objets en sous-objets plus élémentaires à l'aide d'opérateurs (tels que l'union disjointe, le produit cartésien,...). On peut ensuite traduire ces décompositions sur des séries formelles. Le premier volet de résultats présentés dans cette thèse traite de la méthode symbolique et de son utilisation. On y présente des résultats asymptotiques sur des modèles d'arbres croissants issus de la théorie de la concurrence, puis une discussion sur comment décomposer certains opérateurs en réplications élémentaires. Le deuxième volet de résultats s'intéresse au sujet de la génération aléatoire uniforme d'objets dans une classe donnée. On montre tout d'abord comment générer des structures croissantes en adaptant les méthodes de génération récursive classiques aux opérateurs de produit croissant. On présente ensuite des résultats sur la génération de Boltzmann, avec une comparaison quantitative de deux méthodes, puis une extension permettant de conserver les propriétés d'uniformité de la génération en utilisant des approximations.

Je présenterai une implémentation en développement d'algorithmes d'évaluation numérique de fonctions D-finies (c.-à-d. solutions d'équations différentielles linéaires à coefficients polynomiaux), pour le logiciel de calcul formel libre SageMath. Ce nouveau package a vocation à remplacer NumGfun, un package un peu similaire pour Maple que j'ai présenté au séminaire CALIN il y a quelques années. Si le temps le permet, je dirai aussi quelques mots des algorithmes originaux utilisés. La fonctionnalité centrale de ce code est le « prolongement analytique numérique » d'une fonction D-finie, qui fournit une approximation de la matrice envoyant un jeu de conditions initiales en un point donné du plan complexe sur les conditions « initiales » qui définissent la même fonction au voisinage d'un autre point. Le prolongement analytique numérique permet de calculer des valeurs ou encore des approximations polynomiales de fonctions D-finies n'importe où sur leur surface de Riemann, des matrices de monodromie d'opérateurs différentiels, etc. Le code traite complètement le cas limite important de conditions initiales généralisées données en un point singulier régulier de l'opérateur. Il peut donc être utilisé pour calculer des matrices de connexion entre singularités régulières, ce qui est utile notamment en combinatoire analytique. Par ailleurs, il s'agit d'une implémentation rigoureuse, au sens où elle renvoie des intervalles qui (sauf bug !) contiennent à coup sûr le résultat mathématique exact.

Growth-fragmentation processes describe the evolution of particles that grow and divide as time proceeds. Previous studies on growth-fragmentations have mostly focused on the self-similar case. In this talk we introduce a new class of growth-fragmentations, called Ornstein- Uhlenbeck type growth-fragmentations. Loosely speaking, the size of each fragment evolves according to the exponential of a Lévy driven Ornstein-Uhlenbeck type process. This model is partly motivated by the work of Bertoin and Baur (EJP. 2015) which shows that such processes arise naturally in dynamical percolation on an infinite random recursive tree.

Colored tensor models generate Feynman graphs representing discrete geometries. They form as an interesting approach of quantum gravity where discrete geometries represent quanta of spacetime. The coloring in tensor models improves a lot the topology type of these discrete structures and this helps a lot in their understanding. In my presentation, I will review (in a pedestrian way) their construction and then list basic properties of their observables. Recalling that an observable simply means in this context a convolution or contraction of tensors, observables of colored tensor models map to bi-partite colored graphs. A first question that one can address is can we enumerate these observables? I will explain how such an enumeration is possible and how it has lead us to an intriguing bijection with the counting of branched covers of the 2-sphere.

Les shuffles (battages) jouent un rôle important dans la compréhension du produit d'ensembles simpliciaux, qui intervient à de nombreux endroits en topologie algébrique. Récemment, une généralisation des ensembles simpliciaux a été introduite : les ensembles dendroidaux (on remplace les {0,1,...,p} (avec leur ordre total) par des arbres (avec leur ordre partiel)). La catégorie des ensembles dendroidaux est également munie d'un produit, où interviennent des shuffles d'arbres. Dans cet exposé, après une brève motivation topologique, j'introduirai cette notion de shuffles d'arbres, en donnant plusieurs définitions équivalentes et de nombreux exemples. Je présenterai ensuite quelques propriétés algébriques et combinatoires de ces shuffles. Mon exposé est basé sur un travail en commun avec Ieke Moerdijk.

L'alignement d'arbres est la généralisation naturelle de la notion classique d'alignement de séquences. Elle est utilisée dans de nombreux domaines, y compris pour la comparaison de structures secondaires d'ARN (ce qui nous intéressera aujourd'hui). Nous allons donc comprendre comment explorer l'espace des alignements d'arbres et comment déduire des algorithmes efficaces pour comparer les ARN. Cet exposé introduit ainsi les notions d'alignement de séquences et d'arbres et décrit le problème d'ambiguïté qui point quand nous voulons générer de manière correcte les alignements d'arbres. Pour résoudre ce problème d'ambiguïté dans le contexte des alignements d'arbres, nous donnons un schéma de décomposition sous la forme de grammaire sans contexte. Cela conduit à de nombreux résultats : propriétés statistiques sur les larges structures d'ARN, algorithmes efficaces d'échantillonnage... Ces travaux, en collaboration avec Cédric Chauve et Yann Ponty, illustrent le fait que la combinatoire peut être un puissant couteau suisse pour traiter des problèmes algorithmiques qui apparaissent dans de nombreux champs appliqués.

On the one hand, asymptotic expansions of harmonic sums are constructed by following the Euler-Maclaurin formula. On the other hand, due to relations among polylogarithms, polyzetas, harmonic sums and their generating series, which are the Lie exponentials in the shuffle and quasi shuffle algebras, we will show structure of polylogarithms and polyzetas. From this, asymptotic expansions of harmonic sums will also establish by following generating series.

We enumerate the connected graphs that contain a linear number of edges with respect to the number of vertices. So far, only first term of the asymptotics and a bound on the error were known (Bender Canfield McKay 1995, Pittel Wormald 2005, van der Hofstad Spencer 2006). We present a proof based on analytic combinatorics, i.e. generating function manipulations, and derive the complete asymptotic expansion.

The U-polynomial of a graph was introduced by Noble and Welsh as a generalization of some invariants coming from Knot theory. It also generalizes the chromatic symmetric function of Stanley. In this talk, we will consider the problem of whether there exist non-isomorphic trees with the same U-polynomial (or,equivalently, with the same chromatic symmetric function). We will survey what is know about the U-polynomial and this problem. In particular, we will show how to recover some classic invariants from the U-polynomial and we exhibit several subclasses of trees for which a solution of this problem is known. FInally, we construct some non-isomorphic trees with "almost" the same U-polynomial, based on solutions of an old problem in Number theory due to Prouhet-Tarry-Escott.

We consider the family of rooted planar maps where the vertex degrees belong to a (possibly infinite) set of positive integers. Using a classical bijection with mobiles and some refined analytic tools to deal with the systems of equations that arise, we first recover the universal asymptotic behaviour of planar maps. Furthermore we establish that the expected number of vertices of a given degree satisfies a multi-dimensional central limit theorem. We also discuss some possible extension to maps of higher genus.

In this talk, we start from two sources [i) The poly- and hyper-logarithms ii) the classic Dyson series] in order to develop the theory of noncommutative differential equations, giving a touch of Lie-theoretic insights to understand the interplay between orbits and coordinates which are - following Gelfand's paradigm - special functions. The talk(s) will be illustrated with concrete examples and explicit computations.

The lattice of noncrossing set partitions of an n-set can be seen as a subgraph of the Cayley graph of the symmetric group S generated by all transpositions. We mimic this construction for the alternating group A_2n+1 generated by all 3-cycles. The resulting poset provides a rich new source of combinatorics coming from the alternating groups, which in some sense parallels the combinatorics behind the noncrossing set partitions. We present some enumerative and bijective results, and suggest an extension of this construction to all finite Coxeter groups. This is joint work with Philippe Nadeau.

Dans cet exposé je présenterai des résultats dans l' intersection de la géométrie Riemannienne et la topologie algorithmique. Plus précisément, je discuterai des manières effectives de planariser une surface triangulée, des problèmes de nombre de croisements, et de la "meilleure" métrique Riemannienne pour une surface. Si le temps le permet, je parlerai également des défis en haute dimension et des connections avec les nombres de faces des complexes simpliciaux.

We use a linear algebra point of view to describe the derivatives and higher order derivatives over F_2^n. On one hand, this new approach ennobles us to prove several properties of these functions, as well as the functions that have these derivatives. On the other hand, we provide a method to construct all of the higher order derivatives in given directions. We also demonstrate some properties of the higher order derivatives and their decomposition as a sum of functions with 0-linear structure. Moreover, we introduce a criterion and an algorithm to realize discrete antidifferentiation of vectorial Boolean functions. This leads us to define a new equivalence of functions, that we call differential equivalence, which links functions that share the same derivatives in directions given by some subspace.

I will introduce a class of three indices tensor models, endowed with O(N)⊗3 invariance (N being the size of the tensor). They generate weights for general 3-colored graphs, which are not necessarily bipartite. Relying on combinatorial properties of colored graphs, I will first prove the existence of a 1/N expansion for any such model. I will then focus on a model with two parameters, and illustrate how standard methods from analytic combinatorics allow to compute physical quantities such as critical exponents.

An infinite word x on an alphabet A is self-shuffling, if x admits factorizations: $x=\prod_{i=1}^\infty U_iV_i=\prod_{i=1}^\infty U_i=\prod_{i=1}^\infty V_i$ with $U_i,V_i \in \A^*$. In other words, there exists a shuffle of x with itself which reproduces x. W­­e prove that many important and well studied words are self-shuffling: This includes the Thue-Morse word and all Sturmian words except Lyndons. We further establish a number of necessary conditions for a word to be self-shuffling, and show that certain other important words (including the paper-folding word and infinite Lyndon words) are not self-shuffling. This new notion has some unexpected applications: As a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic. Finally, we provide a positive answer to a recent question by T. Harju whether square-free self-shuffling words exist and discuss self-shuffling in a shift orbit closure.

Les multizêtas sont des nombres généralisant la fonction zêta de Riemann au cas de la dimension supérieure. Ces nombres sont (en particulier) définis sur des n-uplets d'entiers strictement positifs, mais grâce à des prolongements analytiques, il est possible de les prolonger tous les n-uplets d'entiers. Cela correspondant alors une généralisation des nombres puis des polynômes de Bernoulli. Bien qu'il n'y ait pas unicité d'une telle généralisation, nous introduirons un exemple explicite et satisfaisant où nombres de propriétés importantes des polynômes de Bernoulli se transmettent au cas multiple. Au passage, cela permet de répondre à une question sur la renormalisation des multizêtas aux entiers négatifs.

This talk explains the gist underlying regulated grammars and automata as well as the main purpose of their investigation. This investigation is classified into four major topics--the study of their power, properties, reduction, and mutual convertibility. The talk illustrates this inevstigation by a case study in terms of one-sided random-context grammars. Most importantly, it points out that propagating versions of one-sided random-context grammars characterize the family of context-sensitive languages, and with erasing rules, they characterize the family of recursively enumerable languages; as a result, they are stronger than ordinary random context grammars. Open problem areas are formulated.

On s'intéresse au parallèle entre 2 problèmes sur des modèles distincts d'automates. D'une part, les automates de Mealy (transducteurs lettre à lettre complets) qui produisent des semi-groupes engendrés par les transformations sur les mots infinis associées aux états. En 2013, Gillibert a montré que le problème de la finitude de ces semi-groupes était indécidable. En revanche la question est ouverte dans le cas où l'automate de Mealy produit un groupe. D'autre part, les automates cellulaires unidirectionnels pour lesquels la question de la décidabilité de la périodicité est ouverte. On peut montrer l'équivalence de ces problèmes. On fera un pas dans cette étude en montrant qu'il est possible de simuler du calcul Turing dans un automate cellulaire unidirectionnel réversible, rendant ainsi des problèmes de prédiction indécidables ainsi que la question de la périodicité partant d'une configuration finie.

En 2009, Han a redécouvert et généralisé une identité due à Nekrasov et Okounkov, qui fait un lien entre d'un coté, les puissances de la fonction êta de Dedekind, et de l'autre les partages d'entiers et leurs longueurs d'équerres. Pour cela, il utilise la formule de Macdonald pour le système affine de racines de type A. Je montrerai comment, à l'aide de bijections, il est possible de démontrer des identités de Nekrasov-Okounkov pour d'autres types de systèmes de racines (type affine C et D notamment), et je présenterai les nouvelles formules des équerres qui en découlent. Dans une seconde partie, je présenterai la notion d'éléments cycliquement pleinement commutatifs dans les groupes de Coxeter, qui ont été introduits pour étudier une version cyclique d'un théorème de Matsumoto. Je montrerai ensuit comment, en utilisant la théorie des automates finis, on peut démontrer que la série génératrice de ces éléments est une fraction rationnelle, quelque soit le groupe de Coxeter considéré.

Dans les années 1990, Schmitt a décrit un procédé qui permet d'associer à toute famille d'intervalles vérifiant certaines conditions une algèbre de Hopf, appelée algèbre de Hopf d'incidence. Une algèbre de Hopf d'incidence bien connue est celle associée aux posets de partitions, aussi connue sous le nom d'algèbre de Hopf de Faà Di Bruno. Après avoir rappelé les définitions nécessaires et présenté l'algèbre de Faà di Bruno, nous introduirons une algèbre de Hopf généralisant celle de Faà di Bruno : l'algèbre de Hopf d'incidence des partitions semi-pointées. [En fonction du temps qui me restera, j'évoquerai mes récents résultats en collaboration avec J.-C. Aval, Adrien Boussicault, P. Laborde-Zubieta et F. Hivert sur les arbres non ambigus. ]

En 1998, Loday et Ronco décrivent une algèbre de Hopf combinatoire dont la base est indicée par des arbres binaires. Cette algèbre possède de nombreux liens avec divers résultats antérieurs. Son produit est en particulier lié aux intervalles du treillis de Tamari, structure d'ordre partiel dont les éléments sont des arbres binaires. En 2006, Reading définit la notion de treillis cambrien d'un groupes de Coxeter. Le treillis Cambrien généralise l'ordre de Tamari en utilisant des structures arborescentes qui généralisent les arbres binaires : les arbres cambriens. Une question naturelle se pose alors : est-il possible de généraliser l'algèbre de Hopf de Loday-Ronco aux arbres cambriens ? Dans cette présentation, j'expliquerai les résultats que nous avons obtenus avec Vincent Pilaud sur les arbres cambriens en type A.

Une transformation T : X -> X d'un espace X est dite randomisante si son itération tend à uniformiser la distribution des configurations de l'espace X. Plus précisément, quand une mesure de probabilité initiale non uniforme est fixée sur X (la distribution initiale), l'itération de la transformation T fait converger cette mesure vers la mesure uniforme.
De tels comportements ont été remarqués expérimentalement dans certains automates cellulaires et sous-décalages de dimension 2. Dans cet exposé, je présenterai nos récentes avancées dans l'étude des causes et des limites de ces phénomènes, qui nous ont amenées à la première preuve rigoureuse de leur existence. Cette preuve repose sur le fort contenu algébrique des systèmes considérés qui donne à leur évolution temporelle une structure géométrique autosimilaire. Dans un sous-décalage particulier (celui de Ledrappier), nous obtenons des changements surprenants de dynamique directionnelle suivant la direction considérée.
Ce travail est issu d'une collaboration avec Ville Salo et Guillaume Theyssier (ex-CMM, Universidad de Chile).

Dans l’espoir de comprendre certains travaux récents de Berenstein et Rudel (« Quantum cluster characters of Hall algebras », arXiv:1308.2992 et « The Feigin tetrahedron », arXiv:1401.4338v2), en particulier la construction d’un homomorphisme, appelé « quantum shuffle character », entre le dual de l’algèbre de Ringel-Hall et l’algèbre de mélange quantique, j’étudierai l’algèbre de Ringel-Hall, en insistant sur sa structure d’algèbre de Hopf auto-duale.

Finite automata are used in a wide range of verification problems. We introduce "bisimulation up to congruence" as a technique for proving language equivalence of non-deterministic finite automata. Exploiting this technique, we devise an optimisation of the classical algorithm by Hopcroft and Karp which, as we show, is exploiting a weaker "bisimulation up to equivalence" technique. The resulting algorithm can be exponentially faster than the recently introduced "antichain algorithms".

Dans un premier temps j'exposerai de manière générales la théorie de la volumétrie des langages temporisés développés durant (et depuis) ma thèse. Avec mes collègues nous avons trouvé des applications à cette théorie dans divers domaines de recherche tels que la théorie de l’information, la vérification, la combinatoire énumérative. Dans un second temps, je décrirai plus précisément comment étant donné un automate temporisé, on peut exprimer et calculer son entropie et sa fonction génératrice des volume s à l'aide de la théorie spectrale d'un opérateur fonctionnel associé à cet automate temporisé. Nous fonctionnons par analogie avec le cas discret, au lieu d'appliquer la théorie de Perron-Frobenius à la matrice d'adjacence d'un automate fini, nous appliquons la théorie des opérateurs positifs agissant sur les espaces de Banach à l'opérateur fonctionnel de notre automate temporisé. Dans un troisième temps je décrirai les applications au dénombrement et à la génération aléatoire de permutations dans les classes régulières (c'est à dire chaque permutation de la classe a un mot de montées et de descentes appartennant à un langage régulier donné). Nous nous intéresserons particulièrement à la génération aléatoire par générateur de Boltzmann et par processus stochastique d'entropie maximal.

Les groupes de traces sont une généralisation des monoïdes de traces (encore appelés monoïdes partiellement commutatifs libres). Un résultat de 1969 de Carier et Foata montre l'existence d'une formule d'inversion de Möbius pour la série génératrice du monoïde de traces. Nous généralisons ce résultat aux groupes de traces, ce qui nous permettra également d'étudier la hauteur moyennes des traces.

Peut-être souvent mésestimés, les diagrammes de cordes et leur énumération apparaissent dans de nombreux domaines mathématiques : physique quantique, théorie des noeux, échantillonnage de graphes, analyse de structures informatiques, et même bio-informatique... Les travaux de cet exposé, en cours de rédaction et coréalisés avec Karen Yeats (SFU, Vancouver), se placent de le cadre de la physique quantique. En effet, les solutions à certaines équations de Dyson-Schwinger (nous n'en parlerons que très peu, soyez rassurés) peuvent être définies grâce aux diagrammes de cordes connexes munies d'un paramètre particulier : les cordes dites terminales. Nous étudierons donc quelques statistiques sur ces cordes terminales : leur nombre en moyenne, la position de la première corde terminale, etc. Nous constaterons notamment l'apparition d'une loi limite de probabilité qui, à ma connaissance, n'est pas répertoriée dans la littérature. Nous montrerons également en quoi les techniques classiques de combinatoire analytique ne peuvent s'appliquer et donnerons quelques idées sur la démarche à emprunter dans ce cas-là.

Les jeux combinatoires sont des jeux finis sans hasard à deux joueurs et à information complète. En convention normale, un joueur perd lorsqu'il ne peut plus jouer, alors que ce joueur gagnerait en convention misère. La théorie des jeux combinatoires développée par Berlekamp, Conway et Guy pour les jeux en convention normale a donné peu de résultats pour les jeux en convention misère, ce qui explique que nous étudiions ici un sous-ensemble de jeux, appelés dead-ending, dans lesquels un joueur qui ne peut pas jouer à un certain point ne pourra plus jamais jouer dans ce jeu, quelle que soit la séquence de coups jouée par son adversaire. Les jeux combinatoires peuvent être représentés par des arbres dans lesquels les fils d'un nœud représentent les positions que les joueurs peuvent atteindre depuis la position que le nœud représente. Nous étudions la somme des jeux dead-ending et utilisons ses propriétés pour réduire ses arbres, leur donnant une forme canonique et garantissant que l'inverse d'un jeu inversible est naturel.

Le modèle du tas de sable abélien décrit d'une façon élémentaire des processus de diffusion dans des réseaux. Des configurations de sable instables se stabilisent en des configurations stables, suite à une dynamique de avalanches. Malgré sa simplicité, ce modèle présente des phenoménes surprenants. On peut ansi considérer des configurations instables très simples à décrire, sur des réseaux réguliers, et observer le résultat à la fin de l'avalanche : on verra apparaitre des formes fractales complexes. Une de ces configurations est l'identité récurrente, Id. Quand le graphe est une portion carrée, de taille L, du réseau carré. On a donc une suite Id(L) de configurations, qui, mises à l'échelle, semblent converger vers une forme limite fractale qui fascine les chercheurs depuis longtemps. On vient d'obtenir une description complète de cette forme. Ce résultat fait apparaitre plusieurs surprises : tous les points de contact entre les morceaux qui forment la fractale ont des coordonnées (x,y) qui appartiennent au meme corps cubique. Par exemple, le bien connu "carré bleu" qu'on trouve au milieu de la configuration est à une distance du bord de 0.58315637..., c'est-à-dire, la seule racine réelle de l'équation 2x^3+3x^2+x-2=0.

Une dissection du polygone régulier à n côtés est la graphe formé par le polygone et certaines de ses diagonales, avec la règle que deux diagonales ne peuvent se croiser qu'aux sommets du polygone. On s'intéresse ici au comportement asymptotiquement d'une dissection uniformément distribuée dans l'ensemble des dissections du polygone à n côtés. Nous verrons que multipliée par n^(-1/2) cette dissection uniforme converge vers un multiple du CRT brownien. Ce résultat se généralise à des mesures attribuant des poids de Boltzmann aux degrés des faces des dissections, lorsque ces poids décroissent suffisamment vite. Il s'agit d'un travail en collaboration avec Nicolas Curien et Igor Kortchemski.

Un théorème fondamental pour la théorie des égalités affirme que les polynômes symétriques élémentaires engendrent la sous-algèbre des polynômes symétriques, et sont algébriquement indépendants. Nous explorons l'utilité de ce résultat pour la théorie des inégalités.

Peu de résultats sont connus sur la nature diophantienne des valeurs de la fonction zêta et de leurs généralisations, les polyzêtas. Une méthode générale pour parvenir à montrer l'irrationalité de tel ou tel nombre consiste à construire des approximations polynomiales, dites de Padé, de séries entières, puis à spécialiser pour obtenir des approximations numériques de ces nombres. Je présenterai diverses constructions d'approximants de Padé dans le contexte des polyzêtas. Certaines proviennent de travaux en commun avec Stéphane Fischler.

Je présenterai un curieux théorème de factorisation pour le nombre des pavages en losanges d'un hexagone avec symétrie verticale et horizontale dont plusieurs trous triangulaires ont été enlevés le long de l'axe de symétrie horizontale. Je relierai ce théorème avec des autres théorèmes de factorisation, et je discuterai quelques conséquences et questions ouvertes. Ce travail a été effectué en commun avec Mihai Ciucu.

---

"A factorisation theorem for the number of rhombus tilings of a hexagon with trianglar holes"

I shall present a curious factorisation theorem for the number of rhombus tilings of a hexagon with vertical and horizontal symmetry axis, with triangular holes along the latter axis. I shall set this theorem in relation with other factorisation theorems, and discuss some consequences and open questions. This is joint work with Mihai Ciucu.

Regular D-edge-colored graphs encode D-dimensional colored triangulations of pseudo-manifolds. We study such families of edge-colored graphs built from a finite but arbitrary set of building blocks, which extend the notion of p-angulations to arbitrary dimensions. I will introduce a bijection between any such family and some colored combinatorial maps which we call stuffed Walsh maps. Those maps generalize Walsh's representation of hypermaps as bipartite maps, by replacing the vertices which correspond to hyperedges with non-properly-edge-colored maps.

We are interested in the number of bi-chromatic cycles of the initial edge-colored graphs because because they encode the curvature of the corresponding triangulated pseudo-manifold. I will therefore present new tools that use the bijection in order to study the graphs which maximize the number of bi-chromatic cycles at fixed number of vertices and provide examples where the corresponding stuffed Walsh maps can be completely characterized.

Algèbres de (Ringel-)Hall Suivi de : Échelles de comparaison et développements singuliers. Dans l’espoir de comprendre certains travaux récents de Berenstein et Rudel (« Quantum cluster characters of Hall algebras », arXiv:1308.2992 et « The Feigin tetrahedron », arXiv:1401.4338v2), en particulier la construction d’un homomorphisme, appelé « quantum shuffle character », entre le dual de l’algèbre de Ringel-Hall et l’algèbre de mélange quantique, j’étudierai l’algèbre de Ringel-Hall, en insistant sur sa structure d’algèbre de Hopf auto-duale. En deuxième partie est prévu un rapppel de ce que sont les échelles suivant des bases de filtres générales (voisinages, pointés, fendus, bases de filtre de Fréchet, complémentaires de points isolés etc...). On appliquera ces notions aux développements singuliers de P. Flajolet et A. Odlyzko. Une discussion générale sur les travaux en cours s'ensuivra.

Consider a random coloring of a bounded domain in Zd with the probability of each coloring F proportional to exp(-β*N(F)), where β>0 is a parameter (representing the inverse temperature) and N(F) is the number of nea rest neighboring pairs colored by the same color. This is the anti-ferromagnetic 3-state Potts model of statistical physics, used to describe magnetic interactions in a spin system. The Kotecký conjecture is that in such a model, for d≥3 and high enough β, a sampled coloring will typically exhibit long-range order, placing the same color at most of either the even or odd vertices of the domain. We give the first rigorous proof of this fact for large d. This extends previous works of Peled and of Galvin, Kahn, Randall and Sorkin, who treated the case β=infinity. No background in statistical physics will be assumed and all terms will be explained thoroughly. Joint work with Ohad Feldheim.

One approach to solving some questions in probability theory--especially questions about asymptotic properties of algorithms and data structures--is to take an analytic approach, i.e., to utilize complex-valued methods of attack. These methods are especially useful with several types of branching processes, leader election algorithms, pattern matching in trees, data compression, etc. This talk will focus on some of the highlights of this approach. I endeavor to keep it at a level that is accessible for graduate students.

Lattice spin systems are used in statistical physics to model various magnetic materials. I will first introduce some well-known models in this field and give a short review of known results, with an emphasis on the phenomenon of long-range order. I will then discuss a result on the existence of long-range order for random 3-coloring of Z^d in high-dimensions (joint work with Ohad Feldheim). Finally, I will also discuss a result of long-range order for the loop O(n) model on the hexagonal lattice (joint work with Hugo Duminil-Copin, Ron Peled and Wojciech Samotij). No background in statistical physics will be assumed and all terms will be explained thoroughly.

Lattice spin systems are used in statistical physics to model various magnetic materials. I will first introduce some well-known models in this field and give a short review of known results, with an emphasis on the phenomenon of long-range order. I will then discuss a result on the existence of long-range order for random 3-coloring of Z^d in high-dimensions (joint work with Ohad Feldheim). Finally, I will also discuss a result of long-range order for the loop O(n) model on the hexagonal lattice (joint work with Hugo Duminil-Copin, Ron Peled and Wojciech Samotij). No background in statistical physics will be assumed and all terms will be explained thoroughly.

Coin-tossing is one of the simplest ways of resolving a conflict, deciding between two alternatives, and generating random phenomena. It has been widely adopted in many daily-life situations and scientific disciplines. In this talk, I will present a few research themes connected to the use of coin-tossing in algorithmics, taken from my research: these include random permutations, data structures, evolutionary algorithms and leader selection. The main focus will be on the stochastic behaviors and the methods of analysis.

We report on the formal verification of an irrationality proof of the evaluation at 3 of the Riemann zeta function. This verification uses the Coq proof assistant in conjunction with algorithmic calculations in Maple. This irrationality result was first proved by Apéry in 1978, and our formalization follows the proof path of his original presentation. The crux of it is to establish that some sequences satisfy a common recurrence. We formally prove this by an a posteriori verification of calculations performed by a Maple session. This bases on computer-algebra algorithms implementing Zeilberger's approach of creative telescoping. This experience illustrates the limits of the belief that creative telescoping can discover recurrences for holonomic sequences that are easily checked a posteriori. We discuss this observation and describe the protocol we devised in order to produce complete formal proofs of the recurrences. Beside establishing the recurrences, our proof combines the formalization of arithmetical ingredients and of some asymptotic analysis.
Joint work with Assia Mahboubi, Thomas Sibut-Pinote, and Enrico Tassi.

Part 1: We show that the Flajolet-Soria coeffcient extraction formula for algebraic series can be deduced from a theorem of Furstenberg, with which we can prove that the formula is valid for all fields and not only for the complex field.
Part 2: We present a method of finding infinite products involving block counting functions in any base. This is a generalization of the work of Allouche and Shallit, where the result applies to base 2.

Self-avoiding walks appear ubiquitously in the study of linear polymers as it naturally captures their volume exclusion property. However, self-avoiding walks are very difficult to analyse with few rigourous results available. In 2008, Alvarez et al. determined numerical results for the forces induced by a self-avoiding walk in an interactive slit. These results resembled the exact results for a directed model in the same setting by Brak et al. in 2005, suggesting the physical consistency of directed walks as polymer models. Via the kernel method, we extend the directed walk model to a series of models involving two directed walks as a way to find exact enumerative results for studying the behaviour of ring polymers near an interactive wall, or walls. In the final model we considered, we are unable to find exact solutions via the kernel method. Instead, we use transfer matrices to obtain numerical results that are qualitatively similar to those presented by Alvarez et al.

On s'intéresse aux pavages par carrés et losanges qui discrétisent des plans de l'espace à quatre dimensions. Plus précisément, on veut savoir lesquels peuvent être caractérisés par leurs motifs locaux. Il se trouve qu'ils correspondent à des plans définis par des entiers quadratiques (et pas plus). La généralisation aux pavages par plus de losanges reste ouverte.

En 2004, Pittel et Romik ont montré l'existence d'une forme limite pour les tableaux de Young rectangulaires. Je montrerai comment la méthode probabiliste des "densités", que je développe depuis quelques travaux déjà, permet de retrouver cette forme limite et donne aussi les fluctuations sur le bord : on trouve une gaussienne dans les coins et Tracy-Widom ailleurs sur le bord.

Nous allons d'écrire et étudier une classe importante de DAG, appelé structure en diamant. Cette étude repose sur une analyse asymptotique d'équations différentielles non linéaires. Nous expliquerons aussi comment développer des générateurs aléatoires efficaces pour ces structures. Travail en commun avec Hsien-Kuei Hwang, Antoine Genetrini et Xavier Fontaine.

During this defense I present pieces of the work I achieved on random tensor models (tensor models for short). I will define colored triangulations and then review their combinatorics. After this is done I show how one can write integral representation of their generating series. These representations are called tensor models. Using this representation I will describe the combinatorial 1/N expansion for two different kinds of models generating specific classes of colored and non-colored combinatorial maps. I will then concentrate on a specific model, that is the simpler non trivial tensor model and explore some of its properties. In particula r I review the properties of its double scaling limit, then using its Hubbard-Stratanovitch representation, I show how one can use matrix models techniques to recover results obtained using combinatorial techniques. I will finally present several results that point towards integrable structures in the framework of random tensor models.

Les pavages, ou sous-shifts de type fini sont des ensembles de coloriages du plan vérifiant des contraintes locales en nombre fini. Nous nous intéresserons en particulier au problèmes d'isomorphisme entre sous-shifts, connu sous le nom de conjugaison et plus particulièrement aux invariants de conjugaison, qui sont des "objets" permettant de caractériser certains aspects des sous-shifts. Nous donnerons en particulier des caractérisations calculatoires de ces derniers qui permettront de voir les liens intimes qui lient pavages et classes de complexité/calculabilité.

I will review some new results in the stochastic euclidean bipartite matching problem. First I will look at the simple one dimensional version, for which many exact results can be achieved. Afterwards, by discarding the discrete nature of the problem, as usual in a critical system, I will show how it is possible to resort to a continuous version for which an analytical expression for the minimum cost and correlation functions can be computed.

We present an extension of a theorem by Michael Drmota and Michèle Soria [1997] that can be used to identify the limiting distribution for a class of combinatorial schemata. This is achieved by determining analytical and algebraic properties of the associated bivariate generating function. We give sufficient conditions implying a half-normal limiting distribution, extending the known conditions leading to either a Rayleigh, a Gaussian or a convolution of the last two distributions. Finally, we present some applications to lattice path and tree enumeration, images and preimages in random mappings.

Les monoïdes J-triviaux forment une importante famille de monoïdes dont l'étude des représentations est particulièrement combinatoire. De plus, certains exemples (la paire NCSF/Qsym est catégorifiée par les monoïdes 0-Hecke, l'algèbre de Weyl par NilHecke, etc) laissent suggérer que ce sont des candidats naturels pour catégorifier certaines algèbres de Hopf. Dans cet exposé, nous considérerons des tours de monoïdes J-triviaux et étudierons des formules générales d'induction et de restriction. Nous verrons en détail le cas des tours de semi-treillis duquel on tire des "semi-catégorifications" de certaines algèbres de Hopf (FQSym, PBT, NCSF).

The diagonal of a multivariate power series F is the univariate power series Diag F generated by the diagonal terms of F. Diagonals form an important class of power series; they occur frequently in number theory, theoretical physics and enumerative combinatorics. We study algorithmic questions related to diagonals in the case where F is the Taylor expansion of a bivariate rational function. It is classical that in this case Diag F is an algebraic function. We propose an algorithm that computes an annihilating polynomial for Diag F. Generically, it is its minimal polynomial and is obtained in time quasi-linear in its size. We show that this minimal polynomial has an exponential size with respect to the degree of the input rational function. Throughout the talk, we use a common problem of counting certain lattice walks to illustrate the capacities and limits of our tools.

The AdS/CFT (anti-de Sitter/conformal field theory) quantum spectral curve is a tool for computing the conformal spectrum of a four-dimensional gauge theory, N=4 SYM, in the planar limit. This tool proved to be very efficient: we were able to get the explicit 10-loop perturbative results. The answer is expressed in terms of multiple zeta values. I will explain what the quantum spectral curve is and how the multiple zeta values emerge from it.

The AdS/CFT (anti-de Sitter/conformal field theory) quantum spectral curve is a tool for computing the conformal spectrum of a four-dimensional gauge theory, N=4 SYM, in the planar limit. This tool proved to be very efficient: we were able to get the explicit 10-loop perturbative results. The answer is expressed in terms of multiple zeta values. I will explain what the quantum spectral curve is and how the multiple zeta values emerge from it.

Les fonctions de parking sont intéressantes pour de nombreuses raisons. Elles sont en bijection avec les séquences de Prüfer, les chemins de Dyck décorés, etc., et sont liées à l’inversion de Lagrange, aux polynômes harmoniques diagonaux, etc. En particulier, elles sont en bijection avec les forêts d'arbres enracinés, autrement dit avec les endo-fonctions acycliques. En 2002, Jim Pitman et Richard P. Stanley ont introduit une généralisation des fonctions de parking. Nous verrons qu'une sous-famille de ces fonctions de parking généralisées est en bijection avec l’ensemble des fonctions de transition des automates finis déterministes acycliques. Nous expliciterons une bijection et nous montrerons que cette dernière transporte une information précieuse sur les langages droits des états de l'automate. Nous utiliserons cette information pour extraire et énumérer les automates acycliques non-initiaux pour lesquels tous les langages droits des états sont distincts. Enfin, par une technique usuelle de graphes, nous obtiendrons une formule exacte d'énumération des automates acycliques minimaux.

Soit s une permutation dans Sigma_n. Soit i(s)=s(1), j(s)=s^{-1}(1), Soit C_k le cycle 1>2>...>(k-1)>1 (k,k+1,..,n points fixes). On definit L et R comme suit: L(s) = C_{j(s)}.s et R(s) = s.C_{i(s)}^{-1} Il est facile de voir que L et R sont inversibles, la dynamique L/R partitionne donc Sigma_n en classes d'équivalence qui sont des graphes orientés uniformes (une arête entrant/sortant par "couleur" L et R) fortement connexes. Dans cet exposé, on étudiera ces classes : leur nombre, leur taille, leur structure, etc.

Dans la version classique de "la Tour de Hanoï", c'est-à-dire avec trois aiguilles, on sait bien qu'on peut transférer N disques d'une aiguille vers une autre en 2^N-1 mouvements, et que ce nombre est minimal. Ajoutons une quatrième aiguille: quel est alors le nombre minimum de mouvements nécessaires pour transférer N disques d'une aiguille vers une autre? Etrangement, ce problème posé il y a plus d'un siècle par le puzzliste anglais Henry Ernest Dudeney n'a été résolu que tout récemment. Et pour d'autres variantes de la Tour de Hanoï, avec davantage d'aiguilles ou des restrictions sur les mouvements, le problème est largement ouvert. http://www.cnrs.fr/insmi/spip.php?article1170

I will give an introduction to, and describe recent research on the multi-type TASEP on a ring. This is a Markov process on permutations given by randomly sorting (cyclically) adjacent letters in the permutation at hand. The model is motivated both by physical and combinatorial considerations. The stationary distribution has a nice description in terms of the multi-line queues discovered by Ferrari and Martin.

In this work, we extend the definition of Christoffel words to directed subgraphs of the hypercubic lattice in arbitrary dimension that we call Christoffel graphs. Christoffel graphs when d=2 correspond to well-known Christoffel words. We show that Christoffel graphs have similar properties to those of Christoffel words: symmetry of their central part and conjugation with their reversal. Our main result extends Pirillo's theorem (characterization of Christoffel words which asserts that a word amb is a Christoffel word if and only if it is conjugate to bma) in arbitrary dimension. In the generalization, the map amb\mapsto bma is seen as a flip operation on graphs embedded in Z^d and the conjugation is a translation. We show that a fully periodic subgraph of the hypercubic lattice is a translate of its flip if and only if it is a Christoffel graph. This is joint work with Christophe Reutenauer. Preprint is available at http://arxiv.org/abs/1404.4021.

Les nombres et polynômes de Bernoulli sont des objets classiques qui apparaissent respectivement lors du prolongement analytique des fonctions zêta de Riemann et de Hurwitz aux entiers négatifs. En lien avec la généralisation multiple de ces fonctions, les multizêtas et multizêtas de Hurwitz, nous allons généraliser les nombres et polynômes de Bernoulli au cas multiple. Bien qu'il n'y a pas unicité d'une telle généralisation, nous introduirons un exemple explicite et satisfaisant où nombres de propriétés importantes des polynômes de Bernoulli se transmettent au cas multiple. Au passage, cela permet de répondre à une question sur la renormalisation des multizêtas aux entiers négatifs.

Automatic sequences T(n) are the output sequence of a finite automaton, where the input is the q-adic digital representation of n. The most prominent example is the Thue-Morse sequence t(n) (that is also the fixed point of the substitution 0 -> 01, 1 -> 10). Automatic sequences have been studied in many diff erent contexts from combinatorics to algebra, number theory, harmonic analysis, geometry and dynamical systems. For example, they have a linear subword complexity and they are almost periodic. Since the subword complexity is linear the entropy of the related dynamical system is zero. This also means that they do not behave like a random sequence. However, the situation changes drastically when one uses proper subsequences of automatic sequences, for example the subsequence along primes or squares. It is conjectured that the resulting sequences are normal sequences so that they behave like random sequences (=quasi random sequences). Recently this property was proved (together with C. Mauduit and J. Rivat) for the Thue-Morse sequence along the subsequence of squares - and it turns out that this propery extends to several other automatic sequences and also to subsequences of the form [n^c], where 1 < c < 4/3. Thus such subsequences of automatic sequences give rise to a completely new class of pseudo random sequences that can be computed very efficiently.

The purpose of this talk is to give a survey on the behaviour of the profile of three different kind of random trees, namely Galton-Watson trees, search trees and digital trees.

Les cartes sont des surfaces discrètes construites en recollant le long de leurs bords des polygônes - l'exemple le plus simple étant les triangulations. En tant que surfaces orientables, leur topologie est caractérisée par le nombre de bords n, et le nombre d'anses g. Si l'on se donne un poids de Boltzmann t_k pour chaque k-gone, l'énumération des cartes à un bord et de genre 0 est un problème très bien étudié. Ici, je considèrerai le problème plus général d'énumérer les cartes farcies: ce sont les surfaces obtenues en a) piochant dans une boîte à outils pouvant contenir des surfaces à bords polygonaux et de topologie quelconque ; b) en recollant ces morceaux élémentaires le long de leurs bords ; c) pondérant l'énumération par des poids de Boltzmann dépendant du genre et de la longueur des bords de chaque morceau élémentaire. J'expliquerai notamment qu'il existe une récurrence universelle sur la caractéristique d'Euler totale 2 - 2g - n, qui réduit le problème d'énumération en toute topologie à celui des disques (n = 1, g = 0) et des cylindres (n = 2,g = 0).

In the first part of the talk I will introduce the Tutte polynomial of graphs and explicitly show its relation with polynomials appearing in the so-called parametric representation of integrands canonically associated to graphs in quantum field theory. In the second part of the talk I will show a new proof of the celebrated property of universality of the Tutte polynomial of graphs (or matroids), proof which does not require the usual edge induction arguments. Finally, I will present how this proof generalizes for the universality property of the Bollobas-Riordan polynomial of ribbon graphs (or embedded graphs).

Approximate message passing is an iterative algorithm for compressed sensing and related applications. A solid theory about the performance and convergence of the algorithm exists for measurement matrices having iid entries of zero mean. However, it was observed by several authors that for more general matrices the algorithm often encounters convergence problems. In this paper we identify the reason of the non-convergence for measurement matrices with iid entries and non-zero mean in the context of Bayes optimal inference. Finally we demonstrate numerically that when the iterative update is changed from parallel to sequential the convergence is restored.

Three-dimensional random tensor models are a natural generalization of the celebrated matrix models. The associated tensor graphs, or 3D maps, can be classified with respect to a particular integer or half-integer, the degree of the respective graph. I will present in this talk a combinatorial analysis of the general term of the asymptotic expansion in N, the size of the tensor, of a particular random tensor model, the so-called multi-orientable model. I will then present some enumerative results and show which are the dominant configurations of a given degree; several examples will also be given.

Les associaèdres généralisés ont été introduits par Sergey Fomin et Andrei Zelevinsky dans le cadre de la théorie des algèbres amassées, et réalisés géométriquement par Chapoton, Fomin et Zelevinsky. Ils sont associés à n'importe quel groupe de Coxeter fini. Parmi eux figurent trois familles infinies de polytopes : les associaèdres de type A (associaèdres usuels), de type B ou C (cycloèdres), et de type D. Le diamètre asymptotique des associaèdres de types A, B (ou C), et D est maintenant connu et cet exposé passera en revue les cas des types B (ou C), et D. Les preuves ne seront pas données entièrement, mais seulement esquissées. Quelques questions associées seront finalement discutées.

Effective construction of pairs of bases in duality in the general co-commutative deformations of the shuffle co-product allow to identify the local coordinates in the group of associators leading to the ideal of homogeneous polynomial relations among polyzetas.

It is a commonly observed phenomenon in enumerative combinatorics that several combinatorial classes share the same enumeration. For any two classes which seem to have the same enumeration sequence, a natural problem is to prove that it is indeed the case, ideally with a bijective proof that allows to map the structure of one class to that of the other. Such coincidences of enumeration are called Wilf-equivalences in the context of pattern-avoiding permutation classes (the definition of pattern-avoidance will be given during the talk). Wilf-equivalence has been a popular topic in the research on pattern-avoiding permutations, from its beginnings in the seventies until now. It is fair to say that most of the works done so far are specific to given pairs of equi-numerous classes, thus forming a sort of "case-by-case catalogue" of the known Wilf-equivalences. In this talk, we explore a different approach: we are interested in describing all Wilf-equivalences between permutations classes defined by the avoidance of two patterns: 231 and an additional pattern p (w.l.o.g., we can assume that p itself avoids 231). We will explain that this is one way of phrasing a seemingly more general (but actually equivalent) question: that of describing all Wilf-equivalences between classes of Catalan objects subject to one further avoidance restriction. Such classes are denoted Av(A), A being a Catalan object. Our results, to be presented in the talk, are the following. First, we define an equivalence relation ~ among Catalan objects. Our main result is that it refines Wilf-equivalence: if A ~ B, then Av(A) and Av(B) have the same enumeration. The proof is subdivided in several cases, and it is bijective in all cases but one. We further conjecture that the converse statement holds, i.e., that this relation ~ coincides with Wilf-equivalence. Then, we show how to enumerate the number of equivalence classes for ~, hereby providing an upper bound on the number of Wilf-equivalence classes. It is also interesting to study a special ~-equivalence class, which can be understood at a very fine level of details. Our results on this ~-class (called the "main" one) unify and generalize several results of the literature on Wilf-equivalence. Finally, we explain how our bijective cases in the proof of the main theorem can often be refined to provide comparison results between the enumerations of classes Av(A) and Av(B) when A and B are not equivalent for ~. A consequence is that the "main" ~-class corresponds to the largest possible enumeration sequence. This is joint work with Michael Albert (University of Otago), and a preprint is available at arXiv:1407.8261.

Dans cet exposé (au tableau), je regarderai la série génératrice multivariée des fonctions croissantes sur un ensemble ordonné donné. Le but est de décrire combinatoirement (à l'aide des diagrammes de Hasse des ensembles ordonnés) les relations entre les séries formelles obtenues. Je vais d'abord présenter le travail fondamental de Stanley sur les P-partitions qui répond, en quelque sorte, à cette question. Je donnerai ensuite une seconde réponse, à l'aide de l'opération d'inclusion-exclusion cyclique que j'ai récemment introduite.

Le tracé d'une courbe sur une grille produit une suite de pixels consécutifs qui peut être représentée par un mot sur l'alphabet {droite, haut, gauche, bas}. Ce codage établit un dictionnaire entre objets géométriques (ou différentiels) et propriétés combinatoires sur les mots. Par exemple, le codage des segments de droites correspond aux mots dits 1-équilibrés, qui sont les facteurs finis des mots sturmiens. Une méthode classique pour analyser une courbe lisse discrétisée consiste à décomposer son codage en mots 1-équilibrés maximaux, qui servent alors de tangentes discrètes. Sans ajout d'hypothèses, les estimateurs de tangentes ou de courbure associés ne convergent pas nécéssairement lorsque la maille de la grille tend vers zéro. Une raison possible est la suivante : certains mots non 1-équilibrés peuvent apparaître dans le codage de courbes lisses pour des mailles arbitrairement fines. Let but de cet exposé est de décrire ce langage et voir ce qu'on peut lui faire dire.

Tutte polynomial is a 2-variable polynomial defined on a graph which satisfies a contraction/deletion recurrence relation. This polynomial generalizes into the so-called Bollobas-Riordan (4-variable) polynomial for ribbon graphs which also satisfies a similar recurrence rule. In the recent Physics literature, there exists a growing interest for a new category of graphs called rank d stranded graphs. Such graphs encompass simple and ribbon graph structures and represent simplicial complexes in any dimension d. I will introduce a genuine 7-variable polynomial on these graph structures when restricted in rank 3 and when provided with a specific coloring. The polynomial satisfies a new contraction/cut rule. The procedure can be certainly extended in any rank.

A chaque langage régulier, on associe la classe (appelée régulière) de permutations ayant un motif d'ascentes/descentes (a/d) dans ce langage régulier de {a,d}^*. Par exemple, on peut définir ainsi les permutations alternantes, les permutations n’ayant pas deux descentes consécutives, les permutations ayant un nombre pair de descentes... J’expliquerai un algorithme qui étant donné un automate renvoie une formule close pour la série génératrice exponentielle de la classe régulière de permutations associée. J’expliquerai ensuite un algorithme qui permet de générer des permutations aléatoirement et de façon uniforme les permutations de même longueur de la classe régulière de permutations considérée. Les deux algorithmes sont basés sur une correspondance entre comptage de permutations et volumes de langages temporisés qui s’explique en terme de polytopes d’ordre et polytopes de chaîne de Stanley. Les deux algorithmes évoqués ci-dessus sont ainsi obtenus à partir d’algorithmes de calcul de fonction génératrice des volumes et de génération aléatoire de mots temporisé associés à un automate temporisé.

Dans cette présentation, on s'intéressera à deux sujets a priori distincts. Le premier concerne la génération aléatoire d'arbres planaires dans lequel on maîtrise le nombre d'occurrences d'un motif d'arbre. Le but est, partant d'un motif donné, de produire automatiquement une grammaire d'arbre dans laquelle les occurrences du motif sont marqués. Cette grammaire permet directement d'obtenir un générateur aléatoire en utilisant la méthode récursive, mais permet également d'obtenir une série génératrice bivariée. Le second est une présentation d'une famille de grammaires d'arbres et des automates qui y sont associés, appelés machines de Lukasiewicz. Cette famille fut utilisé pour résoudre le premier problème. Il s'agit d'une généralisation des grammaires d'arbre régulières. Si ces grammaires et les machines associés ont des propriétés de clôtures décevantes, on a pu décrire un algorithme de minimisation pour les machines déterministes.

Les systèmes dynamiques symboliques sont des suites bi-infinies de symboles dont les facteurs finis évitent un ensemble de mots finis donné. Nous présentons les systèmes appelés sofiques-Dyck. Ces systèmes sont une généralisation des systèmes Markov-Dyck introduits par Krieger et Matsumoto. Nous montrons que ces systèmes de séquences sont exactement les systèmes dont le langage des facteurs finis est un langage de mots imbriqués (nested words). Nous calculons la fonction zêta, qui compte les séquences périodiques du système, pour un système sofic-Dyck. (Travaux avec Michel Blockelet et Catalin Dima)

Marcel-Paul Schützenberger était un fan du monoïde plaxique et aussi des monoïdes de commutation : souvenirs et réminiscences.

Le 1er juillet aura lieu à Marne une journée de l'ANR MAGNUM, avec des exposés le matin et la soutenance de thèse de Sven De Félice l'après-midi. Voilà le programme de la journée : 9h30 Accueil, 10h Chaim Goodman-Strauss (Univ. Arkansas), 11h Julien Clément (GREYC), 12h Discussions, 12h30 Buffet, 14h30 Soutenance de thèse de Sven De Félice, 16h30 Pot de thèse et discussions sur Magnum. Cela a lieu dans la salle de séminaire 4B08R, au 4eme étage du batiment Copernic. Pour venir, descendre à la station Noisy-Champs du RER A (direction Marne-la-vallee ou Torcy) et suivre le plan : http://www.u-pem.fr/universite/presentation/plans-dacces/plan-du-campus/

Les positroïdes sont des matroïdes qui sont liés à l'étude de la partie positive des variétés grassmanniennes. Ils sont depuis quelques années l'objet de nombreuses études, en combinatoire, en géométrie et même en physique. L'exposé retracera le chemin qui, des variétés grassmanniennes, a mené à leur définition. On commencera par de nombreux rappels et on s'appuiera surtout sur les travaux d'A. Postnikov.

Les positroïdes sont des matroïdes qui sont liés à l'étude de la partie positive des variétés grassmanniennes. Ils sont depuis quelques années l'objet de nombreuses études, en combinatoire, en géométrie et même en physique. L'exposé retracera le chemin qui, des variétés grassmanniennes, a mené à leur définition. On commencera par de nombreux rappels et on s'appuiera surtout sur les travaux d'A. Postnikov.

Pour une famille F de cartes planaires on appelle "fonction à k points" la série génératrice de comptage des cartes de F avec k points marqués dont les distances deux à deux sont prescrites. On sait depuis les résultats de Bouttier, Di Francesco et Guitter (s'appuyant sur une bijection de Schaeffer) que la fonction à 2 points des quadrangulations admet une expression explicite, et des réultats plus récents de Bouttier et Guitter (s'appuyant sur une bijection de Miermont) ont établi une expression explicite pour la fonction à trois points des quadrangulations. Nous passerons en revue ces résultats et montrerons comment on peut exploiter une bijection récente due à Ambjorn et Budd pour établir des expressions explicites pour les fonctions à deux points et à trois points des cartes générales. Travaux en commun avec Jérémie Bouttier et Emmanuel Guitter

A two-dimensional system enjoys conformal symmetry when the invariance under rescaling and rotations is enhanced to invariance under any conformal (i.e. analytic and invertible) mapping. The conformal field theory (CFT) approach aims to find the solutions of the infinite set of equations imposed by conformal invariance. This approach has been successfully employed in diverse areas of physics and mathematics for almost thirty years. We will survey the basics ideas behind the CFT approach. We will adress some recent results concerning the representation of Virasoro algebras and its relations with Benjamin-Ono and Calogero-Moser integrable models. We finally show new results on conformally invariant random fractals.

Les positroïdes sont des matroïdes qui sont liés à l'étude de la partie positive des variétés grassmanniennes. Ils sont depuis quelques années l'objet de nombreuses études, en combinatoire, en géométrie et même en physique. L'exposé retracera le chemin qui, des variétés grassmanniennes, a mené à leur définition. On commencera par de nombreux rappels et on s'appuiera surtout sur les travaux d'A. Postnikov.

Les fonctions courbes ont été introduites par Rothaus et étudiées pour la première fois par Dillon dans sa thèse. Les fonctions courbes sont les fonctions booléennes qui sont à distance de Hamming maximale des fonctions affines. Depuis leur introduction, elles sont devenues l'un des objets les plus important en cryptographie symétrique. Une des raisons motivant leur étude est qu'il est recommandé que la fonction booléenne utilisée pour concevoir un système de chiffrement symétrique soit une fonction courbe pour pouvoir résister de manière optimale aux attaques par corrélation rapides. En plus de cette importance cryptographique, les fonctions courbes ont la propriété fascinante que leurs supports sont des objets combinatoires intéressants. Leurs supports forment des ensembles à différence, appelés ensembles à différence de Hadamard. Parmi les familles de fonctions courbes, il en est une qui pourrait avoir une importance grandissante dans les années à venir : les fonctions hyper-courbes (introduites par Youssef et Gong en 2001). Les fonctions hyper-courbes sont des fonctions courbes qui ont la propriété d'être aussi à distance maximale des permutations polynomiales. Très récemment, il a été mis en lumière que ces fonctions étaient en relation étroite avec des objets géométriques intéressants: les hyperovales. Dans cet exposé, nous présenterons un résumé des résultats les plus importants et de nos apports à l'étude des fonctions booléennes courbes en illustrant les liens possibles entre les fonctions courbes et des objets combinatoires et géométriques cités précédemment. Nous présenterons aussi le lien entre les fonctions courbes et la théorie des codes et plus particulièrement entre certaines fonctions vectorielles courbes et les codes minimaux (dont les propriétés combinatoires peuvent être exploitées par les systèmes de partage de secret).

Considérons une surface orientable S de genre g avec k>0 bords. Plaçons un ensemble E de n points sur S de manière que chaque bord contienne au moins un de ces points. Le graphe des flips de E est le graphe G dont les sommets sont les triangulations de E et dont les arêtes joignent deux triangulations qui peuvent être transformées l'une en l'autre par un flip (cette opération consiste à échanger les diagonales d'un quadrilatère). Le graphe G est connexe. Si on considère les triangulations de E à homéomorphisme près, les sommets de E étant marqués, le diamètre de ce graphe est borné. Lorsque S est un disque dont le bord contient tous les points de E, G est le graphe de l'associaèdre de dimension n-3. Il a été montré récemment que le diamètre de ce graphe est 2n-10 dès que n est supérieur à 12. La preuve de ce résultat sera esquissée. Plusieurs autres résultats sur le diamètre de G seront ensuite donnés et discutés dans le cas où S n'est pas un disque.

The chip firing game is a discrete dynamical model on graphs which was first defined by D. Dhar (1990) and by A. Björner, L. Lovász and W. Shor (1991). The model has various applications in many fields of science such as physics, computer science, social science and mathematics. Recently, this model is used as a tool to study many properties of graphs and it was proved to be related to subjects of graph theory, such as Laplacian matrix, Tutte polynomial, spanning tree or graphic matroid, etc. In this talk, I will present some algebraic structure raised on this model.

En combinatoire des mots finis ou infinis, la nature des motifs qui apparaissent dans un mot donné sont une des nombreuses manières de déterminer sa complexité. Les calculs de diverses statistiques permettent de mettre en évidence certaines relations qu'il vérifie.

Un automate cellulaire probabiliste (ACP) est une chaîne de Markov sur un espace symbolique. Le temps est discret, les cellules évoluent de manière synchrone, et le nouvel état de chaque cellule est choisi de manière aléatoire, indépendamment des autres cellules, selon une distribution déterminée par les états d'un nombre fini de cellules situées dans le voisinage. Je présenterai les résultats obtenus au cours de ma thèse sur deux "problèmes inverses" : le premier consiste à étudier les ACP ayant des mesures invariantes de forme produit de Bernoulli ; le second est le problème de la classification de la densité, qui consiste à trouver un AC(P) dont l'évolution permette de distinguer une configuration initiale sur l'alphabet binaire tirée selon une mesure de Bernoulli de paramètre inférieur ou supérieur à 1/2, et que nous avons résolu sur les grilles de dimension supérieure ou égale à 2 et sur les arbres.

Soit S_w^{(q)} une base construit avec la même relation de réccurence et avec la même condition iniatiale que la base S_w. Soit P_w^{(q)} la base duale de la base S_w^{(q)}. Nous allons montrer qu'une q-déformation de la base de Poincaré-Birkhoff-Witt-Lyndon P_w^{(q)} est aussi multiplicative. Cette deuxième séance sera consacrée à l'examen fin des stastistiques sur le groupe symétrique induite par la q-shuffle et au conditions suffisantes de multiplicativité des bases.

Nous étudions l’énumération de deux familles de polycubes, les pyramides et les espaliers, en lien avec une version multi-indexée de la convolution de Dirichlet.

I'll discuss the history of work on the question of how and whether rationality of growth depends on generators. That is, for a finitely generated group, one can study the growth function (the number of words spellable in up to n letters) and its growth series, the associated generating function. This growth series is itself a rational function when there is a recursive relationship among the values of the growth function. It is known that all virtually abelian groups and all hyperbolic groups have rational growth in any generators, by work of Benson and Cannon respectively. Work of Shapiro and of Stoll sheds some light on the situation in nilpotent groups, but shows it to be more complicated-- even for the second Heisenberg group H_5, some generators give rational growth but others do not. I'll describe work in progress with Shapiro giving geometric arguments to establish rationality in all generators for the classical Heisenberg group H_3.

Soit S_w^{(q)} une base construite avec la même relation de réccurence et avec la même condition iniatiale que la base S_w, mais en utilisant une déformation du shuffle. Soit P_w^{(q)} la base duale de la base S_w^{(q)}. Nous allons proposer une démonstration du fait que cette q-déformation de la base de Poincaré-Birkhoff-Witt-Lyndon P_w^{(q)} est aussi multiplicative.

Soit s une permutation dans Sigma_n. Soit i(s)=s(1), j(s)=s^{-1}(1), Soit C_k le cycle 1>2>...>(k-1)>1 (k,k+1,..,n points fixes). On definit L et R comme suit: L(s) = C_{j(s)}.s et R(s) = s.C_{i(s)}^{-1} Il est facile de voir que L et R sont inversibles, la dynamique L/R partitionne donc Sigma_n en classes d'équivalence qui sont des graphes orientés uniformes (une arête entrant/sortant par "couleur" L et R) fortement connexes. Dans cet exposé, on étudiera ces classes : leur nombre, leur taille, leur structure, etc.

One of the main motivation of S.Fomin and A.Zelevinsky for introducing cluster algebras was the desire to provide a combinatorial framework to understand the structure of ''dual canonical bases'' in coordinate rings of various algebraic varieties related to semisimple groups. For a finite cluster algebra, they show that the cluster complex can be implemented as a simplical fan in the vector space span by the simple roots of the corresponding Lie algebra. We show that the cluster complex for cluster algebra of the base affine space for GL(n) can be implemented as a simplicial fan in the space span by interval one-column semistandard Young tableaux filled in the alphabet {1,...,n}. For n>6, such a fan contains infinitely many cones and its support covers semistandard Young tableaux corresponding to real elements of the dual canonical basis. For types ADE, cluster complexes of the corresponding finite cluster algebras are subfans of our cluster complex with appropriate n's.

Une sémantique dénotationelle interprète les types de données (comme Bool ou Int) par des espaces mathématiques (posets, treillis, structures algébriques) et les programmes par des fonctions sur ces espaces. L'intérêt d'une telle interprétation étant de donner une description du comportement opérationnel des programmes qui fait abstraction du langage dans lequel les programmes sont écrits. Les sémantiques quantitatives sont en particulier les sémantiques dénotationelles issues de la logique linéaire, où les types de données sont interprétés par des espaces vectoriels (ou, plus généralement, des modules), les programmes qui utilisent exactement une fois leurs données d'entrée deviennent des fonctions linéaires (au sens algébrique), alors que les programmes qui utilisent leurs ressources un nombre indéterminé de fois (comme les programmes récursifs ou les programmes utilisant l'instruction while, par exemple) sont interprétés par des fonctions analytiques, approximables par des polynômes, qui représentent des calculs partiels. Ces sémantiques sont particulièrement naturels pour décrire des programmes non-déterministes, voire probabilistes ou quantiques, l'addition exprimant une sorte de superposition des états élémentaires et les scalaires associant une estimation quantitative à une telle superposition. Dans cet exposé, je chercherai à donner une intuition de l'interprétation des programmes via quelques exemples de sémantiques quantitatives et à donner un aperçu des résultats récemment obtenus, en particulier dans le cadre des langages fonctionnels probabilistes.

Les algèbres PSH sont des algèbres de Hopf (sur les rationnels ou les réels) autoduales qui ont une base pour laquelle les constantes de structures sont positives. Le premier exposé sera consacré à quelques résultats de structure, et le deuxième à l'usage que Zelevinsky a fait de ces algèbres en théorie des représentations.

Cet exposé donnera un aperçu du domaine de recherche accessible et dynamique des permutations à motifs exclus, tout en illustrant dans ce cadre les interactions fructueuses existantes entre combinatoire et algorithmique. Un outil clé présenté sera la décomposition par substitution des permutations, qui est un exemple de décomposition récursive d'objets discrets utile tant sur le plan combinatoire qu'algorithmique, et qui fait partie du même cadre général que la décomposition modulaire des graphes. Une telle décomposition permet de mettre en évidence la structure des objets étudiés, et de l'exploiter afin d'obtenir des résultats de nature énumérative, des algorithmes de génération aléatoire, ou des algorithmes de décision.

La repr\'esentation int\'egrale des polylogarithmes, pour $|z|<1$, $${\rm Li}_{s_1,\ldots,s_r}(z)=\sum_{n_1>\ldots>n_r}\frac{z^{n_1}}{n_1^{s_1}\ldots n_r^{s_r}},$$ permet de le prolonger analytiquement sur ${\mathbb C}^r$. Aux entiers n\'egatifs, ils sont devenus des fonctions rationnelles en $z$ $${\rm Li}_{-s_1,\ldots,-s_r}(z)=\sum_{n_1>\ldots>n_r} n_1^{s_1}\ldots n_r^{s_r} z^{n_1}\in{\mathbb C}[z,1/z,1/(1-z)]$$ dont le d\'eveloppement de Laurent, en $z=1$, conduisent aux poly-Bernoulli.

Je m'intéresse à l'espérance de polynômes en des variables aléatoires tensorielles distribuées selon une gaussienne. Je présenterai brièvement une famille de polynômes dont les espérances comptent des nombres de systèmes de méandres, puis je discuterai en détail cette famille de méandres. Un méandre étant vu comme un collage de deux systèmes d'arches, il s'agit ici de méandres étiquetés par une permutation qui détermine un système d'arches à partir de l'autre. Je montrerai que le nombre de méandres étiquetés par une permutation donnée se décomposent naturellement en méandres irréductibles, étiquetés par des permutations qui ne stabilisent aucun sous-interval (Stabilized-Interval-Free permutations).

Using cluster transformations we design subtraction-free algorithms for computing Schur functions and their skew, double and supersymemtric analogues, for generating spanning trees and arborescences polynomials. The latter provides an exponential complexity gap between circuits admitting arithmetic operations +, x, / versus +, x. In addition, we establish an exponential complexity gap between circuits admitting +, -, x, / versus +, x, /. Together with V. Strassen's result on "Vermeidung von Divisionen" this closes a long-standing problem on comparative complexity power between all possible subsets of operations +, -, x, /. (joint work with S. Fomin and D. Grigoriev)

Dans cet exposé, on introduit deux familles de polycubes : les pyramides et les espaliers. On calcule les séries génératrices ordinaire et de Dirichlet de ces objets à l'aide d'une version multi-indexée de la convolution de Dirichlet. On s'intéresse ensuite à une généralisation des pyramides et des espaliers en dimension d quelconque et on montre que le nombre de pyramides de volume fixé en dimension d+1 est un polynôme en d. On explique enfin comment appliquer les techniques mises en œuvre ici à d'autres familles de polycubes.

Soit S_w^(q) une base construite avec la même relation de récurrence et avec la même condition initiale que la base S_w. Soit P_w^(q) la base duale de la base S_w^(q). Nous allons montrer que cette q-déformation de la base de Poincaré-Birkhoff-Witt-Lyndon P_w^(q) est aussi multiplicative.

Les pavages auto-assemblants sont un modèle de formation de structures moléculaires, dans lequel on peut simuler des machines de Turing. Il s'agit essentiellement d'une modification des tuiles de Wang, où l'on rajoute un mécanisme de formation des pavages. Je présenterai dans cet exposé deux résultats de séparation entre deux variantes de ce modèle : le modèle coopératif, où certaines tuiles ne peuvent s'assembler avec le reste du pavage que si plusieurs de leurs côtés correspondent, et le modèle non-coopératif, où toutes les tuiles peuvent s'assembler si au moins un de leurs côtés correspond.

Une triangulation est un graphe (planaire, fini connexe) dessiné proprement dans la sphère de dimension 2 dont toutes les faces sont des triangles. On considère une triangulation aléatoire T_n choisie uniformément dans l'ensemble de toutes les triangulations à n faces. La structure métrique de T_n munie de la distance de graphe a été étudiée en profondeur récemment. En particulier, Le Gall (voir aussi Miermont) a prouvé que T_n renormalisée par n^{-1/4} converge vers une surface aléatoire fractale appelée la carte brownienne. Dans cet exposé nous nous intéresserons à un autre aspect des triangulations aléatoires. En effet, $T_n$ peut naturellement être munie d'une structure de surface de Riemann et l'on peut ainsi étudier sa "structure conforme" qui est censée être très liée au champs libre gaussien en dimension 2. Je présenterai un chemin pour l'étude de cette structure conforme fondé sur l'exploration markovienne des cartes planaires à l'aide d'un processus SLE_6.

Je parlerai de modèles de pavages par dominos de certaines régions du plan que nous appelons les «pavages pentus». Ces modèles contiennent plusieurs classes de pavages pour lesquelles des propriétés remarquables (énumératives et probabilistes) avaient été obtenues, notamment le «diamant aztèque» et les «partitions pyramides». Nous élucidons leur structure combinatoire en les mettant en correspondance avec des suites de partitions entrelacées, faisant ainsi le lien avec les «processus de Schur» introduits par Okounkov et Reshetikhin. La méthode permet non seulement une compréhension unifiée des formules d'énumération, et leur généralisation à une famille infinie de modèles, mais également le calcul de fonctions de corrélation entre particules, ouvrant potentiellement la voie à l'étude unifiée des formes limites (théorèmes de type «cercle arctique»). Notre point de vue conduit par ailleurs à des algorithmes plaisants de génération aléatoire. L'exposé contiendra de nombreuses illustrations et peut-être même une applet java. Aucun pré-requis n'est nécessaire. (Travail commun avec Jérémie Bouttier et Sylvie Corteel)

Cet exposé présentera un panorama partiel et quelques résultats récents sur le comportement asymptotique (moyenne, variance, lois limites) dans certains problèmes de plus longue sous-suite croissante et/ou commune.

Les arbres de coalescence utilisés en phylogénétique sont naturellement construits depuis les feuilles. Nous posons la question d'une description de ces arbres depuis la racine. Parmi les arbres de coalescence, les Beta coalescents constituent une classe d'étude favorite, et des liens récents avec certaines classes d'arbres combinatoires (arbres récursifs et arbres binaires) ont récemment permis d'en améliorer la compréhension. Nous commencerons par rappeler ces constructions alternatives, dues respectivement à Goldschmidt et Martin, et Abraham et Delmas. Nous présenterons ensuite notre propre contribution, basée sur la représentation dite "lookdown".

Frequent string mining is the problem of finding frequently appearing strings in a given string database or large text. It has many applications to string data analysis on strings such as texts, word sequences, and genome sequences. The problem becomes difficult if the string patterns are allowed to match approximately, i.e., a fixed number of errors leads to an explosion in the number of small solutions, and a fixed ratio of errors violates the monotonicity that disables hill climbing algorithms, and thus makes searching difficult. There would be also a difficulty on the modeling of the problem; simple mathematical definitions would result explosion of the solutions. To solve this difficulty, we go back to the motivations to find frequent strings, and propose a new method for generating string patterns that appear in the input string many times. In the method, we first compute the similarity between the strings in the database, and enumerate clusters generated by similarity. We then compute representative strings for each cluster, and the representatives are our frequent strings. Further, by taking majority votes, we extend the obtained representatives to obtain long frequent strings. The computational experiments we performed show the efficiency of both our model and algorithm; we were able to find many string patterns appearing many times in the data, and that were long but not particularly numerous. The computation time of our method is practically short, such as 20 minutes even for a genomic sequence of 100 millions of letters.

A hypergraph F is a set family defined on vertex set V. The dual of F is the set of minimal subsets H of V such that J \cap H \ne \emptyset for any J in F The computation of the dual is equivalent to many problems, such as minimal hitting set enumeration of a subset family, minimal set cover enumeration, and the enumeration of hypergraph transversals. In this paper, we introduce a new set system induced by the minimality condition of the hitting sets, that enables us to use efficient pruning methods. We further propose an efficient algorithm for checking the minimality, that enables us to construct time efficient and polynomial space dualization algorithms. The computational experiments show that our algorithms are quite fast even for large-scale input for which existing algorithms do not terminate in practical time.

I will discuss the cartographic machinery (encoding of maps on surfaces by permutations) on unoriented surfaces. I will discuss how these appear in calculations with real and quaternionic random matrices, and their connections with other combinatorial objects associated with these objects, such as the hyperoctahedral group and matricial cumulants. I will present some results in asymptotic second-order freeness which may be approached using these objects.

Melonic graphs constitute the family of graphs arising at leading order in the 1/N expansion of tensor models. They were shown to lead to a continuum phase, reminiscent of branched polymers. We show here that they are in fact precisely branched polymers, that is, they possess Hausdorff dimension 2 and spectral dimension 4/3.

After providing some background and motivation for random tensor models and their large N expansion, I will discuss recent results on the next-to-leading order of the large N expansion for the multi-orientable tensor model. I will describe the class of Feynman tensor graphs contributing to this order in the expansion, and the characteristic properties of the next-to-leading order series for this model. These results represent the first step towards the larger goal of defining an appropriate double-scaling limit for the multi-orientable tensor model.

Regular colored graphs are dual representations of pure colored D-dimensional complexes. These graphs can be classified with respect to an integer, their degree, much like maps are characterized by the genus. We analyse the structure of regular colored graphs of fixed positive degree and perform their exact and asymptotic enumeration. In particular we show that the generating function of the family of graphs of fixed degree is an algebraic series with a positive radius of convergence, independant of the degree. We describe the singular behavior of this series near its dominant singularity, and use the results to establish the double scaling limit of colored tensor models.

The theory of Gaussian multiplicative chaos enables to make sense of random measures defined formally by the exponential of a Gaussian Free Field (and more generally any logarithmically correlated field in all dimensions). These random measures are conjectured to be the scaling limit of random planar maps coupled to a CFT and conformally mapped to the sphere or the upper half plane. The construction of the measures involve a parameter gamma related to the central charge c of the CFT. The classical construction does not settle the question of constructing the measure for c=1 or equivalently gamma=2 as it yields a vanishing measure. In this talk, I will explain the appropriate construction and some properties of Gaussian multiplicative chaos at criticality, i.e. for gamma=2. If time permits, I will also explain the construction of the dual measure (gamma larger than 2) and how to make sense of the KPZ equation in this context.

Je commencerai par introduire le concept de S-coloriage de graphe : étant donné un sous-ensemble S(v) de voisins de v pour tout sommet v d'un graphe G, c'est un coloriage propre des sommets de G tel que, en outre, les sommets qui appartiennent ensemble à un même S(v) pour un sommet v reçoivent des couleurs différentes. Ceci généralise à la fois le concept de coloriage du carré de graphe et le coloriage cyclique des graphes plongés.
Je présenterai un résultat structurel fort pour les graphes plongés dans une surface fixe, qui permet par exemple de démontrer que la taille maximum d'une clique dans le carré d'un tel graphe de degré maximum D est au plus 3D / 2 plus une constante.
En utilisant ce résultat de structure, le S-coloriage d'un graphe plongé peut se réduire au coloriage d'arêtes d'un multigraphe. Je donnerai ensuite un aperçu général du travail de Jeff Kahn sur arête-coloriage d'un multigraphe H, basé sur l'utilisation des distributions hardcores sur les couplages, définies par des points à l’intérieur du polytope des couplages de H.
En combinant ces résultats, on peut établir un résultat général sur le S-coloriage des graphes plongés, impliquant notamment les versions asymptotiques des conjectures de Wegner et de Borodin sur le coloriage du carré et le coloriage cyclique des graphes planaires. Mon exposé est basé sur un travail en commun avec L. Esperet et J. van den Heuvel.

Metric properties of random maps (graphs embedded in surfaces) have been subject to a lot of recent interest. In this talk, I will review a combinatorial approach to these questions, which exploits bijections between maps and some labeled trees. Thanks to an unexpected phenomenon of ``discrete integrability'', it is possible to enumerate exactly maps with two or three points at prescribed distances, and more. I will then discuss probabilistic applications to the study of the Brownian map (obtained as the scaling limit of random planar maps) and of uniform infinite planar maps (obtained as local limits). If time allows, I will also explain the combinatorial origin of discrete integrability, related to the continued fraction expansion of the so-called resolvent of the one-matrix model. Based on joint works with E. Guitter and P. Di Francesco.

We are focusing on the approach by noncommutative formal power series in order to study combinatorial aspects of the renormalization of solutions of nonlinear differential equations with three regular singularities involved in QED (quantum electrodynamics).

Un associaèdre est un polytope dont les sommets correspondent aux triangulations d'un polygone convexe et dont les arêtes correspondent aux flips entre ces triangulations. J.-L. Loday en a donné une réalisation particulièrement élégante qui a été généralisée ensuite dans deux directions : d'un côté par C. Hohlweg et C. Lange pour obtenir de multiples réalisations de l'associaèdre paramétrées par une séquence de signes, et de l'autre par A. Postnikov pour obtenir une réalisation des associaèdres de graphes de M. Carr et S. Devadoss. Le but de cet exposé est de présenter une généralisation commune de ces constructions aux associaèdres d'arbres signés. Nous présenterons aussi les riches propriétés combinatoires et géométriques des polytopes qui en résultent. L'exposé sera illustré par le cas de l'associaèdre classique, dont l'interprétation en termes d'épine dorsale (arXiv:1307.4391, travail en commun avec C. Lange) est le fil directeur de ce travail.

We will investigate the probability distribution on the set of Boolean functions in n variables if a Boolean function is generated by a large Boolean expression drawn uniformly at random from all expressions of the same size. We show that a precise quantitative relation between the probability of a function and its complexity which is defined as the minimal size of an expression representing the function.

Une bien triste nouvelle, ce 19 octobre, Alain Lascoux nous a quitté. Formé comme un spécialiste de géométrie algébrique, puis collaborateur de Marcel-Paul Schützenberger, il avait consacré toute sa vie de chercheur à mettre au jour et à exploiter algorithmiquement les aspects combinatoires de certaines questions d'algèbre, de théorie des représentations et de géométrie. Plusieurs membres de l'équipe l'ont longuement côtoyé, à Jussieu, à Marne-la-Vallée ou pendant les réunions semestrielles du Séminaire Lotharingien de Combinatoire ; nous ne pouvons que dire que samedi dernier, la combinatoire algébrique a perdu un de ses maîtres, et avec lui un peu de ses couleurs et de son mordant. Nous dédions notre traditionnelle séance du séminaire de l'équipe CALIN (dont Alain fut l'un des parrains scientifiques) à sa mémoire.

Il existe des égalités inattendues autour du rang d'une suite unimodale, telle que U(1,5,5n+3) = U(2,5,5n+3), où U(t,m,n) est le nombre de suites unimodales de poids n avec rang congru à t modulo m. De telles égalités rappellent celles pour le rang d'une partition qui ont été observées par F. Dyson et qui sont liées aux formes modulaires et mock modulaires. Dans le cas des suites unimodales, il n'y a pas cette structure modulaire ; la démonstration dépend d'une identité de fonctions thêta partielles due à Ramanujan. Ceci est un travail en commun avec B. Kim (Séoul).

We strengthen the theorem that establishes that deterministic finite transducers can not compress normal infinite words. We prove that, indeed, non-deterministic finite transducers, even augmented with a fixed number of counters, can not compress normal infinite words. However, there are push-down non-deterministic transducers that can compress normal infinite words. We also obtain new results on the preservation of normality with automata selectors. Complementing Agafonov's theorem for prefix selectors, we show that suffix selectors also preserve normality. However, there are simple two-sided selectors that do not preserve normality.

Étude de chaînes de Markov à l'aide de représentations de monoïdes

La théorie des représentations des groupes finis est un sujet classique. Dans le cadre plus général des monoïdes finis, la théorie est plus récente et a priori plus complexe. Cependant il existe des classes de monoïdes où, comme pour les groupes, la théorie se simplifie et fait surgir de la combinatoire, ce qui ouvre la porte à des applications.

Dans cet exposé, nous présenterons brièvement les éléments de la théorie en mentionnant quelques développements algorithmiques récents [1], et décriront une application typique à l'étude d'une chaîne de Markov sur des tas de sable à écoulement orienté [2]. La démarche exploratoire sera illustrée par quelques calculs typiques avec le logiciel Sage.

Refs:
- [1] Cartan invariant matrices for finite monoids
http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewArticle/dmAR0178
- [2] arXiv:1305.1697: Directed nonabelian sandpile models on trees
Ayyer, Schilling, Steinberg, T.

The Ben Geloun-Rivasseau quantum field theoretical model is the first tensor model shown to be perturbatively renormalizable. We define here an appropriate Hopf algebra describing the combinatorics of this new tensorial renormalization. The structure we propose is significantly different from the previously defined Connes-Kreimer combinatorial Hopf algebras due to the involved combinatorial and topological properties of the tensorial Feynman graphs. In particular, the 2- and 4-point function insertions must be defined to be non-trivial only if the superficial divergence degree of the associated Feynman integral is conserved.

The set of hypertrees on n vertices can be endowed with a poset structure. This poset has been used by McCammond and Meier to study the group of motions of the trivial link, which is an analogue of the braid group. They also proved that this poset is Cohen-Macaulay and computed the dimension of its only homology group. After a short introduction on this topological context, we explain how we used the theory of species to compute the action of the symmetric group on this homology group. We then link it with the PreLie operad.

Kontsevich proved that the Lie homology of symplectic Hamiltonians can be encoded as the homology of a Hopf bialgebra of graph complex attached to the commutative world. In this talk we will see some generalisation of this theorem : commutative world being replaced by operad, symplectic by a classical group, and we can consider Lie homology or its lifting to Leibniz homology.

There is a well-known natural functorial construction which, from a set-operad, produces a Hopf algebra. We extend this construction to the category of PROs with some extra properties. By this generalization, we retrieve, among other, the Hopf algebra of noncommutative symmetric functions in various bases and the noncommutative Faà di Bruno Hopf algebra. We also obtain new ones, as some Hopf algebras involving forests, heaps of pieces, and some kinds of combinational circuits. All these Hopf algebras are similar in a sense to the Connes-Kremier Hopf algebra. In this talk, we shall recall some background about PROs, then present the construction associating a Hopf algebra with a PRO, and finally, review some examples of applications.

Un jeu de tuiles de Wang est un ensemble fini de carrés unités dont on a colorié chaque côté. Un jeu de tuiles T pave le plan si celui-ci peut être recouvert par des translatés de copies d'éléments de T (selon Z^2), de sorte que les arêtes en contact de deux tuiles adjacentes soient de même couleur. Un jeu de tuiles est dit apériodique s'il pave le plan mais si aucun pavage obtenu n'est invariant par une translation. La plupart des jeux de tuiles apériodiques sont construits de façon autosimilaire (via une règle de substitution). Le but de cet exposé est d'introduire des invariants permettant de quantifier le niveau d'apériodicité d'un jeu de tuiles de Wang. L'un des invariants est de nature topologique, l'autre est métrique. Ils reposent sur la manière dont le jeu de tuiles pave d'autres objets que le plan. Ces invariants nous permettent de démontrer que les jeux de tuiles de Kari et Culik ne sont pas gouvernés par une construction autosimilaire, car trop apériodiques.

Une sous-classe importante des fonctions holonomes est la classe des G-fonctions (définie par Siegel), qui jouent notamment un rôle important en théorie des nombres, en physique et en combinatoire. Une grande question, qui demeure en partie ouverte, est de comprendre de façon fine la structure de l'ensemble des valeurs prises par ces fonctions en des points algébriques. Ces valeurs englobent de célèbres constantes mathématiques, comme pi, les polyzêtas, des valeurs de fonctions hypergéométriques... Nous montrerons le résultat suivant : toute valeur en un point algébrique d'une G-fonction peut s'écrire f(1), où f est une G-fonction à coefficients rationnels dont le rayon de convergence peut de surcroît être choisi arbitrairement grand. On démontre aussi d'autres propriétés de ces valeurs de G-fonctions ; par exemple les constantes de connexion obtenues en prolongeant des G-fonctions sont de tels nombres. Il s'agit d'un travail en commun avec Tanguy Rivoal, dédié à la mémoire de Philippe Flajolet.

It is now sure that one can show a version of the CQMM theorem which holds even in presence of heavy torsion. However the arrow constructed from the enveloping algebra of the primitive elements may not be into. There is a strange connection between the counter-example given on Mathoverflow and the q-infiltration product discovered by Luque et al.

Starting from a slightly more abstract definition of Hopf algebras as usual, we present a method towards solutions of universal constructions for Hopf algebras (as, e.g., existence of free and cofree ones). On doing so we propose the use of results of category theory, not just of categorical language.
The talk, however, will be non-technical in this respect. Only elementary knowledge of categorical language will be expected.

10h30 Aline Parreau (LIFL) Une preuve combinatoire du lemme local de Lovasz
11h45 Julien David (LIPN) & Yann Ponty (LIX) présentation de RDos (Random Discrete Objects Suite): un ensemble d'outils pour la génération aléatoire d'objets combinatoires
12h30 Buffet en salle A201
14h Mathieu Raffinot (LIAFA) Nouvelles avancées dans la recherche de motifs uniques ou consécutifs dans des permutations travail en commun avec D.l Belazzougui (Univ. of Helsinki), A. Pierrot (LIAFA) et S. Vialette (LIGM)
15h15 Axel Bacher (LIPN) Génération aléatoire d'arbres en taille exacte et linéaire en temps et en espace
16h15 Discussion : bilan et perspectives après 30 mois

Non-intersecting Brownian motions (BMs) have been the subject of numerous studies both in mathematics and in physics. In addition to their deep connection with random matrix theory, It was shown that they are at the heart of many fundamental models of statistical physics, like stochastic growth models or directed paths in random media. In this talk I will review some  recent results which we have obtained for the extreme statistics, like the maximal height, of such non-intersecting BMs.   
Les marcheurs Browniens conditionnés à ne pas se croiser ont suscité beaucoup d'intérêt ces dernières années, tant en mathématique (pour leurs aspects probabilistes et combinatoires) qu'en physique (comme des modèles de polymères ou de transition de mouillage ou de fusion). Dans cet exposé je présenterai un calcul exact de la distribution de la hauteur maximale d'une collection de N ponts Browniens (appelés 'watermelons without wall') et de N excursions Browniennes (appelées 'watermelons with a wall') conditionnés à ne pas se croiser. Je montrerai que dans la limite asymptotique où N tend vers l'infini cette distribution converge vers la distribution de Tracy-Widom qui décrit les fluctuations de la plus grande valeur propre de matrices aléatoires de l'ensemble gaussien orthogonal (GOE pour 'Gaussian Orthogonal Ensemble'). Je discuterai enfin une application de ces résultats asymptotiques à des modèles de croissance stochastique.

Le théorème de Roth établit que pour tout a>0, il exite un entier N tel que tout sous-ensemble de {1,...,N} de cardinal au moins aN contient une progression arithmétique de longueur 3 (un ensemble de la forme {x,x+r,x+2r} avec x et r des entiers non nuls). Plusieurs autres théorèmes importants de combinatoire additive concernent les progressions arithmétiques, comme le théorème de Szemeredi ou celui de Green-Tao. Après une introduction à la combinatoire additive, nous présenterons une généralisation du théorème de Roth aux "d-configurations" (ensembles de la forme {x_i+x_j+a|1<=i<=j<=d}, avec x_1,...,x_d et a des entiers) et nous étudierons son application aux sous-ensembles sans somme.

Un code identifiant d'un graphe est un sous-ensemble C de sommets qui est à la fois dominant (tout sommet du graphe a un voisin dans C ou appartient à C) et séparant (tous les sommets ont un voisinage distinct à l'intérieur de C). Dans cet exposé, nous faisons un tour d'horizon de quelques résultats sur cette notion. Nous proposons une caractérisation des graphes qui ont le code minimum de taille n-1, n étant l'ordre du graphe. Également nous nous intéressons à ce paramètre dans la classe des graphes adjoints. Si le temps le permet, nous parlerons de la complexité du problème dans différentes sous-classes des graphes parfaits.

Les polynômes symétriques jouent, depuis toujours, un rôle assez important en physique. Par exemple, il est connu que la « fonction génératrice » du modèle à 6 vertex (remarquablement, ce modèle est en bijection avec les matrices à signes alternants) est un polynôme de Schur. Plus récemment, on a découvert, que la « fonction génératrice » d'une généralisation de ce modèle est aussi un polynôme symétrique, plus précisément, un polynôme de Macdonald.

Certaines approches à la gravité quantique reposent sur une construction combinatoire de l'intégrale fonctionnelle.
Une question centrale dans ce contexte est de savoir comment incorporer, ou éventuellement retrouver dans un régime approprié, les symétries de la théorie classique (invariance par difféomorphismes).
Je présenterai certains aspects mathématiques de ce problème, que j'examinerai sous deux angles complémentaires :

• le point de vue des invariants dits de "state sum", où les difféomorphismes de la variété sont remplacés par certaines opérations combinatoires sur des triangulations (mouvements de Pachner).
• le point de vue des modèles de matrices, où l'invariance par difféomorphismes est le résultat de la sommation sur une certaine classe de graphes associés à des triangulations.

Le théorème (classique) de Cartier-Quillen-Milnor-Moore (CQMM) dit que, en caractéristique zéro, une bigèbre est l'algèbre enveloppante de ses éléments primitifs si et seulement si elle est filtrée positivement.
Dans le but de poursuivre l'étude de l'arithmétique de certaines fonctions spéciales, il est nécessaire d'étendre ce résultat aux situations où les éléments primitifs n'ont plus nécessairement de base.
Nous donnons une preuve nouvelle du théorème de CQMM classique utilisant la combinatoire des idempotents eulériens et les fonctions symétriques noncommutatives ainsi que des applications combinatoires récentes du CQMM.

Journée inaugurale du pôle MATHSTIC :

3 laboratoires de l'Institut Galilée (Le LAGA, le LIPN, et le L2TI) s'associent pour proposer une journée inaugurale du POLE MATHSTIC, le 18 avril de 9h30 à 17h30 en Amphi A.

9h30 Accueil
9h45 Présentation du pôle (C. Fouqueré) Mots de C. Desfrançois VPCS et F. Dibos Directrice de l'institut Galilée
10h Présentation de l'axe 2 (L. Halpern) Architectures émergentes et passage à l'échelle d'applications parallèles (C. Coti) Déploiement de réseaux sans fil (N. Achir ) Méthodes de décomposition de domaine espace-temps (C. Japhet) Calculs performants pour la simulation d'écoulements à fronts raides (F. Benkhaldoun)
12h Buffet (salle M100 de l'IUT)
13h15 Présentation de l'axe 3 (A. Sportiello) Mots circulaires (B. Rittaud) Physique combinatoire : algèbres de Hopf - combinatoires en théories quantiques de champs (A. Tanasa) Combinatoire et aléas (P. Marchal)
15h15 pause café
15h30 Présentation de l'axe 1 (R. Wolfler-Calvo) Les algorithmes de flots à la rescousse (L. Létocart) Compression d'images avec contrôle de qualité : au delà ( B. Matei) Améliorer la mobilité grâce aux Systèmes de Transport Intelligents (K. Boussetta)
17h30 fin

Un semi-groupe numérique est une partie de N stable par addition et de complément fini. D'apparence simple, ces objets conduisent à de nombreux problèmes : problème de Frobenius (ou de rendu de monnaie), conjecture de Wilf, ... Les semi-groupes numériques peuvent être regroupés par genre, le genre d'un semi-groupe numérique étant le cardinal de son complémentaire dans N. Une question naturelle est alors de déterminer le nombre de semi-groupes numériques de genre donné. Les valeurs de n_g ont été calculés par Maria Bras Amoros pour g<=52. Sur sa page web, Manuel Delgado donne la valeur de n_55. Dans cet exposé, après une introduction aux semi-groupes numériques, nous présenteront différentes optimisation algorithmiques permettant d'améliorer les résultats de Maria Bras Amoros et Manuel Delgado.

On cherche à énumérer des pavages par dominos d'une région obtenus par flip à partir d'un pavage minimal unique. Pour cela, on utilise les diagrammes maya, les "vertex operators" et les fonctions de Schur supersymétriques. On obtient des formules type "équerre" ; dont des cas particuliers compte les pavages du diamant aztèque ou les partitions pyramides de Ben Young. [Travail en commun avec Jérémie Bouttier et Guillaume Chapuy)]

I will talk about families of triangulations of manifolds in arbitrary dimensions which can be represented by multi-graphs with colored edges. I will focus on an important family of such triangulations, called melonic triangulations, which controls the behavior of integrals over random tensors (a promising approach to quantum gravity). These integrals can be solved by an exact counting of the melonic triangulations. If time permits, I will describe the relation to loop models on random planar maps, and also an interesting family of colored triangulations related to meanders.

Cellular complexes are often used in physics as discretizations of spacetime. An interesting class of amplitudes associated to those complexes are topological invariants. I will present a simple model which relates an integral over some Lie group elements associated to the edges of the complex to the so called combinatorial, or Reidemeister torsion of the complex.

Au cours de cet exposé, je définirai des nouveaux objets combinatoires, les arbres non-ambigus. Ces objets peuvent être vus comme des arbres dessinés sur une grille sous certaines contraintes et ils sont liés à plusieurs objets combinatoires, comme les polyominos parallélogrammes et les tableaux boisés définis par Aval, Boussicault et Nadeau. L'on verra comment l'énumération des arbres non-ambigus satisfaisant des contraintes supplémentaires permet de donner des preuves combinatoires élégantes d'identités dues à Carlitz, et à Ehrenborg et Steingrìmsson. Je montrerai aussi une formule des équerres pour le comptage des arbres non-ambigus dont l'arbre sous-jacent est fixé. Enfin, je utiliserai les arbres non-ambigus pour décrire une bijection très naturelle entre polyominos parallélogrammes et arbres binaires.

I will survey the techniques used to get asymptotic results for subfamilies of planar graphs, as well as how to relate this methodology with the context of map enumeration. In the second part of the talk, I will explain the ideas behind some on-going projects related to the enumeration of bipartite subfamilies of graphs.

We expose the reformulation of the Jacobian conjecture in terms of the combinatorics of Feynman diagrams of a certain Quantum Field Theory. We will also discuss considerations about Dixmier conjecture and Noncommutative Quantum Field Theory.

By using Kirillov's orbits method and Weyl-type quantization on the Heisenberg supergroup, we construct a non-formal deformation quantization of superspaces. We are led by the theory to introduce new notions such as Hilbert superspaces and C*-superalgebras. Then, a noncommutative superspace coming from this deformation yields an interpretation of the renormalizable quantum field theory with harmonic term on the Moyal space.

Une algèbre A est localement semi-simple si c'est la limite inductive d'une chaîne d'algèbres semi-simples de dimension finie A_n. On associe à A un graphe gradué (appelé diagramme de Bratteli), qui se construit facilement à partir de la décomposition de chaque A_n en somme directe d'algèbres (pleine) de matrices. Les diagrammes de Bratteli jouent un rôle de premier plan dans la théorie algébrico-combinatoire des algèbres localement semi-simples. Je présenterai quelques résultats fondamentaux de cette théorie.

Le modèle des promeneurs vicieux (sic!) a été introduit par Michael Fisher en mécanique statistique en 1984. De nombreuses variantes ont été étudiées depuis, en particulier celle que je condidère dans mon exposé : lorsque qu'il y a une interaction entre ces promeneurs et un mur. Ce modèle a été originellement proposé par Owczarek, Essam et Brak, qui ont établi quelques résultats partiels. Je montrerai comment complètement déterminer le comportement asymptotique de la fonction de partition correspondante (et celle d'un autre paramètre pertinent). Nous rencontrerons comme de bien entendu (attendu!) mes chers amis : déterminants, une bijection de tableau et des séries hypergéometriques.

En lien avec les multizetas qui généralisent la fonction zeta de Riemann en plusieurs dimension, il existe deux autres familles apparentées et naturelles : les multizetas de Hurwitz et les multitangentes. Alors que les multizetas sont des nombres, les multizetas de Hurwitz et les multitangentes sont des fonctions méromorphes sur C.
Nous présenterons une vue d'ensemble des liens important unissant ces objets, des résultats connues et de ce que l'on peut espérer obtenir à terme.
Nous présenterons notamment les derniers résultats d'un travail en cours sur les multizetas de Hurwitz, à savoir leur indépendance linéaire sur le corps des fractions rationnelles.

Nous présenterons la théorie de Galois différentielle appliquée aux équations différentielles à coefficients polynomiaux puis aux équations aux différences. On montrera ensuite comment calculer ces groupes de Galois, et quels sont les algorithmes disponibles. On présentera alors les méthodes disponibles pour résoudre ces équations en introduisant les fonctions liouviliennes. Enfin nous appliquerons ces méthodes pour l'analyse du comportement asymptotique des solutions : le groupe de Galois donne en particulier des relations algébriques a priori sur les constantes apparaissant dans ces développements asymptotiques, et permettent dans le cas liouvillien de les expliciter.

This small account aims at presenting a project which deals with combinatorial aspects of Quantum Mechanics (or Physics).
This project brings together specialists in Mathematics, Informatics and Physics.
The general subjects are: Hopf algebras, representation theory, deformations, discrete operators and evolution equations.
Since the accomplishment of Connes and Kreimer, the Hopf algebras entered Physics as an efficient tool to solve or to render compact computation problems of composition and decomposition. As many of these Hopf algebras are defined by diagrams (the language of R. Feynman), the problem of implementing them in order to compute at a high order induces many fundamental questions (polynomial realizations, data structures, finite orbits, etc.). These are indeed the problems of (multiple) indexation which appear in ``special sums'' like MZV, EZS, Jack polynomials, MacDonald polynomials or in geometric problems like the combinatorial presentation of Schubert cycles, combinatorics of flag manifolds, or the computation and measure of entangled states.
Quantum Mechanics rests almost entirely on commutation relations (of Heisenberg-Weyl type or deformed) and on evolution equations which give new insights respectively for orthogonal polynomials and for exact solutions of Fokker-Planck or non-commutative evolution equations ($KZ_n$).
The strength of the project relies not only on its scientific unity but also on a well coordinated team scattered among several communities. The qualities and complementarity of the different centers will be commented throughout this small talk.

In this talk I will introduce Grassmann variables and the basic rules of Grassmann-Berezin calculus. I will then show how we can use these tools to express Pfaffians and determinants and to derive various non-trivial identities in combinatorics and combinatorial physics (deletion/contraction relation for graph polynomial, Desnanot-Jacobi identities etc.).

Désiré André (dans son article de 1879) a montré que le développement en série de tan(x) et sec(x) est lié à une jolie suite combinatoire, les nombres Eulériens, qui comptent le nombre de permutations alternées. J'introduis un nouvel algorithme, basé sur des idées de théorie des probabilités, qui permet d'engendrer une telle permutation de longueur n en temps n log n. Je montrerai que l'idée peut aussi s'étendre à d'autres classes de permutations contraintes.

Using a quantum field theory renormalization group-like differential equation, we give a new proof of the recipe theorem for the Tutte polynomial for matroids. The solution of such an equation is in fact given by some appropriate characters of the Hopf algebra of isomorphic classes of matroids, characters which are then related to the Tutte polynomial for matroids.

The enumeration of lattice walks in restricted regions is an elegant problem which has been the subject of much attention. In this talk we survey recent results on lattice walks in the quarter plane, regarding the analytic properties of their generating functions. Specifically, we discuss the classification of walks whose generating functions satisfy linear differential equations, and why this property is desirable.

Dans les années 70, Ammann et Penrose ont indépendamment découvert deux losanges légèrement déformés qui permettent de paver le plan (c'est-à-dire de le couvrir en entier sans que les losanges ne se superposent), mais seulement de façon non-périodique. De Bruijn a par la suite montré que ces pavages pouvaient être vus comme des discrétisations d'un plan totalement irrationnel de l'espace euclidien à cinq dimensions. Nous montrerons comment, dans cet espace, les déformations de ces losanges se traduisent en contraintes géométriques simples qui permettent de retrouver le résultat de De Bruijn par une méthode différente, plus générique. Pour illustrer cette généricité, nous présenterons une variante des losanges de Ammann et Penrose dont les pavages peuvent être vus comme des discrétisations d'une famille à deux paramètres de plans de l'espace euclidien à cinq dimensions. Il s'agit d'un travail en commun avec Nicolas Bédaride (LATP, Marseille).

In their recent paper proving the connective constant mu of self-avoiding walks (SAWs) on the hexagonal (honeycomb) lattice, Duminil-Copin and Smirnov consider the generating function of self-avoiding bridges which span a strip of width T, and conjecture that this generating function vanishes at 1/mu in the large T limit. This generating function was again considered by Bousquet-Mélou, de Gier, Duminil-Copin, Guttmann and myself when we studied the adsorption of SAWs onto an impenetrable surface, and we proved the conjecture of Duminil-Copin and Smirnov. I will discuss this conjecture and its proof, as well as what happens after rotating the lattice by pi/4. http://arxiv.org/abs/1109.0358 http://arxiv.org/abs/1210.0274

Le livre "Analytic Combinatorics" de Flajolet et Sedgewick propose un cadre agréable -- la Méthode Symbolique -- pour définir des classes d'objets combinatoires à partir de grammaires (systèmes combinatoires) semblables à celles de la théorie des langages. En se plaçant dans ce cadre, il est possible d'effectuer un certain nombre de traitements quasi-automatiques sur ces objets : manipulation de séries génératrices, génération aléatoire, analyse asymptotique, ... Cependant, lorsqu'il s'agit d'implanter de telles méthodes, il est nécessaire de se poser la question: comment savoir si un système combinatoire donné est "bien formé" ? Cette question nous a amenés à considérer une autre approche permettant de décrire des objets combinatoires : la théorie des espèces de structures. Bien qu'étudiées à des fins très différentes, ces deux approches présentent de nombreux points communs et permettent, lorsqu'elles sont associées, de fournir une base de travail solide pour l'automatisation d'un certain nombre de traitements combinatoires. Dans cet exposé, nous présenterons ces deux approches et nous décrirons les passerelles menant de l'une à l'autre, dans le but de caractériser les systèmes qui décrivent effectivement des structures combinatoires. Cette présentation est basée sur un travail en commun avec B. Salvy et M. Soria.

Le livre "Analytic Combinatorics" de Flajolet et Sedgewick propose un cadre agréable -- la Méthode Symbolique -- pour définir des classes d'objets combinatoires à partir de grammaires (systèmes combinatoires) semblables à celles de la théorie des langages. En se plaçant dans ce cadre, il est possible d'effectuer un certain nombre de traitements quasi-automatiques sur ces objets : manipulation de séries génératrices, génération aléatoire, analyse asymptotique, ... Cependant, lorsqu'il s'agit d'implanter de telles méthodes, il est nécessaire de se poser la question: comment savoir si un système combinatoire donné est "bien formé" ? Cette question nous a amenés à considérer une autre approche permettant de décrire des objets combinatoires : la théorie des espèces de structures. Bien qu'étudiées à des fins très différentes, ces deux approches présentent de nombreux points communs et permettent, lorsqu'elles sont associées, de fournir une base de travail solide pour l'automatisation d'un certain nombre de traitements combinatoires. Dans cet exposé, nous présenterons ces deux approches et nous décrirons les passerelles menant de l'une à l'autre, dans le but de caractériser les systèmes qui décrivent effectivement des structures combinatoires. Cette présentation est basée sur un travail en commun avec B. Salvy et M. Soria.

Consider the uniform random graph G(n,M) with n vertices and M edges. Erdős and Rényi (1960) conjectured that when n goes to infinity, then the limit of "Pr(G(n,n/2) is planar" exists and is a constant strictly between 0 and 1. Łuczak, Pittel and Wierman (1994) proved this conjecture and Janson, Łuczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this talk we show how to determine the exact probability of a random graph beingplanar near the critical point M=n/2. More exactly, for each λ, we find an exact analytic expression for p(λ) = \lim_{n \to \infty} \Pr{G(n,n/2 (1+λ n^{-1/3})) is planar}. In particular, we obtain p(0) \approx 0.99780. If time permits we will show extensions of these techniques and further research. This is joint work with Marc Noy (UPC-Barcelona) and Vlady Ravelomanana (LIAFA-Paris)

The theoretical setting of his talk is based essentially on the paper - http://hal.archives-ouvertes.fr/hal-00193180/ - published in a workshop about Combinatorial Physics [1]. This setting was used to prove, with Christophe Reutenauer, a conjecture by Alain Connes [2]. We give new insights and applications of this concept.
[1] G.H.E. Duchamp and C. Tollu, Sweedler’s duals and Schützenberger’s calculus, In K. Ebrahimi-Fard, M. Marcolli and W. van Suijlekom (eds), Combinatorics and Physics, p. 67–78, Amer. Math. Soc. (Contemporary Mathematics, vol. 539), 2011.
[2] G. Duchamp, C. Reutenauer, Un critère de rationalité provenant de la géométrie non-commutative (à la mémoire de Schützenberger), Inventiones Mathematicae, 128, 613-622, (1997).

Nous donnons une formule précise pour le nombre total des mots de rotation engendrés par deux intervalles. Le résultat utilise les travaux de Berstel et Pocchiola sur les mots sturmiens. Il continue aussi un résultat par Cassaigne et Frid (2007) sur le comptage des mots de rotation dont l'intervalle est fixé. [Travail commun avec D. Jamet]

In classical Lie groups, the product of one-parameter groups wrt any basis of the tangent Lie algebra provides an open mapping which gives at once a system of local coordinates. We discuss the transposition of this process to the Hausdorff (profinite) Lie group with several combinatorial alphabets.

Ce "salon de thé combinatoire" avec petits gâteaux et grandes questions se veut un groupe de travail libre autour de la combinatoire. Ce salon est ouvert à tous, chacun pouvant exposer de manière décontractée ses travaux en cours, ses problèmes ouverts, ses lectures scientifiques... Nous souhaitons un lieu de partage convivial et actif. Un lieu où l'on peut lancer des idées, poser des questions naïves ou profondes sans crainte. En d'autres termes, un lieu où faire de la recherche !

What Philippe Flajolet popularized as the "Drmota-Lalley-Woods theorem" gives a kind generalisation of the Perron-Frobenius theory (rational world) to polynomial system of equations (algebraic world). It establishes a universal behaviour (square singularity, Gaussian limit law). This talk will deal with systems of functional equations in finitely or infinitely many random variables arising in combinatorial enumeration problems. We prove sufficient conditions under which the combinatorial random variables encoded in the generating function of the system tend to a finite or infinite dimensional limiting distribution. The proofs use a pinch of complex analysis and functional analysis. [Joint work with Michael Drmota and Johannes Morgenbesser]

In recent years there has been increasing interest in the asymptotic analysis of (several classes of) planar maps and planar graphs. This was initiated by bijective methods (e.g. the Shaeffer bijection), generating function methods (e.g. Gimenez and Noy's result on the asymptotics of number of planar graphs) and the search for probabilistic limiting objects (e.g. the Brownian map by Le Gall). In particular in the discussion of several planar graph classes (like series-parallel graphs or labelled planar graphs) a dichotomy between a "critical" and "subcritical" behaviour between 2-connected and connected graphs was observed. Informally a graph class is subcritical when all 2-connected components are small (i.e., at most of log n - size) and one observes a "treelike structure". Conversely a graph class is critical when the largest 2-connected component is comparable to the size of the whole graph. The purpose of this talk is to discuss the asymptotic behaviour of several (extremal) parameters of subcritical and critical graph classes, in particular the diameter and the maximum degree. For subcritical graph classes the diameter is (usually) of oder n^(1/2) whereas we can expect the order n^(1/4) in the critial case. On the other hand the maximum degree is (usually) of order log n in both cases. However, critical graph classes are notoriously more difficult to handle than subcritical ones. This talk is mainly based on joint work with Omer Gimenez, Marc Noy, Konstantinos Panagiotou, and Angelika Steger.

Dans cet exposé, nous présentons un théorème relatif à un critère d'indépendance linéaire des coefficients d'une solution d'une équation différentielle non commutative. Ce théorème a pour conséquence l'indépendance linéaire des polylogarithmes et de leur généralisation, les hyperlogarithmes, sur des corps de fonctions. Dans la suite nous regardons à travers le miroir pour avoir des renseignements sur les dérivations.

Nous devons comprendre les aspects du théorème de CQMM préparatoires à l'implémentation. Cela passe par une phase d'analyse/conception des différentes réécritures qui lui sont liées.

Nous devons comprendre les aspects du théorème de CQMM préparatoires à l'implémentation. Cela passe par une phase d'analyse/conception des différentes réécritures qui lui sont liées.

Les constantes de structure (ou coefficients de linéarisation) de certaines algèbres (comme les fonctions rationnelles nulles à l'infini) ont une riche combinatoire que nous nous proposons d'illustrer et de discuter sur quelques exemples.