Programme

Les exposés commenceront le mercredi à 9 heures pour se terminer le vendredi à 12h. Le mercredi et le jeudi, les exposés finiront à 17 heures. Le programme est aussi disponible au format pdf.

Mercredi 25 janvier

Résumé

Dans cet exposé, je vais utiliser les théories classiques de Viennot pour les polynômes orthogonaux à une variable et leurs moments. Une extension de cette théorie permet de construire des polynômes orthogonaux multivariés, qui sont les polynômes de Koornwinder pour $q=t$. Le point clé de cette construction est une formule de Cauchy pour les polynômes de Koornwinder due à Mimachi et une formule de Jacobi-Trudi pour la 9e variation des fonctions de Schur, fonctions dues à Nakagawa, Noumi, Shirakawa et Yamada.

Travail en commun avec Olya Mandelshtam et Lauren Williams.

Résumé
Let T be any simply generated tree. Write vol(T) for the volume of T (the number of nodes), ht(T) for the height of T (the greatest distance of any node from the root) and wid(T) for the width of T (the greatest number of nodes at any level). We study the relation between vol(T), ht(T) and wid(T).
In the case when T may be represented as a Galton-Watson tree whose offspring distribution p = (p_i, i \geq 0) has mean one and finite variance, both ht(T) and wid(T) are typically of order vol(T)^{1/2}, and have sub-Gaussian upper tails on this scale (A-B, Devroye and Janson, 2013). Heuristically, as the tail of the offspring distribution becomes heavier, the tree T becomes “shorter and bushier'”. We describe a handful of theorems which can be viewed as justifying this heuristic. In particular, we show that the random variable ht(T)/wid(T) always has sub-exponential tails and, more strongly, the random variable ht(T)/vol(T)^{1/2} always has sub-Gaussian tails. The proofs are probabilistic, but a combinatorial approach may well yield stronger and (even) more general results.
Résumé

On s'intéresse à des densités d'ensembles définis via la fonction somme des chiffres en base deux $s_2$. Plus précisément, pour chaque entier naturel $a$ et pour chaque entier relatif $d$, on s'intéresse à la densité de l'ensemble des entiers naturel $n$ tels que $s_2(n+a)-s_2(n)=d$. On appelle cette densité $\mu_a(d)$ et on remarque que $\mu_a$ est une mesure de probabilité sur $\mathbb{Z}$. Ces ensembles interviennent naturellement en arithmétique, notamment dans les travaux de Bésineau sur les corrélations de certaines fonctions arithmétiques. Ici notre approche est différente et nous faisons d'abord une étude combinatoire des solutions de $s_2(n+a)-s_2(n)=d$. Ceci permet d'exprimer $\mu_a$ comme produit de matrices. À partir de cette expression nous donnons des propriétés asymptotiques de cette mesure de probabilité lorsque $a$ tend vers l'infini (en un sens plus précis que nous définirons). Par exemple nous montrons que la norme $l^2$ de cette mesure tend vers zéro lorsque $a$ tend vers l'infini. Nous avons par ailleurs des bornes sur la variance de $\mu_a$ pour $a$ “assez grand”. Enfin, dans un travail en commun avec Pascal Hubert reprenant ces résultats, nous montrons que $\mu_a$ vérifie un théorème central limite.

Repas salle 76, LaBRI

Résumé
Les coefficients de nombreuses séries holonomes, hypergéométriques ou pas, satisfont à des congruences (modulo des nombres premiers) analogues à celles classiques de Lucas concernant les coefficients binomiaux. Elles se généralisent également, en considérant des congruences modulo des polynômes cyclotomiques, à des q-analogues de telles séries. De nombreux articles sont consacrés à l’étude de ces différentes congruences dans des cas particuliers.
Dans cet exposé, je présenterai un résultat général très simple permettant de retrouver la plupart d’entre elles par un argument de spécialisation. Je décrirai ensuite comment ces congruences conduisent à des résultats d’indépendance algébrique concernant les séries génératrices sous-jacentes.
Il s’agit de travaux communs avec J. Bell, E. Delaygue et F. Jouhet.
Résumé

I’ll present a surprising corollary to results by Borot, Bouttier, Duplantier, and Guitter on the O(n) loop model on random bipartite planar maps: some of the generating functions can be naturally interpreted as counting simple walks on the square lattice while keeping track of the winding angle around the origin. Applications include: a combinatorial derivation of the hyperbolic secant law of the winding of a simple random walk; counting of walks on cones of various angles. In particular, I will show how one can reproduce a generating function for the Gessel numbers, which count walks starting and ending at the origin in 3*Pi/4-cone.

Résumé
Power domination in graphs emerged from the problem of monitoring an electrical system by placing as few measurement devices in the system as possible. Given a set S of vertices of a graph, a set M of vertices is built as follows: at first, M = N [S], and then iteratively a vertex v is added to M if v has a neighbor u in M such that v is the only neighbor of u not in M . Such a set S is said to be power dominating for a graph G if all vertices of G are in M at the end of the process. The power domination number of a graph is the minimum size of a power dominating set. In this talk, I will give an algorithm computing a power dominating set of size at most $(n−2)/4$ for any maximal planar graph of order n ≥ 6.

Jeudi 26 janvier

Résumé
Dans un graphe plongé sur une surface, un cycle de partage est un cycle qui sépare le plongement en deux parties connexes de genre strictement plus petit que la surface de départ. Par exemple, un cycle de partage d’un graphe plongé sur un double tore séparera la surface en deux tores troués. En général, il n'est pas évident qu’un plongement donné contient un cycle de partage. Il a été conjecturé par Barnette que si le plongement était une triangulation alors il devait contenir un tel cycle. Je donnerai des contre-exemples à une version forte de cette conjecture. Ces contre-exemples utilisent les plongements des graphes complets qui ont servi a démontrer la conjecture de Heawood. Je donnerai aussi des détails sur la construction de ces plongements.
Résumé

I will present an analytical study of the statistics of increments in record values in a time series $x_0=0,x_1, x_2, ..., x_n$ generated by the positions of a random walk (discrete time, continuous space) of duration $n$ steps. For arbitrary jump length distribution, including Lévy flights, we show that the distribution of the record increment becomes stationary, i.e., independent of $n$ for large $n$, and compute it explicitly for a wide class of jump distributions. In addition, we compute exactly the probability $Q(n)$ that the record increments decrease monotonically up to step $n$. Remarkably, $Q(n)$ is universal (i..e., independent of the jump distribution) for each $n$, decaying as $A/\sqrt{n}$ for large $n$, with a universal amplitude $A = e/\sqrt{\pi} = 1.53362…..$ If time allows, I will also discuss the case where the time series ${x_0=0,x_1, x_2, ..., x_n}$ is generated by i.i.d. random variables.

Résumé
Pour étudier ou manipuler un objet géométrique, il est souvent utile de lui associer un objet combinatoire qui souligne certaines de ses propriétés. J'illustrerai cette idée sur l'analyse des motifs d'intersection de sous-ensembles de l'espace. D'après un théorème de Helly, il est impossible de trouver 4 convexes du plan qui se coupent 3 à 3 (ou d+2 convexes de R^d qui se coupent (d+1) à (d+1)) sans qu´ils n'aient tous un point en commun. Cette propriété donne lieu à de très nombreuses généralisations, relaxant par exemple la convexité. J'esquisserai la manière dont des outils de combinatoire topologique (plongement de graphes et de complexes simpliciaux, homologie des complexes de nerf et théorème du nerf) permettent d'unifier une bonne part de ces résultats.

Repas salle 76, LaBRI

Résumé
Étant donné un graphe F, nous étudions le nombre de copies de F qui sont sous-graphes d’un grand graphe aléatoire. Cette question a été d'abord étudiée par Erdős and Rényi (1960), puis par de nombreux chercheurs, dont Bollobás, Alon, Ruciński, Janson et Łuczak. L'approche probabiliste a été privilégiée dans ces travaux. Nous suivons une approche différente, basée sur l'étude de la série génératrice des graphes où le nombre de sous-graphes copies de F est marqué.
Résumé
Nous présentons des formules exactes pour les séries génératrices bivariées des permutations et involutions affines évitant le motif 321, par rapport au rang et au nombre d’inversions. Nous utilisons deux méthodes basées sur la théorie des empilements de pièces de Viennot. Il s’agit d’un travail en collaboration avec F. Jouhet et P. Nadeau.
Résumé

A matrix $M$ of real numbers is called totally positive if every minor of $M$ is nonnegative; I will call a matrix $M$ of polynomials (in some set of indeterminates) coefficientwise totally positive if every minor of $M$ is a polynomial with nonnegative coefficients. I will call a sequence $(a_n)_{n \ge 0}$ of real numbers (or polynomials) (coefficientwise) Hankel-totally positive if the Hankel matrix $H = (a_{i+j})_{i,j \ge 0}$ is (coefficientwise) totally positive. The (coefficientwise) Hankel-total positivity of a sequence $(a_n)_{n \ge 0}$ implies its (coefficientwise) log-convexity, but is much stronger. (For sequences of real numbers, Hankel-total positivity is equivalent to being a Stieltjes moment sequence.)

I will point out a simple sufficient condition for the (coefficientwise) total positivity of a Hankel matrix, based on expanding the power series $\sum_{n=0}^\infty a_n t^n$ into a Stieltjes-type or Jacobi-type continued fraction. As a consequence I can show that many sequences of polynomials arising in enumerative combinatorics are coefficientwise Hankel-totally positive; this approach also gives combinatorial interpretations of all the Hankel minors, and explicit formulae for the first few leading principal minors.

I conclude by giving some examples of sequences of combinatorial polynomials that appear empirically to be Hankel-totally positive but which cannot be handled by this continued-fraction approach. Foremost among these are the inversion enumerator for trees, $I_n(y)$, which is related to the generating polynomials $C_n(v)$ of connected graphs.

Vendredi 26 janvier

Résumé

On considère un 2n-gone P avec des sommets alternativement coloriés en rouge et en bleu, et une dissection D de P dont toutes les diagonales relient deux sommets rouges. Le complexe d'accordéon de D est le complexe simplicial des dissections de P utilisant des diagonales aux extrémités bleues, et qui croisent chacune un accordéon de D (ensemble connexe de diagonales). Lorsque toutes les cellules internes de D sont des triangles, ce complexe est l'associaèdre classique. Les complexes d'accordéons ont été introduit par A. Garver et T. McConville afin d'étudier des structures de treillis sur leur graphe des flips. Dans cet exposé, je présenterai des réalisations géométriques des complexes d'accordéons, comme polytopes et comme éventails simpliciaux, basées sur des idées inspirées de la théorie des algèbres amassées. Travail en commun avec Vincent Pilaud (CNRS & LIX, École Polytechnique).

Résumé
Tait conjectured in 1884 that each cubic planar graph contains a Hamilton cycle. Had the conjecture been true, it would have implied the Four Color Theorem. However, it was disproved by Tutte in 1946. Later on, other counterexamples with different structural properties were found. On the other hand, for several subclasses of cubic planar graphs hamiltonicity was proven. In general, the problem of finding a Hamilton cycle in a cubic planar graph turned out to be NP-complete.
All known conterexamples to Tait’s conjecture contain odd cycles and faces of large size. That’s why Barnette formulated in the 60s two conjectures in the form of sufficient conditions for the hamiltonicity of cubic planar graphs: He conjectured that bipartite cubic planar graphs, as well as cubic planar graphs with faces of size at most 6, are hamiltonian. We will present results, methods and ideas leading to a computer-assisted proof of the latter.
Résumé

La dynamique symbolique est l'étude des décalages, qui sont des ensembles de coloriages de Z^d ou d’un groupe de type fini par un alphabet fini, respectant certaines contraintes locales. Pour montrer qu’un décalage n'est pas vide, il suffit donc d'expliciter un coloriage respectant ces contraintes. Dans cet exposé je présenterai en quoi le lemme local de Lovász peut aider en ce sens. Je montrerai par exemple l'existence d’un décalage fortement apériodique sur tout groupe de type fini. Il s'agit d’un travail en collaboration avec Sebastián Barbieri et Stéphan Thomassé.