Journées de combinatoire de Bordeaux 2017 (JCB 2017)

Les JCB 2017 ont eu lieu du mercredi 25 au vendredi 27 janvier 2017. Les exposés ont eu lieu dans l’amphithéâtre du LaBRI (Bâtiment A30) à l’Université de Bordeaux.

Orateurs et résumés

Accéder au programme complet au format pdf.

• Sylvie Corteel (IRIF, Paris 7) Combinatoire des polynômes de Koornwinder pour $q=t$
  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.

• Louigi Addario-Berry (McGill, Montréal) Most trees are short and fat
  Résumé

  Let T be any simply generated tree. Write $\mathrm{vol}(T)$ for the volume of T (the number of nodes), $\mathrm{ht}(T)$ for the height of T (the greatest distance of any node from the root) and $\mathrm{wid}(T)$ for the width of T (the greatest number of nodes at any level). We study the relation between $\mathrm{vol}(T)$, $\mathrm{ht}(T)$ and $\mathrm{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 $\mathrm{ht}(T)$ and $\mathrm{wid}(T)$ are typically of order $\mathrm{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 $\mathrm{ht}(T)/\mathrm{wid}(T)$ always has sub-exponential tails and, more strongly, the random variable $\mathrm{ht}(T)/\mathrm{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.

• Jordan Emme (Institut de mathématiques de Marseille) Densités d’ensembles définis par la fonction somme des chiffres en base 2
  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.
• Boris Adamczewski (Institut Camille Jordan, Lyon) Congruences modulo des polynômes cyclotomiques et indépendance algébrique
  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.

• Timothy Budd (CEA Saclay) Winding of walks on the square lattice
  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.
• Claire Pennarun (LaBRI, Bordeaux) Power domination in triangulations
  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 for any maximal planar graph of order $n \geq 6$.
• Vincent Despré (LaBRI, Bordeaux) Cycles de partage dans les plongements de graphes complets
  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.
• Grégory Schehr (LPTMS, Paris Sud) Exact statistics of record increments of random walks
  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.
• Xavier Goaoc (LIGM, Marne-la-Vallée) Théorèmes de Helly et combinatoire topologique
  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 $\mathbb{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.
• Élie de Panafieu (Bell Labs France) Combinatoire analytique des graphes et de leurs sous-graphes
  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é.
• Riccardo Biagioli (Institut Camille Jordan, Lyon) Polyominos parallélogrammes périodiques et permutations affines évitant le motif 321
  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.
• Alan Sokal (Dept. of Physics, New York University) Coefficientwise total positivity (via continued fractions) for some Hankel matrices of combinatorial polynomials
  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.

• Thibault Manneville (École polytechnique, Palaiseau) Réalisations géométriques des complexes d’accordéons
  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).
• Frantisek Kardos (LaBRI, Bordeaux) Hamilton cycles in cubic planar graphs
  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.

• Nathalie Aubrun (ENS Lyon) Applications du lemme local de Lovász en dynamique symbolique
  Résumé

  La dynamique symbolique est l’étude des décalages, qui sont des ensembles de coloriages de $\mathbb{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é.

Emploi du temps

Mercredi 25 janvier

Jeudi 26 janvier

Vendredi 26 janvier

Informations pratiques

Accès et logement

Les exposés ont eu lieu dans l’amphithéâtre du LaBRI (bât. A30).

• Accès au LaBRI.
• Plan local des environs du LaBRI. Les stations de tramway les plus proches sont Forum et Béthanie.
• Une liste d’hôtels.

Taxis

• Taxi Talençais : 06 17 82 34 34
• Emile taxi : 06 72 38 82 27
• Taxis Girondins : 05 56 80 70 37

Restaurants

Plan interactif

• Proches du LaBRI: Plan
  • Le Bistro Régent, brasserie, en face du cinéma Gaumont.
  • Yamato, japonais en face du cinéma Gaumont.
  • L’Alcala, pizzeria, sur la place, de l’autre côté de l’arrêt de tram Forum.
  • La Parcelle, bar à vins sympa, charcuterie, fromages. Sur la place, de l’autre côté de l’arrêt de tram Forum.
  • L’Atelier du D, cuisine classique, en face de l’arrêt Forum.
  • Campo Verde, pizzeria, Cours Gambetta au Nord de l’arrêt Forum.
  • Le Carpe Diem, brasserie près de l’arrêt Béthanie.
  • Le 48, boulangerie près de l’arrêt Peixotto.
  • Le café bleu, crêperie un peu au Sud de l’arrêt Forum.
• Près du centre: Plan
  • Le Scopitone, 5 rue de la Vieille Tour (formule à 16 euros).
  • Le plat à oreilles, 8 rue des Faussets.
  • Le Cochon Volant, 22 place des Capucins, pour carnivores.
  • Le Croc Loup, rue du Loup (petit, il fallait réserver, fermé lundi).
  • La Belle Époque, angle sud des quais et des Quinconces.
  • Le Karma, rue du Pas St Georges, cuisine “fusion”.
  • Aux 4 coins du vin, rue de la Devise (très bon bar à vin, assiettes “diététiques” également).
  • A Cantina, restaurant XOR tapas, Corse.
  • Le Petit Commerce, rue du Parlement St-Pierre, restaurant et tapas, poisson & fruits de mer.
  • Elios, rue du Chapeau Rouge, sarde, très copieux.
  • La Brasserie du Sud Ouest, Cours de la Somme.
  • L’Estacade, restaurant sur pilotis, rive droite belle vue sur Bordeaux.
  • Le Café du Port, poissons et fruits de mer, rive droite au niveau du Pont de Pierre.
  • Le Café des Moines, bar à bières.

Participants

• Yvan Le Borgne (LaBRI, Université de Bordeaux, CNRS)
• Mireille Bousquet-Mélou (CNRS, LaBRI, U. Bordeaux)
• Vincent Delecroix (CNRS)
• Patxi Laborde-Zubieta (LaBRI)
• Henri Derycke (Labri)
• Élie de Panafieu (Bell Labs France, Nokia)
• Xavier Goaoc (LIGM, Université Paris Est)
• Thibault Manneville (LIX, Ecole Polytechnique)
• Jean-Christophe Aval (LaBRI, CNRS)
• David ILCINKAS (LaBRI, CNRS)
• Mohamed Lamine Lamali (LABRI)
• Bruno Courcelle (LaBRI)
• Olivier Guibert (LaBRI)
• Jean-François Marckert (LaBRI)
• Arnaud Casteigts (LaBRI)
• Cyril Banderier (LIPN, Univ Paris Nord/CNRS)
• Philippe Duchon (LaBRI, Université de Bordeaux)
• Louigi Addario-Berry (McGill University)
• Riccardo BIAGIOLI (ICJ - Université Lyon 1)
• Nathalie Aubrun (LIP, CNRS)
• Frederique Bassino (LIPN, Université Paris 13)
• Thomas Fernique (LIPN)
• Bérénice DELCROIX-OGER (INSTITUT DE MATHEMATIQUES DE TOULOUSE - IMT)
• Samuele Giraudo (LIGM, Université Paris-Est Marne-la-Vallée)
• Jean Bétréma (LaBRI *)
• Timothy Budd (CEA Saclay)
• Mathias Pétréolle (LaBRI, Université de Bordeaux)
• grégory schehr (LPTMS, CNRS-Univ. Paris Sud)
• Boris Adamczewski (CNRS, ICJ)
• Thierry Monteil (LIPN, CNRS)
• Srecko BRLEK (LaCIM, Université du Québec à Montréal)
• Adrian Tanasa (Labri, Univ. Bordeaux)
• Julien Courtiel (Laboratoire d’Informatique de Paris Nord)
• Sébastien Labbé (CNRS)
• Luis Fredes (LaBRI)
• Andrea Sportiello (LIPN, Université Paris 13)
• Valentin Bonzom (LIPN)
• Pierre Nicodeme (LIPN-Paris13)
• Philippe Nadeau (ICJ, CNRS)
• Gwendal Collet (Université de Vienne)
• Marthe Bonamy (LaBRI, CNRS)
• Claire Pennarun (LaBRI, Univ. Bordeaux)
• Jean-Florent Raymond (LIRMM et Université de Varsovie)
• Robert CORI (Labri)
• Paul Dorbec (LaBRI, CNRS-Univ. Bordeaux)
• Nicolas DUB (LIPN - Université Paris 13)
• Jean-Guy PENAUD (Labri)
• Alina Mayorova (LIX, Ecole Polytechnique)
• Christophe Cordero (LIGM)
• Arthur Nunge (LIGM)
• Philippe Marchal (LAGA, Université paris 13)
• Nicolas Bonichon (LaBRI - U. Bordeaux)
• Zakaria Chemli (LIGM)
• Sylvie Corteel (IRIF, CNRS)
• Axel Bacher (LIPN)
• Alexandre Zvonkine (LaBRI)
• Lucas Randazzo (LIGM)
• Gérard DUCHAMP (LIPN)
• Jordan Emme (i2m)
• Camille Male (IMB et CNRS)
• Alan Sokal (University College London)
• Sergey Dovgal (Université Paris 13)
• Jérôme Leroux (LABRI)
• LoadShardBlock: 1361.352 (3)
• PetaboxLoader3.resolve: 238.546 (3)
• PetaboxLoader3.datanode: 1220.195 (4)

Organisateurs

• Mireille Bousquet-Mélou
• Auriane Dantes
• Katel Guérin
• Yvan Le Borgne

Soutien financier

• LaBRI
• Projet ANR GRAAL
• Projet ANR JCJC Physique Combinatoire, des modèles de matrices aux modèles de tenseurs aléatoires
• Open DREAMKIt, projet européen H2020
• Département Sciences et techniques, Université de Bordeaux
• ALEA network Europe