2012 – 2013

Le séminaire a eu lieu les jeudis 27 septembre 2012, 6 décembre 2012, 31 janvier 2013, 28 mars 2013, et 6 juin 2013.

27 septembre 2012

• Patrick Dehornoy (Université de Caen),
  Combinatoire des tresses et des structures de Garside.
  Transparents.

On passera en revue quelques problèmes combinatoires mettant en jeu les groupes de tresses et, plus généralement, les structures de Garside dont ils fournissent des exemples. Le point commun unificateur est l'existence pour les éléments des structures considérées d'un certain type de forme normale définie par des conditions locales et, de ce fait, liée à un automate et à une série rationnelle. Si le temps le permet, on mentionnera une application à des résultats de non-prouvabilité un peu paradoxaux.

• Konstantinos Panagiotou (LMU Munich),
  Catching the k-NAESAT Threshold.
  Transparents.

The best current estimates of the thresholds for the existence of solutions in random constraint satisfaction problems ('CSPs') mostly derive from the first and the second moment method. Yet apart from a very few exceptional cases these methods do not quite yield matching upper and lower bounds. According to deep but non-rigorous arguments from statistical mechanics, this discrepancy is due to a change in the geometry of the set of solutions called condensation that occurs shortly before the actual threshold for the existence of solutions. To cope with condensation, physicists have developed a sophisticated but non-rigorous formalism called Survey Propagation, which yields precise conjectures on the threshold values of many random CSPs. In this talk I will discuss a new Survey Propagation inspired method for the random k-NAESAT problem, which is one of the standard benchmark problems in the theory of random CSPs. This new technique allows us to overcome the barrier posed by condensation rigorously, and prove very accurate estimates for the k-NAESAT threshold; in particular, we verify the statistical mechanics conjecture for this problem.

Joint work with Amin Coja-Oghlan.

• Michel Bauer (IPHT CEA/DSM),
  Variables échangeables, martingales et mesures non-destructives en mécanique quantique.
  Transparents.

Plus de 80 ans après la découverte des lois de la mécanique quantique, celles-ci continuent de susciter l'étonnement. La notion de mesure en particulier, reste très mystérieuse. Des expériences récentes très simples et belles, que nous décrirons brièvement, permettent de lever légèrement un coin du voile. Après avoir présenté, pour des non-physiciens, les notions de base de la mécanique quantique, nous montrerons pourquoi l'interprétation de ces expériences est étroitement liée à la théorie des variables échangeables, au théorème de de Finetti et au théorème de convergence des martingales.

6 décembre 2012

• Brigitte Chauvin (Université de Versailles),
  Des arbres dans les urnes de Pólya et réciproquement.
  Transparents.

Les urnes de Pólya se prêtent à de nombreuses approches : par combinatoire analytique, on obtient une description exacte de la composition de l'urne à un instant $n$ fini. C'est plutôt une description par tranche. Quand les systèmes différentiels obtenus se résolvent, c'est magique.
La vision probabiliste conduit plutôt à des résultats sur le comportement global limite de l'urne quand $n$ tend vers l'infini. Nous verrons qu'une transition de phase existe, entre les « petites urnes » à asymptotique Gaussienne et les «grandes urnes», pour lesquelles l'asymptotique du vecteur composition de l'urne fait apparaître une variable aléatoire limite $W$ dont la loi est non classique. L'étude probabiliste repose sur la mise en évidence de la structure arborescente de l'évolution de l'urne. Un raisonnement de type «diviser pour régner» conduit à écrire des équations de point fixe en loi pour $W$, qui ont un intérêt en elles-mêmes et qui donnent des indications sur $W$ (densité, moments) et aussi des conjectures. Enfin plonger l'urne en temps continu produit un processus de branchement dont les agréables propriétés d'indépendance conduisent à d'autres équations de point fixe en loi, pas tout à fait les mêmes qu'en temps discret. Lorsqu'on traduit ces équations sur la transformée de Fourier de $W$, le système différentiel obtenu se résout, faisant avancer la compréhension de $W$.
Travail commun avec Quansheng Liu, Cécile Mailler et Nicolas Pouyanne.

• Marni Mishna (Simon Fraser University),
  D-finite by design.

D-finite functions satisfy linear differential equations with polynomial coefficients. As innocuous as that might sound, they have been a rich treasure trove for number theorists, computer algebraists, and combinatorialists. Despite deep investigations from several different angles, they still hold many mysteries. For example, Gilles Christol conjectured over 20 years ago that all D-finite globally bounded functions are diagonals of rational functions. This would imply that combinatorial classes with D-finite generating functions are very structured, but yet we have no firm grasp on the anatomy of such classes. This talk will examine the hypothesis using recent developments in lattice path enumeration, in particular the orbit sum variant of the kernel method, amongst other combinatorial evidence. We will also look at the flip side, and describe some techniques to prove that generating functions are not D-finite.

• Michèle Vergne (Institut de Mathématiques de Jussieu),
  Continuation analytique de polytopes.
  Transparents. Synthèse.

Soit $P(b)$ un polytope défini par $N$ inéquations linéaires $(\mu_1, x) \leq b_1$, $(\mu_2, x) \leq b_2 ,\ldots, (\mu_N, x) \leq b_N$. Lorsque le paramètre $b$ varie dans un petit voisinage du paramètre initial $b^0$, le polytope $P(b)$ garde la même forme. En particulier, son volume $vol(b)$ est donné par une fonction polynomiale de $b$, lorque $b$ est proche de la valeur $b^0$. Ce polynôme change lorsque $b$ passe un mur. Varchenko a défini une "continuation analytique" $AP(b)$ de $P(b)$ : une réunion signée de polytopes $Q_i(b)$, de diverses dimensions. Si $b$ est proche de $b^0$, $AP(b) = P(b)$, mais $AP(b)$ est "analytique" en $b$. Par exemple le volume de $AP(b)$ (une somme signée de volumes) est un polynôme en $b$ pour tout $b\in \mathbb{R}^{N}$. Nous avons donné une formule de saut pour $AP(b)$. Cette étude est une version ensembliste de la variation en fonction du fibré en lignes $L$ du support du module $\sum_i (-1)^i H_i(M,O(L))$ lorsque $M$ est une variété torique. En particulier, on retrouve les formules de saut de Paradan pour le nombre de points entiers dans le polytope $P(b)$, lorsque le paramètre $b$ passe un mur. 

Travail commun avec Nicole Berline.

31 janvier 2013

• Philippe Chassaing (IECN),
  The height of the Lyndon tree.
  Transparents. Synthèse.

We consider the set $L_n$ of n-letters long Lyndon words on the alphabet $\{0,1\}$. For a random uniform element $l_n$ of the set $L_n$, the binary tree obtained by successive standard factorization of $l_n$ and of the factors produced by these factorization is the Lyndon tree of $l_n$. We prove that the height $H_n$ of the Lyndon tree of $l_n$ satisfies $\lim_n (Hn/ \ln n) = \Delta$, in which the constant $\Delta$ is solution of an equation involving large deviation rate functions related to the asymptotics of Eulerian numbers ($\Delta \approx 5.091\ldots$). The convergence is the convergence in probability of random variables.

Joint work with Lucas Mercier.

• Valérie Berthé (LIAFA),
  Dynamique euclidienne : une approche symbolique.
  Transparents.

La transformation de Gauss (qui sous-tend le développement en fraction continue) a été très efficacement étudiée par Baladi-Vallée sous l'angle de l'analyse dynamique d'algorithmes. Le but de cet exposé est de montrer comment revisiter les résultats obtenus dans ce contexte sous l'angle de la dynamique symbolique.

• Éric Fusy (LIX),
  Bijections autour des bois de Schnyder.
  Transparents. Synthèse.

Les bois de Schnyder sont des structures combinatoires sur les triangulations planaires (aussi graphes planaires maximaux), introduites à l'origine par Schnyder pour fournir un nouveau critère de planarité. Ces structures se sont avérées également très pertinentes d'un point de vue algorithmique et elles bénéficient d'une riche combinatoire bijective que nous survoleront ici, ainsi que des généralisations à d'autres classes de graphes. 
Basé sur des travaux avec Olivier Bernardi, Dominique Poulalhon, et Gilles Schaeffer.

28 mars 2013

• Marc Lelarge (INRIA, DI ENS),
  Law of large numbers for matchings, extension and applications.
  Transparents. Synthèse.

The fact that global properties of matchings can be read from local properties of the underlying graph has been rediscovered many times in statistical physics, combinatorics, group theory and computer science. I will present a probabilistic approach allowing to derive law of large numbers. I will show how it extends previous results in several directions and describe some algorithmic applications.
Joint work with Charles Bordenave, Justin Salez, Mathieu Leconte, Laurent Massoulié, Hang Zhou.

• Federico Ardila (SFSU USA),
  Arithmetic Tutte polynomials of classical Coxeter groups.

Arithmetic Tutte polynomials of classical Coxeter groups The Tutte polynomial is a very important combinatorial invariant of an arrangement of hyperplanes. It encodes a great amount of enumerative, topological, and algebraic information about the arrangement - whether the underlying vector space is real, complex, or finite. The arithmetic Tutte polynomial, introduced by Moci in 2009, plays the analogous role for toric arrangements. We introduce a "finite field method" for computing arithmetic Tutte polynomials, and use it to compute these polynomials for the classical Coxeter groups. The talk will not assume previous knowledge of the subject.

Joint work with Federico Castillo (Los Andes / UC Davis) and Mike Henley (SFSU).

• Alin Bostan (SpecFun, INRIA Saclay),
  Computer Algebra for Lattice Path Combinatorics.
  Transparents. Synthèse.

Classifying lattice walks in restricted lattices is an important problem in enumerative combinatorics. Recently, computer algebra methods have been used to explore and solve a number of difficult questions related to lattice walks. In this talk, we will give an overview of recent results on structural properties and explicit formulas for generating functions of walks in the quarter plane, with an emphasis on the algorithmic methodology.

6 juin 2013

• Emmanuel Guitter (CEA Saclay),
  Énumération des cartes planaires irréductibles par découpage géodésique.
  Transparents.

Une carte $d$-irréductible est une carte dont tous les cycles ont une longueur au moins égale à $d$, et dont tous les cycles de longueur exactement $d$ sont des bords de faces. Je montrerai comment une technique éprouvée d'énumération des cartes, le découpage géodésique, peut être adaptée avec succès au cas des cartes $d$-irréductibles. Les briques élémentaires obtenues par découpage, les "slices", ont elles-mêmes une structure récursive, induisant un codage naturel des cartes $d$-irréductibles par des arbres. 

Cet exposé décrit un travail en commun avec J. Bouttier.

• Philippe Dumas (SpecFun, INRIA Saclay),
  Asymptotics of linear divide-and-conquer recurrences.
  Transparents. Synthèse.

Asymptotics of divide-and-conquer recurrences is usually dealt either with elementary inequalities or with sophisticated methods coming from analytic number theory. We propose a new approach based on linear algebra. The method is rather simple but able to catch the subtle oscillations arising in the context, as does the analytic approach. It is restricted to a class of divide-and-conquer sequences, namely the sequences rational with respect to a numeration system. This family is as basic as the classical rational sequences for the usual linear recurrences.

• Andrew Rechnitzer (University of British Columbia, Vancouver),
  Trivial words in groups.
  Transparents.

Random walks appear at the heart of many problems in mathematics. Perhaps one of the most famous questions is "What is the probability that a random walk returns to its starting point?"

For a random walk on the line or the square-grid, this question can be answered quite directly by recasting the problem as one of counting loops.
However on more complicated graphs the problem is far from trivial. In the setting of geometric group theory, this question is intimately tied to the problem of "amenability" and the number of trivial words. While amenability (and so the probability that a random walker returns) can be decided for many groups, it remains "very open" for Thompson's group $F$.

In this work, we apply numerical and enumerative methods from statistical mechanics and combinatorics to the study of random walks on groups and so examine the amenability of Thompson's group.

This is work together with Murray Elder, Buks van Rensburg and Thomas Wong. No prior knowledge of group theory or statistical mechanics required...